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

Timestamp:

06/13/06 08:03:35 (19 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• AxisAlignedBox3.cpp (modified) (1 diff)
• AxisAlignedBox3.h (modified) (1 diff)
• ViewCellBsp.h (modified) (1 diff)
• VspBspTree.cpp (modified) (2 diffs)
• VspKdTree.cpp (modified) (4 diffs)
• VspKdTree.h (modified) (1 diff)
• VspOspTree.cpp (modified) (16 diffs)
• VspOspTree.h (modified) (10 diffs)

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

@@ -2126 +2126 @@
                                                         const float value, 
                                                         AxisAlignedBox3 &left, 
-                                                        AxisAlignedBox3 &right)
+                                                        AxisAlignedBox3 &right) const
 {
         if ( (value >= mMin[axis]) && (value <= mMax[axis]) )

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

@@ -391 +391 @@
   void ExtractPolys(PolygonContainer &polys) const;
 
-  /** Splits the box into two separate boxes according to the split plane
-  */
-  void Split(const int axis, const float value, AxisAlignedBox3 &left, AxisAlignedBox3 &right);
+  /** Splits the box into two separate boxes with respect to the split plane
+  */
+  void Split(const int axis, const float value, AxisAlignedBox3 &left, AxisAlignedBox3 &right) const;
 
 #define __EXTENT_HACK

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

@@ -1084 +1084 @@
 {
         VssRay *vssRay;
-
         std::vector<BspIntersection> intersections;
-
         BspRay(VssRay *ray): vssRay(ray) {}
 };

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

@@ -2388 +2388 @@
         Intersectable::NewMail();
         ViewCell::NewMail();
+
         Vector3 entp = ray.Extrap(mint);
         Vector3 extp = ray.Extrap(maxt);
@@ -2424 +2425 @@
                         else // ray and plane are coincident
                         {
-                                // WHAT TO DO IN THIS CASE ?
+                                // matt: WHAT TO DO IN THIS CASE ?
                                 //break;
                                 node = in->GetFront();

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

@@ -1903 +1903 @@
 }
 
+
 AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
 {
@@ -1930 +1931 @@
 }
 
+
 int     VspKdTree::GetRootPvsSize() const
 {
@@ -1935 +1937 @@
 }
 
+
 const VspKdStatistics &VspKdTree::GetStatistics() const
 {
         return mStat;
 }
+
 
 void VspKdTree::AddRays(VssRayContainer &add)
@@ -1955 +1959 @@
                  mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
+
 
 float VspKdTree::GetRayMemUsage() const

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

@@ -592 +592 @@
     
                 LineTraversalData () {}
-                LineTraversalData (VspKdNode *n,
-                                                                  const Vector3 &p,
-                                                                  const float maxt):
+                LineTraversalData (VspKdNode *n, const Vector3 &p, const float maxt):
                 mNode(n), mExitPoint(p), mMaxT(maxt) {}
         };

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

@@ -156 +156 @@
 
 
+float VspInterior::GetPosition() const
+{
+        return mPlane.mPosition;
+}
+
+
+int VspInterior::GetAxis() const
+{
+        return mPlane.mAxis;
+}
+
+
 void VspInterior::ReplaceChildLink(VspNode *oldChild, VspNode *newChild) 
 {
@@ -172 +184 @@
 
 
+AxisAlignedBox3 VspInterior::GetBox() const
+{
+        return mBox;
+}
+
+
+void VspInterior::SetBox(const AxisAlignedBox3 &box)
+{
+        mBox = box;
+}
+
+
+int VspInterior::Type() const
+{
+        return Interior;
+}
+
 /****************************************************************/
 /*                  class VspLeaf implementation                */
@@ -186 +215 @@
         DEL_PTR(mPvs);
 }
+
+int VspLeaf::Type() const
+{
+        return Leaf;
+}
+
 
 
@@ -1381 +1416 @@
 
 
-int VspOspTree::CastRay(Ray &ray)
-{
-        int hits = 0;
-#if TODO
-        stack<BspRayTraversalData> tQueue;
-
-        float maxt, mint;
-
-        if (!mBox.GetRaySegment(ray, mint, maxt))
-                return 0;
-
-        Intersectable::NewMail();
+void VspOspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
+{
         ViewCell::NewMail();
-
-        Vector3 entp = ray.Extrap(mint);
-        Vector3 extp = ray.Extrap(maxt);
-
-        VspNode *node = mRoot;
-        VspNode *farChild = NULL;
-
-        while (1)
-        {
-                if (!node->IsLeaf())
-                {
-                        VspInterior *in = dynamic_cast<VspInterior *>(node);
-
-                        Plane3 splitPlane = in->GetPlane();
-                        const int entSide = splitPlane.Side(entp);
-                        const int extSide = splitPlane.Side(extp);
-
-                        if (entSide < 0)
-                        {
-                                node = in->GetBack();
-
-                                if(extSide <= 0) // plane does not split ray => no far child
-                                        continue;
-
-                                farChild = in->GetFront(); // plane splits ray
-
-                        } else if (entSide > 0)
-                        {
-                                node = in->GetFront();
-
-                                if (extSide >= 0) // plane does not split ray => no far child
-                                        continue;
-
-                                farChild = in->GetBack(); // plane splits ray
-                        }
-                        else // ray and plane are coincident
-                        {
-                                // WHAT TO DO IN THIS CASE ?
-                                //break;
-                                node = in->GetFront();
-                                continue;
-                        }
-
-                        // push data for far child
-                        tQueue.push(VspRayTraversalData(farChild, extp, maxt));
-
-                        // find intersection of ray segment with plane
-                        float t;
-                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
-                        maxt *= t;
-
-                } else // reached leaf => intersection with view cell
-                {
-                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
-
-                        if (!leaf->GetViewCell()->Mailed())
-                        {
-                                //ray.bspIntersections.push_back(Ray::VspOspIntersection(maxt, leaf));
-                                leaf->GetViewCell()->Mail();
-                                ++ hits;
-                        }
-
-                        //-- fetch the next far child from the stack
-                        if (tQueue.empty())
-                                break;
-
-                        entp = extp;
-                        mint = maxt; // NOTE: need this?
-
-                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
-                                break;
-
-                        BspRayTraversalData &s = tQueue.top();
-
-                        node = s.mNode;
-                        extp = s.mExitPoint;
-                        maxt = s.mMaxT;
-
-                        tQueue.pop();
-                }
-        }
-#endif
-        return hits;
-}
-
-
-void VspOspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
-{
-        ViewCell::NewMail();
-        
         CollectViewCells(mRoot, onlyValid, viewCells, true);
 }
@@ -1647 +1582 @@
 
 
-int VspOspTree::FindNeighbors(VspNode *n, vector<VspLeaf *> &neighbors,
+int VspOspTree::FindNeighbors(VspLeaf *n,
+                                                          vector<VspLeaf *> &neighbors,
                                                           const bool onlyUnmailed) const
 {
-        // TODO
-        return 0;
-}
-
-
-VspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &halfspace)
-{
-#if TODO
-    stack<VspNode *> nodeStack;
-        nodeStack.push(mRoot);
-
-        int mask = rand();
+        stack<VspNode *> nodeStack;
+
+        nodeStack.push(mRoot);
+
+        const AxisAlignedBox3 box = GetBBox(n);
 
         while (!nodeStack.empty())
@@ -1670 +1599 @@
                 if (node->IsLeaf())
                 {
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
+
+                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
+                                neighbors.push_back(leaf);
+                }
+                else
+                {
+                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
+                        
+                        if (interior->GetPosition() > box.Max(interior->GetAxis()))
+                                nodeStack.push(interior->GetBack());
+                        else
+                        {
+                                if (interior->GetPosition() < box.Min(interior->GetAxis()))
+                                        nodeStack.push(interior->GetFront());
+                                else
+                                {
+                                        // random decision
+                                        nodeStack.push(interior->GetBack());
+                                        nodeStack.push(interior->GetFront());
+                                }
+                        }
+                }
+        }
+
+        return (int)neighbors.size();
+}
+
+
+// Find random neighbor which was not mailed
+VspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &plane)
+{
+        stack<VspNode *> nodeStack;
+        nodeStack.push(mRoot);
+  
+        int mask = rand();
+  
+        while (!nodeStack.empty()) 
+        {
+                VspNode *node = nodeStack.top();
+                
+                nodeStack.pop();
+                
+                if (node->IsLeaf()) 
+                {
                         return dynamic_cast<VspLeaf *>(node);
-                }
-                else
+                } 
+                else 
                 {
                         VspInterior *interior = dynamic_cast<VspInterior *>(node);
                         VspNode *next;
-                        BspNodeGeometry geom;
-
-                        // todo: not very efficient: constructs full cell everytime
-                        ConstructGeometry(interior, geom);
-
-                        const int cf = 
-                                Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
-
-                        if (cf == Polygon3::BACK_SIDE)
+                        
+                        if (GetBBox(interior->GetBack()).Side(plane) < 0)
                                 next = interior->GetFront();
-                        else
-                                if (cf == Polygon3::FRONT_SIDE)
-                                        next = interior->GetFront();
-                        else
-                        {
-                                // random decision
-                                if (mask & 1)
+            else
+                                if (GetBBox(interior->GetFront()).Side(plane) < 0)
                                         next = interior->GetBack();
-                                else
-                                        next = interior->GetFront();
-                                mask = mask >> 1;
-                        }
-
-                        nodeStack.push(next);
-                }
-        }
-#endif
+                                else 
+                                {
+                                        // random decision
+                                        if (mask & 1)
+                                                next = interior->GetBack();
+                                        else
+                                                next = interior->GetFront();
+                                        mask = mask >> 1;
+                                }
+
+                                nodeStack.push(next);
+                }
+        }
+  
         return NULL;
 }
@@ -1783 +1750 @@
 
 
-
 int VspOspTree::CastLineSegment(const Vector3 &origin,
                                                                 const Vector3 &termination,
@@ -1789 +1755 @@
 {
         int hits = 0;
-#if TODO
-        stack<VspRayTraversalData> tStack;
 
         float mint = 0.0f, maxt = 1.0f;
+        const Vector3 dir = termination - origin;
+
+        stack<LineTraversalData> tStack;
 
         Intersectable::NewMail();
@@ -1801 +1768 @@
 
         VspNode *node = mRoot;
-        VspNode *farChild = NULL;
-
-        float t;
-        const float thresh = 1e-6f; // matt: change this to adjustable value
-        
+        VspNode *farChild;
+
+        float position;
+        int axis;
+
         while (1)
         {
@@ -1811 +1778 @@
                 {
                         VspInterior *in = dynamic_cast<VspInterior *>(node);
-
-                        Plane3 splitPlane = in->GetPlane();
-                        
-                        const int entSide = splitPlane.Side(entp, thresh);
-                        const int extSide = splitPlane.Side(extp, thresh);
-
-                        if (entSide < 0) 
-                        {
-                                node = in->GetBack();
-                                
-                                // plane does not split ray => no far child
-                                if (extSide <= 0) 
+                        position = in->GetPosition();
+                        axis = in->GetAxis();
+
+                        if (entp[axis] <= position)
+                        {
+                                if (extp[axis] <= position)
+                                {
+                                        node = in->GetBack();
+                                        // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-  
-                                farChild = in->GetFront(); // plane splits ray
-                        } 
-                        else if (entSide > 0)
-                        {
-                                node = in->GetFront();
-
-                                if (extSide >= 0) // plane does not split ray => no far child
+                                } else
+                                {
+                                        // case N4
+                                        node = in->GetBack();
+                                        farChild = in->GetFront();
+                                }
+                        }
+                        else
+                        {
+                                if (position <= extp[axis])
+                                {
+                                        node = in->GetFront();
+                                        // cases P1,P2,P3,N5,Z1
                                         continue;
-
-                                farChild = in->GetBack(); // plane splits ray
-                        }
-                        else // one of the ray end points is on the plane
-                        {       // NOTE: what to do if ray is coincident with plane?
-                                if (extSide < 0)
-                                        node = in->GetBack();
-                                else //if (extSide > 0)
+                                }
+                                else
+                                {
                                         node = in->GetFront();
-                                //else break; // coincident => count no intersections
-
-                                continue; // no far child
-                        }
-
-                        // push data for far child
-                        tStack.push(VspRayTraversalData(farChild, extp));
-
-                        // find intersection of ray segment with plane
-                        extp = splitPlane.FindIntersection(origin, extp, &t);
-                } 
+                                        farChild = in->GetBack();
+                                        // case P4
+                                }
+                        }
+
+                        // $$ modification 3.5.2004 - hints from Kamil Ghais
+                        // case N4 or P4
+                        const float tdist = (position - origin[axis]) / dir[axis];
+                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
+
+                        extp = origin + dir * tdist;
+                        maxt = tdist;
+                }
                 else
                 {
-                        // reached leaf => intersection with view cell
+                        // compute intersection with all objects in this leaf
                         VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
-                        ViewCell *viewCell;
-                        
-                        if (0)
-                                viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
-                        else
-                                viewCell = leaf->GetViewCell();
-
-                        if (!viewCell->Mailed())
-                        {
-                                viewcells.push_back(viewCell);
-                                viewCell->Mail();
+                        ViewCell *vc = leaf->GetViewCell();
+
+                        if (!vc->Mailed())
+                        {
+                                vc->Mail();
+                                viewcells.push_back(vc);
                                 ++ hits;
                         }
-
-                        //-- fetch the next far child from the stack
+#if 0
+                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
+#endif
+                        // get the next node from the stack
                         if (tStack.empty())
                                 break;
 
                         entp = extp;
+                        mint = maxt;
                         
-                        const BspRayTraversalData &s = tStack.top();
-
+                        LineTraversalData &s  = tStack.top();
                         node = s.mNode;
                         extp = s.mExitPoint;
-
+                        maxt = s.mMaxT;
                         tStack.pop();
                 }
         }
+
+        return hits;
+}
+
+
+int VspOspTree::CastRay(Ray &ray)
+{
+        int hits = 0;
+
+        stack<LineTraversalData> tStack;
+        const Vector3 dir = ray.GetDir();
+
+        float maxt, mint;
+
+        if (!mBox.GetRaySegment(ray, mint, maxt))
+                return 0;
+
+        Intersectable::NewMail();
+        ViewCell::NewMail();
+
+        Vector3 entp = ray.Extrap(mint);
+        Vector3 extp = ray.Extrap(maxt);
+
+        const Vector3 origin = entp;
+
+        VspNode *node = mRoot;
+        VspNode *farChild = NULL;
+
+        float position;
+        int axis;
+
+        while (1)
+        {
+                if (!node->IsLeaf())
+                {
+                        VspInterior *in = dynamic_cast<VspInterior *>(node);
+                        position = in->GetPosition();
+                        axis = in->GetAxis();
+
+                        if (entp[axis] <= position)
+                        {
+                                if (extp[axis] <= position)
+                                {
+                                        node = in->GetBack();
+                                        // cases N1,N2,N3,P5,Z2,Z3
+                                        continue;
+                                } else
+                                {
+                                        // case N4
+                                        node = in->GetBack();
+                                        farChild = in->GetFront();
+                                }
+                        }
+                        else
+                        {
+                                if (position <= extp[axis])
+                                {
+                                        node = in->GetFront();
+                                        // cases P1,P2,P3,N5,Z1
+                                        continue;
+                                }
+                                else
+                                {
+                                        node = in->GetFront();
+                                        farChild = in->GetBack();
+                                        // case P4
+                                }
+                        }
+
+                        // $$ modification 3.5.2004 - hints from Kamil Ghais
+                        // case N4 or P4
+                        const float tdist = (position - origin[axis]) / dir[axis];
+                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
+                        extp = origin + dir * tdist;
+                        maxt = tdist;
+                }
+                else
+                {
+                        // compute intersection with all objects in this leaf
+                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
+                        ViewCell *vc = leaf->GetViewCell();
+
+                        if (!vc->Mailed())
+                        {
+                                vc->Mail();
+                                // todo: add view cells to ray
+                                ++ hits;
+                        }
+
+#if 0
+                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
 #endif
+                        // get the next node from the stack
+                        if (tStack.empty())
+                                break;
+
+                        entp = extp;
+                        mint = maxt;
+                        
+                        LineTraversalData &s  = tStack.top();
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+                        tStack.pop();
+                }
+        }
+
         return hits;
 }
-
 
 
@@ -2014 +2082 @@
                 {       
                         VspInterior *interior = dynamic_cast<VspInterior *>(node);
-#if TODO        
+     
                         // random decision
-                        if (interior->GetPlane().Side(point) < 0)
+                        if (interior->GetPosition() - point[interior->GetAxis()] < 0)
                                 nodeStack.push(interior->GetBack());
                         else
                                 nodeStack.push(interior->GetFront());
-#endif
                 }
         }
@@ -2033 +2100 @@
 bool VspOspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
-#if TODO
         VspNode *node = mRoot;
 
@@ -2047 +2113 @@
                 VspInterior *in = dynamic_cast<VspInterior *>(node);
                                         
-                if (in->GetPlane().Side(viewPoint) <= 0) 
+                if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0) 
                 {
                         node = in->GetBack();
@@ -2056 +2122 @@
                 }
         }
-#endif
+
         // should never come here
         return false;
@@ -2120 +2186 @@
         }
         else
-        {
-#if TODO        
+        {       
                 VspInterior *interior = dynamic_cast<VspInterior *>(node);
         
-                Plane3 plane = interior->GetPlane();
-                stream << "<Interior plane=\"" << plane.mNormal.x << " " 
-                           << plane.mNormal.y << " " << plane.mNormal.z << " " 
-                           << plane.mD << "\">" << endl;
+                AxisAlignedPlane plane = interior->GetPlane();
+                stream << "<Interior plane=\"" << plane.mPosition << " " 
+                           << plane.mAxis << "\">" << endl;
 
                 ExportNode(interior->GetBack(), stream);
                 ExportNode(interior->GetFront(), stream);
-#endif
+
                 stream << "</Interior>" << endl;
         }
@@ -2186 +2250 @@
 }
 
-}
+
+AxisAlignedBox3 VspOspTree::GetBBox(VspNode *node) const
+{
+        if (!node->GetParent())
+                return mBox;
+
+        if (!node->IsLeaf())
+        {
+                return (dynamic_cast<VspInterior *>(node))->GetBox();           
+        }
+
+        VspInterior *parent = dynamic_cast<VspInterior *>(node->GetParent());
+
+        AxisAlignedBox3 box(parent->GetBox());
+
+        if (parent->GetFront() == node)
+                box.SetMin(parent->GetAxis(), parent->GetPosition());
+        else
+                box.SetMax(parent->GetAxis(), parent->GetPosition());
+
+        return box;
+}
+
+
+}

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

@@ -144 +144 @@
 class VspNode 
 {
-
 public:
+        
+        // types of vsp nodes
+        enum {Interior, Leaf};
+
         VspNode();
         virtual ~VspNode(){};
@@ -154 +157 @@
         */
         virtual bool IsLeaf() const = 0;
+
+        virtual int Type() const;
 
         /** Determines whether this node is a root
@@ -215 +220 @@
         bool IsLeaf() const;
 
+        int Type() const;
+
         VspNode *GetBack();
         VspNode *GetFront();
@@ -221 +228 @@
         */
         AxisAlignedPlane GetPlane() const;
+
+        /** Returns position of split plane.
+        */
+        float GetPosition() const;
+
+        /** Returns split axis.
+        */
+        int GetAxis() const;
 
         /** Replace front or back child with new child.
@@ -234 +249 @@
         }
 
+        AxisAlignedBox3 GetBox() const;
+        void SetBox(const AxisAlignedBox3 &box);
+
 protected:
+
+        AxisAlignedBox3 mBox;
 
         /// Splitting plane corresponding to this node
@@ -263 +283 @@
         bool IsLeaf() const;
         
+                virtual int Type() const;
+
         /** Returns pointer of view cell.
         */
@@ -414 +436 @@
         
 
+        /** Struct for traversing line segment.
+        */
+        struct LineTraversalData 
+        {
+                VspNode *mNode;
+                Vector3 mExitPoint;
+                
+                float mMaxT;
+    
+                LineTraversalData () {}
+                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
+                mNode(n), mExitPoint(p), mMaxT(maxt) {}
+        };
+
         typedef std::priority_queue<VspOspTraversalData> VspOspTraversalQueue;
         
-        
+        /** candidate for a view space split
+        */
         struct VspOspSplitCandidate
         {  
@@ -466 +503 @@
         const VspTreeStatistics &GetStatistics() const; 
   
+        /** Returns bounding box of the specified node.
+        */
+        AxisAlignedBox3 GetBBox(VspNode *node) const;
 
         /** Constructs the tree from a given set of rays.
@@ -506 +546 @@
         /** finds neighbouring leaves of this tree node.
         */
-        int FindNeighbors(VspNode *n, 
+        int FindNeighbors(VspLeaf *n, 
                                           vector<VspLeaf *> &neighbors, 
                                           const bool onlyUnmailed) const;
@@ -594 +634 @@
                 @returns number of view cells found
         */
-        int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
+        int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
+                                                                ViewCellContainer &viewCells) const;
 
         // pointer to the hierarchy of view cells