Changeset 1072

Timestamp:

07/03/06 02:03:59 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• Containers.h (modified) (2 diffs)
• Intersectable.h (modified) (2 diffs)
• KdTree.h (modified) (1 diff)
• ViewCellsManager.cpp (modified) (3 diffs)
• VspBspTree.cpp (modified) (7 diffs)
• VspOspTree.cpp (modified) (9 diffs)
• VspOspTree.h (modified) (4 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/Containers.h

@@ -4 +4 @@
 #include <vector>
 #include <queue>
+#include <map>
 
 using namespace std;
@@ -54 +55 @@
 typedef vector<IndexedBoundingBox> IndexedBoundingBoxContainer;
 
+typedef std::map<int, Intersectable *> ObjectMap;
+
 }
 

GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h

@@ -8 +8 @@
 
 struct VssRayContainer;
+class KdLeaf;
 
 class Intersectable {
@@ -17 +18 @@
   int mMailbox;
   
-  // unique object Id
+  /// unique object Id
   int mId;
   
-  // universal counter
+  /// universal counter
   int mCounter;
         
-  // object based pvs
+  /// object based pvs
   KdPvs mKdPvs;
   
+  /// kd leaves that this intersectable belongs to
+  std::vector<KdLeaf *> mKdLeaves;
+
   enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE };
   

GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h

@@ -188 +188 @@
   /** pointers to occluders contained in this node */
   ObjectContainer mObjects;
-  
+
+  /** Objects that are part of several leaves.
+  */
+  ObjectMap mMultipleObjects;
+
   /** Ray set description of the rays passing through this node */
   PassingRaySet mPassingRays;

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

@@ -5253 +5253 @@
 
                         // export rays
-                        if (1 && mExportRays)
+                        if (0 && mExportRays)
                         {
                                 exporter->ExportRays(visRays, RgbColor(0, 1, 0));
@@ -5262 +5262 @@
                         // HACK: export without clip plane
                         const bool b = mUseClipPlaneForViz;
-                        mUseClipPlaneForViz = false;
+                        if (0)
+                                mUseClipPlaneForViz = false;
 
                         ExportViewCellsForViz(exporter);
@@ -5336 +5337 @@
 
                                 raysOut = min((int)rays.size(), 100);
-
-                                Debug  << "here12 " << raysOut << endl;
 
                                 // collect intial view cells

GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

@@ -1230 +1230 @@
                         ++ contributingSamples;
                 
+                // note: vss rays are never deleted
                 if (0) leaf->mVssRays.push_back(new VssRay(*ray));
         }
@@ -1610 +1611 @@
                                         bestAxis = axis;
                                 }
-                                else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                                /*else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                                {
                                         Debug << "taking split along longest axis (" << bestAxis << ") instead of  (" << axis << ")" << endl;
-                                
+                                }*/
+
                         }
                         else
@@ -1629 +1632 @@
 
         //-- assign values
+
         axis = bestAxis;
         pFront = nProbFront[bestAxis];
@@ -1646 +1650 @@
 
         //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
-        //Debug << "!!!!!!!!!!!!!!" << endl;
+
         return nCostRatio[bestAxis];
 }
@@ -1659 +1663 @@
 {
         // HACK matt: subdivide regularily to certain depth
-        if (data.mDepth < 0)    
-        {
-                cout << "d: " << data.mDepth << endl;
+        if (data.mDepth < 0)    // question matt: why depth < 0 ?
+        {
+                cout << "depth: " << data.mDepth << endl;
+
                 // return axis aligned split
                 AxisAlignedBox3 box;
@@ -1675 +1680 @@
                 bestPlane = Plane3(norm, position);
                 splitAxis = axis;
+
                 return true;
         }
@@ -2509 +2515 @@
 
 
-void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
+void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, 
+                                                                  bool onlyValid) const
 {
         ViewCell::NewMail();

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

@@ -777 +777 @@
                         ++ contributingSamples;
                 
+                // warning: rays get never deleted!
                 if (0) leaf->mVssRays.push_back(new VssRay(*ray));
         }
@@ -803 +804 @@
         float pos;
 
-        // float values => don't compare with exact values
         if (0)
         {
+                // float values => don't compare with exact values
                 minBand += Limits::Small;
                 maxBand -= Limits::Small;
@@ -816 +817 @@
                                 
                 pos = (*ri).ExtrapOrigin(axis);
-                // clamp to min / max band
-                if (0) ClipValue(pos, minBand, maxBand);
                 
+                if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
                                                                         pos, (*ri).mRay));
 
                 pos = (*ri).ExtrapTermination(axis);
-                // clamp to min / max band
-                if (0) ClipValue(pos, minBand, maxBand);
+
+                if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
 
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
@@ -831 +831 @@
 
         stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
+}
+
+
+int VspTree::GetPvsContribution(Intersectable *object) const
+{
+    int pvsContri = 0;
+
+        KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
+
+        Intersectable::NewMail();
+
+        // Search kd leaves this object is attached to
+        for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+        {
+                KdNode *l = (*kit).first;
+
+                // new object found during sweep 
+                // => increase pvs contribution of this kd node
+                if (!l->Mailed())
+                {
+                        l->Mail();
+                        ++ pvsContri;
+                }
+        }
+
+        return pvsContri;
+}
+
+
+void VspTree::PrepareHeuristics(const RayInfoContainer &rays)
+{       
+        ObjectContainer objects;
+
+        // Collect all pvs that can be seen from the view cell
+        CollectPvs(rays, objects);
+
+        // adjust kd node info table
+        // for each object the entry must be updated 
+        // which belongs to the same kd nodes
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *obj = *oit;
+                // TODO
+                //UpdateKdNodeInfo(obj);
+        }
+}
+
+
+int VspTree::GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes)
+{
+        // TODO:
+        // use kd info table to apply set theory in order to
+        // sort out dublicate pvs entries due to objects which
+        // belong to more than one kd leaves.
+#if TODO
+        KdPvsMap::const_iterator kit, kit_end = obj->mKdPvs.mEntries.end();
+
+        // Search kd leaves this object is attached to
+        for (kit = obj->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+        {
+                KdNode *l = (*kit).first;
+
+                // new object found during sweep 
+                // => increase pvs contribution of this kd node
+                if (!l->Mailed())
+                {
+                        l->Mail();
+                        ++ pvsContr;
+                }
+        }
+#endif
+        return 0;
 }
 
@@ -875 +949 @@
         RayInfoContainer::const_iterator ri, ri_end = rays.end();
 
-        // set all object as belonging to the front pvs
+        //-- set all object as belonging to the front pvs
+
         for(ri = rays.begin(); ri != ri_end; ++ ri)
         {
@@ -1015 +1090 @@
 
 
+void VspTree::EvalPvsIncr(ObjectMap &multipleObjects,
+                                                  KdLeaf *leaf, 
+                                                  const SortableEntry &ci,
+                                                  int &pvsLeft,
+                                                  int &pvsRight) const
+{
+        int pvsSize = 0;
+
+        if (ci.type == SortableEntry::ERayMin)
+        {
+                if (!leaf->Mailed())
+                {
+                        leaf->Mail();
+                        pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
+
+                        // add duplicates
+                        ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+
+                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+                        {
+                                const int id = (*oit)->first;
+                                Intersectable *object = (*oit)->second;
+
+                                if (multipleObjects[id] != object) // object not previously in pvs
+                                {
+                                        multipleObjects[id] = object;
+                                        ++ pvsLeft;
+                                }
+
+                        }
+                }                                       
+        }
+        else if (ci.type == SortableEntry::ERayMax)
+        {
+                if (-- leaf->mCounter == 0)
+                        pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
+        }
+}
+
+
+float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays,
+                                                                        const AxisAlignedBox3 &box,
+                                                                        const int pvsSize,
+                                                                        const int axis,
+                                                                        float &position)
+{
+        const float minBox = box.Min(axis);
+        const float maxBox = box.Max(axis);
+
+        const float sizeBox = maxBox - minBox;
+
+        const float minBand = minBox + mMinBand * sizeBox;
+        const float maxBand = minBox + mMaxBand * sizeBox;
+
+        SortSplitCandidates(rays, axis, minBand, maxBand);
+
+        // go through the lists, count the number of objects left and right
+        // and evaluate the following cost funcion:
+        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
+
+        int pvsl = 0;
+        int pvsr = pvsSize;
+
+        int pvsBack = pvsl;
+        int pvsFront = pvsr;
+
+        float sum = (float)pvsSize * sizeBox;
+        float minSum = 1e20f;
+
+        
+        // if no good split can be found, take mid split
+        position = minBox + 0.5f * sizeBox;
+        
+        // the relative cost ratio
+        float ratio = /*Limits::Infinity;*/99999999.0f;
+        bool splitPlaneFound = false;
+
+        Intersectable::NewMail();
+        KdNode::NewMail();
+
+        RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+        //-- set all kd nodes as belonging to the front pvs
+
+        for (ri = rays.begin(); ri != ri_end; ++ ri)
+        {
+                Intersectable *oObject = (*ri).mRay->mOriginObject;
+
+                if (oObject)
+                {
+                        KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+                
+                        for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+                        {
+                                KdNode *node = (*kit).first;
+
+                                if (!node->Mailed())
+                                {
+                                        node->Mail();
+                                        //node->mCounter = 1;
+                                }
+                                else
+                                {
+                                        //++ node->mCounter;
+                                }
+                        }       
+                }
+
+                Intersectable *tObject = (*ri).mRay->mTerminationObject;
+
+                if (tObject)
+                {
+                        KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+                
+                        for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+                        {
+                                KdNode *node = (*kit).first;
+
+                                if (!node->Mailed())
+                                {
+                                        node->Mail();
+                                        //node->mCounter = 1;
+                                }
+                                else
+                                {
+                                        //++ node->mCounter;
+                                }
+                        }       
+                }
+        }
+
+        Intersectable::NewMail();
+
+        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
+
+        ObjectMap multipleObjectsLeft, multipleObjectsRight;
+
+
+        // -- traverse through visibility events
+
+        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
+        {
+                VssRay *ray;
+                ray = (*ci).ray;
+                
+                Intersectable *oObject = ray->mOriginObject;
+                
+                KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
+
+                if (oObject)
+                {       
+                        for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+                        {
+                KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
+
+                                EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr);
+                        }
+                }
+
+                Intersectable *tObject = ray->mOriginObject;
+
+                if (tObject)
+                {       
+                        for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
+                        {
+                                KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
+
+                                EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr);
+                        }
+                }
+
+
+                // Note: sufficient to compare size of bounding boxes of front and back side?
+                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+                {
+                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
+
+                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+                        //Debug << "cost= " << sum << endl;
+
+                        if (sum < minSum)
+                        {
+                                splitPlaneFound = true;
+
+                                minSum = sum;
+                                position = (*ci).value;
+                                
+                                pvsBack = pvsl;
+                                pvsFront = pvsr;
+                        }
+                }
+        }
+        
+        
+        // -- compute cost
+
+        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+        const float pOverall = sizeBox;
+        const float pBack = position - minBox;
+        const float pFront = maxBox - position;
+
+        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        
+        const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
+        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+        if (splitPlaneFound)
+        {
+                ratio = newRenderCost / oldRenderCost;
+        }
+        //if (axis != 1)
+        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+
+        return ratio;
+}
+
+
+#if TODO
+
+float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays,
+                                                                                                          const AxisAlignedBox3 &box,
+                                                                                                          const int pvsSize,
+                                                                                                          const int axis,
+                                                                                                          float &position)
+{
+        const float minBox = box.Min(axis);
+        const float maxBox = box.Max(axis);
+
+        const float sizeBox = maxBox - minBox;
+
+        const float minBand = minBox + mMinBand * sizeBox;
+        const float maxBand = minBox + mMaxBand * sizeBox;
+
+        SortSplitCandidates(rays, axis, minBand, maxBand);
+
+        // go through the lists, count the number of objects left and right
+        // and evaluate the following cost funcion:
+        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
+
+        int pvsl = 0;
+        int pvsr = pvsSize;
+
+        int pvsBack = pvsl;
+        int pvsFront = pvsr;
+
+        float sum = (float)pvsSize * sizeBox;
+        float minSum = 1e20f;
+
+        
+        // if no good split can be found, take mid split
+        position = minBox + 0.5f * sizeBox;
+        
+        // the relative cost ratio
+        float ratio = /*Limits::Infinity;*/99999999.0f;
+        bool splitPlaneFound = false;
+
+        Intersectable::NewMail();
+
+        RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+        //-- set all object as belonging to the front pvs
+
+        for(ri = rays.begin(); ri != ri_end; ++ ri)
+        {
+                // Note: sufficient to compare size of bounding boxes of front and back side?
+                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+                {
+                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
+
+                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
+                        //Debug << "cost= " << sum << endl;
+
+                        if (sum < minSum)
+                        {
+                                splitPlaneFound = true;
+
+                                minSum = sum;
+                                position = (*ci).value;
+                                
+                                pvsBack = pvsl;
+                                pvsFront = pvsr;
+                        }
+                }
+        }
+
+        
+        // -- compute cost
+
+        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+        const float pOverall = sizeBox;
+        const float pBack = position - minBox;
+        const float pFront = maxBox - position;
+
+        
+        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        
+        const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
+        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+        if (splitPlaneFound)
+        {
+                ratio = newRenderCost / oldRenderCost;
+        }
+        //if (axis != 1)
+        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+
+        return ratio;
+}
+#endif
+
+
 float VspTree::SelectSplitPlane(const VspTraversalData &tData,
                                                                 AxisAlignedPlane &plane,
@@ -1699 +2095 @@
 
 
+void VspTree::CollectPvs(const RayInfoContainer &rays, 
+                                                 ObjectContainer &objects) const
+{
+        RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
+        Intersectable::NewMail();
+
+        for (rit = rays.begin(); rit != rays.end(); ++ rit)
+        {
+                VssRay *ray = (*rit).mRay;
+
+                Intersectable *object;
+                object = ray->mOriginObject;
+
+        if (object)
+                {
+                        if (!object->Mailed())
+                        {
+                                object->Mail();
+                                objects.push_back(object);
+                        }
+                }
+
+                object = ray->mTerminationObject;
+
+                if (object)
+                {
+                        if (!object->Mailed())
+                        {
+                                object->Mail();
+                                objects.push_back(object);
+                        }
+                }
+        }
+}
+
+
 int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
 {
@@ -2576 +3009 @@
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
                   << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
+                  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
                   << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
                   << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
@@ -2586 +3019 @@
 
 
+
 /*********************************************************************/
 /*                class HierarchyManager implementation              */
 /*********************************************************************/
+
+
 
 HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

@@ -868 +868 @@
                                                    float &pBack);
 
-        /** Sorts split candidates for surface area heuristics for axis aligned splits.
+        /** Sorts split candidates along the specified axis.
+                The split candidates are generated on possible visibility
+                events (i.e., where ray segments intersect the ray boundaries).
+                The sorted candidates are needed to compute the SAH.
+
                 @param polys the input for choosing split candidates
                 @param axis the current split axis
@@ -877 +881 @@
                                                          float minBand, 
                                                          float maxBand);
+
+        /** Prepares objects for SAH.
+        */
+        void PrepareHeuristics(const RayInfoContainer &rays);
+
+        /** Computes pvs increase with respect to the previous pvs for SAH.
+        */
+        int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);
+
+        /** Returns absolute pvs contribution of this object.
+        */
+        int GetPvsContribution(Intersectable *object) const;
 
         /** Computes best cost for axis aligned planes.
@@ -886 +902 @@
                                                                   float &position);
 
+        float EvalKdCostHeuristics(const RayInfoContainer &rays,
+                                                           const AxisAlignedBox3 &box,
+                                                           const int pvsSize,
+                                                           const int axis,
+                                                           float &position);
+         void EvalPvsIncr(ObjectMap &multipleObjects,
+                                          KdLeaf *leaf, 
+                                          const SortableEntry &ci,
+                                          int &pvsLeft,
+                                          int &pvsRight) const;
+
+
         /** Subdivides the rays into front and back rays according to the split plane.
                 
@@ -918 +946 @@
         */
         int ComputePvsSize(const RayInfoContainer &rays) const;
+        
+        /** Collects pvs from rays.
+        */
+        void CollectPvs(const RayInfoContainer &rays,
+                                        ObjectContainer &objects) const;
 
         /** Returns true if tree can be terminated.