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

Timestamp:

01/11/09 12:56:56 (15 years ago)

Author:

mattausch

Message:

 

File:

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

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

@@ -202 +202 @@
         }
 
-        cout << "max depth for testing children" << mMaxDepthForTestingChildren << endl;
+        //cout << "max depth for testing children " << mMaxDepthForTestingChildren << endl;
 }
 
@@ -229 +229 @@
 
         mMaxDepthForTestingChildren = maxDepthForTestingChildren;
-        cout << "max depth for testing children" << mMaxDepthForTestingChildren << endl;
+        //cout << "max depth for testing children " << mMaxDepthForTestingChildren << endl;
 }
 
@@ -956 +956 @@
         int numVirtualLeaves = 0;
         int numGeometry = 0;
-
+cout<<"here3 computing stats"<<endl;
         while (!nodeStack.empty()) 
         {
@@ -962 +962 @@
                 nodeStack.pop();
 
+                cout << "x";
+                if (node->IsLeaf() && !node->IsVirtualLeaf())
+                        cerr << "here34"<<endl;
+
                 if (node->IsVirtualLeaf()) 
                 {
@@ -967 +971 @@
                         numGeometry += node->CountPrimitives();
 
+                        cout << " l " << numGeometry;
                         BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
 
@@ -975 +980 @@
                 else 
                 {
+                        cout << "i";
+
                         bvhStats.mInteriorSA += node->mBox.SurfaceArea();
                         bvhStats.mInteriorVol += node->mBox.GetVolume();
@@ -991 +998 @@
 
 
-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;
+void Bvh::PrintBvhStats(const BvhStats &bvhStats, BvhNode *root) const
+{
+        cout << "interiorNodesSA = " << bvhStats.mInteriorSA / root->mBox.SurfaceArea() << endl;
+        cout << "leafNodesSA = " << bvhStats.mLeafSA / root->mBox.SurfaceArea() << endl;
+        cout << "interiorNodesVolume = " << bvhStats.mInteriorVol / root->mBox.GetVolume() << endl;
+        cout << "leafNodesVolume = " << bvhStats.mLeafVol / root->mBox.GetVolume() << endl;
 
         cout << "geometry per leaf: " << bvhStats.mGeometryRatio << endl;
@@ -1086 +1092 @@
         nodeStack.push(mRoot);
 
+        cout << "here9" << endl;
         while (!nodeStack.empty()) 
         {
+                cout <<"u"<< endl;
                 BvhNode *node = nodeStack.top();
                 nodeStack.pop();
@@ -1108 +1116 @@
                                 (CountTriangles(node) <= numTriangles))
                         {
-                                 node->mIsVirtualLeaf = true;
+                                cout << " l " << CountTriangles(node) << " " << node->mIsMaxDepthForVirtualLeaf << endl;
+                                node->mIsVirtualLeaf = true;
                         }
                         else
@@ -1138 +1147 @@
         nodeStack.push(mRoot);
 
+        cout << "here7 computing depth" << endl;
         while (!nodeStack.empty()) 
         {
                 BvhNode *node = nodeStack.top();
                 nodeStack.pop();
-
+cout << "z";
                 if (node->IsLeaf()) 
                 {
@@ -1156 +1166 @@
                         if ((f->mFirst == b->mFirst) && (f->mLast == b->mLast))
                         {
+                                cout << "f: " << f->mFirst << " " << f->mLast << endl;
                                 // point reached where beyond there would be no further reduction 
                                 // as both subtrees contain the same objects => stop here
@@ -1169 +1180 @@
                 }
         }
+        cout << "here7" << endl;
 }
 
@@ -1191 +1203 @@
         // compute and print stats for whole (static + dynamic) bvh
         ComputeBvhStats(mRoot, mBvhStats);
-        PrintBvhStats(mBvhStats);
+
+        BvhStats staticBvhStats;
+        ComputeBvhStats(mRoot, staticBvhStats);
+        cout << "\n============ Static BVH statistics =============" << endl;
+
+        PrintBvhStats(staticBvhStats, mStaticRoot);
 
         // also output dynamic stats
         if (mDynamicGeometrySize)
         {
-                BvhStats bvhStats;
-                ComputeBvhStats(mDynamicRoot, bvhStats);
-
+                BvhStats dynBvhStats;
+                ComputeBvhStats(mDynamicRoot, dynBvhStats);
+        
                 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;
+                PrintBvhStats(dynBvhStats, mDynamicRoot);
         }
 }
@@ -1344 +1353 @@
 
 
-////////////////////////
-//-- functions for construction of the dynamic hierarchy
-
-int Bvh::SortTriangles(BvhLeaf *leaf, 
-                                           int axis, 
-                                           float position
-                                           )
-{
-        int i = leaf->mFirst;
-        int j = leaf->mLast;
-
-    while (1)
-        {
-                //while (mGeometry[i]->GetWorldCenter()[axis] < position) ++ i;
-                //while (position < mGeometry[j]->GetWorldCenter()[axis]) -- j;
-
-                while ((i < leaf->mLast) && (mGeometry[i]->GetWorldCenter()[axis] < position)) ++ i;
-                while ((j > leaf->mFirst) && (position < mGeometry[j]->GetWorldCenter()[axis])) -- j;
-
-                // sorting finished
-                if (i >= j) break;
-
-                // swap entities
-                swap(mGeometry[i], mGeometry[j]);
-                        
-                ++ i;
-                -- j;
-        }
-
-        return j;
-}
-
-
-int Bvh::SortTrianglesSpatialMedian(BvhLeaf *leaf, 
-                                                                        int axis
-                                                                        )
-{
-        // spatial median
-        float m = leaf->mBox.Center()[axis];
-        return SortTriangles(leaf, axis, m);
-}
-
-
-BvhNode *Bvh::SubdivideLeaf(BvhLeaf *leaf, 
-                                                        int parentAxis
-                                                        )
-{
-        if (TerminationCriteriaMet(leaf))
-        {
-                if (leaf->CountPrimitives() == 0)
-                        cout << "error: leaf constructed:" << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
-                
-                return leaf;
-        }
-
-        //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;
-        float pos = -1.0f;
-        
-        // Spatial median subdivision
-        split = SortTrianglesSpatialMedian(leaf, axis);
-        pos = leaf->mBox.Center()[axis];
-        
-        //if ((split >= leaf->mLast) || (split < leaf->mFirst))
-        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 << " " << leaf->mLast << " " << split << endl;
-        }
-
-        // create two more nodes
-        mNumNodes += 2;
-        BvhInterior *parent = new BvhInterior(leaf->GetParent());
-        parent->mFirst = leaf->mFirst;
-        parent->mLast = leaf->mLast;
-        
-        parent->mAxis = axis;
-        parent->mBox = leaf->mBox;
-        parent->mDepth = leaf->mDepth;
-
-        BvhLeaf *front = new BvhLeaf(parent);
-
-        parent->mBack = leaf;
-        parent->mFront = front;
-                
-        // now assign the triangles to the subnodes
-        front->mFirst = split + 1;
-        front->mLast = leaf->mLast;
-        front->mDepth = leaf->mDepth + 1;
-
-        if (leaf->mFirst > leaf->mLast)
-                cerr << "erorr!!! " << leaf->CountPrimitives() << " " << leaf->mFirst << " " << leaf->mLast << " " << split << endl;
-
-        leaf->mLast = split;
-        leaf->mDepth = front->mDepth;
-        leaf->mParent = parent;
-        
-        front->mBox = SceneEntity::ComputeBoundingBox(mGeometry + front->mFirst, front->CountPrimitives());
-        leaf->mBox = SceneEntity::ComputeBoundingBox(mGeometry + leaf->mFirst, leaf->CountPrimitives());
-
-        // recursively continue subdivision
-        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis);
-        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis);
-        
-        return parent;
-}
-
-
-bool Bvh::TerminationCriteriaMet(BvhLeaf *leaf) const
-{
-        const bool criteriaMet = 
-                (leaf->mDepth > mMaxDepthForDynamicBranch) ||
-                (leaf->CountPrimitives() <= 1);
-
-        return criteriaMet;
-}
-
-
-void Bvh::UpdateDynamicBranch(BvhNode *node)
-{
-        if (node->IsLeaf())
-        {
-                int numEntities;
-                SceneEntity **entities = GetGeometry(node, numEntities);
-
-                node->mBox = SceneEntity::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
-        // a static branch (the old root), and a dynamic branch 
-        // we create a 'dynamic' leaf which basically is a container
-        // for all dynamic objects underneath
-
-        // the bounding boxes of the dynamic tree must be updated
-        // once each frame in order to be able to incorporate
-        // the movements of the objects within
-
-        cout << "creating dynamic bvh branch"  << endl;
-
-        DEL_PTR(mDynamicRoot);
-        -- mNumNodes;
-
-#if 1
-        BvhConstructor bvhConstructor(mGeometry, (int)mStaticGeometrySize, (int)mGeometrySize - 1);
-
-        int numNodes;
-        mDynamicRoot = bvhConstructor.Construct(numNodes);
-
-        mNumNodes += numNodes;
-
-#else
-
-        BvhLeaf *l = new BvhLeaf(mRoot);
-        mDynamicRoot = l;
-
-        l->mBox = SceneEntity::ComputeBoundingBox(mGeometry + mStaticGeometrySize, 
-                                                      (int)mDynamicGeometrySize);
-
-        l->mFirst = (int)mStaticGeometrySize;
-        l->mLast = (int)mGeometrySize - 1;
-        l->mArea = l->mBox.SurfaceArea();
-        
-        if (mDynamicGeometrySize)
-        {
-                mDynamicRoot = SubdivideLeaf(l, 0);
-        }
-#endif
-}
-
 
 bool Bvh::IntersectsNearPlane(BvhNode *node) const
@@ -1581 +1398 @@
   
 
-}
+
+
+////////////////////////
+//-- dynamic hierarchy stuff
+
+
+void Bvh::UpdateDynamicBranch(BvhNode *node)
+{
+        if (node->IsLeaf())
+        {
+                int numEntities;
+                SceneEntity **entities = GetGeometry(node, numEntities);
+
+                node->mBox = SceneEntity::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
+        // a static branch (the old root), and a dynamic branch 
+        // we create a 'dynamic' leaf which basically is a container
+        // for all dynamic objects underneath
+
+        // the bounding boxes of the dynamic tree must be updated
+        // once each frame in order to be able to incorporate
+        // the movements of the objects within
+
+        cout << "creating dynamic bvh branch"  << endl;
+
+        DEL_PTR(mDynamicRoot);
+        -- mNumNodes;
+
+        BvhConstructor bvhConstructor(mGeometry, (int)mStaticGeometrySize, (int)mGeometrySize - 1);
+
+        int numNodes;
+        mDynamicRoot = bvhConstructor.Construct(numNodes);
+
+        mNumNodes += numNodes;
+}
+
+}