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
/*=========================================================================

  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.

=========================================================================*/
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
/**
 * @class   vtkHyperOctree
 * @brief   A dataset structured as a tree where each node has
 * exactly 2^n children.
 *
 * An hyperoctree is a dataset where each node has either exactly 2^n children
 * 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) ).
 * The class name comes from the following paper:
 *
 * \verbatim
 * @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}
 *  }
 * \endverbatim
 *
 * 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
 * \verbatim
 *              +y
 * +-+-+        ^
 * |2|3|        |
 * +-+-+  O +z  +-> +x
 * |0|1|
 * +-+-+
 * \endverbatim
 *
 * - then the +z side, in counter-clockwise
 * - 4: -y -x sides
 * - 5: -y +x sides
 * - 6: +y -x sides
 * - 7: +y +x sides
 * \verbatim
 *              +y
 * +-+-+        ^
 * |6|7|        |
 * +-+-+  O +z  +-> +x
 * |4|5|
 * +-+-+
 * \endverbatim
 *
 * 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
 * \verbatim
 *         +y
 * +-+-+   ^
 * |2|3|   |
 * +-+-+  O+-> +x
 * |0|1|
 * +-+-+
 * \endverbatim
 *
 * * Binary tree:
 * \verbatim
 * +0+1+  O+-> +x
 * \endverbatim
 *
 * @warning
 * It is not a spatial search object! If you looking for this kind of
 * octree see vtkCellLocator instead.
 *
 * @sa
 * vtkHyperOctreeAlgorithm
*/
Francois Bertel's avatar
Francois Bertel committed
118

119
120
#ifndef vtkHyperOctree_h
#define vtkHyperOctree_h
Francois Bertel's avatar
Francois Bertel committed
121

122
#include "vtkCommonDataModelModule.h" // For export macro
Francois Bertel's avatar
Francois Bertel committed
123
124
#include "vtkDataSet.h"

125
class vtkHyperOctreeLightWeightCursor;
Francois Bertel's avatar
Francois Bertel committed
126
127
128
129
130
131
class vtkHyperOctreeCursor;
class vtkHyperOctreeInternal;
class vtkHyperOctreePointsGrabber;

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

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

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

151
  vtkTypeMacro(vtkHyperOctree,vtkDataSet);
152
  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
153

154
155
156
  /**
   * Return what type of dataset this is.
   */
157
  int GetDataObjectType() VTK_OVERRIDE;
158

159
160
161
162
  /**
   * Copy the geometric and topological structure of an input rectilinear grid
   * object.
   */
163
  void CopyStructure(vtkDataSet *ds) VTK_OVERRIDE;
164

Francois Bertel's avatar
Francois Bertel committed
165
166
167
168
169
  // 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);
170

171
172
173
174
175
  /**
   * 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
   */
Francois Bertel's avatar
Francois Bertel committed
176
  int GetDimension();
177

178
179
180
181
182
  /**
   * Set the dimension of the tree with `dim'. See GetDimension() for details.
   * \pre valid_dim: dim>=1 && dim<=3
   * \post dimension_is_set: GetDimension()==dim
   */
Francois Bertel's avatar
Francois Bertel committed
183
  void SetDimension(int dim);
184

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

Francois Bertel's avatar
Francois Bertel committed
189
190
191
192
  // 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);
193

Francois Bertel's avatar
Francois Bertel committed
194
  // Measurement: topology
195

196
197
198
199
  /**
   * Return the number of cells in the dual grid.
   * \post positive_result: result>=0
   */
200
  vtkIdType GetNumberOfCells() VTK_OVERRIDE;
201

202
203
204
  /**
   * Get the number of leaves in the tree.
   */
205
  vtkIdType GetNumberOfLeaves();
206

207
208
209
210
  /**
   * Return the number of points in the dual grid.
   * \post positive_result: result>=0
   */
211
  vtkIdType GetNumberOfPoints() VTK_OVERRIDE;
212

213
214
215
216
217
218
219
220
  /**
   * 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()
   */
Francois Bertel's avatar
Francois Bertel committed
221
  vtkIdType GetMaxNumberOfPoints(int level);
222

223
224
225
226
227
228
229
230
231
232
233
234
  /**
   * 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)
   */
Francois Bertel's avatar
Francois Bertel committed
235
  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
236

237
238
239
240
241
242
  /**
   * 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
   */
Francois Bertel's avatar
Francois Bertel committed
243
  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
244

245
246
247
248
  /**
   * Return the number of levels.
   * \post result_greater_or_equal_to_one: result>=1
   */
Francois Bertel's avatar
Francois Bertel committed
249
250
251
  vtkIdType GetNumberOfLevels();

  // Measurement: geometry
252

253
254
255
256
  //@{
  /**
   * Set the size on each axis.
   */
Francois Bertel's avatar
Francois Bertel committed
257
  vtkSetVector3Macro(Size,double);
258
  //@}
259

260
261
262
263
  //@{
  /**
   * Return the size on each axis.
   */
Francois Bertel's avatar
Francois Bertel committed
264
  vtkGetVector3Macro(Size,double);
265
  //@}
266

267
268
269
270
  //@{
  /**
   * Set the origin (position of corner (0,0,0) of the root.
   */
Francois Bertel's avatar
Francois Bertel committed
271
272
273
  vtkSetVector3Macro(Origin,double);
  // Return the origin (position of corner (0,0,0) ) of the root.
  vtkGetVector3Macro(Origin,double);
274
  //@}
275

276
277
278
279
280
  /**
   * Create a new cursor: an object that can traverse
   * the cell of an hyperoctree.
   * \post result_exists: result!=0
   */
Francois Bertel's avatar
Francois Bertel committed
281
  vtkHyperOctreeCursor *NewCellCursor();
282

283
284
285
286
287
288
  /**
   * 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()
   */
Francois Bertel's avatar
Francois Bertel committed
289
  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
290

291
292
293
294
295
296
297
  /**
   * 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()
   */
Francois Bertel's avatar
Francois Bertel committed
298
  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
299

300
301
302
303
  /**
   * Get point coordinates with ptId such that: 0 <= ptId < NumberOfPoints.
   * THIS METHOD IS NOT THREAD SAFE.
   */
304
  double *GetPoint(vtkIdType ptId) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
305

306
307
308
309
310
311
  /**
   * 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
   */
312
  void GetPoint(vtkIdType id, double x[3]) VTK_OVERRIDE;
313

314
315
316
317
  /**
   * Get cell with cellId such that: 0 <= cellId < NumberOfCells.
   * THIS METHOD IS NOT THREAD SAFE.
   */
318
  using vtkDataSet::GetCell;
319
  vtkCell *GetCell(vtkIdType cellId) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
320

321
322
323
324
325
326
327
  /**
   * 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
   */
328
  void GetCell(vtkIdType cellId, vtkGenericCell *cell) VTK_OVERRIDE;
329
330


331
332
333
334
335
  /**
   * 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
   */
336
  int GetCellType(vtkIdType cellId) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
337

338
339
340
341
342
343
  //@{
  /**
   * 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
   */
344
  void GetCellPoints(vtkIdType cellId, vtkIdList *ptIds) VTK_OVERRIDE;
345
346
  virtual void GetCellPoints(vtkIdType cellId, vtkIdType& npts,
                             vtkIdType* &pts);
347
  //@}
Francois Bertel's avatar
Francois Bertel committed
348

349
350
351
352
353
  /**
   * 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
   */
354
  void GetPointCells(vtkIdType ptId, vtkIdList *cellIds) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
355

356

357
358
359
360
361
362
363
  /**
   * 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
   */
364
365
  void GetCellNeighbors(vtkIdType cellId, vtkIdList *ptIds,
                        vtkIdList *cellIds) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
366

367
  vtkIdType FindPoint(double x[3]) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
368

369
370
371
372
373
374
375
376
377
378
379
  /**
   * 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.
   */
380
381
382
  vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
                     double tol2, int& subId, double pcoords[3],
                     double *weights) VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
383

384
385
386
387
388
389
390
  /**
   * 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
   */
391
392
393
394
  vtkIdType FindCell(double x[3], vtkCell *cell,
                     vtkGenericCell *gencell, vtkIdType cellId,
                     double tol2, int& subId, double pcoords[3],
                     double *weights) VTK_OVERRIDE;
395

396
397
398
399
  /**
   * Restore data object to initial state,
   * THIS METHOD IS NOT THREAD SAFE.
   */
400
  void Initialize() VTK_OVERRIDE;
401

402
403
404
405
406
407
  /**
   * 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
   */
408
  int GetMaxCellSize() VTK_OVERRIDE;
409

410
411
412
413
  //@{
  /**
   * Shallow and Deep copy.
   */
414
415
  void ShallowCopy(vtkDataObject *src) VTK_OVERRIDE;
  void DeepCopy(vtkDataObject *src) VTK_OVERRIDE;
416
417
418
419
420
421
422
423
424
425
  //@}

  /**
   * 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)
   */
Francois Bertel's avatar
Francois Bertel committed
426
427
428
429
  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
                       int face,
                       int level,
                       vtkHyperOctreePointsGrabber *grabber);
430

431
432
433
434
435
436
437
438
  /**
   * 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)
   */
Francois Bertel's avatar
Francois Bertel committed
439
440
441
442
  void GetPointsOnParentFaces(int faces[3],
                              int level,
                              vtkHyperOctreeCursor *cursor,
                              vtkHyperOctreePointsGrabber *grabber);
443

444
445
446
447
448
449
450
451
452
453
454
455
456
457
  /**
   * 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)
   */
Francois Bertel's avatar
Francois Bertel committed
458
459
460
461
462
463
  void GetPointsOnEdge(vtkHyperOctreeCursor *sibling,
                       int level,
                       int axis,
                       int k,
                       int j,
                       vtkHyperOctreePointsGrabber *grabber);
464

465
466
467
468
469
470
471
472
473
474
475
476
477
478
  /**
   * 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
   */
Francois Bertel's avatar
Francois Bertel committed
479
480
481
482
483
484
  void GetPointsOnParentEdge(vtkHyperOctreeCursor *cursor,
                             int level,
                             int axis,
                             int k,
                             int j,
                             vtkHyperOctreePointsGrabber *grabber);
485

486
487
488
489
490
491
492
493
  /**
   * 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)
   */
Francois Bertel's avatar
Francois Bertel committed
494
495
496
497
  void GetPointsOnEdge2D(vtkHyperOctreeCursor *sibling,
                         int edge,
                         int level,
                         vtkHyperOctreePointsGrabber *grabber);
498

499
500
501
502
503
504
505
506
  /**
   * 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
   */
Francois Bertel's avatar
Francois Bertel committed
507
508
509
510
  void GetPointsOnParentEdge2D(vtkHyperOctreeCursor *cursor,
                               int edge,
                               int level,
                               vtkHyperOctreePointsGrabber *grabber);
511

512
513
514
515
  /**
   * A generic way to set the leaf data attributes.
   * This can be either point data for dual or cell data for normal grid.
   */
516
  vtkDataSetAttributes* GetLeafData();
517

518
519
520
521
  //@{
  /**
   * Switch between returning leaves as cells, or the dual grid.
   */
522
523
  void SetDualGridFlag(int flag);
  vtkGetMacro(DualGridFlag,int);
524
525
526
527
528
529
530
531
532
533
  //@}

  /**
   * Return the actual size of the data in kibibytes (1024 bytes). 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.
   */
534
  unsigned long GetActualMemorySize() VTK_OVERRIDE;
535

536
537
538
539
  //@{
  /**
   * Retrieve an instance of this class from an information object.
   */
540
541
  static vtkHyperOctree* GetData(vtkInformation* info);
  static vtkHyperOctree* GetData(vtkInformationVector* v, int i=0);
542
  //@}
543

Francois Bertel's avatar
Francois Bertel committed
544
545
546
protected:
  // Constructor with default bounds (0,1, 0,1, 0,1).
  vtkHyperOctree();
547
  ~vtkHyperOctree() VTK_OVERRIDE;
Francois Bertel's avatar
Francois Bertel committed
548

549
  void ComputeBounds() VTK_OVERRIDE;
550

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

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

Francois Bertel's avatar
Francois Bertel committed
556
557
558
559
  vtkHyperOctreeInternal *CellTree;

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

560
  friend class vtkHyperOctreeLightWeightCursor;
561

562
563
564
  // Initialize the arrays if necessary, then return it.
  void UpdateDualArrays();
  vtkPoints* GetLeafCenters();
565
  vtkIdTypeArray* GetCornerLeafIds();
566
  vtkPoints *LeafCenters;
567
  vtkIdTypeArray *CornerLeafIds;
568

569
570
571
572
573
  void UpdateGridArrays();
  vtkPoints* GetCornerPoints();
  vtkIdTypeArray* GetLeafCornerIds();
  vtkPoints* CornerPoints;
  vtkIdTypeArray* LeafCornerIds;
574

575
576
  void DeleteInternalArrays();

577
  void TraverseDualRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
578
                               unsigned short *xyzIds, int level);
579
  void TraverseGridRecursively(vtkHyperOctreeLightWeightCursor* neighborhood,
580
581
582
583
584
585
586
587
588
589
590
                               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.
591
592
  // I was using unsigned char, but VS60 optimized build had a problem.
  int NeighborhoodTraversalTable[216];
593
594
  void GenerateGridNeighborhoodTraversalTable();
  void GenerateDualNeighborhoodTraversalTable();
595
596
597
598
599
600

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

601
  vtkCellLinks* Links;
Berk Geveci's avatar
Berk Geveci committed
602
  void BuildLinks();
603

604
605
  vtkIdType RecursiveFindPoint(double x[3],
    vtkHyperOctreeLightWeightCursor* cursor,
606
607
    double *origin, double *size);

608
  // This toggles the data set API between the leaf cells and
609
  // the dual grid (leaves are points, corners are cells).
610
611
  int DualGridFlag;

Francois Bertel's avatar
Francois Bertel committed
612
private:
613
  vtkHyperOctree(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
614
  void operator=(const vtkHyperOctree&) VTK_DELETE_FUNCTION;
Francois Bertel's avatar
Francois Bertel committed
615
616
};

617
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
618
{
619
public:
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
  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
635
#endif