vtkHyperOctree.h 20.4 KB
Newer Older
Francois Bertel's avatar
Francois Bertel committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkHyperOctree.h

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm 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.

=========================================================================*/
// .NAME vtkHyperOctree - A dataset structured as a tree where each node has
// exactly 2^n children.
// .SECTION Description
// An hyperoctree is a dataset where each node has either exactly 2^n children
19
20
// or no child at all if the node is a leaf. `n' is the dimension of the
// dataset (1 (binary tree), 2 (quadtree) or 3 (octree) ).
Francois Bertel's avatar
Francois Bertel committed
21
22
// The class name comes from the following paper:
//
Francois Bertel's avatar
Francois Bertel committed
23
// \verbatim
Francois Bertel's avatar
Francois Bertel committed
24
25
26
27
28
29
30
31
32
33
// @ARTICLE{yau-srihari-1983,
//  author={Mann-May Yau and Sargur N. Srihari},
//  title={A Hierarchical Data Structure for Multidimensional Digital Images},
//  journal={Communications of the ACM},
//  month={July},
//  year={1983},
//  volume={26},
//  number={7},
//  pages={504--515}
//  }
Francois Bertel's avatar
Francois Bertel committed
34
// \endverbatim
Francois Bertel's avatar
Francois Bertel committed
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
//
// Each node is a cell. Attributes are associated with cells, not with points.
// The geometry is implicitly given by the size of the root node on each axis
// and position of the center and the orientation. (TODO: review center
// position and orientation). The geometry is then not limited to an hybercube
// but can have a rectangular shape.
// Attributes are associated with leaves. For LOD (Level-Of-Detail) purpose,
// attributes can be computed on none-leaf nodes by computing the average
// values from its children (which can be leaves or not).
//
// By construction, an hyperoctree is efficient in memory usage when the
// geometry is sparse. The LOD feature allows to cull quickly part of the
// dataset.
//
// A couple of filters can be applied on this dataset: contour, outline,
// geometry.
//
// * 3D case (octree)
// for each node, each child index (from 0 to 7) is encoded in the following
// orientation. It is easy to access each child as a cell of a grid.
// Note also that the binary representation is relevant, each bit code a
// side: bit 0 encodes -x side (0) or +x side (1)
// bit 1 encodes -y side (0) or +y side (1)
// bit 2 encodes -z side (0) or +z side (2)
// - the -z side first
// - 0: -y -x sides
// - 1: -y +x sides
// - 2: +y -x sides
// - 3: +y +x sides
64
// \verbatim
Francois Bertel's avatar
Francois Bertel committed
65
66
67
68
69
70
//              +y
// +-+-+        ^
// |2|3|        |
// +-+-+  O +z  +-> +x
// |0|1|
// +-+-+
71
72
// \endverbatim
//
Francois Bertel's avatar
Francois Bertel committed
73
74
75
76
77
// - then the +z side, in counter-clockwise
// - 4: -y -x sides
// - 5: -y +x sides
// - 6: +y -x sides
// - 7: +y +x sides
78
// \verbatim
Francois Bertel's avatar
Francois Bertel committed
79
80
81
82
83
84
//              +y
// +-+-+        ^
// |6|7|        |
// +-+-+  O +z  +-> +x
// |4|5|
// +-+-+
85
86
// \endverbatim
//
Francois Bertel's avatar
Francois Bertel committed
87
88
89
90
91
92
93
94
// The cases with fewer dimensions are consistent with the octree case:
//
// * Quadtree:
// in counter-clockwise
// - 0: -y -x edges
// - 1: -y +x edges
// - 2: +y -x edges
// - 3: +y +x edges
95
// \verbatim
Francois Bertel's avatar
Francois Bertel committed
96
97
98
99
100
101
//         +y
// +-+-+   ^
// |2|3|   |
// +-+-+  O+-> +x
// |0|1|
// +-+-+
102
// \endverbatim
Francois Bertel's avatar
Francois Bertel committed
103
104
//
// * Binary tree:
105
// \verbatim
Francois Bertel's avatar
Francois Bertel committed
106
// +0+1+  O+-> +x
107
108
// \endverbatim
//
Francois Bertel's avatar
Francois Bertel committed
109
110
111
112
113
114
115
// .SECTION Caveats
// It is not a spatial search object! If you looking for this kind of
// octree see vtkCellLocator instead.

// .SECTION See Also
// vtkHyperOctreeAlgorithm

116
117
#ifndef vtkHyperOctree_h
#define vtkHyperOctree_h
Francois Bertel's avatar
Francois Bertel committed
118

119
#include "vtkCommonDataModelModule.h" // For export macro
Francois Bertel's avatar
Francois Bertel committed
120
121
#include "vtkDataSet.h"

122
class vtkHyperOctreeLightWeightCursor;
Francois Bertel's avatar
Francois Bertel committed
123
124
125
126
127
128
class vtkHyperOctreeCursor;
class vtkHyperOctreeInternal;
class vtkHyperOctreePointsGrabber;

class vtkHyperOctreeIdSet; // Pimpl idiom
class vtkPolygon;
129
130
class vtkIdTypeArray;
class vtkPoints;
131
class vtkPointLocator;
Francois Bertel's avatar
Francois Bertel committed
132
class vtkOrderedTriangulator;
133
134
135
136
137
138
class vtkDataSetAttributes;

class vtkLine;
class vtkPixel;
class vtkVoxel;
class vtkCellLinks;
Francois Bertel's avatar
Francois Bertel committed
139

140
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
Francois Bertel's avatar
Francois Bertel committed
141
142
143
144
145
146
{
public:
  static vtkInformationIntegerKey* LEVELS();
  static vtkInformationIntegerKey* DIMENSION();
  static vtkInformationDoubleVectorKey* SIZES();
  static vtkHyperOctree *New();
147

148
  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
149
  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
150

Francois Bertel's avatar
Francois Bertel committed
151
152
153
  // Description:
  // Return what type of dataset this is.
  int GetDataObjectType();
154

Francois Bertel's avatar
Francois Bertel committed
155
156
157
158
  // Description:
  // Copy the geometric and topological structure of an input rectilinear grid
  // object.
  void CopyStructure(vtkDataSet *ds);
159

Francois Bertel's avatar
Francois Bertel committed
160
161
162
163
164
  // Return the node describes by the path from the root.
  // Path is a sequence of number between 0 and 7.
  // \pre path_exists: path!=0
  // \pre node_exists: IsANode(path)
//  vtkOctree *GetNode(vtkPath *path);
165

166
  // Description:
Francois Bertel's avatar
Francois Bertel committed
167
168
169
170
  // Return the dimension of the tree (1D:binary tree(2 children), 2D:quadtree(4 children),
  // 3D:octree (8 children))
  // \post valid_result: result>=1 && result<=3
  int GetDimension();
171

172
173
  // Description:
  // Set the dimension of the tree with `dim'. See GetDimension() for details.
Francois Bertel's avatar
Francois Bertel committed
174
175
176
  // \pre valid_dim: dim>=1 && dim<=3
  // \post dimension_is_set: GetDimension()==dim
  void SetDimension(int dim);
177

Francois Bertel's avatar
Francois Bertel committed
178
179
180
  // Return if the node for the given path exists or not.
  // \pre path_exists: path!=0
//  int IsANode(vtkPath *path);
181

Francois Bertel's avatar
Francois Bertel committed
182
183
184
185
  // Return if the node for the given path is a leaf or not.
  // \pre path_exists: path!=0
  // \pre node_exists: IsANode(path)
//  int IsALeaf(vtkPath *path);
186

Francois Bertel's avatar
Francois Bertel committed
187
  // Measurement: topology
188

Francois Bertel's avatar
Francois Bertel committed
189
  // Description:
190
  // Return the number of cells in the dual grid.
Francois Bertel's avatar
Francois Bertel committed
191
192
  // \post positive_result: result>=0
  vtkIdType GetNumberOfCells();
193

Francois Bertel's avatar
Francois Bertel committed
194
  // Description:
195
196
  // Get the number of leaves in the tree.
  vtkIdType GetNumberOfLeaves();
197

198
199
  // Description:
  // Return the number of points in the dual grid.
Francois Bertel's avatar
Francois Bertel committed
200
201
  // \post positive_result: result>=0
  vtkIdType GetNumberOfPoints();
202

Francois Bertel's avatar
Francois Bertel committed
203
204
205
206
  // Description:
  // Return the number of points corresponding to an hyperoctree starting at
  // level `level' where all the leaves at at the last level. In this case, the
  // hyperoctree is like a uniform grid. So this number is the number of points
207
  // of the uniform grid.
Francois Bertel's avatar
Francois Bertel committed
208
209
210
  // \pre positive_level: level>=0 && level<this->GetNumberOfLevels()
  // \post definition: result==(2^(GetNumberOfLevels()-level-1)+1)^GetDimension()
  vtkIdType GetMaxNumberOfPoints(int level);
211

Francois Bertel's avatar
Francois Bertel committed
212
213
214
215
216
217
218
219
220
221
222
223
  // Description:
  // Return the number of points corresponding to the boundary of an
  // hyperoctree starting at level `level' where all the leaves at at the last
  // level. In this case, the hyperoctree is like a uniform grid. So this
  // number is the number of points of on the boundary of the uniform grid.
  // For an octree, the boundary are the faces. For a quadtree, the boundary
  // are the edges.
  // \pre 2d_or_3d: this->GetDimension()==2 || this->GetDimension()==3
  // \pre positive_level: level>=0 && level<this->GetNumberOfLevels()
  // \post min_result: result>=GetMaxNumberOfPoints(this->GetNumberOfLevels()-1)
  // \post max_result: result<=GetMaxNumberOfPoints(level)
  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
224

Francois Bertel's avatar
Francois Bertel committed
225
226
  // Description:
  // Return the number of cells corresponding to the boundary of a cell
227
  // of level `level' where all the leaves at at the last level.
Francois Bertel's avatar
Francois Bertel committed
228
229
230
  // \pre positive_level: level>=0 && level<this->GetNumberOfLevels()
  // \post positive_result: result>=0
  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
231

Francois Bertel's avatar
Francois Bertel committed
232
233
234
235
236
237
  // Description:
  // Return the number of levels.
  // \post result_greater_or_equal_to_one: result>=1
  vtkIdType GetNumberOfLevels();

  // Measurement: geometry
238

Francois Bertel's avatar
Francois Bertel committed
239
240
241
  // Description:
  // Set the size on each axis.
  vtkSetVector3Macro(Size,double);
242

Francois Bertel's avatar
Francois Bertel committed
243
244
245
  // Description:
  // Return the size on each axis.
  vtkGetVector3Macro(Size,double);
246

Francois Bertel's avatar
Francois Bertel committed
247
248
249
250
251
  // Description:
  // Set the origin (position of corner (0,0,0) of the root.
  vtkSetVector3Macro(Origin,double);
  // Return the origin (position of corner (0,0,0) ) of the root.
  vtkGetVector3Macro(Origin,double);
252

Francois Bertel's avatar
Francois Bertel committed
253
254
255
256
257
  // Description:
  // Create a new cursor: an object that can traverse
  // the cell of an hyperoctree.
  // \post result_exists: result!=0
  vtkHyperOctreeCursor *NewCellCursor();
258

Francois Bertel's avatar
Francois Bertel committed
259
260
261
262
263
264
  // Description:
  // Subdivide node pointed by cursor, only if its a leaf.
  // At the end, cursor points on the node that used to be leaf.
  // \pre leaf_exists: leaf!=0
  // \pre is_a_leaf: leaf->CurrentIsLeaf()
  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
265

Francois Bertel's avatar
Francois Bertel committed
266
267
268
269
270
271
272
  // Description:
  // Collapse a node for which all children are leaves.
  // At the end, cursor points on the leaf that used to be a node.
  // \pre node_exists: node!=0
  // \pre node_is_node: !node->CurrentIsLeaf()
  // \pre children_are_leaves: node->CurrentIsTerminalNode()
  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
273

Francois Bertel's avatar
Francois Bertel committed
274
275
276
277
278
  // Description:
  // Get point coordinates with ptId such that: 0 <= ptId < NumberOfPoints.
  // THIS METHOD IS NOT THREAD SAFE.
  virtual double *GetPoint(vtkIdType ptId);

279
  // Description:
Francois Bertel's avatar
Francois Bertel committed
280
281
282
283
284
  // Copy point coordinates into user provided array x[3] for specified
  // point id.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual void GetPoint(vtkIdType id, double x[3]);
285

Francois Bertel's avatar
Francois Bertel committed
286
287
288
289
290
291
  // Description:
  // Get cell with cellId such that: 0 <= cellId < NumberOfCells.
  // THIS METHOD IS NOT THREAD SAFE.
  virtual vtkCell *GetCell(vtkIdType cellId);

  // Description:
292
  // Get cell with cellId such that: 0 <= cellId < NumberOfCells.
Francois Bertel's avatar
Francois Bertel committed
293
294
295
296
297
  // This is a thread-safe alternative to the previous GetCell()
  // method.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual void GetCell(vtkIdType cellId, vtkGenericCell *cell);
298
299


Francois Bertel's avatar
Francois Bertel committed
300
301
302
303
304
305
306
307
308
309
310
  // Description:
  // Get type of cell with cellId such that: 0 <= cellId < NumberOfCells.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual int GetCellType(vtkIdType cellId);

  // Description:
  // Topological inquiry to get points defining cell.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds);
311
312
  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
                             vtkIdType* &pts);
Francois Bertel's avatar
Francois Bertel committed
313
314
315
316
317
318
319

  // Description:
  // Topological inquiry to get cells using point.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual void GetPointCells(vtkIdType ptId, vtkIdList *cellIds);

320

Francois Bertel's avatar
Francois Bertel committed
321
322
323
324
325
326
  // Description:
  // Topological inquiry to get all cells using list of points exclusive of
  // cell specified (e.g., cellId). Note that the list consists of only
  // cells that use ALL the points provided.
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
327
  virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
Francois Bertel's avatar
Francois Bertel committed
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
                                vtkIdList *cellIds);

  virtual vtkIdType FindPoint(double x[3]);

  // Description:
  // Locate cell based on global coordinate x and tolerance
  // squared. If cell and cellId is non-NULL, then search starts from
  // this cell and looks at immediate neighbors.  Returns cellId >= 0
  // if inside, < 0 otherwise.  The parametric coordinates are
  // provided in pcoords[3]. The interpolation weights are returned in
  // weights[]. (The number of weights is equal to the number of
  // points in the found cell). Tolerance is used to control how close
  // the point is to be considered "in" the cell.
  // THIS METHOD IS NOT THREAD SAFE.
  virtual vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
                             double tol2, int& subId, double pcoords[3],
                             double *weights);

  // Description:
347
  // This is a version of the above method that can be used with
Francois Bertel's avatar
Francois Bertel committed
348
349
350
351
352
353
354
355
  // multithreaded applications. A vtkGenericCell must be passed in
  // to be used in internal calls that might be made to GetCell()
  // THIS METHOD IS THREAD SAFE IF FIRST CALLED FROM A SINGLE THREAD AND
  // THE DATASET IS NOT MODIFIED
  virtual vtkIdType FindCell(double x[3], vtkCell *cell,
                             vtkGenericCell *gencell, vtkIdType cellId,
                             double tol2, int& subId, double pcoords[3],
                             double *weights);
356

Francois Bertel's avatar
Francois Bertel committed
357
358
359
360
  // Description:
  // Restore data object to initial state,
  // THIS METHOD IS NOT THREAD SAFE.
  void Initialize();
361

Francois Bertel's avatar
Francois Bertel committed
362
363
364
365
366
367
  // Description:
  // Convenience method returns largest cell size in dataset. This is generally
  // used to allocate memory for supporting data structures.
  // This is the number of points of a cell.
  // THIS METHOD IS THREAD SAFE
  virtual int GetMaxCellSize();
368

Francois Bertel's avatar
Francois Bertel committed
369
370
  // Description:
  // Shallow and Deep copy.
371
  void ShallowCopy(vtkDataObject *src);
Francois Bertel's avatar
Francois Bertel committed
372
  void DeepCopy(vtkDataObject *src);
373

Francois Bertel's avatar
Francois Bertel committed
374
375
376
377
378
379
380
381
382
383
384
  // Description:
  // Get the points of node `sibling' on its face `face'.
  // \pre sibling_exists: sibling!=0
  // \pre sibling_not_leaf: !sibling->CurrentIsLeaf()
  // \pre sibling_3d: sibling->GetDimension()==3
  // \pre valid_face: face>=0 && face<6
  // \pre valid_level_not_leaf: level>=0 level<(this->GetNumberOfLevels()-1)
  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
                       int face,
                       int level,
                       vtkHyperOctreePointsGrabber *grabber);
385

Francois Bertel's avatar
Francois Bertel committed
386
387
388
389
390
391
392
393
394
395
396
  // Description:
  // Get the points of the parent node of `cursor' on its faces `faces' at
  // level `level' or deeper.
  // \pre cursor_exists: cursor!=0
  // \pre cursor_3d: cursor->GetDimension()==3
  // \pre valid_level: level>=0
  // \pre boolean_faces: (faces[0]==0 || faces[0]==1) && (faces[1]==0 || faces[1]==1) && (faces[2]==0 || faces[2]==1)
  void GetPointsOnParentFaces(int faces[3],
                              int level,
                              vtkHyperOctreeCursor *cursor,
                              vtkHyperOctreePointsGrabber *grabber);
397

Francois Bertel's avatar
Francois Bertel committed
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
  // Description:
  // Get the points of node `sibling' on its edge `axis','k','j'.
  // If axis==0, the edge is X-aligned and k gives the z coordinate and j the
  // y-coordinate. If axis==1, the edge is Y-aligned and k gives the x coordinate
  // and j the z coordinate. If axis==2, the edge is Z-aligned and k gives the
  // y coordinate and j the x coordinate.
  // \pre sibling_exists: sibling!=0
  // \pre sibling_3d: sibling->GetDimension()==3
  // \pre sibling_not_leaf: !sibling->CurrentIsLeaf()
  // \pre valid_axis: axis>=0 && axis<3
  // \pre valid_k: k>=0 && k<=1
  // \pre valid_j: j>=0 && j<=1
  // \pre valid_level_not_leaf: level>=0 level<(this->Input->GetNumberOfLevels()-1)
  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
                       int level,
                       int axis,
                       int k,
                       int j,
                       vtkHyperOctreePointsGrabber *grabber);
417

Francois Bertel's avatar
Francois Bertel committed
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
  // Description:
  // Get the points of the parent node of `cursor' on its edge `axis','k','j'
  // at level `level' or deeper.
  // If axis==0, the edge is X-aligned and k gives the z coordinate and j the
  // y-coordinate. If axis==1, the edge is Y-aligned and k gives the x
  // coordinate and j the z coordinate. If axis==2, the edge is Z-aligned and
  // k gives the y coordinate and j the x coordinate.
  // \pre cursor_exists: cursor!=0
  // \pre cursor_3d: cursor->GetDimension()==3
  // \pre valid_level: level>=0
  // \pre valid_range_axis: axis>=0 && axis<3
  // \pre valid_range_k: k>=0 && k<=1
  // \pre valid_range_j: j>=0 && j<=1
  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
                             int level,
                             int axis,
                             int k,
                             int j,
                             vtkHyperOctreePointsGrabber *grabber);
437

Francois Bertel's avatar
Francois Bertel committed
438
439
440
441
442
443
444
445
446
447
448
  // Description:
  // Get the points of node `sibling' on its edge `edge'.
  // \pre sibling_exists: sibling!=0
  // \pre sibling_not_leaf: !sibling->CurrentIsLeaf()
  // \pre sibling_2d: sibling->GetDimension()==2
  // \pre valid_edge: edge>=0 && edge<4
  // \pre valid_level_not_leaf: level>=0 level<(this->Input->GetNumberOfLevels()-1)
  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
                         int edge,
                         int level,
                         vtkHyperOctreePointsGrabber *grabber);
449

Francois Bertel's avatar
Francois Bertel committed
450
451
452
453
454
455
456
457
458
459
460
  // Description:
  // Get the points of the parent node of `cursor' on its edge `edge' at
  // level `level' or deeper. (edge=0 for -X, 1 for +X, 2 for -Y, 3 for +Y)
  // \pre cursor_exists: cursor!=0
  // \pre cursor_2d: cursor->GetDimension()==2
  // \pre valid_level: level>=0
  // \pre valid_edge: edge>=0 && edge<4
  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
                               int edge,
                               int level,
                               vtkHyperOctreePointsGrabber *grabber);
461

462
463
464
465
  // Description:
  // A generic way to set the leaf data attributes.
  // This can be either point data for dual or cell data for normal grid.
  vtkDataSetAttributes* GetLeafData();
466

467
468
469
470
471
472
  // Description:
  // Switch between returning leaves as cells, or the dual grid.
  void SetDualGridFlag(int flag);
  vtkGetMacro(DualGridFlag,int);

  // Description:
473
  // Return the actual size of the data in kibibytes (1024 bytes). This number
474
475
476
477
478
479
  // is valid only after the pipeline has updated. The memory size
  // returned is guaranteed to be greater than or equal to the
  // memory required to represent the data (e.g., extra space in
  // arrays, etc. are not included in the return value). THIS METHOD
  // IS THREAD SAFE.
  unsigned long GetActualMemorySize();
480
481
482
483
484
485

  // Description:
  // Retrieve an instance of this class from an information object.
  static vtkHyperOctree* GetData(vtkInformation* info);
  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);

Francois Bertel's avatar
Francois Bertel committed
486
487
488
489
490
491
protected:
  // Constructor with default bounds (0,1, 0,1, 0,1).
  vtkHyperOctree();
  ~vtkHyperOctree();

  void ComputeBounds();
492

Francois Bertel's avatar
Francois Bertel committed
493
  int Dimension; // 1, 2 or 3.
494

Francois Bertel's avatar
Francois Bertel committed
495
496
  double Size[3]; // size on each axis
  double Origin[3]; // position of corner (0,0,0) of the root.
497

Francois Bertel's avatar
Francois Bertel committed
498
499
500
501
  vtkHyperOctreeInternal *CellTree;

  vtkHyperOctreeCursor *TmpChild; // to avoid allocation in the loop

502
  friend class vtkHyperOctreeLightWeightCursor;
503

504
505
506
  // Initialize the arrays if necessary, then return it.
  void UpdateDualArrays();
  vtkPoints* GetLeafCenters();
507
  vtkIdTypeArray* GetCornerLeafIds();
508
  vtkPoints *LeafCenters;
509
  vtkIdTypeArray *CornerLeafIds;
510

511
512
513
514
515
  void UpdateGridArrays();
  vtkPoints* GetCornerPoints();
  vtkIdTypeArray* GetLeafCornerIds();
  vtkPoints* CornerPoints;
  vtkIdTypeArray* LeafCornerIds;
516

517
518
  void DeleteInternalArrays();

519
  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
520
                               unsigned short *xyzIds, int level);
521
  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
522
523
524
525
526
527
528
529
530
531
532
                               unsigned char* visited,
                               double* origin, double* size);
  void EvaluateDualCorner(vtkHyperOctreeLightWeightCursor* neighborhood);
  vtkIdType EvaluateGridCorner(int level,vtkHyperOctreeLightWeightCursor* neighborhood,
                               unsigned char* visited, int* cornerNeighborIds);

  // This is a table for traversing a neighborhood down an octree.
  // 8 children x 27 cursors
  // First three bits encode the child,  rest encode the cursor id.
  // 8xCursorId + childId.
  // This will be shorter when we get rid of the 3x3x3 neighborhood.
533
534
  // I was using unsigned char, but VS60 optimized build had a problem.
  int NeighborhoodTraversalTable[216];
535
536
  void GenerateGridNeighborhoodTraversalTable();
  void GenerateDualNeighborhoodTraversalTable();
537
538
539
540
541
542

  // for the GetCell method
  vtkLine *Line;
  vtkPixel *Pixel;
  vtkVoxel *Voxel;

543
  vtkCellLinks* Links;
Berk Geveci's avatar
Berk Geveci committed
544
  void BuildLinks();
545

546
547
  vtkIdType RecursiveFindPoint(double x[3],
    vtkHyperOctreeLightWeightCursor* cursor,
548
549
    double *origin, double *size);

550
  // This toggles the data set API between the leaf cells and
551
  // the dual grid (leaves are points, corners are cells).
552
553
  int DualGridFlag;

Francois Bertel's avatar
Francois Bertel committed
554
private:
555
  vtkHyperOctree(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
556
  void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
Francois Bertel's avatar
Francois Bertel committed
557
558
};

559
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
560
{
561
public:
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
  vtkHyperOctreeLightWeightCursor();
  void Initialize(vtkHyperOctree* tree);
  void ToRoot();
  void ToChild(int child);
  unsigned short GetIsLeaf();
  int GetLeafIndex() {return this->Index;} // Only valid for leaves.
  vtkHyperOctree* GetTree() { return this->Tree; }
  unsigned short GetLevel() {return this->Level;}
private:
  vtkHyperOctree* Tree;
  int Index;
  unsigned short IsLeaf;
  unsigned short Level;
};

Francois Bertel's avatar
Francois Bertel committed
577
#endif