Changeset 1089

Timestamp:

07/06/06 16:22:15 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• KdTree.cpp (modified) (4 diffs)
• KdTree.h (modified) (1 diff)
• Pvs.h (modified) (1 diff)
• VspOspTree.cpp (modified) (19 diffs)
• VspOspTree.h (modified) (5 diffs)

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

@@ -92 +92 @@
   }
 
-        ProcessLeafObjects(leaf, NULL);
+        ProcessLeafObjects(NULL, leaf, NULL);
 
   cout <<"KdTree Root Box:"<<mBox<<endl;
@@ -308 +308 @@
   }
   
-   ProcessLeafObjects(back, leaf);
-    ProcessLeafObjects(front, leaf);
+   ProcessLeafObjects(leaf, front, back);
+  
 
   delete leaf;
   return node;
 }
-
 
 
@@ -1095 +1094 @@
 
 
-void KdTree::ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const
-{
-        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
-
-        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+void KdTree::ProcessLeafObjects(KdLeaf *parent, KdLeaf *front, KdLeaf *back) const
+{
+        if (parent)
         {
-                Intersectable *object = *oit;
-
-                if (parent)
+                // remove the parents from the set
+                ObjectContainer::const_iterator oit, oit_end = parent->mObjects.end();
+
+                for (oit = parent->mObjects.begin(); oit != oit_end; ++ oit)
                 {
+                        Intersectable *object = *oit;
+
                         set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent);
 
@@ -1111 +1111 @@
                                 object->mKdLeaves.erase(kdit);
                 }
-
-                object->mKdLeaves.insert(leaf);
-
-                if (object->mKdLeaves.size() > 1)
-                        leaf->mMultipleObjects.push_back(object);
         }
-}
-
-
-}
+
+        //Intersectable::NewMail();
+
+        if (front)
+        {
+                // Add front to leaf kd cells
+                ObjectContainer::const_iterator oit, oit_end = front->mObjects.end();
+
+                for (oit = front->mObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+                        object->mKdLeaves.insert(front);
+                }
+        }
+
+        if (back)
+        {
+                // Add back to leaf kd cells
+                ObjectContainer::const_iterator oit, oit_end = back->mObjects.end();
+
+                for (oit = back->mObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+                        object->mKdLeaves.insert(back); 
+                }
+        }
+
+        // note: can find out about multiple objects only now after adding and deleting
+        // finished 
+        if (front)
+        {
+                // find objects from multiple kd-leaves
+                ObjectContainer::const_iterator oit, oit_end = front->mObjects.end();
+
+                for (oit = front->mObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+
+                        if (object->mKdLeaves.size() > 1)
+                                front->mMultipleObjects.push_back(object);
+                }
+        }
+
+        if (back) 
+        {
+                // find objects from multiple kd-leaves
+                ObjectContainer::const_iterator oit, oit_end = back->mObjects.end();
+
+                for (oit = back->mObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+
+                        if (object->mKdLeaves.size() > 1)
+                                back->mMultipleObjects.push_back(object);
+                }
+        }
+        
+}
+
+
+}

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

@@ -531 +531 @@
 
 
-  /** does some post processing on the objects that are contained
-  in this leaf.
-  */
-  void ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const;
+  /** does some post processing on the objects in the new child leaves.
+  */
+  void ProcessLeafObjects(KdLeaf *parent, KdLeaf *front, KdLeaf *back) const;
 
   int mTermMaxNodes;

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

@@ -109 +109 @@
 
   /** Removes sample from PVS if reference count is zero.
-          @param visibleSampels number of references to be removed
+          @param visibleSamples number of references to be removed
   */
   bool RemoveSample(T sample, const float pdf);

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

@@ -729 +729 @@
         interior->SetBoundingBox(tData.mBoundingBox);
 
-        frontData.mNode = interior->GetFront();
-        backData.mNode = interior->GetBack();
-
         interior->mTimeStamp = mTimeStamp ++;
         
@@ -738 +735 @@
 
 
+
+void VspTree::ProcessViewCellObjects(ViewCell *parent, ViewCell *front, ViewCell *back) const
+{
+        if (parent)
+        {
+                // remove the parents from the object pvss
+                ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
+
+                for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = (*oit).first;
+                        // HACK: make sure that the view cell is removed from the pvs
+                        const float high_contri = 99999999999;
+                        object->mViewCellPvs.RemoveSample(parent, 999999);
+                }
+        }
+
+        if (front)
+        {
+                // Add front view cell to the object pvsss
+                ObjectPvsMap::const_iterator oit, oit_end = front->GetPvs().mEntries.end();
+
+                for (oit = front->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = (*oit).first;
+                        object->mViewCellPvs.AddSample(front, 1);
+                }
+        }
+
+        if (back)
+        {
+                // Add back view cell to the object pvsss
+                ObjectPvsMap::const_iterator oit, oit_end = back->GetPvs().mEntries.end();
+
+                for (oit = back->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = (*oit).first;
+                        object->mViewCellPvs.AddSample(back, 1);
+                }
+        }
+}
+
+
 void VspTree::AddToPvs(VspLeaf *leaf,
-                                                  const RayInfoContainer &rays,
-                                                  float &sampleContributions,
-                                                  int &contributingSamples)
+                                           const RayInfoContainer &rays,
+                                           float &sampleContributions,
+                                           int &contributingSamples)
 {
         sampleContributions = 0;
@@ -762 +802 @@
                 {
                         if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
+                        {
                                 madeContrib = true;
+                        }
+
                         sc += contribution;
                 }
@@ -769 +812 @@
                 {
                         if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
+                        {
                                 madeContrib = true;
+                        }
+
                         sc += contribution;
                 }
@@ -1327 +1373 @@
 
 
-inline void VspTree::GenerateUniqueIdsForPvs()
-{
-        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
-        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
-        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
-}
-
-
 float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                           const VspTraversalData &data) const
@@ -1352 +1390 @@
 
         // create unique ids for pvs heuristics
-        GenerateUniqueIdsForPvs();
+        Intersectable::NewMail();
         
         RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
@@ -1418 +1456 @@
         
         // create unique ids for pvs heuristics
-        GenerateUniqueIdsForPvs();
+        Intersectable::NewMail();
 
         const int pvsSize = data.mPvs;
@@ -1470 +1508 @@
         const int renderCost = 1;
 
-        // new object
-        if ((obj->mMailbox != sFrontId) &&
-                (obj->mMailbox != sBackId) &&
-                (obj->mMailbox != sFrontAndBackId))
+        // object in no pvs => new
+        if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
         {
                 totalPvs += renderCost;
@@ -1481 +1517 @@
         //if (cf == Ray::COINCIDENT) return;
 
-        // object belongs to both PVS
-        if (cf >= 0)
-        {
-                if ((obj->mMailbox != sFrontId) &&
-                        (obj->mMailbox != sFrontAndBackId))
+        if (cf >= 0) // front pvs
+        {
+                if (!obj->Mailed() && !obj->Mailed(2))
                 {
                         frontPvs += renderCost;
                 
-                        if (obj->mMailbox == sBackId)
-                                obj->mMailbox = sFrontAndBackId;
+                        // already in back pvs => in both pvss
+                        if (obj->Mailed(1))
+                                obj->Mail(2);
                         else
-                                obj->mMailbox = sFrontId;
-                }
-        }
-
-        if (cf <= 0)
-        {
-                if ((obj->mMailbox != sBackId) &&
-                        (obj->mMailbox != sFrontAndBackId))
+                                obj->Mail();
+                }
+        }
+
+        if (cf <= 0) // back pvs
+        {
+                if (!obj->Mailed(1) && !obj->Mailed(2))
                 {
                         backPvs += renderCost;
                 
-                        if (obj->mMailbox == sFrontId)
-                                obj->mMailbox = sFrontAndBackId;
+                        // already in front pvs => in both pvss
+                        if (obj->Mailed())
+                                obj->Mail(2);
                         else
-                                obj->mMailbox = sBackId;
+                                obj->Mail(1);
                 }
         }
@@ -2676 +2711 @@
 
         SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
+
+        ProcessLeafObjects(back, leaf);
+    ProcessLeafObjects(front, leaf);
   
         //delete leaf;
@@ -2745 +2783 @@
 {
         float frontProb;
-        float backtProb;
+        float backProb;
         
         KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode);
@@ -2755 +2793 @@
         //TODO
         // compute global decrease in render cost
-        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
-        splitData.mParentData = tData;
-        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+        splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData);
+        splitCandidate.mParentData = tData;
+        splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
 }
 
@@ -3072 +3110 @@
 
 
-float OspTree::SelectSplitPlane(const VspTraversalData &tData,
+float OspTree::SelectSplitPlane(const OspTraversalData &tData,
                                                                 AxisAlignedPlane &plane,
                                                                 float &pFront,
@@ -3093 +3131 @@
         }
 
+/*
         //sAxis = 2;
         for (int axis = 0; axis < 3; ++ axis)
@@ -3132 +3171 @@
         }
 
-
+*/
         //-- assign values
         
@@ -3145 +3184 @@
         return nCostRatio[bestAxis];
 }
+
+
+float OspTree::EvalViewCellPvsIncr(Intersectable *object) const
+{
+        return 0;
+}
+
+
+float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
+                                                                          const OspTraversalData &data) const
+{
+#if 0
+        return (float)-data.mDepth;
+#endif
+
+        float pvsFront = 0;
+        float pvsBack = 0;
+        float totalPvs = 0;
+
+        // probability that view point lies in back / front node
+        float pOverall = data.mProbability;
+        float pFront = 0;
+        float pBack = 0;
+
+
+        Intersectable::NewMail();
+        ViewCell::NewMail();
+
+        KdLeaf *leaf = dynamic_cast<KdLeaf *>(data.mNode);
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *obj = *oit;
+                const AxisAlignedBox3 box = obj->GetBox();
+
+                if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
+                        pvsFront += EvalViewCellPvsIncr(obj);
+                if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition)
+                        pvsBack += EvalViewCellPvsIncr(obj);
+        }
+
+
+        AxisAlignedBox3 frontBox;
+        AxisAlignedBox3 backBox;
+
+        data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
+
+        pFront = frontBox.GetVolume();
+        pBack = pOverall - pFront;
+                
+
+        //-- pvs rendering heuristics
+        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+        //-- 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 oldRenderCost = pOverall * penaltyOld;
+        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+        //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
+        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
+        
+        // take render cost of node into account 
+        // otherwise danger of being stuck in a local minimum!!
+        const float factor = 0.99f;
+
+        const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
+        return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
+}
+
+
+void OspTree::PrepareConstruction(const ObjectContainer &objects,
+                                                                  AxisAlignedBox3 *forcedBoundingBox) 
+{
+        mOspStats.nodes = 1;
+        
+        if (forcedBoundingBox)
+        {
+                mBoundingBox = *forcedBoundingBox;
+        }
+        else // compute vsp tree bounding box
+        {
+                mBoundingBox.Initialize();
+
+                ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+                //-- compute bounding box
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *obj = *oit;
+
+                        // compute bounding box of view space
+                        mBoundingBox.Include(obj->GetBox());
+                        mBoundingBox.Include(obj->GetBox());
+                }
+
+                mTermMinProbability *= mBoundingBox.GetVolume();
+                mGlobalCostMisses = 0;
+        }
+}
+
+
+void OspTree::ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const
+{
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *object = *oit;
+
+                if (parent)
+                {
+                        set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent);
+
+                        // remove parent leaf
+                        if (kdit != object->mKdLeaves.end())
+                                object->mKdLeaves.erase(kdit);
+                }
+
+                object->mKdLeaves.insert(leaf);
+
+                if (object->mKdLeaves.size() > 1)
+                        leaf->mMultipleObjects.push_back(object);
+        }
+}
+
 
 
@@ -3208 +3378 @@
         cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
 
-        /// add first candidate for view space partition
+
+        int pvsSize = mVspTree.ComputePvsSize(rays);
+
+        // -- prepare view space partition
+
+        // add first candidate for view space partition
         mVspTree.mRoot = new VspLeaf();
         const float prop = mVspTree.mBoundingBox.GetVolume();
 
-        /// first traversal data
-        VspTree::VspTraversalData tData(mVspTree.mRoot,
+        // first vsp traversal data
+        VspTree::VspTraversalData vData(mVspTree.mRoot,
                                                                         0,
                                                                         &rays,
                                                                         //(int)objects.size(),
-                                                                        mVspTree.ComputePvsSize(rays),
+                                                                        pvsSize,        
                                                                         prop,
                                                                         mVspTree.mBoundingBox);
 
+
         // compute first split candidate
         VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate();
-    mVspTree.EvalSplitCandidate(tData, *splitCandidate);
+    mVspTree.EvalSplitCandidate(vData, *splitCandidate);
 
         mTQueue.push(splitCandidate);
 
-        //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
+
+        //-- object space partition
+
+        mOspTree.PrepareConstruction(objects, forcedViewSpace);
+
+        // add first candidate for view space partition
+        KdLeaf *leaf = new KdLeaf(NULL, 0);
+        leaf->mObjects = objects;
+
+        mOspTree.mRoot = leaf;
+        
+
+        // first osp traversal data
+        OspTree::OspTraversalData oData(mOspTree.mRoot,
+                                                                        0,
+                                                                        &rays,
+                                                                        pvsSize,
+                                                                        prop,
+                                                                        mOspTree.mBoundingBox);
+
+                
+        mOspTree.ProcessLeafObjects(leaf, NULL);
+
+        // compute first split candidate
+        OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate();
+    mOspTree.EvalSplitCandidate(oData, *oSplitCandidate);
+
+        mTQueue.push(splitCandidate);
 }
 
@@ -3240 +3443 @@
                 return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
         }
+        else
+        {
+                OspTree::OspSplitCandidate *sc = 
+                        dynamic_cast<OspTree::OspSplitCandidate *>(candidate);
+                
+                return mOspTree.GlobalTerminationCriteriaMet(sc->mParentData);
+        }
 
         return true;
@@ -3287 +3497 @@
                 }
                 else // object space split
-                {
-#if TODO
-                        KdNode *r = mKdtree.Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
-#endif
+                {                       
+                        OspTree::OspSplitCandidate *sc = 
+                                dynamic_cast<OspTree::OspSplitCandidate *>(splitCandidate);
+
+                        KdNode *r = mOspTree.Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
                 }
 

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

@@ -990 +990 @@
         float GetMemUsage() const;
 
+        void ProcessViewCellObjects(ViewCell *parent, ViewCell *front, ViewCell *back) const;
 
 protected:
@@ -1380 +1381 @@
                                                                  const OspTraversalData &data) const;
 
+        float EvalViewCellPvsIncr(Intersectable *object) const;
+
+
         /** Collects view cells in the subtree under root.
         */
@@ -1425 +1429 @@
                                                           AxisAlignedBox3 &frontBBox);
 
-        /*KdInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
-                                                          OspTraversalData &tData,
-                                                          OspTraversalData &frontData,
-                                                          OspTraversalData &backData);*/
+        void ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const;
 
         /** Selects an axis aligned for the next split.
@@ -1494 +1495 @@
         inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
 
-        float SelectSplitPlane(const VspTraversalData &tData,
-                                                                AxisAlignedPlane &plane,
-                                                                float &pFront,
-                                                                float &pBack);
+        float SelectSplitPlane(const OspTraversalData &tData,
+                AxisAlignedPlane &plane,
+                float &pFront,
+                float &pBack);
         /** Adds ray sample contributions to the PVS.
                 @param sampleContributions the number contributions of the samples
@@ -1543 +1544 @@
 
         int PrepareHeuristics(Intersectable *object);
+
+        void PrepareConstruction(const ObjectContainer &objects,
+                AxisAlignedBox3 *forcedBoundingBox);
+
 
 protected: