VTK  9.3.20240328
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
136 #ifndef vtkOBBTree_h
137 #define vtkOBBTree_h
138 
139 #include "vtkAbstractCellLocator.h"
140 #include "vtkFiltersGeneralModule.h" // For export macro
141 
142 VTK_ABI_NAMESPACE_BEGIN
143 class vtkMatrix4x4;
144 
145 // Special class defines node for the OBB tree
146 class VTKFILTERSGENERAL_EXPORT vtkOBBNode
147 { //;prevent man page generation
148 public:
151 
152  double Corner[3]; // center point of this node
153  double Axes[3][3]; // the axes defining the OBB - ordered from long->short
154  vtkOBBNode* Parent; // parent node; nullptr if root
155  vtkOBBNode** Kids; // two children of this node; nullptr if leaf
156  vtkIdList* Cells; // list of cells in node
157  void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);
158 
159 private:
160  vtkOBBNode(const vtkOBBNode& other) = delete;
161  vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
162 };
163 
164 class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
165 {
166 public:
168 
172  void PrintSelf(ostream& os, vtkIndent indent) override;
174 
179  static vtkOBBTree* New();
180 
181  // Re-use any superclass signatures that we don't override.
183 
190  int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
191  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
192 
205  const double a0[3], const double a1[3], vtkPoints* points, vtkIdList* cellIds) override;
206 
212  static void ComputeOBB(
213  vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);
214 
221  void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
222  double size[3]);
223 
229  int InsideOrOutside(const double point[3]);
230 
235  int DisjointOBBNodes(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA);
236 
240  int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3]);
241 
246  vtkOBBNode* pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4* XformBtoA);
247 
252  int IntersectWithOBBTree(vtkOBBTree* OBBTreeB, vtkMatrix4x4* XformBtoA,
253  int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
254  void* data_arg);
255 
257 
260  void FreeSearchStructure() override;
261  void BuildLocator() override;
262  void ForceBuildLocator() override;
264 
274  void GenerateRepresentation(int level, vtkPolyData* pd) override;
275 
276 protected:
278  ~vtkOBBTree() override;
279 
280  void BuildLocatorInternal() override;
281 
282  // Compute an OBB from the list of cells given. This used to be
283  // public but should not have been. A public call has been added
284  // so that the functionality can be accessed.
285  void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
286  double size[3]);
287 
289  void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
292  int OBBCount;
293 
294  void DeleteTree(vtkOBBNode* OBBptr);
296  vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);
297 
298 private:
299  vtkOBBTree(const vtkOBBTree&) = delete;
300  void operator=(const vtkOBBTree&) = delete;
301 };
302 
303 VTK_ABI_NAMESPACE_END
304 #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:285
abstract class to specify dataset behavior
Definition: vtkDataSet.h:165
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:132
a simple class to control print indentation
Definition: vtkIndent.h:108
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:140
vtkOBBNode * Parent
Definition: vtkOBBTree.h:154
vtkIdList * Cells
Definition: vtkOBBTree.h:156
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:155
generate oriented bounding box (OBB) tree
Definition: vtkOBBTree.h:165
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:288
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:290
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:292
int * InsertedPoints
Definition: vtkOBBTree.h:291
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:138
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:180
@ 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)