Changeset 327

Timestamp:

10/13/05 17:58:37 (19 years ago)

Author:

mattausch

Message:

worked on the ray based subdivision. finished extracting polygons from rays

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Mesh.h (modified) (3 diffs)
• Plane3.h (modified) (2 diffs)
• Polygon3.cpp (modified) (3 diffs)
• Polygon3.h (modified) (1 diff)
• Preprocessor.cpp (modified) (2 diffs)
• Ray.cpp (modified) (2 diffs)
• Ray.h (modified) (3 diffs)
• SamplingPreprocessor.cpp (modified) (2 diffs)
• ViewCellBsp.cpp (modified) (12 diffs)
• ViewCellBsp.h (modified) (4 diffs)
• X3dExporter.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.h

@@ -24 +24 @@
 class Face {
 public:
-  Face():mVertexIndices() {}
+  Face(): mVertexIndices() {}
   Face(const int a, const int b, const int c):mVertexIndices(3) {
     mVertexIndices[0] = a;
@@ -31 +31 @@
   }
 
-  Face(const int a, const int b, const int c, const int d):mVertexIndices(4) {
+  Face(const int a, const int b, const int c, const int d): 
+  mVertexIndices(4) {
     mVertexIndices[0] = a;
     mVertexIndices[1] = b;
@@ -41 +42 @@
   
   /// list of vertex pointers
-  VertexIndexContainer mVertexIndices;
+  VertexIndexContainer mVertexIndices;  
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -8 +8 @@
 class Plane3 {
 public:
+
   Vector3 mNormal;
   float mD;
@@ -28 +29 @@
     mD = -DotProd(normal, point);
   }
+
+  // relation of objects with the plane
+  enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
 
   float Distance(const Vector3 &v) const {

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -132 +132 @@
         int classification = ClassifyPlane(plane);
         
-        if (classification == BACK_SIDE)
+        if (classification == Plane3::BACK_SIDE)
                 return -1;
-        else if (classification == FRONT_SIDE)
+        else if (classification == Plane3::FRONT_SIDE)
                 return 1;
 
@@ -161 +161 @@
                 if (onFrontSide && onBackSide) // split 
                 {
-                        return SPLIT;
+                        return Plane3::SPLIT;
                 }
                 // 3 vertices enough to decide coincident
                 else if (((++ count) >= 3) && !onFrontSide && !onBackSide)
                 {   
-                        return COINCIDENT; 
+                        return Plane3::COINCIDENT; 
                 }
         }
@@ -172 +172 @@
         if (onBackSide)
         {
-                return BACK_SIDE;
+                return Plane3::BACK_SIDE;
         }
         else if (onFrontSide)
         {
-                return FRONT_SIDE;
-        }
-
-        return COINCIDENT; // plane and polygon are coincident
+                return Plane3::FRONT_SIDE;
+        }
+
+        return Plane3::COINCIDENT; // plane and polygon are coincident
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -42 +42 @@
                 @param splitPts returns the split points
         */
-        void Polygon3::Split(const Plane3 &partition, 
-                                                 Polygon3 &front, 
-                                                 Polygon3 &back, 
-                                                 VertexContainer &splitPts);
+        void Split(const Plane3 &partition, 
+                           Polygon3 &front, 
+                           Polygon3 &back, 
+                           VertexContainer &splitPts);
 
         /** Returns the area of this polygon.
         */
         float GetArea() const;
-
-        enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
 
         /** Classify polygon with respect to the plane.

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -152 +152 @@
 
         ObjectContainer objects;
-        RayContainer rays;
+        RayContainer *rays = new RayContainer();
 
         switch (BspTree::sConstructionMethod)
@@ -167 +167 @@
                 DeleteViewCells(); // we generate new view cells
                 mSceneGraph->CollectObjects(&objects);
-                mBspTree->Construct(objects, rays, &mViewCells);
+                mBspTree->Construct(rays, &mViewCells);
                 break;
         default:

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

@@ -1 +1 @@
 #include "Ray.h"
-
+#include "Plane3.h"
 
 // =========================================================
@@ -158 +158 @@
 }
 
+int Ray::ClassifyPlane(const Plane3 &plane, float minT, float maxT)
+{
+        Vector3 entp = Extrap(minT);
+        Vector3 extp = Extrap(maxT);
+  
+        int entSide = plane.Side(entp);
+        int extSide = plane.Side(extp);
+
+        if ((entSide == 0) && (extSide == 0)) 
+        {
+                return Plane3::COINCIDENT;
+        }
+        else if ((entSide <= 0) && (entSide <= 0))
+        {
+                return Plane3::BACK_SIDE;
+        }
+        else if ((entSide >= 0) && (entSide >= 0))
+        {
+                return Plane3::FRONT_SIDE;
+        }
+        
+        return Plane3::SPLIT;
+}
+
 ostream &
 operator<<(ostream &s, const PassingRaySet &set)

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.h

@@ -60 +60 @@
   vector<MeshInstance *> meshes;
   vector<ViewCell *> viewCells;
-
+  
   // constructors
   Ray(const Vector3 &wherefrom,
@@ -188 +188 @@
   void SetDepth(int newDepth) { depth = newDepth;}
   
+  /** Classifies ray with respect to the plane.
+  */
+  int ClassifyPlane(const Plane3 &plane, float minT, float maxT);
+
 private:
   Vector3 loc, dir;             // Describes ray origin and vector
@@ -222 +226 @@
 
   friend class AxisAlignedBox3;
-  friend class Plane;
+  friend class Plane3;
 
   // for CKDR GEMS

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -114 +114 @@
                 sampleContributions += AddObjectSamples(object, ray);
                                 
-                if (ray.intersections.size() > 0) // second intersection found
+                if (!ray.intersections.empty()) // second intersection found
                 {
                         sampleContributions += 
@@ -379 +379 @@
                                 rays[i].push_back(ray);
                         
-                        if (ray.intersections.size()) {
+                        if (!ray.intersections.empty()) {
                                         // check whether we can add this to the rays
                                 for (int j = 0; j < pvsOut; j++) {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -12 +12 @@
 #include <iomanip>
 #include "Exporter.h"
+#include "Plane3.h"
 
 int BspTree::sTermMaxPolygons = 10;
@@ -160 +161 @@
 {
         Polygon3 *splitPoly = NULL;
+
 #ifdef _Debug
         Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
@@ -170 +172 @@
                 //Debug << "New polygon with plane: " << poly->GetSupportingPlane() << "\n";
 
-                // get polygon classification
+                // classify polygon
                 int classification = poly->ClassifyPlane(mPlane);
 
@@ -180 +182 @@
                 switch (classification)
                 {
-                        case Polygon3::COINCIDENT:
+                        case Plane3::COINCIDENT:
                                 coincident.push_back(poly);
                                 break;                  
-                        case Polygon3::FRONT_SIDE:      
+                        case Plane3::FRONT_SIDE:        
                                 frontPolys.push_back(poly);
                                 break;
-                        case Polygon3::BACK_SIDE:
+                        case Plane3::BACK_SIDE:
                                 backPolys.push_back(poly);
                                 break;
-                        case Polygon3::SPLIT:
+                        case Plane3::SPLIT:
                                 front_piece = new Polygon3(poly->mParent);
                                 back_piece = new Polygon3(poly->mParent);
@@ -505 +507 @@
         mStat.polys = AddToPolygonSoup(viewCells, *polys);
 
-        // construct tree from viewcell polygons
-        Construct(polys);
+        // construct tree from the view cell polygons
+        Construct(polys, NULL);
 }
 
@@ -521 +523 @@
 
         // construct tree from polygon soup
-        Construct(polys, viewCells);
-}
-
-void BspTree::Construct(const ObjectContainer &objects,
-                                                const RayContainer &rays, 
+        Construct(polys, NULL, viewCells);
+}
+
+void BspTree::Construct(RayContainer *rays, 
                                                 ViewCellContainer *viewCells)
 {
         PolygonContainer *polys = new PolygonContainer();
         
-        // copy mesh instance polygons into one big polygon soup
-        mStat.polys = AddToPolygonSoup(objects, *polys);
-
-        RayContainer::const_iterator rit, rit_end = rays.end();
+        RayContainer::const_iterator rit, rit_end = rays->end();
 
         long startTime = GetTime();
-        Debug << "**** Casting rays into polygons ****\n";
-
-        //-- cast rays into all polygons
-        for (rit = rays.begin(); rit != rays.end(); ++ rit)
+        Debug << "**** Extracting polygons from rays ****\n";
+
+        std::map<Face *, Polygon3 *> facePolyMap;
+
+        //-- extract polygons from faces stored in the rays
+        for (rit = rays->begin(); rit != rit_end; ++ rit)
         {
                 Ray *ray = *rit;
-
-                PolygonContainer::const_iterator pit, pit_end = polys->end();
-                
-                for (pit = polys->begin(); pit != pit_end; ++ pit)
-                {
-                        Polygon3 *poly = *pit;
+        
+                for (int i = 0; i < (int)ray->intersections.size(); ++ i)
+                {
+                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->intersections[i].mObject);
+                        Face *face = obj->GetMesh()->mFaces[i];
                         
-                        float t = 0;
-                        float nearestT = 0;
-
-                        if (poly->CastRay(*ray, t, nearestT) > 0)
-                                poly->AddPiercingRay(ray);
-                }
-        }
-
-        Debug << "**** Finished ray casting ****\n";
+                         std::map<Face *, Polygon3 *>::iterator it= facePolyMap.find(face);
+
+                         if (it != facePolyMap.end()) 
+                         {
+                                 (*it).second->AddPiercingRay(ray);
+                         } 
+                         else
+                         {
+                                 Polygon3 *poly = new Polygon3(face, obj->GetMesh());
+                                 polys->push_back(poly);
+                                 poly->AddPiercingRay(ray);
+
+                                 facePolyMap[face] = poly;
+                         }
+                }
+        }
+
+        
+        mStat.polys = (int)polys->size();
+
+        Debug << "**** Finished polygon extraction ****\n";
         Debug << "ray casting time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-        Construct(polys, viewCells);
-}
-
-void BspTree::Construct(PolygonContainer *polys, ViewCellContainer *viewCells)
+        Construct(polys, rays, viewCells);
+}
+
+void BspTree::Construct(PolygonContainer *polys, RayContainer *rays, ViewCellContainer *viewCells)
 {
         std::stack<BspTraversalData> tStack;
         
-        BspTraversalData tData(new BspLeaf(), polys, 0, mRootCell);
+        BspTraversalData tData(new BspLeaf(), polys, 0, mRootCell, rays);
         tStack.push(tData);
 
@@ -670 +681 @@
                 RayContainer *backRays = new RayContainer();
 
-                Plane3 plane;
-                SplitRays(plane, *tData.mRays, *frontRays, *backRays);
+                SplitRays(interior->mPlane, *tData.mRays, *frontRays, *backRays);
         }
 
@@ -1022 +1032 @@
                 if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
                 {
-                        if (classification == Polygon3::COINCIDENT)
+                        if (classification == Plane3::COINCIDENT)
                                 sumPolyArea += (*it)->GetArea();
                         //totalArea += area;
@@ -1031 +1041 @@
                 {
                         float blockedRays = (float)(*it)->GetPiercingRays()->size();
-                        if (classification == Polygon3::COINCIDENT)
+                        if (classification == Plane3::COINCIDENT)
                         {
                                 sumBlockedRays += blockedRays;
@@ -1044 +1054 @@
                         MeshInstance *viewCell = (*it)->mParent;
                 
-                        if (classification == Polygon3::FRONT_SIDE)
+                        if (classification == Plane3::FRONT_SIDE)
                                 frontViewCells.push_back(viewCell);
-                        else if (viewCell && (classification == Polygon3::BACK_SIDE))
+                        else if (viewCell && (classification == Plane3::BACK_SIDE))
                                 backViewCells.push_back(viewCell);
                 }
@@ -1249 +1259 @@
 
         // bound ray
-        if ((ray.GetType() == Ray::LOCAL_RAY)   && 
-                ((int)ray.intersections.size() > 0) &&
+        if ((ray.GetType() == Ray::LOCAL_RAY) && 
+                (!ray.intersections.empty())      &&
             (ray.intersections[0].mT <= maxt))
         {
@@ -1383 +1393 @@
 }
 
+
 void BspTree::SplitRays(const Plane3 plane,
-                                                RayContainer &rays, 
-                                                RayContainer &frontRays, 
-                                                RayContainer &backRays)
+                                           RayContainer &rays, 
+                                           RayContainer &frontRays, 
+                                           RayContainer &backRays)
 {
         while (!rays.empty())
         {
-                //TODO
+                Ray *ray = rays.back();
+                rays.pop_back();
+
+                //-- ray-plane intersection
+                float maxT = 1e6;
+                float minT = 0;
+        
+                // test with tree bounding box
+                if (!mBox.GetMinMaxT(*ray, &minT, &maxT))
+                        continue;
+
+                if (minT < 0) // start ray from origin
+                        minT = 0;
+
+                // bound ray
+                if ((ray->GetType() == Ray::LOCAL_RAY) && 
+                        (ray->intersections.empty())      &&
+                        (ray->intersections[0].mT <= maxT))
+                {
+                        maxT = ray->intersections[0].mT;
+                }
+                
+                int classification = ray->ClassifyPlane(plane, minT, maxT);
+                
+                switch (classification)
+                {
+                case Plane3::COINCIDENT:
+                        break;
+                case Plane3::BACK_SIDE:
+                        backRays.push_back(ray);
+                        break;
+                case Plane3::FRONT_SIDE:
+                        frontRays.push_back(ray);
+                        break;
+                case Plane3::SPLIT:
+                        frontRays.push_back(ray);
+                        backRays.push_back(ray);
+                        //extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);
+                        break;
+                default:
+                        break;
+                }
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -287 +287 @@
         void Construct(const ObjectContainer &objects, ViewCellContainer *viewCells);
 
-        /** Constructs the tree from the given list of polygons.
-                @param viewCells if not NULL, new view cells are 
-                created in the leafs and stored in the conatainer
-        */
-        void Construct(PolygonContainer *polys, ViewCellContainer *viewCells = NULL);
-        
-        /** Constructs the tree from a list of scene geometry and a 
-                given bundle of rays.
-                @param objects list of objects
+        /** Constructs the tree from  a given bundle of rays.
                 @param rays the bundle of sample rays
                 @param viewCells if not NULL, new view cells are 
                 created in the leafs and stored in the conatainer
         */
-        void Construct(const ObjectContainer &objects,
-                                   const RayContainer &rays, 
+        void Construct(RayContainer *rays, 
                                    ViewCellContainer *viewCells = NULL);
 
@@ -353 +344 @@
         };
 
-        /** Evaluates the contribution of the candidate split plane.
-                @note the polygons can be reordered in the process.
-                @returns the cost of the candidate split plane
-        */
-        float SplitPlaneCost(PolygonContainer &polys, 
-                                                 const Plane3 &candidatePlane,
-                                                 const RayContainer &rays);
 
         /** Evaluates tree stats in the BSP tree leafs.
@@ -371 +355 @@
         */
         BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData);
+
+        /** Constructs the tree from the given list of polygons.
+                @param rayContainer stores bundle of rays on which subdivision may be based
+                @param viewCells if not NULL, new view cells are 
+                created in the leafs and stored in the conatainer
+        */
+        void Construct(PolygonContainer *polys, RayContainer *rays, ViewCellContainer *viewCells = NULL);
 
         /** Selects the best possible splitting plane. 
@@ -381 +372 @@
                                            PolygonContainer &polys,
                                            const RayContainer &ray);
+
+        /** Evaluates the contribution of the candidate split plane.
+                @note the polygons can be reordered in the process.
+                @returns the cost of the candidate split plane
+        */
+        float SplitPlaneCost(PolygonContainer &polys, 
+                                                 const Plane3 &candidatePlane,
+                                                 const RayContainer &rays);
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -667 +667 @@
                                 Polygon3 *backPoly = new Polygon3();
 
-                                if (planePoly->ClassifyPlane(*tData.mPlanes[i]) == Polygon3::SPLIT)
+                                if (planePoly->ClassifyPlane(*tData.mPlanes[i]) == Plane3::SPLIT)
                                 {
                                         planePoly->Split(*tData.mPlanes[i], *frontPoly, *backPoly, splitPts);