Changeset 3269 for GTP/trunk/App/Demos/Vis/FriendlyCulling/src

Timestamp:

01/12/09 00:17:58 (15 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/App/Demos/Vis/FriendlyCulling/src

Files:

• Bvh.cpp (modified) (2 diffs)
• BvhConstructor.cpp (modified) (7 diffs)
• BvhConstructor.h (modified) (2 diffs)
• BvhLoader.cpp (modified) (1 diff)
• chcdemo.cpp (modified) (2 diffs)

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

@@ -857 +857 @@
         CollectNodes(mRoot, nodes);
 
-        cout << "recomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren << endl;
+        cout << "\nrecomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren << endl;
 
         int success = 0;
@@ -1430 +1430 @@
         // the movements of the objects within
 
+        
+        cout << "\n==============================" << endl;
         cout << "creating dynamic bvh branch"  << endl;
 

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

@@ -8 +8 @@
 #include <stack>
 #include <fstream>
+
+#define MAX_FLOAT 1e20f
+
 
 #ifdef _CRT_SET
@@ -32 +35 @@
 mFirst(first),
 mLast(last),
-mMaxDepth(10),
+mMaxDepth(20),
 mMaxObjects(1),
-mNumNodes(0)
-{
+mMaxTriangles(1),
+mNumNodes(0),
+mSplitType(SAH)
+{
+}
+
+
+float BvhConstructor::EvaluateSahCost(BvhLeaf *leaf, int axis, float position)
+{
+        // count triangles on the left / right
+        int left = 0;
+        int right = 0;
+        AxisAlignedBox3 leftBox, rightBox;
+
+        leftBox.Initialize();
+        rightBox.Initialize();
+
+        const int candidates = std::max(50, (int)(leaf->CountPrimitives() / 20));
+        const float finc = leaf->CountPrimitives() / (float)candidates;
+
+        int i = leaf->mFirst;
+        float fi = leaf->mFirst + 0.5f;
+
+        AxisAlignedBox3 box;
+
+        for (; i <= leaf->mLast;) 
+        {
+                box = mEntities[i]->GetWorldBoundingBox();
+
+                if (box.Center(axis) < position) 
+                {
+                        ++ left;
+                        // update the box
+                        leftBox.Include(box);
+                } 
+                else 
+                {
+                        ++ right;
+                        rightBox.Include(box);
+                }
+                 
+                fi += finc;
+                i = (int)fi;
+        }
+
+        float bW = 1.0f;
+        float leftRatio = left / (float)leaf->CountPrimitives();
+        float rightRatio = right / (float)leaf->CountPrimitives();
+
+        float saLeft = 0.0f;
+        float saRight = 0.0f;
+
+        // not a valid split
+        if (!left || !right)
+                return 1e25f;
+
+        saLeft = leftBox.SurfaceArea();
+        saRight = rightBox.SurfaceArea();
+
+
+        return
+                saLeft  * ((1.0f - bW) + bW * leftRatio) + 
+                saRight * ((1.0f - bW) + bW * rightRatio);
+}
+
+
+float BvhConstructor::SelectPlaneSah(BvhLeaf *leaf, int &axis, float &minCost)
+{
+        minCost = MAX_FLOAT;
+        float bestPos = minCost;
+        int bestAxis = 0;
+
+        //  cout<<"Evaluating axis..."<<endl<<flush;
+
+        const int initialPlanes = 3;
+
+        // initiate the costs
+        for (axis = 0; axis < 3; ++ axis) 
+        {
+                const float size = leaf->mBox.Size(axis);
+
+                for (int i = 0; i < initialPlanes; ++ i) 
+                {
+                        const float pos = leaf->mBox.Min(axis) + (i + 1) * size / (initialPlanes + 1);
+                        const float cost = EvaluateSahCost(leaf, axis, pos);
+
+                        if (cost < minCost) 
+                        {
+                                minCost = cost;
+                                bestPos = pos;
+                                bestAxis = axis;
+                        }
+                }
+        }
+
+        axis = bestAxis;
+
+        //  cout<<axis<<endl<<flush;
+        const float shrink = 0.5f;
+
+        // now hierarchically refine the initial interval
+        float size = shrink * 
+                (leaf->mBox.Max(axis) - leaf->mBox.Min(axis)) / (initialPlanes + 1);
+
+        const int steps = 4;
+        float cost;
+
+        for (int i = 0; i < steps; ++ i) 
+        {
+                const float left = bestPos - size;
+                const float right = bestPos + size;
+
+                cost = EvaluateSahCost(leaf, axis, left);
+
+                if (cost < minCost) 
+                {
+                        minCost = cost;
+                        bestPos = left;
+                }
+
+                cost = EvaluateSahCost(leaf, axis, right);
+
+                if (cost < minCost) 
+                {
+                        minCost = cost;
+                        bestPos = right;
+                }
+
+                size = shrink * size;
+        }
+
+        //OUT1("best axis: " << axis << " " << bestPos << " " << minCost);
+
+        return bestPos;
 }
 
@@ -102 +237 @@
 
 
+int BvhConstructor::SortTrianglesObjectMedian(BvhLeaf *leaf, int axis, float &pos)
+{
+        // Now distribute the objects into the subnodes
+        // Use QuickMedian sort
+        int l = leaf->mFirst;
+        int r = leaf->mLast;
+        int k = (l + r) / 2;
+
+        while (l < r) 
+        {
+                int i = l;
+                int j = r;
+
+                // get some estimation of the pivot
+                pos = mEntities[(l + r) / 2]->GetBoundingBox().Center(axis);
+
+                while (1) 
+                {
+                        while ((i <= leaf->mLast) && (mEntities[i]->GetWorldBoundingBox().Center(axis) < pos))
+                                ++ i;
+
+                        while((j >= leaf->mFirst) && (pos < mEntities[j]->GetWorldBoundingBox().Center(axis)))
+                                -- j;
+
+                        if (i <= j) 
+                        {
+                                std::swap(mEntities[i], mEntities[j]);
+                                ++ i;
+                                -- j;
+                        }
+                        else
+                        {
+                                break;
+                        }
+                }
+
+                // now check the extents
+                if (i >= k)
+                        r = j;
+                else
+                        l = i;
+        }
+
+        return k;
+}
+
+
 BvhNode *BvhConstructor::SubdivideLeaf(BvhLeaf *leaf, 
                                                                            int parentAxis
@@ -114 +296 @@
 
         //const int axis = (parentAxis + 1) % 3;
-        const int axis = leaf->mBox.MajorAxis();
+        int axis = leaf->mBox.MajorAxis();
         const int scale = 20;
 
@@ -121 +303 @@
         int split = -1;
         float pos = -1.0f;
-        
+
         // Spatial median subdivision
-        split = SortTrianglesSpatialMedian(leaf, axis);
-        pos = leaf->mBox.Center()[axis];
+        switch (mSplitType) 
+        {
+        case SPATIAL_MEDIAN:
+                split = SortTrianglesSpatialMedian(leaf, axis);
+                pos = leaf->mBox.Center()[axis];
+                break;
+        case OBJECT_MEDIAN:
+                // Object median subdivision: approximately the same number
+                // of objects on the left of the the splitting point.
+                split = SortTrianglesObjectMedian(leaf, axis, pos);
+                break;
+        case SAH:
+                {
+                        float cost;
+                        pos = SelectPlaneSah(leaf, axis, cost);
+
+                        if (pos != MAX_FLOAT)
+                        {
+                                split = SortTriangles(leaf, axis, pos);
+                        }
+
+                        if ((pos == MAX_FLOAT) || (split == leaf->mLast))
+                        {
+                                split = -1;
+                                split = SortTrianglesObjectMedian(leaf, axis, pos);
+                        }
+                }
+                break;
+        default:
+                cerr << "should not come here" << endl;
+                break;
+        }
         
         if (split == leaf->mLast)
@@ -168 +380 @@
 
 
+int BvhConstructor::CountTriangles(BvhNode *node) const
+{
+        int numTriangles = 0;
+
+        for (int i = node->mFirst; i <= node->mLast; ++ i)
+        {
+                numTriangles += mEntities[i]->CountNumTriangles(0);
+        }
+
+        return numTriangles;
+}
+
+
 bool BvhConstructor::TerminationCriteriaMet(BvhLeaf *leaf) const
 {
         const bool criteriaMet = 
                 (leaf->mDepth > mMaxDepth) ||
-                (leaf->CountPrimitives() <= mMaxObjects);
+                (leaf->CountPrimitives() <= mMaxObjects) ||
+                (CountTriangles(leaf) <= mMaxTriangles);
 
         return criteriaMet;
@@ -188 +414 @@
         l->mLast = mLast;
 
-        cout << "constructing bvh from "  << l->mFirst << " to " << l->mLast << endl;
+        cout << "\n================================" << endl;
+        cout << "constructing bvh for " << l->mLast - l->mFirst + 1 << " entities" << endl;
 
         l->mBox = SceneEntity::ComputeBoundingBox(mEntities + mFirst, mLast - mFirst + 1);

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

@@ -21 +21 @@
         BvhNode *Construct(int &nodes);
 
+        /** Types of split heuristics.
+        */      
+        enum {SPATIAL_MEDIAN, OBJECT_MEDIAN, SAH};      
 
 protected:
 
-        int SortTriangles(BvhLeaf *leaf, int axis, float position);
+        //////////
+        //-- sorting functions
 
-        int SortTrianglesSpatialMedian(BvhLeaf *leaf, int axis);
-
+        /** The method of subdividing objects into halves in some axis using spatial median
+        */
+        int     SortTrianglesSpatialMedian(BvhLeaf *leaf, int axis);
+        /** The method of subdividing objects into halves in some axis
+                using object median.
+        */
+        int SortTrianglesObjectMedian(BvhLeaf *leaf, int axis, float &pos);
+        /** sort triangles along the axis with respect to the splitting plane 
+                given by axis/position return index of the first tiangles belong 
+                to the front of the splitting plane.
+        */
+        int     SortTriangles(BvhLeaf *leaf, const int axis, const float position);
+        /** sort triangles by their area.
+        */
+        int SortTrianglesSurfaceArea(BvhLeaf *leaf, float sa);
+        /** This function drives the subdivision.
+        */
         BvhNode *SubdivideLeaf(BvhLeaf *leaf, int parentAxis);
 
         inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;
+        /** Update the bounding box of this node and the child nodes
+        */
+        void UpdateBoundingBoxes(BvhNode *node);
+        /** Select splitting plane using SAH - returns the position of the splitting plane.
+        */
+        float SelectPlaneSah(BvhLeaf *leaf, int &axis, float &minCost);
+        /** evaluate the SAH cost of a particulkar splitting plane
+        */
+        float EvaluateSahCost(BvhLeaf *leaf, int axis, float position);
 
-        void UpdateBoundingBoxes(BvhNode *node);
+        int CountTriangles(BvhNode *node) const;
+
 
 
@@ -45 +74 @@
         int mMaxObjects;
         int mNumNodes;
+        int mSplitType;
+        int mMaxTriangles;
 };
 

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

@@ -138 +138 @@
 {
 
-        cout << "\n******************* bvh *******************" << endl;
-
         Bvh *bvh = new Bvh(staticEntities, dynamicEntities, maxDepthForTestingChildren);
 
-        cout << "here8 " << (int)bvh->mStaticGeometrySize - 1 << endl;
         BvhConstructor bvhConstructor(bvh->mGeometry, 
                                           0,

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

@@ -1387 +1387 @@
 
                 if (recordFrames && replayPath)
+                {
+                        // record all frames of the walkthrough
                         deferredShader->SetSaveFrame(recordedFramesSuffix, currentReplayFrame);
+                }
                 else if (makeSnapShot)
-                        deferredShader->SetSaveFrame("snap", snapShotIdx ++);           
+                {
+                        // make snap shot
+                        deferredShader->SetSaveFrame("snap", snapShotIdx ++);
+                }
                 else
+                {
+                        // do nothing
                         deferredShader->SetSaveFrame("", -1);           
-
+                }
                 //if (makeSnapShot) makeSnapShot = false;
 
@@ -1402 +1410 @@
         renderState.SetRenderTechnique(FORWARD);
         renderState.Reset();
-
 
         glDisableClientState(GL_VERTEX_ARRAY);