vtkCellTreeLocator.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkCellTreeLocator.h
 
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
 
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.
 
=========================================================================*/
#ifndef vtkCellTreeLocator_h
#define vtkCellTreeLocator_h
 
#include "vtkFiltersGeneralModule.h" // For export macro
#include "vtkAbstractCellLocator.h"
#include <vector> // Needed for internal class
 
class vtkCellPointTraversal;
class vtkIdTypeArray;
class vtkCellArray;
 
class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
{
  public:
    class vtkCellTree;
    class vtkCellTreeNode;
 
    vtkTypeMacro(vtkCellTreeLocator,vtkAbstractCellLocator);
    void PrintSelf(ostream& os, vtkIndent indent);
 
    static vtkCellTreeLocator *New();
 
 
    virtual vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell,  double pcoords[3],
                                       double* weights );
 
 
    virtual int IntersectWithLine(double a0[3], double a1[3], double tol,
                                      double& t, double x[3], double pcoords[3],
                                      int &subId, vtkIdType &cellId,
                                      vtkGenericCell *cell);
 
    virtual void FindCellsWithinBounds(double *bbox, vtkIdList *cells);
 
    //BTX
    /*
      if the borland compiler is ever removed, we can use these declarations
      instead of reimplementaing the calls in this subclass
      using vtkAbstractCellLocator::IntersectWithLine;
      using vtkAbstractCellLocator::FindClosestPoint;
      using vtkAbstractCellLocator::FindClosestPointWithinRadius;
    */
    //ETX
 
    virtual int IntersectWithLine(
      double p1[3], double p2[3], double tol, double& t, double x[3],
      double pcoords[3], int &subId)
    {
      return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
    }
 
 
    virtual int IntersectWithLine(
      double p1[3], double p2[3], double tol, double &t, double x[3],
      double pcoords[3], int &subId, vtkIdType &cellId);
 
 
    virtual int IntersectWithLine(
      const double p1[3], const double p2[3],
      vtkPoints *points, vtkIdList *cellIds)
    {
      return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
    }
 
 
    virtual vtkIdType FindCell(double x[3])
    { return this->Superclass::FindCell(x); }
 
 
    virtual void FreeSearchStructure();
    virtual void GenerateRepresentation(int level, vtkPolyData *pd);
    virtual void BuildLocatorInternal();
    virtual void BuildLocatorIfNeeded();
    virtual void ForceBuildLocator();
    virtual void BuildLocator();
 
 
//BTX
 
    class VTKFILTERSGENERAL_EXPORT vtkCellTree
    {
      public:
        std::vector<vtkCellTreeNode>  Nodes;
        std::vector<unsigned int> Leaves;
        friend class vtkCellPointTraversal;
        friend class vtkCellTreeNode;
        friend class vtkCellTreeBuilder;
 
      public:
        float DataBBox[6]; // This store the bounding values of the dataset
    };
 
 
    class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
    {
      public:
 
      protected:
        unsigned int Index;
        float LeftMax;  // left max value
        float RightMin;  // right min value
 
        unsigned int Sz; // size
        unsigned int St; // start
 
        friend class vtkCellTree;
        friend class vtkCellPointTraversal;
        friend class vtkCellTreeBuilder;
 
      public:
        void MakeNode( unsigned int left, unsigned int d, float b[2] );
        void SetChildren( unsigned int left );
        bool IsNode() const;
        unsigned int GetLeftChildIndex() const;
        unsigned int GetRightChildIndex() const;
        unsigned int GetDimension() const;
        const float& GetLeftMaxValue() const;
        const float& GetRightMinValue() const;
        void MakeLeaf( unsigned int start, unsigned int size );
        bool IsLeaf() const;
        unsigned int Start() const;
        unsigned int Size() const;
    };
//ETX
 
protected:
     vtkCellTreeLocator();
    ~vtkCellTreeLocator();
 
   // Test ray against node BBox : clip t values to extremes
  bool RayMinMaxT(const double origin[3],
    const double dir[3],
    double &rTmin,
    double &rTmax);
 
  bool RayMinMaxT(const double bounds[6],
    const double origin[3],
    const double dir[3],
    double &rTmin,
    double &rTmax);
 
  int getDominantAxis(const double dir[3]);
 
  // Order nodes as near/far relative to ray
  void Classify(const double origin[3],
    const double dir[3],
    double &rDist,
    vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
    vtkCellTreeNode *&far, int &mustCheck);
 
  // From vtkModifiedBSPTRee
  // We provide a function which does the cell/ray test so that
  // it can be overriden by subclasses to perform special treatment
  // (Example : Particles stored in tree, have no dimension, so we must
  // override the cell test to return a value based on some particle size
  virtual int IntersectCellInternal( vtkIdType cell_ID,  const double p1[3],
    const double p2[3],
    const double tol,
    double &t,
    double ipt[3],
    double pcoords[3],
    int &subId);
 
 
    int NumberOfBuckets;
 
    vtkCellTree* Tree;
 
    friend class vtkCellPointTraversal;
    friend class vtkCellTreeNode;
    friend class vtkCellTreeBuilder;
 
private:
  vtkCellTreeLocator(const vtkCellTreeLocator&);  // Not implemented.
  void operator=(const vtkCellTreeLocator&);      // Not implemented.
};
 
#endif