Changeset 491 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

01/03/06 18:37:32 (19 years ago)

Author:

mattausch

Message:

 

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (12 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -34 +34 @@
 
 float BspMergeCandidate::sOverallCost = 0;
+
+
+/// Adds object to the pvs of the front and back node
+inline void AddObject2Pvs(Intersectable *object,
+                                                  const int side,
+                                                  int &pvsBack,
+                                                  int &pvsFront)
+{
+        if (!object)
+                return;
+
+        if (side <= 0)
+        {
+                if (!object->Mailed() && !object->Mailed(2))
+                {
+                        ++ pvsBack;
+
+                        if (object->Mailed(1))
+                                object->Mail(2);
+                        else
+                                object->Mail();
+                }
+        }
+
+        if (side >= 0)
+        {
+                if (!object->Mailed(1) && !object->Mailed(2))
+                {
+                        ++ pvsFront;
+
+                        if (object->Mailed())
+                                object->Mail(2);
+                        else
+                                object->Mail(1);
+                }
+        }
+}
+
 
 /****************************************************************/
@@ -509 +547 @@
 
         // subdivide polygons
-        mStat.splits += SplitPolygons(interior->GetPlane(),
-                                                                  *tData.mPolygons,
-                                          *frontData.mPolygons,
-                                                                  *backData.mPolygons,
-                                                                  coincident);
+        SplitPolygons(interior->GetPlane(),
+                                  *tData.mPolygons,
+                      *frontData.mPolygons,
+                                  *backData.mPolygons,
+                                  coincident);
 
 
@@ -755 +793 @@
 
 float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
-                                                                                 const VspBspTraversalData &tData)
+                                                                                 const VspBspTraversalData &tData,
+                                                                                 int &bestAxis)
 {
         AxisAlignedBox3 box;
@@ -771 +810 @@
         float nPosition[3];
         float nCostRatio[3];
-        int bestAxis = -1;
+        bestAxis = -1;
 
         const int sAxis = box.Size().DrivingAxis();
@@ -815 +854 @@
         Vector3 normal(0,0,0); normal[bestAxis] = 1;
         plane = Plane3(normal, nPosition[bestAxis]);
-
+        
         return nCostRatio[bestAxis];
 }
+
+
+float VspBspTree::EvalCostRatio(const VspBspTraversalData &tData,
+                                                                const AxisAlignedBox3 &box,
+                                                                const int axis,
+                                                                const float position,
+                                                                int &raysBack,
+                                                                int &raysFront,
+                                                                int &pvsBack,
+                                                                int &pvsFront)
+{
+        raysBack = 0;
+        raysFront = 0;
+        pvsFront = 0;
+        pvsBack = 0;
+
+        Intersectable::NewMail(3);
+
+        // eval pvs size
+        const int pvsSize = tData.mPvs;
+
+        // create unique ids for pvs heuristics
+        GenerateUniqueIdsForPvs();
+
+        // this is the main ray classification loop!
+        for(RayInfoContainer::iterator ri = tData.mRays->begin();
+                        ri != tData.mRays->end(); ++ ri)
+        {
+                if (!(*ri).mRay->IsActive())
+                        continue;
+
+                // determine the side of this ray with respect to the plane
+                float t;
+                int side = (*ri).ComputeRayIntersection(axis, position, t);
+                        
+                if (side <= 0)
+                        ++ raysBack;
+
+                if (side >= 0)
+                        ++ raysFront;
+
+                AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
+        }
+
+        //-- only one of these options should be one
+
+        if (0) //-- only pvs
+        {
+                const float sum = float(pvsBack + pvsFront);
+                const float oldCost = (float)pvsSize;
+
+                return sum / oldCost;
+        }
+
+        //-- pvs + probability heuristics
+        float pBack, pFront, pOverall;
+
+        if (0)
+        {
+                // box length substitute for probability
+                const float minBox = box.Min(axis);
+                const float maxBox = box.Max(axis);
+
+                pBack = position - minBox;
+                pFront = maxBox - position;
+                pOverall = maxBox - minBox;
+        }
+
+        if (1) //-- area substitute for probability
+        {
+                
+                const bool useMidSplit = true;
+                //const bool useMidSplit = false;
+                        
+                pOverall = box.SurfaceArea();
+                        
+                if (!useMidSplit)
+                {
+                        Vector3 pos = box.Max(); pos[axis] = position;
+                        pBack = AxisAlignedBox3(box.Min(), pos).SurfaceArea();
+
+                        pos = box.Min(); pos[axis] = position;
+                        pFront = AxisAlignedBox3(pos, box.Max()).SurfaceArea();
+                }
+                else
+                {
+                        //-- simplified computation for mid split
+                        const int axis2 = (axis + 1) % 3;
+                        const int axis3 = (axis + 2) % 3;
+
+                        const float faceArea = 
+                                (box.Max(axis2) - box.Min(axis2)) *
+                                (box.Max(axis3) - box.Min(axis3));
+
+                        pBack = pFront = pOverall * 0.5f + faceArea;
+                }
+        }
+
+        //-- ray density substitute for probability
+        if (0)
+        {
+                pBack = (float)raysBack;
+                pFront = (float)raysFront;
+                pOverall = (float)tData.mRays->size();
+        }
+
+        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
+        //Debug << pFront << " " << pBack << " " << pOverall << endl;
+
+        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
+        const float newCost = pvsBack * pBack + pvsFront * pFront;
+        //  float oldCost = leaf->mRays.size();
+        const float oldCost = (float)pvsSize * pOverall;
+
+        return  (mCtDivCi + newCost) / oldCost;
+}
+
 
 
@@ -835 +991 @@
                         return true;
                 }
-                else
-                {
-                        //-- choose plane on midpoint of a ray
-                        const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1));
-
-                        const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin();
-                        const Vector3 maxPt = (*data.mRays)[candidateIdx].ExtrapTermination();
-
-                        const Vector3 pt = (maxPt + minPt) * 0.5;
-
-                        const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir();
-
-                        plane = Plane3(normal, pt);
-                        return true;
-                }
-
-                return false;
         }
 
@@ -938 +1077 @@
         // intermediate plane
         Plane3 plane;
+        bool useAxisAlignedPlane = false;
 
         const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
@@ -967 +1107 @@
         }
 
-#if 0
-        //-- choose candidate planes extracted from rays
-        //-- different methods are available
-        for (int i = 0; i < mMaxRayCandidates; ++ i)
-        {
-                plane = ChooseCandidatePlane3(*data.mRays);
-                candidateCost = SplitPlaneCost(plane, data);
-
-                if (candidateCost < lowestCost)
-                {
-                        bestPlane = plane;
-                        lowestCost = candidateCost;
-                }
-        }
-#endif
-
-        // axis aligned splits
-        candidateCost = SelectAxisAlignedPlane(plane, data);
+        //-- axis aligned splits
+        int axis;
+        candidateCost = SelectAxisAlignedPlane(plane, data, axis);
 
         if (candidateCost < lowestCost)
-        {
+        {       
+                if (!useAxisAlignedPlane)
+                {
+                        useAxisAlignedPlane = true;
+                        //! error also computed if cost ratio is missed
+                        ++ mStat.splits[axis];
+                }
+
                 bestPlane = plane;
                 lowestCost = candidateCost;
@@ -1031 +1163 @@
         if (mSplitPlaneStrategy & PVS)
         {
+// matt: change back!!
+Intersectable::NewMail(3);
                 // create unique ids for pvs heuristics
-                GenerateUniqueIdsForPvs();
+                //GenerateUniqueIdsForPvs();
 
                 if (mPvsUseArea) // use front and back cell areas to approximate volume
@@ -1056 +1190 @@
         bool useRand;
 
-        // choose test polyongs randomly if over threshold
+        // choose test rays randomly if too much
         if ((int)data.mRays->size() > mMaxTests)
         {
@@ -1095 +1229 @@
 
                         // add the termination object
-                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
+                        //AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
+                        AddObject2Pvs(ray->mTerminationObject, cf, frontPvs, backPvs);
                         // add the source object
-                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
-
-                        // use number or length of rays to approximate volume
+                        //AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
+
+                        // use number of rays to approximate volume
                         if (!mPvsUseArea)
                         {
-                                float len = 1;
-
-                                if (pvsUseLen) // use length of rays
-                                        len = rayInf.SqrSegmentLength();
-
-                                pOverall += len;
-
-                                if (cf == 1)
-                                        pFront += len;
-                                else if (cf == -1)
-                                        pBack += len;
-                                else if (cf == 0)
-                                {
-                                        // use length of rays to approximate volume
-                                        if (pvsUseLen)
-                                        {
-                                                float newLen = len *
-                                                        (rayInf.GetMaxT() - t) /
-                                                        (rayInf.GetMaxT() - rayInf.GetMinT());
-
-                                                if (candidatePlane.Side(rayInf.ExtrapOrigin()) <= 0)
-                                                {
-                                                        pBack += newLen;
-                                                        pFront += len - newLen;
-                                                }
-                                                else
-                                                {
-                                                        pFront += newLen;
-                                                        pBack += len - newLen;
-                                                }
-                                        }
-                                        else
-                                        {
-                                                ++ pFront;
-                                                ++ pBack;
-                                        }
-                                }
+                                ++ pOverall;
+
+                                if (cf >= 0)
+                                        ++ pFront;
+                                if (cf <= 0)
+                                        ++ pBack;
                         }
                 }
@@ -1215 +1319 @@
         }
 }
+
 
 void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves) const