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

Timestamp:

10/27/08 00:25:53 (16 years ago)

Author:

mattausch

Message:

fucked up depth order for some reason!!

File:

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

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

@@ -30 +30 @@
 
 using namespace std;
+
 
 namespace CHCDemoEngine
@@ -80 +81 @@
 static int sClipPlaneAABBVertexIndices[12];
 
-
 #define ALIGN_INDICES
+
 
 BvhNode::BvhNode(BvhNode *parent): 
@@ -154 +155 @@
 inline AxisAlignedBox3 ComputeBoundingBox(SceneEntity **entities, int numEntities)
 {
-        AxisAlignedBox3 box = entities[0]->GetWorldBoundingBox();
-
-        for (int i = 1; i < numEntities; ++ i)
-        {
-                box.Include(entities[i]->GetWorldBoundingBox());
+        AxisAlignedBox3 box;
+        
+        if (!numEntities)
+        {
+                // no box=> just initialize
+                box.Initialize();
+        }
+        else
+        {
+                box = entities[0]->GetWorldBoundingBox();
+
+                for (int i = 1; i < numEntities; ++ i)
+                {
+                        box.Include(entities[i]->GetWorldBoundingBox());
+                }
         }
 
@@ -171 +182 @@
 
 
-Bvh::Bvh(const SceneEntityContainer &entities)
+Bvh::Bvh(const SceneEntityContainer &staticEntities, 
+                 const SceneEntityContainer &dynamicEntities)
 {
         Init();
 
-        mGeometrySize = entities.size();
+        mGeometrySize = staticEntities.size() + dynamicEntities.size();
         mGeometry = new SceneEntity*[mGeometrySize];
 
-        SceneEntityContainer::const_iterator it, it_end = entities.end();
-
-        int i = 0;
-        for (it = entities.begin(); it != it_end; ++ it, ++ i)
-        {
-                mGeometry[i] = (*it);
+        mStaticGeometrySize = staticEntities.size();
+        mDynamicGeometrySize = dynamicEntities.size();
+
+        for (size_t i = 0; i < mStaticGeometrySize; ++ i)
+        {
+                mGeometry[i] = staticEntities[i];
+        }
+
+        for (size_t i = 0; i < mDynamicGeometrySize; ++ i)
+        {
+                mGeometry[mStaticGeometrySize + i] = dynamicEntities[i];
         }
 }
@@ -430 +447 @@
         sNear = cam->GetNear();
 
-        // rebuild dynamic part of the hierarchy
-        if (!mDynamicEntities.empty())
-        {
-                if (!mDynamicRoot)
-                        CreateDynamicBranch();
-                
+        // update dynamic part of the hierarchy
+        //if (!mDynamicEntities.empty())
+        if (mDynamicGeometrySize)
+        {
                 UpdateDynamicBranch(mDynamicRoot);
         }
@@ -647 +662 @@
         CollectNodes(mRoot, nodes);
 
-        // assign unique ids to all nodes of the hierarchy
+        // assign ids to all nodes of the "regular" hierarchy
         int i = 0;
         BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
@@ -788 +803 @@
         node->mTestNodesIdx = (int)mTestNodes.size();
 
-        // use the found nodes as nodes during the occlusion tests
+        // use the collected nodes as proxy for the occlusion tests
         for (cit = children.begin(); cit != children.end(); ++ cit)
         {
@@ -992 +1007 @@
 
 
-void Bvh::PostProcess() 
-{
-        // this function must be called once after hierarchy creation
-
-        // We initialize the virtual leaves
+void Bvh::ComputeMaxDepthForVirtualLeaves()
+{
+        // We initialize the maximal depth for virtual leaves
         // of this bvh, i.e., the nodes that are used as
         // leaves of the hierarchy during traversal.
@@ -1043 +1056 @@
 
 
+// this function must be called once after hierarchy creation
+void Bvh::PostProcess() 
+{
+        CreateRoot();
+
+        ComputeIds();
+        ComputeMaxDepthForVirtualLeaves();
+        // set virtual leaves for specified number of triangles
+        SetVirtualLeaves(INITIAL_TRIANGLES_PER_VIRTUAL_LEAVES);
+        /// for each node compute the number of leaves under this node
+        UpdateNumLeaves(mRoot);
+        // specify bounds for occlusion tests
+        RecomputeBounds();
+
+        // compute and print stats
+        ComputeBvhStats(mRoot, mBvhStats);
+        PrintBvhStats(mBvhStats);
+
+        if (mDynamicGeometrySize)
+        {
+                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::RenderBoundingBoxImmediate(const AxisAlignedBox3 &box)
 {
@@ -1219 +1269 @@
                 leaf->mIsVirtualLeaf = true;
                 leaf->mIsMaxDepthForVirtualLeaf = true;
-                cout << "leaf contructed:" << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
+                //cout << "leaf constructed:" << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
                 return leaf;
         }
@@ -1225 +1275 @@
         //const int axis = (parentAxis + 1) % 3;
         const int axis = leaf->mBox.MajorAxis();
-        
 
         const int scale = 20;
@@ -1248 +1297 @@
         mNumNodes += 2;
         BvhInterior *parent = new BvhInterior(leaf->GetParent());
-        BvhLeaf *front = new BvhLeaf(parent);
+        parent->mFirst = leaf->mFirst;
+        parent->mLast = leaf->mLast;
         
         parent->mAxis = axis;
@@ -1254 +1304 @@
         parent->mDepth = leaf->mDepth;
 
+        BvhLeaf *front = new BvhLeaf(parent);
+
         parent->mBack = leaf;
         parent->mFront = front;
-        //parent->mPosition = pos;
-        
+                
         // now assign the triangles to the subnodes
         front->mFirst = split + 1;
@@ -1267 +1318 @@
         leaf->mParent = parent;
         
-        // reset box
-        //leaf->mBox.Initialize();
-
         front->mBox = ComputeBoundingBox(mGeometry + front->mFirst, front->CountPrimitives());
         leaf->mBox = ComputeBoundingBox(mGeometry + leaf->mFirst, leaf->CountPrimitives());
@@ -1329 +1377 @@
 
         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());
+        mDynamicRoot = l;
+
+        l->mBox = ComputeBoundingBox(mGeometry + mStaticGeometrySize, (int)mDynamicGeometrySize);
+
+        l->mFirst = (int)mStaticGeometrySize;
         l->mLast = (int)mGeometrySize - 1;
         l->mArea = l->mBox.SurfaceArea();
@@ -1345 +1387 @@
         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();
+        if (mDynamicGeometrySize)
+                mDynamicRoot = SubdivideLeaf(l, 0);
 }
 
@@ -1394 +1398 @@
         // especially annoying is this problem when using the frustum 
         // fitting on the visible objects for shadow mapping
-        // but don't see how to solve this issue without using much costlier calculations
+        // but don't see how to solve this issue without using costly calculations
         
         // we stored the near plane distance => we can use it also here
@@ -1404 +1408 @@
 
 
-}
+void Bvh::CreateRoot()
+{
+        // create new root
+        mRoot = new BvhInterior(NULL);
+        
+        // the separation is a purely logical one
+        // the bounding boxes of the child nodes are 
+        // identical to those of the root node
+
+        mRoot->mBox = mStaticRoot->mBox;
+        mRoot->mBox.Include(mDynamicRoot->mBox);
+
+        mRoot->mArea = mRoot->mBox.SurfaceArea();
+
+        mRoot->mFirst = 0;
+        mRoot->mLast = (int)mGeometrySize - 1;
+
+        cout<<"f: " << mRoot->mFirst<< " l: " <<mRoot->mLast << endl;
+        // add static root on left subtree
+        mRoot->mFront = mStaticRoot;
+        mStaticRoot->mParent = mRoot;
+
+        // add dynamic root on left subtree
+        mRoot->mBack = mDynamicRoot;
+        mDynamicRoot->mParent = mRoot;
+}
+
+
+}