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

Timestamp:

10/21/08 12:47:27 (16 years ago)

Author:

mattausch

Message:

debug render queue

File:

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

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

@@ -204 +204 @@
 
         mVboId = -1;
+
+        mMaxDepthForDynamicBranch = 10;
 }
 
@@ -397 +399 @@
         // store near plane
         sNearPlane = Plane3(cam->GetDirection(), cam->GetPosition());
+
+        // rebuild dynamic part of the hierarchy
+        if (!mDynamicEntities.empty())
+        {
+                UpdateDynamicBranch();
+        }
 }
 
@@ -1110 +1118 @@
 
 
-}
+////////////////////////
+// construction of the dynamic hierarchy
+
+int Bvh::SortTriangles(BvhLeaf *leaf, 
+                                           int axis, 
+                                           float position,
+                                           SceneEntityContainer &entities)
+{
+        int i = leaf->mFirst;
+        int j = leaf->mLast;
+
+    while (1) 
+        {
+                while (entities[i]->GetCenter()[axis] < position) 
+                        ++ i;
+        
+                while (position < entities[j]->GetCenter()[axis])
+                        -- j;
+
+                if (i < j) 
+                {
+                        swap(entities[i], entities[j]);
+                        
+                        ++ i;
+                        -- j;
+                }
+                else
+                {
+                        break;
+                }
+        }
+
+        return j;
+}
+
+
+int Bvh::SortTrianglesSpatialMedian(BvhLeaf *leaf, 
+                                                                        int axis,
+                                                                        SceneEntityContainer &entities)
+{
+        // spatial median
+        float m = leaf->mBox.Center()[axis];
+        return SortTriangles(leaf, axis, m, entities);
+}
+
+
+BvhNode *Bvh::SubdivideLeaf(BvhLeaf *leaf, 
+                                                        int parentAxis, 
+                                                        SceneEntityContainer &entities)
+{
+        if (TerminationCriteriaMet(leaf))
+                return leaf;
+        
+        //int axis = leaf->mBox.MajorAxis();
+        int axis = (parentAxis + 1) % 3;
+
+        // position of the split in the partailly sorted array of triangles
+        // corresponding to this leaf
+        int split = -1;
+        const int scale = 20;
+
+        float pos = -1.0f;
+
+        // Spatial median subdivision
+        split = SortTrianglesSpatialMedian(leaf, axis, entities);
+        pos = leaf->mBox.Center()[axis];
+        
+        if (split == leaf->mLast)
+        {
+                // no split could be achieved => just halve number of objects
+                split = (leaf->mLast - leaf->mFirst) / 2;
+                cerr << "no reduction " << leaf->CountPrimitives() << " " << leaf->mFirst << " " << split << " " << leaf->mLast << endl;
+        }
+
+        // create two more nodes
+        mNumNodes += 2;
+        BvhInterior *parent = new BvhInterior(leaf->GetParent());
+        BvhLeaf *front = new BvhLeaf(parent);
+        
+        parent->mAxis = axis;
+        parent->mBox = leaf->mBox;
+        parent->mDepth = leaf->mDepth;
+
+        parent->mBack = leaf;
+        parent->mFront = front;
+        //parent->mPosition = pos;
+        
+        // now assign the triangles to the subnodes
+        front->mFirst = split + 1;
+        front->mLast = leaf->mLast;
+        front->mDepth = leaf->mDepth + 1;
+        leaf->mLast = split;
+        leaf->mDepth = front->mDepth;
+        leaf->mParent = parent;
+        
+        // reset box
+        leaf->mBox.Initialize();
+
+        // recursively continue subdivision
+        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis, entities);
+        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis, entities);
+        
+        return parent;
+}
+
+
+bool Bvh::TerminationCriteriaMet(BvhLeaf *leaf) const
+{
+        const bool criteriaMet = 
+                (leaf->mDepth > mMaxDepthForDynamicBranch) ||
+                (leaf->CountPrimitives() == 1);
+
+        return criteriaMet;
+}
+
+
+void Bvh::UpdateDynamicBranch()
+{
+        BvhNode *dynamicRoot = static_cast<BvhInterior *>(mRoot)->mBack;
+
+        cout << "updating dynamic branch" << endl;
+
+        // delete old branch
+        if (!dynamicRoot->IsLeaf())
+        {
+                cout << "deleting old branch" << endl;
+
+                DEL_PTR(dynamicRoot);
+
+                dynamicRoot = new BvhLeaf(mRoot);
+                dynamicRoot->mBox = mRoot->mBox;
+        }
+
+        dynamicRoot = SubdivideLeaf(static_cast<BvhLeaf *>(dynamicRoot), 0, mDynamicEntities);
+}
+
+}