Changeset 306

Timestamp:

10/04/05 03:05:08 (19 years ago)

Author:

mattausch

Message:

fixed polygon area, eval candidate plane

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (2 diffs)
• src/Polygon3.cpp (modified) (2 diffs)
• src/Polygon3.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (10 diffs)
• src/ViewCellBsp.h (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -73 +73 @@
         # vertical axis        = 64
         
-        splitPlaneStrategy 64
+        splitPlaneStrategy 32
         # least splits + balanced polygons
         #splitPlaneStrategy 12
@@ -92 +92 @@
         constructionMethod viewCells
 #       constructionMethod sceneGeometry
-        maxCandidates 25
+        maxCandidates 50
         maxViewCells 999999
         Termination {
-                maxPolysForAxisAligned 50
+                maxPolysForAxisAligned 100
                 maxPolygons 0
-                maxDepth 100
+                maxDepth 200
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -37 +37 @@
 #endif
         return Plane3(mVertices[0], mVertices[1], mVertices[2]);
+}
+
+Vector3 Polygon3::GetNormal() const 
+{
+    return Normalize(CrossProd(mVertices[0]-mVertices[1],
+                                                           mVertices[2]-mVertices[1]));
 }
 
@@ -109 +115 @@
 float Polygon3::GetArea() const
 {
-        VertexContainer vtx;
-
-        //-- rotate polygon to lie in xy plane
-        Vector3 v1 = mVertices[0] - mVertices[1];
-        Vector3 v2 = mVertices[2] - mVertices[1];
-        Vector3 n = Normalize(CrossProd(v2,v1));
-
-        Matrix4x4 rot = GenRotation(v1, v2, n);
-
-        VertexContainer::const_iterator it, it_end = mVertices.end();
-
-        for (it = mVertices.begin(); it != it_end; ++it)
-                vtx.push_back(rot * (*it));
-
-        //-- compute area
-        Vector3 last = vtx.back();
-
-        float area = 0.0f;
-        for (it = vtx.begin(); it != vtx.end(); ++it)
-        {
-                area += last.y * (*it).x - last.x * (*it).y;
-
-                last = *it;
-        }
-        //Debug << "area: " << area * 0.5 << endl;
-        return area * 0.5f;
+        Vector3 v = CrossProd(mVertices.back(), mVertices.front());
+    
+    for (int i=0; i < mVertices.size() - 1; ++i)
+                v += CrossProd(mVertices[i], mVertices[i+1]);
+    
+    //Debug << "area2: " << 0.5f * fabs(DotProd(GetNormal(), v)) << endl;  
+
+        return 0.5f * fabs(DotProd(GetNormal(), v));
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -69 +69 @@
         bool Valid() const; 
 
+        Vector3 GetNormal() const;
+
         /** Includes polygons to axis aligned box.
         */

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -29 +29 @@
 float BspTree::sBalancedViewCellsFactor = 2.0f;
 float BspTree::sVerticalSplitsFactor = 1.0f; // very important criterium for 2.5d scenes
-
+float BspTree::sLargestPolyAreaFactor = 1.0f;
 
 /** Evaluates split plane classification with respect to the plane's 
@@ -365 +365 @@
 
         // extract polygons that guide the split process
-        mStat.polys += AddMesh2Polygons(viewCell->GetMesh(), *polys);
+        mStat.polys += AddMesh2Polygons(viewCell->GetMesh(), *polys, viewCell);
         mBox.Include(viewCell->GetBox()); // add to BSP aabb
 
@@ -460 +460 @@
                 polys.push_back(poly);
 
-                if (!poly->Valid())
-                        Debug << "Input polygon not valid: " << *poly 
-                                  << endl << "Area: " << poly->GetArea() << endl;
+                //if (!poly->Valid())
+                //      Debug << "Input polygon not valid: " << *poly << endl << "Area: " << poly->GetArea() << endl;
                 
                 ++ polysNum;
@@ -511 +510 @@
                 {
                         mBox.Include(object->GetBox()); // add to BSP tree aabb
-                        AddMesh2Polygons(mesh, polys);
+                        AddMesh2Polygons(mesh, polys, mViewCell);
                 }
         }
@@ -907 +906 @@
         
         int candidateIdx = limit;
-        PolygonContainer debugPolys;bool dist = true;
+        
         for (int i = 0; i < limit; ++ i)
         {
@@ -922 +921 @@
                         lowestCost = candidateCost;
                 }
-                for (int i=0; i < debugPolys.size(); ++i)
-                        if (polys[candidateIdx] == debugPolys[i])
-                        {
-                                Debug << "FATAL ERROR" << endl;
-                                dist = false;
-                        }
-                debugPolys.push_back(polys[candidateIdx]);
         }
         
         //Debug << "Plane lowest cost: " << lowestCost << endl;
-        if (!dist)
-                Debug << "FATAL ERROR DUPLICATE TESTS!!" << endl;
         return polys[bestPlaneIdx]->GetSupportingPlane();
 }
@@ -941 +931 @@
         int candidateIdx = Random(currentIdx--);
         
+        //Debug << "new candidate " << candidateIdx << endl;
+
         // swap candidates to avoid testing same plane 2 times
         Polygon3 *p = polys[candidateIdx];
@@ -958 +950 @@
                 // we put a penalty on the dot product between the "tiny" vertical axis
                 // and the split plane axis
-                // NOTE: weight with poly size because vertical split more important if too many polygons
                 val += sVerticalSplitsFactor * 
-                           fabs(DotProd(candidatePlane.mNormal, tinyAxis)) * (float)polys.size();
-        }
+                           fabs(DotProd(candidatePlane.mNormal, tinyAxis));
+        }
+
         //-- strategies where the effect of the split plane on the polygons is tested
-        if ((sSplitPlaneStrategy & BALANCED_POLYS)     || 
-                (sSplitPlaneStrategy & LEAST_SPLITS)       ||
-                (sSplitPlaneStrategy & LARGEST_POLY_AREA))
-        {
-                PolygonContainer::const_iterator it, it_end = polys.end();
-                float sumBalancedPolys = 0;
-                float sumSplits = 0;
-
-                for (it = polys.begin(); it != it_end; ++ it)
-                {
-                        int classification = (*it)->ClassifyPlane(candidatePlane);
-
-                        if (sSplitPlaneStrategy & BALANCED_POLYS)
-                                sumBalancedPolys += sBalancedPolysTable[classification];
-                                
-                        if (sSplitPlaneStrategy & LEAST_SPLITS)
-                                sumSplits += sLeastSplitsTable[classification];
-
-                        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
-                        {
-                                if (classification == Polygon3::COINCIDENT)
-                                {       
-                                        float area = (*it)->GetArea();
-                                        //Debug << "polygon area: " << area << " ";
-                                        if (area) val += 100.0f/area;
-                                }
+        if (!((sSplitPlaneStrategy & BALANCED_POLYS) ||
+                  (sSplitPlaneStrategy & LEAST_SPLITS)   ||
+                  (sSplitPlaneStrategy & LARGEST_POLY_AREA) ||
+                  (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)))
+                return val;
+        
+        PolygonContainer::const_iterator it, it_end = polys.end();
+        float sumBalancedPolys = 0;
+        float sumSplits = 0;
+        float sumPolyArea = 0;
+        float sumBalancedViewCells = 0;
+        //float totalArea = 0;
+
+        // container for view cells
+        ObjectContainer frontViewCells;
+        ObjectContainer backViewCells;
+
+        for (it = polys.begin(); it != it_end; ++ it)
+        {
+                int classification = (*it)->ClassifyPlane(candidatePlane);
+
+                if (sSplitPlaneStrategy & BALANCED_POLYS)
+                        sumBalancedPolys += sBalancedPolysTable[classification];
+                
+                if (sSplitPlaneStrategy & LEAST_SPLITS)
+                        sumSplits += sLeastSplitsTable[classification];
+
+                if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
+                {
+                        if (classification == Polygon3::COINCIDENT)
+                        {               
+                                float area = (*it)->GetArea();
+                                //Debug << "polygon area: " << area << " ";
+                                sumPolyArea += area;
                         }
-                }
-                val += sBalancedPolysFactor * fabs(sumBalancedPolys) + 
-                           sLeastSplitsFactor * sumSplits;
-        }
-        
-        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
-        {
-                // store view cells
-                ObjectContainer frontViewCells;
-                ObjectContainer backViewCells;
-
-                float sumBalancedViewCells = 0;
-
-                PolygonContainer::const_iterator it, it_end = polys.end();
+                        //totalArea += area;
+                }
+
+                // order back and front view cells according to classificaion
+                if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+                {
+                        Intersectable *viewCell = (*it)->mParent;
                 
-                for (it = polys.begin(); it != it_end; ++ it)
-                {
-                        int classification = (*it)->ClassifyPlane(candidatePlane);
-                        Intersectable *viewCell = (*it)->mParent;
-                        
-                        if (viewCell && (classification == Polygon3::FRONT_SIDE))
+                        if (classification == Polygon3::FRONT_SIDE)
                                 frontViewCells.push_back(viewCell);
                         else if (viewCell && (classification == Polygon3::BACK_SIDE))
                                 backViewCells.push_back(viewCell);
                 }
-
+        }
+
+        if (sSplitPlaneStrategy & BALANCED_POLYS)
+                val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
+
+        if (sSplitPlaneStrategy & LEAST_SPLITS)    
+                val += sLeastSplitsFactor * sumSplits / (float)polys.size();
+
+        if ((sSplitPlaneStrategy & LARGEST_POLY_AREA) && sumPolyArea) 
+                val += sLargestPolyAreaFactor * (float)polys.size() / sumPolyArea; // HACK
+
+        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+        {
                 // count number of unique view cells
                 sort(frontViewCells.begin(), frontViewCells.end());
@@ -1021 +1021 @@
 
                 ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
-                
+        
                 Intersectable *intersect = NULL;
                 // increase counter for view cells in front of plane
-        for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
+                for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
                 {
                         if (*frontIt != intersect)
@@ -1036 +1036 @@
                 intersect = NULL;
                 // decrease counter for view cells on back side of plane
-        for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
+                for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
                 {
                         if (*backIt != intersect)
                         {
                                 intersect = *backIt;
-                                sumBalancedViewCells -= 1;
+                                sumBalancedViewCells -= 1.0f;
                         }
                 }
 
-                 val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells);
+                val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / 
+                        (float)(frontViewCells.size() + backViewCells.size());
         }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -436 +436 @@
                 @returns number of polygons
         */
-        int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent = NULL);
+        int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent);
 
         /** A ray is cast possible intersecting the tree.
@@ -545 +545 @@
         static float sBalancedViewCellsFactor;
         static float sVerticalSplitsFactor;
+        static float sLargestPolyAreaFactor;
         
 private: