VTK  9.0.20210422
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
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:34
vtkOBBNode::~vtkOBBNode
~vtkOBBNode()
vtkOBBNode::Kids
vtkOBBNode ** Kids
Definition: vtkOBBTree.h:74
vtkOBBTree::DeleteTree
void DeleteTree(vtkOBBNode *OBBptr)
vtkOBBTree::~vtkOBBTree
~vtkOBBTree() override
vtkIdType
int vtkIdType
Definition: vtkType.h:338
vtkOBBTree::OBBCount
int OBBCount
Definition: vtkOBBTree.h:205
vtkOBBTree::IntersectWithLine
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.
vtkOBBTree::BuildLocator
void BuildLocator() override
Satisfy locator's abstract interface, see vtkLocator.
vtkOBBTree::IntersectWithLine
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...
vtkOBBTree
generate oriented bounding box (OBB) tree
Definition: vtkOBBTree.h:86
vtkAbstractCellLocator.h
vtkOBBTree::New
static vtkOBBTree * New()
Construct with automatic computation of divisions, averaging 25 cells per octant.
vtkOBBTree::ComputeOBB
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.
vtkOBBTree::PointsList
vtkPoints * PointsList
Definition: vtkOBBTree.h:203
vtkOBBNode::Parent
vtkOBBNode * Parent
Definition: vtkOBBTree.h:73
max
#define max(a, b)
Definition: vtkX3DExporterFIWriterHelper.h:31
vtkOBBTree::vtkOBBTree
vtkOBBTree()
vtkX3D::level
@ level
Definition: vtkX3D.h:401
vtkX3D::points
@ points
Definition: vtkX3D.h:452
vtkOBBTree::BuildTree
void BuildTree(vtkIdList *cells, vtkOBBNode *parent, int level)
vtkX3D::point
@ point
Definition: vtkX3D.h:242
vtkOBBNode::Cells
vtkIdList * Cells
Definition: vtkOBBTree.h:75
vtkOBBNode
Definition: vtkOBBTree.h:66
vtkOBBTree::GeneratePolygons
void GeneratePolygons(vtkOBBNode *OBBptr, int level, int repLevel, vtkPoints *pts, vtkCellArray *polys)
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:34
vtkMatrix4x4
represent and manipulate 4x4 transformation matrices
Definition: vtkMatrix4x4.h:36
vtkCellArray
object to represent cell connectivity
Definition: vtkCellArray.h:181
vtkOBBTree::LineIntersectsNode
int LineIntersectsNode(vtkOBBNode *pA, const double b0[3], const double b1[3])
Returns true if line intersects node.
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:31
vtkX3D::size
@ size
Definition: vtkX3D.h:259
vtkOBBTree::IntersectWithOBBTree
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.
vtkAbstractCellLocator
an abstract base class for locators which find cells
Definition: vtkAbstractCellLocator.h:49
vtkDataSet
abstract class to specify dataset behavior
Definition: vtkDataSet.h:57
vtkOBBNode::vtkOBBNode
vtkOBBNode()
vtkOBBTree::DisjointOBBNodes
int DisjointOBBNodes(vtkOBBNode *nodeA, vtkOBBNode *nodeB, vtkMatrix4x4 *XformBtoA)
Returns true if nodeB and nodeA are disjoint after optional transformation of nodeB with matrix Xform...
vtkOBBTree::FreeSearchStructure
void FreeSearchStructure() override
Satisfy locator's abstract interface, see vtkLocator.
vtkOBBTree::InsideOrOutside
int InsideOrOutside(const double point[3])
Determine whether a point is inside or outside the data used to build this OBB tree.
vtkAbstractCellLocator::IntersectWithLine
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.
vtkOBBTree::ComputeOBB
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.
vtkOBBTree::ComputeOBB
void ComputeOBB(vtkIdList *cells, double corner[3], double max[3], double mid[3], double min[3], double size[3])
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
vtkOBBTree::GenerateRepresentation
void GenerateRepresentation(int level, vtkPolyData *pd) override
Create polygonal representation for OBB tree at specified level.
vtkGenericCell
provides thread-safe access to cells
Definition: vtkGenericCell.h:37
vtkOBBTree::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkOBBNode::DebugPrintTree
void DebugPrintTree(int level, double *leaf_vol, int *minCells, int *maxCells)
vtkOBBTree::InsertedPoints
int * InsertedPoints
Definition: vtkOBBTree.h:204
vtkOBBTree::Tree
vtkOBBNode * Tree
Definition: vtkOBBTree.h:201
vtkOBBTree::TriangleIntersectsNode
int TriangleIntersectsNode(vtkOBBNode *pA, double p0[3], double p1[3], double p2[3], vtkMatrix4x4 *XformBtoA)
Returns true if triangle (optionally transformed) intersects node.