Changeset 295 for trunk/VUT/GtpVisibilityPreprocessor

Timestamp:

09/21/05 10:29:41 (19 years ago)

Author:

mattausch

Message:

put out debug output. added new subdivision strategies

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• AxisAlignedBox3.cpp (modified) (2 diffs)
• AxisAlignedBox3.h (modified) (3 diffs)
• Polygon3.cpp (modified) (2 diffs)
• Polygon3.h (modified) (2 diffs)
• ViewCellBsp.cpp (modified) (12 diffs)
• ViewCellBsp.h (modified) (7 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp

@@ -6 +6 @@
 #include "AxisAlignedBox3.h"
 #include "Ray.h"
+#include "Polygon3.h"
 
 #define FATAL Debug
@@ -43 +44 @@
   Minimize(mMin, newpt);
   Maximize(mMax, newpt);
+}
+
+void
+AxisAlignedBox3::Include(const Polygon3 &newpoly)
+{
+        VertexContainer::const_iterator it, it_end = newpoly.mVertices.end();
+
+        for (it = newpoly.mVertices.begin(); it != it_end; ++ it)
+                Include(*it);
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h

@@ -9 +9 @@
 class Plane3;
 class Ray;
-
+class Polygon3;
 
 // --------------------------------------------------------
@@ -91 +91 @@
 
   // the size of the box along all the axes
-  Vector3 Size() const { return mMax -mMin; }
+  Vector3 Size() const { return mMax - mMin; }
 
   // Return whether the box is unbounded.  Unbounded boxes appear
@@ -99 +99 @@
   // Expand the axis-aligned box to include the given object.
   void Include(const Vector3 &newpt);
+  void Include(const Polygon3 &newpoly);
   void Include(const AxisAlignedBox3 &bbox);
   // Expand the axis-aligned box to include given values in particular axis

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -3 +3 @@
 #include "ViewCellBsp.h" // TODO: erase this
 #include "Intersectable.h"
+#include "AxisAlignedBox3.h"
 
 // tolerance value for side relation
@@ -212 +213 @@
         return true;
 }
+
+void Polygon3::IncludeInBox(const PolygonContainer &polys, AxisAlignedBox3 &box)
+{
+        PolygonContainer::const_iterator it, it_end = polys.end();
+
+        for (it = polys.begin(); it != it_end; ++ it)
+                box.Include(*(*it));
+}

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -14 +14 @@
 class Face;
 class Intersectable;
-
+class AxisAlignedBox3;
 //typedef Vertex3 Vector3;
 
@@ -65 +65 @@
         bool CheckValid() const; 
 
+        /** Includes polygons to axis aligned box.
+        */
+        static void IncludeInBox(const PolygonContainer &polys, AxisAlignedBox3 &box);
+
         /// vertices are connected in counterclockwise order.
         VertexContainer mVertices;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -245 +245 @@
 
 BspTree::BspTree(): 
-mTermMaxPolygons(0), 
-mTermMaxDepth(0), 
 mRoot(NULL), 
 mVerticalAxis(Vector3(0, 0, 1)),
@@ -425 +423 @@
 }
 
-void BspTree::InitTree(int maxPolygons, int maxDepth)
-{
-        mTermMaxPolygons = maxPolygons;
-        mTermMaxDepth = maxDepth;
-        mStat.nodes = 1;
-        
-        mBox.Initialize();      // initialise bsp tree bounding box
-}
-
-
-
 int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent)
 {
@@ -506 +493 @@
 void BspTree::Construct(const ViewCellContainer &viewCells)
 {
-        InitTree(sTermMaxPolygons, sTermMaxDepth);
+        mStat.nodes = 1;
+        mBox.Initialize();      // initialise bsp tree bounding box
 
         // copy view cell meshes into one big polygon soup
@@ -520 +508 @@
 void BspTree::Construct(const ObjectContainer &objects, ViewCellContainer *viewCells)
 {
-        // take termination criteria from globals
-        InitTree(sTermMaxPolygons, sTermMaxDepth);
+        mStat.nodes = 1;
+        mBox.Initialize();      // initialise bsp tree bounding box
         
         PolygonContainer *polys = new PolygonContainer();
@@ -569 +557 @@
 {
         //-- terminate traversal  
-        if ((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
+        if ((tData.mPolygons->size() <= sTermMaxPolygons) || (tData.mDepth >= sTermMaxDepth))
         {
 #ifdef _DEBUG
@@ -643 +631 @@
 
         // add the new nodes to the tree + select subdivision plane
-        BspInterior *interior = new BspInterior(SelectPlane(polys)); 
+        BspInterior *interior = new BspInterior(SelectPlane(*polys)); 
 
 #ifdef _DEBUG
@@ -671 +659 @@
 }
 
-Plane3 BspTree::SelectPlane(PolygonContainer *polys)  const
-{
-        if (polys->size() == 0)
+Plane3 BspTree::SelectPlane(const PolygonContainer &polys)  const
+{
+        if (polys.size() == 0)
         {
                 Debug << "Warning: No split candidate available\n";
@@ -682 +670 @@
         if (sSplitPlaneStrategy & NEXT_POLYGON)
         {
-                return polys->front()->GetSupportingPlane();
-        }
-        
-    if (sSplitPlaneStrategy & VERTICAL_AXIS)
+                return polys.front()->GetSupportingPlane();
+        }
+        
+        if (sSplitPlaneStrategy & AXIS_ALIGNED)
+        {
+                AxisAlignedBox3 box;
+                box.Initialize();
+        
+                Polygon3::IncludeInBox(polys, box);
+        
+                int axis = box.Size().DrivingAxis();
+                Vector3 norm(0,0,0); norm[axis] = 1;
+
+                Vector3 pt = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
+
+                return Plane3(norm, pt);
+        }
+
+        /*if (sSplitPlaneStrategy & DRIVING_AXIS)
         {
                 const float dot_thres = 0.999;
@@ -695 +698 @@
                                 return (*it)->GetSupportingPlane();
                 }
-        }
+        }*/
+        
         // use heuristics to find appropriate plane
         return SelectPlaneHeuristics(polys, sMaxCandidates);
 }
 
-Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
+Plane3 BspTree::SelectPlaneHeuristics(const PolygonContainer &polys, int maxTests) const
 {
         float lowestCost = MAX_FLOAT;
         int bestPlaneIdx = 0;
         
-        int limit = Min((int)polygons->size(), maxTests);
+        int limit = Min((int)polys.size(), maxTests);
 
         for (int i = 0; i < limit; ++ i)
         {
-                int candidateIdx = Random((int)polygons->size()); // TODO: avoid testing same plane 2 times
-                Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
+                int candidateIdx = GetNextCandidateIdx((int)polys.size());
+                Plane3 candidatePlane = polys[candidateIdx]->GetSupportingPlane();
                 
                 // evaluate current candidate
-                float candidateCost = EvalSplitPlane(polygons, candidatePlane);
+                float candidateCost = EvalSplitPlane(polys, candidatePlane);
                         
                 if (candidateCost < lowestCost)
@@ -723 +727 @@
         //Debug << "Plane lowest cost: " << lowestCost << endl;
         
-        return (*polygons)[bestPlaneIdx]->GetSupportingPlane();
-}
-
-float BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
-{
-        PolygonContainer::const_iterator it;
-
-        float sumBalanced = 0, sumLeastSplits = 0;
-
-        for (it = polygons->begin(); it != polygons->end(); ++ it)
-        {
-                int classification = (*it)->ClassifyPlane(candidatePlane);
+        return polys[bestPlaneIdx]->GetSupportingPlane();
+}
+
+int BspTree::GetNextCandidateIdx(const int max) const
+{
+        return Random(max); // TODO: avoid testing same plane 2 times
+}
+
+float BspTree::EvalSplitPlane(const PolygonContainer &polys, const Plane3 &candidatePlane) const
+{
+        float sumBalanced = 0, sumLeastSplits, drivingAxis = 0;
+        
+        if (sSplitPlaneStrategy & DRIVING_AXIS)
+        {
+        drivingAxis = (candidatePlane.mNormal.DrivingAxis() == mBox.Size().DrivingAxis()) ?
+                        99.0f : 0.0f; // always prefer driving axis => very high value
+        }
+        if ((sSplitPlaneStrategy & BALANCED_TREE) || (sSplitPlaneStrategy & LEAST_SPLITS))
+        {
+                PolygonContainer::const_iterator it, it_end = polys.end();
                 
-                if (sSplitPlaneStrategy & BALANCED_TREE)
-                {
-                        sumBalanced += sBalancedTreeTable[classification];
-                }
-                
-                if (sSplitPlaneStrategy & LEAST_SPLITS)
-                {
-                        sumLeastSplits += sLeastSplitsTable[classification];
-                }
-        }
-
-        // return linear combination of both sums
-        return fabs(sumBalanced) + fabs(sumLeastSplits);
+                for (it = polys.begin(); it != it_end; ++ it)
+                {
+                        int classification = (*it)->ClassifyPlane(candidatePlane);
+
+                        if (sSplitPlaneStrategy & BALANCED_TREE)
+                                sumBalanced += sBalancedTreeTable[classification];
+        
+                        if (sSplitPlaneStrategy & LEAST_SPLITS)
+                                sumLeastSplits += sLeastSplitsTable[classification];
+                }
+        }
+
+        // return linear combination of the sums
+        return fabs(sumBalanced) + sumLeastSplits + drivingAxis;
 }
 
@@ -879 +892 @@
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
 
-        if (data.mDepth >= mTermMaxDepth)
+        if (data.mDepth >= sTermMaxDepth)
         {
                 ++ mStat.maxDepthNodes;
@@ -898 +911 @@
 #ifdef _DEBUG
         Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), #polygons: " << 
-          data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
+          data.mPolygons->size() << " (max: " << sTermMaxPolygons << ")" << endl;
 #endif
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -329 +329 @@
 protected:
         
-        /** Initialises BSP tree.
-                @param maxPolygons the maximal polygon count before termination of 
-                subdivision
-                @param maxDepth the maximal depth before termination of 
-                subdivision
-        */
-        void InitTree(int maxPolygons, int maxDepth);
-
         /** Constructs the tree from the given list of polygons.
                 @param viewCells if not NULL, new view cells are 
@@ -346 +338 @@
                 @returns the cost of the candidate split plane
         */
-        float EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const;
+        float EvalSplitPlane(const PolygonContainer &polys, const Plane3 &candidatePlane) const;
 
         /** Evaluates tree stats in the BSP tree leafs.
@@ -363 +355 @@
                 @param polys the polygon list on which the split decition is based
         */
-        Plane3 SelectPlane(PolygonContainer *polys) const;
+        Plane3 SelectPlane(const PolygonContainer &polys) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -402 +394 @@
                 @param maxTests the maximal number of candidate tests
         */
-        Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const;
+        Plane3 SelectPlaneHeuristics(const PolygonContainer &polys, const int maxTests) const;
 
         /** Extracts the meshes of the objects and copies them into the mesh. 
@@ -430 +422 @@
         int CastRay(Ray &ray);
 
+        /** returns next candidate index
+                @param max the range of candidates
+        */
+        inline int GetNextCandidateIdx(const int max) const;
+
         /// Pointer to the root of the tree
         BspNode *mRoot;
@@ -438 +435 @@
         BspTreeStatistics mStat;
 
-        /// local maximal polygons (changes depending on method)
-        int mTermMaxPolygons;
-        int mTermMaxDepth;
-
         /// Strategies for choosing next split plane.
         enum {NEXT_POLYGON = 0, 
                   LEAST_SPLITS = 2, 
                   BALANCED_TREE = 4, 
-                  VERTICAL_AXIS = 8, 
+                  DRIVING_AXIS = 8, 
                   AXIS_ALIGNED = 16};
 
@@ -457 +450 @@
         /// vertical axis of scene
         Vector3 mVerticalAxis;
+
 public:
         /// Parses the environment and stores the global BSP tree parameters