vtkHyperOctree.h 20.3 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
#if !defined(VTK_LEGACY_REMOVE)
144
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctree : public vtkDataSet
Francois Bertel's avatar
Francois Bertel committed
145
146
147
148
149
150
{
public:
  static vtkInformationIntegerKey* LEVELS();
  static vtkInformationIntegerKey* DIMENSION();
  static vtkInformationDoubleVectorKey* SIZES();
  static vtkHyperOctree *New();
151

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

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

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

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

172
173
174
175
176
  /**
   * 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
177
  int GetDimension();
178

179
180
181
182
183
  /**
   * 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
184
  void SetDimension(int dim);
185

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

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

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

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

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

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

214
215
216
217
218
219
220
221
  /**
   * 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
222
  vtkIdType GetMaxNumberOfPoints(int level);
223

224
225
226
227
228
229
230
231
232
233
234
235
  /**
   * 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
236
  vtkIdType GetMaxNumberOfPointsOnBoundary(int level);
237

238
239
240
241
242
243
  /**
   * 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
244
  vtkIdType GetMaxNumberOfCellsOnBoundary(int level);
245

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

  // Measurement: geometry
253

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

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

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

277
278
279
280
281
  /**
   * 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
282
  vtkHyperOctreeCursor *NewCellCursor();
283

284
285
286
287
288
289
  /**
   * 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
290
  void SubdivideLeaf(vtkHyperOctreeCursor *leaf);
291

292
293
294
295
296
297
298
  /**
   * 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
299
  void CollapseTerminalNode(vtkHyperOctreeCursor *node);
300

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

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

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

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


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

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

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

357

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

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

370
371
  /**
   * Locate cell based on global coordinate x and tolerance
372
   * squared. If cell and cellId is non-nullptr, then search starts from
373
374
375
376
377
378
379
380
   * 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.
   */
381
382
  vtkIdType FindCell(double x[3], vtkCell *cell, vtkIdType cellId,
                     double tol2, int& subId, double pcoords[3],
383
                     double *weights) override;
Francois Bertel's avatar
Francois Bertel committed
384

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

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

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

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

  /**
   * 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
427
428
429
430
  void GetPointsOnFace(vtkHyperOctreeCursor *sibling,
                       int face,
                       int level,
                       vtkHyperOctreePointsGrabber *grabber);
431

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

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

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

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

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

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

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

  /**
   * 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.
   */
535
  unsigned long GetActualMemorySize() override;
536

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

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

550
  void ComputeBounds() override;
551

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

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

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

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

561
  friend class vtkHyperOctreeLightWeightCursor;
562

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

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

576
577
  void DeleteInternalArrays();

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

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

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

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

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

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

618
class VTKCOMMONDATAMODEL_EXPORT vtkHyperOctreeLightWeightCursor
619
{
620
public:
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;
};
635
#endif // LEGACY remove
636

Francois Bertel's avatar
Francois Bertel committed
637
#endif