Ignore:
Timestamp:
12/30/05 12:08:15 (19 years ago)
Author:
mattausch
Message:

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
19 edited

Legend:

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

    r484 r485  
    160160                maxPvs 150 
    161161                # how much samples are used for post processing 
    162                 samples 10 
     162                samples 100000 
    163163        } 
    164164 
     
    170170                #colorCode MergedTreeDiff 
    171171                colorCode Random 
     172                exportRays false 
     173                exportGeometry true 
    172174        } 
    173175         
    174176#       filename ../data/atlanta/atlanta_viewcells_large.x3d 
    175         filename ../data/vienna/viewcells-25-sel.x3d 
     177#       filename ../data/vienna/viewcells-25-sel.x3d 
    176178#       filename ../data/vienna/viewcells-25.x3d 
    177179#       filename ../data/vienna/viewcells-large-sel.x3d 
     
    196198        Termination { 
    197199                maxDepth                40 
    198                 minPvs                  1 
     200                minPvs                  50 
    199201                minRays                 300 
    200202                minSize                 0.1 
    201203                maxCostRatio            0.9 
    202                 missTolerance           6 
    203                 maxRayContribution      0.3 
    204         } 
    205          
    206         maxTotalMemory  400 
    207         maxStaticMemory 200 
     204                missTolerance           4 
     205                maxRayContribution      0.5 
     206        } 
     207         
     208        maxTotalMemory  100 
     209        maxStaticMemory 50 
    208210 
    209211        splitType       regular 
    210212        #splitType      heuristics 
     213        splitUseOnlyDrivingAxis true 
    211214        ct_div_ci       0.0 
    212215         
     
    214217        PostProcess { 
    215218                maxCostRatio 0.005 
    216                 minViewCells 50 
     219                minViewCells 200 
    217220                maxPvsSize   50000 
    218221        } 
     
    220223         
    221224        Visualization { 
    222                 exportRays true 
    223                 exportGeometry true 
    224225        } 
    225226} 
     
    272273        } 
    273274         
     275        splitUseOnlyDrivingAxis false 
     276         
    274277        Visualization { 
    275278                # x3d visualization of the split planes 
    276279                exportSplits true 
    277                 exportRays true 
    278                 exportGeometry true 
    279280        } 
    280281         
    281282        PostProcess { 
    282                 maxCostRatio 0.005 
    283                 minViewCells 100 
     283                maxCostRatio 0.1 
     284                minViewCells 200 
    284285                maxPvsSize   500 
     286                useRaysForMerge false 
    285287        } 
    286288} 
     
    378380                # x3d visualization of the split planes 
    379381                exportSplits true 
    380                 exportRays true 
    381                 exportGeometry false 
    382         } 
    383 } 
     382        } 
     383} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r482 r485  
    12311231                 "-view_cells_height=", 
    12321232                 "5.0"); 
     1233 
    12331234   RegisterOption("ViewCells.Visualization.colorCode", 
    12341235                optString, 
     
    12361237                "PVS"); 
    12371238 
     1239   RegisterOption("ViewCells.Visualization.exportRays", 
     1240          optBool, 
     1241          "-bsp_visualization.export_rays", 
     1242          "false"); 
     1243    
     1244   RegisterOption("ViewCells.Visualization.exportGeometry", 
     1245          optBool, 
     1246          "-bsp_visualization.export_geometry", 
     1247          "false"); 
     1248 
    12381249  /************************************************************************************/ 
    12391250  /*                         Render simulation related options                        */ 
     
    13741385          "false"); 
    13751386 
    1376    RegisterOption("BspTree.Visualization.exportRays", 
    1377           optBool, 
    1378           "-bsp_visualization.export_rays", 
    1379           "false"); 
    1380     
    1381    RegisterOption("BspTree.Visualization.exportGeometry", 
    1382           optBool, 
    1383           "-bsp_visualization.export_geometry", 
    1384           "false"); 
    13851387 
    13861388   RegisterOption("BspTree.Factor.verticalSplits", optFloat, "-bsp_factor_vertical=", "1.0"); 
     
    14561458           "queries"); 
    14571459 
     1460  RegisterOption("VspKdTree.splitAxis",  
     1461           optString,  
     1462           "split=",  
     1463           "drivingAxis"); 
     1464 
     1465  RegisterOption("VspKdTree.splitUseOnlyDrivingAxis",  
     1466          optBool,  
     1467          "vsp_kd_splitdriving=",  
     1468          "false"); 
     1469 
    14581470        RegisterOption("VspKdTree.numberOfEndPointDomains",  
    14591471                optInt,  
     
    15051517                "vsp_kd_term_post_process_max_pvs_size=",  
    15061518                "100"); 
    1507          
    1508         RegisterOption("VspKdTree.Visualization.exportRays", 
    1509                 optBool, 
    1510                 "-vsp_kd_visualization.export_rays", 
    1511                 "false"); 
    1512     
    1513         RegisterOption("VspKdTree.Visualization.exportGeometry", 
    1514                 optBool, 
    1515                 "-vsp_kd_visualization.export_geometry", 
    1516                 "false"); 
    15171519 
    15181520        RegisterOption("VspKdTree.Termination.missTolerance", 
     
    17191721                "-vsp_bsp_visualization.export_splits", 
    17201722                "false"); 
    1721  
    1722         RegisterOption("VspBspTree.Visualization.exportRays", 
    1723                 optBool, 
    1724                 "-vsp_bsp_visualization.export_rays", 
     1723         
     1724        RegisterOption("VspBspTree.splitUseOnlyDrivingAxis",  
     1725                optBool,  
     1726                "vsp_bsp_splitdriving=",  
    17251727                "false"); 
    1726     
    1727         RegisterOption("VspBspTree.Visualization.exportGeometry", 
    1728                 optBool, 
    1729                 "-vsp_bsp_visualization.export_geometry", 
    1730                 "false"); 
    1731  
    1732          
     1728 
     1729 
    17331730        RegisterOption("VspBspTree.Factor.leastRaySplits", optFloat, "-vsp_bsp_factor_least_ray_splits=", "1.0"); 
    17341731        RegisterOption("VspBspTree.Factor.balancedRays", optFloat, "-vsp_bsp_factor_balanced_rays=", "1.0"); 
     
    17491746                "vsp_bsp_term_post_process_max_pvs_size=",  
    17501747                "100"); 
     1748         
     1749        RegisterOption("VspBspTree.PostProcess.useRaysForMerge",  
     1750                optBool,  
     1751                "vsp_bsp_term_post_process_use_rays_for_merge=",  
     1752                "false"); 
    17511753         
    17521754        ////////////////////////////////////////////////////////////////////////////////// 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp

    r469 r485  
    271271Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) 
    272272{ 
    273   int faceIndex = RandomValue(0, mFaces.size()-1); 
     273  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1)); 
    274274   
    275275  // assume the face is convex and generate a convex combination 
     
    298298{ 
    299299  Plane3 plane; 
    300   int faceIndex = RandomValue(0, mFaces.size()-1); 
     300  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1)); 
    301301        int tries; 
    302302  for (tries = 0; tries < maxTries; tries++) { 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

    r448 r485  
    7676      @returns -1 if coplanar, else parameter t 
    7777  */ 
    78   float FindT(const Vector3 &a, 
    79                           const Vector3 &b) const  
     78  float FindT(const Vector3 &a, const Vector3 &b) const  
    8079  {        
    8180          const Vector3 v = b - a; // line from A to B 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h

    r469 r485  
    7272  int AddSample(T sample); 
    7373 
     74  /** Adds one pvs to another one. 
     75          @returns new pvs size 
     76  */ 
     77  int AddPvs(const Pvs<T> &pvs); 
     78  /** Subtracts one pvs from another one. 
     79          @returns new pvs size 
     80  */ 
     81  int SubtractPvs(const Pvs<T> &pvs); 
    7482  /** Returns PVS data, i.e., how often it was seen from the view cell,  
    7583          and the object itsef. 
     
    8088  */ 
    8189  void CollectEntries(std::vector<T> &entries); 
     90 
     91  /** Removes sample from PVS if reference count is zero. 
     92          @param visibleSampels number of references to be removed 
     93  */ 
     94  bool RemoveSample(T sample, const int visibleSamples); 
    8295 
    8396  /// Map of PVS entries 
     
    108121        // todo: copy all elements instead of inserting 
    109122        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it) 
    110         { 
    111123                mEntries.insert(*it); 
    112         } 
    113  
     124         
    114125        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
    115126        { 
     
    135146template <typename T> 
    136147void Pvs<T>::GetData(const int index, 
    137               T &entry, 
    138               PvsData<T> &data) 
     148                                        T &entry, 
     149                                        PvsData<T> &data) 
    139150{ 
    140151  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin(); 
     
    170181 
    171182template <typename T> 
     183bool Pvs<T>::RemoveSample(T sample, const int visibleSamples) 
     184{ 
     185        std::map<T, PvsData<T>, LtSample<T> >:: 
     186                iterator it = mEntries.find(sample); 
     187 
     188        if (it == mEntries.end()) 
     189                return false; 
     190 
     191        PvsData<T> *data = &(*it).second; 
     192   
     193        data->mVisibleSamples -= visibleSamples; 
     194        if (data->mVisibleSamples <= 0) 
     195                mEntries.erase(it); 
     196 
     197        return true; 
     198} 
     199 
     200template <typename T> 
     201int Pvs<T>::AddPvs(const Pvs<T> &pvs) 
     202{ 
     203        std::map<T, PvsData<T>, LtSample<T> >:: 
     204                const_iterator it, it_end = pvs.mEntries.end(); 
     205 
     206        float contri; 
     207        // output PVS of view cell 
     208        for (it = pvs.mEntries.begin(); it != it_end; ++ it)  
     209                AddSample((*it).first, contri); 
     210 
     211        return GetSize(); 
     212} 
     213  
     214template <typename T> 
     215int Pvs<T>::SubtractPvs(const Pvs<T> &pvs) 
     216{ 
     217        std::map<T, PvsData<T>, LtSample<T> >:: 
     218                const_iterator it, it_end = pvs.mEntries.end(); 
     219 
     220        // output PVS of view cell 
     221        for (it = pvs.mEntries.begin(); it != it_end; ++ it)  
     222                RemoveSample((*it).first, (*it).second.mVisibleSamples); 
     223 
     224        return GetSize(); 
     225} 
     226 
     227template <typename T> 
    172228void Pvs<T>::CollectEntries(std::vector<T> &entries) 
    173229{ 
    174         PvsMap<T>::const_iterator it, it_end = mEntries.end(); 
     230        std::map<T, PvsData<T>, LtSample<T> >:: 
     231                const_iterator it, it_end = mEntries.end(); 
    175232 
    176233        // output PVS of view cell 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

    r475 r485  
    5050Ray::CorrectZeroComponents() 
    5151{ 
    52   const float eps = 1e-6; 
     52  const float eps = 1e-6f; 
    5353 
    5454  // it does change the ray direction very slightly, 
     
    9999  } 
    100100  else 
    101     invDir.x = 1.0 / dir.x; 
     101    invDir.x = 1.0f / dir.x; 
    102102   
    103103  if (fabs(dir.y) < eps) { 
     
    108108  } 
    109109  else 
    110     invDir.y = 1.0 / dir.y; 
     110    invDir.y = 1.0f / dir.y; 
    111111   
    112112  if (fabs(dir.z) < eps) { 
    113     if (dir.z < 0.0) 
     113    if (dir.z < 0.0f) 
    114114      invDir.z = -invEps; 
    115115    else 
     
    117117  } 
    118118  else 
    119     invDir.z = 1.0 / dir.z; 
     119    invDir.z = 1.0f / dir.z; 
    120120 
    121121  return; 
     
    165165  float x, y; 
    166166  dir.ExtractVerts(&x, &y, axis); 
    167   int ix = (x + 1.0f)*0.5f*Resolution; 
    168   int iy = (y + 1.0f)*0.5f*Resolution; 
     167  int ix = (int)((x + 1.0f)*0.5f*Resolution); 
     168  int iy = (int)((y + 1.0f)*0.5f*Resolution); 
    169169 
    170170  return Resolution*(Resolution*axis + iy) + ix; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/RayInfo.cpp

    r448 r485  
    133133{        
    134134        t = splitPlane.FindT(mRay->GetOrigin(), mRay->GetTermination()); 
     135//      Debug << "t: " << t << " mint " << GetMinT() << " maxt " << GetMaxT() <<  
     136//      " orig: " << mRay->GetOrigin() << " term " << mRay->GetTermination() << endl; 
    135137 
    136 //      Debug << "t: " << t << " mint " << GetMinT() << " maxt " << GetMaxT() << " orig: " << mRay->GetOrigin() << 
    137 //              " term " << mRay->GetTermination() << endl; 
    138         if ((t < GetMinT()) || (t > GetMaxT())) 
     138        // NOTE: if plane equals end point of ray, the ray should be classified 
     139        // non-intersecting, otherwise polygon-plane intersections of bsp tree 
     140        // approaches are not eliminating any rays intersecting the polygon! 
     141 
     142        //if (t > GetMaxT()) 
     143        if (t >= GetMaxT() - 1e-20) 
    139144                return splitPlane.Side(ExtrapOrigin()); 
     145        //if (t < GetMinT()) 
     146        if (t <= GetMinT() + 1e-20) 
     147                return splitPlane.Side(ExtrapTermination()); 
    140148 
    141149        return 0; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/RssTree.cpp

    r466 r485  
    824824  float sizeBox = maxBox - minBox; 
    825825         
    826   float minBand = minBox + 0.1*(maxBox - minBox); 
    827   float maxBand = minBox + 0.9*(maxBox - minBox); 
    828          
    829   float minRatio = 1e20; 
     826  float minBand = minBox + 0.1f*(maxBox - minBox); 
     827  float maxBand = minBox + 0.9f*(maxBox - minBox); 
     828         
     829  float minRatio = 1e20f; 
    830830         
    831831  Intersectable::NewMail(); 
     
    11231123   
    11241124  // update stats 
    1125   stat.rayRefs -= leaf->rays.size(); 
     1125  stat.rayRefs -= (int)leaf->rays.size(); 
    11261126  stat.rayRefs += raysBack + raysFront; 
    11271127 
     
    12961296         
    12971297                if (removeAllScheduledRays) { 
    1298                   int tail = leaf->rays.size()-1; 
     1298                  int tail = (int)leaf->rays.size()-1; 
    12991299 
    13001300                  for (int i=0; i < (int)(leaf->rays.size()); i++) { 
     
    20692069        } 
    20702070  } 
    2071   return rays.size(); 
     2071  return (int)rays.size(); 
    20722072} 
    20732073 
     
    21032103  } 
    21042104   
    2105   return rays.size(); 
    2106 } 
     2105  return (int)rays.size(); 
     2106} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

    r479 r485  
    105105        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl; 
    106106 
    107         app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl; 
     107        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl; 
    108108 
    109109        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r483 r485  
    144144 
    145145 
    146 BspLeaf::BspLeaf(): mViewCell(NULL) 
    147 { 
     146BspLeaf::BspLeaf(): mViewCell(NULL), mPvs(NULL) 
     147{ 
     148} 
     149 
     150 
     151BspLeaf::~BspLeaf() 
     152{ 
     153        DEL_PTR(mPvs); 
    148154} 
    149155 
     
    156162 
    157163BspLeaf::BspLeaf(BspInterior *parent):  
    158 BspNode(parent), mViewCell(NULL) 
     164BspNode(parent), mViewCell(NULL), mPvs(NULL) 
    159165{} 
    160166 
     
    162168 
    163169BspLeaf::BspLeaf(BspInterior *parent, BspViewCell *viewCell):  
    164 BspNode(parent), mViewCell(viewCell) 
     170BspNode(parent), mViewCell(viewCell), mPvs(NULL) 
    165171{ 
    166172} 
     
    406412{ 
    407413        DEL_PTR(mRoot); 
    408         DEL_PTR(mRootCell); 
     414 
     415        // root cell not used 
     416        if (mGenerateViewCells) 
     417                DEL_PTR(mRootCell); 
    409418} 
    410419 
     
    795804                // generate new view cell for each leaf 
    796805                if (mGenerateViewCells) 
    797                 { 
    798806                        viewCell = new BspViewCell(); 
    799                 } 
    800807                else 
    801                 { 
    802808                        // add view cell to leaf 
    803809                        viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell); 
    804                 } 
    805  
     810                 
    806811                leaf->SetViewCell(viewCell); 
    807812                viewCell->mLeaves.push_back(leaf); 
     
    13121317        } 
    13131318         
    1314         //-- choose candidate planes extracted from rays 
    1315         //-- different methods are available 
     1319        // choose candidate planes extracted from rays 
    13161320        for (int i = 0; i < mMaxRayCandidates; ++ i) 
    13171321        { 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r482 r485  
    6363    BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt): 
    6464    mNode(n), mExitPoint(extp), mMaxT(maxt)  
     65        {} 
     66 
     67        BspRayTraversalData(BspNode *n, const Vector3 &extp): 
     68        mNode(n), mExitPoint(extp) 
    6569        {} 
    6670}; 
     
    122126        int sampleContributions; 
    123127        /// largest pvs 
    124         int largestPvs; 
     128        int maxPvs; 
    125129 
    126130        // Constructor 
     
    156160                contributingSamples = 0; 
    157161                sampleContributions = 0; 
     162 
     163                maxPvs = 0; 
    158164        } 
    159165 
     
    274280        BspLeaf(BspInterior *parent, BspViewCell *viewCell); 
    275281 
     282        ~BspLeaf(); 
     283 
    276284        /** @return true since it is an interior node  
    277285        */ 
     
    287295 
    288296        VssRayContainer mVssRays; 
     297         
     298        /// leaf pvs 
     299        ObjectPvs *mPvs; 
     300        /// leaf area 
     301        float mArea; 
    289302 
    290303protected: 
    291  
     304         
    292305        /// if NULL this does not correspond to feasible viewcell 
    293306        BspViewCell *mViewCell; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

    r484 r485  
    4040        environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs); 
    4141 
     42        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays); 
     43        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry); 
     44 
    4245        char buf[50]; 
    4346         
     
    5659} 
    5760 
     61 
    5862ViewCellsManager::~ViewCellsManager() 
    5963{ 
     
    6266        CLEAR_CONTAINER(mViewCells); 
    6367} 
     68 
    6469 
    6570bool ViewCellsManager::LoadViewCells(const string filename) 
     
    7479        return success; 
    7580} 
     81 
    7682 
    7783void ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays) 
     
    8288   
    8389        VssRayContainer::const_iterator it, it_end = rays.end(); 
    84          
     90        int i = 0;       
    8591        for (it = rays.begin(); it != it_end; ++ it)  
    86         { 
     92        {       if ((i ++) % 50000 == 0) 
     93                        cout << "Computed 50000 samples" << endl; 
    8794                ComputeSampleContributions(*(*it)); 
    8895        } 
    8996} 
     97 
    9098 
    9199void ViewCellsManager::EvaluateViewCellsStats() 
     
    99107} 
    100108 
     109 
    101110void ViewCellsManager::AddViewCell(ViewCell *viewCell) 
    102111{ 
     
    104113} 
    105114 
     115 
    106116float ViewCellsManager::GetArea(ViewCell *viewCell) const 
    107117{ 
     
    114124        return viewCell->GetVolume(); 
    115125} 
     126 
    116127 
    117128void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects,  
     
    138149        } 
    139150} 
     151 
    140152 
    141153ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,  
     
    174186} 
    175187 
     188 
    176189ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const 
    177190{ 
     
    193206} 
    194207 
     208 
    195209void ViewCellsManager::SetRenderer(Renderer *renderer) 
    196210{ 
     
    198212} 
    199213 
     214 
    200215ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    201216{ 
     
    209224} 
    210225 
     226 
    211227void ViewCellsManager::SetConstructionSamples(const int constructionSamples) 
    212228{ 
     
    214230} 
    215231 
     232 
    216233void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples) 
    217234{ 
     
    219236} 
    220237 
     238 
    221239int ViewCellsManager::GetVisualizationSamples() const 
    222240{ 
     
    224242} 
    225243 
     244 
    226245int ViewCellsManager::GetConstructionSamples() const 
    227246{ 
     
    229248} 
    230249 
     250 
    231251int ViewCellsManager::GetPostProcessSamples() const 
    232252{ 
     
    234254} 
    235255 
    236 void 
    237 ViewCellsManager::GetPvsStatistics(PvsStatistics &stat) 
     256 
     257void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat) 
    238258{ 
    239259  ViewCellContainer::const_iterator it = mViewCells.begin(); 
     
    257277} 
    258278 
     279 
    259280void ViewCellsManager::PrintPvsStatistics(ostream &s) 
    260281{ 
     
    267288} 
    268289 
     290 
    269291ViewCellContainer &ViewCellsManager::GetViewCells() 
    270292{ 
    271293        return mViewCells; 
    272294} 
     295 
    273296 
    274297void ViewCellsManager::ResetViewCells() 
     
    282305} 
    283306 
     307 
    284308void ViewCellsManager::ComputeSampleContributions(VssRay &ray) 
    285309{ 
    286310        ViewCellContainer viewcells; 
    287          
     311                 
     312        ray.mPvsContribution = 0; 
     313        ray.mRelativePvsContribution = 0.0f; 
     314 
     315        // matt TODO: remove this!! 
    288316        Ray hray(ray); 
    289317        float tmin = 0, tmax = 1.0; 
    290         // matt TODO: remove this!! 
     318        Debug << "here2" << endl; 
    291319        //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT); 
    292  
    293320        if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) 
    294321                return; 
     
    300327                                        termination, 
    301328                                        viewcells); 
    302          
    303         ray.mPvsContribution = 0; 
    304         ray.mRelativePvsContribution = 0.0f; 
    305329   
    306330        ViewCellContainer::const_iterator it = viewcells.begin(); 
     
    320344                 
    321345                ray.mRelativePvsContribution += contribution; 
    322         } 
     346        }Debug << "here5" << endl; 
    323347} 
    324348 
    325349 
    326350void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays, 
    327                                                                   VssRayContainer &constructionRays,  
    328                                                                   VssRayContainer &savedRays) const 
    329 { 
    330         const int limit = min(mConstructionSamples, (int)sourceRays.size()); 
     351                                                                  const int maxSize, 
     352                                                                  VssRayContainer &usedRays,  
     353                                                                  VssRayContainer *savedRays) const 
     354{ 
     355        const int limit = min(maxSize, (int)sourceRays.size()); 
     356        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small); 
    331357 
    332358        VssRayContainer::const_iterator it, it_end = sourceRays.end(); 
    333          
    334         const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small); 
    335  
    336359        for (it = sourceRays.begin(); it != it_end; ++ it) 
    337360        { 
    338361                if (Random(1.0f) < prop) 
    339                         constructionRays.push_back(*it); 
    340                 else 
    341                         savedRays.push_back(*it); 
     362                        usedRays.push_back(*it); 
     363                else if (savedRays) 
     364                        savedRays->push_back(*it); 
    342365        } 
    343366} 
     
    378401        { 
    379402                ExportColor(exporter, *it); 
    380                 ExportGeometry(exporter, *it); 
     403                ExportVcGeometry(exporter, *it); 
    381404        } 
    382405} 
     
    512535 
    513536        EvaluateViewCellsStats(); 
    514         Debug << "original view cell partition:\n" << mViewCellsStats << endl; 
     537        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl; 
    515538 
    516539        mRenderer->RenderScene(); 
     
    531554                        ExportViewCells(exporter); 
    532555                                 
    533                         if (0) 
     556                        if (mExportGeometry) 
    534557                        { 
    535558                                Material m; 
     
    552575 
    553576        // $$JB we do not have connectivity information from the ray in the moment 
    554         // perhaps we could recast the rays or rember the cells traversed inside the 
     577        // perhaps we could recast the rays or remember the cells traversed inside the 
    555578        // vssray (which would on other hand create some overhead) 
    556579        //-- merge or subdivide view cells 
     
    558581 
    559582        vector<BspIntersection>::const_iterator iit; 
    560  
    561         if (mBspRays.empty()) 
    562                 ConstructBspRays(rays, mPostProcessSamples); 
     583        CLEAR_CONTAINER(mBspRays); 
     584        ConstructBspRays(rays, mPostProcessSamples); 
    563585         
    564586        for (int i = 0; i < (int)mBspRays.size(); ++ i) 
     
    597619 
    598620        Debug << "Postprocessing: Merged " << merged << " view cells in " 
    599                   << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
    600          
     621                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs"  
     622                  << "using " << (int)mBspRays.size() << " samples" << endl << endl; 
     623         
     624        CLEAR_CONTAINER(mBspRays); 
     625 
    601626        // reset view cells and stats 
    602627        ResetViewCells(); 
     
    623648        if (!ViewCellsConstructed()) 
    624649                return; 
    625  
    626         if (mBspRays.empty()) 
    627                 ConstructBspRays(sampleRays, mVisualizationSamples); 
     650        CLEAR_CONTAINER(mBspRays); 
     651        ConstructBspRays(sampleRays, mVisualizationSamples); 
    628652         
    629653        if (1) // export view cells 
     
    697721                } 
    698722 
    699                 if (0) 
     723                if (mExportGeometry) 
    700724                        exporter->ExportGeometry(objects); 
    701725 
     
    707731void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects) 
    708732{ 
    709         bool exportRays = false; 
    710         bool exportGeometry = false; 
    711  
    712         environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 
    713         environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 
    714  
    715733        const int leafOut = 10; 
    716734         
     
    777795                } 
    778796                         
    779                          
    780797                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()  
    781                           << ", piercing rays=" << (int)vcRays.size() << endl; 
     798                          << ", piercing rays=" << (int)vcRays.size() 
     799                          << ", leaves=" << (int)vc->mLeaves.size() << endl; 
    782800 
    783801                         
     
    951969} 
    952970 
    953 void BspViewCellsManager::ExportGeometry(Exporter *exporter,  
     971void BspViewCellsManager::ExportVcGeometry(Exporter *exporter,  
    954972                                                                                 ViewCell *vc) const 
    955973{ 
     
    959977        { 
    960978                PolygonContainer cell; 
    961                 mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(vc), cell); 
    962  
     979                mBspTree->ConstructGeometry( 
     980                        dynamic_cast<BspViewCell *>(vc), cell); 
    963981                exporter->ExportPolygons(cell); 
    964982        } 
     
    12211239 
    12221240 
    1223 void KdViewCellsManager::ExportGeometry(Exporter *exporter,  
    1224                                                                                 ViewCell *vc) const 
    1225 { 
    1226         // TODO 
     1241void KdViewCellsManager::ExportVcGeometry(Exporter *exporter,  
     1242                                                                                  ViewCell *vc) const 
     1243{ 
     1244        KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc); 
     1245        vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end(); 
     1246 
     1247        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it) 
     1248                exporter->ExportBox(mKdTree->GetBox(*it)); 
    12271249} 
    12281250 
     
    12971319        VssRayContainer savedRays; 
    12981320 
    1299         GetRaySets(rays, constructionRays, savedRays); 
     1321        GetRaySets(rays,  
     1322                           mConstructionSamples,  
     1323                           constructionRays,  
     1324                           &savedRays); 
    13001325         
    13011326        Debug << "constructing vsp kd tree using "  
     
    13081333        ExportLeaves(objects, rays); 
    13091334 
    1310         mVspKdTree->CollectMergeCandidates(); 
    13111335        // finally merge kd leaf building blocks to view cells 
    1312         const int merged = mVspKdTree->MergeLeaves(); 
     1336        const int merged = mVspKdTree->MergeViewCells(rays); 
     1337 
     1338        // collapse siblings belonging to the same view cell 
     1339        mVspKdTree->CollapseTree(mVspKdTree->GetRoot()); 
     1340         
     1341        // collapse siblings belonging to the same view cell 
     1342        mVspKdTree->RefineViewCells(); 
     1343 
    13131344        // evaluale view cell stats 
    13141345        ResetViewCells(); 
     
    13161347        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
    13171348 
     1349        long startTime = GetTime(); 
    13181350        // recast rest of rays 
    13191351        ComputeSampleContributions(savedRays); 
     1352         
     1353        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3  
     1354                  << " secs" << endl; 
    13201355 
    13211356        return merged; 
     
    13551390                                                                                 const VssRayContainer &sampleRays) 
    13561391{ 
    1357         bool exportRays = false; 
    1358         bool exportGeometry = false; 
    1359  
    1360         environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays); 
    1361         environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry); 
    1362  
    13631392        if (!ViewCellsConstructed()) 
    13641393                return; 
     
    13731402        exporter->ExportVspKdTree(*mVspKdTree); 
    13741403 
    1375         if (exportGeometry)  
     1404        if (mExportGeometry)  
    13761405                exporter->ExportGeometry(objects); 
    13771406 
    1378         if (exportRays)  
     1407        if (mExportRays)  
    13791408        { 
    13801409                const float prob = (float)mVisualizationSamples  
     
    14001429                                                                          const VssRayContainer &sampleRays) 
    14011430{ 
    1402         bool exportRays = false; 
    1403         bool exportGeometry = false; 
    1404  
    1405         environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays); 
    1406         environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry); 
    1407  
    14081431        if (!ViewCellsConstructed()) 
    14091432                return; 
     
    14291452                exporter->SetWireframe(); 
    14301453 
    1431                 ExportGeometry(exporter, vc); 
     1454                ExportVcGeometry(exporter, vc); 
    14321455 
    14331456                //-- export stored rays 
    1434                 if (exportRays) 
     1457                if (mExportRays) 
    14351458                { 
    14361459                        vector<VspKdLeaf *>::const_iterator it,  
     
    14541477                                for (it = vssRays.begin(); it != it_end; ++ it) 
    14551478                                { 
    1456                                         if (RandomValue(0, 1) < prop) 
     1479                                        if (Random(1) < prop) 
    14571480                                                if ((*it)->mTerminationObject == NULL) 
    14581481                                                        castRays.push_back(*it); 
     
    14971520        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");  
    14981521         
    1499         /*if (exportGeometry) exporter->SetWireframe(); 
    1500         else exporter->SetFilled();*/ 
     1522        //if (exportGeometry) exporter->SetWireframe(); 
     1523        //else exporter->SetFilled(); 
    15011524 
    15021525        ExportViewCells(exporter); 
    15031526 
    1504         if (exportGeometry)  
     1527        if (mExportGeometry)  
    15051528        { 
    15061529                exporter->SetFilled(); 
     
    15081531        } 
    15091532 
    1510         if (exportRays)  
     1533        if (mExportRays)  
    15111534        { 
    15121535                const float prob = (float)mVisualizationSamples  
     
    15661589                } 
    15671590                break; 
    1568         case 3: // merge tree differene 
     1591        case 3: // merged tree depth difference 
    15691592                { 
    15701593                        //importance = (float)GetMaxTreeDiff(vc) /  
     
    15851608 
    15861609 
    1587 void VspKdViewCellsManager::ExportGeometry(Exporter *exporter,  
     1610void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter,  
    15881611                                                                                   ViewCell *vc) const 
    15891612{ 
    15901613        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc); 
    1591  
    15921614        vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end(); 
    15931615 
    15941616        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it) 
    1595         { 
    15961617                exporter->ExportBox(mVspKdTree->GetBBox(*it)); 
    1597         } 
    15981618} 
    15991619 
     
    16151635VspBspViewCellsManager::~VspBspViewCellsManager() 
    16161636{ 
    1617         CLEAR_CONTAINER(mBspRays); 
    16181637} 
    16191638 
     
    16721691        VssRayContainer savedRays; 
    16731692 
    1674         GetRaySets(rays, constructionRays, savedRays); 
    1675          
     1693        GetRaySets(rays, mConstructionSamples, constructionRays, &savedRays); 
     1694         
     1695        Debug << "construction rays: " << (int)savedRays.size() << endl; 
     1696        Debug << "saved rays: " << (int)constructionRays.size() << endl; 
     1697 
    16761698        mVspBspTree->Construct(constructionRays, sceneBbox); 
    16771699        Debug << mVspBspTree->GetStatistics() << endl; 
     
    16801702 
    16811703        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl; 
     1704         
     1705        long startTime = GetTime(); 
    16821706        // recast rest of rays 
    16831707        ComputeSampleContributions(savedRays); 
    1684  
     1708         
     1709        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3  
     1710                  << " secs" << endl; 
     1711 
     1712        cout << "construction finished" << endl; 
    16851713        return sampleContributions; 
    16861714} 
    16871715 
    1688  
    1689 void VspBspViewCellsManager::ConstructBspRays(const VssRayContainer &rays, 
    1690                                                                                           const int numSamples) 
    1691 { 
    1692         VssRayContainer::const_iterator it, it_end = rays.end(); 
    1693  
    1694         for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it) 
    1695         { 
    1696                 VssRay *vssRay = *it; 
    1697                  
    1698                 Ray hray(*vssRay); 
    1699                 float tmin = 0, tmax = 1.0; 
    1700          
    1701                 //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT); 
    1702  
    1703                 if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) 
     1716// matt TODO: remove 
     1717int VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays) const 
     1718{ 
     1719        vector<BspIntersection>::const_iterator iit; 
     1720        vector<BspRay *>bspRays; 
     1721        int merged = 0; 
     1722 
     1723        mVspBspTree->ConstructBspRays(bspRays, rays); 
     1724 
     1725        for (int i = 0; i < (int)bspRays.size(); ++ i) 
     1726        { 
     1727                BspRay *ray = bspRays[i]; 
     1728           
     1729                // traverse leaves stored in the rays and compare and merge consecutive 
     1730                // leaves (i.e., the neighbors in the tree) 
     1731                if (ray->intersections.size() < 2) 
    17041732                        continue; 
    1705  
    1706                 Vector3 origin = hray.Extrap(tmin); 
    1707                 Vector3 termination = hray.Extrap(tmax); 
    1708          
    1709                 BspRay *ray = new BspRay(vssRay); 
    1710  
    1711                 ViewCellContainer viewCells; 
    1712  
    1713                 // cast line segment and store intersections with the rays 
    1714                 CastLineSegment(origin, termination, viewCells); 
    1715  
    1716                 ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 
    1717                  
    1718                 for (vit = viewCells.begin(); vit != vit_end; ++ vit) 
    1719                 { 
    1720                         BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit); 
    1721                         ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0])); 
    1722                 } 
    1723  
    1724                 mBspRays.push_back(ray); 
    1725         } 
    1726 } 
    1727  
     1733           
     1734                iit = ray->intersections.begin(); 
     1735 
     1736                BspLeaf *previousLeaf = (*iit).mLeaf; 
     1737                ++ iit; 
     1738                 
     1739                for (; iit != ray->intersections.end(); ++ iit) 
     1740                { 
     1741                        BspLeaf *leaf = (*iit).mLeaf; 
     1742 
     1743                        if (ShouldMerge(leaf, previousLeaf)) 
     1744                        {                        
     1745                                mVspBspTree->MergeViewCells(leaf, previousLeaf); 
     1746                                ++ merged; 
     1747                        } 
     1748                        previousLeaf = leaf; 
     1749                } 
     1750        } 
     1751        CLEAR_CONTAINER(bspRays); 
     1752 
     1753        return merged; 
     1754} 
     1755         
    17281756 
    17291757int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,  
     
    17401768        int pvsSize = 0; 
    17411769 
     1770        VssRayContainer postProcessRays; 
     1771        GetRaySets(rays, mPostProcessSamples, postProcessRays); 
     1772 
     1773        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl; 
    17421774        EvaluateViewCellsStats(); 
    1743         Debug << "original view cell partition:\n" << mViewCellsStats << endl; 
     1775        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl << endl; 
    17441776 
    17451777        mRenderer->RenderScene(); 
     
    17591791                        ExportViewCells(exporter); 
    17601792 
    1761                         bool exportGeometry = false; 
    1762                         environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry); 
    1763  
    1764                         if (exportGeometry) 
     1793                        if (mExportGeometry) 
    17651794                        { 
    17661795                                Material m; 
     
    17771806        } 
    17781807 
    1779         cout << "starting post processing using " << mPostProcessSamples << " samples ... "; 
    1780                  
    1781         long startTime = GetTime(); 
    1782  
    1783  
    1784         // $$JB we do not have connectivity information from the ray in the moment 
    1785         // perhaps we could recast the rays or rember the cells traversed inside the 
    1786         // vssray (which would on other hand create some overhead) 
    17871808        //-- merge or subdivide view cells 
    17881809        int merged = 0; 
    1789  
    1790         vector<BspIntersection>::const_iterator iit; 
    1791  
    1792         // matt TODO: remove 
    1793         if (0) 
    1794         { 
    1795                 if (mBspRays.empty()) 
    1796                         ConstructBspRays(rays, mPostProcessSamples); 
    1797  
    1798                 for (int i = 0; i < (int)mBspRays.size(); ++ i) 
    1799                 { 
    1800                         BspRay *ray = mBspRays[i]; 
    1801            
    1802                         // traverse leaves stored in the rays and compare and merge consecutive 
    1803                         // leaves (i.e., the neighbors in the tree) 
    1804                         if (ray->intersections.size() < 2) 
    1805                                 continue; 
    1806            
    1807                         iit = ray->intersections.begin(); 
    1808  
    1809                         BspLeaf *previousLeaf = (*iit).mLeaf; 
    1810                         ++ iit; 
    1811                  
    1812                         for (; iit != ray->intersections.end(); ++ iit) 
    1813                         { 
    1814                                 BspLeaf *leaf = (*iit).mLeaf; 
    1815  
    1816                                 if (ShouldMerge(leaf, previousLeaf)) 
    1817                                 {                        
    1818                                         MergeVspBspLeafViewCells(leaf, previousLeaf); 
    1819                                         ++ merged; 
    1820                                 } 
    1821                                 previousLeaf = leaf; 
    1822                         } 
    1823                 } 
    1824         } 
    1825         else 
    1826         { 
    1827                 merged = mVspBspTree->MergeLeaves(); 
    1828         } 
     1810         
     1811        cout << "starting merge using " << mPostProcessSamples << " samples ... "; 
     1812        long startTime = GetTime(); 
     1813 
     1814        merged = mVspBspTree->MergeViewCells(postProcessRays); 
    18291815 
    18301816        //-- stats and visualizations 
     
    18361822                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
    18371823         
     1824        ResetViewCells(); 
     1825        //BspLeaf::NewMail(); 
     1826        if (1) // export merged view cells 
     1827        { 
     1828                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d"); 
     1829                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl; 
     1830 
     1831                cout << "exporting view cells after merge ... "; 
     1832 
     1833                if (exporter) 
     1834                { 
     1835                        //exporter->SetWireframe(); 
     1836                        exporter->SetFilled(); 
     1837                        ExportViewCells(exporter); 
     1838 
     1839                        if (mExportGeometry) 
     1840                        { 
     1841                                Material m; 
     1842                                m.mDiffuseColor = RgbColor(0, 1, 0); 
     1843                                exporter->SetForcedMaterial(m); 
     1844                                exporter->SetFilled(); 
     1845 
     1846                                exporter->ExportGeometry(objects); 
     1847                        } 
     1848 
     1849                        delete exporter; 
     1850                } 
     1851                cout << "finished" << endl; 
     1852        } 
     1853 
     1854        Debug << "render time before refine:" << endl; 
     1855        mRenderer->RenderScene(); 
     1856        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss); 
     1857    Debug << ss << endl; 
     1858 
     1859        cout << "Refining the view cells ... "; 
     1860        startTime = GetTime(); 
     1861 
     1862        // refining the merged view cells 
     1863        const int refined = mVspBspTree->RefineViewCells(rays); 
     1864 
     1865        //-- stats and visualizations 
     1866        cout << "finished" << endl; 
     1867        cout << "refined " << refined << " view cells in " 
     1868                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl; 
     1869 
     1870        Debug << "Postprocessing: refined " << refined << " view cells in " 
     1871                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl; 
     1872         
     1873        // collapse sibling leaves that share the same view cell 
     1874        mVspBspTree->CollapseTree(mVspBspTree->GetRoot()); 
    18381875        // reset view cells and stats 
    18391876        ResetViewCells(); 
     
    18541891                return; 
    18551892 
    1856 #if 1 
    1857         if (mBspRays.empty()) 
    1858                 ConstructBspRays(sampleRays, mVisualizationSamples); 
    1859 #endif 
     1893        VssRayContainer visRays; 
     1894         
     1895        GetRaySets(sampleRays, mVisualizationSamples, visRays); 
    18601896 
    18611897        if (1) // export view cells 
    18621898        { 
    18631899                cout << "exporting view cells after post process ... "; 
    1864                 Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d"); 
     1900                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d"); 
    18651901 
    18661902                if (exporter) 
    18671903                { 
     1904                        if (mExportGeometry) 
     1905                                exporter->ExportGeometry(objects); 
    18681906                        ExportViewCells(exporter); 
    18691907                        delete exporter; 
     
    18801918        { 
    18811919                cout << "exporting splits ... "; 
    1882                 ExportSplits(objects); 
     1920                ExportSplits(objects, visRays); 
    18831921                cout << "finished" << endl; 
    18841922        } 
    18851923 
    1886         ExportBspPvs(objects); 
    1887 } 
    1888          
    1889  
    1890 void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects) 
     1924        // export single view cells 
     1925        ExportBspPvs(objects, visRays); 
     1926} 
     1927         
     1928 
     1929void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects, 
     1930                                                                                  const VssRayContainer &rays) 
    18911931{ 
    18921932        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d"); 
    1893  
    1894         bool exportRays = false; 
    1895         bool exportGeometry = false; 
    1896  
    1897         environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 
    1898         environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry); 
    18991933 
    19001934        if (exporter)  
     
    19151949                 
    19161950                // export rays 
    1917                 if (exportRays) 
    1918                 { 
    1919                         VssRayContainer outRays; 
    1920                  
    1921                         int raysSize = min((int)mBspRays.size(), mVisualizationSamples); 
    1922  
    1923                         for (int i = 0; i < raysSize; ++ i) 
    1924                                 // only rays piercing geometry 
    1925                                 outRays.push_back(mBspRays[i]->vssRay); 
    1926                                                  
    1927                         // export rays  
    1928                         exporter->ExportRays(outRays, RgbColor(1, 1, 0)); 
    1929                 } 
    1930  
    1931                 if (exportGeometry) 
     1951                if (mExportRays) 
     1952                        exporter->ExportRays(rays, RgbColor(1, 1, 0)); 
     1953         
     1954                if (mExportGeometry) 
    19321955                        exporter->ExportGeometry(objects); 
    19331956 
     
    19361959} 
    19371960 
    1938 void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects) 
    1939 { 
    1940         bool exportRays = false; 
    1941         bool exportGeometry = false; 
    1942  
    1943         environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 
    1944         environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry); 
    1945  
     1961void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects, 
     1962                                                                                  const VssRayContainer &rays) 
     1963{ 
    19461964        const int leafOut = 10; 
    19471965         
    19481966        ViewCell::NewMail(); 
    1949  
    1950         //-- some rays for output 
    1951         const int raysOut = min((int)mBspRays.size(), mVisualizationSamples); 
    19521967         
    19531968        cout << "visualization using " << mVisualizationSamples << " samples" << endl; 
    19541969        Debug << "\nOutput view cells: " << endl; 
    19551970         
    1956         // sort view cells to get largest view cells 
     1971        // sort view cells to visualize the largest view cells 
    19571972#if 0 
    19581973        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt); 
     
    19601975        int limit = min(leafOut, (int)mViewCells.size());  
    19611976 
     1977#if 1 
     1978        //-- some rays for output 
     1979        vector<BspRay *> bspRays; 
     1980        mVspBspTree->ConstructBspRays(bspRays, rays); 
     1981 
     1982        const int raysOut = min((int)bspRays.size(), mVisualizationSamples); 
     1983#endif 
     1984 
    19621985        for (int i = 0; i < limit; ++ i) 
    19631986        { 
    19641987                cout << "creating output for view cell " << i << " ... "; 
     1988                 
    19651989                VssRayContainer vcRays; 
    1966            Intersectable::NewMail(); 
     1990                Intersectable::NewMail(); 
    19671991#if 0 
    19681992                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]); 
    19691993#else 
    1970                 BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]); 
     1994                BspViewCell *vc = dynamic_cast<BspViewCell *> 
     1995                        (mViewCells[Random((int)mViewCells.size())]); 
    19711996#endif 
    1972                 cout << "creating output for view cell " << i << " ... "; 
    19731997 
    19741998#if 1 
     
    19762000                for (int k = 0; k < raysOut; ++ k)  
    19772001                { 
    1978                         BspRay *ray = mBspRays[k]; 
     2002                        BspRay *ray = bspRays[k]; 
    19792003                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j) 
    19802004                        { 
     
    19872011                //bspLeaves[j]->Mail(); 
    19882012                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i); 
    1989  
    19902013                Exporter *exporter = Exporter::GetExporter(s); 
    1991                          
    19922014                exporter->SetWireframe(); 
    19932015 
     
    19962018                exporter->SetForcedMaterial(m); 
    19972019 
    1998                 if (vc->GetMesh()) 
    1999                         exporter->ExportViewCell(vc); 
    2000                 else 
    2001                 { 
    2002                         PolygonContainer vcGeom; 
    2003                         // export view cell 
    2004                         mVspBspTree->ConstructGeometry(vc, vcGeom); 
    2005                         exporter->ExportPolygons(vcGeom); 
    2006                         CLEAR_CONTAINER(vcGeom); 
    2007                 } 
     2020                ExportVcGeometry(exporter, vc);  
    20082021                         
    2009                          
     2022                                 
    20102023                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()  
    2011                           << ", piercing rays=" << (int)vcRays.size() << endl; 
    2012  
    2013                          
    2014                 // export rays piercing this view cell 
     2024                          << ", piercing rays=" << (int)vcRays.size() 
     2025                          << ", leaves=" << (int)vc->mLeaves.size() << endl; 
     2026                 
     2027                //-- export rays piercing this view cell 
    20152028#if 1 
    20162029                exporter->ExportRays(vcRays, RgbColor(0, 1, 0)); 
     
    20492062        } 
    20502063 
     2064#if 1 
     2065        CLEAR_CONTAINER(bspRays); 
     2066#endif 
    20512067        Debug << endl; 
    20522068} 
    20532069 
    2054  
    2055 bool VspBspViewCellsManager::MergeVspBspLeafViewCells(BspLeaf *front,  
    2056                                                                                                           BspLeaf *back) const 
    2057 { 
    2058         BspViewCell *viewCell =  
    2059                 dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(),  
    2060                                                                                                    *back->GetViewCell())); 
    2061          
    2062         if (!viewCell) 
    2063                 return false; 
    2064  
    2065         // change view cells of all leaves 
    2066         // associated with the previous view cells 
    2067         BspViewCell *fVc = front->GetViewCell(); 
    2068         BspViewCell *bVc = back->GetViewCell(); 
    2069  
    2070         vector<BspLeaf *> fLeaves = fVc->mLeaves; 
    2071         vector<BspLeaf *> bLeaves = bVc->mLeaves; 
    2072  
    2073         vector<BspLeaf *>::const_iterator it; 
    2074          
    2075         for (it = fLeaves.begin(); it != fLeaves.end(); ++ it) 
    2076         { 
    2077                 (*it)->SetViewCell(viewCell); 
    2078                 viewCell->mLeaves.push_back(*it); 
    2079         } 
    2080         for (it = bLeaves.begin(); it != bLeaves.end(); ++ it) 
    2081         { 
    2082                 (*it)->SetViewCell(viewCell); 
    2083                 viewCell->mLeaves.push_back(*it); 
    2084         } 
    2085          
    2086         DEL_PTR(fVc); 
    2087         DEL_PTR(bVc); 
    2088  
    2089         return true; 
    2090 } 
    20912070 
    20922071bool VspBspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const 
     
    20952074        ViewCell *bvc = back->GetViewCell(); 
    20962075 
    2097         if ((fvc == mVspBspTree->GetRootCell()) ||  
    2098                 (bvc == mVspBspTree->GetRootCell()) ||  
    2099                 (fvc == bvc)) 
     2076        if (fvc == bvc) 
    21002077                return false; 
    21012078 
     
    21062083                if ((fvc->GetPvs().GetSize() < mMinPvs) ||       
    21072084                        (bvc->GetPvs().GetSize() < mMinPvs) || 
    2108                         ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif))) 
     2085                        ((fdiff < mMinPvsDif) &&  
     2086                         (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif))) 
    21092087                { 
    21102088                        return true; 
     
    21672145 
    21682146 
    2169 void VspBspViewCellsManager::ExportGeometry(Exporter *exporter,  
    2170                                                                                         ViewCell *vc) const 
    2171 { 
    2172         if (vc->GetMesh()) 
    2173                 exporter->ExportViewCell(vc); 
    2174         else 
    2175         { 
    2176                 PolygonContainer cell; 
    2177                 mVspBspTree-> 
    2178                         ConstructGeometry(dynamic_cast<BspViewCell *>(vc), cell); 
    2179  
    2180                 exporter->ExportPolygons(cell); 
    2181         } 
     2147void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter,  
     2148                                                                                          ViewCell *vc) const 
     2149{ 
     2150#if 1 
     2151        BspNodeGeometry geom; 
     2152        mVspBspTree-> 
     2153                ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom.mPolys); 
     2154        exporter->ExportPolygons(geom.mPolys); 
     2155#else 
     2156         
     2157        Material m2; 
     2158        m2.mDiffuseColor.b = 0.3f + Random(0.7f); 
     2159        m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f); 
     2160        m2.mDiffuseColor.g = 0.3f + Random(0.7f); 
     2161        Material m; 
     2162        m.mDiffuseColor.b = 0.0f; 
     2163        m.mDiffuseColor.r = 1.0f; 
     2164        m.mDiffuseColor.g = 0.0f; 
     2165 
     2166        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc); 
     2167        vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end(); 
     2168 
     2169        for (it = bspVc->mLeaves.begin(); it != it_end; ++ it) 
     2170        { 
     2171                if ((*it)->Mailed()) 
     2172                        exporter->SetForcedMaterial(m); 
     2173                else 
     2174                        exporter->SetForcedMaterial(m2); 
     2175                        //exporter->ResetForcedMaterial(); 
     2176                BspNodeGeometry geom; 
     2177                mVspBspTree->ConstructGeometry(*it, geom); 
     2178                exporter->ExportPolygons(geom.mPolys); 
     2179        } 
     2180#endif 
    21822181} 
    21832182 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

    r482 r485  
    186186        ViewCellContainer &GetViewCells(); 
    187187 
    188         /** Helper function used to split ray set into one used for view cell 
    189                 construction and one cast after construction. 
     188        /** Helper function used to split ray sets uniformly  
     189                into one that is currently used and the other that  
     190                is saved for later processing. 
     191                @param sourceRays the input ray set 
     192                @param maxSize the maximal number of rays that will be used 
     193                @param usedRays returns the used ray set 
     194                @param savedRays if not null, returns the saved ray set 
    190195        */ 
    191196        void GetRaySets(const VssRayContainer &sourceRays, 
    192                                         VssRayContainer &constructionRays,  
    193                                         VssRayContainer &savedRays) const; 
    194  
     197                                        const int maxSize, 
     198                                        VssRayContainer &usedRays,  
     199                                        VssRayContainer *savedRays = NULL) const; 
     200         
    195201        /** Returns accumulated area of all view cells. 
    196202        */ 
     
    242248        /** Exports view cell geometry. 
    243249        */ 
    244         virtual void ExportGeometry(Exporter *exporter, ViewCell *vc) const = 0; 
     250        virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0; 
    245251 
    246252        /// the view cell corresponding to unbounded space 
     
    266272        float mTotalArea; 
    267273 
    268         // visualization color code 
     274        //-- visualization options 
     275         
     276        /// color code for view cells 
    269277        int mColorCode; 
     278        bool mExportGeometry; 
     279        bool mExportRays; 
    270280 
    271281        ViewCellsStatistics mViewCellsStats; 
     
    281291 
    282292public: 
    283  
     293        /** Constructor taking the bsp tree and the number of samples 
     294                used to construct the bsp tree. 
     295        */ 
    284296        BspViewCellsManager(BspTree *tree, int constructionSamples); 
    285297 
     
    330342 
    331343        void ExportColor(Exporter *exporter, ViewCell *vc) const; 
    332         void ExportGeometry(Exporter *exporter, ViewCell *vc) const; 
     344        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 
    333345 
    334346        /// the BSP tree. 
     
    393405 
    394406        void ExportColor(Exporter *exporter, ViewCell *vc) const; 
    395         void ExportGeometry(Exporter *exporter, ViewCell *vc) const; 
     407        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 
    396408 
    397409        /// the BSP tree. 
     
    450462 
    451463        void ExportColor(Exporter *exporter, ViewCell *vc) const; 
    452         void ExportGeometry(Exporter *exporter, ViewCell *vc) const; 
     464        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 
    453465 
    454466 
     
    499511 
    500512protected: 
    501  
    502         /** Constructs bsp rays for post processing and visualization. 
    503         */ 
    504         void ConstructBspRays(const VssRayContainer &rays, const int numSamples); 
    505  
    506         /** Merges view cells front and back leaf view cell. 
    507         */ 
    508         bool MergeVspBspLeafViewCells(BspLeaf *front, BspLeaf *back) const; 
     513        /** DEPRECATED 
     514        */ 
     515        int MergeViewCells(const VssRayContainer &rays) const; 
    509516 
    510517        /** Returns true if front and back leaf should be merged. 
     
    513520 
    514521        void CollectViewCells(); 
    515  
    516         void ExportColor(Exporter *exporter, ViewCell *vc) const; 
    517         void ExportGeometry(Exporter *exporter, ViewCell *vc) const; 
    518522 
    519523        /** Returns maximal depth difference of view cell  
     
    521525        */ 
    522526        int GetMaxTreeDiff(ViewCell *vc) const; 
     527         
     528 
     529        void ExportColor(Exporter *exporter, ViewCell *vc) const; 
     530        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const; 
     531 
    523532 
    524533        /// the view space partition BSP tree. 
    525534        VspBspTree *mVspBspTree; 
    526535 
    527         /// helper array of rays 
    528         vector<BspRay *> mBspRays; 
    529  
    530536private: 
    531537 
    532538        /** Exports visualization of the BSP splits. 
    533539        */ 
    534         void ExportSplits(const ObjectContainer &objects); 
     540        void ExportSplits(const ObjectContainer &objects,  
     541                                          const VssRayContainer &rays); 
    535542 
    536543        /** Exports visualization of the BSP PVS. 
    537544        */ 
    538         void ExportBspPvs(const ObjectContainer &objects); 
     545        void ExportBspPvs(const ObjectContainer &objects, 
     546                                          const VssRayContainer &rays); 
    539547 
    540548}; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

    r484 r485  
    3333int VspBspTree::sFrontAndBackId = 0; 
    3434 
    35 float BspMergeCandidate::sOverallCost = Limits::Small; 
     35float BspMergeCandidate::sOverallCost = 0; 
    3636 
    3737/****************************************************************/ 
     
    4444mCostNormalizer(Limits::Small), 
    4545mViewCellsManager(NULL), 
    46 mStoreRays(true), 
     46mStoreRays(false), 
    4747mOnlyDrivingAxis(false) 
    4848{ 
    49         mRootCell = new BspViewCell(); 
    50  
    5149        Randomize(); // initialise random generator for heuristics 
    5250 
     
    8280        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio); 
    8381 
     82        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); 
     83        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge); 
    8484 
    8585        //-- debug output 
     
    137137{ 
    138138        DEL_PTR(mRoot); 
    139         DEL_PTR(mRootCell); 
    140139        DEL_PTR(mSplitCandidates); 
    141140} 
     
    216215                { 
    217216                        mBox.Include(object->GetBox()); // add to BSP tree aabb 
    218                         AddMeshToPolygons(mesh, polys, mRootCell); 
     217                        AddMeshToPolygons(mesh, polys, NULL); 
    219218                } 
    220219        } 
     
    360359                 (data.mPvs <= mTermMinPvs)   || 
    361360                 (data.mArea <= mTermMinArea) || 
    362                  (mStat.nodes / 2 + 1 >= mMaxViewCells) || 
     361                 (mStat.Leaves() >= mMaxViewCells) || 
    363362                // (data.GetAvgRayContribution() >= mTermMaxRayContribution) || 
    364363                 (data.mDepth >= mTermMaxDepth)); 
     
    400399                BspViewCell *viewCell = new BspViewCell(); 
    401400                leaf->SetViewCell(viewCell); 
    402  
     401                 
    403402                if (mStoreRays) 
    404403                { 
     
    410409                viewCell->mLeaves.push_back(leaf); 
    411410                viewCell->SetArea(tData.mArea); 
     411                leaf->mArea = tData.mArea; 
    412412 
    413413                //-- update pvs 
    414414                int conSamp = 0, sampCon = 0; 
    415415                AddToPvs(leaf, *tData.mRays, conSamp, sampCon); 
    416  
     416         
    417417                mStat.contributingSamples += conSamp; 
    418418                mStat.sampleContributions += sampCon; 
     
    10651065                        // add the termination object 
    10661066                        AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs); 
    1067  
    10681067                        // add the source object 
    10691068                        AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs); 
     
    10811080                                if (cf == 1) 
    10821081                                        pFront += len; 
    1083                                 if (cf == -1) 
     1082                                else if (cf == -1) 
    10841083                                        pBack += len; 
    1085                                 if (cf == 0) 
     1084                                else if (cf == 0) 
    10861085                                { 
    10871086                                        // use length of rays to approximate volume 
     
    12311230                mStat.maxDepth = data.mDepth; 
    12321231 
     1232        if (data.mPvs > mStat.maxPvs) 
     1233                mStat.maxPvs = data.mPvs; 
    12331234        if (data.mDepth < mStat.minDepth) 
    12341235                mStat.minDepth = data.mDepth; 
    1235  
    12361236        if (data.mDepth >= mTermMaxDepth) 
    12371237                ++ mStat.maxDepthNodes; 
     
    14361436                float t; 
    14371437 
    1438                         // get classification and receive new t 
     1438                // get classification and receive new t 
    14391439                const int cf = bRay.ComputeRayIntersection(plane, t); 
    14401440 
     
    14481448                        break; 
    14491449                case 0: 
    1450                         //-- split ray 
    1451                         //--  look if start point behind or in front of plane 
    1452                         if (plane.Side(bRay.ExtrapOrigin()) <= 0) 
    14531450                        { 
    1454                                 backRays.push_back(RayInfo(ray, bRay.GetMinT(), t)); 
    1455                                 frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT())); 
    1456                         } 
    1457                         else 
    1458                         { 
    1459                                 frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t)); 
    1460                                 backRays.push_back(RayInfo(ray, t, bRay.GetMaxT())); 
     1451                                //-- split ray 
     1452                                //-- test if start point behind or in front of plane 
     1453                                const int side = plane.Side(bRay.ExtrapOrigin()); 
     1454 
     1455                                if (side <= 0) 
     1456                                { 
     1457                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t)); 
     1458                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT())); 
     1459                                } 
     1460                                else 
     1461                                { 
     1462                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t)); 
     1463                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT())); 
     1464                                } 
    14611465                        } 
    14621466                        break; 
    14631467                default: 
    1464                         Debug << "Should not come here 4" << endl; 
     1468                        Debug << "Should not come here" << endl; 
    14651469                        break; 
    14661470                } 
     
    14971501} 
    14981502 
     1503 
    14991504void VspBspTree::ConstructGeometry(BspNode *n, 
    15001505                                                                   BspNodeGeometry &cell) const 
    15011506{ 
    1502         PolygonContainer polys; 
    1503         ConstructGeometry(n, polys); 
    1504         cell.mPolys = polys; 
    1505 } 
     1507        ConstructGeometry(n, cell.mPolys); 
     1508} 
     1509 
    15061510 
    15071511void VspBspTree::ConstructGeometry(BspNode *n, 
     
    15881592} 
    15891593 
    1590 void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const 
     1594 
     1595void VspBspTree::ConstructGeometry(BspViewCell *vc,  
     1596                                                                   PolygonContainer &vcGeom) const 
    15911597{ 
    15921598        vector<BspLeaf *> leaves = vc->mLeaves; 
    1593  
    15941599        vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 
    15951600 
     
    15981603} 
    15991604 
     1605 
    16001606int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
    16011607                                                   const bool onlyUnmailed) const 
    16021608{ 
    16031609        PolygonContainer cell; 
    1604  
    16051610        ConstructGeometry(n, cell); 
    16061611 
     
    17941799} 
    17951800 
    1796 BspViewCell *VspBspTree::GetRootCell() const 
    1797 { 
    1798         return mRootCell; 
    1799 } 
    18001801 
    18011802int VspBspTree::SplitPolygons(const Plane3 &plane, 
     
    18581859        BspNode *farChild = NULL; 
    18591860 
     1861        float t; 
    18601862        while (1) 
    18611863        { 
     
    18651867 
    18661868                        Plane3 splitPlane = in->GetPlane(); 
     1869                         
    18671870                        const int entSide = splitPlane.Side(entp); 
    18681871                        const int extSide = splitPlane.Side(extp); 
    18691872 
    1870                         if (entSide < 0) 
     1873                        if (entSide < 0)  
    18711874                        { 
    18721875                                node = in->GetBack(); 
    1873  
    1874                                 if (extSide <= 0) // plane does not split ray => no far child 
     1876                                // plane does not split ray => no far child 
     1877                                if (extSide <= 0)  
    18751878                                        continue; 
    18761879 
    18771880                                farChild = in->GetFront(); // plane splits ray 
    1878                         } else if (entSide > 0) 
     1881                        }  
     1882                        else if (entSide > 0) 
    18791883                        { 
    18801884                                node = in->GetFront(); 
     
    18851889                                farChild = in->GetBack(); // plane splits ray 
    18861890                        } 
    1887                         else // ray and plane are coincident 
    1888                         { 
    1889                                 // WHAT TO DO IN THIS CASE ? 
    1890                                 //break; 
    1891                                 node = in->GetFront(); 
    1892                                 continue; 
     1891                        else // ray end point on plane 
     1892                        {       // NOTE: what to do if ray is coincident with plane? 
     1893                                if (extSide < 0) 
     1894                                        node = in->GetBack(); 
     1895                                else if (extSide > 0) 
     1896                                        node = in->GetFront(); 
     1897 
     1898                                continue; // no far child 
    18931899                        } 
    18941900 
    18951901                        // push data for far child 
    1896                         tStack.push(BspRayTraversalData(farChild, extp, maxt)); 
     1902                        tStack.push(BspRayTraversalData(farChild, extp)); 
    18971903 
    18981904                        // find intersection of ray segment with plane 
    1899                         float t; 
    19001905                        extp = splitPlane.FindIntersection(origin, extp, &t); 
    1901                         maxt *= t; 
    1902  
    1903                 } else 
     1906                }  
     1907                else 
    19041908                { 
    19051909                        // reached leaf => intersection with view cell 
     
    19181922 
    19191923                        entp = extp; 
    1920                         mint = maxt; // NOTE: need this? 
    1921  
    1922  
     1924                         
    19231925                        BspRayTraversalData &s = tStack.top(); 
    19241926 
    19251927                        node = s.mNode; 
    19261928                        extp = s.mExitPoint; 
    1927                         maxt = s.mMaxT; 
    19281929 
    19291930                        tStack.pop(); 
    19301931                } 
    19311932        } 
     1933 
    19321934        return hits; 
    19331935} 
    19341936 
    1935 int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) 
     1937int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const 
    19361938{ 
    19371939        std::deque<BspNode *> path1; 
     
    19971999                } 
    19982000        } 
     2001 
     2002        // revalidate leaves 
     2003        RepairVcLeafLists(); 
    19992004 
    20002005        return node; 
     
    20402045 
    20412046 
    2042 int VspBspTree::MergeLeaves() 
    2043 { 
    2044         vector<BspLeaf *> leaves; 
    2045         priority_queue<BspMergeCandidate> mergeQueue; 
    2046  
    2047         // collect the leaves, e.g., the "voxels" that will build the view cells 
    2048         CollectLeaves(leaves); 
    2049  
    2050         int vcSize = (int)leaves.size(); 
    2051         int savedVcSize = vcSize; 
    2052  
    2053         BspLeaf::NewMail(); 
    2054  
    2055         vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 
    2056  
    2057         // find merge candidates and push them into queue 
    2058         for (it = leaves.begin(); it != it_end; ++ it) 
    2059         { 
    2060                 BspLeaf *leaf = *it; 
    2061  
    2062                 // no leaf is part of two merge candidates 
    2063                 if (!leaf->Mailed()) 
    2064                 { 
    2065                         leaf->Mail(); 
    2066  
    2067                         vector<BspLeaf *> neighbors; 
    2068                         FindNeighbors(leaf, neighbors, true); 
    2069  
    2070                         vector<BspLeaf *>::const_iterator nit, 
    2071                                 nit_end = neighbors.end(); 
    2072  
    2073                         for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
    2074                         { 
    2075                                 BspMergeCandidate mc = BspMergeCandidate(leaf, *nit); 
    2076                                 mergeQueue.push(mc); 
    2077  
    2078                                 BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 
    2079                                 BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 
    2080                         } 
    2081                 } 
    2082         } 
    2083  
    2084         int merged = 0; 
    2085         int mergedSiblings = 0; 
    2086         int accTreeDist = 0; 
    2087         int maxTreeDist = 0; 
    2088         const bool mergeStats = true; 
    2089  
    2090  
    2091         //-- use priority queue to merge leaf pairs 
    2092         while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) && 
    2093                    (mergeQueue.top().GetMergeCost() < 
    2094                     mMergeMaxCostRatio * BspMergeCandidate::sOverallCost)) 
    2095         { 
    2096                 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
    2097                 BspMergeCandidate mc = mergeQueue.top(); 
    2098                 mergeQueue.pop(); 
    2099  
    2100                 // both view cells equal! 
    2101                 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 
    2102                         continue; 
    2103  
    2104                 if (mc.Valid()) 
    2105                 { 
    2106                         ViewCell::NewMail(); 
    2107                         MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 
    2108                         -- vcSize; 
    2109                         // increase absolute merge cost 
    2110                         BspMergeCandidate::sOverallCost += mc.GetMergeCost(); 
    2111  
    2112                         //-- stats 
    2113                         ++ merged; 
    2114  
    2115                         if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2())) 
    2116                                 ++ mergedSiblings; 
    2117  
    2118                         if (mergeStats) 
    2119                         { 
    2120                                 const int dist = TreeDistance(mc.GetLeaf1(), mc.GetLeaf2()); 
    2121  
    2122                                 if (dist > maxTreeDist) 
    2123                                         maxTreeDist = dist; 
    2124  
    2125                                 accTreeDist += dist; 
    2126                         } 
    2127                 } 
    2128                 // merge candidate not valid, because one of the leaves was already 
    2129                 // merged with another one 
    2130                 else 
    2131                 { 
    2132                         // validate and reinsert into queue 
    2133                         mc.SetValid(); 
    2134                         mergeQueue.push(mc); 
    2135                         //Debug << "validate " << mc.GetMergeCost() << endl; 
    2136                 } 
    2137         } 
    2138  
    2139         // collapse tree according to view cell partition 
    2140         CollapseTree(mRoot); 
    2141         // revalidate leaves 
    2142         RepairVcLeafLists(); 
    2143  
    2144         Debug << "Merged " << merged << " nodes of " << savedVcSize 
    2145                   << " (merged " << mergedSiblings << " siblings)" << endl; 
    2146  
    2147         if (mergeStats) 
    2148         { 
    2149                 Debug << "maximal tree distance: " << maxTreeDist << endl; 
    2150                 Debug << "Avg tree distance: " << (float)accTreeDist / (float)merged << endl; 
    2151         } 
    2152  
    2153         //TODO: should return sample contributions 
    2154         return merged; 
    2155 } 
    2156  
    2157  
    2158 bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) 
     2047bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) const 
    21592048{ 
    21602049        //-- change pointer to view cells of all leaves associated 
     
    22042093        mViewCellsManager = vcm; 
    22052094} 
     2095 
     2096 
     2097int VspBspTree::CollectMergeCandidates() 
     2098{ 
     2099        vector<BspLeaf *> leaves; 
     2100 
     2101        // collect the leaves, e.g., the "voxels" that will build the view cells 
     2102        CollectLeaves(leaves); 
     2103        BspLeaf::NewMail(); 
     2104 
     2105        vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 
     2106 
     2107        // find merge candidates and push them into queue 
     2108        for (it = leaves.begin(); it != it_end; ++ it) 
     2109        { 
     2110                BspLeaf *leaf = *it; 
     2111                 
     2112                /// create leaf pvs (needed for post processing 
     2113                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs()); 
     2114 
     2115                BspMergeCandidate::sOverallCost +=  
     2116                        leaf->mArea * leaf->mPvs->GetSize(); 
     2117 
     2118                // the same leaves must not be part of two merge candidates 
     2119                leaf->Mail(); 
     2120                vector<BspLeaf *> neighbors; 
     2121                FindNeighbors(leaf, neighbors, true); 
     2122 
     2123                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end(); 
     2124 
     2125                // TODO: test if at least one ray goes from one leaf to the other 
     2126                for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
     2127                {                        
     2128                        mMergeQueue.push(BspMergeCandidate(leaf, *nit)); 
     2129                } 
     2130        } 
     2131 
     2132        return (int)leaves.size(); 
     2133} 
     2134 
     2135 
     2136int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays) 
     2137{ 
     2138        vector<BspRay *> bspRays; 
     2139 
     2140        ConstructBspRays(bspRays, rays); 
     2141        map<BspLeaf *, vector<BspLeaf*> > neighborMap; 
     2142 
     2143        vector<BspIntersection>::const_iterator iit; 
     2144 
     2145        int leaves = 0; 
     2146         
     2147        BspLeaf::NewMail(); 
     2148 
     2149        for (int i = 0; i < (int)bspRays.size(); ++ i) 
     2150        {   
     2151                BspRay *ray = bspRays[i]; 
     2152           
     2153                // traverse leaves stored in the rays and compare and  
     2154                // merge consecutive leaves (i.e., the neighbors in the tree) 
     2155                if (ray->intersections.size() < 2) 
     2156                        continue; 
     2157           
     2158                iit = ray->intersections.begin(); 
     2159                BspLeaf *prevLeaf = (*(iit ++)).mLeaf; 
     2160                 
     2161                // create leaf pvs (needed for post processing) 
     2162                if (!prevLeaf->mPvs) 
     2163                { 
     2164                        prevLeaf->mPvs =  
     2165                                new ObjectPvs(prevLeaf->GetViewCell()->GetPvs()); 
     2166 
     2167                        BspMergeCandidate::sOverallCost +=  
     2168                                prevLeaf->mArea * prevLeaf->mPvs->GetSize(); 
     2169                         
     2170                        ++ leaves; 
     2171                } 
     2172                 
     2173                // traverse intersections  
     2174                // consecutive leaves are neighbors =>  
     2175                // add them to queue 
     2176                for (; iit != ray->intersections.end(); ++ iit) 
     2177                { 
     2178            BspLeaf *leaf = (*iit).mLeaf; 
     2179             
     2180                        if (!leaf->mPvs) 
     2181                        { 
     2182                                leaf->mPvs =  
     2183                                        new ObjectPvs(leaf->GetViewCell()->GetPvs()); 
     2184                                 
     2185                                BspMergeCandidate::sOverallCost +=  
     2186                                        leaf->mArea * leaf->mPvs->GetSize(); 
     2187 
     2188                                ++ leaves; 
     2189                        } 
     2190                 
     2191                        vector<BspLeaf *> &neighbors = neighborMap[leaf]; 
     2192                         
     2193                        bool found = false; 
     2194 
     2195                        // both leaves inserted in queue already => 
     2196                        // look if double pair already exists 
     2197                        if (leaf->Mailed() && prevLeaf->Mailed()) 
     2198                        { 
     2199                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end(); 
     2200                                 
     2201                for (it = neighbors.begin(); !found && (it != it_end); ++ it) 
     2202                                        if (*it == prevLeaf) 
     2203                                                found = true; // already in queue 
     2204                        } 
     2205                         
     2206                        if (!found) 
     2207                        { 
     2208                                // this pair is not in map already 
     2209                                // => insert into the neighbor map and the queue 
     2210                                neighbors.push_back(prevLeaf); 
     2211                                neighborMap[prevLeaf].push_back(leaf); 
     2212 
     2213                                leaf->Mail(); 
     2214                                prevLeaf->Mail(); 
     2215 
     2216                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf)); 
     2217                        } 
     2218 
     2219                        prevLeaf = leaf; 
     2220        } 
     2221        } 
     2222        Debug << "neighbormap size: " << (int)neighborMap.size() << endl; 
     2223        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl; 
     2224        Debug << "leaves in queue: " << leaves << endl; 
     2225        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl; 
     2226 
     2227        CLEAR_CONTAINER(bspRays); 
     2228 
     2229        return leaves; 
     2230} 
     2231 
     2232 
     2233void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays, 
     2234                                                                  const VssRayContainer &rays) 
     2235{ 
     2236        VssRayContainer::const_iterator it, it_end = rays.end(); 
     2237 
     2238        for (it = rays.begin(); it != rays.end(); ++ it) 
     2239        { 
     2240                VssRay *vssRay = *it; 
     2241                BspRay *ray = new BspRay(vssRay); 
     2242 
     2243                ViewCellContainer viewCells; 
     2244 
     2245                Ray hray(*vssRay); 
     2246                float tmin = 0, tmax = 1.0; 
     2247                // matt TODO: remove this!! 
     2248                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT); 
     2249                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) 
     2250                        continue; 
     2251 
     2252                Vector3 origin = hray.Extrap(tmin); 
     2253                Vector3 termination = hray.Extrap(tmax); 
     2254         
     2255                // cast line segment to get intersections with bsp leaves 
     2256                CastLineSegment(origin, termination, viewCells); 
     2257 
     2258                ViewCellContainer::const_iterator vit, vit_end = viewCells.end(); 
     2259                for (vit = viewCells.begin(); vit != vit_end; ++ vit) 
     2260                { 
     2261                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit); 
     2262                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end(); 
     2263                        //NOTE: not sorted! 
     2264                        for (it = vc->mLeaves.begin(); it != it_end; ++ it) 
     2265                                ray->intersections.push_back(BspIntersection(0, *it)); 
     2266                } 
     2267 
     2268                bspRays.push_back(ray); 
     2269        } 
     2270} 
     2271 
     2272 
     2273int VspBspTree::MergeViewCells(const VssRayContainer &rays) 
     2274{ 
     2275        MergeStatistics mergeStats; 
     2276        mergeStats.Start(); 
     2277        // TODO: REMOVE LATER for performance! 
     2278        const bool showMergeStats = true; 
     2279        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs; 
     2280        long startTime = GetTime(); 
     2281 
     2282        if (mUseRaysForMerge) 
     2283                mergeStats.nodes = CollectMergeCandidates(rays); 
     2284        else 
     2285                mergeStats.nodes = CollectMergeCandidates(); 
     2286 
     2287        mergeStats.collectTime = TimeDiff(startTime, GetTime()); 
     2288        mergeStats.candidates = (int)mMergeQueue.size(); 
     2289        startTime = GetTime(); 
     2290 
     2291        int nViewCells = /*mergeStats.nodes*/ mStat.Leaves(); 
     2292 
     2293         
     2294        //-- use priority queue to merge leaf pairs 
     2295        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) && 
     2296                   (mMergeQueue.top().GetMergeCost() < 
     2297                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost)) 
     2298        { 
     2299                //Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: " 
     2300                //        << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost  
     2301                //        << " max ratio: " << mMergeMaxCostRatio << endl; 
     2302                BspMergeCandidate mc = mMergeQueue.top(); 
     2303                mMergeQueue.pop(); 
     2304 
     2305                // both view cells equal! 
     2306                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 
     2307                        continue; 
     2308 
     2309                if (mc.Valid()) 
     2310                { 
     2311                        ViewCell::NewMail(); 
     2312                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 
     2313                        -- nViewCells; 
     2314                         
     2315                        ++ mergeStats.merged; 
     2316                         
     2317                        // increase absolute merge cost 
     2318                        BspMergeCandidate::sOverallCost += mc.GetMergeCost(); 
     2319 
     2320                        if (showMergeStats) 
     2321                        { 
     2322                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2())) 
     2323                                        ++ mergeStats.siblings; 
     2324 
     2325                                const int dist =  
     2326                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2()); 
     2327                                if (dist > mergeStats.maxTreeDist) 
     2328                                        mergeStats.maxTreeDist = dist; 
     2329                                mergeStats.accTreeDist += dist; 
     2330                        } 
     2331                } 
     2332                // merge candidate not valid, because one of the leaves was already 
     2333                // merged with another one => validate and reinsert into queue 
     2334                else 
     2335                {  
     2336                        mc.SetValid(); 
     2337                        mMergeQueue.push(mc); 
     2338                } 
     2339        } 
     2340 
     2341        mergeStats.mergeTime = TimeDiff(startTime, GetTime()); 
     2342        mergeStats.Stop(); 
     2343 
     2344        if (showMergeStats) 
     2345                Debug << mergeStats << endl << endl; 
     2346         
     2347        //TODO: should return sample contributions? 
     2348        return mergeStats.merged; 
     2349} 
     2350 
     2351 
     2352int VspBspTree::RefineViewCells(const VssRayContainer &rays) 
     2353{ 
     2354        int shuffled = 0; 
     2355 
     2356        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl; 
     2357        BspLeaf::NewMail(); 
     2358 
     2359        // Use priority queue of remaining leaf pairs  
     2360        // These candidates either share the same view cells or 
     2361        // are border leaves which share a boundary. 
     2362        // We test if they can be shuffled, i.e., 
     2363        // either one leaf is made part of one view cell or the other 
     2364        // leaf is made part of the other view cell. It is tested if the 
     2365        // remaining view cells are "better" than the old ones. 
     2366        while (!mMergeQueue.empty()) 
     2367        { 
     2368                BspMergeCandidate mc = mMergeQueue.top(); 
     2369                mMergeQueue.pop(); 
     2370 
     2371                // both view cells equal or already shuffled 
     2372                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) || 
     2373                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed())) 
     2374                        continue; 
     2375                 
     2376                // candidate for shuffling 
     2377                const bool wasShuffled =  
     2378                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2()); 
     2379                 
     2380                //-- stats 
     2381                if (wasShuffled) 
     2382                        ++ shuffled; 
     2383        } 
     2384 
     2385        return shuffled; 
     2386} 
     2387 
     2388 
     2389inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 
     2390{ 
     2391        return pvs1.AddPvs(pvs2); 
     2392} 
     2393 
     2394/*inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2) 
     2395{ 
     2396        ObjectPvs pvs; 
     2397        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end(); 
     2398        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it) 
     2399                if (*it != l) 
     2400                        pvs.AddPvs(*(*it)->mPvs); 
     2401        return pvs.GetSize(); 
     2402}*/ 
     2403 
     2404inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2) 
     2405{ 
     2406        return pvs1.SubtractPvs(pvs2); 
     2407} 
     2408 
     2409 
     2410float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) 
     2411{ 
     2412        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs); 
     2413        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs); 
     2414        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs); 
     2415 
     2416        const float area1 = vc1->GetArea() - leaf->mArea; 
     2417        const float area2 = vc2->GetArea() + leaf->mArea; 
     2418 
     2419        const float cost1 = pvs1 * area1; 
     2420        const float cost2 = pvs2 * area2; 
     2421 
     2422        return cost1 + cost2; 
     2423} 
     2424 
     2425 
     2426void VspBspTree::ShuffleLeaf(BspLeaf *leaf,  
     2427                                                         BspViewCell *vc1,  
     2428                                                         BspViewCell *vc2) const 
     2429{ 
     2430        //Debug << "old pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize()  
     2431        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl; 
     2432        // compute new pvs and area 
     2433        vc1->GetPvs().SubtractPvs(*leaf->mPvs); 
     2434        vc2->GetPvs().AddPvs(*leaf->mPvs); 
     2435         
     2436        vc1->SetArea(vc1->GetArea() - leaf->mArea); 
     2437        vc2->SetArea(vc2->GetArea() + leaf->mArea); 
     2438 
     2439        /// add to second view cell 
     2440        vc2->mLeaves.push_back(leaf); 
     2441 
     2442        // erase leaf from old view cell 
     2443        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin(); 
     2444 
     2445        for (; *it != leaf; ++ it); 
     2446        vc1->mLeaves.erase(it); 
     2447 
     2448        /*vc1->GetPvs().mEntries.clear(); 
     2449        for (; it != vc1->mLeaves.end(); ++ it) 
     2450        { 
     2451                if (*it == leaf) 
     2452                        vc1->mLeaves.erase(it); 
     2453                else 
     2454                        vc1->GetPvs().AddPvs(*(*it)->mPvs); 
     2455        }*/ 
     2456 
     2457        leaf->SetViewCell(vc2);         // finally change view cell 
     2458         
     2459        //Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize()  
     2460        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl; 
     2461 
     2462} 
     2463 
     2464 
     2465bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const 
     2466{ 
     2467        BspViewCell *vc1 = leaf1->GetViewCell(); 
     2468        BspViewCell *vc2 = leaf2->GetViewCell(); 
     2469 
     2470        const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea(); 
     2471        const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea(); 
     2472 
     2473        const float oldCost = cost1 + cost2; 
     2474         
     2475        float shuffledCost1 = Limits::Infinity; 
     2476        float shuffledCost2 = Limits::Infinity; 
     2477 
     2478        // the view cell should not be empty after the shuffle 
     2479        if (vc1->mLeaves.size() > 1) 
     2480                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2); 
     2481        if (vc2->mLeaves.size() > 1) 
     2482                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1); 
     2483 
     2484        // shuffling unsuccessful 
     2485        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2)) 
     2486                return false; 
     2487         
     2488        if (shuffledCost1 < shuffledCost2) 
     2489        { 
     2490                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl; 
     2491                ShuffleLeaf(leaf1, vc1, vc2); 
     2492                leaf1->Mail(); 
     2493        } 
     2494        else 
     2495        { 
     2496                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl; 
     2497                ShuffleLeaf(leaf2, vc2, vc1); 
     2498                leaf2->Mail(); 
     2499        } 
     2500 
     2501        return true; 
     2502} 
     2503 
    22062504 
    22072505/************************************************************************/ 
     
    22202518} 
    22212519 
     2520float BspMergeCandidate::GetCost(ViewCell *vc) const 
     2521{ 
     2522        return vc->GetPvs().GetSize() * vc->GetArea(); 
     2523} 
     2524 
    22222525float BspMergeCandidate::GetLeaf1Cost() const 
    22232526{ 
    22242527        BspViewCell *vc = mLeaf1->GetViewCell(); 
    2225         return vc->GetPvs().GetSize() * vc->GetArea(); 
     2528        return GetCost(vc); 
    22262529} 
    22272530 
     
    22292532{ 
    22302533        BspViewCell *vc = mLeaf2->GetViewCell(); 
    2231         return vc->GetPvs().GetSize() * vc->GetVolume(); 
     2534        return GetCost(vc); 
    22322535} 
    22332536 
     
    22392542 
    22402543        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 
    2241         const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 
     2544        const int newPvs = diff1 + vc1->GetPvs().GetSize(); 
    22422545 
    22432546        //-- compute ratio of old cost 
     
    22472550 
    22482551        const float newCost = 
    2249                 (float)vcPvs * (vc1->GetArea() + vc2->GetArea()); 
     2552                (float)newPvs * (vc1->GetArea() + vc2->GetArea()); 
    22502553 
    22512554        mMergeCost = newCost - oldCost; 
    2252  
    22532555//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 
    22542556//              mMergeCost += 1.0; 
     
    22942596        EvalMergeCost(); 
    22952597} 
     2598 
     2599 
     2600/************************************************************************/ 
     2601/*                  MergeStatistics implementation                      */ 
     2602/************************************************************************/ 
     2603 
     2604 
     2605void MergeStatistics::Print(ostream &app) const 
     2606{ 
     2607        app << "===== Merge statistics ===============\n"; 
     2608 
     2609        app << setprecision(4); 
     2610 
     2611        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n"; 
     2612 
     2613        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n"; 
     2614 
     2615        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n"; 
     2616 
     2617        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n"; 
     2618 
     2619        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n"; 
     2620 
     2621        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n"; 
     2622        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n"; 
     2623 
     2624        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n"; 
     2625 
     2626        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n"; 
     2627 
     2628        app << "===== END OF BspTree statistics ==========\n"; 
     2629} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

    r483 r485  
    2121class ViewCellsStatistics; 
    2222class ViewCellsManager; 
     23class BspMergeCandidate; 
     24struct BspRay; 
    2325 
    2426 
     
    222224        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false); 
    223225 
    224         /** Returns view cell corresponding to unbounded space. 
    225         */ 
    226         BspViewCell *GetRootCell() const; 
    227  
    228226        /** Returns epsilon of this tree. 
    229227        */ 
    230228        float GetEpsilon() const; 
    231229 
    232  
     230        /** Casts line segment into the tree. 
     231                @param origin the origin of the line segment 
     232                @param termination the end point of the line segment 
     233                @returns view cells intersecting the line segment. 
     234        */ 
    233235    int CastLineSegment(const Vector3 &origin, 
    234236                                                const Vector3 &termination, 
    235237                                                ViewCellContainer &viewcells); 
    236238 
    237         /** Merges leaves with similar PVS. 
    238         */ 
    239         int MergeLeaves(); 
    240239                 
    241240        /** Sets pointer to view cells manager. 
     
    243242        void SetViewCellsManager(ViewCellsManager *vcm); 
    244243 
    245         /** Helper function revalidating the view cell leaf list after merge. 
    246         */ 
    247         void RepairVcLeafLists(); 
    248  
    249         /** Collapses the tree with respect to the view cell partition. 
    250                 @returns node of type leaf if the node could be collapsed, this node otherwise 
     244        /** Returns distance from node 1 to node 2. 
     245        */ 
     246        int TreeDistance(BspNode *n1, BspNode *n2) const; 
     247 
     248        /** Merges view cells according to some cost heuristics. 
     249        */ 
     250        int MergeViewCells(const VssRayContainer &rays); 
     251         
     252        /** Refines view cells using shuffling, i.e., border leaves  
     253                of two view cells are exchanged if the resulting view cells 
     254                are tested to be "better" than the old ones. 
     255                @returns number of refined view cells 
     256        */ 
     257        int RefineViewCells(const VssRayContainer &rays); 
     258 
     259        /** Collapses the tree with respect to the view cell partition, 
     260                i.e. leaves having the same view cell are collapsed. 
     261                @returns node of type leaf if the node could be collapsed,  
     262                this node otherwise 
    251263        */ 
    252264        BspNode *CollapseTree(BspNode *node); 
    253          
    254  
    255         /** Returns distance from node 1 to node 2. 
    256         */ 
    257         int TreeDistance(BspNode *n1, BspNode *n2); 
     265 
     266        /** Constructs bsp rays for post processing and visualization. 
     267        */ 
     268        void ConstructBspRays(vector<BspRay *> &bspRays, 
     269                                                  const VssRayContainer &rays); 
     270 
     271         
     272        /** Merge view cells of leaves l1 and l2. 
     273        */ 
     274        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2) const; 
    258275 
    259276protected: 
     
    286303        }; 
    287304 
     305        /** Shuffles the leaves, i.e., tests if exchanging 
     306                the leaves helps in improving the view cells. 
     307        */ 
     308        bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const; 
     309 
     310        /** Helper function revalidating the view cell leaf list after merge. 
     311        */ 
     312        void RepairVcLeafLists(); 
     313 
    288314        /** Evaluates tree stats in the BSP tree leafs. 
    289315        */ 
     
    478504 
    479505 
     506        /** Collects candidates for the merge in the merge queue. 
     507                @returns number of leaves in queue 
     508        */ 
     509        int CollectMergeCandidates(); 
     510        /** Collects candidates for the merge in the merge queue. 
     511                @returns number of leaves in queue 
     512        */ 
     513        int CollectMergeCandidates(const VssRayContainer &rays); 
     514 
    480515        /** Take 3 ray endpoints, where two are minimum and one a maximum 
    481516                point or the other way round. 
     
    484519 
    485520        /** Take plane normal as plane normal and the midpoint of the ray. 
    486                 PROBLEM: does not resemble any point where visibility is likely to change 
     521                PROBLEM: does not resemble any point where visibility is  
     522                likely to change 
    487523        */ 
    488524        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const; 
    489525 
    490         /** Fit the plane between the two lines so that the plane has equal shortest  
    491                 distance to both lines. 
     526        /** Fit the plane between the two lines so that the plane  
     527                has equal shortest distance to both lines. 
    492528        */ 
    493529        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const; 
    494530   
    495         /** Merge view cells of leaves l1 and l2. 
    496         */ 
    497         bool MergeViewCells(BspLeaf *l1, BspLeaf *l2); 
     531        void ShuffleLeaf(BspLeaf *leaf,  
     532                                         BspViewCell *vc1,  
     533                                         BspViewCell *vc2) const; 
    498534 
    499535        /// Pointer to the root of the tree 
     
    513549        /// box around the whole view domain 
    514550        AxisAlignedBox3 mBox; 
    515  
    516         /// view cell corresponding to unbounded space 
    517         BspViewCell *mRootCell; 
    518551 
    519552        /// minimal number of rays before subdivision termination 
     
    574607        float mMergeMaxCostRatio; 
    575608 
    576         ViewCellsManager *mViewCellsManager; 
    577  
    578609        // if rays should be stored in leaves 
    579610        bool mStoreRays; 
     611         
     612        /// if only driving axis should be used for split 
     613        bool mOnlyDrivingAxis; 
     614 
     615        ViewCellsManager *mViewCellsManager; 
    580616 
    581617        vector<SortableEntry> *mSplitCandidates; 
    582618 
    583         bool mOnlyDrivingAxis; 
    584  
     619        typedef priority_queue<BspMergeCandidate> MergeQueue; 
     620        MergeQueue mMergeQueue; 
     621         
     622        bool mUseRaysForMerge; 
    585623 
    586624private: 
     
    646684 
    647685protected: 
    648          
     686 
     687        /** Cost of a view cell. 
     688        */ 
     689        float GetCost(ViewCell *vc) const; 
    649690        /** Evaluates the merge costs of the leaves. 
    650691        */ 
     
    661702 
    662703 
     704class MergeStatistics: public StatisticsBase 
     705{ 
     706public: 
     707         
     708        int merged; 
     709        int siblings; 
     710        int candidates; 
     711        int nodes; 
     712 
     713        int accTreeDist; 
     714        int maxTreeDist; 
     715         
     716        Real collectTime; 
     717        Real mergeTime; 
     718 
     719        // Constructor 
     720        MergeStatistics()  
     721        { 
     722                Reset(); 
     723        } 
     724         
     725        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;};  
     726 
     727        void Reset()  
     728        { 
     729                nodes = 0; 
     730                merged = 0; 
     731                siblings = 0; 
     732                candidates = 0; 
     733         
     734                accTreeDist = 0; 
     735                maxTreeDist = 0; 
     736 
     737                collectTime = 0; 
     738                mergeTime = 0; 
     739        } 
     740 
     741        void Print(ostream &app) const; 
     742 
     743        friend ostream &operator<<(ostream &s, const MergeStatistics &stat)  
     744        { 
     745                stat.Print(s); 
     746                return s; 
     747        }  
     748}; 
     749 
    663750#endif 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

    r483 r485  
    372372                                                         MergeCandidate::sMaxPvsSize); 
    373373 
    374         // split type 
    375         char sname[128]; 
    376         environment->GetStringValue("VspKdTree.splitType", sname); 
    377         string name(sname); 
    378  
     374        environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); 
     375 
     376        //-- output 
    379377        Debug << "======= vsp kd tree options ========" << endl; 
    380378        Debug << "max depth: "<< mTermMaxDepth << endl; 
     
    385383        Debug << "min size: " << mTermMinSize << endl; 
    386384 
     385        Debug << "split type: "; 
     386 
     387        //-- split type 
     388        char sname[128]; 
     389        environment->GetStringValue("VspKdTree.splitType", sname); 
     390        string name(sname); 
     391 
    387392        if (name.compare("regular") == 0) 
    388393        { 
    389                 Debug << "using regular split" << endl; 
     394                Debug << "regular split" << endl; 
    390395                splitType = ESplitRegular; 
    391396        } 
     
    394399                if (name.compare("heuristic") == 0) 
    395400                { 
    396                         Debug << "using heuristic split" << endl; 
     401                        Debug << "heuristic split" << endl; 
    397402                        splitType = ESplitHeuristic; 
    398403                } 
     
    405410 
    406411        mRoot = NULL; 
    407  
    408412        mSplitCandidates = new vector<SortableEntry>; 
    409413} 
     
    14641468        { 
    14651469            // determine the side of this ray with respect to the plane 
    1466  float t; 
    1467  int side = in->ComputeRayIntersection(data.mRayData, t); 
     1470                float t; 
     1471                const int side = in->ComputeRayIntersection(data.mRayData, t); 
    14681472 
    14691473                if (side == 0) 
     
    20502054                        } 
    20512055 
    2052                         if (1) //matt TODO: REMOVE LATER 
     2056                        if (0) //matt TODO: REMOVE LATER 
    20532057                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0))); 
    20542058 
     
    21622166        { 
    21632167                VspKdLeaf *leaf = *it; 
    2164  
     2168                ViewCell *vc = leaf->GetViewCell(); 
    21652169                // no leaf is part of two merge candidates 
    2166                 if (!leaf->Mailed()) 
    2167                 { 
    2168                         leaf->Mail(); 
    2169  
    2170                         vector<VspKdLeaf *> neighbors; 
    2171                         FindNeighbors(leaf, neighbors, true); 
    2172  
    2173                         vector<VspKdLeaf *>::const_iterator nit, 
    2174                                 nit_end = neighbors.end(); 
    2175  
    2176                         for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
    2177                         { 
    2178                                 // TODO: test if at least one ray goes from one leaf to the other 
    2179                                 MergeCandidate mc = MergeCandidate(leaf, *nit); 
    2180                                 mMergeQueue.push(mc); 
    2181  
    2182                                 MergeCandidate::sOverallCost += mc.GetLeaf1Cost(); 
    2183                                 MergeCandidate::sOverallCost += mc.GetLeaf2Cost(); 
    2184                         } 
    2185                 } 
    2186         } 
    2187 } 
    2188  
    2189 /* 
     2170                leaf->Mail(); 
     2171                MergeCandidate::sOverallCost +=  
     2172                        vc->GetVolume() * vc->GetPvs().GetSize(); 
     2173                vector<VspKdLeaf *> neighbors; 
     2174                FindNeighbors(leaf, neighbors, true); 
     2175 
     2176                vector<VspKdLeaf *>::const_iterator nit, 
     2177                        nit_end = neighbors.end(); 
     2178 
     2179                for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
     2180                { 
     2181                        mMergeQueue.push(MergeCandidate(leaf, *nit)); 
     2182                } 
     2183        } 
     2184} 
     2185#if 0 
    21902186void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays) 
    21912187{ 
     
    21932189 
    21942190        vector<VspKdIntersection>::const_iterator iit; 
     2191        map<BspLeaf *, vector<BspLeaf*> candidateMap; 
    21952192 
    21962193        for (int i = 0; i < (int)rays.size(); ++ i) 
    21972194        {   
    21982195                //VspKdLeaf::NewMail(); 
    2199  
    22002196                VspKdRay *ray = rays[i]; 
    22012197           
     
    22142210                { 
    22152211            BspLeaf *leaf = (*iit).mLeaf; 
    2216                          
     2212                        leaf->Mail 
    22172213                        // TODO: how to sort out doubles? 
    22182214                        MergeCandidate mc = MergeCandidate(leaf, previousLeaf); 
     
    22262222        } 
    22272223} 
    2228 */ 
    2229  
    2230 int VspKdTree::MergeLeaves() 
    2231 { 
     2224#endif 
     2225 
     2226int VspKdTree::MergeViewCells(const VssRayContainer &rays) 
     2227{ 
     2228        CollectMergeCandidates(); 
     2229 
    22322230        int merged = 0; 
    22332231 
    2234         int vcSize = mStat.nodes / 2 + 1; 
     2232        int vcSize = mStat.Leaves(); 
    22352233        // use priority queue to merge leaves 
    22362234        while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) && 
     
    22382236                    mMergeMaxCostRatio * MergeCandidate::sOverallCost)) 
    22392237        { 
    2240                 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
     2238                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() /  
     2239                //MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl; 
    22412240                MergeCandidate mc = mMergeQueue.top(); 
    22422241                mMergeQueue.pop(); 
     
    22672266        } 
    22682267 
    2269         // collapse siblings belonging to the same view cell 
    2270         CollapseTree(mRoot); 
    2271         // revalidate leaves 
    2272         RepairVcLeafLists(); 
    2273  
    2274         Debug << "merged " << merged << " of " << mStat.nodes / 2 + 1 << " leaves" << endl; 
     2268        Debug << "merged " << merged << " of " << mStat.Leaves() << " leaves" << endl; 
    22752269 
    22762270        //TODO: should return sample contributions 
     
    23502344        } 
    23512345 
     2346        // revalidate leaves 
     2347        RepairVcLeafLists(); 
     2348 
    23522349        return node; 
    23532350} 
     
    23562353void VspKdTree::RefineViewCells() 
    23572354{ 
     2355        //TODO 
    23582356} 
    23592357 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

    r483 r485  
    285285        */ 
    286286        void SetupChildLinks(VspKdNode *b, VspKdNode *f); 
    287  
    288287        /** Replaces the pointer to oldChild with a pointer to newChild. 
    289288        */ 
    290289        void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild); 
    291   
    292290        /** Computes intersection of the ray with the node boundaries. 
    293291        */ 
     
    568566        */ 
    569567        float GetMemUsage() const; 
    570          
     568        //? 
    571569        float GetRayMemUsage() const; 
    572570 
     
    575573        void CollectLeaves(vector<VspKdLeaf *> &leaves) const; 
    576574 
    577         /** Merges leaves of this tree according to some criteria. 
    578         */ 
    579         int MergeLeaves(); 
     575        /** Merges view cells created with this tree according to  
     576                some (global) cost heuristics. 
     577        */ 
     578        int MergeViewCells(const VssRayContainer &rays); 
    580579 
    581580        /** Finds neighbours of this node. 
     
    604603        */ 
    605604        void CollectViewCells(ViewCellContainer &viewCells) const; 
    606  
    607605        /** Refines view cells in a post processing step. 
    608606        */ 
     
    612610        */ 
    613611        void CollectMergeCandidates(); 
     612 
     613        /** Collapses the tree with respect to the view cell partition. 
     614                @returns node of type leaf if the node could be collapsed, this node otherwise 
     615        */ 
     616        VspKdNode *CollapseTree(VspKdNode *node); 
    614617 
    615618protected: 
     
    718721        */ 
    719722        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2); 
    720  
    721         /** Collapses the tree with respect to the view cell partition. 
    722                 @returns node of type leaf if the node could be collapsed, this node otherwise 
    723         */ 
    724         VspKdNode *CollapseTree(VspKdNode *node); 
    725723         
    726724        /** Helper function revalidating the view cell leaf list after merge. 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r475 r485  
    558558 
    559559        //-- several visualizations and statistics 
    560         Debug << "view cells after post processing: " << endl; 
     560        Debug << "\nview cells after post processing: " << endl; 
    561561        mViewCellsManager->PrintStatistics(Debug); 
    562562 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp

    r473 r485  
    558558#if 1 
    559559        float newCost = raysBack*pvsBack  + raysFront*pvsFront; 
    560         float oldCost = leaf->rays.size()*pvsSize; 
     560        float oldCost = (float)leaf->rays.size()*pvsSize; 
    561561        ratio = newCost/oldCost; 
    562562#else 
Note: See TracChangeset for help on using the changeset viewer.