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=========================================================================*/
204#ifndef vtkModifiedBSPTree_h
205#define vtkModifiedBSPTree_h
206
208#include "vtkFiltersFlowPathsModule.h" // For export macro
209#include "vtkSmartPointer.h" // required because it is nice
210
211class Sorted_cell_extents_Lists;
212class BSPNode;
213class vtkGenericCell;
214class vtkIdList;
216
217class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
218{
219public:
221
225 void PrintSelf(ostream& os, vtkIndent indent) override;
227
232
233 // Re-use any superclass signatures that we don't override.
236
240 void FreeSearchStructure() override;
241
245 void BuildLocator() override;
246
250 void GenerateRepresentation(int level, vtkPolyData* pd) override;
251
256
261 int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
262 double pcoords[3], int& subId, vtkIdType& cellId) override;
263
268 int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
269 double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
270
279 virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol,
280 vtkPoints* points, vtkIdList* cellIds);
281
287 double x[3], double tol2, vtkGenericCell* GenCell, double pcoords[3], double* weights) override;
288
289 bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
290
297
298protected:
301 //
302 BSPNode* mRoot; // bounding box root node
303 int npn;
304 int nln;
306
307 //
308 // The main subdivision routine
309 void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
310 vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
311
312 // We provide a function which does the cell/ray test so that
313 // it can be overridden by subclasses to perform special treatment
314 // (Example : Particles stored in tree, have no dimension, so we must
315 // override the cell test to return a value based on some particle size
316 virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
317 const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
318
322
323private:
324 vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
325 void operator=(const vtkModifiedBSPTree&) = delete;
326};
327
329// BSP Node
330// A BSP Node is a BBox - axis aligned etc etc
332#ifndef DOXYGEN_SHOULD_SKIP_THIS
333
334class BSPNode
335{
336public:
337 // Constructor
338 BSPNode(void)
339 {
340 mChild[0] = mChild[1] = mChild[2] = nullptr;
341 for (int i = 0; i < 6; i++)
342 sorted_cell_lists[i] = nullptr;
343 for (int i = 0; i < 3; i++)
344 {
345 this->Bounds[i * 2] = VTK_FLOAT_MAX;
346 this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
347 }
348 }
349 // Destructor
350 ~BSPNode(void)
351 {
352 for (int i = 0; i < 3; i++)
353 delete mChild[i];
354 for (int i = 0; i < 6; i++)
355 delete[] sorted_cell_lists[i];
356 }
357 // Set min box limits
358 void setMin(double minx, double miny, double minz)
359 {
360 this->Bounds[0] = minx;
361 this->Bounds[2] = miny;
362 this->Bounds[4] = minz;
363 }
364 // Set max box limits
365 void setMax(double maxx, double maxy, double maxz)
366 {
367 this->Bounds[1] = maxx;
368 this->Bounds[3] = maxy;
369 this->Bounds[5] = maxz;
370 }
371 //
372 bool Inside(double point[3]) const;
373 // BBox
374 double Bounds[6];
375
376protected:
377 // The child nodes of this one (if present - nullptr otherwise)
378 BSPNode* mChild[3];
379 // The axis we subdivide this voxel along
380 int mAxis;
381 // Just for reference
382 int depth;
383 // the number of cells in this node
384 int num_cells;
385 // 6 lists, sorted after the 6 dominant axes
386 vtkIdType* sorted_cell_lists[6];
387 // Order nodes as near/mid far relative to ray
388 void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
389 BSPNode*& Mid, BSPNode*& Far) const;
390 // Test ray against node BBox : clip t values to extremes
391 bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax) const;
392 //
393 friend class vtkModifiedBSPTree;
394 friend class vtkParticleBoxTree;
395
396public:
397 static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3],
398 const double dir[3], double& rTmin, double& rTmax);
399 static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
400};
401
402#endif /* DOXYGEN_SHOULD_SKIP_THIS */
403
404#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:166
provides thread-safe access to cells
maintain an ordered list of IdList objects
list of point or cell ids
Definition: vtkIdList.h:140
a simple class to control print indentation
Definition: vtkIndent.h:113
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:143
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:195
int vtkIdType
Definition: vtkType.h:332
#define VTK_FLOAT_MAX
Definition: vtkType.h:163