Changeset 3064

Timestamp:

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

Author:

mattausch

Message:

working on dynamic bvh hierarchy: denug version

Location:

GTP/trunk/App/Demos/Vis/FriendlyCulling

Files:

• default.env (modified) (1 diff)
• src/Bvh.cpp (modified) (33 diffs)
• src/Bvh.h (modified) (9 diffs)
• src/BvhLoader.cpp (modified) (2 diffs)
• src/chcdemo.cpp (modified) (2 diffs)

GTP/trunk/App/Demos/Vis/FriendlyCulling/default.env

@@ -10 +10 @@
 winHeight=768
 camPosition=483.398f 242.364f 186.078f
-#camDirection=1 0 0
+camDirection=1 0 0
 lightDirection=-0.8f 1.0f -0.7f
 #lightDirection=0.0f 0.0f -1.0f

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);
+}
+
+
+}

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

@@ -478 +478 @@
         */
         BvhNode *GetRoot() { return mRoot; }
-        /** Sets the scene camera
-        */
-        //void SetCamera(Camera * camera) { mCamera = camera; }
-
+        
         ///////////////
         //-- functions collecting nodes based on some criteria
 
+        /** Collect all nodes higher or equal to a given depth.
+        */
         void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
         void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
+        /** Collect the "physical" leaves of the hierarchy
+        */
         void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
-        /** Collect only the virtual leaves.
+        /** Collect only the virtual leaves (can be anywhere in the Žhierarchy).
         */
         void CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves);
@@ -543 +544 @@
         */
         void ResetNodeClassifications();
-        /** Helper function that renders the bounding boxes of the leaves as
-                wireframes for visualization purpose.
-        */
-        //void RenderBoundingBoxesForViz(int mode);
         /** Count triangles the node contains.
         */
@@ -557 +554 @@
         void ComputeIds();
         /** Assign virtual leaves based on specified number of triangles per leaf.
+                That means that we try to set the leaves at a point where we
+                have less than numTriangles triangles within this leaf and beyond.
+
+                Virtual leaves are nodes that are determined to be the leaves
+                of the hierarchy during render traversal. These nodes are not necessarily 
+                the same as the real leaves of the hierarchy and can be anywhere
+                in the hierarchy. 
+                Please refer to the article for more info about virtual leaves
         */
         void SetVirtualLeaves(int numTriangles);
         
 
-        ////////
-        //-- functions influencing tighter bounds
+        ////////////
+        //-- functions influencing the tightness of the bounds that are used for testing
 
 
         /** Sets maximal depth for taking the bounding boxes to test the
                 visibility of a node. 
-                Deeper => the bounds adapt more to the geometry.
+                Deeper level means that the bounds adapt more to the geometry but
+                also that more boxes are rendered
         */
         void SetMaxDepthForTestingChildren(int maxDepth);
-
+        /** The ratio of area between node and subnodes where 
+                testing the subnodes as proxy is still considered feasable
+        */
         void SetAreaRatioThresholdForTestingChildren(float ratio);
 
@@ -583 +591 @@
         void RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds);
 
+        void AddDynamicObject(SceneEntity *ent);
+
 
 protected:
@@ -608 +618 @@
         
         void PrepareVertices();
-
+        /** Prepare nodes for vbo rendering.
+        */
         int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
+        /** Render the nodes from the vbo prepared previously.
+        */
         void RenderBoundsWithDrawArrays(int numNodes, RenderState *state);
 
@@ -643 +656 @@
 
         /////////////////////////////
-
+        // functions that are required to build the dynamic part of the hierarchy
         int SortTriangles(BvhLeaf *leaf, 
                               int axis, 
@@ -656 +669 @@
                                    int parentAxis, 
                                                    SceneEntityContainer &entities);
-
         /** Recompute the dynamic branch of the hierarchy.
         */
@@ -663 +675 @@
         inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;
 
+        /** Returns number of bvh nodes.
+        */
+        inline int GetNumStaticNodes() const { return mNumNodes; }
 
         ////////////////////////
@@ -670 +685 @@
         /// the root of the hierarchy
         BvhNode *mRoot;
+        /// the root of static part of the the hierarchy
+        BvhNode *mStaticRoot;
+        /// the root of dynamic part of the the hierarchy
+        BvhNode *mDynamicRoot;
         /// pointers to the geometry associated with this node
         SceneEntity **mGeometry;

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

@@ -73 +73 @@
 
         Bvh *bvh = new Bvh(entities);
+        bvh->mStaticRoot = LoadNextNode(stream, NULL);
 
-        BvhNode *root = LoadNextNode(stream, NULL);
+#if 1
+        bvh->mRoot = bvh->mStaticRoot;
+        bvh->mNumNodes = 1;
+#else
 
-#if 0
+        // we are setting a new root node 
+        // and adds one level of indirection to the bvh 
+        // It allows us to use dynamic objects
 
-        bvh->mRoot = root;
-
-#else
-        // we are setting a new root node
-        // which adds one level of indirection to the bvh but 
-        // allows us to use dynamic objects
         // the new bvh has two main branches
-        // one is the static branch (the old root),
-        // one is the dynamic branch 
+        // a static branch (the old root), and adynamic branch 
         // we create a 'dynamic' leaf which basically is a container
         // for all dynamic objects underneath
@@ -93 +92 @@
         // the movements of the objects within
 
+        // create new root
         BvhInterior *newRoot = new BvhInterior(NULL);
         bvh->mRoot = newRoot;
 
-        BvhLeaf *dynamicLeaf = new BvhLeaf(newRoot);
+        // the separation is a purely logical one
+        // the bounding boxes of the child nodes are 
+        // identical to those of the root node
 
-        newRoot->mFront = root;
-        newRoot->mBack = dynamicLeaf;
-        root->mParent = newRoot;
+        newRoot->mBox = bvh->mStaticRoot->mBox;
+        newRoot->mArea = newRoot->mBox.SurfaceArea();
 
-        // the separation is a purely logical one
-        // the bounding boxes of the child nodes is the
-        // same as for the root node
-        newRoot->mBox = root->mBox;
-        dynamicLeaf->mBox = root->mBox;
+        newRoot->mFirst = bvh->mStaticRoot->mFirst;
+        newRoot->mLast = bvh->mStaticRoot->mLast;
 
-        newRoot->mArea = newRoot->mBox.SurfaceArea();
-        dynamicLeaf->mArea = dynamicLeaf->mBox.SurfaceArea();
+        // add static root on left subtree
+        newRoot->mFront = bvh->mStaticRoot;
+        bvh->mStaticRoot->mParent = newRoot;
+        
+        // create and add dynamic root
+        BvhLeaf *dynamicRoot = new BvhLeaf(newRoot);
+        
+        dynamicRoot->mFirst = 0;
+        dynamicRoot->mLast = 0;
+        dynamicRoot->mBox = bvh->mStaticRoot->mBox;
+        dynamicRoot->mArea = dynamicRoot->mBox.SurfaceArea();
 
-        newRoot->mFirst = root->mFirst;
-        newRoot->mLast = root->mLast;
+        bvh->mDynamicRoot = dynamicRoot;
+        newRoot->mBack = dynamicRoot;
 
-        dynamicLeaf->mFirst = 0;
-        dynamicLeaf->mLast = 0;
+        bvh->mNumNodes = 1;
+
 #endif
 
-        tQueue.push(root);
-        bvh->mNumNodes = 1;
+        tQueue.push(bvh->mStaticRoot);
 
         while(!tQueue.empty())

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

@@ -178 +178 @@
 
 bool useOptimization = false;
-bool useTightBounds = true;
+//bool useTightBounds = true;
+bool useTightBounds = false;
 bool useRenderQueue = true;
 bool useMultiQueries = true;
@@ -483 +484 @@
 
         buddha->GetTransform()->SetMatrix(transl);
+
+        bvh->AddDynamicObject(buddha);
+
 
         // this function assign the render queue bucket ids of the materials in beforehand