VTK  9.1.0
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=========================================================================*/
145#ifndef vtkModifiedBSPTree_h
146#define vtkModifiedBSPTree_h
147
149#include "vtkFiltersFlowPathsModule.h" // For export macro
150#include "vtkSmartPointer.h" // required because it is nice
151
152class Sorted_cell_extents_Lists;
153class BSPNode;
154class vtkGenericCell;
155class vtkIdList;
157
158class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
159{
160public:
162
166 void PrintSelf(ostream& os, vtkIndent indent) override;
168
173
174 // Re-use any superclass signatures that we don't override.
177
181 void FreeSearchStructure() override;
182
186 void BuildLocator() override;
187
191 void GenerateRepresentation(int level, vtkPolyData* pd) override;
192
197
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) override;
204
209 int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
210 double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
211
220 virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol,
221 vtkPoints* points, vtkIdList* cellIds);
222
228 double x[3], double tol2, vtkGenericCell* GenCell, double pcoords[3], double* weights) override;
229
230 bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
231
238
239protected:
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
263
264private:
265 vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
266 void operator=(const vtkModifiedBSPTree&) = delete;
267};
268
270// BSP Node
271// A BSP Node is a BBox - axis aligned etc etc
273#ifndef DOXYGEN_SHOULD_SKIP_THIS
274
275class BSPNode
276{
277public:
278 // Constructor
279 BSPNode(void)
280 {
281 mChild[0] = mChild[1] = mChild[2] = nullptr;
282 for (int i = 0; i < 6; i++)
283 sorted_cell_lists[i] = nullptr;
284 for (int i = 0; i < 3; i++)
285 {
286 this->Bounds[i * 2] = VTK_FLOAT_MAX;
287 this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
288 }
289 }
290 // Destructor
291 ~BSPNode(void)
292 {
293 for (int i = 0; i < 3; i++)
294 delete mChild[i];
295 for (int i = 0; i < 6; i++)
296 delete[] sorted_cell_lists[i];
297 }
298 // Set min box limits
299 void setMin(double minx, double miny, double minz)
300 {
301 this->Bounds[0] = minx;
302 this->Bounds[2] = miny;
303 this->Bounds[4] = minz;
304 }
305 // Set max box limits
306 void setMax(double maxx, double maxy, double maxz)
307 {
308 this->Bounds[1] = maxx;
309 this->Bounds[3] = maxy;
310 this->Bounds[5] = maxz;
311 }
312 //
313 bool Inside(double point[3]) const;
314 // BBox
315 double Bounds[6];
316
317protected:
318 // The child nodes of this one (if present - nullptr otherwise)
319 BSPNode* mChild[3];
320 // The axis we subdivide this voxel along
321 int mAxis;
322 // Just for reference
323 int depth;
324 // the number of cells in this node
325 int num_cells;
326 // 6 lists, sorted after the 6 dominant axes
327 vtkIdType* sorted_cell_lists[6];
328 // Order nodes as near/mid far relative to ray
329 void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
330 BSPNode*& Mid, BSPNode*& Far) const;
331 // Test ray against node BBox : clip t values to extremes
332 bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax) const;
333 //
334 friend class vtkModifiedBSPTree;
335 friend class vtkParticleBoxTree;
336
337public:
338 static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3],
339 const double dir[3], double& rTmin, double& rTmax);
340 static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
341};
342
343#endif /* DOXYGEN_SHOULD_SKIP_THIS */
344
345#endif
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(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.
abstract class to specify dataset behavior
Definition: vtkDataSet.h:57
provides thread-safe access to cells
maintain an ordered list of IdList objects
list of point or cell ids
Definition: vtkIdList.h:31
a simple class to control print indentation
Definition: vtkIndent.h:34
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)
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId) override
Return intersection point (if any) AND the cell which was intersected by the finite line.
vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell, double pcoords[3], double *weights) override
Test a point to find if it is inside a cell.
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override
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.
~vtkModifiedBSPTree() override
void GenerateRepresentation(int level, vtkPolyData *pd) override
Generate BBox representation of Nth level.
void PrintSelf(ostream &os, vtkIndent indent) override
Standard Type-Macro.
bool InsideCellBounds(double x[3], vtkIdType cell_ID) override
Quickly test if a point is inside the bounds of a particular cell.
void BuildLocatorIfNeeded()
vtkIdListCollection * GetLeafNodeCellInformation()
After subdivision has completed, one may wish to query the tree to find which cells are in which leaf...
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)
void FreeSearchStructure() override
Free tree memory.
void BuildLocatorInternal()
void BuildLocator() override
Build Tree.
static vtkModifiedBSPTree * New()
Construct with maximum 32 cells per node.
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
@ point
Definition: vtkX3D.h:242
@ points
Definition: vtkX3D.h:452
@ level
Definition: vtkX3D.h:401
@ dir
Definition: vtkX3D.h:330
int vtkIdType
Definition: vtkType.h:332
#define VTK_FLOAT_MAX
Definition: vtkType.h:163