VTK
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 =========================================================================*/
143 #ifndef vtkModifiedBSPTree_h
144 #define vtkModifiedBSPTree_h
145 
146 #include "vtkFiltersFlowPathsModule.h" // For export macro
147 #include "vtkAbstractCellLocator.h"
148 #include "vtkSmartPointer.h" // required because it is nice
149 
150 class Sorted_cell_extents_Lists;
151 class BSPNode;
152 class vtkGenericCell;
153 class vtkIdList;
154 class vtkIdListCollection;
155 
156 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator {
157  public:
159 
163  void PrintSelf(ostream& os, vtkIndent indent) override;
165 
169  static vtkModifiedBSPTree *New();
170 
171  // Re-use any superclass signatures that we don't override.
174 
178  void FreeSearchStructure() override;
179 
183  void BuildLocator() override;
184 
188  void GenerateRepresentation(int level, vtkPolyData *pd) override;
189 
193  virtual void GenerateRepresentationLeafs(vtkPolyData *pd);
194 
199  int IntersectWithLine(
200  double p1[3], double p2[3], double tol, double &t, double x[3],
201  double pcoords[3], int &subId, vtkIdType &cellId) override;
202 
207  int IntersectWithLine(
208  double p1[3], double p2[3], double tol, double &t, double x[3],
209  double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override;
210 
219  virtual int IntersectWithLine(
220  const double p1[3], const double p2[3], const double tol,
221  vtkPoints *points, vtkIdList *cellIds);
222 
227  vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
228  double pcoords[3], double *weights) override;
229 
230  bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
231 
237  vtkIdListCollection *GetLeafNodeCellInformation();
238 
239  protected:
241  ~vtkModifiedBSPTree() override;
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 
260  void BuildLocatorIfNeeded();
261  void ForceBuildLocator();
262  void BuildLocatorInternal();
263 private:
264  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
265  void operator=(const vtkModifiedBSPTree&) = delete;
266 };
267 
269 // BSP Node
270 // A BSP Node is a BBox - axis aligned etc etc
272 #ifndef DOXYGEN_SHOULD_SKIP_THIS
273 
274 class BSPNode {
275  public:
276  // Constructor
277  BSPNode(void) {
278  mChild[0] = mChild[1] = mChild[2] = nullptr;
279  for (int i=0; i<6; i++) sorted_cell_lists[i] = nullptr;
280  for (int i=0; i<3; i++) { this->Bounds[i*2] = VTK_FLOAT_MAX; this->Bounds[i*2+1] = -VTK_FLOAT_MAX; }
281  }
282  // Destructor
283  ~BSPNode(void) {
284  for (int i=0; i<3; i++) delete mChild[i];
285  for (int i=0; i<6; i++) delete []sorted_cell_lists[i];
286  }
287  // Set min box limits
288  void setMin(double minx, double miny, double minz) {
289  this->Bounds[0] = minx; this->Bounds[2] = miny; this->Bounds[4] = minz;
290  }
291  // Set max box limits
292  void setMax(double maxx, double maxy, double maxz) {
293  this->Bounds[1] = maxx; this->Bounds[3] = maxy; this->Bounds[5] = maxz;
294  }
295  //
296  bool Inside(double point[3]) const;
297  // BBox
298  double Bounds[6];
299  protected:
300  // The child nodes of this one (if present - nullptr otherwise)
302  // The axis we subdivide this voxel along
303  int mAxis;
304  // Just for reference
305  int depth;
306  // the number of cells in this node
308  // 6 lists, sorted after the 6 dominant axes
310  // Order nodes as near/mid far relative to ray
311  void Classify(const double origin[3], const double dir[3],
312  double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
313  // Test ray against node BBox : clip t values to extremes
314  bool RayMinMaxT(const double origin[3], const double dir[3],
315  double &rTmin, double &rTmax) const;
316  //
317  friend class vtkModifiedBSPTree;
318  friend class vtkParticleBoxTree;
319  public:
320  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(
321  const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
322  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
323 };
324 
325 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
326 
327 #endif
virtual void BuildLocator()=0
Build the locator from the input dataset.
virtual bool InsideCellBounds(double x[3], vtkIdType cell_ID)
Quickly test if a point is inside the bounds of a particular cell.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:56
BSPNode * mChild[3]
an abstract base class for locators which find cells
static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3])
int vtkIdType
Definition: vtkType.h:345
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
void Classify(const double origin[3], const double dir[3], double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const
#define VTK_FLOAT_MAX
Definition: vtkType.h:165
void setMax(double maxx, double maxy, double maxz)
a simple class to control print indentation
Definition: vtkIndent.h:33
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:30
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax) const
friend class vtkParticleBoxTree
void setMin(double minx, double miny, double minz)
bool Inside(double point[3]) const
virtual int IntersectWithLine(double p1[3], 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.
maintain an ordered list of IdList objects
vtkIdType * sorted_cell_lists[6]
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...
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
double Bounds[6]
represent and manipulate 3D points
Definition: vtkPoints.h:33
Generate axis aligned BBox tree for raycasting and other Locator based searches.