VTK
vtkModifiedBSPTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkModifiedBSPTree.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 =========================================================================*/
15 
16 /*=========================================================================
17  This code is derived from an earlier work and is distributed
18  with permission from, and thanks to
19 
20  ------------------------------------------
21  Copyright (C) 1997-2000 John Biddiscombe
22  Rutherford Appleton Laboratory,
23  Chilton, Oxon, England
24  ------------------------------------------
25  Copyright (C) 2000-2004 John Biddiscombe
26  Skipping Mouse Software Ltd,
27  Blewbury, England
28  ------------------------------------------
29  Copyright (C) 2004-2009 John Biddiscombe
30  CSCS - Swiss National Supercomputing Centre
31  Galleria 2 - Via Cantonale
32  CH-6928 Manno, Switzerland
33  ------------------------------------
34 =========================================================================*/
145 #ifndef _vtkModifiedBSPTree_h
146 #define _vtkModifiedBSPTree_h
147 
148 #include "vtkAbstractCellLocator.h"
149 #include "vtkSmartPointer.h" // required because it is nice
150 
151 //BTX
152 class Sorted_cell_extents_Lists;
153 class BSPNode;
154 class vtkGenericCell;
155 class vtkIdList;
156 class vtkIdListCollection;
157 //ETX
158 
160  public:
162 
164  void PrintSelf(ostream& os, vtkIndent indent);
166 
168  static vtkModifiedBSPTree *New();
169 
170 //BTX
174 //ETX
175 
177  void FreeSearchStructure();
178 
180  void BuildLocator();
181 
182 //BTX
184  virtual void GenerateRepresentation(int level, vtkPolyData *pd);
185 
187  virtual void GenerateRepresentationLeafs(vtkPolyData *pd);
188 
190 
192  virtual int IntersectWithLine(
193  double p1[3], double p2[3], double tol, double& t, double x[3],
194  double pcoords[3], int &subId)
195  { return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId); }
197 
199 
201  virtual int IntersectWithLine(
202  double p1[3], double p2[3], double tol, double &t, double x[3],
203  double pcoords[3], int &subId, vtkIdType &cellId);
205 
207 
210  virtual int IntersectWithLine(
211  double p1[3], double p2[3], double tol, double &t, double x[3],
212  double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell);
214 
216 
225  virtual int IntersectWithLine(
226  const double p1[3], const double p2[3],
227  vtkPoints *points, vtkIdList *cellIds)
228  { return this->Superclass::IntersectWithLine(p1, p2, points, cellIds); }
230 
232 
238  virtual int IntersectWithLine(
239  const double p1[3], const double p2[3], const double tol,
240  vtkPoints *points, vtkIdList *cellIds);
242 
244 
246  virtual vtkIdType FindCell(double x[3])
247  { return this->Superclass::FindCell(x); }
249 
251 
253  virtual vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
254  double pcoords[3], double *weights);
256 
257  bool InsideCellBounds(double x[3], vtkIdType cell_ID);
258 
262  vtkIdListCollection *GetLeafNodeCellInformation();
263 
264 //ETX
265  protected:
268  //
269  BSPNode *mRoot; // bounding box root node
270  int npn;
271  int nln;
273 //BTX
274  //
275  // The main subdivision routine
276  void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet,
277  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth);
278 
279  // We provide a function which does the cell/ray test so that
280  // it can be overriden by subclasses to perform special treatment
281  // (Example : Particles stored in tree, have no dimension, so we must
282  // override the cell test to return a value based on some particle size
283  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
284  const double tol, double &t, double ipt[3], double pcoords[3], int &subId);
285 
286 //ETX
287  void BuildLocatorIfNeeded();
288  void ForceBuildLocator();
289  void BuildLocatorInternal();
290 private:
291  vtkModifiedBSPTree(const vtkModifiedBSPTree&); // Not implemented.
292  void operator=(const vtkModifiedBSPTree&); // Not implemented.
293 };
294 
295 //BTX
296 
298 // BSP Node
299 // A BSP Node is a BBox - axis aligned etc etc
301 #ifndef DOXYGEN_SHOULD_SKIP_THIS
302 
303 class BSPNode {
304  public:
305  // Constructor
306  BSPNode(void) {
307  mChild[0] = mChild[1] = mChild[2] = NULL;
308  for (int i=0; i<6; i++) sorted_cell_lists[i] = NULL;
309  for (int i=0; i<3; i++) { bounds[i*2] = VTK_LARGE_FLOAT; bounds[i*2+1] = -VTK_LARGE_FLOAT; }
310  }
311  // Destructor
312  ~BSPNode(void) {
313  for (int i=0; i<3; i++) if (mChild[i]) delete mChild[i];
314  for (int i=0; i<6; i++) if (sorted_cell_lists[i]) delete []sorted_cell_lists[i];
315  }
316  // Set min box limits
317  void setMin(double minx, double miny, double minz) {
318  bounds[0] = minx; bounds[2] = miny; bounds[4] = minz;
319  }
320  // Set max box limits
321  void setMax(double maxx, double maxy, double maxz) {
322  bounds[1] = maxx; bounds[3] = maxy; bounds[5] = maxz;
323  }
324  //
325  bool Inside(double point[3]) const;
326  // BBox
327  double bounds[6];
328  protected:
329  // The child nodes of this one (if present - NULL otherwise)
331  // The axis we subdivide this voxel along
332  int mAxis;
333  // Just for reference
334  int depth;
335  // the number of cells in this node
337  // 6 lists, sorted after the 6 dominant axes
339  // Order nodes as near/mid far relative to ray
340  void Classify(const double origin[3], const double dir[3],
341  double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
342  // Test ray against node BBox : clip t values to extremes
343  bool RayMinMaxT(const double origin[3], const double dir[3],
344  double &rTmin, double &rTmax) const;
345  //
346  friend class vtkModifiedBSPTree;
347  friend class vtkParticleBoxTree;
348  public:
349  static bool VTK_GRAPHICS_EXPORT RayMinMaxT(
350  const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
351  static int VTK_GRAPHICS_EXPORT getDominantAxis(const double dir[3]);
352 };
353 
354 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
355 
356 //ETX
357 
358 #endif
virtual void BuildLocator()=0
virtual vtkIdType FindClosestPointWithinRadius(double x[3], double radius, double closestPoint[3], vtkIdType &cellId, int &subId, double &dist2)
virtual void FindClosestPoint(double x[3], double closestPoint[3], vtkIdType &cellId, int &subId, double &dist2)
#define VTK_GRAPHICS_EXPORT
virtual int IntersectWithLine(const double p1[3], const double p2[3], vtkPoints *points, vtkIdList *cellIds)
bool Inside(double point[3]) const
virtual vtkIdType FindCell(double x[3])
virtual bool InsideCellBounds(double x[3], vtkIdType cell_ID)
abstract class to specify dataset behavior
Definition: vtkDataSet.h:58
BSPNode * mChild[3]
an abstract base class for locators which find cells
void Classify(const double origin[3], const double dir[3], double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const
int vtkIdType
Definition: vtkType.h:255
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:81
virtual void FreeSearchStructure()=0
provides thread-safe access to cells
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax) const
void PrintSelf(ostream &os, vtkIndent indent)
void setMax(double maxx, double maxy, double maxz)
a simple class to control print indentation
Definition: vtkIndent.h:37
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId)
virtual vtkIdType FindCell(double x[3])
list of point or cell ids
Definition: vtkIdList.h:34
friend class vtkParticleBoxTree
double bounds[6]
void setMin(double minx, double miny, double minz)
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId)
maintain an unordered list of dataarray objects
#define VTK_LARGE_FLOAT
Definition: vtkType.h:149
vtkIdType * sorted_cell_lists[6]
static int VTK_GRAPHICS_EXPORT getDominantAxis(const double dir[3])
static vtkObject * New()
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
represent and manipulate 3D points
Definition: vtkPoints.h:38
Generate axis aligned BBox tree for raycasting and other Locator based searches.