1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
// This code is in the public domain -- castanyo@yahoo.es
#ifndef NV_MESH_WELD_H
#define NV_MESH_WELD_H
#include "nvcore/Array.h"
#include "nvcore/Hash.h"
#include "nvcore/Utils.h" // nextPowerOfTwo
#include <string.h> // for memset, memcmp, memcpy
// Weld function to remove array duplicates in linear time using hashing.
namespace nv
{
/// Generic welding routine. This function welds the elements of the array p
/// and returns the cross references in the xrefs array. To compare the elements
/// it uses the given hash and equal functors.
///
/// This code is based on the ideas of Ville Miettinen and Pierre Terdiman.
template <class T, class H=Hash<T>, class E=Equal<T> >
struct Weld
{
// xrefs maps old elements to new elements
uint operator()(Array<T> & p, Array<uint> & xrefs)
{
const uint N = p.size(); // # of input vertices.
uint outputCount = 0; // # of output vertices
uint hashSize = nextPowerOfTwo(N); // size of the hash table
uint * hashTable = new uint[hashSize + N]; // hash table + linked list
uint * next = hashTable + hashSize; // use bottom part as linked list
xrefs.resize(N);
memset( hashTable, NIL, hashSize*sizeof(uint) ); // init hash table (NIL = 0xFFFFFFFF so memset works)
H hash;
E equal;
for (uint i = 0; i < N; i++)
{
const T & e = p[i];
uint32 hashValue = hash(e) & (hashSize-1);
uint offset = hashTable[hashValue];
// traverse linked list
while( offset != NIL && !equal(p[offset], e) )
{
offset = next[offset];
}
xrefs[i] = offset;
// no match found - copy vertex & add to hash
if( offset == NIL )
{
// save xref
xrefs[i] = outputCount;
// copy element
p[outputCount] = e;
// link to hash table
next[outputCount] = hashTable[hashValue];
// update hash heads and increase output counter
hashTable[hashValue] = outputCount++;
}
}
// cleanup
delete [] hashTable;
p.resize(outputCount);
// number of output vertices
return outputCount;
}
};
/// Reorder the given array accoding to the indices given in xrefs.
template <class T>
void reorderArray(Array<T> & array, const Array<uint> & xrefs)
{
const uint count = xrefs.count();
Array<T> new_array;
new_array.resize(count);
for(uint i = 0; i < count; i++) {
new_array[i] = array[xrefs[i]];
}
swap(array, new_array);
}
/// Reverse the given array so that new indices point to old indices.
inline void reverseXRefs(Array<uint> & xrefs, uint count)
{
Array<uint> new_xrefs;
new_xrefs.resize(count);
for(uint i = 0; i < xrefs.count(); i++) {
new_xrefs[xrefs[i]] = i;
}
swap(xrefs, new_xrefs);
}
//
struct WeldN
{
uint vertexSize;
WeldN(uint n) : vertexSize(n) {}
// xrefs maps old elements to new elements
uint operator()(uint8 * ptr, uint N, Array<uint> & xrefs)
{
uint outputCount = 0; // # of output vertices
uint hashSize = nextPowerOfTwo(N); // size of the hash table
uint * hashTable = new uint[hashSize + N]; // hash table + linked list
uint * next = hashTable + hashSize; // use bottom part as linked list
xrefs.resize(N);
memset( hashTable, NIL, hashSize*sizeof(uint) ); // init hash table (NIL = 0xFFFFFFFF so memset works)
for (uint i = 0; i < N; i++)
{
const uint8 * vertex = ptr + i * vertexSize;
uint32 hashValue = sdbmHash(vertex, vertexSize) & (hashSize-1);
uint offset = hashTable[hashValue];
// traverse linked list
while (offset != NIL && memcmp(ptr + offset * vertexSize, vertex, vertexSize) != 0)
{
offset = next[offset];
}
xrefs[i] = offset;
// no match found - copy vertex & add to hash
if (offset == NIL)
{
// save xref
xrefs[i] = outputCount;
// copy element
memcpy(ptr + outputCount * vertexSize, vertex, vertexSize);
// link to hash table
next[outputCount] = hashTable[hashValue];
// update hash heads and increase output counter
hashTable[hashValue] = outputCount++;
}
}
// cleanup
delete [] hashTable;
// number of output vertices
return outputCount;
}
};
} // nv namespace
#endif // NV_MESH_WELD_H
|