Changeset 437


Ignore:
Timestamp:
11/25/05 22:31:30 (19 years ago)
Author:
mattausch
Message:

detected leak in BspTree?
added specialised fast view cell bsp tree called VspBspTree?

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
2 added
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

    r420 r437  
    300300                        </File> 
    301301                        <File 
     302                                RelativePath="..\src\VspBspTree.cpp"> 
     303                        </File> 
     304                        <File 
     305                                RelativePath="..\src\VspBspTree.h"> 
     306                        </File> 
     307                        <File 
    302308                                RelativePath="..\src\VspKdTree.cpp"> 
    303309                        </File> 

  • trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

    r436 r437  
    1919 
    2020Preprocessor { 
    21         #type sampling 
     21#       type sampling 
    2222        type vss 
    2323} 
    … …  
    184184        Termination { 
    185185                # parameters used for autopartition 
    186                 minRays 200 
     186                minRays 300 
    187187                minPolygons -1 
    188                 maxDepth 30 
    189                 minPvs 150 
     188                maxDepth 20 
     189                minPvs 400 
    190190                minArea 0.01 
    191191                maxRayContribution 0.005 

  • trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

    r396 r437  
    1515   
    1616  Plane3(const Vector3 &a, 
    17         const Vector3 &b, 
    18         const Vector3 &c 
     17                const Vector3 &b, 
     18                const Vector3 &c 
    1919         ) { 
    2020    Vector3 v1=a-b, v2=c-b; 
    … …  
    4444  } 
    4545 
     46  /** Finds intersection of line segment between points a and b with plane. 
     47          @param a start point 
     48          @param b end point 
     49          @param t if not NULL, returns parameter value of intersections 
     50          @param coplanar if not NULL, returns true if plane and line segments are coplanar. 
     51  */ 
    4652  Vector3 FindIntersection(const Vector3 &a, 
    4753                           const Vector3 &b, 
    … …  
    5662        { 
    5763                if (coplanar) (*coplanar) = true;        
    58                 if (t) (*t) = 1; 
     64                if (t) (*t) = 0; 
    5965                return a; 
    6066        } 
    … …  
    6874  } 
    6975   
     76  /** Finds value of intersection parameter t on line segment from a to b. 
     77      @returns -1 if coplanar, else parameter t 
     78  */ 
    7079  float FindT(const Vector3 &a, 
    7180                          const Vector3 &b) const  
    … …  
    7483          const float dv = DotProd(v, mNormal); 
    7584     
     85          // does not intersect 
    7686          if (signum(dv) == 0) 
    77                   return 1; 
     87                  return -1; 
    7888         
    7989          return - Distance(a) / dv; // TODO: could be done more efficiently 

  • trunk/VUT/GtpVisibilityPreprocessor/src/RayInfo.cpp

    r432 r437  
    22#include "Ray.h" 
    33#include "VssRay.h" 
     4#include "Plane3.h" 
    45 
    56RayInfo::RayInfo(): mRay(NULL), mMinT(0), 
    … …  
    5152        return mRay->GetOrigin(axis) + GetMaxT()*mRay->GetDir(axis); 
    5253} 
     54 
     55Vector3 RayInfo::ExtrapOrigin() const  
     56{ 
     57        return mRay->GetOrigin() * mRay->GetDir(); 
     58} 
    5359                 
     60Vector3 RayInfo::ExtrapTermination() const  
     61{ 
     62        return mRay->GetOrigin() + GetMaxT() * mRay->GetDir(); 
     63} 
     64 
    5465#if USE_FIXEDPOINT_T 
    5566        float RayInfo::GetMinT () const  
    … …  
    117128        return 0; 
    118129} 
     130 
     131 
     132int RayInfo::ComputeRayIntersection(const Plane3 &splitPlane, float &t) const 
     133{        
     134        t = splitPlane.FindT(mRay->GetOrigin(), mRay->GetTermination()); 
     135 
     136        if ((t < GetMinT()) || (t > GetMaxT())) 
     137                return splitPlane.Side(ExtrapOrigin()); 
     138 
     139        return 0; 
     140} 
     141 
     142float RayInfo::SegmentLength() const 
     143{ 
     144        return Distance(ExtrapOrigin(), ExtrapTermination()); 
     145} 
     146 
     147float RayInfo::SqrSegmentLength() const 
     148{ 
     149        return SqrDistance(ExtrapOrigin(), ExtrapTermination()); 
     150} 

  • trunk/VUT/GtpVisibilityPreprocessor/src/RayInfo.h

    r420 r437  
    77class VssRay; 
    88class RayInfo; 
     9class Plane3; 
     10class Vector3; 
    911 
    1012typedef vector<RayInfo> RayInfoContainer; 
    … …  
    4042        } 
    4143         
     44        /** Extracts the scalar of the starting point of the ray segment 
     45                that lies in the axis. 
     46        */ 
     47        float ExtrapOrigin(const int axis) const; 
     48        /** Extracts the scalar of the termination point of the ray segment 
     49                that lies in the axis. 
     50        */ 
     51        float ExtrapTermination(const int axis) const; 
    4252         
    43         float ExtrapOrigin(const int axis) const; 
     53        /** Extracts the starting point of the ray segment. 
     54        */ 
     55        Vector3 ExtrapOrigin() const; 
    4456         
    45         float ExtrapTermination(const int axis) const; 
     57        /** Extracts the end point of the ray segment. 
     58        */ 
     59        Vector3 ExtrapTermination() const; 
    4660         
    4761        float GetMinT () const; 
    … …  
    5266        void SetMaxT (const float t); 
    5367 
     68        float SegmentLength() const; 
     69        float SqrSegmentLength() const; 
     70 
    5471        /** Computes intersection of this ray with the axis aligned split plane. 
     72         
    5573                @param axis axis of the split plane 
    56                 @param position position of the split plane 
    57                 @param t returns the t value of the ray intersection 
     74                @param position scalar position of the split plane for the chosen axis 
     75                @param t returns the t parameter value of the ray intersection 
    5876 
    5977                @returns 0 if ray intersects plane, -1 if on back side of plane, 1 if on front side 
    6078        */ 
    6179        int ComputeRayIntersection(const int axis, const float position, float &t) const; 
     80 
     81        /** Computes intersection of this ray with the split plane. 
     82 
     83                @param splitPlane the split plane 
     84                @param t returns the t parameter value of the ray intersection 
     85 
     86                @returns 0 if ray intersects plane, -1 if on back side of plane, 1 if on front side 
     87        */ 
     88        int ComputeRayIntersection(const Plane3 &splitPlane, float &t) const; 
    6289}; 
    6390 

  • trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

    r433 r437  
    6464        { 
    6565        case BspTree::FROM_INPUT_VIEW_CELLS: 
    66                 mBspTree->SetGenerateViewCells(false); 
    6766                mBspTree->Construct(mViewCells); 
    6867                break; 
    6968        case BspTree::FROM_SCENE_GEOMETRY: 
    7069                DeleteViewCells(); // we generate new view cells 
    71                 mBspTree->SetGenerateViewCells(true); 
    7270                mSceneGraph->CollectObjects(&objects); 
    7371                mBspTree->Construct(objects); 
    … …  
    7573        case BspTree::FROM_SAMPLES: 
    7674                DeleteViewCells(); // we generate new view cells 
    77                 mBspTree->SetGenerateViewCells(true); 
    7875                mBspTree->Construct(mSampleRays); 
    7976                break; 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r436 r437  
    124124                                                           PolygonContainer &coincident) 
    125125{ 
    126         Polygon3 *splitPoly = NULL; 
    127  
    128126        int splits = 0; 
    129127 
    … …  
    140138                // classify polygon 
    141139                const int cf = poly->ClassifyPlane(mPlane); 
    142  
    143                 Polygon3 *front_piece = NULL; 
    144                 Polygon3 *back_piece = NULL; 
    145140 
    146141                switch (cf) 
    … …  
    156151                                break; 
    157152                        case Polygon3::SPLIT: 
    158                                 front_piece = new Polygon3(poly->mParent); 
    159                                 back_piece = new Polygon3(poly->mParent); 
    160  
    161                                 //-- split polygon into front and back part 
    162                                 poly->Split(mPlane,  
    163                                                         *front_piece,  
    164                                                         *back_piece); 
     153                                { 
     154                                        Polygon3 *front_piece = new Polygon3(poly->mParent); 
     155                                        Polygon3 *back_piece = new Polygon3(poly->mParent); 
     156 
     157                                        //-- split polygon into front and back part 
     158                                        poly->Split(mPlane, *front_piece, *back_piece); 
    165159                                         
    166                                 ++ splits; // increase number of splits 
    167  
    168                                 //-- inherit rays from parent polygon for blocked ray criterium 
    169                                 poly->InheritRays(*front_piece, *back_piece); 
    170                                 //Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl; 
     160                                        ++ splits; // increase number of splits 
     161 
     162                                        //-- inherit rays from parent polygon for blocked ray criterium 
     163                                        poly->InheritRays(*front_piece, *back_piece); 
     164                                        //Debug << "p: " << poly->mPiercingRays.size() << " f: " << front_piece->mPiercingRays.size() << " b: " << back_piece->mPiercingRays.size() << endl; 
    171165                                 
    172                                 // check if polygons still valid  
    173                                 if (front_piece->Valid()) 
    174                                         frontPolys.push_back(front_piece); 
    175                                 else 
    176                                         DEL_PTR(front_piece); 
     166                                        // check if polygons still valid  
     167                                        if (front_piece->Valid()) 
     168                                                frontPolys.push_back(front_piece); 
     169                                        else 
     170                                                DEL_PTR(front_piece); 
    177171                                 
    178                                 if (back_piece->Valid()) 
    179                                         backPolys.push_back(back_piece); 
    180                                 else                             
    181                                         DEL_PTR(back_piece); 
     172                                        if (back_piece->Valid()) 
     173                                                backPolys.push_back(back_piece); 
     174                                        else                             
     175                                                DEL_PTR(back_piece); 
    182176                                 
    183177#ifdef _DEBUG 
    184                                 Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl; 
     178                                        Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl; 
    185179#endif 
    186                                 DEL_PTR(poly);                   
     180                                        DEL_PTR(poly); 
     181                                } 
    187182                                break; 
    188183                        default: 
    … …  
    273268mRootCell(viewCell),  
    274269mRoot(NULL),  
    275 mGenerateViewCells(false), 
    276270mStoreLeavesWithRays(false), 
    277 mPvsUseArea(true) 
     271mPvsUseArea(true), 
     272mGenerateViewCells(true) 
    278273{ 
    279274        Randomize(); // initialise random generator for heuristics 
    … …  
    447442        PolygonContainer *polys = new PolygonContainer(); 
    448443 
     444        // don't generate new view cell, insert this one 
     445        mGenerateViewCells = false; 
    449446        // extract polygons that guide the split process 
    450447        mStat.polys += AddMeshToPolygons(viewCell->GetMesh(), *polys, viewCell); 
    … …  
    457454{        
    458455        std::stack<BspTraversalData> tStack; 
    459          
     456 
    460457        // traverse existing tree or create new tree 
    461458    if (!mRoot) 
    … …  
    624621        mStat.polys = AddToPolygonSoup(viewCells, *polys); 
    625622 
     623        // view cells are given 
     624        mGenerateViewCells = false; 
    626625        // construct tree from the view cell polygons 
    627626        Construct(polys, new BoundedRayContainer()); 
    … …  
    635634         
    636635        PolygonContainer *polys = new PolygonContainer(); 
    637          
     636 
     637        mGenerateViewCells = true; 
    638638        // copy mesh instance polygons into one big polygon soup 
    639639        mStat.polys = AddToPolygonSoup(objects, *polys); 
    … …  
    652652 
    653653        RayContainer::const_iterator rit, rit_end = sampleRays.end(); 
     654 
     655        // generate view cells 
     656        mGenerateViewCells = false; 
    654657 
    655658        long startTime = GetTime(); 
    … …  
    726729        PolygonContainer *polys = new PolygonContainer(); 
    727730         
     731        mGenerateViewCells = true; 
     732 
    728733        // copy mesh instance polygons into one big polygon soup 
    729734        mStat.polys = AddToPolygonSoup(objects, *polys); 
    … …  
    844849        PolygonContainer coincident; 
    845850         
    846         PolygonContainer *frontPolys = new PolygonContainer(); 
    847         PolygonContainer *backPolys = new PolygonContainer(); 
    848  
    849         BoundedRayContainer *frontRays = new BoundedRayContainer(); 
    850         BoundedRayContainer *backRays = new BoundedRayContainer(); 
    851          
    852851        BspTraversalData tFrontData(NULL, new PolygonContainer(), tData.mDepth + 1, mRootCell,  
    853852                                                                new BoundedRayContainer(), 0, 0, new BspNodeGeometry()); 
    … …  
    856855 
    857856        // create new interior node and two leaf nodes 
    858         BspInterior *interior = SubdivideNode(tData, 
    859                                                                                   tFrontData, 
    860                                                                                   tBackData, 
    861                                                                                   coincident); 
     857        BspInterior *interior =  
     858                SubdivideNode(tData, tFrontData, tBackData, coincident); 
    862859 
    863860#ifdef _DEBUG    
    … …  
    897894                                                           BspTraversalData &backData,  
    898895                                                           const PolygonContainer &coincident, 
    899                                                            const Plane3 splitPlane) const 
     896                                                           const Plane3 &splitPlane) const 
    900897{ 
    901898        // if not empty, tree is further subdivided => don't have to find view cell 
    … …  
    15341531                         
    15351532                        // add the termination object 
    1536                         AddObjToPvs(ray->intersections[0].mObject, cf, frontPvs, backPvs); 
     1533                        if (!ray->intersections.empty()) 
     1534                                AddObjToPvs(ray->intersections[0].mObject, cf, frontPvs, backPvs); 
    15371535                         
    15381536                        // add the source object 
    … …  
    15921590 
    15931591        const float raysSize = (float)rays.size() + Limits::Small; 
     1592 
    15941593        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 
    15951594                val += mLeastRaySplitsFactor * sumRaySplits / raysSize; 
    … …  
    16041603 
    16051604                // give penalty to unbalanced split 
    1606                 if (1) 
     1605                if (0) 
    16071606                if (((pFront * 0.2 + Limits::Small) > pBack) || (pFront < (pBack * 0.2 + Limits::Small))) 
    16081607                        val += 0.5; 
    … …  
    16141613                  << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl; 
    16151614#endif 
     1615         
    16161616        return val; 
    16171617} 
    … …  
    20362036} 
    20372037 
    2038 void BspTree::SetGenerateViewCells(int generateViewCells) 
    2039 { 
    2040         mGenerateViewCells = generateViewCells; 
    2041 } 
    20422038 
    20432039BspTreeStatistics &BspTree::GetStat() 

  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r436 r437  
    333333                 
    334334        */ 
    335         void AddToPvs(const BoundedRayContainer &rays, int &sampleContributions, 
    336                                   int &contributingSamples, bool storeLeavesWithRays = false); 
     335        void AddToPvs(const BoundedRayContainer &rays,  
     336                                  int &sampleContributions, 
     337                                  int &contributingSamples,  
     338                                  bool storeLeavesWithRays = false); 
    337339 
    338340protected: 
    … …  
    471473        int CastRay(Ray &ray); 
    472474 
    473         /** Set to true if new view cells shall be generated in each leaf. 
    474         */ 
    475         void SetGenerateViewCells(int generateViewCells); 
    476  
    477475        /// bsp tree construction types 
    478476        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES}; 
    … …  
    701699                                                  BspTraversalData &backData,  
    702700                                                  const PolygonContainer &coincident, 
    703                                                   const Plane3 splitPlane) const; 
     701                                                  const Plane3 &splitPlane) const; 
    704702         
    705703        /** Computes best cost ratio for the suface area heuristics for axis aligned 
    … …  
    767765        */ 
    768766        void AddObjToPvs(Intersectable *obj, const int cf, int &frontPvs, int &backPvs) const; 
    769          
     767 
     768        /** Computes PVS size induced by the rays. 
     769        */ 
    770770        int ComputePvsSize(const BoundedRayContainer &rays) const; 
    771771 
     772        /** Returns true if tree can be terminated. 
     773        */ 
    772774        inline bool TerminationCriteriaMet(const BspTraversalData &data) const; 
    773775 
     776        /** Computes accumulated ray lenght of this rays. 
     777        */ 
    774778        float AccumulatedRayLength(BoundedRayContainer &rays) const; 
    775779 
    776         /// Pointer to the root of the tree 
     780        /// Pointer to the root of the tree. 
    777781        BspNode *mRoot; 
    778                  
     782 
     783        /// Stores statistics during traversal. 
    779784        BspTreeStatistics mStat; 
    780785 
    … …  
    800805        BspViewCell *mRootCell; 
    801806 
    802         /// should view cells be stored or generated in the leaves? 
     807        /// if view cells should be generated or the given view cells should be used. 
    803808        bool mGenerateViewCells; 
    804809 

  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r436 r437  
    463463          ObjectContainer objects; 
    464464          mSceneGraph->CollectObjects(&objects); 
    465            
    466           mBspTree->SetGenerateViewCells(true); 
    467465          mBspTree->Construct(objects, bspRays); 
    468466        } 
Note: See TracChangeset for help on using the changeset viewer.