Changeset 452 for trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

Timestamp:

12/05/05 20:33:53 (19 years ago)

Author:

mattausch

Message:

started to add view cell merging to vsp kd tree

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp (modified) (9 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -180 +180 @@
 /**************************************************************/
 VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,      const int nRays):
-VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false) 
+VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
 {
         mRays.reserve(nRays);
@@ -447 +447 @@
 VspKdTree::Construct(const VssRayContainer &rays,
                                          AxisAlignedBox3 *forcedBoundingBox)
-{Debug << "here888" << endl;
+{
         mStat.Start();
-  Debug << "here1000" << endl;
+ 
         mMaxMemory = mMaxStaticMemory;
-        Debug << "here1" << endl;
         DEL_PTR(mRoot);
 
@@ -461 +460 @@
         mStat.nodes = 1;
         mBox.Initialize();
-Debug << "here2" << endl;
+
         //-- compute bounding box
         if (forcedBoundingBox)
@@ -468 +467 @@
                 for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
                 {
-                        mBox.Include((*ri)->GetOrigin());
-                        mBox.Include((*ri)->GetTermination()); 
+                        if ((*ri)->mOriginObject)
+                mBox.Include((*ri)->GetOrigin());
+                        if ((*ri)->mTerminationObject)
+                                mBox.Include((*ri)->GetTermination()); 
                 }
 
@@ -676 +677 @@
         }       
 
-        float ratio = 0;
-        
         if (0)
         {
@@ -702 +701 @@
                 const float oldCost = (float)pvsSize;
                 
-                float ratio = newCost / oldCost;
-        }
-        
-        return ratio;
+                return newCost / oldCost;
+        }
 }
 
@@ -731 +728 @@
                 if (!mOnlyDrivingAxis || axis == sAxis) 
                 {
+                        
                         nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis]) * 0.5f;
                                                 
@@ -740 +738 @@
                                                                                          nPvsBack[axis],
                                                                                          nPvsFront[axis]);
+                        if (bestAxis == -1)
+                        {
+                                bestAxis = axis;
+                        }
+                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                        {
+                                /*Debug << "pvs front " << nPvsBack[axis] 
+                                          << " pvs back " << nPvsFront[axis]
+                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/
+                                bestAxis = axis;
+                        }
                         
-                        if (bestAxis == -1)
-                                bestAxis = axis;
-                        else
-                                if (nCostRatio[axis] < nCostRatio[bestAxis])
-                                {
-                                        Debug << "pvs front " << nPvsBack[axis]
-                                                  << " pvs back " << nPvsFront[axis]
-                                                  << " overall pvs " << leaf->GetPvsSize() << endl;
-                                        bestAxis = axis;
-                                }
                 }
         }
@@ -1786 +1785 @@
         }
 }
+
+int VspKdTree::FindNeighbors(VspKdTreeLeaf *n,
+                                                         vector<VspKdTreeLeaf *> &neighbors,
+                                                         bool onlyUnmailed)
+{
+        stack<VspKdTreeNode *> nodeStack;
+  
+        nodeStack.push(mRoot);
+
+        AxisAlignedBox3 box = GetBBox(n);
+
+        while (!nodeStack.empty()) 
+        {
+                VspKdTreeNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+
+                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
+                                neighbors.push_back(leaf);
+                } 
+                else 
+                {
+                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+
+                        if (interior->mPosition > box.Max(interior->mAxis))
+                                nodeStack.push(interior->mBack);
+                        else
+                        {
+                                if (interior->mPosition < box.Min(interior->mAxis))
+                                        nodeStack.push(interior->mFront);
+                                else 
+                                {
+                                        // random decision
+                                        nodeStack.push(interior->mBack);
+                                        nodeStack.push(interior->mFront);
+                                }
+                        }
+                }
+        }
+
+        return (int)neighbors.size();
+}
+
+void VspKdTree::MergeLeaves()
+{
+        vector<VspKdTreeLeaf *> leaves;
+        priority_queue<LeafPair> mergeCandidates;
+        vector<VspKdTreeLeaf *> neighbors;
+
+        CollectLeaves(leaves);
+
+        VspKdTreeLeaf::NewMail();
+
+        vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end();
+
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspKdTreeLeaf *leaf = *it;
+
+                if (!leaf->Mailed())
+                {
+                        FindNeighbors(leaf, neighbors, true);
+
+                        vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+                        for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit)
+                                mergeCandidates.push(LeafPair(leaf, *nit));
+                        
+                        leaf->Mail();
+                }
+        }
+}
+
+
+
+/*********************************************************************/
+/*                MergeCandidate implementation                      */
+/*********************************************************************/
+
+
+MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2):
+mLeaf1(l1), mLeaf2(l2)
+{}
+
+int MergeCandidate::ComputePvsDifference() const
+{
+        return 0;
+}
+
+float MergeCandidate::EvaluateMergeCost() const
+{
+        return 0;
+}