Changeset 1108

Timestamp:

07/10/06 15:57:11 (18 years ago)

Author:

mattausch

Message:

working on vsp osp (should I create view cells in each step?)

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• KdTree.cpp (modified) (1 diff)
• ViewCellsManager.cpp (modified) (4 diffs)
• VrmlExporter.cpp (modified) (1 diff)
• VspOspTree.cpp (modified) (33 diffs)
• VspOspTree.h (modified) (6 diffs)

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

@@ -163 +163 @@
   //  cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
   return
-    (leaf->mObjects.size() <= mTermMinCost) ||
+    ((int)leaf->mObjects.size() <= mTermMinCost) ||
     (leaf->mDepth >= mTermMaxDepth);
   

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

@@ -5039 +5039 @@
         }
         
-        
         VspInterior *interior = dynamic_cast<VspInterior *>(root);
         ViewCellInterior *viewCellInterior = new ViewCellInterior();
@@ -5445 +5444 @@
                 if (1)
                 {       //-- export pvs
+
                         ObjectPvsMap::const_iterator oit,
                                 oit_end = pvs.mEntries.end();
@@ -5460 +5460 @@
                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
                         {       
-                                // "original" pvs
+                                // exportŽ"original" pvs
                                 Intersectable *obj = (*oit).first;
 
@@ -5487 +5487 @@
                         exporter->SetForcedMaterial(m);
 
-                        // export kd node pvs
+                        //-- export kd node pvs
                         Intersectable::NewMail();
 

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

@@ -659 +659 @@
         vector<KdLeaf *>::const_iterator it, it_end = leaves.end();
 
+        Material white; 
+        white.mDiffuseColor.r = 1;
+        white.mDiffuseColor.g = 1;
+        white.mDiffuseColor.b = 1;
+
         for (it = leaves.begin(); it != it_end; ++ it)
         {
                 SetWireframe();
+                SetForcedMaterial(white);
                 ExportBox(ospTree.GetBBox(*it));
 
+                SetFilled();
                 SetForcedMaterial(RandomMaterial());
-
                 ExportGeometry((*it)->mObjects);        
         }

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

@@ -467 +467 @@
                         mBoundingBox.Include(ray->GetOrigin());
                 }
-
-                mTermMinProbability *= mBoundingBox.GetVolume();
-                mGlobalCostMisses = 0;
-        }
+        }
+
+        mTermMinProbability *= mBoundingBox.GetVolume();
+        mGlobalCostMisses = 0;
 }
 
@@ -517 +517 @@
 bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
 {
+        Debug << "cost misses " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
+        Debug << "leaves " << mVspStats.Leaves() << " " <<  mMaxViewCells << endl;
+
         return (
 //              mOutOfMemory || 
@@ -525 +528 @@
 
 
+void VspTree::CreateViewCell(VspTraversalData &tData)
+{
+        //-- create new view cell
+        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
+        
+        VspViewCell *viewCell = new VspViewCell();
+    leaf->SetViewCell(viewCell);
+                
+        //-- update pvs
+        int conSamp = 0;
+        float sampCon = 0.0f;
+        AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
+
+        // update scalar pvs size value
+        mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
+
+        mVspStats.contributingSamples += conSamp;
+        mVspStats.sampleContributions +=(int) sampCon;
+
+        //-- store additional info
+        if (mStoreRays)
+        {
+                RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
+                for (it = tData.mRays->begin(); it != it_end; ++ it)
+                {
+                        (*it).mRay->Ref();                      
+                        leaf->mVssRays.push_back((*it).mRay);
+                }
+        }
+                
+        viewCell->mLeaf = leaf;
+
+        viewCell->SetVolume(tData.mProbability);
+    leaf->mProbability = tData.mProbability;
+
+        mVspStats.contributingSamples += conSamp;
+        mVspStats.sampleContributions +=(int) sampCon;
+
+        // finally evaluate statistics for this leaf
+        EvaluateLeafStats(tData);
+}
+
+
 VspNode *VspTree::Subdivide(SplitQueue &tQueue,
                                                         VspSplitCandidate &splitCandidate,
@@ -551 +597 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                         
-                //-- statistics
+                
                 if (1)
                 {
+                        //-- subdivision statistics
+
                         const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
                         const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
@@ -572 +620 @@
 
         
-                //-- push the new split candidates on the queue
+                //-- evaluate new split candidates for global greedy cost heuristics
                 VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData);
                 VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData);
@@ -586 +634 @@
         }
 
-
-        //-- terminate traversal and create new view cell
+        // subdivision terminated
         if (newNode->IsLeaf())
         {
-                VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
-        
-                VspViewCell *viewCell = new VspViewCell();
-        leaf->SetViewCell(viewCell);
-                
-                //-- update pvs
-                int conSamp = 0;
-                float sampCon = 0.0f;
-                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
-
-                // update scalar pvs size value
-                mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
-
-                mVspStats.contributingSamples += conSamp;
-                mVspStats.sampleContributions +=(int) sampCon;
-
+                //-- create new view cell
+                CreateViewCell(tData);
+        
                 //-- store additional info
                 if (mStoreRays)
@@ -613 +647 @@
                         {
                                 (*it).mRay->Ref();                      
-                                leaf->mVssRays.push_back((*it).mRay);
-                        }
-                }
-                
-                viewCell->mLeaf = leaf;
-
-                viewCell->SetVolume(tData.mProbability);
-        leaf->mProbability = tData.mProbability;
-
-                // finally evaluate stats until this leaf
+                                dynamic_cast<VspLeaf *>(newNode)->mVssRays.push_back((*it).mRay);
+                        }
+                }
+
+                // finally evaluate statistics for this leaf
                 EvaluateLeafStats(tData);
         }
@@ -661 +690 @@
         
         //-- the front and back traversal data is filled with the new values
+
         frontData.mDepth = tData.mDepth + 1;
         frontData.mRays = new RayInfoContainer();
@@ -672 +702 @@
                           *frontData.mRays,
                           *backData.mRays);
+
+        // TODO: 
+        // create front and back view cell
+        // remove "parent" view cell from pvs of all objects (traverse trough rays)
+        // add front and back view cell to "Potentially Visbilie View Cells" 
+        // of the objects in front and back pvs
 
         //Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
@@ -1012 +1048 @@
 
 
-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;
-}
-
-
 void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
 {
@@ -1200 +1209 @@
         pvsSize = PrepareHeuristics(rays);
 
-        Debug << "here45 pvs: " << pvsSize << endl;
-
         // go through the lists, count the number of objects left and right
         // and evaluate the following cost funcion:
@@ -1229 +1236 @@
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-Debug << "****************" << endl;
         //-- traverse through visibility events
 
@@ -1338 +1344 @@
                         {
                                 //-- split plane position is spatial median
-
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
-
                                 nCostRatio[axis] = EvalLocalSplitCost(tData,
                                                                                                           box,
@@ -1361 +1365 @@
 
 
-        //-- assign values
+        //-- assign values of best split
         
         plane.mAxis = bestAxis;
-        // split plane position
-    plane.mPosition = nPosition[bestAxis];
+        plane.mPosition = nPosition[bestAxis]; // split plane position
 
         pFront = nProbFront[bestAxis];
@@ -1475 +1478 @@
         }
 
-        //-- pvs heuristics
+        //-- cost heuristics
         float pOverall;
-
-        //-- compute heurstics
         
         pOverall = data.mProbability;
-        // we take simplified computation for mid split
+
+        // we take simplified computation for spatial mid split
         pBack = pFront = pOverall * 0.5f;
         
+        const float newCost = pvsBack * pBack + pvsFront * pFront;
+        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
         
 #ifdef _DEBUG
@@ -1489 +1493 @@
         Debug << pFront << " " << pBack << " " << pOverall << endl;
 #endif
-
-        
-        const float newCost = pvsBack * pBack + pvsFront * pFront;
-        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
 
         return  (mCtDivCi + newCost) / oldCost;
@@ -2642 +2642 @@
 
 KdInterior *OspTree::SubdivideNode(
-                                                                   KdLeaf *leaf,
                                                                    const AxisAlignedPlane &splitPlane,
-                                                                   const AxisAlignedBox3 &box,
+                                                                   const OspTraversalData &tData,
                                                                    OspTraversalData &frontData,
                                                                    OspTraversalData &backData
                                                                    )
 {
+        KdLeaf *leaf = tData.mNode;
+        
+        // two new leaves
     mOspStats.nodes += 2;
 
@@ -2659 +2661 @@
         node->mAxis = axis;
         node->mPosition = position;
-        node->mBox = box;
-
-        backData.mBoundingBox = box;
-        frontData.mBoundingBox = box;
-  
-        // first count ray sides
+        node->mBox = tData.mBoundingBox;
+
+
+        //-- the front and back traversal data is filled with the new values
+
+        // bounding boxes: split front and back node geometry
+        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition, 
+                frontData.mBoundingBox, backData.mBoundingBox);
+
+        frontData.mDepth = backData.mDepth = tData.mDepth + 1;
+                
+        // TODO matt: compute pvs
+        frontData.mPvs = 999; // ComputePvsSize(*frontData.mRays);
+        backData.mPvs = -999; //ComputePvsSize(*backData.mRays);
+
+        frontData.mProbability = frontData.mBoundingBox.GetVolume();
+
+
+        // classify objects
         int objectsBack = 0;
         int objectsFront = 0;
-  
-        backData.mBoundingBox.SetMax(axis, position);
-        frontData.mBoundingBox.SetMin(axis, position);
 
         ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
@@ -2723 +2735 @@
                                                    OspSplitCandidate &splitCandidate,
                                                    const bool globalCriteriaMet)
-{Debug << "here11" << endl;
+{
         OspTraversalData &tData = splitCandidate.mParentData;
-Debug << "here993" << endl;
         KdNode *newNode = tData.mNode;
 
-Debug << "here996" << endl;
         if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
         {       
                 OspTraversalData tFrontData;
                 OspTraversalData tBackData;
-Debug << "here3" << endl;
+
                 //-- continue subdivision
                 
@@ -2739 +2749 @@
                 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
                 
-                newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 
-                                                                splitPlane, 
-                                                                tData.mBoundingBox, 
+                newNode = SubdivideNode(splitPlane, 
+                                                                tData, 
                                                                 tFrontData, 
                                                                 tBackData);
@@ -2755 +2764 @@
                 OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData);
 
-                Debug << "here 54 " << tFrontData.mNode << " " <<  tBackData.mNode << endl;
-
                 EvalSplitCandidate(*frontCandidate);
                 EvalSplitCandidate(*backCandidate);
@@ -2773 +2780 @@
                 EvaluateLeafStats(tData);               
         }
-        Debug << "here888 "<< endl;
+        
         //-- cleanup
         tData.Clear();
-        Debug << "here876"<< endl;
+        
         return newNode;
 }
@@ -3003 +3010 @@
         return 1;
 #else
-        ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
-        
-        int pvsSize = 0;
-
-        for (vit = object->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
-        {
-        ViewCell *vc = (*vit).first;
-
-                if (!vc->Mailed())
-                {
-                        vc->Mail();
-                        vc->mCounter = 1;
-                        ++ pvsSize;
-                }
-                else
-                {
-                        ++ vc->mCounter;
-                }
-        }
-
-        return pvsSize;
+        // the priotity of the object is the number of view cell pvs entries of the object
+        return object->mViewCellPvs.GetSize();
 #endif
 }
@@ -3041 +3029 @@
         {
                 Intersectable *obj = *oit;
-
                 pvsSize += PrepareHeuristics(obj);              
         }
@@ -3085 +3072 @@
         -- pvs;
 #else
-        ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
-        
-        for (vit = object->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
-        {
-        ViewCell *vc = (*vit).first;
-
-                if (-- vc->mCounter == 0)
-                {
-                        -- pvs;
-                }
-        }
+        // the cost of an object is the number of view cells it is part of
+        pvs -= object->mViewCellPvs.GetSize();
 #endif
 }
@@ -3102 +3080 @@
 void OspTree::AddContriToPvs(Intersectable *object, int &pvs) const
 {
-        ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
-
 #if COUNT_OBJECTS
         ++ pvs;
 #else
-        for (vit = object->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
-        {
-        ViewCell *vc = (*vit).first;
-
-                if (!vc->Mailed())
-                {
-                        vc->Mail();             
-                        ++ pvs;
-                }
-        }
+        // the cost of an object is the number of view cells it is part of
+        pvs += object->mViewCellPvs.GetSize();
 #endif
 }
@@ -3218 +3186 @@
 
         // probability that view point lies in back / front node
-        float pOverall = data.mProbability;
+        float pOverall = data.mBoundingBox.GetVolume();//data.mProbability;
         float pFront = 0;
         float pBack = 0;
-
 
         Intersectable::NewMail();
@@ -3234 +3201 @@
                 Intersectable *obj = *oit;
                 const AxisAlignedBox3 box = obj->GetBox();
+                
+                const float pvsIncr = EvalViewCellPvsIncr(obj);
+                totalPvs += pvsIncr;
 
                 if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
-                        pvsFront += EvalViewCellPvsIncr(obj);
+                {
+                        pvsFront += pvsIncr;
+                }
                 if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition)
-                        pvsBack += EvalViewCellPvsIncr(obj);
+                {
+                        pvsBack += pvsIncr;
+                }
         }
 
@@ -3256 +3230 @@
 
         //-- only render cost heuristics or combined with standard deviation
-        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
+        const float penaltyOld = totalPvs;//EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
+    const float penaltyFront = pvsFront;//EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
+        const float penaltyBack = pvsBack;//EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
                         
+        Debug << "total pvs: " << totalPvs << " p " << pOverall << endl;
         const float oldRenderCost = pOverall * penaltyOld;
         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
 
-        //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
+        Debug << "old: " << oldRenderCost << " new: " << newRenderCost << " decrease: " << oldRenderCost - newRenderCost << endl;
         const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
         
@@ -3303 +3278 @@
                         mBoundingBox.Include(obj->GetBox());
                 }
-
-                mTermMinProbability *= mBoundingBox.GetVolume();
-                mGlobalCostMisses = 0;
-        }
+        }
+
+        mTermMinProbability *= mBoundingBox.GetVolume();
+        mGlobalCostMisses = 0;
 }
 
@@ -3503 +3478 @@
 bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
 {
-        if (candidate->Type() == SplitCandidate::VIEW_SPACE)
-        {
-                VspTree::VspSplitCandidate *sc = 
-                        dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
-                
-                return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
-        }
-        else
-        {
-                OspTree::OspSplitCandidate *sc = 
-                        dynamic_cast<OspTree::OspSplitCandidate *>(candidate);
-                
-                return mOspTree.GlobalTerminationCriteriaMet(sc->mParentData);
-        }
-
-        return true;
+        // TODO matt: make virtual by creating superclasss for traveral data
+        return candidate->GlobalTerminationCriteriaMet();
 }
 
@@ -3595 +3556 @@
                         GlobalTerminationCriteriaMet(splitCandidate);
 
-                cout << "view cells: " << i ++ << endl;
+                //cout << "vsp nodes: " << i ++ << endl;
 
                 // cost ratio of cost decrease / totalCost
@@ -3655 +3616 @@
                         GlobalTerminationCriteriaMet(splitCandidate);
 
-                cout << "kd nodes: " << i ++ << endl;
-
                 // cost ratio of cost decrease / totalCost
                 const float costRatio = splitCandidate->GetPriority() / mTotalCost;
+                
                 //Debug << "cost ratio: " << costRatio << endl;
+                //cout << "kd nodes: " << i ++ << endl;
 
                 if (costRatio < mTermMinGlobalCostRatio)

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

@@ -72 +72 @@
         virtual void EvalPriority() = 0;
         virtual int Type() const = 0;
+        virtual bool GlobalTerminationCriteriaMet() const = 0;
 };
 
@@ -554 +555 @@
         {  
         public:
+
                 static VspTree* sVspTree;
+
                 /// parent node traversal data
                 VspTraversalData mParentData;
@@ -566 +569 @@
                 {
                         sVspTree->EvalSplitCandidate(*this);    
+                }
+
+                bool GlobalTerminationCriteriaMet() const
+                {
+                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
                 }
 
@@ -969 +977 @@
 
         void ProcessViewCellObjects(ViewCell *parent, ViewCell *front, ViewCell *back) const;
+
+        void CreateViewCell(VspTraversalData &tData);
 
 protected:
@@ -1169 +1179 @@
                 }
 
+                bool GlobalTerminationCriteriaMet() const
+                {
+                        return sOspTree->GlobalTerminationCriteriaMet(mParentData);
+                }
+
+
                 OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData): 
                 SplitCandidate(plane), mParentData(tData)
@@ -1379 +1395 @@
                 @returns the root of the subdivision
         */
-        KdInterior *SubdivideNode(KdLeaf *leaf,
+        KdInterior *SubdivideNode(
                 const AxisAlignedPlane &splitPlane,
-                const AxisAlignedBox3 &box,
+                const OspTraversalData &tData,
                 OspTraversalData &frontData,
                 OspTraversalData &backData);