Changeset 263 for trunk/VUT/GtpVisibilityPreprocessor/src

Timestamp:

09/12/05 02:07:02 (19 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Camera.cpp (modified) (1 diff)
• Containers.h (modified) (1 diff)
• Polygon3.h (modified) (2 diffs)
• Preprocessor.cpp (modified) (6 diffs)
• Preprocessor.h (modified) (1 diff)
• ViewCell.cpp (modified) (1 diff)
• ViewCellBsp.cpp (modified) (28 diffs)
• ViewCellBsp.h (modified) (11 diffs)
• X3dExporter.cpp (modified) (4 diffs)
• X3dExporter.h (modified) (2 diffs)
• main.cpp (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Camera.cpp

@@ -97 +97 @@
     exporter->SetWireframe();
     exporter->ExportKdTree(*tree);
-//      exporter->ExportBspTree(*tree);
+        //exporter->ExportBspTree(*bsptree);
     exporter->ExportRays(rays, 10000);
     exporter->SetFilled();

trunk/VUT/GtpVisibilityPreprocessor/src/Containers.h

@@ -11 +11 @@
 class SceneGraphNode;
 class Intersectable;
+class Polygon3;
 
+/** Container storing polygons used during BSP tree construction
+*/
+typedef vector<Polygon3 *> PolygonContainer;
 
 /** Container for Mesh pointers primarily for the use within the kDTree and

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -13 +13 @@
 class Face;
 
-/** Container storing polygons used during BSP tree construction
-*/
-typedef vector<Polygon3 *> PolygonContainer;
 
 /** Class representing a general planar polygon in 3d.
@@ -67 +64 @@
         /// we can also store materials with polygons
         Material *mMaterial;
+
+        static int mLeastSplitTable[4];
+        static int mBalancedTreeTable[4];
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -23 +23 @@
 Preprocessor::LoadViewCells(const string filename)
 {
-        X3dParser *parser = new X3dParser;
-
-        bool result = parser->ParseFile(filename, mViewCells);
-
-        if (result)
-        {
-                Exporter *exporter = Exporter::GetExporter("viewcells.x3d");
-
-                if (exporter) 
-                {
-                        exporter->ExportViewCells(&mViewCells);
-                        delete exporter;
-                }
-
-                Debug << "Generating view cells" << endl;
-                GenerateViewCells();
-                Debug << "Generated view cells" << endl;
-        }
-
-        DEL_PTR(parser);
-        
-
-        return result;
+        return X3dParser().ParseFile(filename, mViewCells);
 }
 
@@ -51 +29 @@
 Preprocessor::GenerateViewCells()
 {
-        return BuildBspTree();
+        // TODO
+        // HACK: derive view cells from the scene objects
+        ObjectContainer objects;
+
+        int maxViewCells = 0;
+        environment->GetIntValue("BspTree.maxViewCells", maxViewCells);
+
+        mSceneGraph->CollectObjects(&objects);
+        ViewCell::DeriveViewCells(objects, mViewCells, maxViewCells);
+
+        return true;
 }
 
@@ -94 +82 @@
 }
 
+
 bool
 Preprocessor::BuildBspTree()
@@ -100 +89 @@
         mBspTree = new BspTree();
 
-        char constructionMethodStr[64];
-        int maxViewCells = 0;
-
-        environment->GetIntValue("BspTree.maxViewCells", maxViewCells);
-        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 if (strcmp(constructionMethodStr, "rays") == 0)
-                constructionMethod = BspTree::RAYS;
-        else 
-        {
-                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
-                exit(1);
-    }
-
         ObjectContainer objects;
         RayContainer rays;
 
-        switch (constructionMethod)
+        switch (BspTree::sConstructionMethod)
         {
-        case BspTree::VIEWCELLS:
+        case BspTree::VIEW_CELLS:
                 Debug << "Construction method: view cells\n";
-
-                // derive view cells from the scene objects
-                if (mViewCells.empty())         
-                {
-                        Debug << "View cells empty => generating new ones\n"; Debug.flush();
-                        mSceneGraph->CollectObjects(&objects);
-                        ViewCell::DeriveViewCells(objects, mViewCells, maxViewCells);
-                }
-
+                
                 mBspTree->Construct(mViewCells);
                 break;
@@ -142 +103 @@
 
         CLEAR_CONTAINER(mViewCells); // we generate new view cells
+
                 mSceneGraph->CollectObjects(&objects);
-
                 mBspTree->Construct(objects, &mViewCells);
                 break;
@@ -149 +110 @@
                 Debug << "Construction method: rays\n";
 
-                CLEAR_CONTAINER(mViewCells); // we generate new view cells
-                
+                CLEAR_CONTAINER(mViewCells); // we generate new view cells      
                 mBspTree->Construct(rays, &mViewCells);
                 break;

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h

@@ -67 +67 @@
   
    /** Build the BSP tree of currently loaded occluders/occludees/viewcells. The construction
-      is driven by the environment settings, which also sais which of the three types of
+      is driven by the environment settings, which also says which of the three types of
       entities should be used to drive the heuristical construction (only occluders by default)
   */

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -116 +116 @@
                 mesh->mVertices.push_back(topTri.mVertices[i]);
         
+        mesh->Preprocess();
+
         return new ViewCell(mesh);
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -19 +19 @@
 int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
 int BspTree::sMaxCandidates = 10;
+int BspTree::sConstructionMethod = VIEW_CELLS;
+
+/** Evaluates split plane classification with respect to the plane's 
+        contribution for a balanced tree.
+*/
+int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0};
+/** Evaluates split plane classification with respect to the plane's 
+        contribution for a minimum number splits in the tree.
+*/
+int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};
 
 /****************************************************************/
@@ -51 +61 @@
 }
 
+void BspNode::AddPolygons(PolygonContainer *polys)
+{
+        while (!polys->empty())
+        {
+                mPolygons.push_back(polys->back());
+                polys->pop_back();
+        }
+}
+
+
 /****************************************************************/
 /*              class BspInterior implementation                */
@@ -56 +76 @@
 
 
-BspInterior::BspInterior(Plane3 plane): mPlane(plane) 
+BspInterior::BspInterior(const Plane3 &plane): 
+mPlane(plane), mFront(NULL), mBack(NULL)
 {}
 
@@ -95 +116 @@
     mBack = b;
     mFront = f;
+}
+
+void BspInterior::ProcessPolygon(Polygon3 *poly, bool storePolys)
+{
+        if (storePolys) 
+                mPolygons.push_back(poly);
+        else
+                delete poly;
 }
 
@@ -116 +145 @@
                 {
                         case Polygon3::COINCIDENT:
-                                // same sides => discard
-                                if (DotProd(poly->GetSupportingPlane().mNormal, mPlane.mNormal) > 0) 
-                                {
-                                        if (storePolys)
-                                                mPolygons.push_back(poly);
-                                        else
-                                                DEL_PTR(poly);
-                                }
-                                else
-                                        backPolys->push_back(poly);
-                                break; // TODO: compare normals
+                                // discard polygons or saves them in node
+                                ProcessPolygon(poly, storePolys);
+                                break;
                         case Polygon3::FRONT_SIDE:
                                 frontPolys->push_back(poly);
@@ -142 +163 @@
                                 frontPolys->push_back(front_piece);
                                 backPolys->push_back(back_piece);
+
+#ifdef _DEBUG
+                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
+#endif
+                                // save or discard polygons
+                                ProcessPolygon(poly, storePolys);
                                 
-                                if (storePolys)
-                                        mPolygons.push_back(poly);
-                                else
-                                        DEL_PTR(poly);
-#ifdef _DEBUG
-                                Debug << "split " << poly << endl << front << endl << back << endl;
-#endif
                                 break;
                         default:
@@ -164 +184 @@
 /*                  class BspLeaf implementation                */
 /****************************************************************/
+BspLeaf::BspLeaf(): mViewCell(NULL)
+{
+}
 
 BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
 {
 }
+
+BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
+{}
 
 ViewCell *BspLeaf::GetViewCell()
@@ -184 +210 @@
 }
 
-void BspLeaf::AddPolygons(PolygonContainer *polys)
-{
-        while (!polys->empty())
-        {
-                mPolygons.push_back(polys->back());
-                polys->pop_back();
-        }
-}
 /****************************************************************/
 /*                  class BspTree implementation                */
@@ -218 +236 @@
 
         app << "#N_RAYS Number of rays )\n"
-                << rays <<endl;
+                << rays << endl;
         app << "#N_DOMAINS  ( Number of query domains )\n"
                 << queryDomains <<endl;
@@ -247 +265 @@
 
         app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
-        zeroQueryNodes*100/(double)Leaves()<<endl;
+        zeroQueryNodes*100/(double)Leaves() << endl;
 
         app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
@@ -300 +318 @@
 {       
         std::stack<BspTraversalData> tStack;
-        
-        PolygonContainer polys;
-
-        // copy polygon information to guide the split process
-        AddMesh2Polygons(viewCell->GetMesh(), polys);
+                Debug << "getting polygons" << endl; Debug.flush();
+        PolygonContainer *polys = new PolygonContainer();
+
+        // extract polygons that guide the split process
+        AddMesh2Polygons(viewCell->GetMesh(), *polys);
         mBox.Include(viewCell->GetBox()); // add to BSP aabb
 
-        BspNode *firstNode = mRoot ? mRoot : new BspLeaf(); // traverse tree or create new one
-
-        tStack.push(BspTraversalData(firstNode, NULL, &polys, 0));
-
+         // traverse tree or create new one
+        BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
+
+        tStack.push(BspTraversalData(firstNode, NULL, polys, 0));
+
+        Debug << "starting traversal" << endl; Debug.flush();
         while (!tStack.empty())
         {
+                Debug << "new traversal step" << endl; Debug.flush();
+                
                 // filter polygons donw the tree
                 BspTraversalData tData = tStack.top();
-
             tStack.pop();
-                                
-        if (!tData.mNode->IsLeaf())
-                {
+                        
+                Debug << "popped stack" << endl; Debug.flush();
+                if (!tData.mNode)
+                        Debug << "ERROR NO NODE\n"; Debug.flush();
+                if (!tData.mNode->IsLeaf())
+                {
+                        Debug << "no leaf" << endl; Debug.flush();
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
 
@@ -327 +352 @@
 
                         int splits = 0;
-                        // split viecell polygons with respect to split plane
-                        interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits);
-
-                        mStat.splits += splits;
-
-                        // push the children on the stack
-                        if (frontPolys->size() > 0) // if polygons on front side of bsp tree
+                
+                        if ((int)tData.mPolygons->size() > 0)
                         {
+                                Debug << "traversing down tree" << endl; Debug.flush();
+                                // split viecell polygons with respect to split plane
+                                interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
+                                Debug << "polygon splitted" << endl; Debug.flush();
+                                //Debug << "Reached level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
+                                mStat.splits += splits;
+
+                                // push the children on the stack
                                 tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), 
                                                         frontPolys, tData.mDepth + 1));
-                        }
-                        else // front side polygons empty
-                                delete frontPolys;
-
-                        if (backPolys->size() > 0) // if polygons on backc side of bsp tree
-                        {
+                        
                                 tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), 
                                                         backPolys, tData.mDepth + 1));
+                        
                         }
-                        else // back side polygons empty
-                                delete backPolys;
+                        else
+                        {
+                                Debug << "deleting data" << endl; Debug.flush();
+                                DEL_PTR(tData.mPolygons);
+                                Debug << "deleted data" << endl; Debug.flush();
+                        }
                 }
                 else // reached leaf => subdivide current viewcell
                 {
-                        BspNode *root = Subdivide(tStack, tData, viewCell);
+                        Debug << "reached leaf" << endl; Debug.flush();
+                        BspNode *root = Subdivide(tStack, tData, viewCell);             
 
             // tree empty => new root
                         if (!mRoot)
-                                mRoot = root;                           
-                }
-        }
+                                mRoot = root;           
+                        Debug << "subdivision done" << endl; Debug.flush();
+                }
+                Debug << "ended one traversal step" << endl; Debug.flush();
+        }
+        Debug << "ended traversal" << endl; Debug.flush();
 }
 
@@ -434 +466 @@
         
         /* for this type of construction we filter all viewcells down the 
-         * tree until there is no polygon left. The split of the last polygon 
+         * tree. If there is no polygon left, the last split plane
          * decides inside or outside of the viewcell.
     */
-        const int maxPolygons = 0;
-        const int maxDepth = 99999;
-        
-        InitTree(maxPolygons, maxDepth);
-        
+        InitTree(sTermMaxPolygons, sTermMaxDepth);
+
+    bool savedStorePolys = mStorePolys;
+
         // tree is completely constructed once before 
         // view cells are inserted one after another => 
@@ -447 +478 @@
         if (!mIsIncremential)
         {
-                Debug << "Not incremential => constructing tree in advance\n";
                 // copy view cell meshes into one big polygon soup
                 PolygonContainer *polys = new PolygonContainer();
                 Copy2PolygonSoup(viewCells, *polys, sMaxCandidates);
 
+                // polygons are stored only during view cell insertion
+                mStorePolys = false;
+
                 // construct tree from viewcell polygons
                 Construct(polys);
-
-                Export("bsp.x3d");
+                //Export("bsp.x3d");
         }
         
@@ -461 +493 @@
         ViewCellContainer::const_iterator it;
 
+        mStorePolys = savedStorePolys;
+
         int counter = 0;
 
-        Debug << "View cells insertion...\n"; Debug.flush();
+        Debug << "\n**** Started view cells insertion ****\n\n";
         for (it = viewCells.begin(); it != viewCells.end(); ++ it)
         {
-                Debug << "Inserting view cell " << ++counter;
+                Debug << "*** Inserting view cell " << counter << " ***" << endl;
                 InsertViewCell(*it);
-        }
-        Debug << "finished view cells insertion";
+                Debug << "*** view cell " << ++ counter << " inserted ***" << endl;
+        }
+        Debug << "**** finished view cells insertion ****" << endl; Debug.flush();
 }
 
@@ -476 +511 @@
 {
         // take termination criteria from globals
-        InitTree(mTermMaxPolygons, mTermMaxDepth);
-        Debug << "HAHAHAHHA";Debug.flush();
+        InitTree(sTermMaxPolygons, sTermMaxDepth);
+        
         PolygonContainer *polys = new PolygonContainer();
         
@@ -497 +532 @@
 {
         std::stack<BspTraversalData> tStack;
-        Debug << "HDDHDH"; Debug.flush();
-
+        
         BspTraversalData tData(new BspLeaf(), NULL, polys, 0);
 
         tStack.push(tData);
 
-        Debug << "Contructing tree using objects..."; Debug.flush();
+        Debug << "**** Contructing tree using objects ****\n";
         while (!tStack.empty()) 
         {
                 tData = tStack.top();
             tStack.pop();
-
         
                 // subdivide leaf node
                 BspNode *root = Subdivide(tStack, tData);
 
-                // empty tree => // new root corresponding to unbounded space
+                // empty tree => new root corresponding to unbounded space
                 if (!mRoot) 
                         mRoot = root;
         }
 
-        Debug << "finished\n";
+        Debug << "**** tree construction finished ****\n";
 }
 
@@ -526 +559 @@
                                                          ViewCell *viewCell)
 {
+        Debug << "subdividing" << endl; Debug.flush();
         PolygonContainer *backPolys = new PolygonContainer();
         PolygonContainer *frontPolys = new PolygonContainer();
@@ -538 +572 @@
         if (!node->IsLeaf()) // node was subdivided
         {
+                Debug << "node was subdivided" << endl; Debug.flush();
                 BspInterior *interior = dynamic_cast<BspInterior *>(node);
 
@@ -544 +579 @@
                 tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, tData.mDepth + 1));
         }
-        else // tree terminates here
-        {
+        else // traversal terminates
+        {
+                Debug << "eval stats" << endl; Debug.flush();
                 EvaluateLeafStats(tData);
 
-                // add view cell if in positive halfspace
-                if (!tData.mParent || (node == tData.mParent->GetFront()))
-                        dynamic_cast<BspLeaf *>(node)->SetViewCell(viewCell);
+        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                // add view cell if in negative halfspace (== inside object) 
+                // or if there is still geometry left
+                if (viewCell && 
+                        (!node->GetParent() || (node == node->GetParent()->GetBack()) || 
+                         (tData.mPolygons->size() > 0)))
+                {
+                        Debug << "** view cell inserted **\n";
+                        leaf->SetViewCell(viewCell);
+                }
+
+                Debug << "storing or deleting polygons: " << mStorePolys << endl; Debug.flush();
+                // add or delete remaining polygons
+                if (mStorePolys)
+                        leaf->AddPolygons(tData.mPolygons);
+                else
+                        CLEAR_CONTAINER(*tData.mPolygons);
+
+                DEL_PTR(tData.mPolygons);
+                Debug << "deleted polygon container" << endl; Debug.flush();
         }
 
@@ -556 +610 @@
 }
 
-bool BspTree::ProcessPolygons(PolygonContainer *polys, BspLeaf *leaf)
-{
-        bool result = false;
-
-        if (mStorePolys)
-        {
-                leaf->AddPolygons(polys);
-                result = true;
-        }
-        else
-                CLEAR_CONTAINER(*polys);
-
-        delete polys;
-        return result;
-}
 
 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
@@ -579 +618 @@
                                                                 PolygonContainer *backPolys)
 {
-        // terminate traversal
-        if ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth))
-        {
-                // add or delete remaining polygons
-                ProcessPolygons(polys, leaf);
-
+        if (leaf->GetViewCell() && (polys->size() == 0))
+                Debug << "error: no distinct view cells!!!!!!!!!!!\n";
+        
+        // terminate traversal  
+        if (//!leaf->GetViewCell() && 
+                ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth)))
+        {Debug << "subdividing node termination" << endl; Debug.flush();
                 return leaf;
         }
@@ -600 +640 @@
         int splits = 0;
                 
+        Debug << "splipoly" << endl; Debug.flush();
         node->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
         
@@ -605 +646 @@
 
         // two new leaves
-        BspLeaf *back = new BspLeaf();
-        BspLeaf *front = new BspLeaf();
+        BspLeaf *back = new BspLeaf(node);
+        BspLeaf *front = new BspLeaf(node);
 
         // replace a link from node's parent
         if (parent)
-        {
                 parent->ReplaceChildLink(leaf, node);
-        }
-
+        
         // and setup child links
         node->SetupChildLinks(back, front);
-
-        delete leaf; // leaf not member of tree anymore
+        
+        DEL_PTR(leaf); // leaf not member of tree anymore
         
         return node;
 }
 
-Plane3 BspTree::SelectPlane(PolygonContainer *polygons)  const
-{
+Plane3 BspTree::SelectPlane(PolygonContainer *polys)  const
+{
+        if (polys->size() == 0)
+        {
+                Debug << "Warning: No split candidate available\n";
+                return Plane3();
+        }
+
         // simple strategy: just take next polygon
         if (sSplitPlaneStrategy == NEXT_POLYGON)
         {
-                return polygons->front()->GetSupportingPlane();
+                return polys->front()->GetSupportingPlane();
         }
         
         // use heuristics to find appropriate plane
-        return SelectPlaneHeuristics(polygons, sMaxCandidates);
+        return SelectPlaneHeuristics(polys, sMaxCandidates);
 }
 
@@ -672 +717 @@
                 if ((sSplitPlaneStrategy == BALANCED_TREE) || (sSplitPlaneStrategy == COMBINED))
                 {
-                        sum += EvalForBalancedTree(classification);
+                        sum += sBalancedTreeTable[classification];
                 }
                 
                 if ((sSplitPlaneStrategy == LEAST_SPLITS) || (sSplitPlaneStrategy == COMBINED))
                 {
-                        sum2 += EvalForLeastSplits(classification);
+                        sum2 += sLeastSplitsTable[classification];
                 }
         }
@@ -684 +729 @@
         return abs(sum) + abs(sum2);
 }
-
-int BspTree::EvalForBalancedTree(const int classification)
-{
-        // there should be roughly the same number of front and back polygons
-        if (classification == Polygon3::FRONT_SIDE)
-                return 1;
-        else if (classification == Polygon3::BACK_SIDE)
-                return -1;
-
-        return 0;
-}
-
-int BspTree::EvalForLeastSplits(const int classification)
-{
-        if (classification == Polygon3::SPLIT)
-                return 1;
-
-        return 0;
-}
-
 
 void BspTree::ParseEnvironment()
@@ -729 +754 @@
                 exit(1);
     }
+
+        //-- parse BSP tree construction method
+        char constructionMethodStr[64];
+        
+        environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);
+
+        sConstructionMethod = BspTree::VIEW_CELLS;
+        
+        if (strcmp(constructionMethodStr, "viewCells") == 0)
+                sConstructionMethod = BspTree::VIEW_CELLS;
+        else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
+                sConstructionMethod = BspTree::SCENE_GEOMETRY;
+        else if (strcmp(constructionMethodStr, "rays") == 0)
+                sConstructionMethod = BspTree::RAYS;
+        else 
+        {
+                cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
+                exit(1);
+    }
+
 }
 
@@ -919 +964 @@
                         BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
                         //ray.leaves.push_back(leaf);
-      
+      // TODO
                         /*ObjectContainer::const_iterator mi;
                         for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi) 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -72 +72 @@
 
   int Nodes() const {return nodes;}
-  int Interior() const { return nodes/2; }
-  int Leaves() const { return (nodes/2) + 1; }
+  int Interior() const { return nodes / 2; }
+  int Leaves() const { return (nodes / 2) + 1; }
 
   void Reset() 
@@ -128 +128 @@
         PolygonContainer *GetPolygons();
 
+        /** Adds polygons to node.
+        */
+        void AddPolygons(PolygonContainer *polys);
+
 protected:
 
@@ -143 +147 @@
         /** Standard contructor taking split plane as argument.
         */
-        BspInterior(Plane3 plane);
+        BspInterior(const Plane3 &plane);
         /** @return false since it is an interior node 
         */
@@ -173 +177 @@
 protected:
         
+        /** Discards or stores polygon in node.
+                @param polys the polygons
+                @param storePolys if the polygons should be stored or discarded
+        */
+        void ProcessPolygon(Polygon3 *poly, bool storePolys);
+
         /// Splitting plane corresponding to this node
         Plane3 mPlane;
@@ -188 +198 @@
 
 public:
-        BspLeaf(ViewCell *viewCell = NULL);
+        BspLeaf();
+        BspLeaf(ViewCell *viewCell);
+        BspLeaf(BspInterior *parent);
 
         /** @return true since it is an interior node 
@@ -201 +213 @@
 
 protected:
-
-        /** Helper function used to add remaining polygons to leaf.
-        */
-        void AddPolygons(PolygonContainer *polys);
 
         /// polygonal representation of this viewcell
@@ -239 +247 @@
 
         /// BSP tree construction type
-        enum {VIEWCELLS, SCENE_GEOMETRY, RAYS};
+        enum {VIEW_CELLS, SCENE_GEOMETRY, RAYS};
 
         /** Default constructor creating an empty tree.
@@ -305 +313 @@
         void Construct(PolygonContainer *polys);
 
-        /** Evaluates plane classification with respect to the plane's 
-                contribution for a balanced tree.
-        */
-        static inline int EvalForBalancedTree(const int classficiation);
-        /** Evaluates plane classification with respect to the plane's 
-                contribution for a minimum number splits in the tree.
-        */
-        static inline int EvalForLeastSplits(const int classification);
-
         /** Evaluates the contribution of the candidate split plane.
         */
@@ -331 +330 @@
 
         /** Selects a splitting plane. 
-                @param polygons the polygon data on which the split decition is based
-        */
-        Plane3 SelectPlane(PolygonContainer *polygons) const;
+                @param polys the polygon list on which the split decition is based
+        */
+        Plane3 SelectPlane(PolygonContainer *polys) const;
 
         /** Filters next viewcell down the tree and inserts it into the appropriate leaves
@@ -391 +390 @@
         int CastRay(Ray &ray);
 
-        /** Discards or stores polygons in leaf and deletes the container.
-                @param polys the polygons
-                @param leaf the leaf where polygons are stored
-        */
-        bool ProcessPolygons(PolygonContainer *polys, BspLeaf *node);
+
 
         /// Pointer to the root of the tree
@@ -433 +428 @@
         /// number of candidates evaluated for the next split plane
         static int sMaxCandidates;
+        /// BSP tree construction method
+        static int sConstructionMethod;
+
+private:
+        /** Evaluates split plane classification with respect to the plane's 
+                contribution for a balanced tree.
+        */
+        static int sLeastSplitsTable[4];
+        /** Evaluates split plane classification with respect to the plane's 
+                contribution for a minimum number splits in the tree.
+        */
+        static int sBalancedTreeTable[4];
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -274 +274 @@
 }
 
+void X3dExporter::ExportPolygons(PolygonContainer *polys)
+{
+        stream << "<Shape>" << endl;
+        stream << "<Appearance>" << endl;
+  
+        // $$ tmp -> random material
+  
+        float r, g, b;
+
+        if (mUseForcedMaterial) 
+        {
+                r = mForcedMaterial.mDiffuseColor.r;
+                g = mForcedMaterial.mDiffuseColor.g;
+                b = mForcedMaterial.mDiffuseColor.b;
+        } 
+        else 
+        {
+                r = RandomValue(0.5, 1.0);
+                g = RandomValue(0.5, 1.0);
+                b = RandomValue(0.5, 1.0);
+        }
+
+        stream << "<Material diffuseColor=\"" << r << " " << g << " " << b 
+                   << "\" specularColor=\"0.0 0.0 0.0\"/>" << endl;
+
+    stream << "</Appearance>" << endl;
+
+
+        //-- create and write indices
+        if (mWireframe)
+                stream << "<IndexedLineSet ccw=\"TRUE\" coordIndex=\"" << endl;
+        else
+                stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl;
+
+        int index = 0;
+        
+        PolygonContainer::const_iterator pit;
+
+    VertexContainer::const_iterator vi;  
+        
+        for (pit = polys->begin(); pit != polys->end(); ++pit)
+        {
+                Polygon3 *poly = *pit;
+                for (vi = poly->mVertices.begin(); vi != poly->mVertices.end(); ++vi) 
+                {
+                        stream << index ++ << " ";
+                }
+                stream << "-1" << endl;
+        }
+
+        stream << "\" >" << endl;
+        
+        stream << "<Coordinate  point=\"" << endl;
+        for (pit = polys->begin(); pit != polys->end(); ++pit)
+        {
+                Polygon3 *poly = *pit;
+        for (vi = poly->mVertices.begin(); vi != poly->mVertices.end(); ++vi) 
+                {
+                        stream << (*vi).x << " " << (*vi).y << " " << (*vi).z;
+                        stream << "," << endl;
+                }
+        }
+        stream << "\" >" << endl;
+        stream << "</Coordinate>" << endl;
+
+        if (mWireframe)
+                stream << "</IndexedLineSet>" << endl;
+        else
+                stream << "</IndexedFaceSet>" << endl;
+  
+        stream << "</Shape>" << endl;
+}
 
 bool
@@ -305 +377 @@
         if (mExportRayDensity) 
         {
-                return false;//ExportKdTreeRayDensity(tree);
+                return ExportBspTreeRayDensity(tree);
         }
   
@@ -340 +412 @@
 
                 }
-                else
+                else if (!tree.StorePolys())
                 {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
                         
-                        // export view cell geometry
-                        
-                        if (!tree.StorePolys() && leaf->GetViewCell())
-                        {
-                                ExportViewCell(leaf->GetViewCell());
-                        }
-                        
+                        if (viewCell) // export view cell geometry
+                                ExportViewCell(viewCell);       
                 }
-  }
-  
-  return true;
+        }
+        
+        return true;
 }
 
@@ -402 +469 @@
 }
 
+
+bool
+X3dExporter::ExportBspTreeRayDensity(const BspTree &tree)
+{
+        // TODO
+        return true;
+}
 
 bool

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

@@ -50 +50 @@
   ExportPolygon(Polygon3 *poly);
 
+  virtual void ExportPolygons(PolygonContainer *polys);
+
   virtual bool
   ExportBox(const AxisAlignedBox3 &box);
@@ -75 +77 @@
   ExportKdTreeRayDensity(const KdTree &tree);
 
-  
+  bool
+  ExportBspTreeRayDensity(const BspTree &tree);  
 };
  

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -35 +35 @@
   environment->GetStringValue("Scene.viewcells", buff);
 
-  string viewCellsFile(buff);
-  p->LoadViewCells(viewCellsFile);
+  string vcFileName(buff);
 
+  // if BSP tree construction method needs predefined view cells
+  if (BspTree::sConstructionMethod == BspTree::VIEW_CELLS)
+  {
+          if (vcFileName != "")
+          p->LoadViewCells(vcFileName);
+          else
+                  p->GenerateViewCells();
+  }
+
+  p->BuildBspTree();
   p->BspTreeStatistics(Debug);
+  p->Export(filename + "-bsptree.x3d", false, false, true);
+
 #endif
 
@@ -44 +55 @@
   if (0) {
     p->Export(filename + "-out.x3d", true, false, false);
-    p->Export(filename + "-kdtree.x3d", false, true, false);
+    p->Export(filename + "-kdtree.x3d", false, true, false);    
   }