VTK  9.0.1
vtkOBBTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkOBBTree.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 =========================================================================*/
53 #ifndef vtkOBBTree_h
54 #define vtkOBBTree_h
55 
56 #include "vtkAbstractCellLocator.h"
57 #include "vtkFiltersGeneralModule.h" // For export macro
58 
59 class vtkMatrix4x4;
60 
61 // Special class defines node for the OBB tree
62 //
63 
64 //
65 class VTKFILTERSGENERAL_EXPORT vtkOBBNode
66 { //;prevent man page generation
67 public:
70 
71  double Corner[3]; // center point of this node
72  double Axes[3][3]; // the axes defining the OBB - ordered from long->short
73  vtkOBBNode* Parent; // parent node; nullptr if root
74  vtkOBBNode** Kids; // two children of this node; nullptr if leaf
75  vtkIdList* Cells; // list of cells in node
76  void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);
77 
78 private:
79  vtkOBBNode(const vtkOBBNode& other) = delete;
80  vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
81 };
82 
83 //
84 
85 class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
86 {
87 public:
89  void PrintSelf(ostream& os, vtkIndent indent) override;
90 
95  static vtkOBBTree* New();
96 
97  // Re-use any superclass signatures that we don't override.
99 
112  const double a0[3], const double a1[3], vtkPoints* points, vtkIdList* cellIds) override;
113 
120  int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
121  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
122 
128  static void ComputeOBB(
129  vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);
130 
137  void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
138  double size[3]);
139 
145  int InsideOrOutside(const double point[3]);
146 
151  int DisjointOBBNodes(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA);
152 
156  int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3]);
157 
162  vtkOBBNode* pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4* XformBtoA);
163 
168  int IntersectWithOBBTree(vtkOBBTree* OBBTreeB, vtkMatrix4x4* XformBtoA,
169  int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
170  void* data_arg);
171 
173 
176  void FreeSearchStructure() override;
177  void BuildLocator() override;
179 
189  void GenerateRepresentation(int level, vtkPolyData* pd) override;
190 
191 protected:
193  ~vtkOBBTree() override;
194 
195  // Compute an OBB from the list of cells given. This used to be
196  // public but should not have been. A public call has been added
197  // so that the functionality can be accessed.
198  void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
199  double size[3]);
200 
202  void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
205  int OBBCount;
206 
207  void DeleteTree(vtkOBBNode* OBBptr);
209  vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);
210 
211 private:
212  vtkOBBTree(const vtkOBBTree&) = delete;
213  void operator=(const vtkOBBTree&) = delete;
214 };
215 
216 #endif
an abstract base class for locators which find cells
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.
object to represent cell connectivity
Definition: vtkCellArray.h:180
abstract class to specify dataset behavior
Definition: vtkDataSet.h:57
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:31
a simple class to control print indentation
Definition: vtkIndent.h:34
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:36
vtkOBBNode * Parent
Definition: vtkOBBTree.h:73
vtkIdList * Cells
Definition: vtkOBBTree.h:75
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:74
generate oriented bounding box (OBB) tree
Definition: vtkOBBTree.h:86
void ComputeOBB(vtkDataSet *input, double corner[3], double max[3], double mid[3], double min[3], double size[3])
Compute an OBB for the input dataset using the cells in the data.
void BuildLocator() override
Build the locator from the input dataset.
void FreeSearchStructure() override
Satisfy locator's abstract interface, see vtkLocator.
int IntersectWithLine(const double a0[3], const double a1[3], double tol, double &t, double x[3], double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell) override
Return the first intersection of the specified line segment with the OBB tree, as well as information...
int DisjointOBBNodes(vtkOBBNode *nodeA, vtkOBBNode *nodeB, vtkMatrix4x4 *XformBtoA)
Returns true if nodeB and nodeA are disjoint after optional transformation of nodeB with matrix Xform...
int InsideOrOutside(const double point[3])
Determine whether a point is inside or outside the data used to build this OBB tree.
void GenerateRepresentation(int level, vtkPolyData *pd) override
Create polygonal representation for OBB tree at specified level.
void GeneratePolygons(vtkOBBNode *OBBptr, int level, int repLevel, vtkPoints *pts, vtkCellArray *polys)
~vtkOBBTree() override
vtkOBBNode * Tree
Definition: vtkOBBTree.h:201
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
static vtkOBBTree * New()
Construct with automatic computation of divisions, averaging 25 cells per octant.
int LineIntersectsNode(vtkOBBNode *pA, const double b0[3], const double b1[3])
Returns true if line intersects node.
void ComputeOBB(vtkIdList *cells, double corner[3], double max[3], double mid[3], double min[3], double size[3])
vtkPoints * PointsList
Definition: vtkOBBTree.h:203
int IntersectWithLine(const double a0[3], const double a1[3], vtkPoints *points, vtkIdList *cellIds) override
Take the passed line segment and intersect it with the data set.
int IntersectWithOBBTree(vtkOBBTree *OBBTreeB, vtkMatrix4x4 *XformBtoA, int(*function)(vtkOBBNode *nodeA, vtkOBBNode *nodeB, vtkMatrix4x4 *Xform, void *arg), void *data_arg)
For each intersecting leaf node pair, call function.
int TriangleIntersectsNode(vtkOBBNode *pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4 *XformBtoA)
Returns true if triangle (optionally transformed) intersects node.
int OBBCount
Definition: vtkOBBTree.h:205
int * InsertedPoints
Definition: vtkOBBTree.h:204
void DeleteTree(vtkOBBNode *OBBptr)
static void ComputeOBB(vtkPoints *pts, double corner[3], double max[3], double mid[3], double min[3], double size[3])
Compute an OBB from the list of points given.
void BuildTree(vtkIdList *cells, vtkOBBNode *parent, int level)
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:85
@ point
Definition: vtkX3D.h:242
@ points
Definition: vtkX3D.h:452
@ level
Definition: vtkX3D.h:401
@ size
Definition: vtkX3D.h:259
int vtkIdType
Definition: vtkType.h:338
#define max(a, b)