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

Timestamp:

10/26/08 18:29:27 (16 years ago)

Author:

mattausch

Message:

 

File:

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

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

@@ -151 +151 @@
 
 
+
+inline AxisAlignedBox3 ComputeBoundingBox(SceneEntity **entities, int numEntities)
+{
+        AxisAlignedBox3 box = entities[0]->GetWorldBoundingBox();
+
+        for (int i = 1; i < numEntities; ++ i)
+        {
+                box.Include(entities[i]->GetWorldBoundingBox());
+        }
+
+        return box;
+}
+
+
 Bvh::Bvh()
 {
@@ -419 +433 @@
         if (!mDynamicEntities.empty())
         {
-                UpdateDynamicBranch();
+                if (!mDynamicRoot)
+                        CreateDynamicBranch();
+                
+                UpdateDynamicBranch(mDynamicRoot);
         }
 }
@@ -448 +465 @@
         {
                 SceneEntity *ent = entities[i];
-                float dist = ent->GetTransformedBoundingBox().GetMaxDistance(sNearPlane);
+                float dist = ent->GetWorldBoundingBox().GetMaxDistance(sNearPlane);
 
                 if (dist > maxDist) maxDist = dist;
@@ -800 +817 @@
 
 
-void Bvh::ComputeBvhStats() 
-{
+void Bvh::ComputeBvhStats(BvhNode *root, BvhStats &bvhStats) 
+{
+        bvhStats.Reset();
         std::stack<BvhNode *> nodeStack;
-        nodeStack.push(mRoot);
+        nodeStack.push(root);
 
         int numVirtualLeaves = 0;
+        int numGeometry = 0;
 
         while (!nodeStack.empty()) 
@@ -815 +834 @@
                 {
                         ++ numVirtualLeaves;
+                        numGeometry += node->CountPrimitives();
 
                         BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
 
-                        mBvhStats.mTriangles += CountTriangles(leaf);
-                        mBvhStats.mLeafSA += leaf->mBox.SurfaceArea();
-                        mBvhStats.mLeafVol += leaf->mBox.GetVolume();
+                        bvhStats.mTriangles += CountTriangles(leaf);
+                        bvhStats.mLeafSA += leaf->mBox.SurfaceArea();
+                        bvhStats.mLeafVol += leaf->mBox.GetVolume();
                 } 
                 else 
                 {
-                        mBvhStats.mInteriorSA += node->mBox.SurfaceArea();
-                        mBvhStats.mInteriorVol += node->mBox.GetVolume();
+                        bvhStats.mInteriorSA += node->mBox.SurfaceArea();
+                        bvhStats.mInteriorVol += node->mBox.GetVolume();
 
                         BvhInterior *interior = static_cast<BvhInterior *>(node);
@@ -834 +854 @@
         }
 
-        mBvhStats.mGeometryRatio = mGeometrySize / (float)numVirtualLeaves;
-        mBvhStats.mTriangleRatio = mBvhStats.mTriangles / (float)numVirtualLeaves;
-}
-
-
-void Bvh::PrintBvhStats() const
-{
-        cout << "\n******** bvh stats: ***********" << endl;
-        cout << "interiorNodesSA = " << mBvhStats.mInteriorSA / mRoot->mBox.SurfaceArea() << endl;
-        cout << "leafNodesSA = " << mBvhStats.mLeafSA / mRoot->mBox.SurfaceArea() << endl;
-        cout << "interiorNodesVolume = " << mBvhStats.mInteriorVol / mRoot->mBox.GetVolume() << endl;
-        cout << "leafNodesVolume = " << mBvhStats.mLeafVol / mRoot->mBox.GetVolume() << endl;
-
-        cout << "geometry per leaf: " <<  mBvhStats.mGeometryRatio << endl;
-        cout << "triangles per leaf: " <<  mBvhStats.mTriangleRatio << endl;
-        cout << "**************" << endl << endl;
+        bvhStats.mGeometryRatio = (float)numGeometry / numVirtualLeaves;
+        bvhStats.mTriangleRatio = (float)bvhStats.mTriangles / numVirtualLeaves;
+        bvhStats.mLeaves = numVirtualLeaves;
+}
+
+
+void Bvh::PrintBvhStats(const BvhStats &bvhStats) const
+{
+        cout << "\n============ BVH statistics =============" << endl;
+        cout << "interiorNodesSA = " << bvhStats.mInteriorSA / mRoot->mBox.SurfaceArea() << endl;
+        cout << "leafNodesSA = " << bvhStats.mLeafSA / mRoot->mBox.SurfaceArea() << endl;
+        cout << "interiorNodesVolume = " << bvhStats.mInteriorVol / mRoot->mBox.GetVolume() << endl;
+        cout << "leafNodesVolume = " << bvhStats.mLeafVol / mRoot->mBox.GetVolume() << endl;
+
+        cout << "geometry per leaf: " << bvhStats.mGeometryRatio << endl;
+        cout << "triangles per leaf: " << bvhStats.mTriangleRatio << endl;
+        cout << "===========================================" << endl << endl;
 }
 
@@ -1155 +1176 @@
 int Bvh::SortTriangles(BvhLeaf *leaf, 
                                            int axis, 
-                                           float position,
-                                           SceneEntityContainer &entities)
+                                           float position
+                                           )
 {
         int i = leaf->mFirst;
         int j = leaf->mLast;
 
-    while (1) 
-        {
-                while (entities[i]->GetCenter()[axis] < position) 
+    while (1)
+        {
+                while (mGeometry[i]->GetWorldCenter()[axis] < position) 
+                {
+                        //cout<<" i " << i << " " << mGeometry[i]->GetWorldCenter()[axis];
                         ++ i;
-        
-                while (position < entities[j]->GetCenter()[axis])
+                }
+
+                while (position < mGeometry[j]->GetWorldCenter()[axis])
+                {
+                        //cout<< axis << " j " << j << " " << mGeometry[j]->GetWorldCenter()[axis] << " " << position<< " ";
                         -- j;
+                }
 
                 // sorting finished
@@ -1173 +1200 @@
 
                 // swap entities
-                swap(entities[i], entities[j]);
+                swap(mGeometry[i], mGeometry[j]);
                         
                 ++ i;
@@ -1184 +1211 @@
 
 int Bvh::SortTrianglesSpatialMedian(BvhLeaf *leaf, 
-                                                                        int axis,
-                                                                        SceneEntityContainer &entities)
+                                                                        int axis
+                                                                        )
 {
         // spatial median
         float m = leaf->mBox.Center()[axis];
-        return SortTriangles(leaf, axis, m, entities);
+        //cout << "here3 " << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
+        return SortTriangles(leaf, axis, m);
 }
 
 
 BvhNode *Bvh::SubdivideLeaf(BvhLeaf *leaf, 
-                                                        int parentAxis, 
-                                                        SceneEntityContainer &entities)
+                                                        int parentAxis
+                                                        )
 {
         if (TerminationCriteriaMet(leaf))
         {
                 leaf->mIsVirtualLeaf = true;
+                leaf->mIsMaxDepthForVirtualLeaf = true;
                 return leaf;
         }
 
-        //int axis = leaf->mBox.MajorAxis();
-        int axis = (parentAxis + 1) % 3;
+        //const int axis = (parentAxis + 1) % 3;
+        const int axis = leaf->mBox.MajorAxis();
+        
+
+        const int scale = 20;
 
         // 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);
+        split = SortTrianglesSpatialMedian(leaf, axis);
         pos = leaf->mBox.Center()[axis];
         
@@ -1247 +1277 @@
         
         // reset box
-        leaf->mBox.Initialize();
+        //leaf->mBox.Initialize();
+
+        front->mBox = ComputeBoundingBox(mGeometry + front->mFirst, front->CountPrimitives());
+        leaf->mBox = ComputeBoundingBox(mGeometry + leaf->mFirst, leaf->CountPrimitives());
 
         // recursively continue subdivision
-        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis, entities);
-        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis, entities);
+        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis);
+        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis);
         
         return parent;
@@ -1267 +1300 @@
 
 
-void Bvh::UpdateDynamicBranch()
+void Bvh::UpdateDynamicBranch(BvhNode *node)
+{
+        if (node->IsLeaf())
+        {
+                int numEntities;
+                SceneEntity **entities = GetGeometry(node, numEntities);
+
+                node->mBox = ComputeBoundingBox(entities, numEntities);
+                //cout << "box: " << node->mBox << endl;
+        }
+        else
+        {
+                BvhNode *f = static_cast<BvhInterior *>(node)->GetFront();
+                BvhNode *b = static_cast<BvhInterior *>(node)->GetBack();
+
+                UpdateDynamicBranch(f);
+                UpdateDynamicBranch(b);
+
+                node->mBox = f->mBox;
+                node->mBox.Include(b->mBox);
+        }
+}
+
+
+void Bvh::CreateDynamicBranch()
 {
         // the bvh has two main branches
@@ -1278 +1335 @@
         // the movements of the objects within
 
-        // delete old branch
-        cout << "deleting old branch" << endl;
-
         DEL_PTR(mDynamicRoot);
 
-        mDynamicRoot = new BvhLeaf(mRoot);
-        mDynamicRoot->mBox = mRoot->mBox;
-
-        mDynamicRoot->mFirst = 0;
-        mDynamicRoot->mLast = (int)mDynamicEntities.size() - 1;
-        mDynamicRoot->mArea = mDynamicRoot->mBox.SurfaceArea();
-        
-        cout << "updating dynamic branch" << endl;
-
-        mDynamicRoot = SubdivideLeaf(static_cast<BvhLeaf *>(mDynamicRoot), 0, mDynamicEntities);
-
-        cout << "finished updating dynamic branch" << endl;
-}
-
-
-void Bvh::AddDynamicObject(SceneEntity *ent)
-{
-        mDynamicEntities.push_back(ent);
+        BvhLeaf *l = new BvhLeaf(mRoot);
+
+        l->mBox.Initialize();
+
+        SceneEntityContainer::const_iterator sit, sit_end = mDynamicEntities.end();
+
+        for (sit = mDynamicEntities.begin(); sit != sit_end; ++ sit)
+        {
+                l->mBox.Include((*sit)->GetWorldBoundingBox());
+        }
+
+        l->mFirst = (int)(mGeometrySize - mDynamicEntities.size());
+        l->mLast = (int)mGeometrySize - 1;
+        l->mArea = l->mBox.SurfaceArea();
+        
+        cout << "updating dynamic branch " << l->mFirst << " " << l->mLast << endl;
+
+        mDynamicRoot = SubdivideLeaf(l, 0);
+
+        BvhStats bvhStats;
+        ComputeBvhStats(mDynamicRoot, bvhStats);
+
+        cout << "\n=========== Dynamic BVH statistics: =========" << endl;
+        cout << "leaves = " << bvhStats.mLeaves << endl;
+        cout << "interiorNodesSA = " << bvhStats.mInteriorSA << endl;
+        cout << "leafNodesSA = " << bvhStats.mLeafSA << endl;
+        cout << "interiorNodesVolume = " << bvhStats.mInteriorVol  << endl;
+        cout << "leafNodesVolume = " << bvhStats.mLeafVol << endl;
+
+        cout << "geometry per leaf: " << bvhStats.mGeometryRatio << endl;
+        cout << "triangles per leaf: " << bvhStats.mTriangleRatio << endl;
+        cout << "=============================================" << endl << endl;
+}
+
+
+void Bvh::AddDynamicObjects(const SceneEntityContainer &entities)
+{
+        // copy old entities
+        SceneEntity **newGeom = new SceneEntity*[mGeometrySize + (int)entities.size()];
+
+        memcpy(newGeom, mGeometry, mGeometrySize * sizeof(SceneEntity *));
+
+        delete [] mGeometry;
+        mGeometry = newGeom;
+
+        // now add new entities
+        SceneEntityContainer::const_iterator it, it_end = entities.end();
+
+        size_t i = mGeometrySize;
+        for (it = entities.begin(); it != it_end; ++ it, ++ i)
+        {
+                mGeometry[i] = (*it);
+                mDynamicEntities.push_back(*it);
+        }
+
+
+        mGeometrySize += entities.size();
 }