Changeset 1008

Timestamp:

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

Author:

mattausch

Message:

worked on vsp osp tree. warning: does not compile

Location:

GTP/trunk/Lib/Vis

Files:

• Preprocessing/src/GlRenderer.h (modified) (1 diff)
• Preprocessing/src/ViewCell.h (modified) (4 diffs)
• Preprocessing/src/ViewCellBsp.h (modified) (1 diff)
• Preprocessing/src/VspOspTree.cpp (modified) (79 diffs)
• Preprocessing/src/VspOspTree.h (modified) (25 diffs)
• shared/scripts/GtpVisibility.suo (modified) (previous)

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

@@ -259 +259 @@
 public:
   signals:
-        UpdatePvsErrorItem(int i,
-                                           GlRendererBuffer::PvsErrorEntry &);
+        void UpdatePvsErrorItem(int i, GlRendererBuffer::PvsErrorEntry &);
 };
 

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

@@ -8 +8 @@
 #include "Material.h"
 #include "gzstream.h"
-
+#include "VspOspTree.h"
 
 namespace GtpVisibilityPreprocessor {
@@ -17 +17 @@
 class BspPvs;
 class BspLeaf;
-class VspKdLeaf;
+class VspLeaf;
 class KdLeaf;
 class ViewCellInterior;
@@ -97 +97 @@
         friend class ViewCellsTree;
         friend class ViewCellsManager;
-        //friend class VspBspViewCellsManager;
-        //friend class BspViewCellsManager;
-        //friend class VspBspTree;
-        //friend class FromPointVisibilityTree;
-        //friend class BspTree;
-
 
 public:
@@ -380 +374 @@
 
 
+//typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
 typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
 typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;
-typedef HierarchyLeafViewCell<VspKdLeaf *> VspKdViewCell;
+
 
 

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

@@ -410 +410 @@
 };
 
+
 /** Implementation of the view cell BSP tree. 
 */

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

@@ -46 +46 @@
 
 
+int VspNode::sMailId = 1;
+
+
+/******************************************************************/
+/*                  class VspNode implementation                  */
+/******************************************************************/
+
+
+VspNode::VspNode(): 
+mParent(NULL), mTreeValid(true), mTimeStamp(0)
+{}
+
+
+VspNode::VspNode(VspInterior *parent): 
+mParent(parent), mTreeValid(true)
+{}
+
+
+bool VspNode::IsRoot() const 
+{
+        return mParent == NULL;
+}
+
+
+VspInterior *VspNode::GetParent() 
+{ 
+        return mParent; 
+}
+
+
+void VspNode::SetParent(VspInterior *parent)
+{
+        mParent = parent;
+}
+
+
+bool VspNode::IsSibling(VspNode *n) const
+{
+        return  ((this != n) && mParent && 
+                         (mParent->GetFront() == n) || (mParent->GetBack() == n));
+}
+
+
+int VspNode::GetDepth() const
+{
+        int depth = 0;
+        VspNode *p = mParent;
+        
+        while (p)
+        {
+                p = p->mParent;
+                ++ depth;
+        }
+
+        return depth;
+}
+
+
+bool VspNode::TreeValid() const
+{
+        return mTreeValid;
+}
+
+
+void VspNode::SetTreeValid(const bool v)
+{
+        mTreeValid = v;
+}
+
+
+/****************************************************************/
+/*              class VspInterior implementation                */
+/****************************************************************/
+
+
+VspInterior::VspInterior(const AxisAlignedPlane &plane): 
+mPlane(plane), mFront(NULL), mBack(NULL)
+{}
+
+VspInterior::~VspInterior() 
+{ 
+        DEL_PTR(mFront); 
+        DEL_PTR(mBack);
+}
+
+bool VspInterior::IsLeaf() const
+{ 
+        return false; 
+}
+
+VspNode *VspInterior::GetBack() 
+{
+        return mBack;
+}
+
+VspNode *VspInterior::GetFront() 
+{
+        return mFront;
+}
+
+AxisAlignedPlane VspInterior::GetPlane() const
+{
+        return mPlane;
+}
+
+void VspInterior::ReplaceChildLink(VspNode *oldChild, VspNode *newChild) 
+{
+        if (mBack == oldChild)
+                mBack = newChild;
+        else
+                mFront = newChild;
+}
+
+void VspInterior::SetupChildLinks(VspNode *b, VspNode *f) 
+{
+    mBack = b;
+    mFront = f;
+}
+
+
+/****************************************************************/
+/*                  class VspLeaf implementation                */
+/****************************************************************/
+
+
+VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
+{
+}
+
+
+VspLeaf::~VspLeaf()
+{
+        DEL_PTR(mPvs);
+}
+
+
+VspLeaf::VspLeaf(ViewCellLeaf *viewCell): 
+mViewCell(viewCell)
+{
+}
+
+
+VspLeaf::VspLeaf(VspInterior *parent): 
+VspNode(parent), mViewCell(NULL), mPvs(NULL)
+{}
+
+
+
+VspLeaf::VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell): 
+VspNode(parent), mViewCell(viewCell), mPvs(NULL)
+{
+}
+
+ViewCellLeaf *VspLeaf::GetViewCell() const
+{
+        return mViewCell;
+}
+
+void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
+{
+        mViewCell = viewCell;
+}
+
+
+bool VspLeaf::IsLeaf() const 
+{ 
+        return true; 
+}
 
 
@@ -140 +308 @@
 
 
-BspViewCell *VspOspTree::GetOutOfBoundsCell()
+VspViewCell *VspOspTree::GetOutOfBoundsCell()
 {
         return mOutOfBoundsCell;
@@ -146 +314 @@
 
 
-BspViewCell *VspOspTree::GetOrCreateOutOfBoundsCell()
+VspViewCell *VspOspTree::GetOrCreateOutOfBoundsCell()
 {
         if (!mOutOfBoundsCell)
         {
-                mOutOfBoundsCell = new BspViewCell();
+                mOutOfBoundsCell = new VspViewCell();
                 mOutOfBoundsCell->SetId(-1);
                 mOutOfBoundsCell->SetValid(false);
@@ -159 +327 @@
 
 
-const BspTreeStatistics &VspOspTree::GetStatistics() const
-{
-        return mBspStats;
+const VspTreeStatistics &VspOspTree::GetStatistics() const
+{
+        return mVspStats;
 }
 
@@ -171 +339 @@
 }
 
+
 void VspOspTree::Construct(const VssRayContainer &sampleRays,
                                                    AxisAlignedBox3 *forcedBoundingBox)
 {
-        mBspStats.nodes = 1;
+        mVspStats.nodes = 1;
         mBox.Initialize();      // initialise BSP tree bounding box
 
@@ -231 +400 @@
         return (float)
                  (sizeof(VspOspTree) + 
-                  mBspStats.Leaves() * sizeof(BspLeaf) + 
+                  mVspStats.Leaves() * sizeof(VspLeaf) + 
                   mCreatedViewCells * sizeof(BspViewCell) +
-                  mBspStats.pvs * sizeof(ObjectPvsData) +
-                  mBspStats.Interior() * sizeof(BspInterior) +
-                  mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
+                  mVspStats.pvs * sizeof(ObjectPvsData) +
+                  mVspStats.Interior() * sizeof(VspInterior) +
+                  mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
 
@@ -243 +412 @@
         VspOspSplitQueue tQueue;
 
-        mRoot = new BspLeaf();
+        mRoot = new VspLeaf();
 
         const float prop = mBox.GetVolume();
@@ -274 +443 @@
         
         
-        mBspStats.Start();
+        mVspStats.Start();
         cout << "Constructing vsp bsp tree ... \n";
 
@@ -313 +482 @@
 
                 // subdivide leaf node
-                BspNode *r = Subdivide(tQueue, splitCandidate);
+                VspNode *r = Subdivide(tQueue, splitCandidate);
 
                 if (r == mRoot)
@@ -319 +488 @@
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-                if (mBspStats.Leaves() >= nLeaves)
+                if (mVspStats.Leaves() >= nLeaves)
                 {
                         nLeaves += 500;
 
-                        cout << "leaves=" << mBspStats.Leaves() << endl;
+                        cout << "leaves=" << mVspStats.Leaves() << endl;
                         Debug << "needed "
                                   << TimeDiff(interTime, GetTime())*1e-3 
@@ -341 +510 @@
         cout << "finished\n";
 
-        mBspStats.Stop();
+        mVspStats.Stop();
 }
 
@@ -360 +529 @@
         return
                 (mOutOfMemory 
-                || (mBspStats.Leaves() >= mMaxViewCells) 
+                || (mVspStats.Leaves() >= mMaxViewCells) 
                 || (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                  );
@@ -367 +536 @@
 
 // subdivide using a split plane queue
-BspNode *VspOspTree::Subdivide(VspOspSplitQueue &tQueue,
+VspNode *VspOspTree::Subdivide(VspOspSplitQueue &tQueue,
                                                            VspOspSplitCandidate &splitCandidate)
 {
         VspOspTraversalData &tData = splitCandidate.mParentData;
 
-        BspNode *newNode = tData.mNode;
+        VspNode *newNode = tData.mNode;
 
         if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
@@ -382 +551 @@
                 
                 // create new interior node and two leaf node
-                //TODO
-                const Plane3 splitPlane;// = splitCandidate.mSplitPlane;
-                                
+                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+
                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
         
@@ -409 +577 @@
 
                         mSubdivisionStats 
-                                        << "#ViewCells\n" << mBspStats.Leaves() << endl
+                                        << "#ViewCells\n" << mVspStats.Leaves() << endl
                                         << "#RenderCostDecrease\n" << -costDecr << endl
                                         << "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl
                                         << "#TotalRenderCost\n" << mTotalCost << endl
-                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
+                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mVspStats.Leaves() << endl;
                 }
 
@@ -435 +603 @@
         if (newNode->IsLeaf())
         {
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
+                VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
                 BspViewCell *viewCell = new BspViewCell();
 
@@ -448 +616 @@
                 mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
 
-                mBspStats.contributingSamples += conSamp;
-                mBspStats.sampleContributions +=(int) sampCon;
+                mVspStats.contributingSamples += conSamp;
+                mVspStats.sampleContributions +=(int) sampCon;
 
                 //-- store additional info
@@ -484 +652 @@
         VspOspTraversalData backData;
 
-        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
 
         // compute locally best split plane
-        // TODO
-    const bool success =0;/// SelectPlane(splitData.mSplitPlane, tData, 
-//                                                                       frontData, backData);
+        const bool success = 
+                SelectPlane(tData, splitData.mSplitPlane,
+                                        frontData.mProbability, backData.mProbability);
+
         //TODO
         // compute global decrease in render cost
-        splitData.mRenderCost = 0;//EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
         splitData.mParentData = tData;
         splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
@@ -498 +667 @@
 
 
-BspInterior *VspOspTree::SubdivideNode(const Plane3 &splitPlane,
+VspInterior *VspOspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
                                                                            VspOspTraversalData &tData,
                                                                            VspOspTraversalData &frontData,
                                                                            VspOspTraversalData &backData)
 {
-        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
         
         //-- the front and back traversal data is filled with the new values
@@ -514 +683 @@
 
         //-- subdivide rays
+#if TODO        
         SplitRays(splitPlane,
                           *tData.mRays,
                           *frontData.mRays,
                           *backData.mRays);
-
+#endif
 
         // compute pvs
@@ -543 +713 @@
 
         // store maximal and minimal depth
-        if (tData.mDepth > mBspStats.maxDepth)
-        {
-                Debug << "max depth increases to " << tData.mDepth << " at " << mBspStats.Leaves() << " leaves" << endl;
-                mBspStats.maxDepth = tData.mDepth;
-        }
-
-        mBspStats.nodes += 2;
+        if (tData.mDepth > mVspStats.maxDepth)
+        {
+                Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
+                mVspStats.maxDepth = tData.mDepth;
+        }
+
+        mVspStats.nodes += 2;
 
     
-        BspInterior *interior = new BspInterior(splitPlane);
+        VspInterior *interior = new VspInterior(splitPlane);
 
 #ifdef _DEBUG
@@ -561 +731 @@
         //-- create front and back leaf
 
-        BspInterior *parent = leaf->GetParent();
+        VspInterior *parent = leaf->GetParent();
 
         // replace a link from node's parent
@@ -575 +745 @@
 
         // and setup child links
-        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
+        interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
 
         frontData.mNode = interior->GetFront();
@@ -586 +756 @@
 
 
-void VspOspTree::AddToPvs(BspLeaf *leaf,
+void VspOspTree::AddToPvs(VspLeaf *leaf,
                                                   const RayInfoContainer &rays,
                                                   float &sampleContributions,
@@ -946 +1116 @@
 
 
-float VspOspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
+float VspOspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                                  const VspOspTraversalData &data) const
 {
@@ -968 +1138 @@
                 float t;
                 VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+                const int cf = 
+                        rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
+                                                                                  candidatePlane.mPosition, t);
 
                 // find front and back pvs for origing and termination object
@@ -1116 +1288 @@
 
 
-void VspOspTree::CollectLeaves(vector<BspLeaf *> &leaves, 
+void VspOspTree::CollectLeaves(vector<VspLeaf *> &leaves, 
                                                            const bool onlyUnmailed,
                                                            const int maxPvsSize) const
 {
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
         nodeStack.push(mRoot);
 
         while (!nodeStack.empty())
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
                 
@@ -1131 +1303 @@
                 {
                         // test if this leaf is in valid view space
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
                         if (leaf->TreeValid() && 
                                 (!onlyUnmailed || !leaf->Mailed()) &&
@@ -1141 +1313 @@
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
 
                         nodeStack.push(interior->GetBack());
@@ -1156 +1328 @@
 
 
-BspNode *VspOspTree::GetRoot() const
+VspNode *VspOspTree::GetRoot() const
 {
         return mRoot;
@@ -1165 +1337 @@
 {
         // the node became a leaf -> evaluate stats for leafs
-        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
-
-
-        if (data.mPvs > mBspStats.maxPvs)
-        {
-                mBspStats.maxPvs = data.mPvs;
-        }
-
-        mBspStats.pvs += data.mPvs;
-
-        if (data.mDepth < mBspStats.minDepth)
-        {
-                mBspStats.minDepth = data.mDepth;
+        VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);
+
+
+        if (data.mPvs > mVspStats.maxPvs)
+        {
+                mVspStats.maxPvs = data.mPvs;
+        }
+
+        mVspStats.pvs += data.mPvs;
+
+        if (data.mDepth < mVspStats.minDepth)
+        {
+                mVspStats.minDepth = data.mDepth;
         }
         
         if (data.mDepth >= mTermMaxDepth)
         {
-        ++ mBspStats.maxDepthNodes;
-                //Debug << "new max depth: " << mBspStats.maxDepthNodes << endl;
+        ++ mVspStats.maxDepthNodes;
+                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
         }
 
         // accumulate rays to compute rays /  leaf
-        mBspStats.accumRays += (int)data.mRays->size();
+        mVspStats.accumRays += (int)data.mRays->size();
 
         if (data.mPvs < mTermMinPvs)
-                ++ mBspStats.minPvsNodes;
+                ++ mVspStats.minPvsNodes;
 
         if ((int)data.mRays->size() < mTermMinRays)
-                ++ mBspStats.minRaysNodes;
+                ++ mVspStats.minRaysNodes;
 
         if (data.GetAvgRayContribution() > mTermMaxRayContribution)
-                ++ mBspStats.maxRayContribNodes;
+                ++ mVspStats.maxRayContribNodes;
 
         if (data.mProbability <= mTermMinProbability)
-                ++ mBspStats.minProbabilityNodes;
+                ++ mVspStats.minProbabilityNodes;
         
         // accumulate depth to compute average depth
-        mBspStats.accumDepth += data.mDepth;
+        mVspStats.accumDepth += data.mDepth;
 
         ++ mCreatedViewCells;
@@ -1221 +1393 @@
 {
         int hits = 0;
-
+#if TODO
         stack<BspRayTraversalData> tQueue;
 
@@ -1234 +1406 @@
         Vector3 extp = ray.Extrap(maxt);
 
-        BspNode *node = mRoot;
-        BspNode *farChild = NULL;
+        VspNode *node = mRoot;
+        VspNode *farChild = NULL;
 
         while (1)
@@ -1241 +1413 @@
                 if (!node->IsLeaf())
                 {
-                        BspInterior *in = dynamic_cast<BspInterior *>(node);
+                        VspInterior *in = dynamic_cast<VspInterior *>(node);
 
                         Plane3 splitPlane = in->GetPlane();
@@ -1274 +1446 @@
 
                         // push data for far child
-                        tQueue.push(BspRayTraversalData(farChild, extp, maxt));
+                        tQueue.push(VspRayTraversalData(farChild, extp, maxt));
 
                         // find intersection of ray segment with plane
@@ -1283 +1455 @@
                 } else // reached leaf => intersection with view cell
                 {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
 
                         if (!leaf->GetViewCell()->Mailed())
@@ -1311 +1483 @@
                 }
         }
-
+#endif
         return hits;
 }
@@ -1328 +1500 @@
 // TODO
 #if HAS_TO_BE_REDONE
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
 
         if (!mRoot)
@@ -1337 +1509 @@
         while (!nodeStack.empty()) 
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
                 
                 if (node->IsLeaf())
         {
-                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                        BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
 
                         if (!viewCell->GetValid())
                         {
-                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                                BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
         
                                 ViewCellContainer leaves;
@@ -1355 +1527 @@
                                 for (it = leaves.begin(); it != it_end; ++ it)
                                 {
-                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                                        VspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                                         l->SetViewCell(GetOrCreateOutOfBoundsCell());
-                                        ++ mBspStats.invalidLeaves;
+                                        ++ mVspStats.invalidLeaves;
                                 }
 
@@ -1367 +1539 @@
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
                 
                         nodeStack.push(interior->GetFront());
@@ -1374 +1546 @@
         }
 
-        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
 #endif
 }
@@ -1381 +1553 @@
 void VspOspTree::CollectRays(VssRayContainer &rays)
 {
-        vector<BspLeaf *> leaves;
-
-        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
+        vector<VspLeaf *> leaves;
+
+        vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
 
         for (lit = leaves.begin(); lit != lit_end; ++ lit)
         {
-                BspLeaf *leaf = *lit;
+                VspLeaf *leaf = *lit;
                 VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
 
@@ -1398 +1570 @@
 void VspOspTree::ValidateTree()
 {
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
 
         if (!mRoot)
@@ -1405 +1577 @@
         nodeStack.push(mRoot);
         
-        mBspStats.invalidLeaves = 0;
+        mVspStats.invalidLeaves = 0;
         while (!nodeStack.empty()) 
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
                 
                 if (node->IsLeaf())
                 {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
 
                         if (!leaf->GetViewCell()->GetValid())
-                                ++ mBspStats.invalidLeaves;
+                                ++ mVspStats.invalidLeaves;
 
                         // validity flags don't match => repair
@@ -1427 +1599 @@
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
                 
                         nodeStack.push(interior->GetFront());
@@ -1434 +1606 @@
         }
 
-        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
-}
-
-
-
-void VspOspTree::CollectViewCells(BspNode *root,
+        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
+}
+
+
+
+void VspOspTree::CollectViewCells(VspNode *root,
                                                                   bool onlyValid,
                                                                   ViewCellContainer &viewCells,
                                                                   bool onlyUnmailed) const
 {
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
 
         if (!root)
@@ -1453 +1625 @@
         while (!nodeStack.empty()) 
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
                 
@@ -1460 +1632 @@
                         if (!onlyValid || node->TreeValid())
                         {
-                                ViewCellLeaf *leafVc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                                ViewCellLeaf *leafVc = dynamic_cast<VspLeaf *>(node)->GetViewCell();
 
                                 ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
@@ -1473 +1645 @@
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
                 
                         nodeStack.push(interior->GetFront());
@@ -1538 +1710 @@
 
 
-int VspOspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
+int VspOspTree::FindNeighbors(VspNode *n, vector<VspLeaf *> &neighbors,
                                                           const bool onlyUnmailed) const
 {
@@ -1546 +1718 @@
 
 
-BspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &halfspace)
+VspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &halfspace)
 {
 #if TODO
-    stack<BspNode *> nodeStack;
+    stack<VspNode *> nodeStack;
         nodeStack.push(mRoot);
 
@@ -1556 +1728 @@
         while (!nodeStack.empty())
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
 
                 if (node->IsLeaf())
                 {
-                        return dynamic_cast<BspLeaf *>(node);
+                        return dynamic_cast<VspLeaf *>(node);
                 }
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                        BspNode *next;
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
+                        VspNode *next;
                         BspNodeGeometry geom;
 
@@ -1598 +1770 @@
 
 
-BspLeaf *VspOspTree::GetRandomLeaf(const bool onlyUnmailed)
-{
-        stack<BspNode *> nodeStack;
+VspLeaf *VspOspTree::GetRandomLeaf(const bool onlyUnmailed)
+{
+        stack<VspNode *> nodeStack;
 
         nodeStack.push(mRoot);
@@ -1608 +1780 @@
         while (!nodeStack.empty())
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
 
@@ -1614 +1786 @@
                 {
                         if ( (!onlyUnmailed || !node->Mailed()) )
-                                return dynamic_cast<BspLeaf *>(node);
+                                return dynamic_cast<VspLeaf *>(node);
                 }
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
 
                         // random decision
@@ -1680 +1852 @@
 {
         int hits = 0;
+#if TODO
         stack<BspRayTraversalData> tStack;
 
@@ -1690 +1863 @@
         Vector3 extp = termination;
 
-        BspNode *node = mRoot;
-        BspNode *farChild = NULL;
+        VspNode *node = mRoot;
+        VspNode *farChild = NULL;
 
         float t;
@@ -1700 +1873 @@
                 if (!node->IsLeaf())
                 {
-                        BspInterior *in = dynamic_cast<BspInterior *>(node);
+                        VspInterior *in = dynamic_cast<VspInterior *>(node);
 
                         Plane3 splitPlane = in->GetPlane();
@@ -1738 +1911 @@
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp));
+                        tStack.push(VspRayTraversalData(farChild, extp));
 
                         // find intersection of ray segment with plane
@@ -1746 +1919 @@
                 {
                         // reached leaf => intersection with view cell
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
                         ViewCell *viewCell;
                         
@@ -1775 +1948 @@
                 }
         }
-
+#endif
         return hits;
 }
@@ -1781 +1954 @@
 
 
-BspNode *VspOspTree::CollapseTree(BspNode *node, int &collapsed)
+VspNode *VspOspTree::CollapseTree(VspNode *node, int &collapsed)
 {
 // TODO
@@ -1788 +1961 @@
                 return node;
 
-        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-        BspNode *front = CollapseTree(interior->GetFront(), collapsed);
-        BspNode *back = CollapseTree(interior->GetBack(), collapsed);
+        VspInterior *interior = dynamic_cast<VspInterior *>(node);
+
+        VspNode *front = CollapseTree(interior->GetFront(), collapsed);
+        VspNode *back = CollapseTree(interior->GetBack(), collapsed);
 
         if (front->IsLeaf() && back->IsLeaf())
         {
-                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
-                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
+                VspLeaf *frontLeaf = dynamic_cast<VspLeaf *>(front);
+                VspLeaf *backLeaf = dynamic_cast<VspLeaf *>(back);
 
                 //-- collapse tree
@@ -1803 +1976 @@
                         BspViewCell *vc = frontLeaf->GetViewCell();
 
-                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
+                        VspLeaf *leaf = new VspLeaf(interior->GetParent(), vc);
                         leaf->SetTreeValid(frontLeaf->TreeValid());
 
@@ -1842 +2015 @@
 #if HAS_TO_BE_REDONE
         // list not valid anymore => clear
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
         nodeStack.push(mRoot);
 
@@ -1849 +2022 @@
         while (!nodeStack.empty())
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
 
                 if (node->IsLeaf())
                 {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
 
                         BspViewCell *viewCell = leaf->GetViewCell();
@@ -1869 +2042 @@
                 else
                 {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
 
                         nodeStack.push(interior->GetFront());
@@ -1883 +2056 @@
 ViewCell *VspOspTree::GetViewCell(const Vector3 &point, const bool active)
 {
+#if TODO
         if (mRoot == NULL)
                 return NULL;
 
-        stack<BspNode *> nodeStack;
+        stack<VspNode *> nodeStack;
         nodeStack.push(mRoot);
   
@@ -1893 +2067 @@
         while (!nodeStack.empty())  
         {
-                BspNode *node = nodeStack.top();
+                VspNode *node = nodeStack.top();
                 nodeStack.pop();
         
                 if (node->IsLeaf()) 
                 {
-                        viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+                        viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
                         break;
                 } 
                 else    
                 {       
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
         
                         // random decision
@@ -1917 +2091 @@
         else
                 return viewcell;
+#endif
 }
 
@@ -1922 +2097 @@
 bool VspOspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
-        BspNode *node = mRoot;
+#if TODO
+        VspNode *node = mRoot;
 
         while (1)
@@ -1933 +2109 @@
                         return false;
                         
-                BspInterior *in = dynamic_cast<BspInterior *>(node);
+                VspInterior *in = dynamic_cast<VspInterior *>(node);
                                         
                 if (in->GetPlane().Side(viewPoint) <= 0) 
@@ -1944 +2120 @@
                 }
         }
-
+#endif
         // should never come here
         return false;
@@ -1950 +2126 @@
 
 
-void VspOspTree::PropagateUpValidity(BspNode *node)
+void VspOspTree::PropagateUpValidity(VspNode *node)
 {
         const bool isValid = node->TreeValid();
@@ -1969 +2145 @@
                 {
             node = node->GetParent();
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
                         
                         // the parent is valid iff both leaves are valid
@@ -1991 +2167 @@
 
 #if ZIPPED_VIEWCELLS
-void VspOspTree::ExportNode(BspNode *node, ogzstream &stream)
+void VspOspTree::ExportNode(VspNode *node, ogzstream &stream)
 #else
-void VspOspTree::ExportNode(BspNode *node, ofstream &stream)
+void VspOspTree::ExportNode(VspNode *node, ofstream &stream)
 #endif
 {
         if (node->IsLeaf())
         {
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
                 ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
 
@@ -2009 +2185 @@
         else
         {
-                BspInterior *interior = dynamic_cast<BspInterior *>(node);
+#if TODO        
+                VspInterior *interior = dynamic_cast<VspInterior *>(node);
         
                 Plane3 plane = interior->GetPlane();
@@ -2018 +2195 @@
                 ExportNode(interior->GetBack(), stream);
                 ExportNode(interior->GetFront(), stream);
-
+#endif
                 stream << "</Interior>" << endl;
         }

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

@@ -9 +9 @@
 #include "VssRay.h"
 #include "RayInfo.h"
-#include "ViewCellBsp.h"
-
+#include "gzstream.h"
 
 
@@ -16 +15 @@
 
 class ViewCellLeaf;
-//class BspViewCell;
+class VspViewCell;
 class Plane3;
-class VspBspTree;  
-class BspInterior;
-class BspNode;
 class AxisAlignedBox3;
 class Ray;
@@ -29 +25 @@
 class ViewCellsTree;
 class Environment;
+class VspInterior;
+class VspLeaf;
+class VspNode;
+
+
+/** A definition for an axis aligned plane.
+*/
+struct AxisAlignedPlane
+{
+public:
+        int mAxis;
+        float mPosition;
+};
+
+
+class VspTreeStatistics: public StatisticsBase
+{
+public:
+        // total number of nodes
+        int nodes;
+        // number of splits
+        int splits[3];
+        
+        // totals number of rays
+        int rays;
+        // maximal reached depth
+        int maxDepth;
+        // minimal depth
+        int minDepth;
+        
+        // max depth nodes
+        int maxDepthNodes;
+        // minimum depth nodes
+        int minDepthNodes;
+        // max depth nodes
+        int minPvsNodes;
+        // nodes with minimum PVS
+        int minRaysNodes;
+        // max ray contribution nodes
+        int maxRayContribNodes;
+        // minimum area nodes
+        int minProbabilityNodes;
+        /// nodes termination because of max cost ratio;
+        int maxCostNodes;
+        // max number of rays per node
+        int maxObjectRefs;
+        /// samples contributing to pvs
+        int contributingSamples;
+        /// sample contributions to pvs
+        int sampleContributions;
+        /// largest pvs
+        int maxPvs;
+        /// number of invalid leaves
+        int invalidLeaves;
+        /// accumulated number of rays refs
+        int accumRays;
+        int pvs;
+        // accumulated depth (used to compute average)
+        int accumDepth;
+
+        // Constructor
+        VspTreeStatistics() 
+        {
+                Reset();
+        }
+
+        int Nodes() const {return nodes;}
+        int Interior() const { return nodes / 2; }
+        int Leaves() const { return (nodes / 2) + 1; }
+        
+        // TODO: computation wrong
+        double AvgDepth() const { return accumDepth / (double)Leaves();}; 
+        double AvgRays() const { return accumRays / (double)Leaves();}; 
+
+        void Reset() 
+        {
+                nodes = 0;
+                for (int i = 0; i < 3; ++ i)
+                        splits[i] = 0;
+                
+                maxDepth = 0;
+                minDepth = 99999;
+                accumDepth = 0;
+        pvs = 0;
+                maxDepthNodes = 0;
+                minPvsNodes = 0;
+                minRaysNodes = 0;
+                maxRayContribNodes = 0;
+                minProbabilityNodes = 0;
+                maxCostNodes = 0;
+
+                contributingSamples = 0;
+                sampleContributions = 0;
+
+                maxPvs = 0;
+                invalidLeaves = 0;
+                accumRays = 0;
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const VspTreeStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        } 
+};
+
+/**
+    VspNode abstract class serving for interior and leaf node implementation
+*/
+class VspNode 
+{
+
+public:
+        VspNode();
+        virtual ~VspNode(){};
+        VspNode(VspInterior *parent);
+
+        /** Determines whether this node is a leaf or not
+        @return true if leaf
+        */
+        virtual bool IsLeaf() const = 0;
+
+        /** Determines whether this node is a root
+        @return true if root
+        */
+        virtual bool IsRoot() const;
+
+        /** Returns parent node.
+        */
+        VspInterior *GetParent();
+
+        /** Sets parent node.
+        */
+        void SetParent(VspInterior *parent);
+
+        /** Returns true if this node is a sibling of node n.
+        */
+        bool IsSibling(VspNode *n) const;
+
+        /** returns depth of the node.
+        */
+        int GetDepth() const;
+
+        /** returns true if the whole subtree is valid
+        */
+        bool TreeValid() const;
+
+        void SetTreeValid(const bool v);
+
+        //-- mailing options
+
+        void Mail() { mMailbox = sMailId; }
+        static void NewMail() { ++ sMailId; }
+        bool Mailed() const { return mMailbox == sMailId; }
+
+        static int sMailId;
+        int mMailbox;
+
+        int mTimeStamp;
+
+protected:
+
+        /// if this sub tree is a completely valid view space region
+        bool mTreeValid;
+        /// parent of this node
+        VspInterior *mParent;
+};
+
+
+/** BSP interior node implementation 
+*/
+class VspInterior: public VspNode 
+{
+public:
+        /** Standard contructor taking split plane as argument.
+        */
+        VspInterior(const AxisAlignedPlane &plane);
+        ~VspInterior();
+        /** @return false since it is an interior node 
+        */
+        bool IsLeaf() const;
+
+        VspNode *GetBack();
+        VspNode *GetFront();
+
+        /** Returns split plane.
+        */
+        AxisAlignedPlane GetPlane() const;
+
+        /** Replace front or back child with new child.
+        */
+        void ReplaceChildLink(VspNode *oldChild, VspNode *newChild);
+        /** Replace front and back child.
+        */
+        void SetupChildLinks(VspNode *b, VspNode *f);
+
+        friend ostream &operator<<(ostream &s, const VspInterior &A)
+        {
+                return s << A.mPlane.mAxis << " " << A.mPlane.mPosition;
+        }
+
+protected:
+
+        /// Splitting plane corresponding to this node
+        AxisAlignedPlane mPlane;
+
+        /// back node
+        VspNode *mBack;
+        /// front node
+        VspNode *mFront;
+};
+
+
+/** BSP leaf node implementation.
+*/
+class VspLeaf: public VspNode 
+{
+
+public:
+        VspLeaf();
+        VspLeaf(ViewCellLeaf *viewCell);
+        VspLeaf(VspInterior *parent);
+        VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell);
+
+        ~VspLeaf();
+
+        /** @return true since it is an interior node 
+        */
+        bool IsLeaf() const;
+        
+        /** Returns pointer of view cell.
+        */
+        ViewCellLeaf *GetViewCell() const;
+
+        /** Sets pointer to view cell.
+        */
+        void SetViewCell(ViewCellLeaf *viewCell);
+
+        /// Rays piercing this leaf.
+        VssRayContainer mVssRays;
+        
+        /// leaf pvs
+        ObjectPvs *mPvs;
+
+        /// Probability that the view point lies in this leaf
+        float mProbability;
+
+protected:
+        
+        /// if NULL this does not correspond to feasible viewcell
+        ViewCellLeaf *mViewCell;
+};
+
 
 /**
@@ -57 +308 @@
 {
         friend class ViewCellsParseHandlers;
-        friend class VspBspViewCellsManager;
+        friend class VspVspViewCellsManager;
 
 public:
         
-        /** A definition for an axis aligned plane.
-        */
-        struct AxisAlignedPlane
-        {
-        public:
-                int mAxis;
-                float mPosition;
-        };
-
         /** Additional data which is passed down the BSP tree during traversal.
         */
@@ -76 +318 @@
         public:
                 /// the current node
-                BspNode *mNode;
+                VspNode *mNode;
                 /// current depth
                 int mDepth;
@@ -114 +356 @@
                 {}
                 
-                VspOspTraversalData(BspNode *node, 
+                VspOspTraversalData(VspNode *node, 
                                                         const int depth, 
                                                         RayInfoContainer *rays,
@@ -193 +435 @@
 #if 1
                         return mRenderCost;
-#endif
-#if 0
+#else
                         return (float) (-mDepth); // for kd tree
 #endif
@@ -217 +458 @@
         /** Returns BSP Tree statistics.
         */
-        const BspTreeStatistics &GetStatistics() const; 
+        const VspTreeStatistics &GetStatistics() const; 
   
 
@@ -233 +474 @@
                 @param maxPvs the maximal pvs (-1 means unlimited)
         */
-        void CollectLeaves(vector<BspLeaf *> &leaves, 
+        void CollectLeaves(vector<VspLeaf *> &leaves, 
                                            const bool onlyUnmailed = false,
                                            const int maxPvs = -1) const;
@@ -241 +482 @@
         AxisAlignedBox3 GetBoundingBox()const;
 
-        /** Returns root of BSP tree.
-        */
-        BspNode *GetRoot() const;
+        /** Returns root of the view space partitioning tree.
+        */
+        VspNode *GetRoot() const;
 
         /** Collects the leaf view cells of the tree
@@ -259 +500 @@
         /** finds neighbouring leaves of this tree node.
         */
-        int FindNeighbors(BspNode *n, 
-                                          vector<BspLeaf *> &neighbors, 
+        int FindNeighbors(VspNode *n, 
+                                          vector<VspLeaf *> &neighbors, 
                                           const bool onlyUnmailed) const;
 
@@ -266 +507 @@
                 @param halfspace defines the halfspace from which the leaf is taken.
         */
-        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
+        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
 
         /** Returns random leaf of BSP tree.
                 @param onlyUnmailed if only unmailed leaves should be returned.
         */
-        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
+        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
         /** Returns epsilon of this tree.
@@ -291 +532 @@
         void SetViewCellsManager(ViewCellsManager *vcm);
 
-        /** Returns distance from node 1 to node 2.
-        */
-        int TreeDistance(BspNode *n1, BspNode *n2) const;
 
         /** Collapses the tree with respect to the view cell partition.
@@ -316 +554 @@
                 the invalid view space.
         */
-        BspViewCell *GetOutOfBoundsCell();
+        VspViewCell *GetOutOfBoundsCell();
 
         /** Writes tree to output stream
@@ -332 +570 @@
         int CastBeam(Beam &beam);
 
-        /** Finds approximate neighbours, i.e., finds correct neighbors
-                in most cases but sometimes more.
-        */
-        int FindApproximateNeighbors(BspNode *n, 
-                                                             vector<BspLeaf *> &neighbors,
-                                                                 const bool onlyUnmailed) const;
 
         /** Checks if tree validity-flags are right 
@@ -410 +642 @@
         /** Evaluates render cost decrease of next split.
         */
-        float EvalRenderCostDecrease(const Plane3 &candidatePlane,
+        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
                                                                  const VspOspTraversalData &data) const;
 
@@ -419 +651 @@
         /** Collects view cells in the subtree under root.
         */
-        void CollectViewCells(BspNode *root, 
+        void CollectViewCells(VspNode *root, 
                                                   bool onlyValid, 
                                                   ViewCellContainer &viewCells,
@@ -427 +659 @@
                 the invalid view space. If it does not exist, it is created.
         */
-        BspViewCell *GetOrCreateOutOfBoundsCell();
+        VspViewCell *GetOrCreateOutOfBoundsCell();
 
         /** Collapses the tree with respect to the view cell partition,
@@ -436 +668 @@
                 this node otherwise
         */
-        BspNode *CollapseTree(BspNode *node, int &collapsed);
+        VspNode *CollapseTree(VspNode *node, int &collapsed);
 
         /** Helper function revalidating the view cell leaf list after merge.
@@ -451 +683 @@
                 @returns new root of the subtree
         */
-        BspNode *Subdivide(VspOspSplitQueue &tQueue,
+        VspNode *Subdivide(VspOspSplitQueue &tQueue,
                                            VspOspSplitCandidate &splitCandidate);
 
@@ -469 +701 @@
         */
 
-        BspInterior *SubdivideNode(const Plane3 &splitPlane,
+        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
                                                            VspOspTraversalData &tData,
                                                            VspOspTraversalData &frontData,
@@ -546 +778 @@
                 
         */
-        void AddToPvs(BspLeaf *leaf,
+        void AddToPvs(VspLeaf *leaf,
                                   const RayInfoContainer &rays, 
                                   float &sampleContributions,
@@ -553 +785 @@
         /** Propagates valid flag up the tree.
         */
-        void PropagateUpValidity(BspNode *node);
+        void PropagateUpValidity(VspNode *node);
 
         /** Writes the node to disk
@@ -559 +791 @@
         */
 #if ZIPPED_VIEWCELLS
-        void ExportNode(BspNode *node, ogzstream &stream);
+        void ExportNode(VspNode *node, ogzstream &stream);
 #else
-        void ExportNode(BspNode *node, ofstream &stream);
+        void ExportNode(VspNode *node, ofstream &stream);
 #endif
 
@@ -575 +807 @@
 
         /// Pointer to the root of the tree
-        BspNode *mRoot;
-                
-        BspTreeStatistics mBspStats;
+        VspNode *mRoot;
+                
+        VspTreeStatistics mVspStats;
         
         /// View cell corresponding to the space outside the valid view space
-        BspViewCell *mOutOfBoundsCell;
+        VspViewCell *mOutOfBoundsCell;
 
         /// box around the whole view domain