Changeset 362 for trunk/VUT


Ignore:
Timestamp:
11/01/05 02:37:51 (19 years ago)
Author:
mattausch
Message:

added post merging bsp view cells
fixed bug at per ray subdivision

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
18 edited

Legend:

Unmodified
Added
Removed
  • trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

    r361 r362  
    99#       filename vienna.x3d 
    1010#       filename ../data/vienna/vienna-simple.x3d 
    11         filename ../data/vienna/vienna-buildings.x3d 
     11#       filename ../data/vienna/vienna-buildings.x3d 
    1212#       filename ../data/vienna/viewcells-25-sel.x3d 
    13 #       filename ../data/atlanta/atlanta2.x3d 
     13        filename ../data/atlanta/atlanta2.x3d 
    1414#       filename ../data/soda/soda.dat 
    1515#       filename ../data/soda/soda5.dat 
     
    5656 
    5757Sampling { 
    58         totalSamples    20000 
    59         samplesPerPass  2 
     58        totalSamples    200000 
     59        samplesPerPass  3 
    6060} 
    6161 
     
    6868        maxViewCells 0 
    6969         
     70        minPvsDif 10 
     71         
    7072#       filename ../data/atlanta/atlanta_viewcells_large.x3d 
    7173        filename ../data/vienna/viewcells-25-sel.x3d 
     
    7678BspTree { 
    7779        Construction { 
    78         #       input fromRays 
    79                 input fromViewCells 
     80                input fromRays 
     81        #       input fromViewCells 
    8082        #       input fromSceneGeometry 
    81                 samples 15000 
     83                samples 100000 
    8284                sideTolerance 0.005 
    8385        } 
     
    116118        #splitPlaneStrategy 130 
    117119         
    118         splitPlaneStrategy 66 
     120        splitPlaneStrategy 130 
    119121         
    120122        maxCandidates 80 
     
    122124        Termination { 
    123125                # autopartition 
    124                 maxRays -1 
     126                maxRays 80 
    125127                maxPolygons 0 
    126128                maxDepth 100 
    127129                 
    128130                # axis aligned splits 
    129                 maxPolysForAxisAligned 400 
    130                 maxCostRatio 0.9 
    131                 ct_div_ci 0.5 
     131                AxisAligned { 
     132                        maxPolys 500 
     133                        maxRays 300 
     134                        maxObjects 20 
     135                        maxCostRatio 0.9 
     136                        ct_div_ci 0.5 
     137                } 
    132138        } 
    133139         
    134         #axis aligned split 
    135         splitBorder 0.01 
    136          
     140        AxisAligned { 
     141                splitBorder 0.01 
     142        } 
     143                 
    137144        # if split polys are stored for visualization 
    138145        storeSplitPolys false 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Camera.cpp

    r263 r362  
    102102    int k =0; 
    103103    for (int j=0; j < rays.size(); j++) 
    104       if (rays[j].leaves.size()) { 
     104      if (rays[j].kdLeaves.size()) { 
    105105        Ray *ray = &(rays[j]); 
    106106        int i; 
    107107        if (1) 
    108         for (i= 0; i < ray->leaves.size(); i++) 
    109           exporter->ExportBox(tree->GetBox(ray->leaves[i])); 
     108        for (i= 0; i < ray->kdLeaves.size(); i++) 
     109          exporter->ExportBox(tree->GetBox(ray->kdLeaves[i])); 
    110110        if (0) 
    111111        for (i= 0; i < ray->meshes.size(); i++) 
     
    130130 
    131131  ray.intersections.clear(); 
    132   ray.leaves.clear(); 
     132  ray.kdLeaves.clear(); 
    133133  ray.meshes.clear(); 
    134    
     134  ray.bspLeaves.clear(); 
     135 
    135136  ray.Init(mPosition, target, Ray::LOCAL_RAY); 
    136137   
  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r332 r362  
    11471147  RegisterOption("Sampling.samplesPerPass", 
    11481148                 optInt, 
    1149                  "-total_samples=", 
     1149                 "-samples_per_pass=", 
    11501150                 "10"); 
    11511151 
     
    11551155                 "bspTree"); 
    11561156 
     1157  RegisterOption("ViewCells.minPvsDif", 
     1158                 optString, 
     1159                 "-view_cells_min_pvs_dif", 
     1160                 "10"); 
     1161 
    11571162  RegisterOption("ViewCells.filename", 
    11581163                 optString, 
     
    11901195                 "-1"); 
    11911196 
    1192   RegisterOption("BspTree.Termination.maxPolysForAxisAligned", 
     1197  RegisterOption("BspTree.Termination.AxisAligned.maxCostRatio", 
     1198                 optFloat, 
     1199                 "-bsp_term_max_cost_ratio=", 
     1200                 "1.5"); 
     1201 
     1202  RegisterOption("BspTree.Termination.AxisAligned.ct_div_ci", 
     1203                 optFloat, 
     1204                 "-bsp_term_ct_div_ci=", 
     1205                 "1.0"); 
     1206 
     1207  RegisterOption("BspTree.AxisAligned.splitBorder", 
     1208                 optFloat, 
     1209                 "-bsp_split_border=", 
     1210                 "0.1"); 
     1211 
     1212  RegisterOption("BspTree.Termination.AxisAligned.maxPolys", 
    11931213                 optInt, 
    11941214                 "-bsp_term_max_polygons=", 
    11951215                 "50"); 
     1216 
     1217   RegisterOption("BspTree.Termination.AxisAligned.maxObjects", 
     1218                 optInt, 
     1219                 "-bsp_term_max_objects=", 
     1220                 "3"); 
     1221 
     1222  RegisterOption("BspTree.Termination.AxisAligned.maxRays", 
     1223                 optInt, 
     1224                 "-bsp_term_max_rays=", 
     1225                 "-1"); 
    11961226 
    11971227  RegisterOption("BspTree.Termination.maxDepth", 
     
    11991229                 "-bsp_term_max_depth=", 
    12001230                 "100"); 
    1201    
    1202   RegisterOption("BspTree.Termination.maxCostRatio", 
    1203                  optFloat, 
    1204                  "-bsp_term_max_cost_ratio=", 
    1205                  "1.5"); 
    1206  
    1207   RegisterOption("BspTree.Termination.ct_div_ci", 
    1208                  optFloat, 
    1209                  "-bsp_term_ct_div_ci=", 
    1210                  "1.0"); 
    1211  
    1212   RegisterOption("BspTree.splitBorder", 
    1213                  optFloat, 
    1214                  "-bsp_split_border=", 
    1215                  "0.1"); 
    12161231 
    12171232  RegisterOption("BspTree.storeSplitPolys", 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

    r360 r362  
    1616class Intersectable; 
    1717class BspLeaf; 
     18class Polygon3; 
    1819 
    1920class Exporter 
     
    7475  ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves) = 0; 
    7576         
     77  virtual void  
     78  ExportPolygons(const PolygonContainer &polys) = 0; 
     79 
    7680  void SetExportRayDensity(const bool d) { mExportRayDensity = d; } 
    7781   
  • trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

    r354 r362  
    572572      // compute intersection with all objects in this leaf 
    573573      KdLeaf *leaf = (KdLeaf *) node; 
    574       ray.leaves.push_back(leaf); 
     574      ray.kdLeaves.push_back(leaf); 
    575575       
    576576      ObjectContainer::const_iterator mi; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

    r349 r362  
    5555        } 
    5656         
     57        if (coplanar) (*coplanar) = false; 
    5758    float u = - Distance(a) / dv; // TODO: could be done more efficiently 
    5859     
    59         if (coplanar) (*coplanar) = false; 
    6060        if (t) (*t) = u; 
    6161         
    62         //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl; 
    63     //return a - Distance(a) * b / dv + Distance(a) * a / dv; // NOTE: gives better precision than calclulating a + u * v 
    6462    return a + u * v; 
    6563  } 
    6664   
     65  float FindT(const Vector3 &a, 
     66                          const Vector3 &b) const  
     67  {        
     68          const Vector3 v = b - a; // line from A to B 
     69          const float dv = DotProd(v, mNormal); 
     70     
     71          if (signum(dv) == 0) 
     72                  return 1; 
     73         
     74          return - Distance(a) / dv; // TODO: could be done more efficiently 
     75  } 
     76 
    6777  friend bool 
    6878  PlaneIntersection(const Plane3 &a, const Plane3 &b, const Plane3 &c, Vector3 &result); 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

    r361 r362  
    147147        for (it = mVertices.begin(); it != mVertices.end(); ++ it) 
    148148        { 
    149                 int side = plane.Side(*it, Vector3::sDistTolerance); 
     149                const int side = plane.Side(*it, Vector3::sDistTolerance); 
    150150                 
    151151                if (side > 0) 
     
    395395                if ((cf == SPLIT) || (cf == COINCIDENT) || (onFrontSide && onBackSide)) 
    396396                { 
    397                         Debug << "here" << endl; 
    398397                        return SPLIT; 
    399398                } 
     
    411410        return SPLIT; 
    412411} 
     412 
     413int Polygon3::CountIntersectables(const PolygonContainer &polys) 
     414{ 
     415        int count = 0; 
     416 
     417        PolygonContainer::const_iterator it, it_end = polys.end(); 
     418 
     419        MeshInstance::NewMail(); 
     420 
     421        for (it = polys.begin(); it != it_end; ++ it) 
     422        { 
     423                if ((*it)->mParent && !(*it)->mParent->Mailed()) 
     424                { 
     425                        ++ count; 
     426                        (*it)->mParent->Mail(); 
     427                } 
     428        } 
     429        return count; 
     430} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

    r360 r362  
    118118        void InheritRays(Polygon3 &front_piece,  
    119119                                         Polygon3 &back_piece) const; 
     120 
     121 
     122        /** Counts the number of different intersectables associated with the polygons. 
     123        */ 
     124        static int CountIntersectables(const PolygonContainer &polys); 
    120125}; 
    121126 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h

    r350 r362  
    3737        int GetSize() {return (int)mEntries.size();} 
    3838        bool Empty() {return mEntries.size() == 0;} 
     39        /** Merges pvs of a and pvs of b into this pvs. 
     40        */ 
    3941        void Merge(const Pvs<T> &a, const Pvs<T> &b); 
     42    /** Difference of pvs to pvs b. 
     43                @returns number of different entries. 
     44        */ 
     45        int Diff(const Pvs<T> &b); 
    4046 
    4147        PvsData<T> *Find(T sample); 
    4248        int AddSample(T sample); 
    4349 
    44         void GetData(const int index, 
    45                T &entry, 
    46                PvsData<T> &data); 
     50        void GetData(const int index, T &entry, PvsData<T> &data); 
    4751        std::map<T, PvsData<T>, LtSample<T> > mEntries; 
    4852}; 
    4953 
    5054template <typename T> 
     55int Pvs<T>::Diff(const Pvs<T> &b) 
     56{ 
     57        int dif = 0; 
     58 
     59        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it; 
     60 
     61        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
     62        { 
     63                PvsData<T> *data = Find((*it).first);            
     64                if (!data) ++ dif; 
     65        } 
     66 
     67        return dif; 
     68} 
     69 
     70template <typename T> 
    5171void Pvs<T>::Merge(const Pvs<T> &a, const Pvs<T> &b) 
    5272{ 
    53         //std::merge(a.mEntries.begin(), a.mEntries.end(),  
    54         //             b.mEntries.begin(), b.mEntries.end(), mEntries.begin()); 
     73        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it; 
     74 
     75        // todo: copy all elements instead of inserting 
     76        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it) 
     77        { 
     78                mEntries.insert(*it); 
     79        } 
     80 
     81        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
     82        { 
     83                PvsData<T> *data = Find((*it).first); 
     84                 
     85                if (data) 
     86                        data->mVisibleSamples += (*it).second.mVisibleSamples; 
     87                else 
     88                        mEntries.insert(*it); 
     89        } 
    5590} 
     91 
    5692 
    5793template <typename T> 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

    r349 r362  
    168168        const int extSide = plane.Side(extp); 
    169169 
    170         if ((entSide == 0) && (extSide == 0))  
     170        if (entSide < 0) 
    171171        { 
    172                 return COINCIDENT; 
    173         } 
    174         else if ((entSide <= 0) && (extSide <= 0)) 
    175         { 
     172                if (extSide >= 0) 
     173                { 
     174                        return BACK_FRONT; 
     175                } 
    176176                return BACK; 
    177177        } 
    178         else if ((entSide >= 0) && (extSide >= 0)) 
     178        else if (entSide > 0) 
    179179        { 
     180                if (extSide <= 0) 
     181                        return FRONT_BACK; 
     182 
    180183                return FRONT; 
    181184        } 
    182         else if ((entSide <= 0) && (extSide >= 0)) 
    183                 return BACK_FRONT; 
     185        else if (entSide == 0) 
     186        { 
     187                if (extSide > 0) 
     188                        return BACK_FRONT; 
     189                else if (extSide < 0) 
     190                        return FRONT_BACK; 
     191        } 
    184192         
    185         return FRONT_BACK; 
     193        return COINCIDENT; 
    186194} 
    187195 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Ray.h

    r350 r362  
    1212class MeshInstance; 
    1313class ViewCell; 
     14class BspLeaf; 
    1415 
    1516// ------------------------------------------------------------------- 
     
    6162   
    6263  vector<Intersection> intersections; 
    63   vector<KdLeaf *> leaves; 
     64  vector<KdLeaf *> kdLeaves; 
    6465  vector<MeshInstance *> meshes; 
    65   vector<ViewCell *> viewCells; 
     66  vector<BspLeaf *> bspLeaves; 
    6667   
    6768  // constructors 
  • trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

    r361 r362  
    3232{ 
    3333  ray.intersections.clear(); 
    34   ray.leaves.clear(); 
     34  ray.kdLeaves.clear(); 
    3535  ray.meshes.clear(); 
    36   ray.viewCells.clear(); 
     36  ray.bspLeaves.clear(); 
    3737 
    3838  //  cout<<point<<" "<<direction<<endl; 
     
    6868                mSceneGraph->CollectObjects(&objects); 
    6969                mBspTree->Construct(objects); 
    70                  
    71                 mBspTree->CollectViewCells(mViewCells); 
    7270                break; 
    7371        case BspTree::FROM_RAYS: 
     
    7573                mBspTree->SetGenerateViewCells(true); 
    7674                mBspTree->Construct(mSampleRays); 
    77                  
    78                 mBspTree->CollectViewCells(mViewCells); 
    7975                break; 
    8076        default: 
     
    9490  int contributingSamples = 0; 
    9591  int j; 
    96   for (j=0; j < ray.leaves.size(); j++) { 
    97     KdNode *node = GetNodeForPvs( ray.leaves[j] ); 
     92  for (j=0; j < ray.kdLeaves.size(); j++) { 
     93    KdNode *node = GetNodeForPvs( ray.kdLeaves[j] ); 
    9894    contributingSamples += object->mKdPvs.AddSample(node); 
    9995  } 
    10096    
    10197  if (mPass > 10) 
    102     for (j=1; j < ((int)ray.leaves.size() - 1); j++) { 
    103       ray.leaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0); 
     98    for (j=1; j < ((int)ray.kdLeaves.size() - 1); j++) { 
     99      ray.kdLeaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0); 
    104100  } 
    105101   
     
    114110  
    115111        // object can be seen from the view cell => add to view cell pvs 
    116         for (j=0; j < ray.viewCells.size(); ++ j)  
     112        for (j=0; j < ray.bspLeaves.size(); ++ j)  
    117113        {       // if ray not in unbounded space 
    118                 if (ray.viewCells[j] != &mUnbounded) 
    119                         contributingSamples += ray.viewCells[j]->GetPvs().AddSample(obj); 
     114                if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded) 
     115                        contributingSamples +=  
     116                                ray.bspLeaves[j]->GetViewCell()->GetPvs().AddSample(obj); 
    120117        } 
    121118  
    122119        // rays passing through this viewcell 
    123120        if (mPass > 1) 
    124                 for (j=1; j < ((int)ray.viewCells.size() - 1); ++ j)  
    125                 { 
    126                         if (ray.viewCells[j] != &mUnbounded) 
    127                                 ray.viewCells[j]->AddPassingRay(ray, contributingSamples ? 1 : 0); 
     121                for (j=1; j < ((int)ray.bspLeaves.size() - 1); ++ j)  
     122                { 
     123                        if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded) 
     124                                ray.bspLeaves[j]->GetViewCell()-> 
     125                                        AddPassingRay(ray, contributingSamples ? 1 : 0); 
    128126                } 
    129127  
     
    183181        else 
    184182                { 
    185                         if (ray.leaves.size()) { 
     183                        if (ray.kdLeaves.size()) { 
    186184                                if (!reverseRay) 
    187185                                        sampleContributions += AddNodeSamples(object, ray); 
     
    372370 
    373371  vector<Ray> rays[10]; 
    374  
    375   vector<Ray> vcRays[5]; 
    376   ViewCellContainer pvsViewCells; 
    377   vector<Ray> viewCellRays; // used for BSP tree construction 
    378372 
    379373  while (totalSamples < mTotalSamples) { 
     
    462456                                        } 
    463457                                        //------------------- 
    464  
    465458                                        if (mViewCellsType == BSP_VIEW_CELLS)  
    466459                                        { 
    467                                                 // save rays for bsp tree construction 
    468                                                 if (collectSamplesForBsp) 
    469                                                 { 
    470                                                         // also add origin to sample in order to extract it as input polygons 
    471                                                         MeshInstance *mi = dynamic_cast<MeshInstance *>(object); 
    472                                                         ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex); 
    473                                                          
    474                             mSampleRays.push_back(new Ray(ray)); 
    475                                                 } 
    476                                                 else 
    477                                                 { 
    478                                                         // construct BSP tree using the samples 
    479                                                         if (!mBspTree) 
    480                                                         { 
    481                                                                 BuildBspTree(); 
    482  
    483                                                                 cout << "generated " << (int)mViewCells.size() << " view cells" << endl; 
    484  
    485                                                                 passContributingSamples += mBspTree->GetStat().contributingSamples; 
    486                                                                 passSampleContributions += mBspTree->GetStat().sampleContributions; 
    487  
    488                                                                 BspTreeStatistics(Debug);        
    489                                                                 Export("vc_bsptree.x3d", false, false, true); 
    490                                                         } 
    491                                                                  
    492                                                         // some random view cells for output 
    493                                                         if (pvsViewCells.empty()) 
    494                                                         { 
    495                                                                 int vcPvsOut = Min((int)mViewCells.size(), 5); 
    496                                                          
    497                                                                 for (int j = 0; j < vcPvsOut; ++ j) 
    498                                                                 { 
    499                                                                         int idx = Random((int)mViewCells.size()); 
    500                                                                         Debug << "output view cell=" << idx << endl; 
    501                                                                         pvsViewCells.push_back(mViewCells[Random((int)mViewCells.size())]); 
    502                                                                 } 
    503                                                         } 
    504                                                         else 
    505                                                         {        
    506                                                                 // check whether we can add the current ray to the rays 
    507                                                                 for (int k = 0; k < (int)ray.viewCells.size(); ++ k) 
    508                                                                         for (int j = 0; j < (int)pvsViewCells.size(); ++ j)  
    509                                                                                 if (pvsViewCells[j] == ray.viewCells[k])  
    510                                                                                         vcRays[j].push_back(ray);                                                        
    511                                                         } 
    512                                                 } 
     460                                                ProcessBspViewCells(collectSamplesForBsp, 
     461                                                                                        ray, 
     462                                                                                        object, 
     463                                                                                        faceIndex, 
     464                                                                                        passContributingSamples, 
     465                                                                                        passSampleContributions); 
    513466                                        } 
    514                  
    515467                                } 
    516468                        } else { 
     
    580532                cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl; 
    581533   
     534        // merge or subdivide view cells 
     535        if (mBspTree) 
     536        { 
     537                int merged = PostprocessViewCells(mSampleRays); 
     538                Debug << "merged " << merged << " view cells" << endl; 
     539 
     540                ViewCellContainer vc; 
     541                mBspTree->CollectViewCells(vc); 
     542 
     543                ViewCellContainer::const_iterator it, it_end = vc.end(); 
     544 
     545                int mergedPvs = 0; 
     546                for (it = vc.begin(); it != it_end; ++ it) 
     547                        mergedPvs += (*it)->GetPvs().GetSize(); 
     548 
     549                Debug << "merged pvs size: " << mergedPvs << endl; 
     550 
     551        } 
     552         
    582553  //  HoleSamplingPass(); 
    583   if (0) { 
    584     Exporter *exporter = Exporter::GetExporter("ray-density.x3d"); 
    585     exporter->SetExportRayDensity(true); 
    586     exporter->ExportKdTree(*mKdTree); 
    587  
     554        if (0) { 
     555                Exporter *exporter = Exporter::GetExporter("ray-density.x3d");  
     556                exporter->SetExportRayDensity(true); 
     557                exporter->ExportKdTree(*mKdTree); 
     558 
     559                if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS)) 
     560                        exporter->ExportBspTree(*mBspTree); 
     561 
     562                delete exporter; 
     563        } 
     564   
     565        bool exportRays = false; 
     566        if (exportRays) { 
     567                Exporter *exporter = NULL; 
     568                exporter = Exporter::GetExporter("sample-rays.x3d"); 
     569                exporter->SetWireframe(); 
     570                exporter->ExportKdTree(*mKdTree); 
     571                exporter->ExportBspTree(*mBspTree); 
     572 
     573                for (i=0; i < pvsOut; i++)  
     574                exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0)); 
     575                exporter->SetFilled(); 
     576                   
     577                delete exporter; 
     578        } 
     579 
     580        //-- several visualizations and statistics 
     581        if (1) { 
    588582        if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS)) 
    589                 exporter->ExportBspTree(*mBspTree); 
    590  
    591     delete exporter; 
    592   } 
    593    
    594   bool exportRays = false; 
    595   if (exportRays) { 
    596     Exporter *exporter = NULL; 
    597     exporter = Exporter::GetExporter("sample-rays.x3d"); 
    598     exporter->SetWireframe(); 
    599     exporter->ExportKdTree(*mKdTree); 
    600         exporter->ExportBspTree(*mBspTree); 
    601  
    602     for (i=0; i < pvsOut; i++)  
    603       exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0)); 
    604     exporter->SetFilled(); 
    605            
    606     delete exporter; 
    607   } 
    608  
    609   //-- several visualizations and statistics 
    610   if (1) { 
    611   if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS)) 
    612   { 
    613           bool exportSplits = false; 
    614           environment->GetBoolValue("BspTree.exportSplits", exportSplits); 
    615  
    616           // export the bsp splits 
    617           if (exportSplits) 
    618                   ExportSplits(objects); 
    619          
    620           Exporter *exporter = Exporter::GetExporter("viewCells.x3d"); 
    621  
    622           // export leaves 
    623           if (0 && exporter) 
    624           { 
    625                   vector<BspLeaf *> leaves; 
    626                   mBspTree->CollectLeaves(leaves); 
    627                   vector<BspLeaf *> randLeaves; 
    628                   vector<BspLeaf *> neighbors; 
    629  
    630                   for (int k = 0; k < 1; ++ k)  
    631                   { 
    632                           BspLeaf *leaf = leaves[Random((int)leaves.size())]; 
    633                           randLeaves.push_back(leaf); 
    634                           mBspTree->FindNeighbors(leaf, neighbors, false); 
    635                   }      
    636  
    637                   exporter->ExportLeavesGeometry(*mBspTree, randLeaves); 
    638                   exporter->SetWireframe(); 
    639           exporter->ExportLeavesGeometry(*mBspTree, neighbors);  
    640                          
    641           delete exporter; 
    642           } 
    643  
    644            vector<BspLeaf *> leaves; 
    645            mBspTree->CollectLeaves(leaves); 
    646             
    647            for (int k = 0; k < 100; ++ k)  
    648            { 
    649                    vector<BspLeaf *> randLeaves; 
    650                    vector<BspLeaf *> neighbors; 
    651                     
    652                    char s[64]; sprintf(s, "bsp-vc%04d.x3d", k); 
    653                    Exporter *exporter = Exporter::GetExporter(s); 
    654  
    655                    BspLeaf *leaf = leaves[Random((int)leaves.size())]; 
    656                    Debug << "\noutput leaf " << k << endl; 
    657                    randLeaves.push_back(leaf); 
    658                    mBspTree->FindNeighbors(leaf, neighbors, false); 
    659  
    660                    exporter->ExportLeavesGeometry(*mBspTree, randLeaves); 
    661                    exporter->SetWireframe(); 
    662                    exporter->ExportLeavesGeometry(*mBspTree, neighbors);         
    663                          
    664                    delete exporter; 
    665            }     
    666  
    667           for (int j = 0; j < pvsViewCells.size(); ++ j) 
    668           { 
    669                   ViewCell *vc = pvsViewCells[j]; 
    670  
    671                   Intersectable::NewMail(); 
    672                   char s[64]; sprintf(s, "bsp-pvs%04d.x3d", j); 
    673  
    674                   Exporter *exporter = Exporter::GetExporter(s); 
    675                   exporter->SetFilled(); 
    676  
    677                   ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin(); 
    678  
    679                   Material m;//= RandomMaterial(); 
    680                   m.mDiffuseColor = RgbColor(0, 1, 0); 
    681                   exporter->SetForcedMaterial(m); 
    682  
    683                   exporter->ExportViewCell(vc); 
    684  
    685                   Debug << j << ": pvs size=" << (int)vc->GetPvs().GetSize()  
    686                             << ", piercing rays=" << (int)vcRays[j].size() << endl; 
    687  
    688                   exporter->SetWireframe(); 
    689  
    690                   // export view cells 
    691                   m.mDiffuseColor = RgbColor(1, 0, 1); 
    692                   exporter->SetForcedMaterial(m); 
    693                   exporter->ExportViewCells(mViewCells); 
    694                          
    695                   // export rays piercing this view cell 
    696                   exporter->ExportRays(vcRays[j], 1000, RgbColor(0, 1, 0)); 
    697  
    698                   m.mDiffuseColor = RgbColor(1, 0, 0); 
    699                   exporter->SetForcedMaterial(m); 
    700  
    701                   // output PVS of view cell 
    702                   for (; it != vc->GetPvs().mEntries.end(); ++ it)  
    703                   { 
    704                           Intersectable *intersect = (*it).first; 
    705                           if (!intersect->Mailed()) 
    706                           { 
    707                                   exporter->ExportIntersectable(intersect); 
    708                                   intersect->Mail(); 
    709                           }                      
    710                   } 
    711                  
    712                   // output rest of the objects 
    713                   if (0) 
    714                   { 
    715                           Material m;//= RandomMaterial(); 
    716                           m.mDiffuseColor = RgbColor(0, 0, 1); 
    717                           exporter->SetForcedMaterial(m); 
    718  
    719                           for (int j = 0; j < objects.size(); ++ j) 
    720                                   if (!objects[j]->Mailed()) 
    721                                   { 
    722                                           //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1); 
    723                                           //else m.mDiffuseColor = RgbColor(1, 1, 0); 
    724                                           exporter->SetForcedMaterial(m); 
    725                                           exporter->ExportIntersectable(objects[j]); 
    726                                           objects[j]->Mail(); 
    727                                   } 
    728                   } 
    729                   DEL_PTR(exporter); 
    730                 } 
    731   }   
    732  
     583        { 
     584                bool exportSplits = false; 
     585                environment->GetBoolValue("BspTree.exportSplits", exportSplits); 
     586 
     587                // export the bsp splits 
     588                if (exportSplits) 
     589                        ExportSplits(objects); 
     590                 
     591                ExportBspPvs(objects); 
     592        } 
    733593   for (int k=0; k < pvsOut; k++) { 
    734594      Intersectable *object = objects[k]; 
     
    772632} 
    773633 
     634bool SamplingPreprocessor::ProcessBspViewCells(bool collectSamplesForBsp, 
     635                                                                                           Ray &ray, 
     636                                                                                           Intersectable *object, 
     637                                                                                           int faceIndex, 
     638                                                                                           int &contributingSamples, 
     639                                                                                           int &sampleContributions) 
     640{ 
     641        // save rays for bsp tree construction 
     642        if (collectSamplesForBsp) 
     643        { 
     644                // also add origin to sample in order to extract it as input polygons 
     645                MeshInstance *mi = dynamic_cast<MeshInstance *>(object); 
     646                ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex); 
     647                                                         
     648        mSampleRays.push_back(new Ray(ray)); 
     649                 
     650                return false; 
     651        } 
     652         
     653        // construct BSP tree using the samples 
     654        if (!mBspTree) 
     655        { 
     656                BuildBspTree(); 
     657                 
     658                contributingSamples += mBspTree->GetStat().contributingSamples; 
     659                sampleContributions += mBspTree->GetStat().sampleContributions; 
     660 
     661                BspTreeStatistics(Debug);        
     662                if (0) Export("vc_bsptree.x3d", false, false, true); 
     663        } 
     664 
     665        return true; 
     666} 
     667 
     668// merge or subdivide view cells 
     669int SamplingPreprocessor::PostprocessViewCells(const RayContainer &rays) 
     670{ 
     671        int merged = 0; 
     672        RayContainer::const_iterator rit, rit_end = rays.end(); 
     673        vector<BspLeaf *>::const_iterator lit; 
     674if (0) 
     675        for (rit = rays.begin(); rit != rays.end(); ++ rit) 
     676        {   
     677                // traverse leaves stored in the rays and compare and merge consecutive 
     678                // leaves (i.e., the neighbors in the tree) 
     679                lit = (*rit)->bspLeaves.begin(); 
     680 
     681                BspLeaf *previousLeaf = *lit; 
     682                ++ lit; 
     683                 
     684                for (; lit != (*rit)->bspLeaves.end(); ++ lit) 
     685                { 
     686                        BspLeaf *leaf = *lit; 
     687                        if (mBspTree->ShouldMerge(leaf, previousLeaf)) 
     688                        {                        
     689                                mBspTree->MergeViewCells(leaf, previousLeaf); 
     690                                ++ merged; 
     691                        } 
     692                        previousLeaf = leaf; 
     693                } 
     694        } 
     695        return merged; 
     696} 
    774697 
    775698void SamplingPreprocessor::ExportSplits(const ObjectContainer &objects) 
     
    829752        } 
    830753} 
     754 
     755void SamplingPreprocessor::ExportBspPvs(const ObjectContainer &objects) 
     756{ 
     757        //-- some random view cells and rays for output 
     758        const int leafOut = 10; 
     759 
     760        vector<Ray> vcRays[leafOut]; 
     761        vector<BspLeaf *> bspLeaves; 
     762                         
     763        for (int i = 0; i < leafOut; ++ i) 
     764                bspLeaves.push_back(mBspTree->GetRandomLeaf()); 
     765         
     766        const int raysOut = min((int)mSampleRays.size(), 20000); 
     767 
     768        // check whether we can add the current ray to the output rays 
     769        for (int k = 0; k < raysOut; ++ k)  
     770        { 
     771                Ray *ray = mSampleRays[k]; 
     772 
     773                for (int j = 0; j < (int)ray->bspLeaves.size(); ++ j) 
     774                { 
     775                        for (int i = 0; i < (int)bspLeaves.size(); ++ i) 
     776                        { 
     777                                if (bspLeaves[i] == ray->bspLeaves[j])  
     778                                { 
     779                                        vcRays[i].push_back(*ray); 
     780                                } 
     781                        } 
     782                } 
     783        } 
     784 
     785        ViewCell::NewMail(); 
     786 
     787        for (int i = 0; i < bspLeaves.size(); ++ i) 
     788        { 
     789                Intersectable::NewMail(); 
     790 
     791                ViewCell *vc = bspLeaves[i]->GetViewCell(); 
     792 
     793                //bspLeaves[j]->Mail(); 
     794                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i); 
     795 
     796                Exporter *exporter = Exporter::GetExporter(s); 
     797                exporter->SetFilled(); 
     798 
     799                ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin(); 
     800 
     801                Material m;//= RandomMaterial(); 
     802                m.mDiffuseColor = RgbColor(0, 1, 0); 
     803                exporter->SetForcedMaterial(m); 
     804 
     805                exporter->SetWireframe(); 
     806 
     807                if (vc->GetMesh()) 
     808                        exporter->ExportViewCell(vc); 
     809                else 
     810                { 
     811            PolygonContainer cell; 
     812 
     813                        mBspTree->ConstructGeometry(bspLeaves[i], cell); 
     814                        exporter->ExportPolygons(cell); 
     815                        CLEAR_CONTAINER(cell); 
     816 
     817                        /*vector<BspLeaf *> neighbors; 
     818                        mBspTree->FindNeighbors(bspLeaves[j], neighbors); 
     819                        for (int j = 0; j < (int)neighbors.size(); ++ j) 
     820                        {       if (neighbors[j]->mViewCell == bspLeaves[j]->mViewCell) 
     821                                {}}*/ 
     822                } 
     823 
     824                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()  
     825                                << ", piercing rays=" << (int)vcRays[i].size() << endl; 
     826 
     827                // export view cells 
     828                if (0) 
     829                { 
     830                        m.mDiffuseColor = RgbColor(1, 0, 1); 
     831                        exporter->SetForcedMaterial(m); 
     832                        exporter->ExportViewCells(mViewCells); 
     833                } 
     834 
     835                // export rays piercing this view cell 
     836                exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0)); 
     837 
     838                m.mDiffuseColor = RgbColor(1, 0, 0); 
     839                exporter->SetForcedMaterial(m); 
     840 
     841                // output PVS of view cell 
     842                for (; it != vc->GetPvs().mEntries.end(); ++ it)  
     843                { 
     844                        Intersectable *intersect = (*it).first; 
     845                        if (!intersect->Mailed()) 
     846                        { 
     847                                exporter->ExportIntersectable(intersect); 
     848                                intersect->Mail(); 
     849                        }                        
     850                } 
     851                         
     852                // output rest of the objects 
     853                if (0) 
     854                { 
     855                        Material m;//= RandomMaterial(); 
     856                        m.mDiffuseColor = RgbColor(0, 0, 1); 
     857                        exporter->SetForcedMaterial(m); 
     858 
     859                        for (int j = 0; j < objects.size(); ++ j) 
     860                                if (!objects[j]->Mailed()) 
     861                                { 
     862                                        //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1); 
     863                                        //else m.mDiffuseColor = RgbColor(1, 1, 0); 
     864                                        exporter->SetForcedMaterial(m); 
     865                                        exporter->ExportIntersectable(objects[j]); 
     866                                        objects[j]->Mail(); 
     867                                } 
     868                } 
     869                DEL_PTR(exporter); 
     870        } 
     871} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.h

    r354 r362  
    6464                                                                        ); 
    6565 
    66         /** Adds objects samples to view cells. 
     66        /** Processes the BSP based view cells during a pass. 
     67                @param collectSamplesForBps if still in sample collection phase 
     68                @param ray the current ray 
     69                @param object the currently processed object 
     70                @param faceIndex the sampled face of the object 
     71                @param contributingSamples samples contributing to pvs 
     72                @param sampleContributions contribution of the samples 
     73 
     74                @returns true if BSP tree has been constructed, false if not yet 
     75 
     76        */ 
     77        bool ProcessBspViewCells(bool collectSamplesForBsp, 
     78                                                         Ray &ray, 
     79                                                         Intersectable *object, 
     80                                                         int faceIndex, 
     81                                                         int &contributingSamples, 
     82                                                         int &sampleContributions); 
     83 
     84        /** Adds objects samples to bsp view cells. 
    6785        */ 
    6886        int AddObjectSamples(Intersectable *obj, const Ray &ray); 
     
    7189 
    7290        void ExportSplits(const ObjectContainer &objects); 
     91 
     92        void ExportBspPvs(const ObjectContainer &objects); 
     93 
     94        /** Post processes view cells (i.e., merges or subdivides view cells based 
     95                on the PVS and the ray sets. 
     96                @returns number of merged view cells. 
     97        */ 
     98        int PostprocessViewCells(const RayContainer &rays); 
     99 
    73100}; 
    74101 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

    r359 r362  
    8181} 
    8282 
    83 ViewCell *ViewCell::MergeViewCells(const ViewCell &front, const ViewCell &back) 
     83ViewCell *ViewCell::Merge(ViewCell &front, ViewCell &back) 
    8484{ 
    85         /*stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end()); 
     85        ViewCell *vc = new ViewCell(); 
     86        // merge pvs 
     87        vc->mPvs.Merge(front.mPvs, back.mPvs); 
     88 
     89        // merge ray sets 
     90        stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end()); 
    8691        stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end()); 
    8792 
    88         ViewCell *vc = front.Merge(back); 
     93        std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(), 
     94                           back.mPiercingRays.begin(), back.mPiercingRays.end(),  
     95                           vc->mPiercingRays.begin()); 
    8996 
    90         if (vc) 
    91                 return vc; 
    92  
    93         return back.Merge(front);*/return NULL; 
     97        return vc; 
    9498} 
    95  
    96 ViewCell *ViewCell::Merge(const ViewCell &other) const 
    97 { 
    98         //-- compute set differences 
    99         const float minDif = 10; 
    100  
    101         RayContainer diff; 
    102  
    103         set_difference(mPiercingRays.begin(), mPiercingRays.end(),  
    104                                    other.mPiercingRays.begin(), other.mPiercingRays.end(), 
    105                                    diff.begin()); 
    106  
    107         if (diff.size() < minDif) 
    108         { 
    109                 ViewCell *vc = new ViewCell(); 
    110  
    111                 RayContainer::const_iterator it, it_end = other.mPiercingRays.end(); 
    112  
    113                 for (it = other.mPiercingRays.begin(); it != it_end; ++ it) 
    114                         vc->mPiercingRays.push_back(*it); 
    115  
    116                 while (!diff.empty()) 
    117                 { 
    118                         vc->mPiercingRays.push_back(diff.back()); 
    119                         diff.pop_back(); 
    120                 } 
    121  
    122                 return vc; 
    123         } 
    124  
    125         return NULL; 
    126 } 
    127  
    12899 
    129100void ViewCell::AddPassingRay(const Ray &ray, const int contributions) 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

    r352 r362  
    4848        static ViewCell *ExtrudeViewCell(const Triangle3 &baseTri, const float height); 
    4949 
    50         /** Merges two view cells based on some criteria 
    51                 @returns new view cell if merge was success. NULL if merge failed. 
     50        /** Merges two view cells. 
     51                @note the piercing rays of the front and back will be ordered    
     52                @returns new view cell based on the merging. 
    5253        */ 
    53         static ViewCell *MergeViewCells(const ViewCell &front, const ViewCell &back); 
     54        static ViewCell *Merge(ViewCell &front, ViewCell &back); 
    5455 
    5556 
     
    6162 
    6263protected: 
    63          
    64         /** Merges view cell with other view cell if certain criteria are met. 
    65                 @note because of performance issues the precondition is that the piercing rays are ordered. 
    66         */ 
    67         ViewCell *Merge(const ViewCell &other) const; 
    6864 
    6965        /// the potentially visible objects 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r361 r362  
    2020int BspTree::sConstructionMethod = FROM_INPUT_VIEW_CELLS; 
    2121int BspTree::sTermMaxPolysForAxisAligned = 50; 
     22int BspTree::sTermMaxObjectsForAxisAligned = 50; 
     23int BspTree::sTermMaxRaysForAxisAligned = -1; 
    2224int BspTree::sTermMaxRays = -1; 
     25int BspTree::sMinPvsDif = 10; 
    2326 
    2427float BspTree::sCt_div_ci = 1.0f; 
     
    3134float BspTree::sBalancedPolysFactor = 1.0f; 
    3235float BspTree::sBalancedViewCellsFactor = 1.0f; 
     36 
    3337// NOTE:  very important criterium for 2.5d scenes 
    3438float BspTree::sVerticalSplitsFactor = 1.0f; 
     
    285289} 
    286290 
    287 void BspLeaf::GenerateViewCell(const RayContainer &rays,  
     291void BspLeaf::GenerateViewCell(const BoundedRayContainer &rays,  
    288292                                                           int &sampleContributions, 
    289293                                                           int &contributingSamples, 
     
    295299        mViewCell = new ViewCell(); 
    296300 
    297     RayContainer::const_iterator it, it_end = rays.end(); 
     301    BoundedRayContainer::const_iterator it, it_end = rays.end(); 
    298302 
    299303        // add contributions from samples to the PVS 
     
    301305        { 
    302306                int contribution = 0; 
    303  
    304                 if (!(*it)->intersections.empty()) 
     307                Ray *ray = (*it)->mRay; 
     308                         
     309                if (!ray->intersections.empty()) 
    305310                {        
    306             contribution +=  mViewCell->GetPvs().AddSample((*it)->intersections[0].mObject); 
    307                 } 
    308  
    309                 contribution +=  mViewCell->GetPvs().AddSample((*it)->sourceObject.mObject); 
     311            contribution += mViewCell->GetPvs().AddSample(ray->intersections[0].mObject); 
     312                } 
     313 
     314                contribution += mViewCell->GetPvs().AddSample(ray->sourceObject.mObject); 
    310315 
    311316                if (contribution > 0) 
     
    315320                } 
    316321 
     322                ray->bspLeaves.push_back(this); 
     323 
    317324                if (storeRays) 
    318                         mViewCell->mPiercingRays.push_back(*it); 
     325                        mViewCell->mPiercingRays.push_back(ray); 
    319326        } 
    320327} 
     
    414421                mRoot = new BspLeaf(); 
    415422 
    416         tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new RayContainer())); 
     423        tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer())); 
    417424 
    418425        while (!tStack.empty()) 
     
    472479                                                                                         tData.mDepth + 1,  
    473480                                                                                         backViewCell, 
    474                                                                                          new RayContainer())); 
     481                                                                                         new BoundedRayContainer())); 
    475482                        } 
    476483 
     
    570577 
    571578        // construct tree from the view cell polygons 
    572         Construct(polys, new RayContainer()); 
     579        Construct(polys, new BoundedRayContainer()); 
    573580} 
    574581 
     
    585592 
    586593        // construct tree from polygon soup 
    587         Construct(polys, new RayContainer()); 
     594        Construct(polys, new BoundedRayContainer()); 
    588595} 
    589596 
     
    591598{ 
    592599        mStat.nodes = 1; 
    593         mBox.Initialize();      // initialise bsp tree bounding box 
     600        mBox.Initialize();      // initialise BSP tree bounding box 
    594601         
    595602        PolygonContainer *polys = new PolygonContainer(); 
    596         RayContainer *rays = new RayContainer(); 
     603        BoundedRayContainer *rays = new BoundedRayContainer(); 
    597604 
    598605        RayContainer::const_iterator rit, rit_end = sampleRays.end(); 
     
    608615        { 
    609616                Ray *ray = *rit; 
    610                 ray->SetId(-1); // reset id 
    611                 rays->push_back(ray); 
    612  
    613                 //Debug << "extracting ray with intersections" << ray->intersections.size() << endl; 
    614  
     617         
    615618                // get ray-face intersection. Store polygon representing the rays together 
    616619                // with rays intersecting the face. 
     
    629632                        { 
    630633                                Polygon3 *poly = new Polygon3(face, obj->GetMesh()); 
     634                                poly->mParent = obj; 
    631635                                polys->push_back(poly); 
    632636                                poly->mPiercingRays.push_back(ray); 
     
    638642         
    639643        Polygon3::IncludeInBox(*polys, mBox); 
     644 
     645        //-- store rays 
     646        for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 
     647        { 
     648                Ray *ray = *rit; 
     649        ray->SetId(-1); // reset id 
     650 
     651                float minT, maxT; 
     652                if (BoundRay(*ray, minT, maxT)) 
     653                        rays->push_back(new BoundedRay(ray, minT, maxT)); 
     654        } 
     655 
    640656        mStat.polys = (int)polys->size(); 
    641657 
     
    647663} 
    648664 
    649 void BspTree::Construct(PolygonContainer *polys, RayContainer *rays) 
     665void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays) 
    650666{ 
    651667        std::stack<BspTraversalData> tStack; 
     
    705721                leaf->ProcessPolygons(tData.mPolygons, sStoreSplitPolys); 
    706722                DEL_PTR(tData.mPolygons); 
     723                // discard rays 
     724                CLEAR_CONTAINER(*tData.mRays); 
    707725                DEL_PTR(tData.mRays); 
    708726 
     
    717735        PolygonContainer *backPolys = new PolygonContainer(); 
    718736 
    719         RayContainer *frontRays = new RayContainer(); 
    720         RayContainer *backRays = new RayContainer(); 
     737        BoundedRayContainer *frontRays = new BoundedRayContainer(); 
     738        BoundedRayContainer *backRays = new BoundedRayContainer(); 
    721739         
    722740        // create new interior node and two leaf nodes 
     
    810828                                                                        PolygonContainer &backPolys, 
    811829                                                                        PolygonContainer &coincident, 
    812                                                                         RayContainer &rays, 
    813                                                                         RayContainer &frontRays, 
    814                                                                         RayContainer &backRays) 
     830                                                                        BoundedRayContainer &rays, 
     831                                                                        BoundedRayContainer &frontRays, 
     832                                                                        BoundedRayContainer &backRays) 
    815833{ 
    816834        mStat.nodes += 2; 
     
    827845        SplitRays(interior->mPlane, rays, frontRays, backRays); 
    828846         
    829         // split polygons with split plane 
    830         mStat.splits +=interior->SplitPolygons(polys,  
    831                                                                                frontPolys,  
    832                                                                        backPolys,  
    833                                                                        coincident,  
    834                                                                        sStoreSplitPolys); 
     847        // subdivide polygons with plane 
     848        mStat.splits +=  
     849                interior->SplitPolygons(polys, frontPolys, backPolys,  
     850                                                                coincident, sStoreSplitPolys); 
    835851 
    836852        BspInterior *parent = leaf->GetParent(); 
     
    9951011Plane3 BspTree::SelectPlane(BspLeaf *leaf,  
    9961012                                                        PolygonContainer &polys,  
    997                                                         const RayContainer &rays) 
     1013                                                        const BoundedRayContainer &rays) 
    9981014{ 
    9991015        if (polys.empty()) 
     
    10141030                return Plane3(norm, position); 
    10151031        } 
    1016  
     1032         
    10171033        if ((sSplitPlaneStrategy & AXIS_ALIGNED) && 
    1018                 ((int)polys.size() > sTermMaxPolysForAxisAligned)) 
     1034                ((int)polys.size() > sTermMaxPolysForAxisAligned) && 
     1035                ((int)rays.size() > sTermMaxRaysForAxisAligned) && 
     1036                ((sTermMaxObjectsForAxisAligned < 0) ||  
     1037                  (Polygon3::CountIntersectables(polys) > sTermMaxObjectsForAxisAligned))) 
    10191038        { 
    10201039                Plane3 plane; 
     
    10341053 
    10351054Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer &polys, 
    1036                                                                           const RayContainer &rays, 
     1055                                                                          const BoundedRayContainer &rays, 
    10371056                                                                          const int maxTests) 
    10381057{ 
     
    10931112        int totalViewCells = 0; 
    10941113 
    1095         // needed for balanced view cells criterium 
     1114        // need three unique ids for each type of view cell 
     1115        // for balanced view cells criterium 
    10961116        ViewCell::NewMail(); 
    10971117        const int backId = ViewCell::sMailId; 
     
    12061226                minT = 0; 
    12071227 
    1208         //Debug << "ray intersections " << ray.intersections.size() << endl; 
    12091228        // bound ray or line segment 
    12101229        if ((ray.GetType() == Ray::LOCAL_RAY) &&  
     
    12191238 
    12201239float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,  
    1221                                                           const RayContainer &rays) const 
     1240                                                          const BoundedRayContainer &rays) const 
    12221241{ 
    12231242        float val = 0; 
     
    12261245        float sumRaySplits = 0; 
    12271246 
    1228         RayContainer::const_iterator rit, rit_end = rays.end(); 
     1247        BoundedRayContainer::const_iterator rit, rit_end = rays.end(); 
    12291248 
    12301249        for (rit = rays.begin(); rit != rays.end(); ++ rit) 
    12311250        { 
    1232                 Ray *ray = *rit; 
    1233  
    1234                 float minT, maxT; 
    1235                 if (!BoundRay(*ray, minT, maxT)) 
    1236                         continue; 
     1251                Ray *ray = (*rit)->mRay; 
     1252                const float minT = (*rit)->mMinT; 
     1253                const float maxT = (*rit)->mMaxT; 
    12371254 
    12381255                const int classification =  
     
    12631280float BspTree::SplitPlaneCost(const Plane3 &candidatePlane,  
    12641281                                                          const PolygonContainer &polys,                                                           
    1265                                                           const RayContainer &rays) const 
     1282                                                          const BoundedRayContainer &rays) const 
    12661283{ 
    12671284        float val = 0; 
     
    13261343 
    13271344        //-- termination criteria for axis aligned split 
    1328         environment->GetFloatValue("BspTree.Termination.ct_div_ci", sCt_div_ci); 
    1329         environment->GetFloatValue("BspTree.Termination.maxCostRatio", sMaxCostRatio); 
    1330         environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned",  
     1345        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", sCt_div_ci); 
     1346        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", sMaxCostRatio); 
     1347        environment->GetIntValue("BspTree.Termination.AxisAligned.maxPolys",  
    13311348                                                         sTermMaxPolysForAxisAligned); 
    1332          
     1349        environment->GetIntValue("BspTree.Termination.AxisAligned.maxRays",  
     1350                                                         sTermMaxRaysForAxisAligned); 
     1351        environment->GetIntValue("BspTree.Termination.AxisAligned.maxObjects",  
     1352                                                         sTermMaxObjectsForAxisAligned); 
    13331353        //-- partition criteria 
    13341354        environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates); 
    13351355        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy); 
    1336         environment->GetFloatValue("BspTree.splitBorder", sSplitBorder); 
     1356        environment->GetFloatValue("BspTree.AxisAligned.splitBorder", sSplitBorder); 
    13371357         
    13381358        environment->GetBoolValue("BspTree.storeSplitPolys", sStoreSplitPolys); 
     
    13401360        environment->GetFloatValue("BspTree.Construction.sideTolerance", Vector3::sDistTolerance); 
    13411361        Vector3::sDistToleranceSqrt = Vector3::sDistTolerance * Vector3::sDistTolerance; 
     1362 
     1363        environment->GetIntValue("ViewCells.minPvsDif", sMinPvsDif); 
    13421364 
    13431365    Debug << "BSP max depth: " << sTermMaxDepth << endl; 
     
    14401462        float maxt, mint; 
    14411463 
     1464        if (!BoundRay(ray, mint, maxt)) 
     1465                return 0; 
     1466 
    14421467        Intersectable::NewMail(); 
    14431468 
    1444         BoundRay(ray, mint, maxt); 
    1445          
    14461469        Vector3 entp = ray.Extrap(mint); 
    14471470        Vector3 extp = ray.Extrap(maxt); 
     
    14581481                        Plane3 *splitPlane = in->GetPlane(); 
    14591482 
    1460                         float t = 0; 
    1461                         bool coplanar = false; 
    1462                  
    14631483                        int entSide = splitPlane->Side(entp); 
    14641484                        int extSide = splitPlane->Side(extp); 
     
    14941514 
    14951515                        // find intersection of ray segment with plane 
    1496                         extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt); 
     1516                        float t; 
     1517                        extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &t); 
     1518                        maxt *= t; 
    14971519                         
    14981520                } else // reached leaf => intersection with view cell 
     
    15021524                        if (!leaf->mViewCell->Mailed()) 
    15031525                        { 
    1504                                 ray.viewCells.push_back(leaf->mViewCell); 
     1526                                ray.bspLeaves.push_back(leaf); 
    15051527                                leaf->mViewCell->Mail(); 
    15061528                                ++ hits; 
     
    15141536                        mint = maxt; // NOTE: need this? 
    15151537 
    1516                          if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
     1538                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
    15171539                                break; 
    15181540 
     
    15221544                        extp = s.mExitPoint; 
    15231545                        maxt = s.mMaxT; 
    1524  
    1525                         //Debug << "leaf: new entrypt: " << entp << " new extp: " << extp << endl; 
    15261546 
    15271547                        tStack.pop(); 
     
    15771597} 
    15781598 
    1579 int BspTree::MergeViewCells() 
    1580 { 
    1581         stack<BspNode *> nodeStack; 
    1582         nodeStack.push(mRoot); 
    1583  
    1584         BspLeaf *storedLeaf = NULL; 
    1585  
    1586         while (!nodeStack.empty())  
    1587         { 
    1588                 BspNode *node = nodeStack.top(); 
    1589                 nodeStack.pop(); 
    1590  
    1591                 if (node->IsLeaf())  
    1592                 { 
    1593                         BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 
    1594  
    1595                         if (storedLeaf) 
    1596                                 MergeLeafs(leaf, storedLeaf); 
    1597  
    1598                         // store current leaf 
    1599                         storedLeaf = leaf; 
    1600                 } 
    1601                 else  
    1602                 { 
    1603                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    1604  
    1605                         nodeStack.push(interior->mFront); 
    1606                         nodeStack.push(interior->mBack); 
    1607                 } 
    1608         } 
    1609         return 0; 
    1610 } 
    1611  
    1612 void BspTree::MergeLeafs(BspLeaf *front, BspLeaf *back) const 
    1613 { 
    1614         //std::merge(front->mPvs.mEntries.begin(), back->mPvs.mEntries.begin()); 
    1615         ViewCell *viewCell = ViewCell::MergeViewCells(*front->mViewCell, *back->mViewCell); 
    1616         //viewCell->GetPvs().Merge(front->mViewCell->GetPvs(), back->mViewCell->GetPvs()); 
    1617  
    1618         if (viewCell) 
    1619         { 
    1620                 DEL_PTR(front->mViewCell); 
    1621                 DEL_PTR(back->mViewCell); 
    1622  
    1623                 front->SetViewCell(viewCell); 
    1624                 back->SetViewCell(viewCell); 
    1625         } 
     1599 
     1600bool BspTree::MergeViewCells(BspLeaf *front, BspLeaf *back) const 
     1601{ 
     1602        ViewCell *viewCell = ViewCell::Merge(*front->mViewCell, *back->mViewCell); 
     1603         
     1604        if (!viewCell) 
     1605                return false; 
     1606 
     1607        DEL_PTR(front->mViewCell); 
     1608        DEL_PTR(back->mViewCell); 
     1609 
     1610        front->SetViewCell(viewCell); 
     1611        back->SetViewCell(viewCell); 
     1612 
     1613        return true; 
     1614} 
     1615 
     1616bool BspTree::ShouldMerge(BspLeaf *front, BspLeaf *back) const 
     1617{ 
     1618        if (front->mViewCell->GetPvs().Diff(back->mViewCell->GetPvs()) <  
     1619                sMinPvsDif) 
     1620                return true; 
     1621         
     1622        if (back->mViewCell->GetPvs().Diff(front->mViewCell->GetPvs()) <  
     1623                sMinPvsDif) 
     1624                return true; 
     1625 
     1626        return false; 
    16261627} 
    16271628 
     
    16371638 
    16381639int BspTree::SplitRays(const Plane3 &plane, 
    1639                                            RayContainer &rays,  
    1640                                            RayContainer &frontRays,  
    1641                                            RayContainer &backRays) 
     1640                                           BoundedRayContainer &rays,  
     1641                                           BoundedRayContainer &frontRays,  
     1642                                           BoundedRayContainer &backRays) 
    16421643{ 
    16431644        int splits = 0; 
     
    16451646        while (!rays.empty()) 
    16461647        { 
    1647                 Ray *ray = rays.back(); 
     1648                BoundedRay *bRay = rays.back(); 
     1649                Ray *ray = bRay->mRay; 
    16481650                rays.pop_back(); 
    1649  
    1650                 //-- ray-plane intersection 
    1651                 float maxT, minT; 
    1652          
    1653                 if (!BoundRay(*ray, minT, maxT)) 
    1654                         continue; 
    1655                                  
    1656                 const int classification = ray->ClassifyPlane(plane, minT, maxT); 
    16571651                 
    1658                 ray->SetId(classification); 
    1659  
    1660                 switch (classification) 
     1652                const int cf =  
     1653                        ray->ClassifyPlane(plane, bRay->mMinT, bRay->mMaxT); 
     1654                 
     1655                ray->SetId(cf); 
     1656 
     1657                switch (cf) 
    16611658                { 
    16621659                case Ray::COINCIDENT: 
     1660                        frontRays.push_back(bRay); 
    16631661                        break; 
    16641662                case Ray::BACK: 
    1665                         backRays.push_back(ray); 
     1663                        backRays.push_back(bRay); 
    16661664                        break; 
    16671665                case Ray::FRONT: 
    1668                         frontRays.push_back(ray); 
     1666                        frontRays.push_back(bRay); 
    16691667                        break; 
    16701668                case Ray::FRONT_BACK: 
    1671                         ray->SetId(Ray::FRONT_BACK); 
    1672                         backRays.push_back(ray); 
    1673                         ++ splits;                       
     1669                        { 
     1670                                // find intersection of ray segment with plane 
     1671                                const Vector3 extp = ray->Extrap(bRay->mMaxT); 
     1672                                const float t = plane.FindT(ray->GetLoc(), extp); 
     1673                                 
     1674                                const float newT = t * bRay->mMaxT; 
     1675 
     1676                                frontRays.push_back(new BoundedRay(ray, bRay->mMinT, newT)); 
     1677                                backRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT)); 
     1678 
     1679                                DEL_PTR(bRay); 
     1680 
     1681                                ++ splits; 
     1682                        } 
    16741683                        break; 
    16751684                case Ray::BACK_FRONT: 
    1676                         frontRays.push_back(ray); 
    1677                         ++ splits; 
     1685                        { 
     1686                                // find intersection of ray segment with plane 
     1687                                const Vector3 extp = ray->Extrap(bRay->mMaxT); 
     1688                                const float t = plane.FindT(ray->GetLoc(), extp); 
     1689                                const float newT = t * bRay->mMaxT; 
     1690 
     1691                                backRays.push_back(new BoundedRay(ray, bRay->mMinT, newT)); 
     1692                                frontRays.push_back(new BoundedRay(ray, newT, bRay->mMaxT)); 
     1693                                 
     1694                                DEL_PTR(bRay); 
     1695 
     1696                                ++ splits; 
     1697                        } 
    16781698                        break; 
    16791699                default: 
     
    16861706} 
    16871707 
    1688 void BspTree::ExtractSplitPlanes(BspNode *n, vector<Plane3 *> &planes, vector<bool> &sides) const 
     1708void BspTree::ExtractSplitPlanes(BspNode *n,  
     1709                                                                 vector<Plane3 *> &planes,  
     1710                                                                 vector<bool> &sides) const 
    16891711{ 
    16901712        BspNode *lastNode; 
     
    16921714        { 
    16931715                lastNode = n; 
     1716 
     1717                // want to get planes defining geometry of this node => don't take 
     1718                // split plane of node itself 
    16941719                n = n->GetParent(); 
    16951720                 
     
    17051730} 
    17061731 
     1732struct Candidate 
     1733{ 
     1734        Polygon3 *mPoly; 
     1735        Plane3 mPlane; 
     1736        bool mSide; 
     1737 
     1738        Candidate(Polygon3 *poly, const Plane3 &plane, const bool &side): 
     1739        mPoly(poly), mPlane(plane), mSide(side) 
     1740        {} 
     1741}; 
     1742 
     1743void BspTree::AddHalfspace(PolygonContainer &cell,  
     1744                                                   vector<Plane3> &planes, 
     1745                                                   vector<bool> &sides, 
     1746                                                   const Plane3 &halfspace,  
     1747                                                   const bool side) const 
     1748{ 
     1749        Polygon3 *poly = GetBoundingBox().CrossSection(halfspace); 
     1750 
     1751        bool inside = true; 
     1752 
     1753        // polygon is split by all other planes 
     1754        for (int i = 0; (i < planes.size()) && inside; ++ i) 
     1755        { 
     1756                VertexContainer splitPts; 
     1757                Polygon3 *frontPoly, *backPoly; 
     1758 
     1759                const int cf = poly->ClassifyPlane(planes[i]); 
     1760                         
     1761                // split new polygon with all previous planes 
     1762                switch (cf) 
     1763                { 
     1764                        case Polygon3::SPLIT: 
     1765                                frontPoly = new Polygon3(); 
     1766                                backPoly = new Polygon3(); 
     1767 
     1768                                poly->Split(planes[i], *frontPoly, *backPoly, splitPts); 
     1769                                DEL_PTR(poly); 
     1770 
     1771                                if(sides[i] == true) 
     1772                                { 
     1773                                        poly = frontPoly; 
     1774                                        DEL_PTR(backPoly); 
     1775                                } 
     1776                                        else 
     1777                                        { 
     1778                                                poly = backPoly; 
     1779                                                DEL_PTR(frontPoly); 
     1780                                        } 
     1781                                        inside = true; 
     1782                                        break; 
     1783                        case Polygon3::BACK_SIDE: 
     1784                                if (sides[i])  
     1785                                        inside = false; 
     1786                                break; 
     1787                        case Polygon3::FRONT_SIDE: 
     1788                                if (!sides[i]) 
     1789                                        inside = false; 
     1790                                break; 
     1791                        default: 
     1792                                break; 
     1793                } 
     1794        } 
     1795 
     1796        //-- plane poly splits all other candidates 
     1797 
     1798    // some polygons may fall out => rebuild cell 
     1799        vector<Candidate> candidates; 
     1800 
     1801        for (int i = 0; i < (int)cell.size(); ++ i) 
     1802        { 
     1803                candidates.push_back(Candidate(cell[i], planes[i], sides[i])); 
     1804        } 
     1805 
     1806        cell.clear(); 
     1807        planes.clear(); 
     1808        sides.clear(); 
     1809 
     1810        for (int i = 0; i < (int)candidates.size(); ++ i) 
     1811        { 
     1812                bool candidateInside = true; 
     1813 
     1814                VertexContainer splitPts; 
     1815                Polygon3 *frontPoly, *backPoly; 
     1816 
     1817                const int cf = poly->ClassifyPlane(halfspace); 
     1818                         
     1819                // split new polygon with all previous planes 
     1820                switch (cf) 
     1821                { 
     1822                        case Polygon3::SPLIT: 
     1823                                frontPoly = new Polygon3(); 
     1824                                backPoly = new Polygon3(); 
     1825 
     1826                                poly->Split(halfspace, *frontPoly, *backPoly, splitPts); 
     1827                                DEL_PTR(candidates[i].mPoly); 
     1828 
     1829                                if (sides[i] == true) 
     1830                                { 
     1831                                        candidates[i].mPoly = frontPoly; 
     1832                                        DEL_PTR(backPoly); 
     1833                                } 
     1834                                else 
     1835                                { 
     1836                                        candidates[i].mPoly = backPoly; 
     1837                                        DEL_PTR(frontPoly); 
     1838                                } 
     1839                                inside = true; 
     1840                                break; 
     1841                        case Polygon3::BACK_SIDE: 
     1842                                if (candidates[i].mSide)  
     1843                                        candidateInside = false; 
     1844                                break; 
     1845                        case Polygon3::FRONT_SIDE: 
     1846                                if (!candidates[i].mSide) 
     1847                                        candidateInside = false; 
     1848                                break; 
     1849                        default: 
     1850                                break; 
     1851                } 
     1852                 
     1853                if (candidateInside) 
     1854                { 
     1855                        cell.push_back(candidates[i].mPoly); 
     1856                        sides.push_back(candidates[i].mSide); 
     1857                        planes.push_back(candidates[i].mPlane); 
     1858                } 
     1859                else 
     1860                { 
     1861                        DEL_PTR(candidates[i].mPoly); 
     1862                } 
     1863        } 
     1864 
     1865        //-- finally add polygon 
     1866        if (inside) 
     1867        { 
     1868                cell.push_back(poly); 
     1869                planes.push_back(halfspace); 
     1870                sides.push_back(side); 
     1871        } 
     1872        else 
     1873        { 
     1874                DEL_PTR(poly); 
     1875        } 
     1876} 
     1877 
     1878 
    17071879void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const 
    17081880{ 
     
    17161888        PolygonContainer candidatePolys; 
    17171889 
    1718         // bounded plane is added to the polygons 
     1890        // bounded planes are added to the polygons 
    17191891        for (int i = 0; i < (int)planes.size(); ++ i) 
    17201892        { 
     
    17221894        } 
    17231895 
     1896        // add faces of bounding box (also could be faces of the cell) 
    17241897        for (int i = 0; i < 6; ++ i) 
    17251898        { 
     
    17361909                bool inside = true; 
    17371910 
    1738                 // polygon is split with all other planes 
     1911                // polygon is split by all other planes 
    17391912                for (int j = 0; (j < planes.size()) && inside; ++ j) 
    17401913                { 
     
    17471920                        Polygon3 *frontPoly, *backPoly; 
    17481921 
    1749                         int cf = candidatePolys[i]->ClassifyPlane(*plane); 
     1922                        const int cf = candidatePolys[i]->ClassifyPlane(*plane); 
    17501923                         
    1751                         // split new polygon with all previous planes 
    1752                         switch(cf) 
     1924                        switch (cf) 
    17531925                        { 
    17541926                                case Polygon3::SPLIT: 
     
    17561928                                        backPoly = new Polygon3(); 
    17571929 
    1758                                         candidatePolys[i]->Split(*plane, *frontPoly, *backPoly, splitPts); 
     1930                                        candidatePolys[i]->Split(*plane, *frontPoly,  
     1931                                                                                         *backPoly, splitPts); 
    17591932                                        DEL_PTR(candidatePolys[i]); 
    17601933 
     
    18352008                                if (isAdjacent) 
    18362009                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node)); 
     2010 
     2011                                CLEAR_CONTAINER(neighborCandidate); 
    18372012                        } 
    18382013                } 
     
    18572032        } 
    18582033         
     2034        CLEAR_CONTAINER(cell); 
    18592035        return (int)neighbors.size(); 
    18602036} 
     2037 
     2038BspLeaf *BspTree::GetRandomLeaf(const Plane3 &halfspace) 
     2039{ 
     2040    stack<BspNode *> nodeStack; 
     2041        nodeStack.push(mRoot); 
     2042         
     2043        int mask = rand(); 
     2044   
     2045        while (!nodeStack.empty())  
     2046        { 
     2047                BspNode *node = nodeStack.top(); 
     2048                nodeStack.pop(); 
     2049           
     2050                if (node->IsLeaf())  
     2051                { 
     2052                        return dynamic_cast<BspLeaf *>(node); 
     2053                }  
     2054                else  
     2055                { 
     2056                        BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     2057                         
     2058                        BspNode *next; 
     2059         
     2060                        PolygonContainer cell; 
     2061 
     2062                        // todo: not very efficient: constructs full cell everytime 
     2063                        ConstructGeometry(interior, cell); 
     2064 
     2065                        const int cf = Polygon3::ClassifyPlane(cell, halfspace); 
     2066 
     2067                        if (cf == Polygon3::BACK_SIDE) 
     2068                                next = interior->mFront; 
     2069                        else 
     2070                                if (cf == Polygon3::FRONT_SIDE) 
     2071                                        next = interior->mFront; 
     2072                        else  
     2073                        { 
     2074                                // random decision 
     2075                                if (mask & 1) 
     2076                                        next = interior->mBack; 
     2077                                else 
     2078                                        next = interior->mFront; 
     2079                                mask = mask >> 1; 
     2080                        } 
     2081 
     2082                        nodeStack.push(next); 
     2083                } 
     2084        } 
     2085         
     2086        return NULL; 
     2087} 
     2088 
     2089BspLeaf *BspTree::GetRandomLeaf(const bool onlyUnmailed) 
     2090{ 
     2091        stack<BspNode *> nodeStack; 
     2092         
     2093        nodeStack.push(mRoot); 
     2094 
     2095        int mask = rand(); 
     2096         
     2097        while (!nodeStack.empty())  
     2098        { 
     2099                BspNode *node = nodeStack.top(); 
     2100                nodeStack.pop(); 
     2101                 
     2102                if (node->IsLeaf())  
     2103                { 
     2104                        if ( (!onlyUnmailed || !node->Mailed()) ) 
     2105                                return dynamic_cast<BspLeaf *>(node); 
     2106                } 
     2107                else  
     2108                { 
     2109                        BspInterior *interior = dynamic_cast<BspInterior *>(node); 
     2110 
     2111                        // random decision 
     2112                        if (mask & 1) 
     2113                                nodeStack.push(interior->mBack); 
     2114                        else 
     2115                                nodeStack.push(interior->mFront); 
     2116 
     2117                        mask = mask >> 1; 
     2118                } 
     2119        } 
     2120         
     2121        return NULL; 
     2122} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r361 r362  
    1414class Ray; 
    1515 
     16/** Data structure used for optimized ray casting. 
     17*/ 
    1618struct BspRayTraversalData  
    1719{ 
     
    2628        {} 
    2729}; 
     30 
     31/** Data used for passing ray data down the tree. 
     32*/ 
     33struct BoundedRay 
     34{ 
     35        Ray *mRay; 
     36        float mMinT; 
     37        float mMaxT; 
     38                 
     39        BoundedRay(): mMinT(0), mMaxT(1e6), mRay(NULL) 
     40        {} 
     41        BoundedRay(Ray *r, float minT, float maxT): 
     42        mRay(r), mMinT(minT), mMaxT(maxT) 
     43        {} 
     44}; 
     45 
     46typedef vector<BoundedRay *> BoundedRayContainer; 
    2847 
    2948class BspTreeStatistics 
     
    230249                @param storeRays if ray set should be stored in view cell 
    231250        */ 
    232         void BspLeaf::GenerateViewCell(const RayContainer &rays,  
    233                                                            int &sampleContributions, 
    234                                                            int &contributingSamples, 
    235                                                            const bool storeRays = false); 
     251        void GenerateViewCell(const BoundedRayContainer &rays,  
     252                                              int &sampleContributions, 
     253                                                  int &contributingSamples, 
     254                                                  const bool storeRays = false); 
    236255 
    237256protected: 
     
    246265{ 
    247266public: 
    248                  
     267         
    249268        /** Additional data which is passed down the BSP tree during traversal. 
    250269        */ 
     
    260279                ViewCell *mViewCell; 
    261280                /// rays piercing this node 
    262                 RayContainer *mRays; 
     281                BoundedRayContainer *mRays; 
    263282 
    264283                BspTraversalData(): 
     
    274293                                                 const int depth,  
    275294                                                 ViewCell *viewCell, 
    276                                                  RayContainer *rays):  
     295                                                 BoundedRayContainer *rays):  
    277296                mNode(node),  
    278297                mPolygons(polys),  
     
    344363        int CastRay(Ray &ray); 
    345364 
     365        /** Set to true if new view cells shall be generated in each leaf. 
     366        */ 
     367        void SetGenerateViewCells(int generateViewCells); 
     368 
     369        /// bsp tree construction types 
     370        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS}; 
     371 
     372        /** Returns statistics. 
     373        */ 
     374        BspTreeStatistics &GetStat(); 
     375 
     376        /** finds neighbouring leaves of this tree node. 
     377        */ 
     378        int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,  
     379                                          const bool onlyUnmailed) const; 
     380 
     381        /** Extracts geometry associated with the split plane leading to this node. 
     382        */ 
     383        void ConstructGeometry(BspNode *n, PolygonContainer &polys) const; 
     384         
     385        /** Returns random leaf of BSP tree. 
     386                @param halfspace defines the halfspace from which the leaf is taken. 
     387        */ 
     388        BspLeaf *GetRandomLeaf(const Plane3 &halfspace); 
     389 
     390        /** Returns random leaf of BSP tree. 
     391                @param onlyUnmailed if only unmailed leaves should be returned. 
     392        */ 
     393        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false); 
     394 
     395        /** Adds halfspace to cell definition. 
     396                @param side indicates which side of halfspace is added 
     397        */ 
     398        void AddHalfspace(PolygonContainer &cell,  
     399                                          vector<Plane3> &planes, 
     400                                          vector<bool> &sides, 
     401                                          const Plane3 &halfspace,  
     402                                          const bool side) const; 
     403 
     404        /** Returns true if merge criteria are reached. 
     405        */ 
     406    bool ShouldMerge(BspLeaf *front, BspLeaf *back) const; 
     407 
    346408        /** Merges view cells based on some criteria 
    347409            E.g., empty view cells can pe purged, view cells which have  
    348                 a very similar PVS can be merged to one larger view cell farther up  
    349                 in the BSP tree. 
    350                 @returns the number of merged view cells 
    351         */ 
    352         int MergeViewCells(); 
    353  
    354         /** Set to true if new view cells shall be generated in each leaf. 
    355         */ 
    356         void SetGenerateViewCells(int generateViewCells); 
    357  
    358         /// bsp tree construction types 
    359         enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_RAYS}; 
    360  
    361         /** Returns statistics. 
    362         */ 
    363         BspTreeStatistics &GetStat(); 
    364  
    365         /** finds neighbouring leaves of this tree node. 
    366         */ 
    367         int FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,  
    368                                           const bool onlyUnmailed) const; 
    369  
    370         /** Extracts geometry associated with the split plane leading to this node. 
    371         */ 
    372         void ConstructGeometry(BspNode *n, PolygonContainer &polys) const; 
     410                a very similar PVS can be merged to one larger view cell. 
     411 
     412                @returns true if merge was successful. 
     413        */ 
     414        bool MergeViewCells(BspLeaf *front, BspLeaf *back) const; 
    373415 
    374416protected: 
     
    394436        }; 
    395437 
    396         /** Merges view cells of leafs. 
    397         */ 
    398         void MergeLeafs(BspLeaf *front, BspLeaf *back) const; 
    399  
    400438        /** Evaluates tree stats in the BSP tree leafs. 
    401439        */ 
     
    413451                @param rays storesset of rays on which subdivision may be based 
    414452        */ 
    415         void Construct(PolygonContainer *polys, RayContainer *rays); 
     453        void Construct(PolygonContainer *polys, BoundedRayContainer *rays); 
    416454 
    417455        /** Selects the best possible splitting plane.  
     
    424462        Plane3 SelectPlane(BspLeaf *leaf,  
    425463                                           PolygonContainer &polys, 
    426                                            const RayContainer &ray); 
     464                                           const BoundedRayContainer &ray); 
    427465 
    428466        /** Evaluates the contribution of the candidate split plane. 
     
    435473        float SplitPlaneCost(const Plane3 &candidatePlane, 
    436474                                                 const PolygonContainer &polys,                                                   
    437                                                  const RayContainer &rays) const; 
     475                                                 const BoundedRayContainer &rays) const; 
    438476 
    439477        /** Strategies where the effect of the split plane is tested 
     
    449487        */ 
    450488        float SplitPlaneCost(const Plane3 &candidatePlane, 
    451                                                  const RayContainer &polys) const; 
     489                                                 const BoundedRayContainer &polys) const; 
    452490 
    453491        /** Filters next view cell down the tree and inserts it into the appropriate leaves 
     
    478516                                                           PolygonContainer &backPolys, 
    479517                                                           PolygonContainer &coincident, 
    480                                                            RayContainer &rays, 
    481                                                            RayContainer &frontRays, 
    482                                                             RayContainer &backRays); 
     518                                                           BoundedRayContainer &rays, 
     519                                                           BoundedRayContainer &frontRays, 
     520                                                           BoundedRayContainer &backRays); 
    483521 
    484522        /** Filters polygons down the tree. 
     
    501539        */ 
    502540        Plane3 SelectPlaneHeuristics(PolygonContainer &polys,  
    503                                                                  const RayContainer &rays, 
     541                                                                 const BoundedRayContainer &rays, 
    504542                                                                 const int maxTests); 
    505543 
     
    597635        */ 
    598636        int SplitRays(const Plane3 &plane, 
    599                                   RayContainer &rays,  
    600                               RayContainer &frontRays,  
    601                                   RayContainer &backRays); 
     637                                  BoundedRayContainer &rays,  
     638                              BoundedRayContainer &frontRays,  
     639                                  BoundedRayContainer &backRays); 
    602640 
    603641 
     
    656694        /// BSP tree construction method 
    657695        static int sConstructionMethod; 
    658         /// maximal number of polygons where we do axis aligned splits 
     696        /// maximal number of polygons for axis aligned split 
    659697        static int sTermMaxPolysForAxisAligned; 
     698        /// maximal number of rays for axis aligned split 
     699        static int sTermMaxRaysForAxisAligned; 
     700        /// maximal number of objects for axis aligned split 
     701        static int sTermMaxObjectsForAxisAligned; 
    660702 
    661703        /// axis aligned split criteria 
     
    677719        static bool sStoreSplitPolys; 
    678720 
     721        /// threshold where view cells are merged 
     722        static int sMinPvsDif; 
     723 
    679724private: 
    680725        /** Evaluates split plane classification with respect to the plane's  
  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

    r360 r362  
    5050  ExportPolygon(Polygon3 *poly); 
    5151 
    52   virtual void ExportPolygons(const PolygonContainer &polys); 
     52  virtual void  
     53  ExportPolygons(const PolygonContainer &polys); 
    5354 
    5455  virtual bool 
Note: See TracChangeset for help on using the changeset viewer.