VTK  9.1.20220518
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 =========================================================================*/
148 #ifndef vtkOBBTree_h
149 #define vtkOBBTree_h
150 
151 #include "vtkAbstractCellLocator.h"
152 #include "vtkFiltersGeneralModule.h" // For export macro
153 
154 class vtkMatrix4x4;
155 
156 // Special class defines node for the OBB tree
157 class VTKFILTERSGENERAL_EXPORT vtkOBBNode
158 { //;prevent man page generation
159 public:
162 
163  double Corner[3]; // center point of this node
164  double Axes[3][3]; // the axes defining the OBB - ordered from long->short
165  vtkOBBNode* Parent; // parent node; nullptr if root
166  vtkOBBNode** Kids; // two children of this node; nullptr if leaf
167  vtkIdList* Cells; // list of cells in node
168  void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);
169 
170 private:
171  vtkOBBNode(const vtkOBBNode& other) = delete;
172  vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
173 };
174 
175 class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
176 {
177 public:
179 
183  void PrintSelf(ostream& os, vtkIndent indent) override;
185 
190  static vtkOBBTree* New();
191 
192  // Re-use any superclass signatures that we don't override.
194 
201  int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
202  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
203 
216  const double a0[3], const double a1[3], vtkPoints* points, vtkIdList* cellIds) override;
217 
223  static void ComputeOBB(
224  vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);
225 
232  void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
233  double size[3]);
234 
240  int InsideOrOutside(const double point[3]);
241 
246  int DisjointOBBNodes(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA);
247 
251  int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3]);
252 
257  vtkOBBNode* pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4* XformBtoA);
258 
263  int IntersectWithOBBTree(vtkOBBTree* OBBTreeB, vtkMatrix4x4* XformBtoA,
264  int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
265  void* data_arg);
266 
268 
271  void FreeSearchStructure() override;
272  void BuildLocator() override;
273  void ForceBuildLocator() override;
275 
285  void GenerateRepresentation(int level, vtkPolyData* pd) override;
286 
287 protected:
289  ~vtkOBBTree() override;
290 
291  void BuildLocatorInternal() override;
292 
293  // Compute an OBB from the list of cells given. This used to be
294  // public but should not have been. A public call has been added
295  // so that the functionality can be accessed.
296  void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
297  double size[3]);
298 
300  void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
303  int OBBCount;
304 
305  void DeleteTree(vtkOBBNode* OBBptr);
307  vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);
308 
309 private:
310  vtkOBBTree(const vtkOBBTree&) = delete;
311  void operator=(const vtkOBBTree&) = delete;
312 };
313 
314 #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:296
abstract class to specify dataset behavior
Definition: vtkDataSet.h:172
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:143
a simple class to control print indentation
Definition: vtkIndent.h:119
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:151
vtkOBBNode * Parent
Definition: vtkOBBTree.h:165
vtkIdList * Cells
Definition: vtkOBBTree.h:167
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:166
generate oriented bounding box (OBB) tree
Definition: vtkOBBTree.h:176
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:299
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:301
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:303
int * InsertedPoints
Definition: vtkOBBTree.h:302
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:149
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:200
@ 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:332
#define max(a, b)