Changeset 241

Timestamp:

08/16/05 20:30:53 (19 years ago)

Author:

mattausch

Message:

added bsp stuff

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• KdTree.cpp (modified) (2 diffs)
• Plane3.h (modified) (1 diff)
• ViewCellBsp.cpp (modified) (7 diffs)
• ViewCellBsp.h (modified) (4 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -562 +562 @@
           // case P4
         }
-      }
+          }
       // $$ modification 3.5.2004 - hints from Kamil Ghais
       // case N4 or P4
@@ -569 +569 @@
       extp = ray.GetLoc() + ray.GetDir()*tdist;
       maxt = tdist;
-    } else {
+        } else {
       // compute intersection with all objects in this leaf
       KdLeaf *leaf = (KdLeaf *) node;

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -45 +45 @@
           const Vector3 v = b - a; // line from A to B
           float dv = DotProd(mNormal, v);
-          float u = 0;
+         
+          if (signum(dv) == 0)
+          {
+                  if (coplanar) 
+                          (*coplanar) = true;   
+
+                  return a;
+          }
+          
+          float u = - Distance(a) / dv; // TODO: could be done more efficiently
+          //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
+          if (coplanar) 
+                  (*coplanar) = false;
         
-          if (signum(dv) != 0)
-          {
-                  u = - Distance(a) / dv; // NOTE: could be done more efficiently
-                  //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
-                  if (coplanar) 
-                          (*coplanar) = false;
-          }
-          else if (coplanar) 
-          {
-                  (*coplanar) = true;     
-          }
-
           if (t) 
                   (*t) = u;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -6 +6 @@
 #include "Environment.h"
 #include "Polygon3.h"
+#include "Ray.h"
 
 #include <stack>
@@ -264 +265 @@
         
         PolygonContainer polys;
+
         // copy polygon information to guide the split process
-        CopyMesh2Polygons(viewCell->GetMesh(), polys);
+        AddMesh2Polygons(viewCell->GetMesh(), polys);
+        mBox.Include(viewCell->GetBox()); // also add to BSP root box
 
         BspNode *firstNode = mRoot ? mRoot : new BspLeaf(); // traverse tree or create new one
@@ -331 +334 @@
 }
 
-void BspTree::CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
+void BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
 {
         FaceContainer::const_iterator fi;
@@ -343 +346 @@
 }
 
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys)
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
 {
         ObjectContainer::const_iterator it, it_end = objects.end();
 
-        int limit = (maxPolys > 0) ? min((int)objects.size(), maxPolys) : (int)objects.size();
-
+        int limit = (maxObjects > 0) ? min((int)objects.size(), maxObjects) : (int)objects.size();
+        
+        // initialise bounding box
+        mBox.Initialize();
+  
         for (int i = 0; i < limit; ++i)
         {
@@ -363 +369 @@
                         mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
                         break;
+                        // TODO: handle transformed mesh instances
                 default:
                         break;
                 }
                 
-                if (mesh) // copy the mesh data to polygons
-                {
-                        CopyMesh2Polygons(mesh, polys);
-                }
-        }
-
-        Debug << "Number of polygons: " << polys.size() << endl;
+        if (mesh) // copy the mesh data to polygons
+                {
+                        mBox.Include(object->GetBox()); // also add to BSP root box
+                        AddMesh2Polygons(mesh, polys);
+                }
+        }
+
+        Debug << "Number of polygons: " << polys.size() << ", BSP root box: " << mBox << endl;
 }
 
@@ -391 +399 @@
         Copy2PolygonSoup(objects, *polys, 100);
 
-        BspTraversalData tData(new BspLeaf(), mRoot->GetParent(), polys, 0);
+        BspTraversalData tData(new BspLeaf(), mRoot->GetParent(), polys, 0); // new root corresponding to unbounded space
 
         tStack.push(tData);
@@ -687 +695 @@
 #endif
 }
+
+int BspTree::CastRay(Ray &ray)
+{
+        int hits = 0;
+  
+        stack<BspRayTraversalData> tStack;
+  
+        float maxt = 1e6;
+        float mint = 0;
+
+        Intersectable::NewMail();
+
+        // test with tree bounding box
+        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
+                return 0;
+
+        if (mint < 0)
+                mint = 0;
+  
+        maxt += Limits::Threshold;
+  
+        Vector3 entp = ray.Extrap(mint);
+        Vector3 extp = ray.Extrap(maxt);
+  
+        BspNode *node = mRoot;
+        BspNode *farChild;
+        
+        float position;
+
+        while (1) // endless loop
+        {
+                if (!node->IsLeaf()) 
+                {
+                        BspInterior *in = (BspInterior *) node;
+                        
+                        Plane3 *splitPlane = in->GetPlane();
+
+                        float t = 0;
+                        bool coplanar = false;
+                
+                        int entSide = splitPlane->Side(entp);
+                        int extSide = splitPlane->Side(extp);
+
+                        Vector3 intersection;
+
+                        if (entSide < 0)
+                        {
+                                if(extSide > 0) // plane splits ray
+                                {
+                                        node = in->GetBack();
+                                        farChild = in->GetFront();
+                                } else
+                                {
+                                        node = in->GetBack();
+                                        continue;
+                                } 
+                        }
+                        } else if (entSide > 0)
+                        {
+                                if (extSide < 0) // plane splits ray
+                                {
+                                        node = in->GetFront();
+                                        farChild = in->GetBack(); 
+                                } else
+                                {
+                                        node = in->GetFront();
+                                        continue;
+                                }
+                        }
+                        else // ray and plane are coincident // DOTO: WHAT IN THIS CASE ?
+                        {
+                                //node = in->GetFront();
+                                continue;
+                        }
+
+                    // case N4 or P4
+                        float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
+      tStack.push(RayTraversalData(farChild, extp, maxt));
+      extp = ray.GetLoc() + ray.GetDir()*tdist;
+      maxt = tdist;
+                        
+                        float tDist = 0;
+                        extp = splitPlane->FindIntersection(entp, extp, &t);
+
+                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+
+                        
+
+                                maxt = tDist;
+                        }
+                } else // compute intersections with objects in leaf
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                        //ray.leaves.push_back(leaf);
+      
+                        /*ObjectContainer::const_iterator mi;
+                        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi) 
+                        {
+                                Intersectable *object = *mi;
+                                if (!object->Mailed()) 
+                                {
+                                        object->Mail();
+                                        //ray.meshes.push_back(mesh);
+                                        hits += object->CastRay(ray);
+                                }
+                        }*/
+
+                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
+                                if (ray.intersections[0].mT <= maxt)
+                                        break;
+      
+                        // get the next node from the stack
+                        if (tStack.empty())
+                                break;
+      
+                        entp = extp;
+                        mint = maxt;
+                        BspRayTraversalData &s  = tStack.top();
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+
+                        tStack.pop();
+                }
+
+                return hits;
+        }
+}
+
 //} // GtpVisibilityPreprocessor

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -4 +4 @@
 #include "Mesh.h"
 #include "Containers.h"
+
+
 #include <queue>
 #include <stack>
@@ -19 +21 @@
 */
 typedef std::vector<Polygon3 *> PolygonContainer;
+
+struct BspRayTraversalData 
+{
+    BspNode *mNode;
+    Vector3 mExitPoint;
+    float mMaxT;
+    
+    BspRayTraversalData() {}
+
+    BspRayTraversalData(BspNode *n, const Vector3 &p, const float maxt):
+    mNode(n), mExitPoint(p), mMaxT(maxt) 
+        {}
+};
 
 class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
@@ -299 +314 @@
         Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const;
 
-        /** Extracts the meshes of the objects and copies them into the mesh.
-        */
-        static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys);
-
-        /** copy this mesh into polygons.
-        */
-        static void CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys);
+        /** Extracts the meshes of the objects and copies them into the mesh. Also calculcates the bounding box of the tree.
+                @param maxPolys the maximal number of objects to be stored as polygons
+        */
+        void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects);
+
+        /** Add this mesh as polygons to polygon container.
+        */
+        void AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys);
+
+        /** A ray is cast possible intersecting the tree.
+                @param the ray that is cast.
+                @returns the number of intersections with objects stored in the tree.
+        */
+        int CastRay(Ray &ray);
 
         /// Pointer to the root of the tree
@@ -321 +343 @@
         /// Strategies for choosing next split plane.
         enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED};
+
+        /// box around the whole view domain
+        AxisAlignedBox3 mBox;
 
 public: