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
151#include "vtkSmartPointer.h" // required because it is nice
152
153class Sorted_cell_extents_Lists;
154class BSPNode;
155class vtkGenericCell;
156class vtkIdList;
158
159class 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
187
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
266private:
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
277class 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.
bool InsideCellBounds(double x[3], vtkIdType cell_ID)
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 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)
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.
static vtkModifiedBSPTree * New()
Construct with maximum 32 cells per node.
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