Changeset 384 for trunk/VUT

Timestamp:

11/07/05 01:27:32 (19 years ago)

Author:

mattausch

Message:

fixed bug in pvs criterium, computing real area

Location:

trunk/VUT

Files:

• GtpVisibilityPreprocessor/scripts/default.env (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/Polygon3.cpp (modified) (1 diff)
• GtpVisibilityPreprocessor/src/Polygon3.h (modified) (3 diffs)
• GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp (modified) (4 diffs)
• GtpVisibilityPreprocessor/src/ViewCell.cpp (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (26 diffs)
• GtpVisibilityPreprocessor/src/ViewCellBsp.h (modified) (5 diffs)
• scripts/GtpVisibility.suo (modified) (previous)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -126 +126 @@
         #splitPlaneStrategy 130
         
-        splitPlaneStrategy 1024
+        splitPlaneStrategy 1032
         
         maxPolyCandidates 50
@@ -133 +133 @@
         Termination {
                 # autopartition
-                maxRays 1000
-                maxPolygons 1
+                maxRays 300
+                maxPolygons 0
                 maxDepth 80
                 

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -432 +432 @@
         return count;
 }
+
+float Polygon3::GetArea(const PolygonContainer &cell)
+{
+        float area = 0;
+        PolygonContainer::const_iterator pit;
+
+        for (pit = cell.begin(); pit != cell.end(); ++ pit)
+                area += (*pit)->GetArea();
+
+        return area;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -87 +87 @@
         Vector3 GetNormal() const;
 
-        /** Includes polygons to axis aligned box.
-        */
-        static void IncludeInBox(const PolygonContainer &polys, AxisAlignedBox3 &box);
-
         /** Casts ray to polygon.
         */
         int CastRay(const Ray &ray, float &t, const float nearestT);
 
-        /** Classify polygons with respect to the plane.
-            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+        
+        /** The piercing rays of the polygon are inherited by the child fragments
+                @parm front_piece the front fragment inheriting the front rays
+                @param back_piece the back fragment inheriting the back rays
         */
-        static int ClassifyPlane(const PolygonContainer &polys, const Plane3 &plane);
+        void InheritRays(Polygon3 &front_piece, 
+                                         Polygon3 &back_piece) const;
+
 
         /// vertices are connected in counterclockwise order.
@@ -112 +112 @@
         RayContainer mPiercingRays;
 
-        /** The piercing rays of the polygon are inherited by the child fragments
-                @parm front_piece the front fragment inheriting the front rays
-                @param back_piece the back fragment inheriting the back rays
+
+
+        /** Includes polygons to axis aligned box.
         */
-        void InheritRays(Polygon3 &front_piece, 
-                                         Polygon3 &back_piece) const;
+        static void IncludeInBox(const PolygonContainer &polys, AxisAlignedBox3 &box);
+
+        /** Classify polygons with respect to the plane.
+            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+        */
+        static int ClassifyPlane(const PolygonContainer &polys, const Plane3 &plane);
 
 
@@ -123 +127 @@
         */
         static int ParentObjectsSize(const PolygonContainer &polys);
+
+        static float GetArea(const PolygonContainer &cell);
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -945 +945 @@
         const float objRt = 1.0f; 
          // const overhead for crossing a view cell border
-        const float vcOverhead = 0.01f;
+        const float vcOverhead = 0;//0.01f;
         
         // total area of view cells
@@ -955 +955 @@
 
         ViewCellContainer::const_iterator it, it_end = viewCells.end();
-        PolygonContainer::const_iterator pit;
-
+        
         for (it = viewCells.begin(); it != it_end; ++ it)
         {
@@ -965 +964 @@
                 mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(*it), cell);
 
-                for (pit = cell.begin(); pit != cell.end(); ++ pit)
-                        area += (*pit)->GetArea();
-                
-                renderTime += area * RenderPvs(*(*it), objRt);
+                area = Polygon3::GetArea(cell);
+                
+                renderTime += area * RenderPvs(*(*it), objRt) + vcOverhead;
                 totalArea += area;
         }
@@ -974 +972 @@
         renderTime /= totalArea;
 
-        Debug << "render time without overhead: " << renderTime * 1e-3 << endl;
-        
-        renderTime += (float)viewCells.size() * vcOverhead;
+        //Debug << "render time without overhead: " << renderTime * 1e-3 << endl;
+        //renderTime += (float)viewCells.size() * vcOverhead;
 
         return renderTime;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -65 +65 @@
 ViewCell *ViewCell::ExtrudeViewCell(const Triangle3 &baseTri, const float height)
 {
- int i; 
- // one mesh per view cell
+        // one mesh per view cell
         Mesh *mesh = new Mesh();
         
@@ -86 +85 @@
 
         // add base vertices and calculate top vertices
-                for (i = 0; i < 3; ++ i)
-                 mesh->mVertices.push_back(baseTri.mVertices[i]);
+        for (int i = 0; i < 3; ++ i)
+                mesh->mVertices.push_back(baseTri.mVertices[i]);
         
         // add top vertices     
-                                                                                                                                for (i = 0; i < 3; ++ i)
+        for (int i = 0; i < 3; ++ i)
                 mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
         

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1088 +1088 @@
 
         // use heuristics to find appropriate plane
-        return SelectPlaneHeuristics(leaf, 
-                                         polys, 
-                                                                 rays, 
-                                                                 sMaxPolyCandidates, 
+        return SelectPlaneHeuristics(leaf, polys, rays, sMaxPolyCandidates, 
                                                                  sMaxRayCandidates);
 }
@@ -1109 +1106 @@
         int candidateIdx = limit;
 
+        // only for pvs criterium
+        PolygonContainer cell;
+        vector<Plane3 *> planes;
+        vector<bool> sides;
+        float pvsSize = 0;
+
+        if (sSplitPlaneStrategy & PVS)
+        {
+                ConstructGeometry(leaf, cell);
+                ExtractSplitPlanes(leaf, planes, sides);
+                pvsSize = ComputePvsSize(rays);
+        }
+
         for (int i = 0; i < limit; ++ i)
         {
@@ -1115 +1125 @@
                 // evaluate current candidate
                 const float candidateCost = 
-                        SplitPlaneCost(leaf,
-                                       polys[candidateIdx]->GetSupportingPlane(), 
-                                                   polys, rays);
+                        SplitPlaneCost(polys[candidateIdx]->GetSupportingPlane(), 
+                                                   polys, rays, cell, planes, sides, pvsSize);
 
                 //Debug << polys[candidateIdx] << endl;
@@ -1151 +1160 @@
 
                 const float candidateCost =
-                        SplitPlaneCost(leaf, Plane3(pt[0], pt[1], pt[2]), 
-                                                   polys, rays);
+                        SplitPlaneCost(Plane3(pt[0], pt[1], pt[2]), 
+                                                   polys, rays, cell, planes, sides, pvsSize);
 
                 if (candidateCost < lowestCost)
@@ -1163 +1172 @@
         }
 
+        CLEAR_CONTAINER(cell);
+
         if (chooseFromRays)
         {
@@ -1186 +1197 @@
 }
 
-float BspTree::SplitPlaneCost(BspLeaf *leaf, 
-                                                          const Plane3 &candidatePlane, 
+float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
                                                           const PolygonContainer &polys) const
 {
@@ -1283 +1293 @@
         if (sSplitPlaneStrategy & BALANCED_POLYS)
                 val += sBalancedPolysFactor * fabs(sumBalancedPolys) / (float)polys.size();
-
+        
         if (sSplitPlaneStrategy & LEAST_SPLITS)    
                 val += sLeastSplitsFactor * sumSplits / (float)polys.size();
@@ -1297 +1307 @@
         if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
                 if (totalViewCells != 0)
-                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / 
-                                (float)totalViewCells;
+                        val += sBalancedViewCellsFactor * fabs(sumBalancedViewCells) / (float)totalViewCells;
         
         return val;
@@ -1326 +1335 @@
 }
 
-float BspTree::SplitPlaneCost(BspLeaf *leaf,
-                                                          const Plane3 &candidatePlane, 
-                                                          const BoundedRayContainer &rays) const
+float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
+                                                          const BoundedRayContainer &rays,
+                                                          const float frontArea,
+                                                          const float backArea,
+                                                          const int pvsSize) const
 {
         float val = 0;
@@ -1344 +1355 @@
         Intersectable::NewMail(); const int frontAndBackId = ViewCell::sMailId;
 
-        PolygonContainer cell;
-        PolygonContainer front;
-        PolygonContainer back;
-
-        vector<Plane3 *> planes;
-        vector<bool> sides;
-
-        ExtractSplitPlanes(leaf, planes, sides);
-
-        ConstructGeometry(leaf, cell);
-        ConstructChildGeometry(front, cell, planes, sides, candidatePlane, true);
-        ConstructChildGeometry(back, cell, planes, sides, candidatePlane, false);
-
-        CLEAR_CONTAINER(cell);
-        CLEAR_CONTAINER(front);
-        CLEAR_CONTAINER(back);
-        
         int frontRays = 0;
         int backRays = 0;
-
-        // todo create geometry of left and right leaves
-        
+                
         BoundedRayContainer::const_iterator rit, rit_end = rays.end();
 
@@ -1394 +1386 @@
                                 // assure that we only count a object 
                                 // once for the front and once for the back side of the plane
-                                ComputePvs(*ray->intersections[0].mObject, 
-                                                   frontPvs, 
-                                               backPvs, 
-                                                   cf, 
-                                                   frontId, 
-                                                   backId, 
-                                                   frontAndBackId);
+                                AddToPvs(*ray->intersections[0].mObject, 
+                                                   frontPvs, backPvs, 
+                                                   cf, frontId, backId, frontAndBackId);
                         }
 
                         // the source object in the origin of the ray
-                        ComputePvs(*ray->sourceObject.mObject, 
-                                           frontPvs, 
-                                       backPvs, 
-                                           cf, 
-                                           frontId, 
-                                           backId, 
-                                           frontAndBackId);
-
-                        if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
-                                ++ backRays;
-                        if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
-                                ++ frontRays;
+                        AddToPvs(*ray->sourceObject.mObject, 
+                                           frontPvs, backPvs, 
+                                           cf, frontId, backId, frontAndBackId);
+
+                        if (0)
+                        {
+                                if ((cf == Ray::BACK) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
+                                        ++ backRays;
+                                if ((cf == Ray::FRONT) || (cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
+                                        ++ frontRays;
+                        }
                 }
         }
@@ -1428 +1415 @@
 
         if (sSplitPlaneStrategy & PVS)
-                if (!rays.empty()) // HACK (should divide by maximal possible pvs)
-                        val += sPvsFactor * (frontPvs * (float)frontRays + (backPvs * (float)backRays)) / 
-                        (float)rays.size(); 
+                if (0 && !rays.empty()) // HACK (should divide by maximal possible pvs)
+                        val += sPvsFactor * (frontPvs * (float)frontRays + (backPvs * (float)backRays)) / (float)rays.size(); 
+                else
+                        val += sPvsFactor * (frontPvs * frontArea + (backPvs * backArea)) /
+                                ((frontArea + backArea) * (float)pvsSize);
 
         //Debug << "pvs: " << pvsSize << " val " << val << endl;
@@ -1436 +1425 @@
 }
 
-
-/*void BspTree::CreateChildrenGeometry(PolygonContainer &cell, 
-                                                                         PolygonContainer &front, 
-                                                                         PolygonContainer &back, 
-                                                                         Plane3 &splitPlane)
-{
-}*/
-
-void BspTree::ComputePvs(Intersectable &obj, 
-                                                 float &frontPvs,
-                                                 float &backPvs,
-                                                 const int cf, 
-                                                 const int frontId, 
-                                                 const int backId, 
-                                                 const int frontAndBackId) const
-{
-        if (cf == Ray::COINCIDENT)
+void BspTree::AddToPvs(Intersectable &obj,
+                                           float &frontPvs,
+                                           float &backPvs,
+                                           const int cf, 
+                                           const int frontId, 
+                                           const int backId, 
+                                           const int frontAndBackId) const
+{
+        if (cf == Ray::COINCIDENT) //TODO: really belongs to no pvs?
                 return;
 
@@ -1459 +1440 @@
                 if ((obj.mMailbox != frontId) && 
                         (obj.mMailbox != frontAndBackId))
+                {
                         frontPvs += 1.0;
 
-                if (obj.mMailbox != backId)
-                        obj.mMailbox = frontId;
-                else
-                        obj.mMailbox = frontAndBackId;                                  
+                        if (obj.mMailbox != backId)
+                                obj.mMailbox = frontId;
+                        else
+                                obj.mMailbox = frontAndBackId;                                  
+                }
         }
         else if (cf == Ray::BACK)
@@ -1479 +1462 @@
                 }
         }
+        // object belongs to both pvs
         else if ((cf == Ray::FRONT_BACK) || (cf == Ray::BACK_FRONT))
         {
-                if (obj.mMailbox == backId)
-                        frontPvs += 1.0;
-                else if (obj.mMailbox == frontId)
-                        backPvs += 1.0;
-                else if (obj.mMailbox != frontAndBackId) // can add to both PVS
-                {
-                        frontPvs += 1.0;
-                        backPvs += 1.0;
-                }
-                obj.mMailbox = frontAndBackId;
-        }
-}
-
-float BspTree::SplitPlaneCost(BspLeaf *leaf,
-                                                          const Plane3 &candidatePlane, 
+                if (obj.mMailbox !=  frontAndBackId)
+                {
+                        if (obj.mMailbox != frontId)
+                                frontPvs += 1.0;
+                        if (obj.mMailbox != backId)
+                                backPvs += 1.0;
+                
+                        obj.mMailbox = frontAndBackId;
+                }
+        }
+}
+
+float BspTree::SplitPlaneCost(const Plane3 &candidatePlane, 
                                                           const PolygonContainer &polys,                                                          
-                                                          const BoundedRayContainer &rays) const
+                                                          const BoundedRayContainer &rays,
+                                                          const PolygonContainer &cell,
+                                                          const vector<Plane3 *> &planes,
+                                                          const vector<bool> &sides,
+                                                          const int pvsSize) const
 {
         float val = 0;
@@ -1517 +1503 @@
                 (sSplitPlaneStrategy & BLOCKED_RAYS))
         {
-        val += SplitPlaneCost(leaf, candidatePlane, polys);
+        val += SplitPlaneCost(candidatePlane, polys);
         }
 
@@ -1525 +1511 @@
                 (sSplitPlaneStrategy & PVS))
         {
-                val += SplitPlaneCost(leaf, candidatePlane, rays);
+                float frontArea = 0;
+                float backArea = 0;
+
+                if (sSplitPlaneStrategy & PVS)
+                {
+                        PolygonContainer frontCell;
+                        PolygonContainer backCell;
+
+                        // construct child geometry with regard to the candidate split plane
+                        ConstructChildGeometry(frontCell, cell, planes, sides, candidatePlane, true);
+                        ConstructChildGeometry(backCell, cell, planes, sides, candidatePlane, false);
+
+                        frontArea = Polygon3::GetArea(frontCell);
+                        backArea = Polygon3::GetArea(backCell);
+
+                        CLEAR_CONTAINER(frontCell);
+                        CLEAR_CONTAINER(backCell);
+                }
+                
+                val += SplitPlaneCost(candidatePlane, rays, frontArea, backArea, pvsSize);
         }
 
@@ -2039 +2044 @@
 }
 
-bool BspTree::ConstructChildGeometry(PolygonContainer &newCell,
+bool BspTree::ConstructChildGeometry(PolygonContainer &childCell,
                                                                          const PolygonContainer &cell,
                                                                          const vector<Plane3 *> &planes,
@@ -2049 +2054 @@
         Polygon3 *planePoly = GetBoundingBox().CrossSection(splitPlane);
 
-        bool inside = true;
-
         // polygon is split by all other planes
-        for (int i = 0; (i < planes.size()) && inside; ++ i)
+        for (int i = 0; (i < (int)planes.size()) && planePoly; ++ i)
         {
                 const int cf = planePoly->ClassifyPlane(*planes[i]);
@@ -2080 +2083 @@
                                         }
                                         
-                                        inside = true;
+                                        if (!planePoly->Valid())
+                                                DEL_PTR(planePoly);
                                 }
                                 break;
                         case Polygon3::BACK_SIDE:
                                 if (sides[i]) 
-                                        inside = false;
+                                        DEL_PTR(planePoly);
                                 break;
                         case Polygon3::FRONT_SIDE:
                                 if (!sides[i])
-                                        inside = false;
+                                        DEL_PTR(planePoly);
+                                break;
+                        case Polygon3::COINCIDENT:
                                 break;
                         default:
@@ -2096 +2102 @@
         }
         
-        //-- finally add polygon
-        if (inside)
-                newCell.push_back(planePoly);
-        else
-        {
-                //just copy polygons
-                DEL_PTR(planePoly);
+        if (!planePoly)
+        {
+                //geometry is not changed at all, hence just copy polygons
                 PolygonContainer::const_iterator it, it_end = cell.end();
                 
                 for (it = cell.begin(); it != it_end; ++ it)
-                        newCell.push_back(*it);
+                        childCell.push_back(new Polygon3((*it)->mVertices));
 
                 return false;
         }
 
-        //-- plane poly splits all other candidates
+        //-- plane poly splits all other cell polygons
         for (int i = 0; i < (int)cell.size(); ++ i)
         {
-                inside = true;
-                
                 const int cf = cell[i]->ClassifyPlane(splitPlane);
                         
@@ -2123 +2123 @@
                         case Polygon3::SPLIT:
                                 {
-                                        Polygon3 *poly = new Polygon3(*cell[i]);
+                                        Polygon3 *poly = new Polygon3(cell[i]->mVertices);
 
                                         Polygon3 *frontPoly = new Polygon3();
@@ -2133 +2133 @@
                                         DEL_PTR(poly);
 
-                                        if (sides[i] == true)
+                                        if (side == true)
                                         {
-                                                newCell.push_back(frontPoly);
+                                                poly = frontPoly;
                                                 DEL_PTR(backPoly);
                                         }
                                         else
                                         {
-                                                newCell.push_back(backPoly);
+                                                poly = backPoly;
                                                 DEL_PTR(frontPoly);
                                         }
+                                        if (!poly->Valid())
+                                                DEL_PTR(poly);
+                                        else
+                                                childCell.push_back(poly);
                                 }
+                                
                                 break;
                         case Polygon3::BACK_SIDE:
-                                if (!sides[i]) 
-                                        newCell.push_back(new Polygon3(*cell[i]));
-                        
+                                if (!side) 
+                                        childCell.push_back(new Polygon3(cell[i]->mVertices));                  
                                 break;
                         case Polygon3::FRONT_SIDE:
-                                if (sides[i])
-                                        newCell.push_back(new Polygon3(*cell[i]));
-                                        inside = false;
+                                if (side)
+                                        childCell.push_back(new Polygon3(cell[i]->mVertices));  
+                                break;
+                        case Polygon3::COINCIDENT:
+                                childCell.push_back(new Polygon3(cell[i]->mVertices));
                                 break;
                         default:
+                                
                                 break;
                 }
         }
 
+        //-- finally add the new polygon
+        childCell.push_back(planePoly);
+        
         return true;
 }
@@ -2229 +2239 @@
                                                 DEL_PTR(frontPoly);
                                         }
-                                        inside = true;
+                                        
                                         break;
 
@@ -2239 +2249 @@
                                         if (!sides[j])
                                                 inside = false;
+                                        break;
+                                case Polygon3::COINCIDENT:
                                         break;
                                 default:
@@ -2418 +2430 @@
         return NULL;
 }
+
+int BspTree::ComputePvsSize(const BoundedRayContainer &rays) const
+{
+        int pvsSize = 0;
+
+        BoundedRayContainer::const_iterator rit, rit_end = rays.end();
+
+        Intersectable::NewMail();
+
+        for (rit = rays.begin(); rit != rays.end(); ++ rit)
+        {
+                Ray *ray = (*rit)->mRay;
+                
+                if (!ray->intersections.empty())
+                {
+                        if (!ray->intersections[0].mObject->Mailed())
+                        {
+                                ray->intersections[0].mObject->Mail();
+                                ++ pvsSize;
+                        }
+                }
+                if (!ray->sourceObject.mObject->Mailed())
+                {
+                        ray->sourceObject.mObject->Mail();
+                        ++ pvsSize;
+                }
+        }
+
+        return pvsSize;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -459 +459 @@
                 @returns true if plane contributes to the cell.
         */
-        bool ConstructChildGeometry(PolygonContainer &newCell,
+        bool ConstructChildGeometry(PolygonContainer &childCell,
                                                             const PolygonContainer &cell,
                                                             const vector<Plane3 *> &planes,
@@ -535 +535 @@
         /** Evaluates the contribution of the candidate split plane.
                 
-                @param canditatePlane the candidate split plane
+                @param candidatePlane the candidate split plane
                 @param polys the polygons the split can be based on
                 @param rays the rays the split can be based on
+
                 @returns the cost of the candidate split plane
         */
-        float SplitPlaneCost(BspLeaf *leaf, 
-                                 const Plane3 &candidatePlane,
+        float SplitPlaneCost(const Plane3 &candidatePlane,
                                                  const PolygonContainer &polys,                                                  
-                                                 const BoundedRayContainer &rays) const;
+                                                 const BoundedRayContainer &rays,
+                                                 const PolygonContainer &cell,
+                                                 const vector<Plane3 *> &plane,
+                                                 const vector<bool> &sides,
+                                                 const int pvsSize) const;
 
         /** Strategies where the effect of the split plane is tested
@@ -549 +553 @@
                 @returns the cost of the candidate split plane
         */
-        float SplitPlaneCost(BspLeaf *leaf, 
-                                 const Plane3 &candidatePlane,
+        float SplitPlaneCost(const Plane3 &candidatePlane,
                                                  const PolygonContainer &polys) const;
 
         /** Strategies where the effect of the split plane is tested
             on all input polygons.
+
                 @returns the cost of the candidate split plane
         */
-        float SplitPlaneCost(BspLeaf *leaf,
-                                 const Plane3 &candidatePlane,
-                                                 const BoundedRayContainer &polys) const;
+        float SplitPlaneCost(const Plane3 &candidatePlane,
+                                                 const BoundedRayContainer &rays,
+                                                 const float frontArea,
+                                                 const float backArea,
+                                                 const int pvsSize) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -721 +727 @@
         /** Computes the pvs of the front and back leaf with a given classification.
         */
-        void ComputePvs(Intersectable &obj, 
+        void AddToPvs(Intersectable &obj, 
                                         float &frontPvs,
                                         float &backPvs,
@@ -729 +735 @@
                                         const int frontAndBackId) const;
         
+        int ComputePvsSize(const BoundedRayContainer &rays) const;
+
         /// Pointer to the root of the tree
         BspNode *mRoot;