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(const double p1[3], const double p2[3], double tol, double &t, double x[3],
200  double pcoords[3], int &subId, vtkIdType &cellId) override;
201 
206  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3],
207  double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override;
208 
217  virtual int IntersectWithLine(
218  const double p1[3], const double p2[3], const double tol,
219  vtkPoints *points, vtkIdList *cellIds);
220 
225  vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
226  double pcoords[3], double *weights) override;
227 
228  bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
229 
235  vtkIdListCollection *GetLeafNodeCellInformation();
236 
237  protected:
239  ~vtkModifiedBSPTree() override;
240  //
241  BSPNode *mRoot; // bounding box root node
242  int npn;
243  int nln;
245 
246  //
247  // The main subdivision routine
248  void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet,
249  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth);
250 
251  // We provide a function which does the cell/ray test so that
252  // it can be overridden by subclasses to perform special treatment
253  // (Example : Particles stored in tree, have no dimension, so we must
254  // override the cell test to return a value based on some particle size
255  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
256  const double tol, double &t, double ipt[3], double pcoords[3], int &subId);
257 
258  void BuildLocatorIfNeeded();
259  void ForceBuildLocator();
260  void BuildLocatorInternal();
261 private:
262  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
263  void operator=(const vtkModifiedBSPTree&) = delete;
264 };
265 
267 // BSP Node
268 // A BSP Node is a BBox - axis aligned etc etc
270 #ifndef DOXYGEN_SHOULD_SKIP_THIS
271 
272 class BSPNode {
273  public:
274  // Constructor
275  BSPNode(void) {
276  mChild[0] = mChild[1] = mChild[2] = nullptr;
277  for (int i=0; i<6; i++) sorted_cell_lists[i] = nullptr;
278  for (int i=0; i<3; i++) { this->Bounds[i*2] = VTK_FLOAT_MAX; this->Bounds[i*2+1] = -VTK_FLOAT_MAX; }
279  }
280  // Destructor
281  ~BSPNode(void) {
282  for (int i=0; i<3; i++) delete mChild[i];
283  for (int i=0; i<6; i++) delete []sorted_cell_lists[i];
284  }
285  // Set min box limits
286  void setMin(double minx, double miny, double minz) {
287  this->Bounds[0] = minx; this->Bounds[2] = miny; this->Bounds[4] = minz;
288  }
289  // Set max box limits
290  void setMax(double maxx, double maxy, double maxz) {
291  this->Bounds[1] = maxx; this->Bounds[3] = maxy; this->Bounds[5] = maxz;
292  }
293  //
294  bool Inside(double point[3]) const;
295  // BBox
296  double Bounds[6];
297  protected:
298  // The child nodes of this one (if present - nullptr otherwise)
299  BSPNode *mChild[3];
300  // The axis we subdivide this voxel along
301  int mAxis;
302  // Just for reference
303  int depth;
304  // the number of cells in this node
305  int num_cells;
306  // 6 lists, sorted after the 6 dominant axes
307  vtkIdType *sorted_cell_lists[6];
308  // Order nodes as near/mid far relative to ray
309  void Classify(const double origin[3], const double dir[3],
310  double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
311  // Test ray against node BBox : clip t values to extremes
312  bool RayMinMaxT(const double origin[3], const double dir[3],
313  double &rTmin, double &rTmax) const;
314  //
315  friend class vtkModifiedBSPTree;
316  friend class vtkParticleBoxTree;
317  public:
318  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(
319  const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
320  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
321 };
322 
323 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
324 
325 #endif
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:33
vtkAbstractCellLocator::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkIdType
int vtkIdType
Definition: vtkType.h:347
vtkModifiedBSPTree::npn
int npn
Definition: vtkModifiedBSPTree.h:242
vtkModifiedBSPTree::mRoot
BSPNode * mRoot
Definition: vtkModifiedBSPTree.h:241
vtkObject::New
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on.
vtkAbstractCellLocator.h
vtkAbstractCellLocator::FindCell
virtual vtkIdType FindCell(double x[3])
Returns the Id of the cell containing the point, returns -1 if no cell found.
vtkX3D::dir
Definition: vtkX3D.h:324
vtkX3D::level
Definition: vtkX3D.h:395
vtkX3D::points
Definition: vtkX3D.h:446
vtkX3D::point
Definition: vtkX3D.h:236
vtkLocator::GenerateRepresentation
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
vtkAbstractCellLocator::InsideCellBounds
virtual bool InsideCellBounds(double x[3], vtkIdType cell_ID)
Quickly test if a point is inside the bounds of a particular cell.
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:33
vtkSmartPointer.h
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:30
vtkLocator::BuildLocator
virtual void BuildLocator()=0
Build the locator from the input dataset.
vtkIdListCollection
maintain an ordered list of IdList objects
Definition: vtkIdListCollection.h:31
VTK_FLOAT_MAX
#define VTK_FLOAT_MAX
Definition: vtkType.h:167
vtkModifiedBSPTree::nln
int nln
Definition: vtkModifiedBSPTree.h:243
vtkAbstractCellLocator
an abstract base class for locators which find cells
Definition: vtkAbstractCellLocator.h:48
vtkDataSet
abstract class to specify dataset behavior
Definition: vtkDataSet.h:56
vtkAbstractCellLocator::IntersectWithLine
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.
vtkModifiedBSPTree::tot_depth
int tot_depth
Definition: vtkModifiedBSPTree.h:244
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:36
vtkModifiedBSPTree
Generate axis aligned BBox tree for raycasting and other Locator based searches.
Definition: vtkModifiedBSPTree.h:156
vtkLocator::FreeSearchStructure
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.