CollisionDetectionNamespace::CollisionDetection_BVH Class Reference

Bounding volumes hierarchy for collision detection module. More...

#include <CollisionDetection_BVH.h>

List of all members.

Public Member Functions

void UpdateBVH (CollisionDetection_BVHNode *node)
void SetCurrentMatrix (const MATRIX &matrix)
 CollisionDetection_BVH (NODE_ID _targetGeometryNode, const MATRIX &_transfMatrix=NULL)
 CollisionDetection_BVH ()
 Class constructor.
 ~CollisionDetection_BVH (void)
void Build (std::vector< Triangle > *items)
void Destroy ()
 Release BVH nodes.

Public Attributes

CollisionDetection_BVHNode * root
 Root node.
MATRIX CurrMatrix
 Current transformation matrix of target geometry.
MATRIX OldMatrix
 Last transformation matrix of target geometry.
NODE_ID TargetGeometryNode
 Target geometry node id.

Private Types

enum  AXIS { X_AXIS, Y_AXIS, Z_AXIS }
 Axis index. More...

Private Member Functions

void splitGeometry (CollisionDetection_BVHNode *pNode, const std::vector< Triangle > *geometry, std::vector< Triangle > *geometryL, std::vector< Triangle > *geometryR)
void calculateNode (CollisionDetection_BVHNode *node, Triangle triangle)

Detailed Description

Bounding volumes hierarchy for collision detection module.

Definition at line 43 of file CollisionDetection_BVH.h.

Member Enumeration Documentation

enum CollisionDetectionNamespace::CollisionDetection_BVH::AXIS [private]

Axis index.

Enumerator:
X_AXIS 
Y_AXIS 
Z_AXIS 

Definition at line 48 of file CollisionDetection_BVH.h.

00048 { X_AXIS, Y_AXIS, Z_AXIS };

Constructor & Destructor Documentation

CollisionDetectionNamespace::CollisionDetection_BVH::CollisionDetection_BVH ( NODE_ID  _targetGeometryNode,
const MATRIX &  _transfMatrix = NULL 
) [inline]

Class constructor

Parameters:
[in] id of target geometry
[in] current transformation matrix of target geometry

Definition at line 88 of file CollisionDetection_BVH.h.

00088 {TargetGeometryNode = _targetGeometryNode;root = NULL; CurrMatrix = OldMatrix = MATRIX(_transfMatrix);}

CollisionDetectionNamespace::CollisionDetection_BVH::CollisionDetection_BVH (  )  [inline]

Class constructor.

Definition at line 91 of file CollisionDetection_BVH.h.

00091 {TargetGeometryNode = NODE_ID_NONE;root = NULL; CurrMatrix = OldMatrix = MATRIX();}

CollisionDetection_BVH::~CollisionDetection_BVH ( void   ) 

Definition at line 7 of file CollisionDetection_BVH.cpp.

00008 {
00009        //SAFE_DELETE(root);
00010 }

Member Function Documentation

void CollisionDetection_BVH::splitGeometry ( CollisionDetection_BVHNode *  pNode,
const std::vector< Triangle > *  geometry,
std::vector< Triangle > *  geometryL,
std::vector< Triangle > *  geometryR 
) [private]

Split list of triangles into to lists

Parameters:
[in] BVH node that is to be split
[in] vector of triangles to split

Get AABB union

If still no split, divide in half

Definition at line 225 of file CollisionDetection_BVH.cpp.

00228 {
00229        //clock_t t,t1,t2,t3,t4;
00230        //double d1,d2,d3,d4;
00231 
00232        if (geometry->empty())
00233               return;
00234 
00235        //t=clock();
00236 
00237        double iMaxX, iMaxY, iMaxZ;
00238        iMaxX = iMaxY = iMaxZ = 0;
00240        pNode->aabb.MinBound = VECTOR3(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);
00241        pNode->aabb.MaxBound = VECTOR3(MIN_FLOAT,MIN_FLOAT,MIN_FLOAT);
00242 
00243        std::vector<Triangle>::const_iterator it = geometry->begin();
00244        for (++it; it != geometry->end(); it++)
00245        {
00246               calculateNode(pNode,(*it));
00247               iMaxX += (*it).v1.x;
00248               iMaxY += (*it).v1.y;
00249               iMaxZ += (*it).v1.z;
00250               
00251               iMaxX += (*it).v2.x;
00252               iMaxY += (*it).v2.y;
00253               iMaxZ += (*it).v2.z;
00254               
00255               iMaxX += (*it).v3.x;
00256               iMaxY += (*it).v3.y;
00257               iMaxZ += (*it).v3.z;
00258        }
00259 
00260        iMaxX = iMaxX / geometry->size();
00261        iMaxY = iMaxY / geometry->size();
00262        iMaxZ = iMaxZ / geometry->size();
00263 
00264        double dMax = __max(iMaxX,iMaxY);
00265        dMax = __max(dMax,iMaxZ);
00266 
00267 
00268        //t1=clock();
00269 
00270        //d1 = double(t1-t);
00271 
00272        VECTOR3 diag = pNode->aabb.MaxBound - pNode->aabb.MinBound;
00273        VECTOR3 center = pNode->aabb.MinBound + (diag * 0.5f);
00274 
00275        int axis;
00276        if (diag.x >= __max(diag.y, diag.z))
00277               axis = X_AXIS;
00278        else if (diag.y >= __max(diag.x, diag.z))
00279               axis = Y_AXIS;
00280        else
00281               axis = Z_AXIS;
00282 
00283        for (int a = 0;
00284               a < 3 && ( geometryL->empty() || geometryR->empty() );
00285               a++, axis = (axis + 1) % 3 )
00286        {
00287               geometryL->clear();
00288               geometryR->clear();
00289 
00290               float axisVal = iMaxX / 2;
00291 
00292               if (axis == 1)
00293                      axisVal = iMaxY / 2;  //center._v[axis];
00294               else if (axis == 2)
00295                      axisVal = iMaxZ / 2;
00296               //t2=clock();
00297 
00298               //d2 = double(t2-t);
00299 
00300               for (std::vector<Triangle>::const_iterator it = geometry->begin(); it != geometry->end(); it++)
00301               {
00302                      if ((*it).v1._v[axis] + (*it).v2._v[axis] + (*it).v2._v[axis] < center._v[axis]*3)
00303                             geometryL->push_back(*it);
00304                      else
00305                             geometryR->push_back(*it);
00306               }
00307 
00308               //t3=clock();
00309 
00310               //d3 = double(t3-t2);
00311        }
00312 
00313        //t4=clock();
00314 
00315        //d4 = double(t4-t);
00316 
00318        if (geometryL->empty() || geometryR->empty())
00319        {
00320               geometryL->clear();
00321               geometryR->clear();
00322               unsigned i;
00323               std::vector<Triangle>::const_iterator it = geometry->begin();
00324               for (i = 0; i < geometry->size()/2; i++, it++)
00325                      geometryL->push_back(*it);
00326               for (; i < geometry->size(); i++, it++)
00327                      geometryR->push_back(*it);
00328        }
00329 
00330 
00331 }

void CollisionDetection_BVH::calculateNode ( CollisionDetection_BVHNode *  node,
Triangle  triangle 
) [private]

Calculate BV for additional triangle

Parameters:
[in] BVH node to be calculated
[in] additional triangle

Definition at line 203 of file CollisionDetection_BVH.cpp.

00204 {
00205        node->GetAABB()->MaxBound.x = std::max(node->aabb.MaxBound.x, std::max(triangle.v1.x,triangle.v2.x));
00206        node->GetAABB()->MaxBound.x = std::max(node->aabb.MaxBound.x, std::max(triangle.v2.x,triangle.v3.x));
00207 
00208        node->GetAABB()->MaxBound.y = std::max(node->aabb.MaxBound.y, std::max(triangle.v1.y,triangle.v2.y));
00209        node->GetAABB()->MaxBound.y = std::max(node->aabb.MaxBound.y, std::max(triangle.v2.y,triangle.v3.y));
00210 
00211        node->GetAABB()->MaxBound.z = std::max(node->aabb.MaxBound.z, std::max(triangle.v1.z,triangle.v2.z));
00212        node->GetAABB()->MaxBound.z = std::max(node->aabb.MaxBound.z, std::max(triangle.v2.z,triangle.v3.z));
00213 
00214        node->GetAABB()->MinBound.x = std::min(node->aabb.MinBound.x, std::min(triangle.v1.x,triangle.v2.x));
00215        node->aabb.MinBound.x = std::min(node->aabb.MinBound.x, std::min(triangle.v2.x,triangle.v3.x));
00216 
00217        node->aabb.MinBound.y = std::min(node->aabb.MinBound.y, std::min(triangle.v1.y,triangle.v2.y));
00218        node->aabb.MinBound.y = std::min(node->aabb.MinBound.y, std::min(triangle.v2.y,triangle.v3.y));
00219 
00220        node->aabb.MinBound.z = std::min(node->aabb.MinBound.z, std::min(triangle.v1.z,triangle.v2.z));
00221        node->aabb.MinBound.z = std::min(node->aabb.MinBound.z, std::min(triangle.v2.z,triangle.v3.z));
00222 
00223 }

void CollisionDetection_BVH::UpdateBVH ( CollisionDetection_BVHNode *  node  ) 

Update BVH

Parameters:
[in] node from which BVH updating start

Inner BVH node

Definition at line 25 of file CollisionDetection_BVH.cpp.

00026 {
00027        if (!node)
00028               node = root;
00029 
00030 
00032        if (node->GetTargetOrigTriangles()->empty())
00033        {
00034               if (!node->GetLChild() && node->GetRChild())
00035               {
00036                      UpdateBVH(node->GetRChild());
00037                      node->aabb = node->GetRChild()->aabb;
00038               }
00039               else if (!node->GetRChild() && node->GetLChild())
00040               {
00041                      UpdateBVH(node->GetLChild());
00042                      node->aabb = node->GetLChild()->aabb;
00043               }
00044               else if (node->GetLChild() && node->GetRChild())
00045               {
00046                      UpdateBVH(node->GetLChild());
00047                      UpdateBVH(node->GetRChild());
00048                      node->aabb = node->GetLChild()->aabb + node->GetRChild()->aabb;
00049               }
00050        }
00051        else
00052        {
00053 
00054               node->aabb.MinBound = VECTOR3(MAX_FLOAT,MAX_FLOAT,MAX_FLOAT);
00055               node->aabb.MaxBound = VECTOR3(MIN_FLOAT,MIN_FLOAT,MIN_FLOAT);
00056 
00057               node->targetTriangles.clear();
00058               for (int i = 0; i < (int)node->targetTrianglesOrig.size(); i++)
00059               {
00060                      node->targetTriangles.push_back(Triangle());
00061                      node->targetTriangles[i].v1 = CurrMatrix.TransformCoord(node->targetTrianglesOrig[i].v1);
00062                      node->targetTriangles[i].v2 = CurrMatrix.TransformCoord(node->targetTrianglesOrig[i].v2);
00063                      node->targetTriangles[i].v3 = CurrMatrix.TransformCoord(node->targetTrianglesOrig[i].v3);
00064                      calculateNode(node,node->targetTriangles[i]);
00065               }
00066        }
00067 
00068        node->bSphere.Center = (node->aabb.MinBound + node->aabb.MaxBound) * 0.5f;
00069        node->bSphere.Radius = (node->aabb.MaxBound - node->aabb.MinBound).Length() * 0.5f;
00070        node->valid = true;
00071 }

void CollisionDetectionNamespace::CollisionDetection_BVH::SetCurrentMatrix ( const MATRIX &  matrix  )  [inline]

Set current transformation matrix of target geometry

Parameters:
[in] current transformation matrix of target geometry

Definition at line 74 of file CollisionDetection_BVH.h.

00075               {
00076                      OldMatrix = MATRIX(CurrMatrix);
00077                      CurrMatrix = MATRIX(matrix);
00078               }

void CollisionDetection_BVH::Build ( std::vector< Triangle > *  items  ) 

Build BVH from vector of triangles

Parameters:
[in] vector of triangles to build BVH for

Build BVH

Definition at line 83 of file CollisionDetection_BVH.cpp.

00084 {
00085 
00086        //clock_t t,t1,t2,t3;
00087 
00088        std::vector<Triangle> * itemsPending = new std::vector<Triangle>();
00089        for (int i = 0; i < (int)items->size();i++)
00090        {
00091               itemsPending->push_back((*items)[i]);
00092        }
00093 
00094 
00096        std::deque<MyQNode> queue;
00097        root = new CollisionDetection_BVHNode();
00098 
00099        MyQNode node(root, itemsPending);
00100        queue.push_back(node);
00101 
00102        int index = 0;
00103        while (!queue.empty())
00104        {
00105               //t=clock();
00106 
00107               MyQNode qnode = queue.front();
00108               queue.pop_front();
00109 
00110               //if (qnode.itemsPending->empty())
00111               //{
00112               //     delete qnode.itemsPending;
00113               //     continue;
00114               //}
00115 
00116               if (qnode.itemsPending->size() <= TRIANGLES_IN_LEAF)
00117               {
00118                      
00119                      qnode.currentNode->aabb.MinBound = VECTOR3(MAX_FLOAT,MAX_FLOAT,MAX_FLOAT);
00120                      qnode.currentNode->aabb.MaxBound = VECTOR3(MIN_FLOAT,MIN_FLOAT,MIN_FLOAT);
00121 
00122 
00123                      int i = 0;
00124                      std::vector<Triangle>::iterator it = qnode.itemsPending->begin();
00125                      while (i < TRIANGLES_IN_LEAF && it != qnode.itemsPending->end())
00126                      {
00127 
00128                             Triangle triangle1 = (*it++);
00129                             //triangle1.v1 = transfMatrix->TransformCoord(triangle1.v1);
00130                             //triangle1.v2 = transfMatrix->TransformCoord(triangle1.v2);
00131                             //triangle1.v3 = transfMatrix->TransformCoord(triangle1.v3);
00132 
00133                             calculateNode(qnode.currentNode,triangle1);
00134                             
00135                             qnode.currentNode->GetTargetOrigTriangles()->push_back(triangle1);
00136 
00137                             i++;
00138                      }
00139 
00140                      //*(qnode.currentNode) = qnode.itemsPending->front();
00141                      //(*(qnode.currentNode))->parent = qnode.parent;
00142                      if (qnode.itemsPending)
00143                      {
00144                             qnode.itemsPending->clear();
00145                             delete qnode.itemsPending;
00146                      }
00147 
00148                      continue;
00149               }
00150 
00151                      
00152 
00153               std::vector<Triangle > * geometryL = new std::vector<Triangle>;
00154               std::vector<Triangle > * geometryR = new std::vector<Triangle>;
00155               
00156 
00157               //t1=clock();
00158 
00159               //double d1 = double(t1-t);
00160 
00161 
00162 
00163               splitGeometry(qnode.currentNode, qnode.itemsPending, geometryL, geometryR);
00164               
00165               //t2=clock();
00166 
00167               //double d2 = double(t2-t1);
00168               
00169               //This should be there!!!!!!
00170               if (qnode.itemsPending)
00171               {
00172                      qnode.itemsPending->clear();
00173                      delete qnode.itemsPending;
00174 
00175               }
00176 
00177               if (!geometryL->empty())
00178               {
00179                      qnode.currentNode->CreateLChild();
00180                      queue.push_back(MyQNode(qnode.currentNode->GetLChild(), geometryL));
00181               }
00182 
00183               if (!geometryR->empty())
00184               {
00185                      qnode.currentNode->CreateRChild();
00186                      queue.push_back(MyQNode(qnode.currentNode->GetRChild(), geometryR));
00187               }
00188 
00189               //t3=clock();
00190 
00191               //double d3 = double(t3-t1);
00192 
00193               //index ++;
00194               //int kk = 7;
00195        }
00196 
00197        //int ahhh = 9;
00198 
00199 
00200 }

void CollisionDetectionNamespace::CollisionDetection_BVH::Destroy (  )  [inline]

Release BVH nodes.

Definition at line 100 of file CollisionDetection_BVH.h.

00100 { SAFE_DELETE(root); }

Member Data Documentation

CollisionDetection_BVHNode* CollisionDetectionNamespace::CollisionDetection_BVH::root

Root node.

Definition at line 70 of file CollisionDetection_BVH.h.

MATRIX CollisionDetectionNamespace::CollisionDetection_BVH::CurrMatrix

Current transformation matrix of target geometry.

Definition at line 81 of file CollisionDetection_BVH.h.

MATRIX CollisionDetectionNamespace::CollisionDetection_BVH::OldMatrix

Last transformation matrix of target geometry.

Definition at line 83 of file CollisionDetection_BVH.h.

NODE_ID CollisionDetectionNamespace::CollisionDetection_BVH::TargetGeometryNode

Target geometry node id.

Definition at line 103 of file CollisionDetection_BVH.h.

The documentation for this class was generated from the following files:
Generated on Tue Mar 10 14:41:39 2009 for VRUT by  doxygen 1.5.5