Changeset 1545 for GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.cpp

Timestamp:

09/29/06 22:42:25 (18 years ago)

Author:

mattausch

Message:

 

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.cpp (modified) (59 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.cpp

@@ -17 +17 @@
 namespace GtpVisibilityPreprocessor {
 
-
+//////////////
 //-- static members
 
@@ -168 +168 @@
 mRoot(NULL), 
 mUseAreaForPvs(false),
-mGenerateViewCells(true),
-mTimeStamp(1)
+mUsePredefinedViewCells(false),
+mTimeStamp(1),
+mViewCellsTree(NULL),
+ mOutOfBoundsCellPartOfTree(false)
 {
         Randomize(); // initialise random generator for heuristics
-
-        mOutOfBoundsCell = GetOrCreateOutOfBoundsCell();
-
+        mOutOfBoundsCell = new BspViewCell();
+
+        /////////
         //-- termination criteria for autopartition
+
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.maxDepth", mTermMaxDepth);
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.minPvs", mTermMinPvs);
@@ -184 +187 @@
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
 
+        
+        /////////
         //-- factors for bsp tree split plane heuristics
+
         Environment::GetSingleton()->GetFloatValue("BspTree.Factor.verticalSplits", mVerticalSplitsFactor);
         Environment::GetSingleton()->GetFloatValue("BspTree.Factor.largestPolyArea", mLargestPolyAreaFactor);
@@ -196 +202 @@
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.ct_div_ci", mCtDivCi);
 
+
+        ///////////
         //-- termination criteria for axis aligned split
+
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
         Environment::GetSingleton()->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio);
@@ -205 +214 @@
         Environment::GetSingleton()->GetIntValue("BspTree.Termination.AxisAligned.minObjects", 
                                                          mTermMinObjectsForAxisAligned);
+        
+        
+        //////////////
         //-- partition criteria
+
         Environment::GetSingleton()->GetIntValue("BspTree.maxPolyCandidates", mMaxPolyCandidates);
         Environment::GetSingleton()->GetIntValue("BspTree.maxRayCandidates", mMaxRayCandidates);
@@ -219 +232 @@
         mSubdivisionStats.open(subdivisionStatsLog);
 
+        /////////////////////7
+
+        Debug << "BSP options: " << endl;
     Debug << "BSP max depth: " << mTermMaxDepth << endl;
         Debug << "BSP min PVS: " << mTermMinPvs << endl;
@@ -401 +417 @@
 {
         DEL_PTR(mRoot);
-
-        // TODO must be deleted if used!!
-        //if (mGenerateViewCells) DEL_PTR(mOutOfBoundsCell);
-}
-
-BspViewCell *BspTree::GetOutOfBoundsCell()
-{
-        return mOutOfBoundsCell;
+        
+        if (!mOutOfBoundsCellPartOfTree)
+        {
+                // out of bounds cell not part of tree =>
+                // delete manually
+                DEL_PTR(mOutOfBoundsCell);
+        }
 }
 
@@ -418 +433 @@
 
 
-BspViewCell *BspTree::GetOrCreateOutOfBoundsCell()
-{
-        if (!mOutOfBoundsCell)
-        {
-                mOutOfBoundsCell = new BspViewCell();
-                mOutOfBoundsCell->SetId(-1);
-                mOutOfBoundsCell->SetValid(false);
-        }
-
-        return mOutOfBoundsCell;
+void BspTree::SetViewCellsTree(ViewCellsTree *viewCellsTree)
+{
+        mViewCellsTree = viewCellsTree;
 }
 
@@ -433 +441 @@
 void BspTree::InsertViewCell(ViewCellLeaf *viewCell)
 {
+        // don't generate new view cell, insert this view cell
+        mUsePredefinedViewCells = true;
         PolygonContainer *polys = new PolygonContainer();
 
-        // don't generate new view cell, insert this one
-        mGenerateViewCells = false;
         // extract polygons that guide the split process
         mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell);
-        mBox.Include(viewCell->GetBox()); // add to BSP aabb
+        mBbox.Include(viewCell->GetBox()); // add to BSP aabb
 
         InsertPolygons(polys);
@@ -459 +467 @@
                                                                  new BoundedRayContainer(), 
                                                                  0, 
-                                                                 mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                 mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                  new BspNodeGeometry()));
 
@@ -472 +480 @@
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
 
+                        ///////////////////
                         //-- filter view cell polygons down the tree until a leaf is reached
                         if (!tData.mPolygons->empty())
@@ -489 +498 @@
                                 
                                 // extract view cells associated with the split polygons
-                                ViewCellLeaf *frontViewCell = GetOrCreateOutOfBoundsCell();
-                                ViewCellLeaf *backViewCell = GetOrCreateOutOfBoundsCell();
+                                ViewCellLeaf *frontViewCell = mOutOfBoundsCell;
+                                ViewCellLeaf *backViewCell = mOutOfBoundsCell;
                         
                                 BspTraversalData frontData(interior->GetFront(), 
@@ -498 +507 @@
                                                                                    tData.mRays,
                                                                                    tData.mPvs,
-                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                                   mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                                    new BspNodeGeometry());
 
@@ -507 +516 @@
                                                                                   tData.mRays,
                                                                                   tData.mPvs,
-                                                                                   mUseAreaForPvs ? mBox.SurfaceArea() : mBox.GetVolume(), 
+                                                                                   mUseAreaForPvs ? mBbox.SurfaceArea() : mBbox.GetVolume(), 
                                                                                   new BspNodeGeometry());
 
-                                if (!mGenerateViewCells)
+                                if (mUsePredefinedViewCells)
                                 {
                                         ExtractViewCells(frontData,
@@ -558 +567 @@
                 }
                 else
+                {
                         DEL_PTR(poly);
+                }
         }
         return (int)mesh->mFaces.size();
@@ -572 +583 @@
   
         int polysSize = 0;
-
+        cout << "here55 " << mBbox << endl;
+        
+cout << "here99";
         for (int i = 0; i < limit; ++ i)
-        {
-                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
-                {
-                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
-                }
-        }
-
+        {cout << "q";
+        Mesh *mesh = viewCells[i]->GetMesh();
+                if (mesh) 
+                {cout << "w";
+                        // copy the mesh into polygons and add to BSP tree aabb
+                        mBbox.Include(viewCells[i]->GetBox()); 
+                        polysSize += AddMeshToPolygons(mesh, polys, viewCells[i]);
+                }
+        }
+cout << "here155 " << mBbox << endl;
         return polysSize;
 }
@@ -593 +608 @@
         int limit = (maxObjects > 0) ? 
                 Min((int)objects.size(), maxObjects) : (int)objects.size();
-  
+  cout << "here88";
         for (int i = 0; i < limit; ++i)
-        {
+        {cout << "e";
                 Intersectable *object = objects[i];
-
                 Mesh *mesh = NULL;
 
@@ -616 +630 @@
                                 mesh = new Mesh();
                                 mi->GetTransformedMesh(*mesh);
-                                
                                 break;
                         }
@@ -624 +637 @@
                 }
                 
-        if (mesh) // copy the mesh data to polygons
-                {
-                        if (addToBbox)
-                                mBox.Include(object->GetBox()); // add to BSP tree aabb
-                                
-                        AddMeshToPolygons(mesh, polys, mOutOfBoundsCell);
-
-                        // cleanup
-                        if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
-                                DEL_PTR(mesh);
+        if (!mesh) continue;
+                // copy the mesh data to polygons
+                if (addToBbox)
+                {cout << "b";
+                        mBbox.Include(object->GetBox()); // add to BSP tree aabb
+                }
+
+                AddMeshToPolygons(mesh, polys, mOutOfBoundsCell);
+
+                // cleanup
+                if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
+                {
+                        DEL_PTR(mesh);
                 }       
         }
@@ -640 +656 @@
 }
 
-
+        
 void BspTree::Construct(const ViewCellContainer &viewCells)
 {
+        cout << "here5500000000" << endl;
+        // construct hierarchy over the given view cells
+        mUsePredefinedViewCells = true;
+
         mStat.nodes = 1;
-        mBox.Initialize();      // initialise bsp tree bounding box
+        mBbox.Initialize(); // initialise bsp tree bounding box
 
         // copy view cell meshes into one big polygon soup
@@ -650 +670 @@
         mStat.polys = AddToPolygonSoup(viewCells, *polys);
 
-        // view cells are given
-        mGenerateViewCells = false;
+        Exporter *expo = Exporter::GetExporter("dummy2.wrl");
+        expo->ExportPolygons(*polys);
+        delete expo;
         // construct tree from the view cell polygons
         Construct(polys, new BoundedRayContainer());
@@ -659 +680 @@
 void BspTree::Construct(const ObjectContainer &objects)
 {
+        // generate new view cells for this type
+        mUsePredefinedViewCells = false;
+
         mStat.nodes = 1;
-        mBox.Initialize();      // initialise bsp tree bounding box
+        mBbox.Initialize();     // initialise bsp tree bounding box
         
         PolygonContainer *polys = new PolygonContainer();
 
-        mGenerateViewCells = true;
         // copy mesh instance polygons into one big polygon soup
         mStat.polys = AddToPolygonSoup(objects, *polys);
@@ -677 +700 @@
         // preprocess: throw out polygons coincident to the view space box (not needed)
         PolygonContainer boxPolys;
-        mBox.ExtractPolys(boxPolys);
+        mBbox.ExtractPolys(boxPolys);
         vector<Plane3> boxPlanes;
 
@@ -722 +745 @@
 
 
-
 void BspTree::Construct(const RayContainer &sampleRays,
                                                 AxisAlignedBox3 *forcedBoundingBox)
 {
+        // generate new view cells for this contruction type
+        mUsePredefinedViewCells = false;
+
     mStat.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
-        
+
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
+        {
+                mBbox = *forcedBoundingBox;
+        }
+        else
+        {
+                mBbox.Initialize(); // initialise BSP tree bounding box 
+        }
 
         PolygonContainer *polys = new PolygonContainer();
@@ -737 +767 @@
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
 
-        // generate view cells
-        mGenerateViewCells = true;
-
         long startTime = GetTime();
-
         Debug << "**** Extracting polygons from rays ****\n";
 
         std::map<Face *, Polygon3 *> facePolyMap;
 
-        //-- extract polygons intersected by the rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
+                //////////////
+                //-- extract polygons intersected by the rays
                 Ray *ray = *rit;
         
@@ -803 +830 @@
         // compute bounding box
         if (!forcedBoundingBox)
-                mBox.Include(*polys);
-
+        {
+                mBbox.Include(*polys);
+        }
+
+        ////////////
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -812 +842 @@
 
                 float minT, maxT;
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBbox.GetRaySegment(*ray, minT, maxT))
                         rays->push_back(new BoundedRay(ray, minT, maxT));
         }
@@ -833 +863 @@
                                                 AxisAlignedBox3 *forcedBoundingBox)
 {
+        // generate new view cells for this construction type
+        mUsePredefinedViewCells = false;
+
     mStat.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
+        mBbox.Initialize();     // initialise BSP tree bounding box
         
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
+        {
+                mBbox = *forcedBoundingBox;
+        }
 
         BoundedRayContainer *rays = new BoundedRayContainer();
         PolygonContainer *polys = new PolygonContainer();
         
-        mGenerateViewCells = true;
-
         // copy mesh instance polygons into one big polygon soup
         mStat.polys = AddToPolygonSoup(objects, *polys, 0, !forcedBoundingBox);
 
-
+        ///////
+        //-- store rays
         RayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        //-- store rays
+        
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
@@ -857 +890 @@
 
                 float minT, maxT;
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBbox.GetRaySegment(*ray, minT, maxT))
                         rays->push_back(new BoundedRay(ray, minT, maxT));
         }
@@ -870 +903 @@
 {
         BspTraversalStack tStack;
-
         mRoot = new BspLeaf();
 
@@ -880 +912 @@
                                                    polys, 
                                                    0, 
-                                                   GetOrCreateOutOfBoundsCell(), 
+                                                   mOutOfBoundsCell, 
                                                    rays, 
                                                    ComputePvsSize(*rays), 
@@ -886 +918 @@
                                                    geom);
 
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
+        mTotalCost = tData.mPvs * tData.mProbability / mBbox.GetVolume();
         mTotalPvsSize = tData.mPvs;
         
@@ -950 +982 @@
 BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
 {
-        //-- terminate traversal  
+        ////////
+        //-- terminate traversal
+
         if (TerminationCriteriaMet(tData))              
         {
@@ -957 +991 @@
                 BspViewCell *viewCell;
 
-                // generate new view cell for each leaf
-                if (mGenerateViewCells)
-                {
+                if (!mUsePredefinedViewCells)
+                {       // generate new view cell for each leaf
                         viewCell = new BspViewCell();
                 }
                 else
                 {
-                        // add view cell to leaf
+                        // add predefined view cell to leaf
                         viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
+                
+                        /// out of bounds cell can be handled as any other cell
+                        if (viewCell == mOutOfBoundsCell)
+                                mOutOfBoundsCellPartOfTree = true;
                 }
 
@@ -979 +1016 @@
                         viewCell->SetVolume(probability);
 
-                //-- add pvs
+                
+                ///////////
+                //-- add pvs contribution of rays
+
                 if (viewCell != mOutOfBoundsCell)
                 {
@@ -989 +1029 @@
                 }
 
-                if (1)
-                        EvaluateLeafStats(tData);
-                
+                if (1)EvaluateLeafStats(tData);
+                
+
+                ////////
                 //-- clean up
-                
+
                 // discard polygons
                 CLEAR_CONTAINER(*tData.mPolygons);
@@ -1006 +1047 @@
         }
 
+        ///////////
         //-- continue subdivision
+
         PolygonContainer coincident;
         
@@ -1019 +1062 @@
                 SubdivideNode(tData, tFrontData, tBackData, coincident);
 
-
         if (1)
         {
@@ -1028 +1070 @@
                 float cBack = (float)tBackData.mPvs * tBackData.mProbability;
 
-                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
+                float costDecr = (cFront + cBack - cData) / mBbox.GetVolume();
                 
                 mTotalCost += costDecr;
@@ -1040 +1082 @@
         }
 
-        // extract view cells from coincident polygons according to plane normal
-    // only if front or back polygons are empty
-        if (!mGenerateViewCells)
+        // extract view cells from coincident polygons 
+        // with respect to the orientation of their normal
+    // note: if front or back polygons are empty, 
+        // we get the valid in - out classification for the view cell
+
+        if (mUsePredefinedViewCells)
         {
                 ExtractViewCells(tFrontData,
@@ -1057 +1102 @@
         tStack.push(tBackData);
 
-        // cleanup
+        ////////
+        //-- cleanup
+
         DEL_PTR(tData.mNode);
-
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
@@ -1080 +1126 @@
                 coincident.begin(), it_end = coincident.end();
 
+        //////////
         //-- find first view cells in front and back leafs
+
         for (; !(foundFront && foundBack) && (it != it_end); ++ it)
         {
@@ -1108 +1156 @@
         // select subdivision plane
         BspInterior *interior = new BspInterior(SelectPlane(leaf, tData)); 
-        
         
 #ifdef _DEBUG
@@ -1135 +1182 @@
                                                                            *backData.mGeometry, 
                                                                            interior->mPlane,
-                                                                           mBox,
+                                                                           mBbox,
                                                                            //0.000000000001);
                                                                            mEpsilon);
@@ -1274 +1321 @@
         const float ratio = newCost / oldCost;
 
-
-#if 0
+#ifdef _DEBUG
   Debug << "====================" << endl;
   Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
@@ -1430 +1476 @@
         return Plane3(pt[0], pt[1], pt[2]);
 }
+
 
 Plane3 BspTree::ChooseCandidatePlane3(const BoundedRayContainer &rays) const
@@ -1697 +1744 @@
                                                            geomBack, 
                                                            candidatePlane,
-                                                           mBox,
+                                                           mBbox,
                                                            mEpsilon);
 
@@ -1856 +1903 @@
         if (mSplitPlaneStrategy & VERTICAL_AXIS)
         {
-                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
+                Vector3 tinyAxis(0,0,0); tinyAxis[mBbox.Size().TinyAxis()] = 1.0f;
                 // we put a penalty on the dot product between the "tiny" vertical axis
                 // and the split plane axis
@@ -1915 +1962 @@
 AxisAlignedBox3 BspTree::GetBoundingBox() const
 {
-        return mBox;
+        return mBbox;
 }
 
@@ -1972 +2019 @@
         float maxt, mint;
 
-        if (!mBox.GetRaySegment(ray, mint, maxt))
+        if (!mBbox.GetRaySegment(ray, mint, maxt))
                 return 0;
 
@@ -2194 +2241 @@
                 }
         }
+
+        // also add out of bounds cell
+        if (0 && !mOutOfBoundsCell->Mailed())
+        {
+                mOutOfBoundsCell->Mail();
+                viewCells.push_back(mOutOfBoundsCell);
+        }
+
+        cout << "here555 " << viewCells.size() << endl;
+
 }
 
@@ -2247 +2304 @@
                 case Ray::COINCIDENT: // TODO: should really discard ray?
                         frontRays.push_back(bRay);
-                        //DEL_PTR(bRay);
                         break;
                 case Ray::BACK:
@@ -2322 +2378 @@
                                                                 BspNodeGeometry &vcGeom) const
 {
+        // if false, cannot construct geometry for interior leaf
+        if (!mViewCellsTree)
+                return;
+
         ViewCellContainer leaves;
         mViewCellsTree->CollectLeaves(vc, leaves);
@@ -2364 +2424 @@
 
                 for (int j = 0; j < 4; ++ j)
-                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
+                        vertices.push_back(mBbox.GetFace(i).mVertices[j]);
 
                 Polygon3 *poly = new Polygon3(vertices);
@@ -2533 +2593 @@
                                                                 *bGeom,
                                                                 interior->GetPlane(),
-                                                                mBox,
+                                                                mBbox,
                                                                 //0.0000001f);
                                                                 mEpsilon);
@@ -2807 +2867 @@
         Debug << "leaves in queue: " << numLeaves << endl;
 
-
+#if 0
+        //////////
         //-- collect the leaves which haven't been found by ray casting
-#if 0
         cout << "finding additional merge candidates using geometry" << endl;
         vector<BspLeaf *> leaves;
@@ -2822 +2882 @@
 
 
-
 /***************************************************************/
 /*              BspNodeGeometry Implementation                 */
@@ -3050 +3109 @@
 bool BspNodeGeometry::Valid() const
 {
+        // geometry is degenerated
         if (mPolys.size() < 4)
                 return false;
@@ -3294 +3354 @@
                 int id = -1;
                 if (leaf->GetViewCell() != mOutOfBoundsCell)
+                {
                         id = leaf->GetViewCell()->GetId();
+                }
 
                 stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;