00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00145 #ifndef _vtkModifiedBSPTree_h
00146 #define _vtkModifiedBSPTree_h
00147
00148 #include "vtkAbstractCellLocator.h"
00149 #include "vtkSmartPointer.h"
00150
00151
00152 class Sorted_cell_extents_Lists;
00153 class BSPNode;
00154 class vtkGenericCell;
00155 class vtkIdList;
00156 class vtkIdListCollection;
00157
00158
00159 class VTK_FILTERING_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator {
00160 public:
00162
00163 vtkTypeMacro(vtkModifiedBSPTree,vtkAbstractCellLocator);
00164 void PrintSelf(ostream& os, vtkIndent indent);
00166
00168 static vtkModifiedBSPTree *New();
00169
00170
00171 using vtkAbstractCellLocator::IntersectWithLine;
00172 using vtkAbstractCellLocator::FindClosestPoint;
00173 using vtkAbstractCellLocator::FindClosestPointWithinRadius;
00174
00175
00177 void FreeSearchStructure();
00178
00180 void BuildLocator();
00181
00182
00184 virtual void GenerateRepresentation(int level, vtkPolyData *pd);
00185
00187 virtual void GenerateRepresentationLeafs(vtkPolyData *pd);
00188
00190
00192 virtual int IntersectWithLine(
00193 double p1[3], double p2[3], double tol, double& t, double x[3],
00194 double pcoords[3], int &subId)
00195 { return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId); }
00197
00199
00201 virtual int IntersectWithLine(
00202 double p1[3], double p2[3], double tol, double &t, double x[3],
00203 double pcoords[3], int &subId, vtkIdType &cellId);
00205
00207
00210 virtual int IntersectWithLine(
00211 double p1[3], double p2[3], double tol, double &t, double x[3],
00212 double pcoords[3], int &subId, vtkIdType &cellId, vtkGenericCell *cell);
00214
00216
00225 virtual int IntersectWithLine(
00226 const double p1[3], const double p2[3],
00227 vtkPoints *points, vtkIdList *cellIds)
00228 { return this->Superclass::IntersectWithLine(p1, p2, points, cellIds); }
00230
00232
00238 virtual int IntersectWithLine(
00239 const double p1[3], const double p2[3], const double tol,
00240 vtkPoints *points, vtkIdList *cellIds);
00242
00244
00246 virtual vtkIdType FindCell(double x[3])
00247 { return this->Superclass::FindCell(x); }
00249
00251
00253 virtual vtkIdType FindCell(double x[3], double tol2, vtkGenericCell *GenCell,
00254 double pcoords[3], double *weights);
00256
00257 bool InsideCellBounds(double x[3], vtkIdType cell_ID);
00258
00262 vtkIdListCollection *GetLeafNodeCellInformation();
00263
00264
00265 protected:
00266 vtkModifiedBSPTree();
00267 ~vtkModifiedBSPTree();
00268
00269 BSPNode *mRoot;
00270 int npn;
00271 int nln;
00272 int tot_depth;
00273
00274
00275
00276 void Subdivide(BSPNode *node, Sorted_cell_extents_Lists *lists, vtkDataSet *dataSet,
00277 vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int &MaxDepth);
00278
00279
00280
00281
00282
00283 virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
00284 const double tol, double &t, double ipt[3], double pcoords[3], int &subId);
00285
00286
00287 void BuildLocatorIfNeeded();
00288 void ForceBuildLocator();
00289 void BuildLocatorInternal();
00290 private:
00291 vtkModifiedBSPTree(const vtkModifiedBSPTree&);
00292 void operator=(const vtkModifiedBSPTree&);
00293 };
00294
00295
00296
00298
00299
00301 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00302
00303 class BSPNode {
00304 public:
00305
00306 BSPNode(void) {
00307 mChild[0] = mChild[1] = mChild[2] = NULL;
00308 for (int i=0; i<6; i++) sorted_cell_lists[i] = NULL;
00309 for (int i=0; i<3; i++) { bounds[i*2] = VTK_LARGE_FLOAT; bounds[i*2+1] = -VTK_LARGE_FLOAT; }
00310 }
00311
00312 ~BSPNode(void) {
00313 for (int i=0; i<3; i++) if (mChild[i]) delete mChild[i];
00314 for (int i=0; i<6; i++) if (sorted_cell_lists[i]) delete []sorted_cell_lists[i];
00315 }
00316
00317 void setMin(double minx, double miny, double minz) {
00318 bounds[0] = minx; bounds[2] = miny; bounds[4] = minz;
00319 }
00320
00321 void setMax(double maxx, double maxy, double maxz) {
00322 bounds[1] = maxx; bounds[3] = maxy; bounds[5] = maxz;
00323 }
00324
00325 bool Inside(double point[3]) const;
00326
00327 double bounds[6];
00328 protected:
00329
00330 BSPNode *mChild[3];
00331
00332 int mAxis;
00333
00334 int depth;
00335
00336 int num_cells;
00337
00338 vtkIdType *sorted_cell_lists[6];
00339
00340 void Classify(const double origin[3], const double dir[3],
00341 double &rDist, BSPNode *&Near, BSPNode *&Mid, BSPNode *&Far) const;
00342
00343 bool RayMinMaxT(const double origin[3], const double dir[3],
00344 double &rTmin, double &rTmax) const;
00345
00346 friend class vtkModifiedBSPTree;
00347 friend class vtkParticleBoxTree;
00348 public:
00349 static bool VTK_FILTERING_EXPORT RayMinMaxT(
00350 const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax);
00351 static int VTK_FILTERING_EXPORT getDominantAxis(const double dir[3]);
00352 };
00353
00354 #endif
00355
00356
00357
00358 #endif
00359
00360