VTK  9.3.0
vtkOBBTree.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-License-Identifier: BSD-3-Clause
66 #ifndef vtkOBBTree_h
67 #define vtkOBBTree_h
68 
69 #include "vtkAbstractCellLocator.h"
70 #include "vtkFiltersGeneralModule.h" // For export macro
71 
72 VTK_ABI_NAMESPACE_BEGIN
73 class vtkMatrix4x4;
74 
75 // Special class defines node for the OBB tree
76 class VTKFILTERSGENERAL_EXPORT vtkOBBNode
77 { //;prevent man page generation
78 public:
81 
82  double Corner[3]; // center point of this node
83  double Axes[3][3]; // the axes defining the OBB - ordered from long->short
84  vtkOBBNode* Parent; // parent node; nullptr if root
85  vtkOBBNode** Kids; // two children of this node; nullptr if leaf
86  vtkIdList* Cells; // list of cells in node
87  void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);
88 
89 private:
90  vtkOBBNode(const vtkOBBNode& other) = delete;
91  vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
92 };
93 
94 class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
95 {
96 public:
98 
102  void PrintSelf(ostream& os, vtkIndent indent) override;
104 
109  static vtkOBBTree* New();
110 
111  // Re-use any superclass signatures that we don't 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 
135  const double a0[3], const double a1[3], vtkPoints* points, vtkIdList* cellIds) override;
136 
142  static void ComputeOBB(
143  vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);
144 
151  void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
152  double size[3]);
153 
159  int InsideOrOutside(const double point[3]);
160 
165  int DisjointOBBNodes(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA);
166 
170  int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3]);
171 
176  vtkOBBNode* pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4* XformBtoA);
177 
182  int IntersectWithOBBTree(vtkOBBTree* OBBTreeB, vtkMatrix4x4* XformBtoA,
183  int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
184  void* data_arg);
185 
187 
190  void FreeSearchStructure() override;
191  void BuildLocator() override;
192  void ForceBuildLocator() override;
194 
204  void GenerateRepresentation(int level, vtkPolyData* pd) override;
205 
206 protected:
208  ~vtkOBBTree() override;
209 
210  void BuildLocatorInternal() override;
211 
212  // Compute an OBB from the list of cells given. This used to be
213  // public but should not have been. A public call has been added
214  // so that the functionality can be accessed.
215  void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
216  double size[3]);
217 
219  void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
222  int OBBCount;
223 
224  void DeleteTree(vtkOBBNode* OBBptr);
226  vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);
227 
228 private:
229  vtkOBBTree(const vtkOBBTree&) = delete;
230  void operator=(const vtkOBBTree&) = delete;
231 };
232 
233 VTK_ABI_NAMESPACE_END
234 #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:185
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:32
a simple class to control print indentation
Definition: vtkIndent.h:38
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:40
vtkOBBNode * Parent
Definition: vtkOBBTree.h:84
vtkIdList * Cells
Definition: vtkOBBTree.h:86
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:85
generate oriented bounding box (OBB) tree
Definition: vtkOBBTree.h:95
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
Satisfy locator's abstract interface, see vtkLocator.
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:218
void PrintSelf(ostream &os, vtkIndent indent) override
Standard methods to print and obtain type-related information.
void BuildLocatorInternal() override
This function is not pure virtual to maintain backwards compatibility.
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:220
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:222
int * InsertedPoints
Definition: vtkOBBTree.h:221
void ForceBuildLocator() override
Satisfy locator's abstract interface, see vtkLocator.
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:38
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:89
@ point
Definition: vtkX3D.h:236
@ points
Definition: vtkX3D.h:446
@ level
Definition: vtkX3D.h:395
@ size
Definition: vtkX3D.h:253
int vtkIdType
Definition: vtkType.h:315
#define max(a, b)