Changeset 235

Timestamp:

08/12/05 01:17:56 (19 years ago)

Author:

mattausch

Message:

added some bsp stuff

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• include/Polygon3.h (added)
• include/ViewCellBsp.h (modified) (1 diff)
• scripts/Preprocessor.vcproj (modified) (4 diffs)
• scripts/default.env (added)
• src/Containers.h (modified) (3 diffs)
• src/Environment.cpp (modified) (1 diff)
• src/Polygon3.cpp (added)
• src/Polygon3.h (added)
• src/Preprocessor.cpp (modified) (4 diffs)
• src/Preprocessor.h (modified) (1 diff)
• src/ViewCell.cpp (added)
• src/ViewCell.h (modified) (2 diffs)
• src/ViewCellBsp.cpp (modified) (15 diffs)
• src/ViewCellBsp.h (modified) (13 diffs)
• src/common.h (modified) (1 diff)
• src/main.cpp (modified) (3 diffs)

trunk/VUT/GtpVisibilityPreprocessor/include/ViewCellBsp.h

@@ -69 +69 @@
   {
   public:
-          /** Constructor takes a pointer to the cell corresponding to the whole
-          viewspace */
-          BspTree(ViewCell *cell);
+          /** Default constructor.
+          */
+          BspTree();
         
   protected:
+
           /// Pointer to the root of the tree
           BspNode *mRoot;

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -63 +63 @@
                                 Name="VCCLCompilerTool"
                                 AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;"$(QTDIR)\include";"$(QTDIR)\include\Qt";..\include"
-                                PreprocessorDefinitions="WIN32;NDEBUG;_LIB;DEST_BSP_VIEWCELLS"
+                                PreprocessorDefinitions="WIN32;NDEBUG;_LIB;TEST_BSP_VIEWCELLS"
                                 RuntimeLibrary="2"
                                 RuntimeTypeInfo="TRUE"
@@ -199 +199 @@
                         </File>
                         <File
+                                RelativePath="..\src\Polygon3.cpp">
+                        </File>
+                        <File
+                                RelativePath="..\src\Polygon3.h">
+                        </File>
+                        <File
                                 RelativePath="..\src\Preprocessor.cpp">
                         </File>
@@ -251 +257 @@
                         <File
                                 RelativePath="..\src\Vector3.h">
+                        </File>
+                        <File
+                                RelativePath="..\src\ViewCell.cpp">
                         </File>
                         <File
@@ -303 +312 @@
                         </File>
                         <File
+                                RelativePath="..\include\Polygon3.h">
+                        </File>
+                        <File
                                 RelativePath="..\include\Preprocessor.h">
                         </File>

trunk/VUT/GtpVisibilityPreprocessor/src/Containers.h

@@ -3 +3 @@
 
 #include <vector>
+#include <queue>
+
 using namespace std;
 
@@ -9 +11 @@
 class SceneGraphNode;
 class Intersectable;
+class Polygon3;
+
 
 /** Container for Mesh pointers primarily for the use within the kDTree and
@@ -18 +22 @@
 
 typedef vector<ViewCell *> ViewCellContainer;
+
+/** Container for ViewCell pointers primarily for the use within the kDTree and
+    BSP hierarchies */
+//typedef vector<MeshInstance *> MeshInstanceContainer;
+
 /** Container for HierarchyNodes pointers primarily for the use within the kDTree and
     BSP hierarchies */
 
 typedef vector<HierarchyNode *> NodeContainer;
+
+/** Queue storing a soup of polygons used during BSP tree construction
+*/
+typedef queue<Polygon3 *> PolygonQueue;
+
+
 
 typedef vector<SceneGraphNode *> SceneGraphNodeContainer;

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1151 +1151 @@
                  "10");
 
-  
+  RegisterOption("BspTree.Termination.maxPolygons",
+                 optInt,
+                 "-bsp_term_max_polygons=",
+                 "5");
+  
+  RegisterOption("BspTree.Termination.maxDepth",
+                 optInt,
+                 "-bsp_term_max_depth=",
+                 "100");
+
+  RegisterOption("BspTree.splitPlaneStrategy",
+                optString,
+                "-bsp_split_method=",
+                "leastSplits");
+
+  RegisterOption("BspTree.constructionMethod",
+          optString,
+          "-bsp_construction_method=",
+          "viewCells");
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -4 +4 @@
 #include "X3dParser.h"
 #include "Preprocessor.h"
-
-
+#include "ViewCell.h"
+#include "Environment.h"
 
   
@@ -18 +18 @@
 Preprocessor::GenerateViewcells()
 {
-        ObjectContainer objects;
-        mSceneGraph->CollectObjects(&objects);
-        //mBspTree = new BspTree(objects);
-  
-        return true;
+        return BuildBspTree();
 }
 
@@ -66 +62 @@
 Preprocessor::BuildBspTree()
 {
-  
-  return true;
+        ObjectContainer objects;
+        mSceneGraph->CollectObjects(&objects);
+
+        mBspTree = new BspTree();
+
+        char constructionMethodStr[64];
+
+        environment->GetStringValue("BspTree.constructionMethod",
+                           constructionMethodStr);
+
+        int constructionMethod = BspTree::VIEWCELLS;
+
+        if (strcmp(constructionMethodStr, "viewCells") == 0)
+                constructionMethod = BspTree::VIEWCELLS;
+        else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
+                constructionMethod = BspTree::SCENE_GEOMETRY;
+        else 
+        {
+                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
+                exit(1);
+    }
+
+        Debug << constructionMethodStr << endl;
+
+        switch (constructionMethod)
+        {
+        case BspTree::VIEWCELLS:
+                mViewcells.clear();
+                // derive viewcells from the scene objects
+                ViewCell::DeriveViewCells(objects, mViewcells, 1000);
+                mBspTree->Construct(mViewcells);
+                break;
+        case BspTree::SCENE_GEOMETRY:
+                mBspTree->Construct(objects);
+                break;
+        default:
+                break;
+        }
+        return true;
 }
 
@@ -81 +114 @@
 Preprocessor::BspTreeStatistics(ostream &s)
 {
-//  s<<mBspTree->GetStatistics();
+        s << mBspTree->GetStatistics();
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h

@@ -98 +98 @@
   
   BspTree * mBspTree;
-  
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -3 +3 @@
 
 #include "Intersectable.h"
+#include "Containers.h"
 
 class Mesh;
@@ -19 +20 @@
                 the viewcell.
         */
-        ViewCell(Mesh *mesh): mMesh(mesh), mPvs(NULL) {}
+        ViewCell(Mesh *mesh);
 
         /** Returns pointer to the mesh which represents the shape of the viewcell.
         */
-        Mesh *GetMesh() {return mMesh;}
+        Mesh *GetMesh();
 
         /** Returns pointer to PVS. 
                 @returns PVS, i.e., the visible BSP tree nodes.
         */
-        BspPvs *GetPVS() {return mPvs;}
+        BspPvs *GetPVS();
 
-        AxisAlignedBox3 GetBox()  {return mMesh->mBox;}
+        AxisAlignedBox3 GetBox();
   
-        int CastRay(Ray &ray) {return 0;}
+        int CastRay(Ray &ray);
   
-        bool IsConvex() {return mMesh->mIsConvex;}
-        bool IsWatertight() {return mMesh->mIsWatertight;}
-        float IntersectionComplexity() {return mMesh->mFaces.size();}
+        bool IsConvex();
+        bool IsWatertight();
+        float IntersectionComplexity();
 
-        int Type() const { return VIEWCELL; }
+        int Type() const;
 
-        void GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) {point = Vector3(0,0,0);};
+        void GetRandomSurfacePoint(Vector3 &point, Vector3 &normal);
 
+        /** Derives viewcells from object container.
+                @param objects the intersectables the viewcells are derived from
+                @param viewCells the viewcells are returned in this container
+                @param if >0, indicates the maximim number of viewcells that will be created
+        */
+        static void DeriveViewCells(const ObjectContainer &objects, 
+                                                                ViewCellContainer &viewCells, 
+                                                                const int max);
 protected:
 
+        /// the mesh defining the geometry of this viewcell
         Mesh *mMesh;
         /// the PVS (i.e., the visible bsp tree nodes)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -2 +2 @@
 #include "ViewCellBsp.h"
 #include "Mesh.h"
-
+#include "common.h"
 #include "ViewCell.h"
 #include <stack>
-
-#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}
+#include "Environment.h"
+#include "Polygon3.h"
+
+int BspTree::sTermMaxPolygons = 10;
+int BspTree::sTermMaxDepth = 20;
 
 //namespace GtpVisibilityPreprocessor {
+
+
 /****************************************************************/
 /*                  class BspNode implementation                */
 /****************************************************************/
+
+BspNode::BspNode(): mParent(NULL)
+{}
+
+BspNode::BspNode(BspInterior *parent): mParent(parent)
+{}
+
+
 bool BspNode::IsRoot() const 
 {
@@ -21 +34 @@
         return mParent; 
 }
+
+void BspNode::SetParent(BspInterior *parent)
+{
+        mParent = parent;
+}
+
 /****************************************************************/
 /*              class BspInterior implementation                */
@@ -67 +86 @@
 }
 
-void BspInterior::SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys)
+void BspInterior::SplitPolygons(PolygonQueue *polys, 
+                                                                PolygonQueue *frontPolys, 
+                                                                PolygonQueue *backPolys, 
+                                                                int &splits)
 {
         while (!polys->empty())
         {
-                Polygon *poly = polys->front();
+                Polygon3 *poly = polys->front();
 
                 polys->pop();
@@ -77 +99 @@
                 int result = poly->Side(&mPlane);
 
-                Polygon *front_piece = NULL;
-                Polygon *back_piece = NULL;
+                Polygon3 *front_piece = NULL;
+                Polygon3 *back_piece = NULL;
 
                 switch (result)
                 {
-                        case Polygon::COINCIDENT:
+                        case Polygon3::COINCIDENT:
                                 break;
-                        case Polygon::FRONT_SIDE:
+                        case Polygon3::FRONT_SIDE:
                                 frontPolys->push(poly);
                                 break;
-                        case Polygon::BACK_SIDE:
+                        case Polygon3::BACK_SIDE:
                                 backPolys->push(poly);
                                 break;
-                        case Polygon::SPLIT:
-                                front_piece = new Polygon();
-                                back_piece = new Polygon();
+                        case Polygon3::SPLIT:
+                                front_piece = new Polygon3();
+                                back_piece = new Polygon3();
 
                                 //-- split polygon
-                poly->Split(&mPlane, front_piece, back_piece);
-
+                                poly->Split(&mPlane, front_piece, back_piece, splits);
+                        
                                 backPolys->push(back_piece);
                                 frontPolys->push(front_piece);
@@ -108 +130 @@
         }
         // delete old polygons
-        Polygon::DeletePolygons(polys);
+//      Polygon3::DeletePolygons(polys);
 }
 
@@ -129 +151 @@
 }
 
-/****************************************************************/
-/*                  class Polygon implementation                */
-/****************************************************************/
-
-Polygon::Polygon()
-{}
-
-Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
-{}
-
-Polygon::Polygon(Face *face, Mesh *parent)
-{
-        VertexIndexContainer::const_iterator it;
-
-        for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
-        {
-                mVertices.push_back(parent->mVertices[*it]);
-        }
-}
-
-Plane3 Polygon::GetSupportingPlane()
-{
-        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
-}
-
-void Polygon::DeletePolygons(PolygonQueue *polys)
-{
-        // don't need to store polygon information = delete polygons
-        while(!polys->empty())
-        {
-                Polygon *poly = polys->front();
-                polys->pop();
-                DEL_PTR(poly);
-        }
-}
-
-void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
-{
-        Vector3 ptA = mVertices[mVertices.size() - 1];;
-        
-        int sideA = partition->Side(ptA);
-        
-        VertexContainer::const_iterator it;
-
-        // find line - plane intersections
-        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-        {
-                Vector3 ptB = (*it);
-                int sideB = partition->Side(ptB);
-
-                // vertices on different sides => split
-                if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
-                {
-                        Vector3 v = ptB - ptA; // line from A to B
-                        float dv = DotProd(partition->mNormal, v);
-                        float t = 0;
-                        
-                        if (dv)
-                        {
-                                t = - partition->Distance(ptA) / dv;
-                        }
-                }
-                if (sideB >= 0)
-                {
-                        back->mVertices.push_back(ptB);
-                }
-                else if (sideB <= 0)
-                {
-                        front->mVertices.push_back(ptB);
-                }
-
-                ptA = ptB;
-                sideA = sideB;
-        }
-}
-
-int Polygon::Side(Plane3 *plane)
-{
-        VertexContainer::const_iterator it;
-
-        bool onFrontSide = false;
-        bool onBackSide = false;
-
-        // find line - plane intersections
-        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
-        {
-                int side = plane->Side(*it);
-                
-                if (side > 0)
-                {
-                        onFrontSide = true;
-                }
-                else if (side < 0)
-                {
-                        onBackSide = true;
-                }
-
-                if (onFrontSide && onBackSide) // splits
-                        return SPLIT;
-        }
-
-        if (onBackSide)
-        {
-                return BACK_SIDE;
-        }
-        else if (onFrontSide)
-        {
-                return FRONT_SIDE;
-        }
-
-        return COINCIDENT;
-}
 
 /****************************************************************/
@@ -246 +156 @@
 /****************************************************************/
 
-BspTree::BspTree(const ViewCellContainer &viewCells): 
-mMaxPolys(0), mMaxDepth(999999), mRoot(NULL) // null => until we stripped all polygons
-{
-        //mRootCell = cell;
-        Subdivide(viewCells);
-}
-
-BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
-mMaxPolys(maxPolys), mMaxDepth(maxDepth)
+BspTree::BspTree(): mTermMaxPolygons(0), mTermMaxDepth(0)
 {
         mRoot = new BspLeaf();
-
-        Subdivide(objects);
 }
  
+const BspTreeStatistics &BspTree::GetStatistics() const 
+{
+        return mStat;
+}
+
+void BspTreeStatistics::Print(ostream &app) const
+{
+        app << "===== BspTree statistics ===============\n";
+
+        app << "#N_RAYS Number of rays )\n"
+                << rays <<endl;
+        app << "#N_DOMAINS  ( Number of query domains )\n"
+                << queryDomains <<endl;
+
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+        app << "#N_SPLITS ( Number of splits)\n" << splits << "\n";
+
+        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+        rayRefs << "\n";
+
+        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+        rayRefs/(double)rays << "\n";
+
+        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+        rayRefs/(double)Leaves() << "\n";
+
+        app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
+        maxObjectRefs << "\n";
+
+        app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
+        rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
+
+        app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
+        objectRefs/(double)Leaves() << "\n";
+
+        //  app << setprecision(4);
+
+        app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
+        zeroQueryNodes*100/(double)Leaves()<<endl;
+
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
+        maxDepthNodes*100/(double)Leaves()<<endl;
+
+        app << "#N_PMAXDEPTH ( Maximal reached depth )\n"<<
+        maxDepth*100/(double)Leaves()<<endl;
+
+        app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
+        addedRayRefs<<endl;
+
+        app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
+        removedRayRefs<<endl;
+
+        //  app << setprecision(4);
+
+        //  app << "#N_CTIME  ( Construction time [s] )\n"
+        //      << Time() << " \n";
+
+        app << "===== END OF BspTree statistics ==========\n";
+}
+
 BspTree::~BspTree()
 {
@@ -296 +259 @@
         PolygonQueue polys;
         // copy polygon information to guide the split process
-        CopyMesh2Polygon(viewCell->GetMesh(), polys);
+        CopyMesh2Polygons(viewCell->GetMesh(), polys);
 
         tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
@@ -315 +278 @@
                         PolygonQueue *backPolys = new PolygonQueue();
 
-                        interior->SplitPolygons(tData.mPolys, frontPolys, backPolys);
+                        int splits = 0;
+                        interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits);
+                        mStat.splits += splits;
 
                         // push the children on the stack
                         if (frontPolys->size() > 0) // if polygons on this side of bsp tree
-                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1));
+                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), 
+                                                        frontPolys, tData.mDepth + 1));
                         else
                                 delete frontPolys;
 
                         if (backPolys > 0) // if polygons on this side of bsp tree
-                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1));
+                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), 
+                                                        backPolys, tData.mDepth + 1));
                         else
                                 delete backPolys;
                 }
-                else // reached leaf and must split
+                else // reached leaf => subdivide
                 {
-                        BuildTree(tStack, tData, NULL);
+                        Subdivide(tStack, tData, NULL);
                 }
         }
 }
 
-void BspTree::Subdivide(const ViewCellContainer &viewCells)
-{
-}
-
-void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
+void BspTree::Construct(const ViewCellContainer &viewCells)
+{
+        // for this type of construction we split until no polygons is left
+        mTermMaxPolygons = 0;
+        mTermMaxDepth = sTermMaxDepth;
+
+        mStat.nodes = 1;
+
+        // insert all viewcells
+        ViewCellContainer::const_iterator it;
+
+        for (it = viewCells.begin(); it != viewCells.end(); ++ it)
+        {
+                InsertViewCell(*it);
+        }
+}
+
+void BspTree::CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys)
 {
         FaceContainer::const_iterator fi;
+        
         // copy the face data to polygons
         for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
         {
-                Polygon *poly = new Polygon((*fi), mesh);
+                Polygon3 *poly = new Polygon3((*fi), mesh);
                 polys.push(poly);
         }
@@ -357 +338 @@
         {
                 Intersectable *object = *it;
-
-                // extract the mesh instances
-                if (object->Type() == Intersectable::MESH_INSTANCE)
+                Mesh *mesh = NULL;
+
+                // extract the meshes
+                switch (object->Type())
                 {
-                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
-
-                        Mesh *mesh = inst->GetMesh();
-
+                case Intersectable::MESH_INSTANCE:
+                        
+                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
+                        
+                case Intersectable::VIEWCELL:
+                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
                         // copy the mesh data to polygons
-                        CopyMesh2Polygon(mesh, polys);
+                        CopyMesh2Polygons(mesh, polys);
+                        break;
+                default:
+                        break;
                 }
         }
-}
-
-void BspTree::Subdivide(const ObjectContainer &objects)
-{
+        Debug << "number of polygons: " << polys.size() << endl;
+}
+
+void BspTree::Construct(const ObjectContainer &objects)
+{
+        mTermMaxPolygons = sTermMaxPolygons;
+        mTermMaxDepth = sTermMaxDepth;
+
+        mStat.nodes = 1;
+
         std::stack<BspTraversalData> tStack;
         PolygonQueue *polys = new PolygonQueue();
@@ -385 +378 @@
         {
             tData = tStack.top();
-
             tStack.pop();
     
-                BuildTree(tStack, tData);
-        }
-}
-
-void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell)
+                Subdivide(tStack, tData);
+        }
+}
+
+void BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell)
 {
         PolygonQueue *backPolys = new PolygonQueue();
         PolygonQueue *frontPolys = new PolygonQueue();
 
-        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(currentData.mNode),
-                                                                  currentData.mParent,
-                                                                  currentData.mPolys,
-                                                                  currentData.mDepth,
+        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
+                                                                  tData.mParent,
+                                                                  tData.mPolygons,
+                                                                  tData.mDepth,
                                                                   viewCell,
                                                                   backPolys,
@@ -410 +402 @@
 
                 // push the children on the stack (there are always two children)
-                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1));
-                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1));
-        }
+                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, tData.mDepth + 1));
+                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, tData.mDepth + 1));
+        }
+        else
+                EvaluateLeafStats(tData);
 }
 
@@ -429 +423 @@
                                                                 PolygonQueue *backPolys)
 {
-        // terminate traversal if no more faces in mesh
-        if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
-        {
-                // don't need to store polygon information = delete polygons
-                Polygon::DeletePolygons(polys);
-                
+        // terminate traversal
+        if ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth))
+        {
+                // don't need to store polygon information => delete polygons
+                Polygon3::DeletePolygons(polys);
+                // Debug << polys->size() << ", " << depth << endl;             
                 return leaf;
         }
+
+         mStat.nodes += 2;
 
         // add the new nodes to the tree + select subdivision plane
@@ -442 +438 @@
 
         // split polygon according to current plane
-        node->SplitPolygons(polys, frontPolys, backPolys);
-        
+        int splits = 0;
+        node->SplitPolygons(polys, frontPolys, backPolys, splits);
+        mStat.splits += splits;
+
         // two new leaves
         BspLeaf *back = new BspLeaf();
@@ -461 +459 @@
         return node;
 }
+
+void BspTree::ParseEnvironment()
+{
+        environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
+        environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
+}
+
+void BspTree::EvaluateLeafStats(const BspTraversalData &data)
+{
+
+  // the node became a leaf -> evaluate stats for leafs
+  BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
+
+  if (data.mDepth > mTermMaxDepth)
+    ++ mStat.maxDepthNodes; 
+
+  // record maximal depth
+  if (data.mDepth > mStat.maxDepth)
+          mStat.maxDepth = data.mDepth;
+}
 //} // GtpVisibilityPreprocessor

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -14 +14 @@
 class BspTree;  
 class BspInterior;
-class Polygon;
-
-typedef std::queue<Polygon *> PolygonQueue;
+class Polygon3;
+
+/** Queue storing a soup of polygons used during BSP tree construction
+*/
+typedef std::queue<Polygon3 *> PolygonQueue;
 
 class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
@@ -23 +25 @@
   // total number of nodes
   int nodes;
+  // number of splits
+  int splits;
   // totals number of rays
   int rays;
+  // maximal reached depth
+  int maxDepth;
   // total number of query domains
   int queryDomains;
@@ -47 +53 @@
   BspTreeStatistics() 
   {
-    Reset();
+          Reset();
   }
 
@@ -57 +63 @@
   {
           nodes = 0;
-
+          splits = 0;
           rays = queryDomains = 0;
           rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
@@ -85 +91 @@
 
 public:
+        BspNode();
+        BspNode(BspInterior *parent);
+
         /** Determines whether this node is a leaf or not
         @return true if leaf
@@ -98 +107 @@
         */
         BspInterior *GetParent();
-        
+        /** Sets parent node.
+        */
+        void SetParent(BspInterior *parent);
+
 protected:
 
@@ -129 +141 @@
                 @param frontPolys returns the polygons in the front of the split plane
                 @param backPolys returns the polygons in the back of the split plane
-        */
-        void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);
+                @param splits number of splits
+        */
+        void SplitPolygons(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys, int &splits);
 
 protected:
@@ -161 +174 @@
 
 
-/** Class representing a polygon.
-*/
-class Polygon
-{
-public:
-        Polygon();
-        Polygon(const VertexContainer &vertices);
-
-        /** Copies all the vertices of the face.
-        */
-        Polygon(Face *face, Mesh *parent);
-        
-        /** Returns supporting plane of this polygon.
-        */
-        Plane3 GetSupportingPlane();
-
-        /** Splits polygon.
-                @param partition the split plane
-                @param front the front polygon
-                @param back the back polygon
-        */
-        void Split(Plane3 *partition, Polygon *front, Polygon *back);
-
-        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
-
-        /** Side of the plane where the polygon is located.
-            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
-        */
-        int Side(Plane3 *plane);
-
-        static void DeletePolygons(PolygonQueue *polys);
-
-        /// vertices are connected in counterclockwise order.
-        VertexContainer mVertices;
-};
-
 /** Implementation of the ViewCell BSP tree. */
 class BspTree 
@@ -211 +188 @@
                 BspInterior *mParent;
                 /// polygonal data for splitting
-                PolygonQueue *mPolys;
+                PolygonQueue *mPolygons;
                 /// current depth
                 int mDepth;
@@ -218 +195 @@
                 
                 BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
-                mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
+                mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {}
     };
 
         typedef std::stack<BspTraversalData> BspTraversalStack;
 
-        /** Constructs BSP tree from list of view cells.
+        /// BSP tree construction type
+        enum {VIEWCELLS, SCENE_GEOMETRY};
+
+        /** Default constructor creating an empty tree.
         */ 
-        BspTree(const ViewCellContainer &viewCells);
-        /** Constructs BSP tree from list of objects.
-                @param object list of intersectables
-                @param maxPolys maximal allowed number of polygons
-                @param maxDepth maximal allowed BSP tree depth
-        */
-        BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
+        BspTree();
 
         ~BspTree();
 
+        const BspTreeStatistics &GetStatistics() const; 
+  
+        /** Constructs tree using the given list of viewcells.
+            A pointer to the appropriate viewcell is stored within each leaf. 
+                Many leafs can point to the same viewcell.
+        */
+        void Construct(const ViewCellContainer &viewCells);
+        /** Constructs tree using the given list of objects. Each leaf is taken as viewcell.
+            No objects are treated as viewcells explicitly.
+
+                @param objects list of objects
+        */
+        void Construct(const ObjectContainer &objects);
+
+
 protected:
-        /** Builds a new extension of the tree.
-        */
-        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell = NULL);
-
-        /** Selects a splitting plane from the given polygons. 
+        void EvaluateLeafStats(const BspTraversalData &data);
+
+        /** Subdivides node with respect to the traversal data.
+            @param tStack current traversal stack
+                @param tData traversal data also holding node to be subdivided
+                @param viewCell the view cell that will be represented with this part of the Bsp tree.
+        */
+        void Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);
+
+        /** Selects a splitting plane. 
+                @param polyQueue the polygon data on which the split decition is based
         */
         Plane3 SelectPlane(PolygonQueue *polyQueue);
@@ -248 +243 @@
         */
         void InsertViewCell(ViewCell *viewCell);
-
-        /** Subdivides tree according to the given list of viewcells.
-        */
-        void Subdivide(const ViewCellContainer &viewCells);
-        /** Subdivides tree according to the given list of objects.
-        */
-        void Subdivide(const ObjectContainer &objects);
         
-        /** Subdivides leaf.
+        /** Subdivide leaf.
                 @param leaf the leaf to be subdivided
                 @param parent the parent node of this leaf
@@ -275 +263 @@
                 @param backPolys returns the polygons in the back of the split plane
         */
-        void FilterPolygons(BspInterior *node, PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys);
-
-        /** Extracts the mesh instances of the objects and copies them into the mesh.
+        void FilterPolygons(BspInterior *node, PolygonQueue *polys, 
+                                                PolygonQueue *frontPolys, PolygonQueue *backPolys);
+
+        /** Extracts the meshes of the objects and copies them into the mesh.
         */
         static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
 
-        static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
+        /** copy this mesh into polygons.
+        */
+        static void CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys);
 
         /// Pointer to the root of the tree
@@ -287 +278 @@
         /// Pointer to the root cell of the viewspace
         // ViewCell *mRootCell;
-        /// maximal number of polygons allowed in leaf
-        int mMaxPolys;
-        /// maximal depth
-        int mMaxDepth;
-
+        
+        
         BspTreeStatistics mStat;
+
+        /// local maximal polygons (changes depending on method)
+        int mTermMaxPolygons;
+        int mTermMaxDepth;
+
+public:
+        /// Parses the environment and stores the global BSP tree parameters
+        static void ParseEnvironment();
+
+        /// maximal number of polygons where tree construction is terminated
+        static int sTermMaxPolygons;
+        /// maximal possible depth
+        static int sTermMaxDepth;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/common.h

@@ -127 +127 @@
 #define MAX_FLOAT  1e30f
 
+#ifndef DEL_PTR
+#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}
+#endif
+
 inline
 int signum(const Real a, const Real thresh = TRASH)

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -18 +18 @@
   environment->Parse(argc, argv, USE_EXE_PATH);
   MeshKdTree::ParseEnvironment();
-  
+  BspTree::ParseEnvironment();
+
   Preprocessor *p =
     new SamplingPreprocessor();
@@ -27 +28 @@
 
   p->LoadScene(filename);
+
   p->BuildKdTree();
   p->KdTreeStatistics(cout);
-
-#ifdef DEST_BSP_VIEWCELLS
+#ifdef TEST_BSP_VIEWCELLS
   p->GenerateViewcells();
-  p->BspTreeStatistics(cout);
+  p->BspTreeStatistics(Debug);
 #endif
 
@@ -46 +47 @@
     p->ExportPreprocessedData("scene.vis");
   }
-  
+
   if (0) {
     Camera camera;