VRUT::BVH Class Reference

Bounding volume hierarchy. More...

#include <bvh.h>

List of all members.

Public Types

typedef std::vector< NODE_ID > ItemsList

typedef std::multimap< float,
NODE_ID > BlendedList

Public Member Functions

BVH (Scene *_scene)

Class constructor.

~BVH ()

Class destructor.

BVHNode * GetRoot () const

Get BVH root.

BVHNode * GetBVHNodeAssignedTo (NODE_ID sceneNodeID) const

Get BVH node assigned to given scene node.

void AssignNodeIds ()

bool IsBuilt () const

Is BVH built or not (empty).

void GetGeometryNodeIDs (std::deque< NODE_ID > *items, const BVHNode *startNode) const

void Destroy ()

Release BVH nodes.

void Rebuild ()

Completely rebuild BVH.

BVHNode * Remove (BVHNode *node)

void Insert (BVHNode *node)

Insert given node or BVH (dirty insert).

void Build (std::deque< NODE_ID > *items)

Build BVH from given geometry list.

void Cull (Camera *camera, ItemsList *itemsList, BlendedList *blendItemsList)

bool BoundProbe (const Ray &ray, IntersectionInfo *info)

bool CastRay (const Ray &ray, RayIntersectionInfo &info)

void UpdateBV (BVHNode *node=(BVHNode *) NULL)

Static Public Member Functions

static unsigned GetNumGeometryNodes (const BVHNode *startNode)

static void SetInvalid (BVHNode *node)

Set node and its supernodes invalid.

Public Attributes

int numberOfNodes

Number of nodes in the bvh.

Private Types

enum AXIS { X_AXIS, Y_AXIS, Z_AXIS }

Axis index. More...

Private Member Functions

WX_DECLARE_HASH_MAP (NODE_ID, BVHNode *, wxIntegerHash, wxIntegerEqual, SceneToBVHMap)

void splitGeometry (const std::deque< BVHNode * > *geometry, std::deque< BVHNode * > *geometryL, std::deque< BVHNode * > *geometryR) const

void queueUpForRender (BVHNode *node, const Camera *camera, ItemsList *itemsList, BlendedList *blendItemsList, bool inclChildren=false)

Static Private Member Functions

static void getGeometryNodes (std::deque< const BVHNode * > *items, const BVHNode *startNode)

static void getGeometryNodes (std::deque< BVHNode * > *items, BVHNode *startNode)

Private Attributes

BVHNode * root

Root node.

Scene * scene

Associated scene.

SceneToBVHMap bvhNodes

Hash map from scene node IDs to BVH nodes.

Friends

class Scene

Classes

struct IntersectionInfo

Structure with pick data. More...

struct QNode

Queue node structure for BVH creation purpose - enables iterative instead of recursive creation of BVH. More...

Detailed Description

Bounding volume hierarchy.

Definition at line 29 of file bvh.h.

Member Typedef Documentation

typedef std::vector<NODE_ID> VRUT::BVH::ItemsList

Definition at line 43 of file bvh.h.

typedef std::multimap<float, NODE_ID> VRUT::BVH::BlendedList

Definition at line 44 of file bvh.h.

Member Enumeration Documentation

enum VRUT::BVH::AXIS [private]

Axis index.

Enumerator:

X_AXIS
Y_AXIS
Z_AXIS

Definition at line 60 of file bvh.h.

00060 { X_AXIS, Y_AXIS, Z_AXIS };

Constructor & Destructor Documentation

BVH::BVH ( Scene * _scene )

Class constructor.

Definition at line 28 of file bvh.cpp.

00028                        : scene(_scene)
00029 {
00030        root = (BVHNode *)NULL;
00031 }

BVH::~BVH ( )

Class destructor.

Definition at line 34 of file bvh.cpp.

00035 {
00036 }

Member Function Documentation

VRUT::BVH::WX_DECLARE_HASH_MAP	(	NODE_ID	,
		BVHNode *	,
		wxIntegerHash	,
		wxIntegerEqual	,
		SceneToBVHMap
	)			`[private]`

void BVH::splitGeometry	(	const std::deque< BVHNode * > *	geometry,
		std::deque< BVHNode * > *	geometryL,
		std::deque< BVHNode * > *	geometryR
	)			const `[private]`

Split geometry into 2 groups according to their relative position, left or right from splitting plane defined by longest dimension of all geometry BV

Parameters:

`[in]`	geometry	List of geometry to split
`[out]`	geometryL	Will be filled with geometry on left
`[out]`	geometryR	Will be filled with geometry on right

Get AABB union

If still no split, divide in half

Definition at line 315 of file bvh.cpp.

00318 {
00319        if (geometry->empty())
00320               return;
00321 
00323        std::deque<BVHNode *>::const_iterator it = geometry->begin();
00324        AABB aabb = (*it)->aabb;
00325        for (++it; it != geometry->end(); it++)
00326               aabb.Merge((*it)->aabb);
00327 
00328        VECTOR3 diag = aabb.MaxBound - aabb.MinBound;
00329        VECTOR3 center = aabb.MinBound + (diag * 0.5f);
00330        int axis;
00331        if (diag.x >= __max(diag.y, diag.z))
00332               axis = X_AXIS;
00333        else if (diag.y >= __max(diag.x, diag.z))
00334               axis = Y_AXIS;
00335        else
00336               axis = Z_AXIS;
00337 
00338        for (int a = 0;
00339               a < 3 && ( geometryL->empty() || geometryR->empty() );
00340               a++, axis = (axis + 1) % 3 )
00341        {
00342               geometryL->clear();
00343               geometryR->clear();
00344               float axisVal = center._v[axis];
00345               for (std::deque<BVHNode *>::const_iterator it = geometry->begin(); it != geometry->end(); it++)
00346               {
00347                      if ((*it)->bSphere.Center._v[axis] < axisVal)
00348                             geometryL->push_back(*it);
00349                      else
00350                             geometryR->push_back(*it);
00351               }
00352        }
00353 
00355        if (geometryL->empty() || geometryR->empty())
00356        {
00357               geometryL->clear();
00358               geometryR->clear();
00359               unsigned i;
00360               std::deque<BVHNode *>::const_iterator it = geometry->begin();
00361               for (i = 0; i < geometry->size()/2; i++, it++)
00362                      geometryL->push_back(*it);
00363               for (; i < geometry->size(); i++, it++)
00364                      geometryR->push_back(*it);
00365        }
00366 }

void BVH::queueUpForRender	(	BVHNode *	node,
		const Camera *	camera,
		ItemsList *	itemsList,
		BlendedList *	blendItemsList,
		bool	inclChildren = `false`
	)			`[private]`

Insert node and its BVH children (optional) to one of render lists

Parameters:

`[in]`	node	Node to be inserted (optionally its BVH children if any)
`[in]`	camera	Use viewing frustum of given camera, camera should be updated
`[out]`	itemsList	One or more matching geometry nodes will be added
`[out]`	blendItemsList	One or more matching geometry nodes with transparency will be added
`[in]`	inclChildren	Tells if all leaves in `node's` subtree are to be inserted

Definition at line 480 of file bvh.cpp.

00481 {
00482        std::deque<BVHNode *> items;
00483        if (inclChildren)
00484               getGeometryNodes(&items, node);
00485        else
00486               items.push_back(node);
00487 
00488        for (std::deque<BVHNode *>::const_iterator it = items.begin();
00489               it != items.end(); it++)
00490        {
00491               const GeometryNode * sceneNode = (const GeometryNode *)scene->GetNode((*it)->sceneNodeID);
00492               const Material * material = scene->GetMaterial(sceneNode->GetMaterialID());
00493               if (material && material->flags & Material::BLENDED)
00494               {
00495                      float zdepth = (camera->GetWorldTransMatrix()->ExtractTranslation()
00496                             - (*it)->GetBSphere()->Center).LengthSq();
00497                      std::pair<float, NODE_ID> blendItem(zdepth, (*it)->sceneNodeID);
00498                      blendItemsList->insert(blendItem);
00499               }
00500               else
00501                      itemsList->push_back((*it)->sceneNodeID);
00502        }
00503 }

void BVH::getGeometryNodes	(	std::deque< const BVHNode * > *	items,
		const BVHNode *	startNode
	)			`[static, private]`

Fill given list with all geometry nodes in BVH - BVHNode version

Parameters:

`[out]`	items	List to be filled
`[in]`	startNode	Root node for subtree

Definition at line 84 of file bvh.cpp.

00085 {
00086        std::deque<const BVHNode *> queue;
00087        queue.push_back(startNode);
00088 
00089        while (queue.size())
00090        {
00091               const BVHNode * node = queue.front();
00092               queue.pop_front();
00093 
00094               if (node)
00095               {
00096                      if (node->sceneNodeID != NODE_ID_NONE)
00097                             items->push_back(node);
00098                      queue.push_back(node->lChild);
00099                      queue.push_back(node->rChild);
00100               }
00101        }
00102 }

void BVH::getGeometryNodes	(	std::deque< BVHNode * > *	items,
		BVHNode *	startNode
	)			`[static, private]`

Fill given list with all geometry nodes in BVH - BVHNode version

Parameters:

`[out]`	items	List to be filled
`[in]`	startNode	Root node for subtree

Definition at line 105 of file bvh.cpp.

00106 {
00107        std::deque<BVHNode *> queue;
00108        queue.push_back(startNode);
00109 
00110        while (queue.size())
00111        {
00112               BVHNode * node = queue.front();
00113               queue.pop_front();
00114 
00115               if (node->sceneNodeID != NODE_ID_NONE)
00116                      items->push_back(node);
00117               if (node->lChild)
00118                      queue.push_back(node->lChild);
00119               if (node->rChild)
00120                      queue.push_back(node->rChild);
00121        }
00122 }

BVHNode* VRUT::BVH::GetRoot ( ) const [inline]

Get BVH root.

Definition at line 107 of file bvh.h.

00108               {
00109                      return root;
00110               }

BVHNode* VRUT::BVH::GetBVHNodeAssignedTo ( NODE_ID sceneNodeID ) const [inline]

Get BVH node assigned to given scene node.

Definition at line 113 of file bvh.h.

00114               {
00115                      SceneToBVHMap::const_iterator mapIt = bvhNodes.find(sceneNodeID);
00116                      return ( mapIt == bvhNodes.end() ? (BVHNode *)NULL : mapIt->second );
00117               }

void BVH::AssignNodeIds ( )

Definition at line 579 of file bvh.cpp.

00580 {
00581   std::stack<BVHNode *> nodeStack;
00582   nodeStack.push(root);
00583   int id = 0;
00584   while(!nodeStack.empty()) {
00585        BVHNode *n = nodeStack.top();
00586        nodeStack.pop();
00587        n->id = id++;
00588        if (!n->IsLeaf()) {
00589          nodeStack.push(n->lChild);
00590          nodeStack.push(n->rChild);
00591        }
00592   }
00593   numberOfNodes = id;
00594 }

bool VRUT::BVH::IsBuilt ( ) const [inline]

Is BVH built or not (empty).

Definition at line 122 of file bvh.h.

00122 { return root != (BVHNode *)NULL; }

unsigned BVH::GetNumGeometryNodes ( const BVHNode * startNode ) [static]

Get number of nodes with geometry of a subtree

Parameters:

[in] startNode Root node for subtree

Definition at line 39 of file bvh.cpp.

00040 {
00041        unsigned num = 0;
00042        std::deque<const BVHNode *> queue;
00043        queue.push_back(startNode);
00044 
00045        while (queue.size())
00046        {
00047               const BVHNode * node = queue.front();
00048               queue.pop_front();
00049 
00050               if (node)
00051               {
00052                      if (node->sceneNodeID != NODE_ID_NONE)
00053                             num++;
00054                      queue.push_back(node->lChild);
00055                      queue.push_back(node->rChild);
00056               }
00057        }
00058 
00059        return num;
00060 }

void BVH::GetGeometryNodeIDs	(	std::deque< NODE_ID > *	items,
		const BVHNode *	startNode
	)			const

Fill given list with IDs of all geometry nodes in BVH

Parameters:

`[out]`	items	List to be filled
`[in]`	startNode	Root node for subtree

Definition at line 63 of file bvh.cpp.

00064 {
00065        std::deque<const BVHNode *> queue;
00066        queue.push_back(startNode);
00067 
00068        while (queue.size())
00069        {
00070               const BVHNode * node = queue.front();
00071               queue.pop_front();
00072 
00073               if (node)
00074               {
00075                      if (node->sceneNodeID != NODE_ID_NONE)
00076                             items->push_back(node->sceneNodeID);
00077                      queue.push_back(node->lChild);
00078                      queue.push_back(node->rChild);
00079               }
00080        }
00081 }

void VRUT::BVH::Destroy ( ) [inline]

Release BVH nodes.

Definition at line 134 of file bvh.h.

00134 { SAFE_DELETE(root); }

void BVH::Rebuild ( )

Completely rebuild BVH.

Definition at line 125 of file bvh.cpp.

00126 {
00127        std::deque<NODE_ID> actList;
00128        GetGeometryNodeIDs(&actList, root);
00129        Destroy();
00130        Build(&actList);
00131 }

BVHNode * BVH::Remove ( BVHNode * node )

Remove given node from BVH

Returns:: Node detached from scene graph

This has to be root

Definition at line 134 of file bvh.cpp.

00135 {
00136        if (node)
00137        {
00138               wxASSERT_MSG((node->lChild == (BVHNode *)NULL) && (node->rChild == (BVHNode *)NULL),
00139                      wxT("<BVH>Cannot remove inner BVH node (node has children)"));
00140               SetInvalid(node);
00141               BVHNode * nparent = node->parent;
00142               if (nparent)
00143               {
00144                      if (nparent->lChild == node)
00145                             nparent->lChild = (BVHNode *)NULL;
00146                      else if (nparent->rChild == node)
00147                             nparent->rChild = (BVHNode *)NULL;
00148                      if ( (nparent->lChild == (BVHNode *)NULL)
00149                             && (nparent->rChild == (BVHNode *)NULL) )
00150                      {
00151                             Remove(nparent);
00152                             SAFE_DELETE(nparent);
00153                      }
00154                      node->parent = (BVHNode *)NULL;
00155                      bvhNodes.erase(node->sceneNodeID);
00156                      node->sceneNodeID = NODE_ID_NONE;
00157               }
00158               else
00159               {
00161                      wxASSERT_MSG(node == root, wxT("<BVH>Invalid BVH hierarchy or trying to remove node from another BVH"));
00162                      root = (BVHNode *)NULL;
00163               }
00164        }
00165        return node;
00166 }

void BVH::Insert ( BVHNode * node )

Insert given node or BVH (dirty insert).

Set parents

Definition at line 169 of file bvh.cpp.

00170 {
00171        if (!IsBuilt())
00172        {
00173               root = node;
00174               return;
00175        }
00176 
00177        bool found = false;
00178        BVHNode ** target = &root;
00179        while (!found)
00180        {
00181               UpdateBV(*target);
00182               if ((*target)->sceneNodeID != NODE_ID_NONE || !(*target)->aabb.PointIsIn(node->bSphere.Center))
00183               {
00184                      BVHNode * newRoot = new BVHNode;
00185                      BVHNode * par = (*target)->parent;
00186                      newRoot->lChild = *target;
00187                      newRoot->rChild = node;
00188                      *target = newRoot;
00190                      newRoot->parent = par;
00191                      newRoot->lChild->parent = newRoot;
00192                      node->parent = newRoot;
00193                      found = true;
00194               }
00195               else
00196               {
00197                      if (!(*target)->lChild)
00198                             target = &((*target)->rChild);
00199                      else if (!(*target)->rChild)
00200                             target = &((*target)->lChild);
00201                      else
00202                      {
00203                             UpdateBV((*target)->lChild);
00204                             UpdateBV((*target)->rChild);
00205                             AABB left = (*target)->lChild->aabb + node->aabb;
00206                             AABB right = (*target)->rChild->aabb + node->aabb;
00207                             if ((left.MaxBound - left.MinBound).LengthSq()
00208                                    < (right.MaxBound - right.MinBound).LengthSq())
00209                                    target = &((*target)->lChild);
00210                             else
00211                                    target = &((*target)->rChild);
00212                      }
00213               }
00214        }
00215 }

void BVH::Build ( std::deque< NODE_ID > * items )

Build BVH from given geometry list.

Create BVH leaves

Build BVH

Definition at line 259 of file bvh.cpp.

00260 {
00262        std::deque<BVHNode *> * bvhItemsPending = new std::deque<BVHNode *>;
00263        for (std::deque<NODE_ID>::const_iterator it = items->begin();
00264               it != items->end(); it++)
00265        {
00266               GeometryNode * geomNode = (GeometryNode *)scene->GetNode(*it);
00267               if (geomNode && scene->GetGeometry(geomNode->GetGeometryID()))
00268               {
00269                      BVHNode * node = new BVHNode;
00270                      node->sceneNodeID = *it;
00271                      bvhNodes.insert(SceneToBVHMap::value_type(*it, node));
00272                      UpdateBV(node);
00273                      bvhItemsPending->push_back(node);
00274               }
00275        }
00276 
00278        std::deque<QNode> queue;
00279        queue.push_back(QNode(&root, bvhItemsPending, (BVHNode *)NULL));
00280 
00281        while (!queue.empty())
00282        {
00283               QNode qnode = queue.front();
00284               queue.pop_front();
00285 
00286               if (qnode.itemsPending->empty())
00287               {
00288                      delete qnode.itemsPending;
00289                      continue;
00290               }
00291 
00292               if (qnode.itemsPending->size() == 1)
00293               {
00294                      *(qnode.currentNode) = qnode.itemsPending->front();
00295                      (*(qnode.currentNode))->parent = qnode.parent;
00296                      delete qnode.itemsPending;
00297                      continue;
00298               }
00299 
00300               BVHNode * node = *(qnode.currentNode) = new BVHNode;
00301               node->parent = qnode.parent;
00302               std::deque<BVHNode *> * geometryL = new std::deque<BVHNode *>;
00303               std::deque<BVHNode *> * geometryR = new std::deque<BVHNode *>;
00304               splitGeometry(qnode.itemsPending, geometryL, geometryR);
00305               delete qnode.itemsPending;
00306 
00307               queue.push_back(QNode(&node->lChild, geometryL, node));
00308               queue.push_back(QNode(&node->rChild, geometryR, node));
00309        }
00310 
00311        AssignNodeIds();
00312 }

void BVH::Cull	(	Camera *	camera,
		ItemsList *	itemsList,
		BlendedList *	blendItemsList
	)

Traverse BVH and update geometry in viewing frustum

Parameters:

`[in]`	camera	Use viewing frustum of given camera, camera should be updated
`[out]`	itemsList	List of geometry nodes inside/intersecting VF will be added
`[out]`	blendItemsList	List of geometry nodes inside/intersecting VF with transparency will be added

Camera not in node

bSphere - bSphere

AABB - frustum

Definition at line 506 of file bvh.cpp.

00507 {
00508        if (!root || !camera)
00509               return;
00510 
00511        std::deque< std::pair<unsigned, BVHNode *> > queue;
00512        std::pair<unsigned, BVHNode *> qnode(0, root);
00513        queue.push_back(qnode);
00514        while (!queue.empty())
00515        {
00516               BVHNode * node = queue.front().second;
00517               unsigned planeMask = queue.front().first;
00518               queue.pop_front();
00519 
00520               UpdateBV(node);
00521               Camera::VFC_RESULT result = Camera::INTERSECT;
00523               if (!node->aabb.PointIsIn(camera->GetWorldTransMatrix()->ExtractTranslation()))
00524               {
00526                      if (!node->bSphere.Intersects(camera->GetBSphere()))
00527                             result = Camera::OUTSIDE;
00528                      else
00530                             result = camera->InFrustum(node->aabb, &node->lastOut, &planeMask);
00531               }
00532 
00533               switch (result)
00534               {
00535               case Camera::OUTSIDE:
00536                      break;
00537 
00538               case Camera::INSIDE:
00539                      queueUpForRender(node, camera, itemsList, blendItemsList, true);
00540                      break;
00541 
00542               case Camera::INTERSECT:
00543                      if (node->sceneNodeID != NODE_ID_NONE)
00544                             queueUpForRender(node, camera, itemsList, blendItemsList);
00545                      else
00546                      {
00547                             if (node->lChild)
00548                                    queue.push_back(std::pair<unsigned, BVHNode *>(planeMask, node->lChild));
00549                             if (node->rChild)
00550                                    queue.push_back(std::pair<unsigned, BVHNode *>(planeMask, node->rChild));
00551                      }
00552                      break;
00553               }
00554        }
00555 
00556 #ifdef __WXDEBUG__
00557        static int nCount = 0;
00558        int newCount = int(itemsList->size() + blendItemsList->size());
00559        if (nCount != newCount)
00560        {
00561               nCount = newCount;
00562               LOGDEBUG(wxString::Format(wxT("<BVH>Nodes to draw after cull: %i"), nCount));
00563        }
00564 #endif
00565 }

bool BVH::BoundProbe	(	const Ray &	ray,
		IntersectionInfo *	info
	)

Test BVH for ray intersection and return true if intersected object found

Parameters:

`[in]`	ray	Ray (world space)
`[out]`	info	Structure will be filled with intersection data if intersection found

Returns:: true if intersection found

Node with geometry

Definition at line 369 of file bvh.cpp.

00370 {
00371        if (!root)
00372               return false;
00373 
00374        IntersectionInfo bestFound;
00375        bestFound.dist = 1e9f;
00376        bestFound.nodeID = NODE_ID_NONE;
00377 
00378        std::deque<BVHNode *> queue;
00379        queue.push_back(root);
00380        while (!queue.empty())
00381        {
00382               BVHNode * node = queue.front();
00383               queue.pop_front();
00384 
00385               float dist = 1e9f;
00386               VECTOR3 intersection;
00387               UpdateBV(node);
00388               if (node->GetAABB()->Intersects(ray, 0, bestFound.dist, &dist))
00389               {
00391                      if (node->sceneNodeID != NODE_ID_NONE)
00392                      {
00393 //                          const MATRIX * worldMat = sNode->GetWorldTransMatrix();
00394 //                          MATRIX invWorldMat = worldMat->Inverse();
00395 //                          VECTOR3 modelOrigin = invWorldMat.TransformCoord(ray.origin);
00396 //                          VECTOR3 modelDir = invWorldMat.TransformNormal(ray.direction).Normalize();
00397 //                          const Ray modelRay(modelOrigin, modelDir);
00398 //                          if (sNode->GetGeometry()->Intersects(modelRay, &dist))
00399                             {
00400 //                                 VECTOR3 intersection = modelRay.origin + modelRay.direction * dist;
00401 //                                 intersection = worldMat->TransformCoord(intersection);
00402 //                                 dist = (ray.origin - intersection).Length();
00403                                    if (dist < bestFound.dist && dist > 0)
00404                                    {
00405                                           bestFound.nodeID = node->sceneNodeID;
00406                                           bestFound.dist = dist;
00407 //                                        bestFound.intersection = intersection;
00408                                    }
00409                             }
00410                      }
00411                      else
00412                      {
00413                             if (node->lChild)
00414                                    queue.push_back(node->lChild);
00415                             if (node->rChild)
00416                                    queue.push_back(node->rChild);
00417                      }
00418               }
00419        }
00420        if (info)
00421               *info = bestFound;
00422 
00423        return bestFound.nodeID != NODE_ID_NONE;
00424 }

bool BVH::CastRay	(	const Ray &	ray,
		RayIntersectionInfo &	info
	)

Test the scene geometry for ray intersection and return true if intersected object found

Parameters:

`[in]`	ray	Ray (world space)
`[out]`	info	Structure will be filled with intersection data if intersection found

Returns:: true if intersection found

Node with geometry

Definition at line 427 of file bvh.cpp.

00428 {
00429        if (!root)
00430               return false;
00431 
00432        bestFound.dist = 1e9f;
00433        bestFound.nodeID = NODE_ID_NONE;
00434        
00435        std::stack<BVHNode *> stack;
00436        stack.push(root);
00437        while (!stack.empty()) {
00438          BVHNode * node = stack.top();
00439          stack.pop();
00440          
00441          float dist = 1e9f;
00442          VECTOR3 intersection;
00443          UpdateBV(node);
00444          if (node->GetAABB()->Intersects(ray, 0, bestFound.dist, &dist)) {
00446               if (node->sceneNodeID != NODE_ID_NONE) {
00447                 const GeometryNode * sNode = (const GeometryNode *)scene->GetNode(node->sceneNodeID);
00448                 const MATRIX * worldMat = sNode->GetWorldTransMatrix();
00449                 MATRIX invWorldMat = worldMat->Inverse();
00450                 VECTOR3 modelOrigin = invWorldMat.TransformCoord(ray.origin);
00451                 VECTOR3 modelDir = invWorldMat.TransformNormal(ray.direction).Normalize();
00452                 const Ray modelRay(modelOrigin, modelDir);
00453                 RayIntersectionInfo gInfo;
00454                 if (scene->GetGeometry(sNode->GetGeometryID())->CastRay(modelRay, gInfo)) {
00455                      VECTOR3 intersection = modelRay.origin + modelRay.direction * gInfo.dist;
00456                      intersection = worldMat->TransformCoord(intersection);
00457                      dist = (ray.origin - intersection).Length();
00458                      if (dist < bestFound.dist && dist > 0) {
00459                        bestFound.nodeID = node->sceneNodeID;
00460                        bestFound.dist = dist;
00461                        bestFound.intersection = intersection;
00462                        bestFound.normal = worldMat->TransformNormal(gInfo.normal);
00463                      }
00464                 }
00465               }
00466               else
00467                 {
00468                      if (node->lChild)
00469                        stack.push(node->lChild);
00470                      if (node->rChild)
00471                        stack.push(node->rChild);
00472                 }
00473          }
00474        }
00475 
00476        return bestFound.nodeID != NODE_ID_NONE;
00477 }

void BVH::UpdateBV ( BVHNode * node = (BVHNode *)NULL )

Update given BVHNode and connected SceneNode if not valid

Parameters:

[in] node BVH node to be updated, if NULL whole BVH is updated

Inner BVH node

Node with geometry

Definition at line 218 of file bvh.cpp.

00219 {
00220        if (!node)
00221               node = root;
00222        if (!node || node->IsValid())
00223               return;
00224 
00226        if (node->sceneNodeID == NODE_ID_NONE)
00227        {
00228               if (!node->lChild)
00229               {
00230                      UpdateBV(node->rChild);
00231                      node->aabb = node->rChild->aabb;
00232               }
00233               else if (!node->rChild)
00234               {
00235                      UpdateBV(node->lChild);
00236                      node->aabb = node->lChild->aabb;
00237               }
00238               else
00239               {
00240                      UpdateBV(node->lChild);
00241                      UpdateBV(node->rChild);
00242                      node->aabb = node->lChild->aabb + node->rChild->aabb;
00243               }
00244        }
00246        else
00247        {
00248               scene->UpdateTransformation(node->sceneNodeID);
00249               const GeometryNode * sceneNode = (const GeometryNode *)scene->GetNode(node->sceneNodeID);
00250               node->aabb = scene->GetGeometry(sceneNode->GetGeometryID())->GetAABB().Transform(sceneNode->GetWorldTransMatrix());
00251        }
00252        node->bSphere.Center = (node->aabb.MinBound + node->aabb.MaxBound) * 0.5f;
00253        node->bSphere.Radius = (node->aabb.MaxBound - node->aabb.MinBound).Length() * 0.5f;
00254        node->valid = true;
00255 }

void BVH::SetInvalid ( BVHNode * node ) [static]

Set node and its supernodes invalid.

Definition at line 568 of file bvh.cpp.

00569 {
00570        if (node)
00571        {
00572               if (node->parent)
00573                      SetInvalid(node->parent);
00574               node->valid = false;
00575        }
00576 }

Friends And Related Function Documentation

friend class Scene [friend]

Definition at line 184 of file bvh.h.

Member Data Documentation

BVHNode* VRUT::BVH::root [private]

Root node.

Definition at line 63 of file bvh.h.

Scene* VRUT::BVH::scene [private]

Associated scene.

Definition at line 65 of file bvh.h.

SceneToBVHMap VRUT::BVH::bvhNodes [private]

Hash map from scene node IDs to BVH nodes.

Definition at line 67 of file bvh.h.

int VRUT::BVH::numberOfNodes

Number of nodes in the bvh.

Definition at line 98 of file bvh.h.

The documentation for this class was generated from the following files:

/cygdrive/d/src/svn/vrut/trunk/core/src/bvh.h
/cygdrive/d/src/svn/vrut/trunk/core/src/bvh.cpp


Public Types
typedef std::vector< NODE_ID >	ItemsList
typedef std::multimap< float, NODE_ID >	BlendedList
Public Member Functions
	BVH (Scene *_scene)
	Class constructor.
	~BVH ()
	Class destructor.
BVHNode *	GetRoot () const
	Get `BVH` root.
BVHNode *	GetBVHNodeAssignedTo (NODE_ID sceneNodeID) const
	Get BVH node assigned to given scene node.
void	AssignNodeIds ()
bool	IsBuilt () const
	Is BVH built or not (empty).
void	GetGeometryNodeIDs (std::deque< NODE_ID > items, const BVHNode startNode) const
void	Destroy ()
	Release BVH nodes.
void	Rebuild ()
	Completely rebuild BVH.
BVHNode *	Remove (BVHNode *node)
void	Insert (BVHNode *node)
	Insert given node or BVH (dirty insert).
void	Build (std::deque< NODE_ID > *items)
	Build BVH from given geometry list.
void	Cull (Camera camera, ItemsList itemsList, BlendedList *blendItemsList)
bool	BoundProbe (const Ray &ray, IntersectionInfo *info)
bool	CastRay (const Ray &ray, RayIntersectionInfo &info)
void	UpdateBV (BVHNode node=(BVHNode ) NULL)
Static Public Member Functions
static unsigned	GetNumGeometryNodes (const BVHNode *startNode)
static void	SetInvalid (BVHNode *node)
	Set node and its supernodes invalid.
Public Attributes
int	numberOfNodes
	Number of nodes in the bvh.
Private Types
enum	AXIS { X_AXIS, Y_AXIS, Z_AXIS }
	Axis index. More...
Private Member Functions
	WX_DECLARE_HASH_MAP (NODE_ID, BVHNode *, wxIntegerHash, wxIntegerEqual, SceneToBVHMap)
void	splitGeometry (const std::deque< BVHNode * > geometry, std::deque< BVHNode > geometryL, std::deque< BVHNode > *geometryR) const
void	queueUpForRender (BVHNode node, const Camera camera, ItemsList itemsList, BlendedList blendItemsList, bool inclChildren=false)
Static Private Member Functions
static void	getGeometryNodes (std::deque< const BVHNode * > items, const BVHNode startNode)
static void	getGeometryNodes (std::deque< BVHNode * > items, BVHNode startNode)
Private Attributes
BVHNode *	root
	Root node.
Scene *	scene
	Associated scene.
SceneToBVHMap	bvhNodes
	Hash map from scene node IDs to BVH nodes.
Friends
class	Scene
Classes
struct	IntersectionInfo
	Structure with pick data. More...
struct	QNode
	Queue node structure for BVH creation purpose - enables iterative instead of recursive creation of BVH. More...