VTK  9.1.0
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=========================================================================*/
132#ifndef vtkOBBTree_h
133#define vtkOBBTree_h
134
136#include "vtkFiltersGeneralModule.h" // For export macro
137
138class vtkMatrix4x4;
139
140// Special class defines node for the OBB tree
141//
142
143//
144class VTKFILTERSGENERAL_EXPORT vtkOBBNode
145{ //;prevent man page generation
146public:
149
150 double Corner[3]; // center point of this node
151 double Axes[3][3]; // the axes defining the OBB - ordered from long->short
152 vtkOBBNode* Parent; // parent node; nullptr if root
153 vtkOBBNode** Kids; // two children of this node; nullptr if leaf
154 vtkIdList* Cells; // list of cells in node
155 void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);
156
157private:
158 vtkOBBNode(const vtkOBBNode& other) = delete;
159 vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
160};
161
162//
163
164class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
165{
166public:
168 void PrintSelf(ostream& os, vtkIndent indent) override;
169
174 static vtkOBBTree* New();
175
176 // Re-use any superclass signatures that we don't override.
178
191 const double a0[3], const double a1[3], vtkPoints* points, vtkIdList* cellIds) override;
192
199 int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
200 double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
201
207 static void ComputeOBB(
208 vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);
209
216 void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
217 double size[3]);
218
224 int InsideOrOutside(const double point[3]);
225
230 int DisjointOBBNodes(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA);
231
235 int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3]);
236
241 vtkOBBNode* pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4* XformBtoA);
242
248 int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
249 void* data_arg);
250
252
255 void FreeSearchStructure() override;
256 void BuildLocator() override;
258
268 void GenerateRepresentation(int level, vtkPolyData* pd) override;
269
270protected:
272 ~vtkOBBTree() override;
273
274 // Compute an OBB from the list of cells given. This used to be
275 // public but should not have been. A public call has been added
276 // so that the functionality can be accessed.
277 void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
278 double size[3]);
279
281 void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
285
286 void DeleteTree(vtkOBBNode* OBBptr);
288 vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);
289
290private:
291 vtkOBBTree(const vtkOBBTree&) = delete;
292 void operator=(const vtkOBBTree&) = delete;
293};
294
295#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:290
abstract class to specify dataset behavior
Definition: vtkDataSet.h:166
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:140
a simple class to control print indentation
Definition: vtkIndent.h:113
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:145
vtkOBBNode * Parent
Definition: vtkOBBTree.h:152
vtkIdList * Cells
Definition: vtkOBBTree.h:154
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:153
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:280
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
int LineIntersectsNode(vtkOBBNode *pA, const double b0[3], const double b1[3])
Returns true if line intersects node.
static vtkOBBTree * New()
Construct with automatic computation of divisions, averaging 25 cells per octant.
void ComputeOBB(vtkIdList *cells, double corner[3], double max[3], double mid[3], double min[3], double size[3])
vtkPoints * PointsList
Definition: vtkOBBTree.h:282
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:284
int * InsertedPoints
Definition: vtkOBBTree.h:283
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:143
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:195
int vtkIdType
Definition: vtkType.h:332
#define max(a, b)