SGI/util/SGI/include/graphics/vtkCellLocator.h

   1 /*=========================================================================
   2
   3   Program:   Visualization Toolkit
   4   Module:    $RCSfile: vtkCellLocator.h,v $
   5   Language:  C++
   6   Date:      $Date: 2002/02/01 06:30:44 $
   7   Version:   $Revision: 1.1.1.1 $
   8
   9
  10 Copyright (c) 1993-1998 Ken Martin, Will Schroeder, Bill Lorensen.
  11
  12 This software is copyrighted by Ken Martin, Will Schroeder and Bill Lorensen.
  13 The following terms apply to all files associated with the software unless
  14 explicitly disclaimed in individual files. This copyright specifically does
  15 not apply to the related textbook "The Visualization Toolkit" ISBN
  16 013199837-4 published by Prentice Hall which is covered by its own copyright.
  17
  18 The authors hereby grant permission to use, copy, and distribute this
  19 software and its documentation for any purpose, provided that existing
  20 copyright notices are retained in all copies and that this notice is included
  21 verbatim in any distributions. Additionally, the authors grant permission to
  22 modify this software and its documentation for any purpose, provided that
  23 such modifications are not distributed without the explicit consent of the
  24 authors and that existing copyright notices are retained in all copies. Some
  25 of the algorithms implemented by this software are patented, observe all
  26 applicable patent law.
  27
  28 IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
  29 DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  30 OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF,
  31 EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32
  33 THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
  34 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  35 PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN
  36 "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
  37 MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  38
  39
  40 =========================================================================*/
  41 // .NAME vtkCellLocator - octree-based spatial search object to quickly locate cells
  42 // .SECTION Description
  43 // vtkCellLocator is a spatial search object to quickly locate cells in 3D.
  44 // vtkCellLocator uses a uniform-level octree subdivision, where each octant
  45 // (an octant is also referred to as a bucket) carries an indication of whether
  46 // it is empty or not, and each leaf octant carries a list of the cells inside
  47 // of it. (An octant is not empty if it has one or more cells inside of it.)
  48 // Typical operations are intersection with a line to return candidate cells,
  49 // or intersection with another vtkCellLocator to return candidate cells.
  50
  51 // .SECTION Caveats
  52 // Many other types of spatial locators have been developed, such as
  53 // variable depth octrees and kd-trees. These are often more efficient
  54 // for the operations described here. vtkCellLocator has been designed
  55 // for subclassing; so these locators can be derived if necessary.
  56
  57 // .SECTION See Also
  58 // vtkLocator vtkPointLocator vtkOBBTree
  59
  60 #ifndef __vtkCellLocator_h
  61 #define __vtkCellLocator_h
  62
  63 #include "vtkLocator.h"
  64
  65 class VTK_EXPORT vtkCellLocator : public vtkLocator
  66 {
  67 public:
  68   vtkCellLocator();
  69   ~vtkCellLocator();
  70   static vtkCellLocator *New() {return new vtkCellLocator;};
  71   const char *GetClassName() {return "vtkCellLocator";};
  72   void PrintSelf(ostream& os, vtkIndent indent);
  73
  74   // Description:
  75   // Specify the average number of cells in each octant.
  76   vtkSetClampMacro(NumberOfCellsPerBucket,int,1,VTK_LARGE_INTEGER);
  77   vtkGetMacro(NumberOfCellsPerBucket,int);
  78
  79   // methods that all cell locators must provide
  80   virtual int IntersectWithLine(float a0[3], float a1[3], float tol,
  81                                 float& t, float x[3], float pcoords[3],
  82                                 int &subId);
  83   virtual vtkIdList *GetCells(int bucket);
  84   virtual void InitializeIntersection(vtkCellLocator& locator);
  85   virtual int GetNextIntersection(int& bucket1, int& bucket2);
  86
  87   // satisfy vtkLocator abstract interface
  88   void FreeSearchStructure();
  89   void BuildLocator();
  90   void GenerateRepresentation(int level, vtkPolyData *pd);
  91
  92 protected:
  93   int NumberOfCellsPerBucket; // cells per octant
  94   int NumberOfOctants; // number of octants in tree
  95   float Bounds[6]; // bounding box root octant
  96   int NumberOfParents; // number of parent octants
  97   float H[3]; // width of root octant in x-y-z directions
  98   int NumberOfDivisions; // number of "leaf" octant sub-divisions
  99   vtkIdList **Tree; // octree
 100
 101   void MarkParents(void*, int, int, int, int, int);
 102   void GetChildren(int idx, int level, int children[8]);
 103   int GenerateIndex(int offset, int numDivs, int i, int j, int k, int &idx);
 104   void GenerateFace(int face, int numDivs, int i, int j, int k,
 105                     vtkPoints *pts, vtkCellArray *polys);
 106 };
 107
 108 #endif
 109
 110