Documentation

animal::octree::FastOctree< T, S, U > Class Template Reference

#include <fastoctreedeformableconstrained.h>

Inheritance diagram for animal::octree::FastOctree< T, S, U >:

animal::octree::Octree animal::octree::OctreeEngine animal::octree::OctreeParticleSystemEngine< t_Vector, t_Real, t_Masses > animal::octree::OctreeODEEngine animal::octree::OctreeSpringEngine List of all members.

Detailed Description

template<class T, class S, class U>
class animal::octree::FastOctree< T, S, U >

Fast is here related to the fact that we use lookup tables to retrieve the different indices needed when working with the octree.

This octree perform vertex sharing, that is, cells of the octree store pointer to points instead of point. Thus, points that belong to several cell are only "created" once and referred by all concerned viewcells. This is useful, along with the fact that the point type is a template parameter of the class to store per-vertex information in the octree.

The octree cells also store a pointer to arbitrary data, whose type is the second template parameter of the FastOctree class.

The FastOctree class is just a wrapper that is needed to access the root cell of an octree. The important class is FastOctree::Cell.

Code Snippets

Here is how to draw an octree using openGL: 

 template<class T,class S,class U>
 void drawCell(FastOctree<T,S,U>::Cell* cell)
 {
   if (!cell->isLeaf())
   {
     for(short i=0;i<8;++i)
     {
       drawCell(cell->child(i));
     }
   }
   else
   {
     glBegin(GL_QUADS);
     for (unsigned short i=0;i<6;++i)
     {
       Octree::Face face = cell->face(i);
       glNormal3fv(face.normal());
       glVertex3fv(*(face.vertex(0)));
       glVertex3fv(*(face.vertex(1)));
       glVertex3fv(*(face.vertex(2)));
       glVertex3fv(*(face.vertex(3)));
     }
     glEnd();
   }
 }
 template<class T,class S,class U>
 void drawOctree(FastOctree<T,S,U>* o)
 {
   if (o->root()) drawCell(o->root());
 }
Here is a code snippet to locate the leaf cell in which a given point P is located. The example also shows how the data type can be used to store in each cell the list of point 
 typedef FastOctreeCell<Vec3,list<Vec3> > Octree;
 Octree octree(Vec3(-1.0f,-1.0f,-1.0f),2.0f);
 
 // ......
 // Here octree is subdivided
 // .......
 
  
P[3] = { 0.5f,0.3f,0.4f };  // The point to localize
  
 Octree::Cell* root = octree->root();
 Octree::Cell* child = root->locate(P);
 while (child && child != root)
 {
   child = (root=child)->locate(P);
 }
 if (child != NULL)
 {
   cout<<" point P is in cell whose diagonale is "
       <<child->vertex(0)<<"-"<<child->vertex(7)<<endl;       
   (*child)->data->push_back(P);
 }
Note that the template parameter allows to search for point of type different than the point type of the octree. The only requirement is that type U defines operator: 
 const FloatingPointType& U::operator[](const int i) const

Here is a more sophisticated version where a set of points is localized in an octree, each cell of the octree remembering which points are in. The points are localized in the tightest octree's cell containing them. Tightness is indicated by a maximum subdivision depth. This time, the octree therefore needs to be subdivided along with the subdivision process. 

 typedef FastOctreeCell<Vec3,list<Vec3> > Octree;
 const int max_depth = 10;
  
 vector<Vec3> points;
 Octree* octree;
  
 // ......
 // Here the points vector is filled and the octree is created
 // with correct size to contain all the points.
 // .......
  
 for(int i=0;i<points.size();++i)
 {
   const Vec3& P = points[i];
   int depth = 0;
   Octree::Cell* cell = octree->root();
   while (depth < depth_max && cell != NULL)
   {
     ++depth;
     cell->subdivide();
     cell = cell->locate(P);
   }
   if (cell != NULL)
   {
     (*cell)->push_back(P);
   }
   else
   {
     // This case should not occur if the octree's root cell has been 
     // created with a sufficient size.
     cout<<"WARNING: I can't locate point (seems to be outside)"<<endl;
   }
 }

Definition at line 152 of file fastoctreedeformableconstrained.h.

Public Types

typedef T Vertex
typedef Vertex * VertexPtr
typedef S Data

Public Member Functions

 FastOctree (Cell *root)
 FastOctree (const U &min, const FloatingPointType &size, const S &defaultData=S())
 FastOctree (const U &min, const FloatingPointType &,const FloatingPointType &,const FloatingPointType &, const S &defaultData=S())
virtual ~FastOctree ()
Cell * root () const

Static Public Member Functions

unsigned short vertexIndex (unsigned short i, unsigned short j, unsigned short k)
unsigned short childIndex (unsigned short i, unsigned short j, unsigned short k)

Public Attributes

Cell * root_

Static Public Attributes

const bool hasBrotherAlongFace [8][6]
const bool hasBrotherAlongEdge [8][12]
const unsigned short alongFace [8][6]
const unsigned short alongEdge [8][12]
const unsigned short supportingFace [8][12]
const bool hasOnFatherEdge [8][12]
const unsigned short childrenSharingFace [6][4]
const unsigned short alterEgoFace [6]
const unsigned short faceVertices [6][4]
const unsigned short verticesConnectedFaces [8][3]
const unsigned short directionForVertexOnEdge [8][8]
const unsigned short directionForVertexOnFace [8][8]

Member Typedef Documentation

template<class T, class S, class U>
typedef S animal::octree::FastOctree< T, S, U >::Data
 

The type of the data that one can associate with each cell of an octree.

Definition at line 191 of file fastoctreedeformableconstrained.h.

Referenced by animal::octree::FastOctree< T, S, U >::Cell::getData(), animal::octree::FastOctree< T, S, U >::Cell::operator *(), animal::octree::FastOctree< T, S, U >::Cell::operator->(), and animal::octree::FastOctree< T, S, U >::Cell::setData().

template<class T, class S, class U>
typedef T animal::octree::FastOctree< T, S, U >::Vertex
 

the 3D point type used in the octree. Its requirements is to have: 

  Point::Point(const FloatingPointType,const FloatingPointType,const FloatingPointType) constructor,
  FloatingPointType& Point::operator[](const int i)
  Point operator+(const Point& a, const Point& b) // vector addition
  FloatingPointType operator*(const Point& a, const Point& b) // scalar product

Definition at line 167 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
typedef Vertex* animal::octree::FastOctree< T, S, U >::VertexPtr
 

Definition at line 168 of file fastoctreedeformableconstrained.h.

Constructor & Destructor Documentation

template<class T, class S, class U>
animal::octree::FastOctree< T, S, U >::FastOctree (  Cell *  root  ) 
 

template<class T, class S, class U>
animal::octree::FastOctree< T, S, U >::FastOctree (  const U &  min,
const FloatingPointType &  size,
const S &  defaultData = S()
) 
 

template<class T, class S, class U>
animal::octree::FastOctree< T, S, U >::FastOctree (  const U &  min,
const FloatingPointType &  ,
const FloatingPointType &  ,
const FloatingPointType &  ,
const S &  defaultData = S()
) 
 

template<class T, class S, class U>
virtual animal::octree::FastOctree< T, S, U >::~FastOctree (   )  [virtual]
 

Member Function Documentation

template<class T, class S, class U>
unsigned short animal::octree::FastOctree< T, S, U >::childIndex (  unsigned short  i,
unsigned short  j,
unsigned short  k
)  [inline, static]
 

template<class T, class S, class U>
Cell* animal::octree::FastOctree< T, S, U >::root (   )  const [inline]
 

Referenced by animal::octree::CGRenderingMachine::computeCGData(), X3DTK::X3D::DeformableOctreeNode::createOctree(), animal::octree::Octree::directManipulation(), X3DTK::X3D::DeformableOctreeNode::draw(), X3DTK::X3D::DeformableOctreeNode::drawOctreeVertices(), X3DTK::X3D::DeformableOctreeNode::getBoundingBox(), animal::octree::Octree::getMeshVertices(), animal::octree::Octree::getNormals(), animal::octree::ManipulatedMeshVertex::ManipulatedMeshVertex(), animal::octree::OctreeParticleSystemEngine< t_Vector, t_Real, t_Masses >::move(), animal::octree::ManipulatedMeshVertexAnimated< t_Vector, t_Real, t_VecReal >::moveTo(), animal::octree::ManipulatedMeshVertex::moveTo(), animal::octree::Octree::Octree(), animal::octree::Octree::setNMaxPointsPerCell(), animal::octree::Octree::setPositionMethod(), animal::octree::Octree::simplify(), X3DTK::X3D::DeformableOctreeNode::slotButtonDirectManipulation(), X3DTK::X3D::DeformableOctreeNode::slotMoveXMinus(), X3DTK::X3D::DeformableOctreeNode::slotMoveXPlus(), X3DTK::X3D::DeformableOctreeNode::slotMoveYMinus(), X3DTK::X3D::DeformableOctreeNode::slotMoveYPlus(), X3DTK::X3D::DeformableOctreeNode::slotMoveZMinus(), X3DTK::X3D::DeformableOctreeNode::slotMoveZPlus(), X3DTK::X3D::DeformableOctreeNode::slotSetInterpolationMethod(), and animal::octree::Octree::subdivideRecDeformed().

template<class T, class S, class U>
unsigned short animal::octree::FastOctree< T, S, U >::vertexIndex (  unsigned short  i,
unsigned short  j,
unsigned short  k
)  [inline, static]
 

Member Data Documentation

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::alongEdge[8][12] [static]
 

Definition at line 215 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::alongFace[8][6] [static]
 

Definition at line 214 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::alterEgoFace[6] [static]
 

Definition at line 219 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::childrenSharingFace[6][4] [static]
 

Definition at line 218 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::directionForVertexOnEdge[8][8] [static]
 

Definition at line 222 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::directionForVertexOnFace[8][8] [static]
 

Definition at line 223 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::faceVertices[6][4] [static]
 

Definition at line 220 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const bool animal::octree::FastOctree< T, S, U >::hasBrotherAlongEdge[8][12] [static]
 

Definition at line 213 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const bool animal::octree::FastOctree< T, S, U >::hasBrotherAlongFace[8][6] [static]
 

Definition at line 212 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const bool animal::octree::FastOctree< T, S, U >::hasOnFatherEdge[8][12] [static]
 

Definition at line 217 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
Cell* animal::octree::FastOctree< T, S, U >::root_
 

Definition at line 228 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::supportingFace[8][12] [static]
 

Definition at line 216 of file fastoctreedeformableconstrained.h.

template<class T, class S, class U>
const unsigned short animal::octree::FastOctree< T, S, U >::verticesConnectedFaces[8][3] [static]
 

Definition at line 221 of file fastoctreedeformableconstrained.h.

The documentation for this class was generated from the following file:
Generated on Thu Dec 23 13:52:32 2004 by doxygen 1.3.6