forked from Kitware/VTK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vtkSimpleScalarTree.h
176 lines (150 loc) · 6.07 KB
/
vtkSimpleScalarTree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*=========================================================================
Program: Visualization Toolkit
Module: vtkSimpleScalarTree.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.
=========================================================================*/
/**
* @class vtkSimpleScalarTree
* @brief organize data according to scalar values (used to accelerate contouring operations)
*
* vtkSimpleScalarTree creates a pointerless binary tree that helps search
* for cells that lie within a particular scalar range. This object is used
* to accelerate some contouring (and other scalar-based techniques).
*
* The tree consists of an array of (min,max) scalar range pairs per
* node in the tree. The (min,max) range is determined from looking at
* the range of the children of the tree node. If the node is a leaf,
* then the range is determined by scanning the range of scalar data
* in n cells in the dataset. The n cells are determined by arbitrary
* selecting cell ids from id(i) to id(i+n), and where n is specified
* using the BranchingFactor ivar. Note that leaf node i=0 contains
* the scalar range computed from cell ids (0,n-1); leaf node i=1
* contains the range from cell ids (n,2n-1); and so on. The
* implication is that there are no direct lists of cell ids per leaf
* node, instead the cell ids are implicitly known. Despite the
* arbitrary grouping of cells, in practice this scalar tree actually
* performs quite well due to spatial/data coherence.
*
* This class has an API that supports both serial and parallel
* operation. The parallel API enables the using class to grab arrays
* (or batches) of cells that potentially intersect the
* isocontour. These batches can then be processed in separate
* threads.
*
* @sa
* vtkScalarTree vtkSpanSpace
*/
#ifndef vtkSimpleScalarTree_h
#define vtkSimpleScalarTree_h
#include "vtkCommonExecutionModelModule.h" // For export macro
#include "vtkScalarTree.h"
class vtkScalarNode;
class vtkSimpleScalarTree;
class VTKCOMMONEXECUTIONMODEL_EXPORT vtkSimpleScalarTree : public vtkScalarTree
{
public:
/**
* Instantiate scalar tree with maximum level of 20 and branching
* factor of three.
*/
static vtkSimpleScalarTree* New();
///@{
/**
* Standard type related macros and PrintSelf() method.
*/
vtkTypeMacro(vtkSimpleScalarTree, vtkScalarTree);
void PrintSelf(ostream& os, vtkIndent indent) override;
///@}
/**
* This method is used to copy data members when cloning an instance of the
* class. It does not copy heavy data.
*/
void ShallowCopy(vtkScalarTree* stree) override;
///@{
/**
* Set the branching factor for the tree. This is the number of
* children per tree node. Smaller values (minimum is 2) mean deeper
* trees and more memory overhead. Larger values mean shallower
* trees, less memory usage, but worse performance.
*/
vtkSetClampMacro(BranchingFactor, int, 2, VTK_INT_MAX);
vtkGetMacro(BranchingFactor, int);
///@}
///@{
/**
* Get the level of the scalar tree. This value may change each time the
* scalar tree is built and the branching factor changes.
*/
vtkGetMacro(Level, int);
///@}
///@{
/**
* Set the maximum allowable level for the tree.
*/
vtkSetClampMacro(MaxLevel, int, 1, VTK_INT_MAX);
vtkGetMacro(MaxLevel, int);
///@}
/**
* Construct the scalar tree from the dataset provided. Checks build times
* and modified time from input and reconstructs the tree if necessary.
*/
void BuildTree() override;
/**
* Initialize locator. Frees memory and resets object as appropriate.
*/
void Initialize() override;
/**
* Begin to traverse the cells based on a scalar value. Returned cells
* will likely have scalar values that span the scalar value specified.
*/
void InitTraversal(double scalarValue) override;
/**
* Return the next cell that may contain scalar value specified to
* initialize traversal. The value nullptr is returned if the list is
* exhausted. Make sure that InitTraversal() has been invoked first or
* you'll get erratic behavior.
*/
vtkCell* GetNextCell(vtkIdType& cellId, vtkIdList*& ptIds, vtkDataArray* cellScalars) override;
// The following methods supports parallel (threaded) traversal. Basically
// batches of cells (which are a portion of the whole dataset) are available for
// processing in a parallel For() operation.
/**
* Get the number of cell batches available for processing as a function of
* the specified scalar value. Each batch contains a list of candidate
* cells that may contain the specified isocontour value.
*/
vtkIdType GetNumberOfCellBatches(double scalarValue) override;
/**
* Return the array of cell ids in the specified batch. The method
* also returns the number of cell ids in the array. Make sure to
* call GetNumberOfCellBatches() beforehand.
*/
const vtkIdType* GetCellBatch(vtkIdType batchNum, vtkIdType& numCells) override;
protected:
vtkSimpleScalarTree();
~vtkSimpleScalarTree() override;
int MaxLevel;
int Level;
int BranchingFactor; // number of children per node
vtkScalarNode* Tree; // pointerless scalar range tree
int TreeSize; // allocated size of tree
vtkIdType LeafOffset; // offset to leaf nodes of tree
private:
vtkIdType NumCells; // the number of cells in this dataset
vtkIdType TreeIndex; // traversal location within tree
int ChildNumber; // current child in traversal
vtkIdType CellId; // current cell id being examined
int FindStartLeaf(vtkIdType index, int level);
int FindNextLeaf(vtkIdType index, int level);
vtkIdType* CandidateCells; // to support parallel computing
vtkIdType NumCandidates;
private:
vtkSimpleScalarTree(const vtkSimpleScalarTree&) = delete;
void operator=(const vtkSimpleScalarTree&) = delete;
};
#endif