VTK
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 =========================================================================*/
55 #ifndef __vtkOBBTree_h
56 #define __vtkOBBTree_h
57 
58 #include "vtkAbstractCellLocator.h"
59 
60 class vtkMatrix4x4;
61 
62 // Special class defines node for the OBB tree
63 //
64 //BTX
65 //
66 class VTK_GRAPHICS_EXPORT vtkOBBNode { //;prevent man page generation
67 public:
68  vtkOBBNode();
69  ~vtkOBBNode();
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; NULL if root
74  vtkOBBNode **Kids; //two children of this node; NULL if leaf
75  vtkIdList *Cells; //list of cells in node
76  void DebugPrintTree( int level, double *leaf_vol, int *minCells,
77  int *maxCells );
78 };
79 //ETX
80 //
81 
83 {
84 public:
86  void PrintSelf(ostream& os, vtkIndent indent);
87 
90  static vtkOBBTree *New();
91 
92 //BTX
93 /*
94  if the borland compiler is ever removed, we can use these declarations
95  instead of reimplementaing the calls in this subclass
96  using vtkAbstractCellLocator::IntersectWithLine;
97  using vtkAbstractCellLocator::FindClosestPoint;
98  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
99 */
100 //ETX
101 
103 
104  virtual int IntersectWithLine(
105  double a0[3], double a1[3], double tol,
106  double& t, double x[3], double pcoords[3],
107  int &subId)
108  {
109  return Superclass::
110  IntersectWithLine(a0, a1, tol,t, x, pcoords, subId);
111  }
113 
115 
116  virtual int IntersectWithLine(
117  double a0[3], double a1[3], double tol,
118  double& t, double x[3], double pcoords[3],
119  int &subId, vtkIdType &cellId)
120  {
121  return Superclass::
122  IntersectWithLine(a0, a1, tol,t, x, pcoords, subId, cellId);
123  }
125 
127 
135  int IntersectWithLine(const double a0[3], const double a1[3],
136  vtkPoints *points, vtkIdList *cellIds);
138 
140 
143  int IntersectWithLine(double a0[3], double a1[3], double tol,
144  double& t, double x[3], double pcoords[3],
145  int &subId, vtkIdType &cellId, vtkGenericCell *cell);
147 
149 
158  virtual void FindClosestPoint(
159  double x[3], double closestPoint[3],
160  vtkIdType &cellId, int &subId, double& dist2)
161  {
162  Superclass::
163  FindClosestPoint(x, closestPoint, cellId, subId, dist2);
164  }
166 
168 
169  virtual void FindClosestPoint(
170  double x[3], double closestPoint[3],
171  vtkGenericCell *cell, vtkIdType &cellId,
172  int &subId, double& dist2)
173  {
174  Superclass::
175  FindClosestPoint(x, closestPoint, cell, cellId, subId, dist2);
176  }
178 
180 
182  double x[3], double radius,
183  double closestPoint[3], vtkIdType &cellId,
184  int &subId, double& dist2)
185  {
186  return Superclass::FindClosestPointWithinRadius
187  (x, radius, closestPoint, cellId, subId, dist2);
188  }
190 
192 
194  double x[3], double radius,
195  double closestPoint[3],
196  vtkGenericCell *cell, vtkIdType &cellId,
197  int &subId, double& dist2)
198  {
199  return Superclass::FindClosestPointWithinRadius
200  (x, radius, closestPoint, cell, cellId, subId, dist2);
201  }
203 
205 
207  double x[3], double radius, double closestPoint[3],
208  vtkGenericCell *cell, vtkIdType &cellId,
209  int &subId, double& dist2, int &inside)
210  {
211  return Superclass::FindClosestPointWithinRadius
212  (x, radius, closestPoint, cell, cellId, subId, dist2, inside);
213  }
215 
217 
220  static void ComputeOBB(vtkPoints *pts, double corner[3], double max[3],
221  double mid[3], double min[3], double size[3]);
223 
225 
229  void ComputeOBB(vtkDataSet *input, double corner[3], double max[3],
230  double mid[3], double min[3], double size[3]);
232 
237  int InsideOrOutside(const double point[3]);
238 
239  //BTX
240 
242 
244  int DisjointOBBNodes( vtkOBBNode *nodeA, vtkOBBNode *nodeB,
245  vtkMatrix4x4 *XformBtoA );
247 
249  int LineIntersectsNode( vtkOBBNode *pA, double b0[3], double b1[3] );
250 
252 
253  int TriangleIntersectsNode( vtkOBBNode *pA,
254  double p0[3], double p1[3],
255  double p2[3], vtkMatrix4x4 *XformBtoA );
257 
259 
261  int IntersectWithOBBTree( vtkOBBTree *OBBTreeB, vtkMatrix4x4 *XformBtoA,
262  int(*function)( vtkOBBNode *nodeA,
263  vtkOBBNode *nodeB,
264  vtkMatrix4x4 *Xform,
265  void *arg ),
266  void *data_arg );
267  //ETX
269 
271 
272  void FreeSearchStructure();
273  void BuildLocator();
275 
285 
286  //BTX
287 protected:
288  vtkOBBTree();
289  ~vtkOBBTree();
290 
291  // Compute an OBB from the list of cells given. This used to be
292  // public but should not have been. A public call has been added
293  // so that the functionality can be accessed.
294  void ComputeOBB(vtkIdList *cells, double corner[3], double max[3],
295  double mid[3], double min[3], double size[3]);
296 
298  void BuildTree(vtkIdList *cells, vtkOBBNode *parent, int level);
301  int OBBCount;
302 
303  void DeleteTree(vtkOBBNode *OBBptr);
304  void GeneratePolygons(vtkOBBNode *OBBptr, int level, int repLevel,
305  vtkPoints* pts, vtkCellArray *polys);
306 
307  //ETX
308 private:
309  vtkOBBTree(const vtkOBBTree&); // Not implemented.
310  void operator=(const vtkOBBTree&); // Not implemented.
311 };
312 
313 #endif