VTK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 "vtkFiltersFlowPathsModule.h" // For export macro
149 #include "vtkAbstractCellLocator.h"
150 #include "vtkSmartPointer.h" // required because it is nice
151 
152 //BTX
153 class Sorted_cell_extents_Lists;
154 class BSPNode;
155 class vtkGenericCell;
156 class vtkIdList;
157 class vtkIdListCollection;
158 //ETX
159 
160 class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator {
161  public:
163 
164  vtkTypeMacro(vtkModifiedBSPTree,vtkAbstractCellLocator);
165  void PrintSelf(ostream& os, vtkIndent indent);
167 
169  static vtkModifiedBSPTree *New();
170 
171 //BTX
172  using vtkAbstractCellLocator::IntersectWithLine;
173  using vtkAbstractCellLocator::FindClosestPoint;
174  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
175 //ETX
176 
178  void FreeSearchStructure();
179 
181  void BuildLocator();
182 
183 //BTX
185  virtual void GenerateRepresentation(int level, vtkPolyData *pd);
186 
188  virtual void GenerateRepresentationLeafs(vtkPolyData *pd);
189 
191 
193  virtual int IntersectWithLine(
194  double p1[3], double p2[3], double tol, double& t, double x[3],
195  double pcoords[3], int &subId)
196  { return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId); }
198 
200 
202  virtual int IntersectWithLine(
203  double p1[3], double p2[3], double tol, double &t, double x[3],
204  double pcoords[3], int &subId, vtkIdType &cellId);
206 
208 
211  virtual int IntersectWithLine(
212  double p1[3], double p2[3], double tol, double &t, double x[3],
213  double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell);
215 
217 
226  virtual int IntersectWithLine(
227  const double p1[3], const double p2[3],
228  vtkPoints *points, vtkIdList *cellIds)
229  { return this->Superclass::IntersectWithLine(p1, p2, points, cellIds); }
231 
233 
239  virtual int IntersectWithLine(
240  const double p1[3], const double p2[3], const double tol,
241  vtkPoints *points, vtkIdList *cellIds);
243 
245 
247  virtual vtkIdType FindCell(double x[3])
248  { return this->Superclass::FindCell(x); }
250 
252 
254  virtual vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
255  double pcoords[3], double *weights);
257 
258  bool InsideCellBounds(double x[3], vtkIdType cell_ID);
259 
263  vtkIdListCollection *GetLeafNodeCellInformation();
264 
265 //ETX
266  protected:
269  //
270  BSPNode *mRoot; // bounding box root node
271  int npn;
272  int nln;
274 //BTX
275  //
276  // The main subdivision routine
277  void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet,
278  vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth);
279 
280  // We provide a function which does the cell/ray test so that
281  // it can be overriden by subclasses to perform special treatment
282  // (Example : Particles stored in tree, have no dimension, so we must
283  // override the cell test to return a value based on some particle size
284  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
285  const double tol, double &t, double ipt[3], double pcoords[3], int &subId);
286 
287 //ETX
288  void BuildLocatorIfNeeded();
289  void ForceBuildLocator();
290  void BuildLocatorInternal();
291 private:
292  vtkModifiedBSPTree(const vtkModifiedBSPTree&); // Not implemented.
293  void operator=(const vtkModifiedBSPTree&); // Not implemented.
294 };
295 
296 //BTX
297 
299 // BSP Node
300 // A BSP Node is a BBox - axis aligned etc etc
302 #ifndef DOXYGEN_SHOULD_SKIP_THIS
303 
304 class BSPNode {
305  public:
306  // Constructor
307  BSPNode(void) {
308  mChild[0] = mChild[1] = mChild[2] = NULL;
309  for (int i=0; i<6; i++) sorted_cell_lists[i] = NULL;
310  for (int i=0; i<3; i++) { bounds[i*2] = VTK_FLOAT_MAX; bounds[i*2+1] = -VTK_FLOAT_MAX; }
311  }
312  // Destructor
313  ~BSPNode(void) {
314  for (int i=0; i<3; i++) if (mChild[i]) delete mChild[i];
315  for (int i=0; i<6; i++) if (sorted_cell_lists[i]) delete []sorted_cell_lists[i];
316  }
317  // Set min box limits
318  void setMin(double minx, double miny, double minz) {
319  bounds[0] = minx; bounds[2] = miny; bounds[4] = minz;
320  }
321  // Set max box limits
322  void setMax(double maxx, double maxy, double maxz) {
323  bounds[1] = maxx; bounds[3] = maxy; bounds[5] = maxz;
324  }
325  //
326  bool Inside(double point[3]) const;
327  // BBox
328  double bounds[6];
329  protected:
330  // The child nodes of this one (if present - NULL otherwise)
332  // The axis we subdivide this voxel along
333  int mAxis;
334  // Just for reference
335  int depth;
336  // the number of cells in this node
338  // 6 lists, sorted after the 6 dominant axes
339  vtkIdType *sorted_cell_lists[6];
340  // Order nodes as near/mid far relative to ray
341  void Classify(const double origin[3], const double dir[3],
342  double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
343  // Test ray against node BBox : clip t values to extremes
344  bool RayMinMaxT(const double origin[3], const double dir[3],
345  double &rTmin, double &rTmax) const;
346  //
347  friend class vtkModifiedBSPTree;
348  friend class vtkParticleBoxTree;
349  public:
350  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(
351  const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
352  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
353 };
354 
355 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
356 
357 //ETX
358 
359 #endif
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])
BSPNode * mChild[3]
static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3])
void Classify(const double origin[3], const double dir[3], double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax) const
void setMax(double maxx, double maxy, double maxz)
virtual int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId)
friend class vtkParticleBoxTree
double bounds[6]
void setMin(double minx, double miny, double minz)
vtkIdType * sorted_cell_lists[6]
Generate axis aligned BBox tree for raycasting and other Locator based searches.