vtkHyperOctree.h 20.6 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
116
117
118
// .SECTION Caveats
// It is not a spatial search object! If you looking for this kind of
// octree see vtkCellLocator instead.

// .SECTION See Also
// vtkHyperOctreeAlgorithm

#ifndef __vtkHyperOctree_h
#define __vtkHyperOctree_h

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
147
{
public:
  static vtkInformationIntegerKey* LEVELS();
  static vtkInformationIntegerKey* DIMENSION();
  static vtkInformationDoubleVectorKey* SIZES();
  static vtkHyperOctree *New();
  
148
  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
Francois Bertel's avatar
Francois Bertel committed
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
  void PrintSelf(ostream& os, vtkIndent indent);
  
  // Description:
  // Return what type of dataset this is.
  int GetDataObjectType();
  
  // Description:
  // Copy the geometric and topological structure of an input rectilinear grid
  // object.
  void CopyStructure(vtkDataSet *ds);
  
  // 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);
  
166
  // Description:
Francois Bertel's avatar
Francois Bertel committed
167
168
169
170
171
  // 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();
  
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
177
178
179
180
181
182
183
184
185
186
187
188
189
  // \pre valid_dim: dim>=1 && dim<=3
  // \post dimension_is_set: GetDimension()==dim
  void SetDimension(int dim);
  
  // Return if the node for the given path exists or not.
  // \pre path_exists: path!=0
//  int IsANode(vtkPath *path);
  
  // 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);
  
  // Measurement: topology
  
  // Description:
190
  // Return the number of cells in the dual grid.
Francois Bertel's avatar
Francois Bertel committed
191
192
193
194
  // \post positive_result: result>=0
  vtkIdType GetNumberOfCells();
  
  // Description:
195
196
197
198
199
  // Get the number of leaves in the tree.
  vtkIdType GetNumberOfLeaves();
  
  // Description:
  // Return the number of points in the dual grid.
Francois Bertel's avatar
Francois Bertel committed
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
  // \post positive_result: result>=0
  vtkIdType GetNumberOfPoints();
  
  // 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
  // of the uniform grid. 
  // \pre positive_level: level>=0 && level<this->GetNumberOfLevels()
  // \post definition: result==(2^(GetNumberOfLevels()-level-1)+1)^GetDimension()
  vtkIdType GetMaxNumberOfPoints(int level);
  
  // 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);
 
  // Description:
  // Return the number of cells corresponding to the boundary of a cell
  // of level `level' where all the leaves at at the last level. 
  // \pre positive_level: level>=0 && level<this->GetNumberOfLevels()
  // \post positive_result: result>=0
  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
  
  // Description:
  // Return the number of levels.
  // \post result_greater_or_equal_to_one: result>=1
  vtkIdType GetNumberOfLevels();

  // Measurement: geometry
  
  // Description:
  // Set the size on each axis.
  vtkSetVector3Macro(Size,double);
  
  // Description:
  // Return the size on each axis.
  vtkGetVector3Macro(Size,double);
  
  // 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);
  
  // 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
265
266
267
268
269
270
271
272
273
274
275
276
277
278
  // 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);
  
  // 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);
  
  // 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
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
  // 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]);
  
  // Description:
  // Get cell with cellId such that: 0 <= cellId < NumberOfCells.
  // THIS METHOD IS NOT THREAD SAFE.
  virtual vtkCell *GetCell(vtkIdType cellId);

  // Description:
  // Get cell with cellId such that: 0 <= cellId < NumberOfCells. 
  // 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);
  
   
  // 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
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461

  // 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);

  
  // 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
  virtual void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds, 
                                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:
  // This is a version of the above method that can be used with 
  // 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);
  
  // Description:
  // Restore data object to initial state,
  // THIS METHOD IS NOT THREAD SAFE.
  void Initialize();
  
  // 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();
  
  // Description:
  // Shallow and Deep copy.
  void ShallowCopy(vtkDataObject *src);  
  void DeepCopy(vtkDataObject *src);
  
  // 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);
 
  // 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);
  
  // 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);
  
  // 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);
  
  // 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);
  
  // 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);
  
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
  // 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();
  
  // Description:
  // Switch between returning leaves as cells, or the dual grid.
  void SetDualGridFlag(int flag);
  vtkGetMacro(DualGridFlag,int);

  // Description:
  // Return the actual size of the data in kilobytes. This number
  // 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
  //BTX
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);
486
  //ETX
487

Francois Bertel's avatar
Francois Bertel committed
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
protected:
  // Constructor with default bounds (0,1, 0,1, 0,1).
  vtkHyperOctree();
  ~vtkHyperOctree();

  void ComputeBounds();
  
  int Dimension; // 1, 2 or 3.
  
  double Size[3]; // size on each axis
  double Origin[3]; // position of corner (0,0,0) of the root.
  
  vtkHyperOctreeInternal *CellTree;

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

504
505
506
507
508
509
510
  //BTX
  friend class vtkHyperOctreeLightWeightCursor;
  //ETX
  
  // Initialize the arrays if necessary, then return it.
  void UpdateDualArrays();
  vtkPoints* GetLeafCenters();
511
  vtkIdTypeArray* GetCornerLeafIds();
512
  vtkPoints *LeafCenters;
513
  vtkIdTypeArray *CornerLeafIds;
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
  
  void UpdateGridArrays();
  vtkPoints* GetCornerPoints();
  vtkIdTypeArray* GetLeafCornerIds();
  vtkPoints* CornerPoints;
  vtkIdTypeArray* LeafCornerIds;
  
  void DeleteInternalArrays();

  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood, 
                               unsigned short *xyzIds, int level);
  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood, 
                               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.
537
538
  // I was using unsigned char, but VS60 optimized build had a problem.
  int NeighborhoodTraversalTable[216];
539
540
541
542
543
544
545
546
547
  void GenerateGridNeighborhoodTraversalTable();  
  void GenerateDualNeighborhoodTraversalTable();  

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

  vtkCellLinks* Links;  
Berk Geveci's avatar
Berk Geveci committed
548
  void BuildLinks();
549

550
551
552
553
  vtkIdType RecursiveFindPoint(double x[3], 
    vtkHyperOctreeLightWeightCursor* cursor, 
    double *origin, double *size);

554
555
556
557
  // This toggles the data set API between the leaf cells and
  // the dual grid (leaves are points, corners are cells). 
  int DualGridFlag;

Francois Bertel's avatar
Francois Bertel committed
558
559
560
561
562
private:
  vtkHyperOctree(const vtkHyperOctree&);  // Not implemented.
  void operator=(const vtkHyperOctree&);    // Not implemented.
};

563

Berk Geveci's avatar
Berk Geveci committed
564
//BTX
565

566
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
{
public:  
  vtkHyperOctreeLightWeightCursor();
  ~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;
};

Berk Geveci's avatar
Berk Geveci committed
586
//ETX
587

Francois Bertel's avatar
Francois Bertel committed
588
#endif