00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "common.h"
00013 #ifdef GRAPHVIZ_SUPPORT
00014 #include <boost/graph/graphviz.hpp>
00015 #endif
00016 #include "flexilog.h"
00017 #include "bvh.h"
00018 #include "kernel.h"
00019 #include "scenemanager.h"
00020 #include "scene.h"
00021 #include "camera.h"
00022 #include "geometrynode.h"
00023 #include "geometrytriangles.h"
00024 #include <stack>
00025
00026 using namespace VRUT;
00027
00028 BVH::BVH(Scene * _scene) : scene(_scene)
00029 {
00030 root = (BVHNode *)NULL;
00031 }
00032
00033
00034 BVH::~BVH()
00035 {
00036 }
00037
00038
00039 unsigned BVH::GetNumGeometryNodes(const BVHNode * startNode)
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 }
00061
00062
00063 void BVH::GetGeometryNodeIDs(std::deque<NODE_ID> * items, const BVHNode * startNode) const
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 }
00082
00083
00084 void BVH::getGeometryNodes(std::deque<const BVHNode *> * items, const BVHNode * startNode)
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 }
00103
00104
00105 void BVH::getGeometryNodes(std::deque<BVHNode *> * items, BVHNode * startNode)
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 }
00123
00124
00125 void BVH::Rebuild()
00126 {
00127 std::deque<NODE_ID> actList;
00128 GetGeometryNodeIDs(&actList, root);
00129 Destroy();
00130 Build(&actList);
00131 }
00132
00133
00134 BVHNode * BVH::Remove(BVHNode * node)
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 }
00167
00168
00169 void BVH::Insert(BVHNode * node)
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 }
00216
00217
00218 void BVH::UpdateBV(BVHNode * node)
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 }
00256
00257
00258
00259 void BVH::Build(std::deque<NODE_ID> * items)
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 }
00313
00314
00315 void BVH::splitGeometry(const std::deque<BVHNode *> * geometry,
00316 std::deque<BVHNode *> * geometryL,
00317 std::deque<BVHNode *> * geometryR) const
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 }
00367
00368
00369 bool BVH::BoundProbe(const Ray & ray, IntersectionInfo * info)
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
00394
00395
00396
00397
00398
00399 {
00400
00401
00402
00403 if (dist < bestFound.dist && dist > 0)
00404 {
00405 bestFound.nodeID = node->sceneNodeID;
00406 bestFound.dist = dist;
00407
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 }
00425
00426 bool
00427 BVH::CastRay(const Ray & ray, RayIntersectionInfo &bestFound)
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 }
00478
00479
00480 void BVH::queueUpForRender(BVHNode * node, const Camera * camera, ItemsList * itemsList, BlendedList * blendItemsList, bool inclChildren)
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 }
00504
00505
00506 void BVH::Cull(Camera * camera, ItemsList * itemsList, BlendedList * blendItemsList)
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 }
00566
00567
00568 void BVH::SetInvalid(BVHNode * node)
00569 {
00570 if (node)
00571 {
00572 if (node->parent)
00573 SetInvalid(node->parent);
00574 node->valid = false;
00575 }
00576 }
00577
00578 void
00579 BVH::AssignNodeIds()
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 }
00595
00596
00597 #ifdef GRAPHVIZ_SUPPORT
00598 void BVH::CreateGraphVizFile() const
00599 {
00600 if (!IsBuilt())
00601 {
00602 LOGWARNING(wxT("<BVH>Nothing to save to GraphViz definition file, BVH is empty"));
00603 return;
00604 }
00605
00606 typedef std::pair<int,int> Edge;
00607 std::vector<Edge> edges;
00608
00609 std::list<const BVHNode *> nodes;
00610 nodes.push_back(GetRoot());
00611 std::vector<wxString> titles;
00612 unsigned id = 0;
00613
00614 for (std::list<const BVHNode *>::const_iterator nodeIt = nodes.begin();
00615 nodeIt != nodes.end(); nodeIt++, id++)
00616 {
00617 if ((*nodeIt)->sceneNodeID != NODE_ID_NONE)
00618 titles.push_back(wxString::Format(wxT("%i_%s"), id, scene->GetNode((*nodeIt)->sceneNodeID)->GetName().c_str()));
00619 else
00620 titles.push_back(wxString::Format(wxT("%i"), id));
00621
00622 if ((*nodeIt)->lChild)
00623 {
00624 edges.push_back(Edge(id, int(nodes.size())));
00625 nodes.push_back((*nodeIt)->lChild);
00626 }
00627 if ((*nodeIt)->rChild)
00628 {
00629 edges.push_back(Edge(id, int(nodes.size())));
00630 nodes.push_back((*nodeIt)->rChild);
00631 }
00632 }
00633
00634 std::vector<int> weights(edges.size());
00635 std::fill(weights.begin(), weights.end(), 1);
00636
00637 typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
00638 boost::property< boost::vertex_color_t, boost::default_color_type >,
00639 boost::property< boost::edge_weight_t, int > > Graph;
00640 Graph g(&(edges[0]), &(edges[0]) + edges.size(), &(weights[0]), nodes.size());
00641
00642 unsigned ver = 0;
00643 wxString fname;
00644 do
00645 {
00646 fname = wxString::Format(wxT("%s.%i.bvh.dot"), scene->GetName().c_str(), ver++);
00647 }
00648 while (wxFileName(fname).FileExists());
00649
00650 std::ofstream fout(fname.ToAscii());
00651 if (fout.is_open())
00652 {
00653 write_graphviz(fout, g, wx_label_writer(&titles));
00654 LOG(wxT("<BVH>GraphViz definition file of BVH graph saved as '") + fname + wxT("'"));
00655 fout.close();
00656 }
00657 else
00658 LOGWARNING(wxT("<BVH>Could not save GraphViz definition file of BVH"));
00659 }
00660 #endif
00661
00662
00663 #ifdef __WXDEBUG__
00664 void BVH::Dump() const
00665 {
00666 unsigned ver = 0;
00667 wxString fname;
00668 do
00669 {
00670 fname = wxString::Format(wxT("%s.%i.txt"), scene->GetName().c_str(), ver++);
00671 }
00672 while (wxFileName(fname).FileExists());
00673
00674 wxFileOutputStream fout(fname);
00675 if (!fout.IsOk())
00676 {
00677 LOGERROR(wxT("<BVH>Could not save bvh dump file"));
00678 return;
00679 }
00680 wxTextOutputStream txtout(fout);
00681
00682 std::deque<const BVHNode *> nodes;
00683 nodes.push_back(GetRoot());
00684 while (!nodes.empty())
00685 {
00686 const BVHNode * node = nodes.front();
00687 nodes.pop_front();
00688 if (node)
00689 {
00690 txtout << node->ToString() << wxT("\n====================================================================================\n");
00691 nodes.push_back(node->lChild);
00692 nodes.push_back(node->rChild);
00693 }
00694 }
00695
00696 LOG(wxT("<BVH>BVH dump file saved as '") + fname + wxT("'"));
00697 }
00698 #endif
