Changeset 3269 for GTP/trunk/App/Demos/Vis/FriendlyCulling/src/BvhConstructor.cpp

Timestamp:

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

Author:

mattausch

Message:

 

File:

• GTP/trunk/App/Demos/Vis/FriendlyCulling/src/BvhConstructor.cpp (modified) (7 diffs)

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