Changeset 1137 for GTP/trunk/Lib/Vis/Preprocessing

Timestamp:

07/17/06 18:17:09 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing

Files:

• scripts/Preprocessor.vcproj (modified) (1 diff)
• src/VspBspTree.cpp (modified) (3 diffs)
• src/VspOspTree.cpp (modified) (21 diffs)
• src/VspOspTree.h (modified) (8 diffs)

GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj

@@ -206 +206 @@
                         </File>
                         <File
-                                RelativePath="..\src\KdIntersectable.cpp">
-                        </File>
-                        <File
-                                RelativePath="..\src\KdIntersectable.h">
-                        </File>
-                        <File
                                 RelativePath="..\src\KdTree.cpp">
                         </File>

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

@@ -1264 +1264 @@
         mLocalSplitCandidates->reserve(requestedSize);
 
-        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;
@@ -1277 +1274 @@
         {
                 const bool positive = (*ri).mRay->HasPosDir(axis);
-                                
-                pos = (*ri).ExtrapOrigin(axis);
+                float pos = (*ri).ExtrapOrigin(axis);
+
                 // clamp to min / max band
                 if (0) ClipValue(pos, minBand, maxBand);
@@ -1286 +1283 @@
 
                 pos = (*ri).ExtrapTermination(axis);
+
                 // clamp to min / max band
                 if (0) ClipValue(pos, minBand, maxBand);

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

@@ -934 +934 @@
         float pos;
 
+        RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
         //-- insert all queries
-        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
-        {
-                const bool positive = (*ri).mRay->HasPosDir(axis);
+        for (rit = rays.begin(); rit != rit_end; ++ rit)
+        {
+                const bool positive = (*rit).mRay->HasPosDir(axis);
                                 
-                pos = (*ri).ExtrapOrigin(axis);
+                pos = (*rit).ExtrapOrigin(axis);
                 
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
-                                                                        pos, (*ri).mRay));
-
-                pos = (*ri).ExtrapTermination(axis);
+                                                                        pos, (*rit).mRay));
+
+                pos = (*rit).ExtrapTermination(axis);
 
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
-                                                                        pos, (*ri).mRay));
+                                                                        pos, (*rit).mRay));
         }
 
@@ -1005 +1007 @@
 
                 //-- the objects belonging to several leaves must be handled seperately
+
                 ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end();
 
@@ -2625 +2628 @@
 
 
-/*****************************************************************/
-/*                class OspTree implementation                   */
-/*****************************************************************/
+void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
+{
+        // if no precomputation of view cells
+        CastLineSegment(ray.mOrigin, ray.mTermination, viewCells);
+}
+
+
+/*******************************************************************/
+/*                  class OspTree implementation                   */
+/*******************************************************************/
 
 
@@ -3009 +3019 @@
   
         const int totalPvs = tData.mNode->mObjects.size();
-
-                                
+        
+        int pvsl = 0;
+        int pvsr = totalPvs;
+
         // if no good split can be found, take mid split
-        int pvsBack = totalPvs / 2;
+        position = minBox + 0.5f * sizeBox;
         
         // the relative cost ratio
@@ -3023 +3035 @@
         float volFront = volr;
 
+        int pvsBack = 0;
+        int pvsFront = 0;
+        
+
         float sum = (float)totalVol * sizeBox;
 
-        int currentPvs = 0;
-
         Intersectable::NewMail();
-
-        //-- traverse through visibility events
+        ViewCell::NewMail();
+
+        //-- traverse through events and find best split plane
 
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci, ++ currentPvs)
+        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
         {
                 Intersectable *object = (*ci).mObject;
 
-                // new object in this node -> add to the pvs
-                if (!object->Mailed())
-                {
-                        object->Mail();
-                        ++ currentPvs;
-                }
-
-                EvalViewCellVolumeIncr(*ci, voll, volr);
+                EvalHeuristicsContribution(*ci, voll, volr, pvsl, pvsr);
 
                 cout << "incr: " << ci->mObject->mViewCellPvs.GetSize() << " obj id " 
@@ -3053 +3061 @@
                 {
                         //sum = costl * ((*ci).value - minBox) + costr * (maxBox - (*ci).value);
-                        sum = voll * currentPvs + volr * (totalPvs - currentPvs);
-
-                        cout << "pos=" << currentPvs << "\t volt=(" <<  voll << "," 
-                                 << volr << ")" << "\t volt= " << sum << endl;
+                        sum = voll * pvsBack + volr * pvsFront;
+
+                        cout << "pos: " << (*ci).mPos 
+                                 << "\t (pvsl: " << pvsBack << ", pvsr: " << pvsFront << ")"
+                                 << "\t (voll: " << voll << ", volr: " << volr << ")"
+                                 << "\t sum: " << sum << endl;
 
                         if (sum < minSum)
@@ -3063 +3073 @@
 
                                 minSum = sum;
-                                pvsBack = currentPvs;
+
+                                pvsBack = pvsl;
+                                pvsFront = pvsr;
                                 
                                 volBack = voll;
                                 volFront = volr;
-                        }
-                }
-        }
-        
+
+                                position = (*ci).mPos;
+                        }
+                }
+        }
+        
+
         //-- compute cost
 
@@ -3081 +3096 @@
 
         const float penaltyOld = (float)totalPvs;//EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = (float)totalPvs - pvsBack;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = (float)pvsFront;//EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
         const float penaltyBack = (float)pvsBack;//EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
         
@@ -3113 +3128 @@
         KdLeaf *leaf = tData.mNode;
 
-        int requestedSize = 2 * (int)rays->size();
+        int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
 
         // creates a sorted split candidates array
@@ -3127 +3142 @@
         float pos;
 
-        //-- insert all queries
-        for (RayInfoContainer::const_iterator ri = rays->begin(); ri < rays->end(); ++ ri)
-        {
-                const bool positive = (*ri).mRay->HasPosDir(axis);
-                                
-                pos = (*ri).ExtrapOrigin(axis);
-        
-
-                //if (mOspTree->GetLeaf() == leaf)
-
-        /*      mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
-                                                                        pos, (*ri).mRay));
-
-                pos = (*ri).ExtrapTermination(axis);
-
-                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
-                                                                        pos, (*ri).mRay));*/
+        //-- insert ray queries
+        //-- we are intersested only in rays which intersect an object that
+        //-- is part of the kd node because they can induce a change in view cell
+        //-- volume on the left and the right part. 
+        //-- Note that they cannot induce a change in pvs size!!
+
+        RayInfoContainer::const_iterator rit, rit_end = rays->end();
+
+        for (rit = rays->begin(); rit < rit_end; ++ rit)
+        {
+                VssRay *ray = (*rit).mRay;
+
+                const bool positive = ray->HasPosDir(axis);
+                
+                // if hitpoint with object is inside this node
+                if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
+                {
+                        pos = ray->mOrigin[axis];
+        
+                        mSplitCandidates->push_back(
+                                SortableEntry(SortableEntry::BOX_INTERSECT, 
+                                                          pos, 
+                                                          ray->mOriginObject, 
+                                                          ray)
+                                                          );
+                }
+
+                if (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf)
+                {
+                        pos = ray->mTermination[axis];
+
+                        mSplitCandidates->push_back(
+                                SortableEntry(SortableEntry::BOX_INTERSECT, 
+                                                          pos, 
+                                                          ray->mOriginObject, 
+                                                          ray)
+                                                          );
+                }
+        }
+
+
+        //-- insert object queries
+        //-- These queries can induce a change in pvs size.
+        //-- Note that they cannot induce a change in view cell volume, as
+        //-- there is no ray associated with these events!!
+
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+    for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit ) 
+        {
+                Intersectable *object = *oit;
+                const AxisAlignedBox3 box = object->GetBox();
+
+                mSplitCandidates->push_back(
+                        SortableEntry(SortableEntry::BOX_MIN,
+                                                  box.Min(axis),
+                                                  object,
+                                                  NULL)
+                                                  );
+   
+    
+                mSplitCandidates->push_back(
+                        SortableEntry(SortableEntry::BOX_MAX,
+                                                  box.Max(axis),
+                                                  object,
+                                                  NULL)
+                                                  );
         }
 
@@ -3150 +3215 @@
 
 
-float OspTree::PrepareHeuristics(Intersectable *object)
-{
-        if (mUseEqualWeightForHeuristics)
-        {       
-                // like sah: each object has weight one for heuristics
-                return 1;
-        }
-        else
-        {
-                // the priotity of the object is the sum of view cells 
-                // weighted per their volume
-                float vol = 0;
-                return vol;
-                //return object->mViewCellPvs.GetSize();
-        }
-}
-
-
 const OspTreeStatistics &OspTree::GetStatistics() const
 {
@@ -3174 +3221 @@
 
 
-float OspTree::PrepareHeuristics(const ObjectContainer &objects)
+float OspTree::PrepareHeuristics(const VssRay &ray)
+{
+        float vol = 0;
+
+        ViewCellContainer viewCells;
+
+        mVspTree->GetViewCells(ray);
+    
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                ViewCell *vc = (*vit);
+
+                if (!vc->Mailed())
+                {
+                        vc->Mail();
+                        vc->mCounter = 0;
+                        vol += vc->GetVolume();
+                }
+        }
+
+        return vol;
+}
+
+
+float OspTree::PrepareHeuristics(const OspTraversalData &tData)
 {       
         Intersectable::NewMail();
@@ -3181 +3254 @@
         float vol = 0;
 
-        ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-        //-- set all view cell volume as belonging to front volume
-        for (oit = objects.begin(); oit != oit_end; ++ oit)
-        {
-                Intersectable *obj = *oit;
-                vol += PrepareHeuristics(obj);          
+        KdLeaf *leaf = tData.mNode;
+
+        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
+
+        for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
+        {
+                VssRay *ray = (*rit).mRay;
+
+                // if hitpoint with one of the objects is inside this node, we
+                // evaluate the volume of the view cells seen by this ray
+                if ((GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf) ||
+                        (GetLeaf(ray->mTermination, ray->mTerminationNode) == leaf))
+                {
+            vol += PrepareHeuristics(ray);
+                }
         }
 
@@ -3194 +3275 @@
 
 
-void OspTree::EvalViewCellVolumeIncr(const SortableEntry &ci,
-                                                                         float &volLeft,
-                                                                         float &volRight) const
+void OspTree::EvalHeuristicsContribution(const SortableEntry &ci,
+                                                                                 float &volLeft,
+                                                                                 float &volRight,
+                                                                                 int &pvsLeft,
+                                                                                 int &pvsRight)
 {
         Intersectable *obj = ci.mObject;
+        VssRay *ray = ci.mRay;
 
         switch (ci.mType) 
         {
+                // add reverse pvs to left side of split plane
                 case SortableEntry::BOX_MIN:
-                        AddContriToPvs(obj, volLeft);
+                        ++ pvsLeft;
                         break;
                         
                 case SortableEntry::BOX_MAX:
-                        RemoveContriFromPvs(obj, volRight);
+                        -- pvsRight;
                         break;
+
+                // compute volume contribution from view cells
+                case SortableEntry::BOX_INTERSECT:
+                        EvalVolumeContribution(*ray, volRight, volLeft);
+                        break;
+                default:
+                        cout << "should not come here" << endl;
+                        break;
         }
 
@@ -3215 +3308 @@
 
 
+void OspTree::EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight)
+{
+        ViewCellContainer viewCells;
+
+        mVspTree->GetViewCells(ray, viewCells);
+
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                // view cells comes to left child node
+                ViewCell *viewCell = *vit;
+
+                if (!viewCell->Mailed())
+                {
+                        viewCell->Mail();
+                        volLeft += viewCell->GetVolume();
+                }
+
+                // remove from right child node
+
+                if (-- viewCell->mCounter == 0)
+                {
+                        volRight -= viewCell->GetVolume();
+                }
+        }
+}
+
+
 void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -3224 +3346 @@
 {
         return mBoundingBox;
-}
-
-
-void OspTree::RemoveContriFromPvs(Intersectable *object, float &pvs) const
-{
-        if (mUseEqualWeightForHeuristics)
-                -- pvs;
-        else
-                // the cost of an object is the number of view cells it is part of
-                pvs -= object->mViewCellPvs.GetSize();
-}
-
-
-void OspTree::AddContriToPvs(Intersectable *object, float &pvs) const
-{
-        if (mUseEqualWeightForHeuristics)
-                ++ pvs;
-        else
-                // the cost of an object is the number of view cells it is part of
-                pvs += object->mViewCellPvs.GetSize();
 }
 
@@ -3279 +3381 @@
 
                                 nCostRatio[axis] =
-                                        EvalLocalCostHeuristics(tData.mNode,
+                                        EvalLocalCostHeuristics(tData,
                                                                            tData.mBoundingBox,
                                                                            axis,
@@ -3325 +3427 @@
 
 
-float OspTree::EvalViewCellPvsIncr(Intersectable *object) const
-{
-        if (mUseEqualWeightForHeuristics)
-                return 1;
-        else
-                return (float)object->mViewCellPvs.GetSize();
-}
-
-
 float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                           const OspTraversalData &data) const
@@ -3357 +3450 @@
         ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
 
+        //TODO §§matt: have to evaluate view cell volume on left and right cell
         for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
         {
@@ -3362 +3456 @@
                 const AxisAlignedBox3 box = obj->GetBox();
                 
-                const float pvsIncr = EvalViewCellPvsIncr(obj);
-                totalPvs += pvsIncr;
-                cout << "totalpvs " << totalPvs << " incr " << pvsIncr << endl;
+                ++ totalPvs;
+
+                cout << "totalpvs " << totalPvs << endl;
 
                 if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
                 {
-                        pvsFront += pvsIncr;
-                }
-                if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition)
-                {
-                        pvsBack += pvsIncr;
-                }
-        }
+                        ++ pvsFront;
+                }
+                if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
+                {
+                        ++ pvsBack;
+                }
+        }
+
+
+        ViewCell::NewMail();
+        
+        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
+
+        for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
+        {
+                VssRay *ray = (*rit).mRay;
+
+                // if hitpoint with one of the objects is inside this node
+                if (GetLeaf(ray->mOrigin, ray->mOriginNode) == leaf)
+                {
+                        if (ray->mOrigin[candidatePlane.mAxis] > candidatePlane.mPosition)
+                        {
+                                // add view cells volume to front       
+                                mVspTree->GetViewCells(ray, viewCells);
+
+                                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+                                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+                                {
+                                        ViewCell *vc = *vit;
+
+                                        if (!vit->Mailed())
+                                        {
+                                                vit->Mail();
+                                                volBack += vc->GetVolume();
+                                        }
+                                }
+                        }
+                        else
+                        {// TODO matt§§
+                                // add view cells volume to back
+                                if (ray->mOrigin[candidatePlane.mAxis] < candidatePlane.mPosition)
+                                {
+                                        // add view cells volume to front       
+                                        mVspTree->GetViewCells(ray, viewCells);
+
+                                        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+                                        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+                                        {
+                                                ViewCell *vc = *vit;
+        
+                                                if (!vit->Mailed())
+                                                {
+                                                        vit->Mail();
+                                                        volBack += vc->GetVolume();
+                                                }
+                                        }
+                                }
+                        }
+                }
+        }
+
 
 
@@ -3776 +3926 @@
 mVspTree(vspTree), mOspTree(ospTree)
 {
+        // cross references
         mVspTree.mOspTree = &ospTree;
+        mOspTree.mVspTree = &vspTree;
 }
 

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

@@ -749 +749 @@
         void AddViewCellReferences(ViewCell *vc) const;
 
+        /** Returns view cells of this ray, either taking precomputed cells
+                or by recomputation.
+        */
+        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
+
 
         /// pointer to the hierarchy of view cells
@@ -900 +905 @@
         /** Computes best cost for axis aligned planes.
         */
-        float EvalLocalCostHeuristics(const VspTraversalData &data,
+        float EvalLocalCostHeuristics(const VspTraversalData &tData,
                                                                   const AxisAlignedBox3 &box,
                                                                   const int axis,
@@ -1365 +1370 @@
         struct SortableEntry
         {
+                /** There is a 3th "event" for rays which intersect a
+                        box in the middle. These "events" don't induce a change in
+                        pvs size, but may induce a change in view cell volume.
+                */
                 enum EType 
                 {
-                        ERayMin,
-                        ERayMax
+                        BOX_MIN,
+                        BOX_MAX,
+                        BOX_INTERSECT
                 };
 
@@ -1374 +1384 @@
                 //int mPvs;
                 float mPos;
-
+                VssRay *mRay;
+                
                 Intersectable *mObject;
 
                 SortableEntry() {}
 
-                SortableEntry(const int type, 
+                SortableEntry(const int type,
                         //const float pvs, 
                         const float pos,
-                        Intersectable *obj):
+                        Intersectable *obj,
+                        VssRay *ray):
                 mType(type), 
                 //mPvs(pvs), 
                 mPos(pos), 
-                mObject(obj) 
+                mObject(obj),
+                mRay(ray)
                 {}
 
@@ -1417 +1430 @@
         float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                  const OspTraversalData &data) const;
-
-        float EvalViewCellPvsIncr(Intersectable *object) const;
 
 
@@ -1490 +1501 @@
         /** Computes best cost for axis aligned planes.
         */
-        float EvalLocalCostHeuristics(const OspTraversalData &data,
+        float EvalLocalCostHeuristics(const OspTraversalData &tData,
                 const AxisAlignedBox3 &box,
                 const int axis,
@@ -1565 +1576 @@
         float GetMemUsage() const;
 
-        /** Evaluates the influence on the pvs of the visibility event ve.
+        /** Evaluates the influence on the pvs of the event.
                 @param ve the visibility event
                 @param pvsLeft updates the left pvs
                 @param rightPvs updates the right pvs
         */
-        void EvalViewCellVolumeIncr(const SortableEntry &ve,
+        void EvalHeuristicsContribution(const SortableEntry &ci,
                 float &volLeft,
-                float &volRight) const;
-
-        void RemoveContriFromPvs(Intersectable *object, float &pvs) const;
-        void AddContriToPvs(Intersectable *object, float &pvs) const;
+                float &volRight,
+                int &pvsLeft,
+                int &pvsRight);
+
+        /** Evaluate the contributions of view cell volume of the left and the right view cell.
+        */
+        void EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight);
 
         /** Prepares objects for the cost heuristics.
                 @returns pvs size of the node
         */
-        float PrepareHeuristics(const ObjectContainer &objects);
-
-        /** Evaluates contribution for one object 
-                to heuristics preparation.
-        */
-        float PrepareHeuristics(Intersectable *object);
+        float PrepareHeuristics(const OspTraversalData &tData);
+
+        /** Prepares heuristics for a particular ray.
+        */
+        float PrepareHeuristics(const VssRay &ray);
 
         /** Prepares construction for vsp and osp trees.
@@ -1605 +1618 @@
 
 protected:
+
+        VspTree *mVspTree;
 
         /// The view cells manager