Changeset 3064 for GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp

Timestamp:

10/23/08 23:10:16 (16 years ago)

Author:

mattausch

Message:

working on dynamic bvh hierarchy: denug version

File:

• GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp (modified) (33 diffs)

GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp

@@ -191 +191 @@
 void Bvh::Init()
 {
+        mStaticRoot = NULL;
+        mDynamicRoot = NULL;
         mRoot = NULL;
+
         mVertices = NULL;
         mIndices = NULL;
@@ -198 +201 @@
         mNumNodes = 0;
         
+        // nodes are tested using the subnodes from 3 levels below
         mMaxDepthForTestingChildren = 3;
         //mMaxDepthForTestingChildren = 4;
+
+        // the ratio of area between node and subnodes where 
+        // testing the subnodes as proxy is still considered feasable
         mAreaRatioThreshold = 2.0f;
         //mAreaRatioThreshold = 1.4f;
@@ -209 +216 @@
 
 
-void Bvh::PullUpLastVisited(BvhNode *node, const int frameId) const
+
+
+//////////////////////
+//-- functions that are used during the main traversal
+
+void Bvh::PullUpLastVisited(BvhNode *node, int frameId) const
 {               
         BvhNode *parent = node->GetParent();
@@ -232 +244 @@
 }
 
+
+////////////////////////////////
 
 void Bvh::CollectLeaves(BvhNode *node, BvhLeafContainer &leaves)
@@ -403 +417 @@
         if (!mDynamicEntities.empty())
         {
-                UpdateDynamicBranch();
+                //UpdateDynamicBranch();
         }
 }
@@ -464 +478 @@
                                           bool useTightBounds)
 {
-        // if not using tight bounds, rendering boxes in immediate mode
-        // is preferable to vertex arrays (less setup time)
-
         int renderedBoxes;
 
         if (!useTightBounds)
         {
+                // if not using tight bounds, rendering boxes in immediate mode
+                // is preferable to vertex arrays (less setup time)
                 BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
                         
@@ -477 +490 @@
                         RenderBoundingBoxImmediate((*nit)->GetBox());
                 }
-
+cout<<"y";
                 renderedBoxes = (int)nodes.size();
         }
         else
-        {
+        {cout<<"x";
                 renderedBoxes = PrepareBoundsWithDrawArrays(nodes);
                 RenderBoundsWithDrawArrays(renderedBoxes, state);
@@ -492 +505 @@
 int Bvh::PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes)
 {
-        //////
-        //-- for the first time we come here ...
+        ///////////////////
+        //-- for the first time we come here => create vbo and indices
 
         if (!mIndices)
-        {       // create list of indices
+        {       
+                // create list of indices
                 CreateIndices();
         }
@@ -532 +546 @@
 void Bvh::RenderBoundsWithDrawArrays(int numNodes, RenderState *state)
 {
-        //////
-        //-- Rendering the vbo
+        /////////
+        //-- Render the vbo
 
         if (state->GetCurrentVboId() != mVboId)
@@ -555 +569 @@
         // collect bvh nodes
         BvhNodeContainer nodes;
-        CollectNodes(mRoot, nodes);
+        CollectNodes(mStaticRoot, nodes);
 
         cout << "creating new indices" << endl;
@@ -567 +581 @@
                 int offset = (*lit)->mNumTestNodes * sNumIndicesPerBox;
 #ifdef ALIGN_INDICES
-                // align with 32
+                // align with 32 in order to speed up memcopy
                 offset = (offset / 32) * 32 + 32; 
 #endif
@@ -582 +596 @@
         // to allocate memory from the chunks of the node
         mIndices = new unsigned int[numMaxIndices];
-
         // create new index buffer for the individual nodes
         mTestIndices = new unsigned int[numMaxIndices];
@@ -627 +640 @@
         CollectNodes(mRoot, nodes);
 
-        // assign ids to all nodes of the "regular" hierarchy
+        // assign unique ids to all nodes of the hierarchy
         int i = 0;
         BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
@@ -643 +656 @@
         BvhNodeContainer nodes;
 
-        nodes.reserve(GetNumNodes());
-        CollectNodes(mRoot, nodes);
+        nodes.reserve(GetNumStaticNodes());
+        CollectNodes(mStaticRoot, nodes);
 
         const unsigned int bufferSize = 8 * (int)nodes.size();
@@ -659 +672 @@
 
                 for (int j = 0; j < 8; ++ j)
-                        ((Vector3 *)mVertices)[node->GetId() * 8 + j] = node->GetBox().GetVertex(j);
+                        (static_cast<Vector3 *>(mVertices))[node->GetId() * 8 + j] = node->GetBox().GetVertex(j);
         }
 
@@ -676 +689 @@
         DEL_PTR(mVertices);
 
-        cout << "***** created vbos for tighter bounds *********" << endl;
+        cout << "******** created vbos for tighter bounds *********" << endl;
 }
 
@@ -704 +717 @@
         // collect all nodes
         BvhNodeContainer nodes;
-        CollectNodes(mRoot, nodes);
+        CollectNodes(mStaticRoot, nodes);
 
         cout << "recomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren << endl;
@@ -739 +752 @@
         // using the tighter bounds is not feasable in case
         // that the tighter bounds represent nearly the same projected area
-        // as the old bounding box. Find this out using either volume or area
-        // heuristics
+        // as the old bounding box. Test this property using either 
+        // volume or area heuristics
 
         float vol = 0;
@@ -915 +928 @@
 void Bvh::SetVirtualLeaves(int numTriangles) 
 {
-        // first invalidate old leaves
+        // first invalidate old virtual leaves
         BvhNodeContainer leaves;
-
-        CollectVirtualLeaves(mRoot, leaves);
+        CollectVirtualLeaves(mStaticRoot, leaves);
 
         BvhNodeContainer::const_iterator bit, bit_end = leaves.end();
@@ -929 +941 @@
         mNumVirtualNodes = 0;
 
-        // assign new virtual leaves based on specified number of triangles per leaf
+        // assign new virtual leaves based on specified #triangles per leaf
         std::stack<BvhNode *> nodeStack;
+
         nodeStack.push(mRoot);
 
@@ -952 +965 @@
                         BvhNode *b = interior->mBack;
 
-                        if (node->mIsMaxDepthForVirtualLeaf || (CountTriangles(node) <= numTriangles))
+                        if (node->mIsMaxDepthForVirtualLeaf || 
+                                (CountTriangles(node) <= numTriangles))
                         {
                                  node->mIsVirtualLeaf = true;
@@ -964 +978 @@
         }
 
+        /// Reset the node states
         ResetNodeClassifications();
 }
@@ -970 +985 @@
 void Bvh::PostProcess() 
 {
+        // this function must be called once after hierarchy creation
+
+        // We initialize the virtual leaves
+        // of this bvh, i.e., the nodes that are used as
+        // leaves of the hierarchy during traversal.
+
+        // Initially they are set either
+        // a) to the real leaves of the hierarchy or
+        // b) the point where the subdivision on object level ends
+        // and the subsequent nodes are just used to provide tighter bounds
+        // (see article for the notations)
+
         std::stack<BvhNode *> nodeStack;
-        nodeStack.push(mRoot);
+        nodeStack.push(mStaticRoot);
 
         while (!nodeStack.empty()) 
@@ -989 +1016 @@
                         BvhNode *b = interior->mBack;
 
-                        // point reached where we cannot subdivide further on object level
                         if ((f->mFirst == b->mFirst) && (f->mLast == b->mLast))
                         {
+                                // point reached where beyond there would be no further reduction 
+                                // as both subtrees contain the same objects => stop here
+                                // The tree beyond the current node is used to describe
+                                // tighter bounds on the geometry contained  in it
                                 node->mIsMaxDepthForVirtualLeaf = true;
                         }
@@ -1014 +1044 @@
                 //-- render AABB as triangle strips
 
+                // render first half of AABB
                 glVertex3f(l.x, l.y, u.z);
                 glVertex3f(u.x, l.y, u.z);
@@ -1025 +1056 @@
                 glPrimitiveRestartNV();
 
-                //-- render second half of AABB
+                // render second half of AABB
                 glVertex3f(l.x, u.y, u.z); 
                 glVertex3f(l.x, u.y, l.z);
@@ -1088 +1119 @@
 
 
-void Bvh::RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds)
+void Bvh::RenderBoundsForViz(BvhNode *node, 
+                                                         RenderState *state, 
+                                                         bool useTightBounds)
 {
         glDisable(GL_TEXTURE_2D);
@@ -1119 +1152 @@
 
 ////////////////////////
-// construction of the dynamic hierarchy
+//-- functions for construction of the dynamic hierarchy
 
 int Bvh::SortTriangles(BvhLeaf *leaf, 
@@ -1137 +1170 @@
                         -- j;
 
-                if (i < j) 
-                {
-                        swap(entities[i], entities[j]);
+                // sorting finished
+                if (i >= j) break;
+
+                // swap entities
+                swap(entities[i], entities[j]);
                         
-                        ++ i;
-                        -- j;
-                }
-                else
-                {
-                        break;
-                }
+                ++ i;
+                -- j;
         }
 
@@ -1169 +1199 @@
 {
         if (TerminationCriteriaMet(leaf))
+        {
+                leaf->mIsVirtualLeaf = true;
                 return leaf;
-        
+        }
+
         //int axis = leaf->mBox.MajorAxis();
         int axis = (parentAxis + 1) % 3;
@@ -1209 +1242 @@
         front->mLast = leaf->mLast;
         front->mDepth = leaf->mDepth + 1;
+
         leaf->mLast = split;
         leaf->mDepth = front->mDepth;
@@ -1238 +1272 @@
         BvhNode *dynamicRoot = static_cast<BvhInterior *>(mRoot)->mBack;
 
-        cout << "updating dynamic branch" << endl;
-
         // delete old branch
         if (!dynamicRoot->IsLeaf())
@@ -1251 +1283 @@
         }
 
+        cout << "updating dynamic branch" << endl;
+
         dynamicRoot = SubdivideLeaf(static_cast<BvhLeaf *>(dynamicRoot), 0, mDynamicEntities);
-}
-
-}
+
+        cout << "finished updating dynamic branch" << endl;
+}
+
+
+void Bvh::AddDynamicObject(SceneEntity *ent)
+{
+        mDynamicEntities.push_back(ent);
+}
+
+
+}