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 =========================================================================*/
146 #ifndef vtkModifiedBSPTree_h
147 #define vtkModifiedBSPTree_h
148 
149 #include "vtkFiltersFlowPathsModule.h" // For export macro
150 #include "vtkAbstractCellLocator.h"
151 #include "vtkSmartPointer.h" // required because it is nice
152 
153 class Sorted_cell_extents_Lists;
154 class BSPNode;
155 class vtkGenericCell;
156 class vtkIdList;
157 class vtkIdListCollection;
158 
159 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator {
160  public:
162 
166  void PrintSelf(ostream& os, vtkIndent indent);
168 
173 
174  // Re-use any superclass signatures that we don't override.
177 
182 
186  void BuildLocator();
187 
191  virtual void GenerateRepresentation(int level, vtkPolyData *pd);
192 
197 
202  virtual int IntersectWithLine(
203  double p1[3], double p2[3], double tol, double &t, double x[3],
204  double pcoords[3], int &subId, vtkIdType &cellId);
205 
210  virtual int IntersectWithLine(
211  double p1[3], double p2[3], double tol, double &t, double x[3],
212  double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell);
213 
222  virtual int IntersectWithLine(
223  const double p1[3], const double p2[3], const double tol,
224  vtkPoints *points, vtkIdList *cellIds);
225 
230  virtual vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
231  double pcoords[3], double *weights);
232 
233  bool InsideCellBounds(double x[3], vtkIdType cell_ID);
234 
241 
242  protected:
245  //
246  BSPNode *mRoot; // bounding box root node
247  int npn;
248  int nln;
250 
251  //
252  // The main subdivision routine
253  void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet,
254  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth);
255 
256  // We provide a function which does the cell/ray test so that
257  // it can be overriden by subclasses to perform special treatment
258  // (Example : Particles stored in tree, have no dimension, so we must
259  // override the cell test to return a value based on some particle size
260  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
261  const double tol, double &t, double ipt[3], double pcoords[3], int &subId);
262 
266 private:
267  vtkModifiedBSPTree(const vtkModifiedBSPTree&) VTK_DELETE_FUNCTION;
268  void operator=(const vtkModifiedBSPTree&) VTK_DELETE_FUNCTION;
269 };
270 
272 // BSP Node
273 // A BSP Node is a BBox - axis aligned etc etc
275 #ifndef DOXYGEN_SHOULD_SKIP_THIS
276 
277 class BSPNode {
278  public:
279  // Constructor
280  BSPNode(void) {
281  mChild[0] = mChild[1] = mChild[2] = NULL;
282  for (int i=0; i<6; i++) sorted_cell_lists[i] = NULL;
283  for (int i=0; i<3; i++) { this->Bounds[i*2] = VTK_FLOAT_MAX; this->Bounds[i*2+1] = -VTK_FLOAT_MAX; }
284  }
285  // Destructor
286  ~BSPNode(void) {
287  for (int i=0; i<3; i++) delete mChild[i];
288  for (int i=0; i<6; i++) delete []sorted_cell_lists[i];
289  }
290  // Set min box limits
291  void setMin(double minx, double miny, double minz) {
292  this->Bounds[0] = minx; this->Bounds[2] = miny; this->Bounds[4] = minz;
293  }
294  // Set max box limits
295  void setMax(double maxx, double maxy, double maxz) {
296  this->Bounds[1] = maxx; this->Bounds[3] = maxy; this->Bounds[5] = maxz;
297  }
298  //
299  bool Inside(double point[3]) const;
300  // BBox
301  double Bounds[6];
302  protected:
303  // The child nodes of this one (if present - NULL otherwise)
305  // The axis we subdivide this voxel along
306  int mAxis;
307  // Just for reference
308  int depth;
309  // the number of cells in this node
311  // 6 lists, sorted after the 6 dominant axes
313  // Order nodes as near/mid far relative to ray
314  void Classify(const double origin[3], const double dir[3],
315  double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
316  // Test ray against node BBox : clip t values to extremes
317  bool RayMinMaxT(const double origin[3], const double dir[3],
318  double &rTmin, double &rTmax) const;
319  //
320  friend class vtkModifiedBSPTree;
321  friend class vtkParticleBoxTree;
322  public:
323  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(
324  const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
325  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
326 };
327 
328 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
329 
330 #endif
BSPNode * mChild[3]
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax) const
void setMin(double minx, double miny, double minz)
void setMax(double maxx, double maxy, double maxz)
static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax)
void Classify(const double origin[3], const double dir[3], double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const
static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3])
bool Inside(double point[3]) const
double Bounds[6]
vtkIdType * sorted_cell_lists[6]
friend class vtkParticleBoxTree
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(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.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:63
provides thread-safe access to cells
maintain an unordered list of dataarray objects
list of point or cell ids
Definition: vtkIdList.h:37
a simple class to control print indentation
Definition: vtkIndent.h:40
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)
void FreeSearchStructure()
Free tree memory.
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell)
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.
void PrintSelf(ostream &os, vtkIndent indent)
Methods invoked by print to print information about the object including superclasses.
virtual void GenerateRepresentation(int level, vtkPolyData *pd)
Generate BBox representation of Nth level.
void BuildLocator()
Build Tree.
vtkIdListCollection * GetLeafNodeCellInformation()
After subdivision has completed, one may wish to query the tree to find which cells are in which leaf...
bool InsideCellBounds(double x[3], vtkIdType cell_ID)
Quickly test if a point is inside the bounds of a particular cell.
void BuildLocatorIfNeeded()
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId)
Return intersection point (if any) AND the cell which was intersected by the finite line.
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 BuildLocatorInternal()
virtual vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell, double pcoords[3], double *weights)
Test a point to find if it is inside a cell.
represent and manipulate 3D points
Definition: vtkPoints.h:40
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
@ point
Definition: vtkX3D.h:236
@ points
Definition: vtkX3D.h:446
@ level
Definition: vtkX3D.h:395
@ dir
Definition: vtkX3D.h:324
int vtkIdType
Definition: vtkType.h:287
#define VTK_FLOAT_MAX
Definition: vtkType.h:161