VTK  9.3.1
vtkModifiedBSPTree.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-FileCopyrightText: Copyright (c) 1997-2009 John Biddiscombe
3 // SPDX-License-Identifier: BSD-3-Clause
132 #ifndef vtkModifiedBSPTree_h
133 #define vtkModifiedBSPTree_h
134 
135 #include "vtkAbstractCellLocator.h"
136 #include "vtkFiltersFlowPathsModule.h" // For export macro
137 #include "vtkSmartPointer.h" // required because it is nice
138 
139 VTK_ABI_NAMESPACE_BEGIN
140 class Sorted_cell_extents_Lists;
141 class BSPNode;
142 class vtkGenericCell;
143 class vtkIdList;
144 class vtkIdListCollection;
145 
146 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
147 {
148 public:
150 
154  void PrintSelf(ostream& os, vtkIndent indent) override;
156 
160  static vtkModifiedBSPTree* New();
161 
162  // Re-use any superclass signatures that we don't override.
165 
172  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
173  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
174 
184  int IntersectWithLine(const double p1[3], const double p2[3], double tol, vtkPoints* points,
185  vtkIdList* cellIds, vtkGenericCell* cell) override;
186 
196  const double p1[3], const double p2[3], double tolerance, vtkIdList* cellsIds) override
197  {
198  this->Superclass::FindCellsAlongLine(p1, p2, tolerance, cellsIds);
199  }
200 
208  vtkIdType FindCell(double x[3], double vtkNotUsed(tol2), vtkGenericCell* GenCell, int& subId,
209  double pcoords[3], double* weights) override;
210 
216  vtkIdListCollection* GetLeafNodeCellInformation();
217 
221  virtual void GenerateRepresentationLeafs(vtkPolyData* pd);
222 
224 
227  void GenerateRepresentation(int level, vtkPolyData* pd) override;
228  void FreeSearchStructure() override;
229  void BuildLocator() override;
230  void ForceBuildLocator() override;
232 
236  void ShallowCopy(vtkAbstractCellLocator* locator) override;
237 
238 protected:
240  ~vtkModifiedBSPTree() override;
241 
242  void BuildLocatorInternal() override;
243  std::shared_ptr<BSPNode> mRoot; // bounding box root node
244  int npn;
245  int nln;
247 
248  // The main subdivision routine
249  void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
250  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
251 
252 private:
253  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
254  void operator=(const vtkModifiedBSPTree&) = delete;
255 };
256 
258 // BSP Node
259 // A BSP Node is a BBox - axis aligned etc etc
261 #ifndef DOXYGEN_SHOULD_SKIP_THIS
262 
263 class BSPNode
264 {
265 public:
266  // Constructor
267  BSPNode()
268  {
269  mChild[0] = mChild[1] = mChild[2] = nullptr;
270  for (int i = 0; i < 6; i++)
271  sorted_cell_lists[i] = nullptr;
272  for (int i = 0; i < 3; i++)
273  {
274  this->Bounds[i * 2] = VTK_FLOAT_MAX;
275  this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
276  }
277  }
278  // Destructor
279  ~BSPNode()
280  {
281  for (int i = 0; i < 3; i++)
282  delete mChild[i];
283  for (int i = 0; i < 6; i++)
284  delete[] sorted_cell_lists[i];
285  }
286  // Set min box limits
287  void setMin(double minx, double miny, double minz)
288  {
289  this->Bounds[0] = minx;
290  this->Bounds[2] = miny;
291  this->Bounds[4] = minz;
292  }
293  // Set max box limits
294  void setMax(double maxx, double maxy, double maxz)
295  {
296  this->Bounds[1] = maxx;
297  this->Bounds[3] = maxy;
298  this->Bounds[5] = maxz;
299  }
300  //
301  bool Inside(double point[3]) const;
302  // BBox
303  double Bounds[6];
304 
305 protected:
306  // The child nodes of this one (if present - nullptr otherwise)
307  BSPNode* mChild[3];
308  // The axis we subdivide this voxel along
309  int mAxis;
310  // Just for reference
311  int depth;
312  // the number of cells in this node
313  int num_cells;
314  // 6 lists, sorted after the 6 dominant axes
315  vtkIdType* sorted_cell_lists[6];
316  // Order nodes as near/mid far relative to ray
317  void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
318  BSPNode*& Mid, BSPNode*& Far) const;
319  friend class vtkModifiedBSPTree;
320 
321 public:
322  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
323 };
324 
325 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
326 
327 VTK_ABI_NAMESPACE_END
328 #endif
virtual void BuildLocator()=0
Build the locator from the input dataset.
void FindCellsAlongLine(const double p1[3], const double p2[3], double tolerance, vtkIdList *cellsIds) override
Take the passed line segment and intersect it with the data set.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:52
an abstract base class for locators which find cells
int vtkIdType
Definition: vtkType.h:315
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
provides thread-safe access to cells
virtual void ShallowCopy(vtkAbstractCellLocator *)
Shallow copy of a vtkAbstractCellLocator.
#define VTK_FLOAT_MAX
Definition: vtkType.h:152
virtual int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId)
Return intersection point (if any) of finite line with cells contained in cell locator.
a simple class to control print indentation
Definition: vtkIndent.h:28
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:192
virtual vtkIdType FindCell(double x[3])
Returns the Id of the cell containing the point, returns -1 if no cell found.
list of point or cell ids
Definition: vtkIdList.h:22
maintain an ordered list of IdList objects
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
std::shared_ptr< BSPNode > mRoot
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
represent and manipulate 3D points
Definition: vtkPoints.h:28
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:156
Generate axis aligned BBox tree for ray-casting and other Locator based searches. ...