VTK  9.1.0
vtkModifiedBSPTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkModifiedBSPTree.h
5 
6  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7  All rights reserved.
8  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
15 
16 /*=========================================================================
17  This code is derived from an earlier work and is distributed
18  with permission from, and thanks to
19 
20  ------------------------------------------
21  Copyright (C) 1997-2000 John Biddiscombe
22  Rutherford Appleton Laboratory,
23  Chilton, Oxon, England
24  ------------------------------------------
25  Copyright (C) 2000-2004 John Biddiscombe
26  Skipping Mouse Software Ltd,
27  Blewbury, England
28  ------------------------------------------
29  Copyright (C) 2004-2009 John Biddiscombe
30  CSCS - Swiss National Supercomputing Centre
31  Galleria 2 - Via Cantonale
32  CH-6928 Manno, Switzerland
33  ------------------------------------
34 =========================================================================*/
145 #ifndef vtkModifiedBSPTree_h
146 #define vtkModifiedBSPTree_h
147 
148 #include "vtkAbstractCellLocator.h"
149 #include "vtkFiltersFlowPathsModule.h" // For export macro
150 #include "vtkSmartPointer.h" // required because it is nice
151 
152 class Sorted_cell_extents_Lists;
153 class BSPNode;
154 class vtkGenericCell;
155 class vtkIdList;
156 class vtkIdListCollection;
157 
158 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
159 {
160 public:
162 
166  void PrintSelf(ostream& os, vtkIndent indent) override;
168 
173 
174  // Re-use any superclass signatures that we don't override.
177 
181  void FreeSearchStructure() override;
182 
186  void BuildLocator() override;
187 
191  void GenerateRepresentation(int level, vtkPolyData* pd) override;
192 
197 
202  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
203  double pcoords[3], int& subId, vtkIdType& cellId) override;
204 
209  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
210  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
211 
220  virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol,
221  vtkPoints* points, vtkIdList* cellIds);
222 
228  double x[3], double tol2, vtkGenericCell* GenCell, double pcoords[3], double* weights) override;
229 
230  bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
231 
238 
239 protected:
242  //
243  BSPNode* mRoot; // bounding box root node
244  int npn;
245  int nln;
247 
248  //
249  // The main subdivision routine
250  void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
251  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
252 
253  // We provide a function which does the cell/ray test so that
254  // it can be overridden by subclasses to perform special treatment
255  // (Example : Particles stored in tree, have no dimension, so we must
256  // override the cell test to return a value based on some particle size
257  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
258  const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
259 
263 
264 private:
265  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
266  void operator=(const vtkModifiedBSPTree&) = delete;
267 };
268 
270 // BSP Node
271 // A BSP Node is a BBox - axis aligned etc etc
273 #ifndef DOXYGEN_SHOULD_SKIP_THIS
274 
275 class BSPNode
276 {
277 public:
278  // Constructor
279  BSPNode(void)
280  {
281  mChild[0] = mChild[1] = mChild[2] = nullptr;
282  for (int i = 0; i < 6; i++)
283  sorted_cell_lists[i] = nullptr;
284  for (int i = 0; i < 3; i++)
285  {
286  this->Bounds[i * 2] = VTK_FLOAT_MAX;
287  this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
288  }
289  }
290  // Destructor
291  ~BSPNode(void)
292  {
293  for (int i = 0; i < 3; i++)
294  delete mChild[i];
295  for (int i = 0; i < 6; i++)
296  delete[] sorted_cell_lists[i];
297  }
298  // Set min box limits
299  void setMin(double minx, double miny, double minz)
300  {
301  this->Bounds[0] = minx;
302  this->Bounds[2] = miny;
303  this->Bounds[4] = minz;
304  }
305  // Set max box limits
306  void setMax(double maxx, double maxy, double maxz)
307  {
308  this->Bounds[1] = maxx;
309  this->Bounds[3] = maxy;
310  this->Bounds[5] = maxz;
311  }
312  //
313  bool Inside(double point[3]) const;
314  // BBox
315  double Bounds[6];
316 
317 protected:
318  // The child nodes of this one (if present - nullptr otherwise)
319  BSPNode* mChild[3];
320  // The axis we subdivide this voxel along
321  int mAxis;
322  // Just for reference
323  int depth;
324  // the number of cells in this node
325  int num_cells;
326  // 6 lists, sorted after the 6 dominant axes
327  vtkIdType* sorted_cell_lists[6];
328  // Order nodes as near/mid far relative to ray
329  void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
330  BSPNode*& Mid, BSPNode*& Far) const;
331  // Test ray against node BBox : clip t values to extremes
332  bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax) const;
333  //
334  friend class vtkModifiedBSPTree;
335  friend class vtkParticleBoxTree;
336 
337 public:
338  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3],
339  const double dir[3], double& rTmin, double& rTmax);
340  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
341 };
342 
343 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
344 
345 #endif
an abstract base class for locators which find cells
virtual vtkIdType FindCell(double x[3])
Returns the Id of the cell containing the point, returns -1 if no cell found.
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.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:57
provides thread-safe access to cells
maintain an ordered list of IdList objects
list of point or cell ids
Definition: vtkIdList.h:31
a simple class to control print indentation
Definition: vtkIndent.h:34
Generate axis aligned BBox tree for raycasting and other Locator based searches.
virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3], const double tol, double &t, double ipt[3], double pcoords[3], int &subId)
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId) override
Return intersection point (if any) AND the cell which was intersected by the finite line.
vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell, double pcoords[3], double *weights) override
Test a point to find if it is inside a cell.
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override
Return intersection point (if any) AND the cell which was intersected by the finite line.
virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol, vtkPoints *points, vtkIdList *cellIds)
Take the passed line segment and intersect it with the data set.
~vtkModifiedBSPTree() override
void GenerateRepresentation(int level, vtkPolyData *pd) override
Generate BBox representation of Nth level.
vtkIdListCollection * GetLeafNodeCellInformation()
After subdivision has completed, one may wish to query the tree to find which cells are in which leaf...
void PrintSelf(ostream &os, vtkIndent indent) override
Standard Type-Macro.
bool InsideCellBounds(double x[3], vtkIdType cell_ID) override
Quickly test if a point is inside the bounds of a particular cell.
void BuildLocatorIfNeeded()
virtual void GenerateRepresentationLeafs(vtkPolyData *pd)
Generate BBox representation of all leaf nodes.
void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet, vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth)
static vtkModifiedBSPTree * New()
Construct with maximum 32 cells per node.
void FreeSearchStructure() override
Free tree memory.
void BuildLocatorInternal()
void BuildLocator() override
Build Tree.
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
@ point
Definition: vtkX3D.h:242
@ points
Definition: vtkX3D.h:452
@ level
Definition: vtkX3D.h:401
@ dir
Definition: vtkX3D.h:330
int vtkIdType
Definition: vtkType.h:332
#define VTK_FLOAT_MAX
Definition: vtkType.h:163