Changeset 241 for trunk


Ignore:
Timestamp:
08/16/05 20:30:53 (19 years ago)
Author:
mattausch
Message:

added bsp stuff

Location:
trunk/VUT/GtpVisibilityPreprocessor/src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

    r191 r241  
    562562          // case P4 
    563563        } 
    564       } 
     564          } 
    565565      // $$ modification 3.5.2004 - hints from Kamil Ghais 
    566566      // case N4 or P4 
     
    569569      extp = ray.GetLoc() + ray.GetDir()*tdist; 
    570570      maxt = tdist; 
    571     } else { 
     571        } else { 
    572572      // compute intersection with all objects in this leaf 
    573573      KdLeaf *leaf = (KdLeaf *) node; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

    r239 r241  
    4545          const Vector3 v = b - a; // line from A to B 
    4646          float dv = DotProd(mNormal, v); 
    47           float u = 0; 
     47          
     48          if (signum(dv) == 0) 
     49          { 
     50                  if (coplanar)  
     51                          (*coplanar) = true;    
     52 
     53                  return a; 
     54          } 
     55           
     56          float u = - Distance(a) / dv; // TODO: could be done more efficiently 
     57          //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl; 
     58          if (coplanar)  
     59                  (*coplanar) = false; 
    4860         
    49           if (signum(dv) != 0) 
    50           { 
    51                   u = - Distance(a) / dv; // NOTE: could be done more efficiently 
    52                   //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl; 
    53                   if (coplanar)  
    54                           (*coplanar) = false; 
    55           } 
    56           else if (coplanar)  
    57           { 
    58                   (*coplanar) = true;      
    59           } 
    60  
    6161          if (t)  
    6262                  (*t) = u; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r240 r241  
    66#include "Environment.h" 
    77#include "Polygon3.h" 
     8#include "Ray.h" 
    89 
    910#include <stack> 
     
    264265         
    265266        PolygonContainer polys; 
     267 
    266268        // copy polygon information to guide the split process 
    267         CopyMesh2Polygons(viewCell->GetMesh(), polys); 
     269        AddMesh2Polygons(viewCell->GetMesh(), polys); 
     270        mBox.Include(viewCell->GetBox()); // also add to BSP root box 
    268271 
    269272        BspNode *firstNode = mRoot ? mRoot : new BspLeaf(); // traverse tree or create new one 
     
    331334} 
    332335 
    333 void BspTree::CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys) 
     336void BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys) 
    334337{ 
    335338        FaceContainer::const_iterator fi; 
     
    343346} 
    344347 
    345 void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys) 
     348void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects) 
    346349{ 
    347350        ObjectContainer::const_iterator it, it_end = objects.end(); 
    348351 
    349         int limit = (maxPolys > 0) ? min((int)objects.size(), maxPolys) : (int)objects.size(); 
    350  
     352        int limit = (maxObjects > 0) ? min((int)objects.size(), maxObjects) : (int)objects.size(); 
     353         
     354        // initialise bounding box 
     355        mBox.Initialize(); 
     356   
    351357        for (int i = 0; i < limit; ++i) 
    352358        { 
     
    363369                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh(); 
    364370                        break; 
     371                        // TODO: handle transformed mesh instances 
    365372                default: 
    366373                        break; 
    367374                } 
    368375                 
    369                 if (mesh) // copy the mesh data to polygons 
    370                 { 
    371                         CopyMesh2Polygons(mesh, polys); 
    372                 } 
    373         } 
    374  
    375         Debug << "Number of polygons: " << polys.size() << endl; 
     376        if (mesh) // copy the mesh data to polygons 
     377                { 
     378                        mBox.Include(object->GetBox()); // also add to BSP root box 
     379                        AddMesh2Polygons(mesh, polys); 
     380                } 
     381        } 
     382 
     383        Debug << "Number of polygons: " << polys.size() << ", BSP root box: " << mBox << endl; 
    376384} 
    377385 
     
    391399        Copy2PolygonSoup(objects, *polys, 100); 
    392400 
    393         BspTraversalData tData(new BspLeaf(), mRoot->GetParent(), polys, 0); 
     401        BspTraversalData tData(new BspLeaf(), mRoot->GetParent(), polys, 0); // new root corresponding to unbounded space 
    394402 
    395403        tStack.push(tData); 
     
    687695#endif 
    688696} 
     697 
     698int BspTree::CastRay(Ray &ray) 
     699{ 
     700        int hits = 0; 
     701   
     702        stack<BspRayTraversalData> tStack; 
     703   
     704        float maxt = 1e6; 
     705        float mint = 0; 
     706 
     707        Intersectable::NewMail(); 
     708 
     709        // test with tree bounding box 
     710        if (!mBox.GetMinMaxT(ray, &mint, &maxt)) 
     711                return 0; 
     712 
     713        if (mint < 0) 
     714                mint = 0; 
     715   
     716        maxt += Limits::Threshold; 
     717   
     718        Vector3 entp = ray.Extrap(mint); 
     719        Vector3 extp = ray.Extrap(maxt); 
     720   
     721        BspNode *node = mRoot; 
     722        BspNode *farChild; 
     723         
     724        float position; 
     725 
     726        while (1) // endless loop 
     727        { 
     728                if (!node->IsLeaf())  
     729                { 
     730                        BspInterior *in = (BspInterior *) node; 
     731                         
     732                        Plane3 *splitPlane = in->GetPlane(); 
     733 
     734                        float t = 0; 
     735                        bool coplanar = false; 
     736                 
     737                        int entSide = splitPlane->Side(entp); 
     738                        int extSide = splitPlane->Side(extp); 
     739 
     740                        Vector3 intersection; 
     741 
     742                        if (entSide < 0) 
     743                        { 
     744                                if(extSide > 0) // plane splits ray 
     745                                { 
     746                                        node = in->GetBack(); 
     747                                        farChild = in->GetFront(); 
     748                                } else 
     749                                { 
     750                                        node = in->GetBack(); 
     751                                        continue; 
     752                                }  
     753                        } 
     754                        } else if (entSide > 0) 
     755                        { 
     756                                if (extSide < 0) // plane splits ray 
     757                                { 
     758                                        node = in->GetFront(); 
     759                                        farChild = in->GetBack();  
     760                                } else 
     761                                { 
     762                                        node = in->GetFront(); 
     763                                        continue; 
     764                                } 
     765                        } 
     766                        else // ray and plane are coincident // DOTO: WHAT IN THIS CASE ? 
     767                        { 
     768                                //node = in->GetFront(); 
     769                                continue; 
     770                        } 
     771 
     772                    // case N4 or P4 
     773                        float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis); 
     774      tStack.push(RayTraversalData(farChild, extp, maxt)); 
     775      extp = ray.GetLoc() + ray.GetDir()*tdist; 
     776      maxt = tdist; 
     777                         
     778                        float tDist = 0; 
     779                        extp = splitPlane->FindIntersection(entp, extp, &t); 
     780 
     781                        tStack.push(BspRayTraversalData(farChild, extp, maxt)); 
     782 
     783                         
     784 
     785                                maxt = tDist; 
     786                        } 
     787                } else // compute intersections with objects in leaf 
     788                { 
     789                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 
     790                        //ray.leaves.push_back(leaf); 
     791       
     792                        /*ObjectContainer::const_iterator mi; 
     793                        for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi)  
     794                        { 
     795                                Intersectable *object = *mi; 
     796                                if (!object->Mailed())  
     797                                { 
     798                                        object->Mail(); 
     799                                        //ray.meshes.push_back(mesh); 
     800                                        hits += object->CastRay(ray); 
     801                                } 
     802                        }*/ 
     803 
     804                        if (hits && ray.GetType() == Ray::LOCAL_RAY) 
     805                                if (ray.intersections[0].mT <= maxt) 
     806                                        break; 
     807       
     808                        // get the next node from the stack 
     809                        if (tStack.empty()) 
     810                                break; 
     811       
     812                        entp = extp; 
     813                        mint = maxt; 
     814                        BspRayTraversalData &s  = tStack.top(); 
     815                        node = s.mNode; 
     816                        extp = s.mExitPoint; 
     817                        maxt = s.mMaxT; 
     818 
     819                        tStack.pop(); 
     820                } 
     821 
     822                return hits; 
     823        } 
     824} 
     825 
    689826//} // GtpVisibilityPreprocessor 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r240 r241  
    44#include "Mesh.h" 
    55#include "Containers.h" 
     6 
     7 
    68#include <queue> 
    79#include <stack> 
     
    1921*/ 
    2022typedef std::vector<Polygon3 *> PolygonContainer; 
     23 
     24struct BspRayTraversalData  
     25{ 
     26    BspNode *mNode; 
     27    Vector3 mExitPoint; 
     28    float mMaxT; 
     29     
     30    BspRayTraversalData() {} 
     31 
     32    BspRayTraversalData(BspNode *n, const Vector3 &p, const float maxt): 
     33    mNode(n), mExitPoint(p), mMaxT(maxt)  
     34        {} 
     35}; 
    2136 
    2237class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics 
     
    299314        Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const; 
    300315 
    301         /** Extracts the meshes of the objects and copies them into the mesh. 
    302         */ 
    303         static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxPolys); 
    304  
    305         /** copy this mesh into polygons. 
    306         */ 
    307         static void CopyMesh2Polygons(Mesh *mesh, PolygonContainer &polys); 
     316        /** Extracts the meshes of the objects and copies them into the mesh. Also calculcates the bounding box of the tree. 
     317                @param maxPolys the maximal number of objects to be stored as polygons 
     318        */ 
     319        void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects); 
     320 
     321        /** Add this mesh as polygons to polygon container. 
     322        */ 
     323        void AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys); 
     324 
     325        /** A ray is cast possible intersecting the tree. 
     326                @param the ray that is cast. 
     327                @returns the number of intersections with objects stored in the tree. 
     328        */ 
     329        int CastRay(Ray &ray); 
    308330 
    309331        /// Pointer to the root of the tree 
     
    321343        /// Strategies for choosing next split plane. 
    322344        enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED}; 
     345 
     346        /// box around the whole view domain 
     347        AxisAlignedBox3 mBox; 
    323348 
    324349public: 
Note: See TracChangeset for help on using the changeset viewer.