VTK  9.0.1
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 "vtkAbstractCellLocator.h"
147 #include "vtkFiltersFlowPathsModule.h" // For export macro
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 {
158 public:
160 
164  void PrintSelf(ostream& os, vtkIndent indent) override;
166 
170  static vtkModifiedBSPTree* New();
171 
172  // Re-use any superclass signatures that we don't override.
175 
179  void FreeSearchStructure() override;
180 
184  void BuildLocator() override;
185 
189  void GenerateRepresentation(int level, vtkPolyData* pd) override;
190 
194  virtual void GenerateRepresentationLeafs(vtkPolyData* pd);
195 
200  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
201  double pcoords[3], int& subId, vtkIdType& cellId) override;
202 
207  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
208  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
209 
218  virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol,
219  vtkPoints* points, vtkIdList* cellIds);
220 
226  double x[3], double tol2, vtkGenericCell* GenCell, 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 
262 private:
263  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
264  void operator=(const vtkModifiedBSPTree&) = delete;
265 };
266 
268 // BSP Node
269 // A BSP Node is a BBox - axis aligned etc etc
271 #ifndef DOXYGEN_SHOULD_SKIP_THIS
272 
273 class BSPNode
274 {
275 public:
276  // Constructor
277  BSPNode(void)
278  {
279  mChild[0] = mChild[1] = mChild[2] = nullptr;
280  for (int i = 0; i < 6; i++)
281  sorted_cell_lists[i] = nullptr;
282  for (int i = 0; i < 3; i++)
283  {
284  this->Bounds[i * 2] = VTK_FLOAT_MAX;
285  this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
286  }
287  }
288  // Destructor
289  ~BSPNode(void)
290  {
291  for (int i = 0; i < 3; i++)
292  delete mChild[i];
293  for (int i = 0; i < 6; i++)
294  delete[] sorted_cell_lists[i];
295  }
296  // Set min box limits
297  void setMin(double minx, double miny, double minz)
298  {
299  this->Bounds[0] = minx;
300  this->Bounds[2] = miny;
301  this->Bounds[4] = minz;
302  }
303  // Set max box limits
304  void setMax(double maxx, double maxy, double maxz)
305  {
306  this->Bounds[1] = maxx;
307  this->Bounds[3] = maxy;
308  this->Bounds[5] = maxz;
309  }
310  //
311  bool Inside(double point[3]) const;
312  // BBox
313  double Bounds[6];
314 
315 protected:
316  // The child nodes of this one (if present - nullptr otherwise)
317  BSPNode* mChild[3];
318  // The axis we subdivide this voxel along
319  int mAxis;
320  // Just for reference
321  int depth;
322  // the number of cells in this node
323  int num_cells;
324  // 6 lists, sorted after the 6 dominant axes
325  vtkIdType* sorted_cell_lists[6];
326  // Order nodes as near/mid far relative to ray
327  void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
328  BSPNode*& Mid, BSPNode*& Far) const;
329  // Test ray against node BBox : clip t values to extremes
330  bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax) const;
331  //
332  friend class vtkModifiedBSPTree;
333  friend class vtkParticleBoxTree;
334 
335 public:
336  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3],
337  const double dir[3], double& rTmin, double& rTmax);
338  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
339 };
340 
341 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
342 
343 #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
an abstract base class for locators which find cells
int vtkIdType
Definition: vtkType.h:338
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:84
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
provides thread-safe access to cells
#define VTK_FLOAT_MAX
Definition: vtkType.h:163
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: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
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...
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:33
Generate axis aligned BBox tree for raycasting and other Locator based searches.