VTK  9.2.6
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 =========================================================================*/
163 #ifndef vtkModifiedBSPTree_h
164 #define vtkModifiedBSPTree_h
165 
166 #include "vtkAbstractCellLocator.h"
167 #include "vtkFiltersFlowPathsModule.h" // For export macro
168 #include "vtkSmartPointer.h" // required because it is nice
169 
170 class Sorted_cell_extents_Lists;
171 class BSPNode;
172 class vtkGenericCell;
173 class vtkIdList;
174 class vtkIdListCollection;
175 
176 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
177 {
178 public:
180 
184  void PrintSelf(ostream& os, vtkIndent indent) override;
186 
190  static vtkModifiedBSPTree* New();
191 
192  // Re-use any superclass signatures that we don't override.
195 
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, vtkGenericCell* cell) override;
204 
214  int IntersectWithLine(const double p1[3], const double p2[3], const double tol, vtkPoints* points,
215  vtkIdList* cellIds, vtkGenericCell* cell) override;
216 
226  const double p1[3], const double p2[3], double tolerance, vtkIdList* cellsIds) override
227  {
228  this->Superclass::FindCellsAlongLine(p1, p2, tolerance, cellsIds);
229  }
230 
238  vtkIdType FindCell(double x[3], double vtkNotUsed(tol2), vtkGenericCell* GenCell, int& subId,
239  double pcoords[3], double* weights) override;
240 
246  vtkIdListCollection* GetLeafNodeCellInformation();
247 
251  virtual void GenerateRepresentationLeafs(vtkPolyData* pd);
252 
254 
257  void GenerateRepresentation(int level, vtkPolyData* pd) override;
258  void FreeSearchStructure() override;
259  void BuildLocator() override;
260  void ForceBuildLocator() override;
262 
266  void ShallowCopy(vtkAbstractCellLocator* locator) override;
267 
268 protected:
270  ~vtkModifiedBSPTree() override;
271 
272  void BuildLocatorInternal() override;
273  std::shared_ptr<BSPNode> mRoot; // bounding box root node
274  int npn;
275  int nln;
277 
278  // The main subdivision routine
279  void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
280  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
281 
282 private:
283  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
284  void operator=(const vtkModifiedBSPTree&) = delete;
285 };
286 
288 // BSP Node
289 // A BSP Node is a BBox - axis aligned etc etc
291 #ifndef DOXYGEN_SHOULD_SKIP_THIS
292 
293 class BSPNode
294 {
295 public:
296  // Constructor
297  BSPNode(void)
298  {
299  mChild[0] = mChild[1] = mChild[2] = nullptr;
300  for (int i = 0; i < 6; i++)
301  sorted_cell_lists[i] = nullptr;
302  for (int i = 0; i < 3; i++)
303  {
304  this->Bounds[i * 2] = VTK_FLOAT_MAX;
305  this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
306  }
307  }
308  // Destructor
309  ~BSPNode(void)
310  {
311  for (int i = 0; i < 3; i++)
312  delete mChild[i];
313  for (int i = 0; i < 6; i++)
314  delete[] sorted_cell_lists[i];
315  }
316  // Set min box limits
317  void setMin(double minx, double miny, double minz)
318  {
319  this->Bounds[0] = minx;
320  this->Bounds[2] = miny;
321  this->Bounds[4] = minz;
322  }
323  // Set max box limits
324  void setMax(double maxx, double maxy, double maxz)
325  {
326  this->Bounds[1] = maxx;
327  this->Bounds[3] = maxy;
328  this->Bounds[5] = maxz;
329  }
330  //
331  bool Inside(double point[3]) const;
332  // BBox
333  double Bounds[6];
334 
335 protected:
336  // The child nodes of this one (if present - nullptr otherwise)
337  BSPNode* mChild[3];
338  // The axis we subdivide this voxel along
339  int mAxis;
340  // Just for reference
341  int depth;
342  // the number of cells in this node
343  int num_cells;
344  // 6 lists, sorted after the 6 dominant axes
345  vtkIdType* sorted_cell_lists[6];
346  // Order nodes as near/mid far relative to ray
347  void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
348  BSPNode*& Mid, BSPNode*& Far) const;
349  friend class vtkModifiedBSPTree;
350 
351 public:
352  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
353 };
354 
355 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
356 
357 #endif
virtual void BuildLocator()=0
Build the locator from the input dataset.
void FindCellsAlongLine(const double p1[3], const double p2[3], double tolerance, vtkIdList *cellsIds) override
Take the passed line segment and intersect it with the data set.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
an abstract base class for locators which find cells
int vtkIdType
Definition: vtkType.h:332
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:90
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
provides thread-safe access to cells
virtual void ShallowCopy(vtkAbstractCellLocator *)
Shallow copy of a vtkAbstractCellLocator.
#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:39
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:203
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:33
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...
std::shared_ptr< BSPNode > mRoot
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:39
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:167
Generate axis aligned BBox tree for ray-casting and other Locator based searches. ...