forked from Kitware/VTK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vtkStaticEdgeLocatorTemplate.h
335 lines (296 loc) · 9.93 KB
/
vtkStaticEdgeLocatorTemplate.h
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
/*=========================================================================
Program: Visualization Toolkit
Module: vtkStaticEdgeLocatorTemplate.h
Copyright (c) Kitware, Inc.
All rights reserved.
See LICENSE file for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
/**
* @class vtkStaticEdgeLocatorTemplate
* @brief templated locator for managing edges and associated data on edges
*
*
* vtkStaticEdgeLocatorTemplate provides methods for ordering and tracking
* edges, as well as associating data with edges. (An edge is a tuple (v0,v1)
* with v0 < v1.) Typically this class may be used for isocontouring or any
* operation that operates on edges and needs to determine whether duplicates
* exist. The class is templated on 1) the type used to represent the id
* tuple; and 2) the data associated with the edge.
*
* This class is non-incremental (i.e., static). That is, an array of edges
* is provided and the locator is built from this array. Incremental
* additions of new edges is not allowed (analogoues to vtkStaticPointLocator
* and vtkStaticCellLocator).
*
* Finally, there are two distinct usage patterns for this class. One is to
* inject edges and then later search for them. This pattern begins with
* BuildLocator() and then is followed by repeated calls to IsInsertedEdge().
* Internally this operates on an array of EdgeTupleType. The second pattern
* operates on an array of MergeTupleType. It simply sorts the array using
* MergeEdges(), thereby grouping identical edges. An offset array is created
* that refers to the beginning of each group, hence indirectly indicating
* the number of unique edges, and providing O(1) access to each edge.
*
* @warning
* The id tuple type can be specified via templating to reduce memory and
* speed processing.
*
* @warning
* By default, a parametric coordinate T is associated with edges. By using
* the appropriate template parameter it is possible to associate other data
* with each edge. Note however that this data is not used when comparing and
* sorting the edges. (This could be changed - define appropriate comparison
* operators.)
*
* @warning
* This class has been threaded with vtkSMPTools. Using TBB or other
* non-sequential type (set in the CMake variable
* VTK_SMP_IMPLEMENTATION_TYPE) may improve performance significantly.
*
* @sa
* vtkEdgeTable vtkStaticPointLocator vtkStaticCellLocator
*/
#ifndef vtkStaticEdgeLocatorTemplate_h
#define vtkStaticEdgeLocatorTemplate_h
#include <vector>
#include <algorithm>
/**
* Definition of an edge tuple. Note that the TId template type may be
* specified to manage memory resources, and provide increased speeds (e.g.,
* sort) by using smaller types (32-int versus 64-bit vtkIdType). It is
* required that V0 < V1; the tuple constructor enforces this.
*/
template<typename TId, typename TED>
struct EdgeTuple
{
TId V0;
TId V1;
TED T;
// Default constructor - nothing needs to be done
EdgeTuple() {}
// Construct an edge and ensure that the edge tuple (vo,v1) is
// specified such that (v0<v1).
EdgeTuple(TId v0, TId v1, TED data) :
V0(v0), V1(v1), T(data)
{
if ( this->V0 > this->V1 )
{
TId tmp = this->V0;
this->V0 = this->V1;
this->V1 = tmp;
}
}
bool operator==(const EdgeTuple& et) const
{ return ( (this->V0 == et.V0 && this->V1 == et.V1) ? true : false ); }
bool IsEdge(TId v0, TId v1) const
{
if ( v0 < v1 ) //ordered properly
{
return ( (this->V0 == v0 && this->V1 == v1) ? true : false );
}
else //swap comparison required
{
return ( (this->V0 == v1 && this->V1 == v0) ? true : false );
}
}
// Sort on v0 first, then v1.
bool operator<(const EdgeTuple& tup) const
{
if ( this->V0 < tup.V0 ) return true;
if ( tup.V0 < this->V0 ) return false;
if ( this->V1 < tup.V1 ) return true;
return false;
}
};
/**
* Definition of an edge tuple using for creating an edge merge table. Note
* that the TId template type may be specified to manage memory resources,
* and provide increased speeds (e.g., sort) by using smaller types (32-int
* versus 64-bit vtkIdType). It is required that V0 < V1.
*/
template<typename TId, typename TED>
struct MergeTuple
{
TId V0;
TId V1;
TId EId; //originating edge id
TED T;
// Default constructor - nothing needs to be done
MergeTuple() {}
// Construct an edge and ensure that the edge tuple (vo,v1) is
// specified such that (v0<v1).
MergeTuple(TId v0, TId v1, TId eid, TED data) :
V0(v0), V1(v1), EId(eid), T(data)
{
if ( this->V0 > this->V1 )
{
TId tmp = this->V0;
this->V0 = this->V1;
this->V1 = tmp;
}
}
bool operator==(const MergeTuple& et) const
{ return ( (this->V0 == et.V0 && this->V1 == et.V1) ? true : false ); }
bool operator!=(const MergeTuple& et) const
{ return ( (this->V0 != et.V0 || this->V1 != et.V1) ? true : false ); }
// Sort on v0 first, then v1.
bool operator<(const MergeTuple& tup) const
{
if ( this->V0 < tup.V0 ) return true;
if ( tup.V0 < this->V0 ) return false;
if ( this->V1 < tup.V1 ) return true;
return false;
}
};
/**
* Templated on types of ids defining an edge, and any data associated with
* the edge.
*/
template <typename IDType, typename EdgeData>
class vtkStaticEdgeLocatorTemplate
{
public:
//@{
/**
* Some convenient typedefs.
*/
typedef EdgeTuple<IDType,EdgeData> EdgeTupleType;
typedef MergeTuple<IDType,EdgeData> MergeTupleType;
//@)
/**
* Construct an empty edge locator.
*/
vtkStaticEdgeLocatorTemplate() : NumEdges(0), NumEdgesPerBin(5),
EdgeArray(nullptr), EdgeOffsets(nullptr), MinV0(0), MaxV0(0), V0Range(0), NDivs(0),
MergeArray(nullptr) {}
/**
* Delete internal offset array. The edgeArray is provided from outside the
* class and so not deleted.
*/
~vtkStaticEdgeLocatorTemplate()
{
delete [] this->EdgeOffsets;
}
/**
* Return the number of edges in the edge array.
*/
IDType GetNumberOfEdges()
{ return this->NumEdges; }
/**
* This method sorts (in place) an array of MergeTupleType (of length
* numEdges) into separate groups, and allocates and returns an offset
* array providing access to each group. Each grouping is a list of
* duplicate edges. The method indicates the number of unique edges
* numUniqueEdges. Note that the offset array end value
* offsets[numUniqueEdges] = numEdges, i.e., total allocation of the
* offsets array is numUniqueEdges+1. Also note that the EId contained in
* the sorted MergeTuples can be used to renumber edges from initial ids
* (possibly one of several duplicates) to unique edge ids.
*/
const IDType *MergeEdges(vtkIdType numEdges, MergeTupleType *edgeArray,
vtkIdType &numUniqueEdges);
/**
* This method contructs the edge locator to be used when searching for
* edges. Basically it does a sort of the provided numEdges edges (which
* likely contains duplicates), and builds an offset table to provide rapid
* access to edge (v0,v1). The sort is performed via a parallel
* vtkSMPTools::Sort(). The provided array is modified in place. The
* method returns the number of unique edges.
*/
vtkIdType BuildLocator(vtkIdType numEdges, EdgeTupleType *edgeArray);
/**
* Return the id of the edge indicated. If the edge has not been inserted
* return <0. Note that the vertices (v0,v1) do not have to be in any
* particular (ascending/descending) order. BuildLocator() should be called
* prior to using this method.
*/
IDType IsInsertedEdge(IDType v0, IDType v1) const
{
// Ensure that data is consistent with what is expected.
IDType V0, V1;
if ( v0 < v1 )
{
V0 = v0;
V1 = v1;
}
else
{
V0 = v1;
V1 = v0;
}
if ( V0 < this->MinV0 || V0 > this->MaxV0 )
{
return -1;
}
// Bin and search for matching edge
IDType curBin = this->HashBin(V0);
IDType curId = this->EdgeOffsets[curBin];
IDType curV0 = this->EdgeArray[curId].V0;
IDType num = this->GetNumberOfEdgesInBin(curBin);
for ( IDType i=0; i < num; ++i )
{
while ( curV0 < V0 )
{
curId++;
curV0 = this->EdgeArray[curId].V0;
}
if ( curV0 > V0 )
{
return -1;
}
else //matched v0, now find v1
{
IDType curV1 = this->EdgeArray[curId].V1;
while ( curV1 < V1 )
{
curId++;
curV1 = this->EdgeArray[curId].V1;
}
if ( curV1 > V1 )
{
return -1;
}
else
{
return curId;
}
}
} //loop over maximum possible candidates
// Nothing found
return -1;
}
/**
* Return the ith edge in the edge array. Either obtain a non-negative
* value i from IsInsertedEdge(); or use 0<=i<NumberOfEdges().
*/
const EdgeTupleType& GetEdge(IDType i) const
{
return (*this->EdgeArray)[i];
}
protected:
vtkIdType NumEdges;
// Support BuildLocator usage pattern
vtkIdType NumEdgesPerBin;
EdgeTupleType *EdgeArray;
IDType *EdgeOffsets;
IDType MinV0;
IDType MaxV0;
IDType V0Range;
int NDivs;
IDType HashBin(IDType v) const
{ return ( (v - this->MinV0) / this->NumEdgesPerBin ); }
IDType GetNumberOfEdgesInBin(IDType bin) const
{ return (this->EdgeOffsets[bin+1] - this->EdgeOffsets[bin]); }
// Support MergeEdges usage pattern
MergeTupleType *MergeArray;
std::vector<IDType> MergeOffsets;
private:
vtkStaticEdgeLocatorTemplate(const vtkStaticEdgeLocatorTemplate&) = delete;
void operator=(const vtkStaticEdgeLocatorTemplate&) = delete;
};
#include "vtkStaticEdgeLocatorTemplate.txx"
#endif
// VTK-HeaderTest-Exclude: vtkStaticEdgeLocatorTemplate.h