Changeset 1006 for GTP/trunk/Lib/Vis


Ignore:
Timestamp:
06/09/06 01:26:46 (19 years ago)
Author:
mattausch
Message:

started viewspace-objectspace subdivision
removed memory leaks

Location:
GTP/trunk/Lib/Vis
Files:
28 edited

Legend:

Unmodified
Added
Removed

  • GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj

    r1004 r1006  
    158158                        </File> 
    159159                        <File 
    160                                 RelativePath="..\src\FromPointVisibilityTree.cpp"> 
    161                         </File> 
    162                         <File 
    163                                 RelativePath="..\src\FromPointVisibilityTree.h"> 
    164                         </File> 
    165                         <File 
    166160                                RelativePath="..\src\glInterface.h"> 
    167161                        </File> 
    … …  
    176170                                                Name="VCCustomBuildTool" 
    177171                                                Description="Performing moc on $(InputName).h" 
    178                                                 CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp&#xA;" 
     172                                                CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp 
     173" 
    179174                                                Outputs="$(InputDir)moc_$(InputName).cpp"/> 
    180175                                </FileConfiguration> 
    … …  
    307302                                                Name="VCCustomBuildTool" 
    308303                                                Description="Performing moc on $(InputName).h" 
    309                                                 CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp&#xA;" 
     304                                                CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp 
     305" 
    310306                                                Outputs="$(InputDir)moc_$(InputName).cpp"/> 
    311307                                </FileConfiguration> 
    … …  
    321317                                                Name="VCCustomBuildTool" 
    322318                                                Description="Performing moc on $(InputName).h" 
    323                                                 CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp&#xA;" 
     319                                                CommandLine="%qtdir%\bin\moc.exe $(InputDir)$(InputName).h -o $(InputDir)moc_$(InputName).cpp 
     320" 
    324321                                                Outputs="$(InputDir)moc_$(InputName).cpp"/> 
    325322                                </FileConfiguration> 
    … …  
    461458                        </File> 
    462459                        <File 
    463                                 RelativePath="..\src\VspKdTree.cpp"> 
    464                         </File> 
    465                         <File 
    466                                 RelativePath="..\src\VspKdTree.h"> 
     460                                RelativePath="..\src\VspOspTree.cpp"> 
     461                        </File> 
     462                        <File 
     463                                RelativePath="..\src\VspOspTree.h"> 
    467464                        </File> 
    468465                        <File 

  • GTP/trunk/Lib/Vis/Preprocessing/src/AxisAlignedBox3.cpp

    r863 r1006  
    21232123} 
    21242124 
    2125 } 
     2125void AxisAlignedBox3::Split(const int axis,  
     2126                                                        const float value,  
     2127                                                        AxisAlignedBox3 &left,  
     2128                                                        AxisAlignedBox3 &right) 
     2129{ 
     2130        if ( (value >= mMin[axis]) && (value <= mMax[axis]) ) 
     2131        { 
     2132                left.mMin = mMin; left.mMax = mMax; 
     2133                right.mMin = mMin; right.mMax = mMax; 
     2134 
     2135                left.mMax[axis] = value; 
     2136                right.mMin[axis] = value; 
     2137 
     2138        } 
     2139} 
     2140} 

  • GTP/trunk/Lib/Vis/Preprocessing/src/AxisAlignedBox3.h

    r870 r1006  
    101101        mMax[axis] = value; 
    102102  } 
    103          
     103 
     104   
     105 
    104106  // the size of the box along all the axes 
    105107  Vector3 Size() const { return mMax - mMin; } 
    … …  
    389391  void ExtractPolys(PolygonContainer &polys) const; 
    390392 
     393  /** Splits the box into two separate boxes according to the split plane 
     394  */ 
     395  void Split(const int axis, const float value, AxisAlignedBox3 &left, AxisAlignedBox3 &right); 
     396 
    391397#define __EXTENT_HACK 
    392398  // get the extent of face 

  • GTP/trunk/Lib/Vis/Preprocessing/src/BoundingBoxConverter.h

    r939 r1006  
    66namespace GtpVisibilityPreprocessor { 
    77 
    8 /** helper struct used for identifying objects with similar bounding boxes. 
     8/** helper struct used to identify objects with similar bounding boxes. 
    99*/ 
    1010struct IndexedBoundingBox: public std::pair<int, AxisAlignedBox3> 

  • GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp

    r1004 r1006  
    13741374                                        "boxes.out"); 
    13751375 
    1376         RegisterOption("ViewCells.PostProcess.emptyViewCellsMerge", 
    1377                                         optBool, 
    1378                                         "view_cells_merge_empty=", 
    1379                                         "true"); 
    1380  
    13811376        RegisterOption("ViewCells.evaluateViewCells", 
    13821377                                        optBool, 
    … …  
    17391734 
    17401735 
    1741         /**************************************************************************************/ 
    1742         /*                  View space partition KD tree related options                      */ 
    1743         /**************************************************************************************/ 
    1744  
    1745         RegisterOption("VspKdTree.Construction.samples", 
    1746                                         optInt, 
    1747                                         "vsp_kd_construction_samples=", 
    1748                                         "100000"); 
    1749  
    1750         RegisterOption("VspKdTree.Termination.maxDepth",  
    1751                 optInt,  
    1752                 "vsp_term_maxdepth=",  
    1753                 "30"); 
    1754  
    1755         RegisterOption("VspKdTree.Termination.minPvs",  
    1756                 optInt,  
    1757                 "vsp_minpvs=",  
    1758                 "1"); 
    1759  
    1760         RegisterOption("VspKdTree.Termination.minRays",  
    1761                 optInt,  
    1762                 "vsp_term_minrays=",  
    1763                 "10"); 
    1764  
    1765         RegisterOption("VspKdTree.Termination.minSize",  
    1766                 optFloat,  
    1767                 "vsp_term_minsize=",  
    1768                 "0.001"); 
    1769  
    1770         RegisterOption("VspKdTree.Termination.maxCostRatio",  
    1771                 optFloat,  
    1772                 "vsp_term_maxcost=", 
    1773                 "0.95"); 
    1774  
    1775         RegisterOption("VspKdTree.Termination.maxRayContribution",  
    1776                 optFloat,  
    1777                 "vsp_term_max_ray_contrib=",  
    1778                 "0.5"); 
    1779  
    1780         RegisterOption("VspKdTree.epsilon",  
    1781                 optFloat,  
    1782                 "kd_eps=",  
    1783                 "1e-6"); 
    1784  
    1785         RegisterOption("VspKdTree.ct_div_ci",  
    1786                 optFloat,  
    1787                 "vsp_ctdivci=", "1.0"); 
    1788  
    1789         RegisterOption("VspKdTree.splitType",  
    1790                 optString,  
    1791                 "split=",  
    1792                 "queries"); 
    1793  
    1794         RegisterOption("VspKdTree.splitAxis",  
    1795                 optString,  
    1796                 "split=",  
    1797                 "drivingAxis"); 
    1798  
    1799         RegisterOption("VspKdTree.splitUseOnlyDrivingAxis",  
    1800                 optBool,  
    1801                 "vsp_kd_splitdriving=",  
    1802                 "false"); 
    1803  
    1804         RegisterOption("VspKdTree.numberOfEndPointDomains",  
    1805                 optInt,  
    1806                 "endpoints=",  
    1807                 "10000"); 
    1808  
    1809         RegisterOption("VspKdTree.maxTotalMemory",  
    1810                 optFloat,  
    1811                 "vsp_max_total_mem=",  
    1812                 "60.0"); 
    1813  
    1814         RegisterOption("VspKdTree.maxStaticMemory",  
    1815                 optFloat,  
    1816                 "vsp_max_static_mem=",  
    1817                 "8.0"); 
    1818  
    1819         RegisterOption("VspKdTree.queryType",  
    1820                 optString,  
    1821                 "qtype=",  
    1822                 "static"); 
    1823  
    1824         RegisterOption("VspKdTree.queryPosWeight",  
    1825                 optFloat,  
    1826                 "vsp_kd_qposweight=",  
    1827                 "0.0"); 
    1828  
    1829         RegisterOption("VspKdTree.accessTimeThreshold",  
    1830                 optInt,  
    1831                 "vsp_kd_accesstime=",  
    1832                 "1000"); 
    1833  
    1834         RegisterOption("VspKdTree.minCollapseDepth",  
    1835                 optInt,  
    1836                 "vsp_kd_min_colldepth=",  
    1837                 "4"); 
    1838  
    1839         RegisterOption("VspKdTree.PostProcess.maxCostRatio", 
    1840                         optFloat, 
    1841                         "vsp_kd_post_process_max_cost_ratio=", 
    1842                         "0.9"); 
    1843  
    1844         RegisterOption("VspKdTree.PostProcess.minViewCells",  
    1845                 optInt,  
    1846                 "vsp_kd_term_post_process_min_view_cells=",  
    1847                 "1000"); 
    1848  
    1849         RegisterOption("VspKdTree.Termination.maxViewCells",  
    1850                 optInt,  
    1851                 "vsp_kd_term_post_process_min_view_cells=",  
    1852                 "300"); 
    1853  
    1854         RegisterOption("VspKdTree.PostProcess.maxPvsSize",  
    1855                 optInt,  
    1856                 "vsp_kd_term_post_process_max_pvs_size=",  
    1857                 "100"); 
    1858  
    1859         RegisterOption("VspKdTree.Termination.missTolerance", 
    1860                         optInt, 
    1861                         "vsp_kd_term_miss_tolerance=", 
    1862                         "4"); 
    1863  
    18641736        /************************************************************************************/ 
    18651737        /*                   VSS Preprocessor cells related options                         */ 

  • GTP/trunk/Lib/Vis/Preprocessing/src/Exporter.h

    r863 r1006  
    1616class KdTree; 
    1717class BspTree; 
    18 class VspKdTree; 
    1918class SceneGraphNode; 
    2019class Ray; 
    … …  
    6463                                 const Vector3 direction 
    6564                                 ) = 0; 
    66  
    67   virtual bool 
    68   ExportVspKdTree(const VspKdTree &tree, const int maxPvs = 0) = 0; 
    6965 
    7066  virtual bool 

  • GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.cpp

    r1004 r1006  
    124124        Environment::GetSingleton()->GetIntValue("FromPointVisibilityTree.nodePriorityQueueType", mNodePriorityQueueType); 
    125125 
    126         Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed); 
    127126         
    128127        char subdivisionStatsLog[100]; 
    … …  
    160159        Debug << "use random axis: " << mUseRandomAxis << endl; 
    161160        Debug << "priority queue type: " << mNodePriorityQueueType << endl; 
    162         Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl; 
     161         
    163162        Debug << "octree: " << mCirculatingAxis << endl; 
    164163        Debug << "minband: " << mMinBand << endl; 
    … …  
    37073706                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell()); 
    37083707 
    3709                                 // dont't merge view cells if they are empty and not front and back leaf of the same parent 
    3710                                 // in the tree? 
    3711                                 if (mEmptyViewCellsMergeAllowed || 
    3712                                         !leaf->GetViewCell()->GetPvs().Empty() ||  
     3708                                if (!leaf->GetViewCell()->GetPvs().Empty() ||  
    37133709                                        !(*nit)->GetViewCell()->GetPvs().Empty() || 
    37143710                    leaf->IsSibling(*nit)) 

  • GTP/trunk/Lib/Vis/Preprocessing/src/FromPointVisibilityTree.h

    r1002 r1006  
    827827        int mNodePriorityQueueType; 
    828828 
    829         bool mEmptyViewCellsMergeAllowed; 
    830  
    831829        // priority queue strategy 
    832830        enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED}; 
     831 
     832 
    833833private: 
    834834 

  • GTP/trunk/Lib/Vis/Preprocessing/src/GlRenderer.h

    r1004 r1006  
    281281  signals: 
    282282   
    283   SetViewCellGranularity(int); 
    284   SetSceneCut(int); 
    285   SetTopDistance(int); 
    286   SetVisibilityFilterSize(int); 
    287   SetSpatialFilterSize(int); 
    288  
    289   SetRenderFilter(bool); 
    290   SetUseFilter(bool); 
    291   SetUseSpatialFilter(bool); 
    292   SetRenderErrors(bool); 
    293   SetShowViewCells(bool); 
    294   SetShowRenderCost(bool); 
    295   SetShowPvsSizes(bool); 
    296   SetTopView(bool); 
    297   SetCutViewCells(bool); 
    298   SetCutScene(bool); 
     283  void SetViewCellGranularity(int); 
     284  void SetSceneCut(int); 
     285  void SetTopDistance(int); 
     286  void SetVisibilityFilterSize(int); 
     287  void SetSpatialFilterSize(int); 
     288 
     289  void SetRenderFilter(bool); 
     290  void SetUseFilter(bool); 
     291  void SetUseSpatialFilter(bool); 
     292  void SetRenderErrors(bool); 
     293  void SetShowViewCells(bool); 
     294  void SetShowRenderCost(bool); 
     295  void SetShowPvsSizes(bool); 
     296  void SetTopView(bool); 
     297  void SetCutViewCells(bool); 
     298  void SetCutScene(bool); 
    299299 
    300300   

  • GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp

    r1004 r1006  
    99#include "ViewCellBsp.h" 
    1010#include "VspBspTree.h" 
    11 #include "VspKdTree.h" 
    1211#include "RenderSimulator.h" 
    1312#include "GlRenderer.h" 
    … …  
    113112mKdTree(NULL), 
    114113mBspTree(NULL), 
    115 mVspKdTree(NULL), 
    116114mVspBspTree(NULL), 
    117115mViewCellsManager(NULL), 
    … …  
    158156  DEL_PTR(mKdTree); 
    159157  cout << "done.\n"; 
    160    
    161   cout << "Deleting vspkd tree...\n"; 
    162   DEL_PTR(mVspKdTree); 
     158  
     159#if 0 
     160  cout << "Deleting vsp osp tree...\n"; 
     161  DEL_PTR(mVspOspTree); 
    163162  cout << "done.\n"; 
     163#endif 
    164164 
    165165  cout << "Deleting vspbsp tree...\n"; 
    … …  
    424424                mViewCellsManager = new VspBspViewCellsManager(mVspBspTree); 
    425425        } 
    426         else if (strcmp(name, "vspKdTree") == 0) 
    427         { 
    428                 mVspKdTree = new VspKdTree();            
    429          
    430                 mViewCellsManager = new VspKdViewCellsManager(mVspKdTree); 
    431         } 
     426#if 0 
     427        else if (strcmp(name, "vspOspTree") == 0) 
     428        { 
     429                mVspOspTree = new VspOspTree();          
     430                mViewCellsManager = new VspOspViewCellsManager(mVspOspTree); 
     431        } 
     432#endif 
    432433        else if (strcmp(name, "sceneDependent") == 0) 
    433434        { 

  • GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.h

    r904 r1006  
    1717class ViewCellsManager; 
    1818class BspTree; 
    19 class VspKdTree; 
     19class VspOspTree; 
    2020class VspBspTree; 
    2121class RenderSimulator; 
    … …  
    151151  ViewCellsManager *mViewCellsManager; 
    152152 
    153   /** Kd tree inducing a coarse partition of view space that are the building 
    154           blocks for view cells. 
    155   */ 
    156   VspKdTree *mVspKdTree; 
     153  /// greedy optimized hierarchy for both objects and view cells 
     154  VspOspTree *mVspOspTree; 
    157155 
    158156  bool mUseGlRenderer; 
    … …  
    183181  /// samples used for construction of the BSP view cells tree. 
    184182  int mBspConstructionSamples; 
    185    /// samples used for construction of the VSP KD tree. 
    186   int mVspKdConstructionSamples; 
     183  /// samples used for construction of the VSP OSP tree. 
     184  int mVspOspConstructionSamples; 
    187185  /** Simulates rendering of the scene. 
    188186  */ 

  • GTP/trunk/Lib/Vis/Preprocessing/src/RenderSimulator.cpp

    r863 r1006  
    44#include "ViewCell.h" 
    55#include "VspBspTree.h" 
    6 #include "VspKdTree.h" 
    76#include "ViewCellsManager.h" 
    87 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h

    r1004 r1006  
    1717class BspPvs; 
    1818class BspLeaf; 
    19 class VspKdTree; 
    2019class VspKdLeaf; 
    2120class KdLeaf; 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellBsp.h

    r882 r1006  
    323323}; 
    324324 
     325 
    325326/** BSP interior node implementation  
    326327*/ 
    … …  
    366367        BspNode *mFront; 
    367368}; 
     369 
    368370 
    369371/** BSP leaf node implementation. 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

    r1004 r1006  
    88#include "ViewCellBsp.h" 
    99#include "KdTree.h" 
    10 #include "VspKdTree.h" 
     10//#include "VspOspTree.h" 
    1111#include "Exporter.h" 
    1212#include "VspBspTree.h" 
    … …  
    18281828        Vector3 termination = hray.Extrap(tmax); 
    18291829 
     1830        // traverse the view space subdivision 
    18301831        CastLineSegment(origin, termination, viewcells); 
    18311832 
    1832         // copy viewcells memory efficiently 
    18331833        //const bool storeViewcells = !addRays; 
    1834  
     1834//return 0; 
    18351835        if (storeViewCells) 
    18361836        { 
     1837                // copy viewcells memory efficiently 
    18371838                ray.mViewCells.reserve(viewcells.size()); 
    18381839                ray.mViewCells = viewcells; 
    … …  
    20902091        } 
    20912092 
    2092  
    20932093        return true; 
    20942094} 
    … …  
    21732173 
    21742174 
    2175 void ViewCellsManager::SetScalarPvsSize(ViewCell *vc, const int pvsSize) const 
     2175void ViewCellsManager::SetScalarPvsSize(ViewCell *vc,  
     2176                                                                                const int pvsSize) const 
    21762177{ 
    21772178        vc->mPvsSize = pvsSize; 
    … …  
    33463347} 
    33473348 
    3348  
    3349 /**********************************************************************/ 
    3350 /*                   VspKdViewCellsManager implementation             */ 
    3351 /**********************************************************************/ 
    3352  
    3353  
    3354 VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree): 
    3355 ViewCellsManager(), mVspKdTree(vspKdTree) 
    3356 { 
    3357         Environment::GetSingleton()->GetIntValue("VspKdTree.Construction.samples", mInitialSamples); 
    3358         mVspKdTree->SetViewCellsManager(this); 
    3359 } 
    3360  
    3361 float VspKdViewCellsManager::GetProbability(ViewCell *viewCell) 
    3362 { 
    3363         // compute view cell area / volume as subsititute for probability 
    3364         if (0) 
    3365                 return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea(); 
    3366         else 
    3367                 return GetVolume(viewCell) / GetViewSpaceBox().GetVolume(); 
    3368 } 
    3369  
    3370  
    3371  
    3372  
    3373 void VspKdViewCellsManager::CollectViewCells() 
    3374 { 
    3375         mVspKdTree->CollectViewCells(mViewCells); 
    3376 } 
    3377  
    3378  
    3379 int VspKdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects, 
    3380                                                                                                 const VssRayContainer &rays) 
    3381 { 
    3382         // if view cells already constructed 
    3383         if (ViewCellsConstructed()) 
    3384                 return 0; 
    3385  
    3386         VssRayContainer constructionRays; 
    3387         VssRayContainer savedRays; 
    3388  
    3389         GetRaySets(rays, 
    3390                            mInitialSamples, 
    3391                            constructionRays, 
    3392                            &savedRays); 
    3393  
    3394         Debug << "constructing vsp kd tree using " 
    3395                   << (int)constructionRays.size() << " samples" << endl; 
    3396  
    3397         mVspKdTree->Construct(constructionRays, &mViewSpaceBox); 
    3398         Debug << mVspKdTree->GetStatistics() << endl; 
    3399  
    3400         // export leaf building blocks 
    3401         ExportLeaves(objects, rays); 
    3402  
    3403         // finally merge kd leaf building blocks to view cells 
    3404         const int merged = mVspKdTree->MergeViewCells(rays); 
    3405  
    3406         // collapse siblings belonging to the same view cell 
    3407         mVspKdTree->RefineViewCells(rays); 
    3408  
    3409         // collapse siblings belonging to the same view cell 
    3410         mVspKdTree->CollapseTree(); 
    3411  
    3412         // evaluale view cell stats 
    3413         ResetViewCells(); 
    3414  
    3415         Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl; 
    3416  
    3417         long startTime = GetTime(); 
    3418  
    3419         // recast rest of rays 
    3420         ComputeSampleContributions(savedRays, true, false); 
    3421  
    3422         Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
    3423                   << " secs" << endl; 
    3424  
    3425         return merged; 
    3426 } 
    3427  
    3428 bool VspKdViewCellsManager::ViewCellsConstructed() const 
    3429 { 
    3430         return mVspKdTree->GetRoot() != NULL; 
    3431 } 
    3432  
    3433  
    3434 ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const 
    3435 { 
    3436         return new VspKdViewCell(mesh); 
    3437 } 
    3438  
    3439 int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects, 
    3440                                                                            const VssRayContainer &rays) 
    3441 { 
    3442         if (!ViewCellsConstructed()) 
    3443                 return 0; 
    3444  
    3445         // recalculate stats 
    3446         EvaluateViewCellsStats(); 
    3447  
    3448         return 0; 
    3449 } 
    3450  
    3451  
    3452 void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects, 
    3453                                                                                  const VssRayContainer &sampleRays) 
    3454 { 
    3455         if (!ViewCellsConstructed()) 
    3456                 return; 
    3457  
    3458         //-- export leaf building blocks 
    3459         Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 
    3460         if (!exporter) 
    3461                 return; 
    3462  
    3463         if (mExportGeometry) 
    3464                 exporter->ExportGeometry(objects); 
    3465          
    3466         //exporter->SetWireframe(); 
    3467         //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize); 
    3468         exporter->ExportVspKdTree(*mVspKdTree); 
    3469  
    3470         if (mExportRays) 
    3471         { 
    3472                 const float prob = (float)mVisualizationSamples 
    3473                         / ((float)sampleRays.size() + Limits::Small); 
    3474  
    3475                 exporter->SetWireframe(); 
    3476  
    3477                 //-- collect uniformly distributed rays 
    3478                 VssRayContainer rays; 
    3479  
    3480                 for (int i = 0; i < sampleRays.size(); ++ i) 
    3481                 { 
    3482                         if (RandomValue(0,1) < prob) 
    3483                                 rays.push_back(sampleRays[i]); 
    3484                 } 
    3485                 exporter->ExportRays(rays, RgbColor(1, 0, 0)); 
    3486         } 
    3487  
    3488         delete exporter; 
    3489 } 
    3490  
    3491  
    3492 void VspKdViewCellsManager::Visualize(const ObjectContainer &objects, 
    3493                                                                           const VssRayContainer &sampleRays) 
    3494 { 
    3495         if (!ViewCellsConstructed()) 
    3496                 return; 
    3497  
    3498         //-- export single view cells 
    3499         for (int i = 0; i < 10; ++ i) 
    3500         { 
    3501                 char s[64]; 
    3502                 sprintf(s, "vsp_viewcell%04d.x3d", i); 
    3503                 Exporter *exporter = Exporter::GetExporter(s); 
    3504                 const int idx = 
    3505                         (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1)); 
    3506  
    3507                 VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]); 
    3508  
    3509                 //-- export geometry 
    3510                 Material m; 
    3511                 m.mDiffuseColor = RgbColor(0, 1, 1); 
    3512  
    3513                 exporter->SetForcedMaterial(m); 
    3514                 exporter->SetWireframe(); 
    3515  
    3516                 ExportViewCellGeometry(exporter, vc); 
    3517  
    3518                 //-- export stored rays 
    3519                  
    3520                 if (mExportRays) 
    3521                 { 
    3522                         ViewCellContainer leaves; 
    3523                         mViewCellsTree->CollectLeaves(vc, leaves); 
    3524  
    3525                         ViewCellContainer::const_iterator it, 
    3526                                 it_end = leaves.end(); 
    3527  
    3528                         for (it = leaves.begin(); it != it_end; ++ it) 
    3529                         { 
    3530                                 VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it); 
    3531                                 VspKdLeaf *leaf = vspKdVc->mLeaf; 
    3532                                 AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 
    3533  
    3534                                 VssRayContainer vssRays; 
    3535  
    3536                                 VssRayContainer castRays; 
    3537                                 VssRayContainer initRays; 
    3538  
    3539                                 leaf->GetRays(vssRays); 
    3540  
    3541                                 VssRayContainer::const_iterator it, it_end = vssRays.end(); 
    3542                                 const float prop = 200.0f / (float)vssRays.size(); 
    3543  
    3544                                 for (it = vssRays.begin(); it != it_end; ++ it) 
    3545                                 { 
    3546                                         if (Random(1) < prop) 
    3547                                                 if ((*it)->mTerminationObject == NULL) 
    3548                                                         castRays.push_back(*it); 
    3549                                                 else 
    3550                                                         initRays.push_back(*it); 
    3551                                 } 
    3552  
    3553                                 exporter->ExportRays(castRays, RgbColor(1, 0, 0)); 
    3554                                 exporter->ExportRays(initRays, RgbColor(0, 1, 0)); 
    3555                         } 
    3556                 } 
    3557          
    3558                 //-- output PVS of view cell 
    3559                 m.mDiffuseColor = RgbColor(1, 0, 0); 
    3560                 exporter->SetForcedMaterial(m); 
    3561  
    3562                 Intersectable::NewMail(); 
    3563  
    3564                 ObjectPvsMap::const_iterator it, 
    3565                         it_end = vc->GetPvs().mEntries.end(); 
    3566  
    3567                 exporter->SetFilled(); 
    3568  
    3569                 for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
    3570                 { 
    3571                         Intersectable *intersect = (*it).first; 
    3572  
    3573                         if (!intersect->Mailed()) 
    3574                         { 
    3575                                 Material m = RandomMaterial(); 
    3576                                 exporter->SetForcedMaterial(m); 
    3577  
    3578                                 exporter->ExportIntersectable(intersect); 
    3579                                 intersect->Mail(); 
    3580                         } 
    3581                 } 
    3582  
    3583                 delete exporter; 
    3584         } 
    3585  
    3586         //-- export final view cells 
    3587         Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
    3588  
    3589  
    3590         ExportViewCellsForViz(exporter); 
    3591  
    3592         if (mExportGeometry) 
    3593         { 
    3594                 exporter->SetFilled(); 
    3595                 exporter->ExportGeometry(objects); 
    3596         } 
    3597  
    3598         if (mExportRays) 
    3599         { 
    3600                 const float prob = (float)mVisualizationSamples 
    3601                         / ((float)sampleRays.size() + Limits::Small); 
    3602  
    3603                 exporter->SetWireframe(); 
    3604  
    3605                 VssRayContainer rays; 
    3606  
    3607                 for (int i = 0; i < sampleRays.size(); ++ i) 
    3608                 { 
    3609                   if (RandomValue(0,1) < prob) 
    3610                         rays.push_back(sampleRays[i]); 
    3611                 } 
    3612                 exporter->ExportRays(rays, RgbColor(1, 0, 0)); 
    3613         } 
    3614  
    3615         delete exporter; 
    3616 } 
    3617  
    3618 int VspKdViewCellsManager::GetType() const 
    3619 { 
    3620         return VSP_KD; 
    3621 } 
    3622  
    3623  
    3624 int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin, 
    3625                                                                                    const Vector3 &termination, 
    3626                                                                                    ViewCellContainer &viewcells) 
    3627 { 
    3628         return mVspKdTree->CastLineSegment(origin, termination, viewcells); 
    3629 } 
    3630  
    3631  
    3632 void VspKdViewCellsManager::ExportColor(Exporter *exporter, 
    3633                                                                                 ViewCell *vc) const 
    3634 { 
    3635         if (mColorCode == 0) // Random color 
    3636                 return; 
    3637  
    3638         float importance = 0; 
    3639  
    3640         switch (mColorCode) 
    3641         { 
    3642         case 1: // pvs 
    3643                 { 
    3644                         importance = (float)mViewCellsTree->GetPvsSize(vc) / 
    3645                                 (float)mCurrentViewCellsStats.maxPvs; 
    3646                 } 
    3647                 break; 
    3648         case 2: // merged leaves 
    3649                 { 
    3650                 const int lSize = mViewCellsTree->GetNumInitialViewCells(vc); 
    3651                         importance = (float)lSize / 
    3652                                 (float)mCurrentViewCellsStats.maxLeaves; 
    3653                 } 
    3654                 break; 
    3655         case 3: // merged tree depth difference 
    3656                 { 
    3657                         //importance = (float)GetMaxTreeDiff(vc) / 
    3658                         //      (float)(mVspBspTree->GetStatistics().maxDepth * 2); 
    3659                 } 
    3660                 break; 
    3661         default: 
    3662                 break; 
    3663         } 
    3664  
    3665         Material m; 
    3666         m.mDiffuseColor.b = 1.0f; 
    3667         m.mDiffuseColor.r = importance; 
    3668         m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r; 
    3669         //Debug << "importance: " << importance << endl; 
    3670         exporter->SetForcedMaterial(m); 
    3671 } 
    3672  
    3673  
    3674 void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter, 
    3675                                                                                                    ViewCell *vc, 
    3676                                                                                                    const Plane3 *clipPlane) const 
    3677 { 
    3678         VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc); 
    3679  
    3680         Mesh m; 
    3681  
    3682         ViewCellContainer leaves; 
    3683         mViewCellsTree->CollectLeaves(vc, leaves); 
    3684  
    3685         ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    3686  
    3687         for (it = leaves.begin(); it != it_end; ++ it) 
    3688         { 
    3689                 VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf; 
    3690                 IncludeBoxInMesh(mVspKdTree->GetBBox(l), m); 
    3691         } 
    3692  
    3693         exporter->ExportMesh(&m); 
    3694 } 
    3695  
    3696  
    3697 void VspKdViewCellsManager::CreateMesh(ViewCell *vc) 
    3698 { 
    3699         //TODO 
    3700 } 
    3701  
    3702  
    3703 void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,  
    3704                                                                                                    vector<MergeCandidate> &candidates) 
    3705 { 
    3706         // TODO 
    3707 } 
    3708  
    3709  
    37103349/**************************************************************************/ 
    37113350/*                   VspBspViewCellsManager implementation                */ 
    … …  
    43433982 
    43443983                        //exporter->SetFilled(); 
    4345                         bool b = mUseClipPlaneForViz; 
     3984                        // HACK: export without clip plane 
     3985                        const bool b = mUseClipPlaneForViz; 
    43463986                        mUseClipPlaneForViz = false; 
    43473987                        ExportViewCellsForViz(exporter); 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h

    r1004 r1006  
    1919class BspTree; 
    2020class KdTree; 
    21 class VspKdTree; 
     21class VspOspTree; 
    2222class VspBspTree; 
    2323class KdNode; 
    2424class KdLeaf; 
    25 class VspKdTree; 
    2625class AxisAlignedBox3; 
    2726class BspLeaf; 
    … …  
    813812 
    814813/** 
    815         Manages different higher order operations on the view cells  
    816         for vsp kd tree view cells. 
    817 */ 
    818 class VspKdViewCellsManager: public ViewCellsManager 
    819 { 
    820  
    821 public: 
    822  
    823         VspKdViewCellsManager(VspKdTree *vspKdTree); 
    824  
    825         int ConstructSubdivision(const ObjectContainer &objects,  
    826                                   const VssRayContainer &rays); 
    827  
    828  
    829         int PostProcess(const ObjectContainer &objects,  
    830                                         const VssRayContainer &rays); 
    831  
    832         void Visualize(const ObjectContainer &objects, 
    833                                    const VssRayContainer &sampleRays); 
    834  
    835         int GetType() const; 
    836          
    837         bool ViewCellsConstructed() const; 
    838  
    839         //virtual void PrintStatistics(ostream &s) const; 
    840  
    841         ViewCell *GenerateViewCell(Mesh *mesh) const; 
    842  
    843  
    844     int CastLineSegment(const Vector3 &origin, 
    845                                                 const Vector3 &termination, 
    846                                                 ViewCellContainer &viewcells); 
    847  
    848         ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const { return NULL; } 
    849  
    850         float GetProbability(ViewCell *viewCell); 
    851  
    852  
    853         void CreateMesh(ViewCell *vc); 
    854  
    855         void ExportViewCellGeometry(Exporter *exporter,  
    856                                                                 ViewCell *vc, 
    857                                                                 const Plane3 *clipPlane = NULL) const; 
    858  
    859         void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 
    860  
    861         virtual void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs) {}; 
    862  
    863  
    864 protected: 
    865  
    866         void ExportLeaves(const ObjectContainer &objects, 
    867                                           const VssRayContainer &sampleRays); 
    868  
    869         void CollectViewCells(); 
    870  
    871         void ExportColor(Exporter *exporter, ViewCell *vc) const; 
    872  
    873  
    874  
    875         /// the BSP tree. 
    876         VspKdTree *mVspKdTree; 
    877 }; 
    878  
    879  
    880  
    881 /** 
    882814        Manages different higher order operations on the view cells. 
    883815*/ 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParser.cpp

    r1004 r1006  
    2828#include "VspBspTree.h" 
    2929#include "ViewCellBsp.h" 
    30 #include "VspKdTree.h" 
    3130#include "ViewCellsManager.h" 
    3231#include "GzFileInputSource.h" 
    … …  
    621620 
    622621                mViewCellsManager = new BspViewCellsManager(mBspTree); 
    623         } 
    624          
    625         else if (strcmp(name, "vspKdTree") == 0) 
    626         { 
    627                 // TODO 
    628                 Debug << "view cell type: VspKd" << endl; 
    629                 mVspKdTree = new VspKdTree();    
    630                 mViewCellsManager = new VspKdViewCellsManager(mVspKdTree); 
    631622        } 
    632623        else // vspBspTree 

  • GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParserXerces.h

    r1004 r1006  
    1818 
    1919class VspBspTree; 
    20 class VspKdTree; 
    2120class BspTree; 
    2221class ViewCellsManager; 
    … …  
    7069 
    7170  VspBspTree *mVspBspTree; 
    72   VspKdTree *mVspKdTree; 
    7371  BspTree *mBspTree; 
    7472  ViewCellsTree *mViewCellsTree; 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VrmlExporter.cpp

    r1004 r1006  
    99#include "Polygon3.h" 
    1010#include "VssRay.h" 
    11 #include "VspKdTree.h" 
    1211#include "VssTree.h" 
    1312#include "VspBspTree.h" 
    … …  
    590589} 
    591590 
    592  
    593 bool VrmlExporter::ExportVspKdTree(const VspKdTree &tree,  
     591#if 0 
     592bool VrmlExporter::ExportVspOspTree(const VspOspTree &tree,  
    594593                                                                   const int maxPvs) 
    595594{ 
    … …  
    662661        return true; 
    663662} 
    664  
     663#endif 
    665664 
    666665bool VrmlExporter::ExportKdTree(const KdTree &tree) 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VrmlExporter.h

    r1001 r1006  
    5959                                 const Vector3 direction 
    6060                                 ); 
    61  
     61#if 0 
    6262  bool 
    63   ExportVspKdTree(const VspKdTree &tree, const int maxPvs); 
    64  
     63  ExportVspOspTree(const VspKdTree &tree, const int maxPvs); 
     64#endif 
    6565  bool ExportBspTree(const BspTree &tree); 
    6666 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

    r1004 r1006  
    124124        Environment::GetSingleton()->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType); 
    125125 
    126         Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed); 
    127126         
    128127        char subdivisionStatsLog[100]; 
    … …  
    132131        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.minBand", mMinBand); 
    133132        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand); 
    134         Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisForMaxCost); 
     133        Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisIfMaxCostViolated); 
    135134 
    136135        //-- debug output 
    … …  
    161160        Debug << "use random axis: " << mUseRandomAxis << endl; 
    162161        Debug << "priority queue type: " << mNodePriorityQueueType << endl; 
    163         Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl; 
    164162        Debug << "circulating axis: " << mCirculatingAxis << endl; 
    165163        Debug << "minband: " << mMinBand << endl; 
    166164        Debug << "maxband: " << mMaxBand << endl; 
    167         Debug << "use driving axis for max cost: " << mUseDrivingAxisForMaxCost << endl; 
     165        Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl; 
    168166 
    169167        Debug << "Split plane strategy: "; 
    … …  
    11941192                } 
    11951193           
    1196                 if (ray->mOriginObject)  
     1194                // only count termination objects? 
     1195                if (1 && ray->mOriginObject)  
    11971196                { 
    11981197                        if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution)) 
    … …  
    14821481        const float maxCostRatioForArbitraryAxis = 0.9f; 
    14831482 
    1484         if (mUseDrivingAxisForMaxCost) 
     1483        if (mUseDrivingAxisIfMaxCostViolated) 
    14851484                bestAxis = box.Size().DrivingAxis(); 
    14861485        else 
    … …  
    15231522                                                                                        nPosition[axis]);                        
    15241523                        } 
    1525                          
    1526                         //-- split plane position is spatial median 
    1527  
    1528  
    1529                         // also use median split if cost ratio very low as 
    1530                         // there are not enough visibility cues 
    1531                         //if (!mUseCostHeuristics || (nCostRatio[axis] > maxCostRatioForHeur)) 
    1532                         else  
     1524                        else //-- split plane position is spatial median 
    15331525                        { 
    15341526 
    … …  
    15781570                                                 
    15791571                         
    1580                         if (mUseDrivingAxisForMaxCost) 
     1572                        if (mUseDrivingAxisIfMaxCostViolated) 
    15811573                        { 
    15821574                                // we take longest axis split if cost ratio exceeds threshold 
    … …  
    17101702        } 
    17111703 
     1704 
    17121705        //-- evaluate axis aligned splits 
     1706         
    17131707        int axis; 
    17141708        BspNodeGeometry *fGeom, *bGeom; 
    … …  
    17171711        candidateCost = 99999999.0f; 
    17181712 
    1719         // option: axis aligned split only if no polygon available 
     1713        // as a variant, we take axis aligned split only if there is  
     1714        // more polygon available to guide the split 
    17201715        if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty()) 
    17211716        { 
    … …  
    19321927 
    19331928#if 1 
    1934         // take render cost of node into account 
     1929        // take render cost of node into account to avoid being stuck in a local minimum 
    19351930        const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume(); 
     1931         
    19361932        //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl; 
    1937         //return 0.5f * renderCostDecrease + 0.5f * normalizedOldRenderCost; 
    19381933        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost; 
    19391934#else 
    … …  
    19561951        float pvsBack = 0; 
    19571952         
     1953        // overall probability is used as normalizer 
     1954        float pOverall = 0; 
     1955 
    19581956        // probability that view point lies in back / front node 
    1959         float pOverall = 0; 
    19601957        pFront = 0; 
    19611958        pBack = 0; 
    … …  
    35323529 
    35333530 
    3534 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair; 
    3535  
    3536  
    35373531int VspBspTree::CastBeam(Beam &beam) 
    35383532{ 
    … …  
    36563650                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell()); 
    36573651 
    3658                                 // dont't merge view cells if they are empty and not front and back leaf of the same parent 
    3659                                 // in the tree? 
    3660                                 if (mEmptyViewCellsMergeAllowed || 
    3661                                         !leaf->GetViewCell()->GetPvs().Empty() ||  
     3652                                if (!leaf->GetViewCell()->GetPvs().Empty() ||  
    36623653                                        !(*nit)->GetViewCell()->GetPvs().Empty() || 
    36633654                    leaf->IsSibling(*nit)) 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h

    r1004 r1006  
    158158        struct VspBspSplitCandidate 
    159159        {   
    160                 /// the current node 
     160                /// the current split plane 
    161161                Plane3 mSplitPlane; 
    162162                /// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned) 
    … …  
    467467                @param plane returns the split plane 
    468468                @param leaf the leaf to be split 
    469                 @param polys the polygon list on which the split decition is based 
    470                 @param rays ray container on which selection may be based 
     469                @param data the traversal data holding the polygons and rays which the split decision is based 
     470                @param frontData the front node traversal data (which may be updated to avoid repcomputations 
     471                @param backData the front node traversal data (which may be updated to avoid repcomputations 
     472                @param splitAxis 0 - 2 if axis aligned split, 3 if polygon-aligned split 
     473 
    471474                @note the polygons can be reordered in the process 
     475                 
    472476                @returns true if the cost of the split is under maxCostRatio 
    473477 
    … …  
    567571                                                                  float &position); 
    568572 
    569         /** Selects an axis aligned split plane. 
    570                 @Returns true if split is valied 
    571         */ 
    572         bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const; 
    573  
    574573        /** Subdivides the rays into front and back rays according to the split plane. 
    575574                 
    … …  
    649648                                  int &contributingSamples); 
    650649 
    651  
    652  
    653  
    654  
    655650         
    656651        /** Take 3 ray endpoints, where two are minimum and one a maximum 
    … …  
    701696        /** Returns estimated memory usage of tree. 
    702697        */ 
     698        float GetMemUsage() const; 
    703699        //float GetMemUsage(const VspBspTraversalQueue &tstack) const; 
    704         float GetMemUsage() const; 
    705  
    706  
    707  
     700 
     701 
     702 
     703        /////////////////////////////////////////////////////////// 
     704protected: 
     705         
    708706        /// Pointer to the root of the tree 
    709707        BspNode *mRoot; 
    710                  
     708         
     709        /// the pointer to the view cells manager 
     710        ViewCellsManager *mViewCellsManager; 
     711         
     712        /// View cell corresponding to the space outside the valid view space 
     713        BspViewCell *mOutOfBoundsCell; 
     714 
     715        /// the bsp tree statistics 
    711716        BspTreeStatistics mBspStats; 
    712717 
    713         /// Strategies for choosing next split plane. 
    714         enum {NO_STRATEGY = 0, 
    715                   RANDOM_POLYGON = 1,  
    716                   AXIS_ALIGNED = 2, 
    717                   LEAST_RAY_SPLITS = 256, 
    718                   BALANCED_RAYS = 512, 
    719                   PVS = 1024 
    720                 }; 
     718        /// sorted split candidates used for sweep-heuristics 
     719        vector<SortableEntry> *mSplitCandidates; 
    721720 
    722721        /// box around the whole view domain 
    723722        AxisAlignedBox3 mBox; 
    724723 
    725         bool mUseCostHeuristics; 
     724         
     725        //-- termination critera 
    726726 
    727727        /// minimal number of rays before subdivision termination 
    … …  
    737737        /// minimal accumulated ray length 
    738738        float mTermMinAccRayLength; 
    739  
    740         //HACK 
    741         int mTermMinPolygons; 
     739        /// maximal acceptable cost ratio 
     740        float mTermMaxCostRatio; 
     741        /// tolerance value indicating how often the max cost ratio can be failed 
     742        int mTermMissTolerance; 
     743 
     744 
     745        //-- termination criteria for 
     746        //-- hybrid stategy where only axis aligned split are used until  
     747        //-- a certain point and then also polygon aligned split are taken 
     748          
     749        /// minimal number of rays where axis aligned split is taken 
     750        int mTermMinRaysForAxisAligned; 
     751        /// max ray contribution 
     752        float mTermMaxRayContriForAxisAligned; 
     753        /// weight for heuristics evaluation 
     754        float mAxisAlignedCtDivCi; 
     755        /// spezifies the split border of the axis aligned split 
     756        float mAxisAlignedSplitBorder; 
     757 
     758 
     759        //-- global terminatino criteria 
    742760 
    743761        float mTermMinGlobalCostRatio; 
    744762        int mTermGlobalCostMissTolerance; 
    745  
    746763        int mGlobalCostMisses; 
    747764 
    748         bool mUseSplitCostQueue; 
    749         //-- termination criteria for axis aligned split 
    750  
    751         /// minimal number of rays for axis aligned split 
    752         int mTermMinRaysForAxisAligned; 
    753         // max ray contribution 
    754         float mTermMaxRayContriForAxisAligned; 
    755  
    756         /// strategy to get the best split plane 
    757         int mSplitPlaneStrategy; 
     765        /// maximal number of view cells 
     766        int mMaxViewCells; 
     767        /// maximal tree memory 
     768        float mMaxMemory; 
     769        /// the tree is out of memory 
     770        bool mOutOfMemory; 
     771 
     772 
    758773        /// number of candidates evaluated for the next split plane 
    759774        int mMaxPolyCandidates; 
    760775        /// number of candidates for split planes evaluated using the rays 
    761776        int mMaxRayCandidates; 
     777         
     778 
     779 
     780        //-- axis aligned split criteria 
     781 
     782        /// if only driving axis should be used for choosing the axis-aligned split 
     783        bool mOnlyDrivingAxis; 
     784        /// if heuristics should be used to place the split plane of an axis-aligned split 
     785        bool mUseCostHeuristics; 
     786        /// if driving axis should taken if max cost is exceeded for 
     787        /// all evaluated axis aligned split plane candidates 
     788        bool mUseDrivingAxisIfMaxCostViolated; 
     789        /// minimal relative position where the split axis can be placed 
     790        float mMinBand; 
     791        /// maximal relative position where the split axis can be placed 
     792        float mMaxBand; 
    762793        /// balancing factor for PVS criterium 
    763794        float mCtDivCi; 
    764  
    765         bool mUseDrivingAxisForMaxCost; 
    766         //-- axis aligned split criteria 
    767         float mAxisAlignedCtDivCi; 
    768         /// spezifies the split border of the axis aligned split 
    769         float mAxisAlignedSplitBorder; 
    770  
    771         /// maximal acceptable cost ratio 
    772         float mTermMaxCostRatio; 
    773         /// tolerance value indicating how often the max cost ratio can be failed 
    774         int mTermMissTolerance; 
     795        /// if random split axis should be used 
     796        bool mUseRandomAxis; 
     797        /// if vsp bsp tree should simulate octree 
     798        bool mCirculatingAxis; 
     799 
     800 
     801         
     802        /// priority queue strategy 
     803        enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED}; 
     804        /// if we should use breath first priority for the splits 
     805        int mNodePriorityQueueType; 
     806        /// if split cost queue should be used to compute next best split 
     807        bool mUseSplitCostQueue; 
     808         
     809 
     810         
     811        /// Strategies for choosing next split plane. 
     812        enum {NO_STRATEGY = 0, 
     813                  RANDOM_POLYGON = 1,  
     814                  AXIS_ALIGNED = 2, 
     815                  LEAST_RAY_SPLITS = 256, 
     816                  BALANCED_RAYS = 512, 
     817                  PVS = 1024 
     818                }; 
     819 
     820        /// strategy to get the best split plane 
     821        int mSplitPlaneStrategy; 
    775822 
    776823        //-- factors guiding the split plane heuristics 
     824 
    777825        float mLeastRaySplitsFactor; 
    778826        float mBalancedRaysFactor; 
    779827        float mPvsFactor; 
     828 
    780829 
    781830        /// if area or volume should be used for PVS heuristics 
    … …  
    787836        /// normalizes different bsp split plane criteria 
    788837        float mCostNormalizer; 
    789         /// maximal number of view cells 
    790         int mMaxViewCells; 
    791          
    792         ofstream  mSubdivisionStats; 
    793  
    794838        // if rays should be stored in leaves 
    795839        bool mStoreRays; 
    796          
    797         /// if only driving axis should be used for split 
    798         bool mOnlyDrivingAxis; 
    799  
    800         ViewCellsManager *mViewCellsManager; 
    801  
    802         vector<SortableEntry> *mSplitCandidates; 
    803  
    804          
     840        /// render cost weight between expected value and variance 
    805841        float mRenderCostWeight; 
    806         /// View cell corresponding to the space outside the valid view space 
    807         BspViewCell *mOutOfBoundsCell; 
    808  
    809         /// maximal tree memory 
    810         float mMaxMemory; 
    811         /// the tree is out of memory 
    812         bool mOutOfMemory; 
    813          
     842         
     843 
     844        //-- subdivision statistics 
     845 
     846        /// subdivision stats output file 
     847        ofstream mSubdivisionStats; 
    814848        float mTotalCost; 
    815849        int mTotalPvsSize; 
    816850 
    817         float mMinBand; 
    818         float mMaxBand; 
    819  
    820         //int mSplits; 
    821         /// subdivision stats output file 
    822         ofstream mSubdivsionStats; 
    823         /// if random split axis should be used 
    824         bool mUseRandomAxis; 
     851 
    825852        /// use polygon split whenever there are polys left 
    826853        bool mUsePolygonSplitIfAvailable; 
    … …  
    829856        /// number of currenly generated view cells 
    830857        int mCreatedViewCells; 
    831         /// if vsp bsp tree should simulate octree 
    832         bool mCirculatingAxis; 
    833  
    834         /// if we should use breath first priority for the splits 
    835         int mNodePriorityQueueType; 
    836  
    837         bool mEmptyViewCellsMergeAllowed; 
    838  
    839         // priority queue strategy 
    840         enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED}; 
     858 
     859 
    841860private: 
    842861 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspKdTree.cpp

    r1004 r1006  
    7373 
    7474/**************************************************************/ 
    75 /*                class VspKdNode implementation          */ 
     75/*                class VspKdNode implementation              */ 
    7676/**************************************************************/ 
    7777 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

    r1002 r1006  
    44 
    55#include "Plane3.h" 
    6 #include "VspBspTree.h" 
     6#include "VspOspTree.h" 
    77#include "Mesh.h" 
    88#include "common.h" 
    … …  
    2525//-- static members 
    2626 
    27  
    28 int VspBspTree::sFrontId = 0; 
    29 int VspBspTree::sBackId = 0; 
    30 int VspBspTree::sFrontAndBackId = 0; 
    31  
    32 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair; 
     27int VspOspTree::sFrontId = 0; 
     28int VspOspTree::sBackId = 0; 
     29int VspOspTree::sFrontAndBackId = 0; 
     30 
    3331 
    3432 
    … …  
    5149 
    5250/******************************************************************************/ 
    53 /*                       class VspBspTree implementation                      */ 
     51/*                       class VspOspTree implementation                      */ 
    5452/******************************************************************************/ 
    5553 
    5654 
    57 VspBspTree::VspBspTree(Environment *env): 
     55VspOspTree::VspOspTree(): 
    5856mRoot(NULL), 
    59 mUseAreaForPvs(false), 
    60 mCostNormalizer(Limits::Small), 
    61 mViewCellsManager(NULL), 
    6257mOutOfBoundsCell(NULL), 
    6358mStoreRays(false), 
    64 mRenderCostWeight(0.5), 
    6559mUseRandomAxis(false), 
    6660mTimeStamp(1) 
    6761{ 
    6862        bool randomize = false; 
    69         env->GetBoolValue("VspBspTree.Construction.randomize", randomize); 
     63        Environment::GetSingleton()->GetBoolValue("VspOspTree.Construction.randomize", randomize); 
    7064        if (randomize) 
    7165                Randomize(); // initialise random generator for heuristics 
    7266 
    7367        //-- termination criteria for autopartition 
    74         env->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth); 
    75         env->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs); 
    76         env->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays); 
    77         env->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability); 
    78         env->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution); 
    79         env->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength); 
    80         env->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
    81         env->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance); 
    82         env->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells); 
     68        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.maxDepth", mTermMaxDepth); 
     69        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.minPvs", mTermMinPvs); 
     70        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.minRays", mTermMinRays); 
     71        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.minProbability", mTermMinProbability); 
     72        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxRayContribution", mTermMaxRayContribution); 
     73        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
     74        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.missTolerance", mTermMissTolerance); 
     75        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.maxViewCells", mMaxViewCells); 
    8376 
    8477        //-- max cost ratio for early tree termination 
    85         env->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
    86  
    87         env->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio); 
    88         env->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance); 
     78        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxCostRatio", mTermMaxCostRatio); 
     79 
     80        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio); 
     81        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance); 
    8982 
    9083        // HACK//mTermMinPolygons = 25; 
    9184 
    9285        //-- factors for bsp tree split plane heuristics 
    93         env->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor); 
    94         env->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi); 
    95  
     86        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.ct_div_ci", mCtDivCi); 
    9687 
    9788        //-- partition criteria 
    98         env->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates); 
    99         env->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates); 
    100         env->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy); 
    101  
    102         env->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon); 
    103         env->GetIntValue("VspBspTree.maxTests", mMaxTests); 
     89        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.epsilon", mEpsilon); 
    10490 
    10591        // if only the driving axis is used for axis aligned split 
    106         env->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); 
    107          
    108         //-- termination criteria for axis aligned split 
    109         env->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",  
    110                                                                 mTermMaxRayContriForAxisAligned); 
    111         env->GetIntValue("VspBspTree.Termination.AxisAligned.minRays", 
    112                                                          mTermMinRaysForAxisAligned); 
    113  
    114         //env->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory); 
    115         env->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory); 
    116  
    117         env->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight); 
    118         env->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable); 
    119  
    120         env->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics); 
    121         env->GetBoolValue("VspBspTree.useSplitCostQueue", mUseSplitCostQueue); 
    122         env->GetBoolValue("VspBspTree.simulateOctree", mCirculatingAxis); 
    123         env->GetBoolValue("VspBspTree.useRandomAxis", mUseRandomAxis); 
    124         env->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType); 
    125  
    126         env->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed); 
     92        Environment::GetSingleton()->GetBoolValue("VspOspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis); 
     93         
     94        //Environment::GetSingleton()->GetFloatValue("VspOspTree.maxTotalMemory", mMaxTotalMemory); 
     95        Environment::GetSingleton()->GetFloatValue("VspOspTree.maxStaticMemory", mMaxMemory); 
     96 
     97        Environment::GetSingleton()->GetBoolValue("VspOspTree.useCostHeuristics", mUseCostHeuristics); 
     98        Environment::GetSingleton()->GetBoolValue("VspOspTree.simulateOctree", mCirculatingAxis); 
     99        Environment::GetSingleton()->GetBoolValue("VspOspTree.useRandomAxis", mUseRandomAxis); 
     100        Environment::GetSingleton()->GetIntValue("VspOspTree.nodePriorityQueueType", mNodePriorityQueueType); 
    127101         
    128102        char subdivisionStatsLog[100]; 
    129         env->GetStringValue("VspBspTree.subdivisionStats", subdivisionStatsLog); 
     103        Environment::GetSingleton()->GetStringValue("VspOspTree.subdivisionStats", subdivisionStatsLog); 
    130104        mSubdivisionStats.open(subdivisionStatsLog); 
    131105 
    132         env->GetFloatValue("VspBspTree.Construction.minBand", mMinBand); 
    133         env->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand); 
    134         env->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisForMaxCost); 
     106        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.minBand", mMinBand); 
     107        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.maxBand", mMaxBand); 
     108         
    135109 
    136110        //-- debug output 
    … …  
    145119        Debug << "miss tolerance: " << mTermMissTolerance << endl; 
    146120        Debug << "max view cells: " << mMaxViewCells << endl; 
    147         Debug << "max polygon candidates: " << mMaxPolyCandidates << endl; 
    148         //Debug << "max plane candidates: " << mMaxRayCandidates << endl; 
    149121        Debug << "randomize: " << randomize << endl; 
    150122 
    151         Debug << "using area for pvs: " << mUseAreaForPvs << endl; 
    152         Debug << "render cost weight: " << mRenderCostWeight << endl; 
    153123        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl; 
    154124        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl; 
    155125        Debug << "only driving axis: " << mOnlyDrivingAxis << endl; 
    156126        Debug << "max memory: " << mMaxMemory << endl; 
    157         Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl; 
    158127        Debug << "use cost heuristics: " << mUseCostHeuristics << endl; 
    159         Debug << "use split cost queue: " << mUseSplitCostQueue << endl; 
    160128        Debug << "subdivision stats log: " << subdivisionStatsLog << endl; 
    161129        Debug << "use random axis: " << mUseRandomAxis << endl; 
    162130        Debug << "priority queue type: " << mNodePriorityQueueType << endl; 
    163         Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl; 
    164131        Debug << "circulating axis: " << mCirculatingAxis << endl; 
    165132        Debug << "minband: " << mMinBand << endl; 
    166133        Debug << "maxband: " << mMaxBand << endl; 
    167         Debug << "use driving axis for max cost: " << mUseDrivingAxisForMaxCost << endl; 
    168  
    169         Debug << "Split plane strategy: "; 
    170  
    171         if (mSplitPlaneStrategy & RANDOM_POLYGON) 
    172         { 
    173                 Debug << "random polygon "; 
    174         } 
    175         if (mSplitPlaneStrategy & AXIS_ALIGNED) 
    176         { 
    177                 Debug << "axis aligned "; 
    178         } 
    179         if (mSplitPlaneStrategy & LEAST_RAY_SPLITS) 
    180         { 
    181                 mCostNormalizer += mLeastRaySplitsFactor; 
    182                 Debug << "least ray splits "; 
    183         } 
    184         if (mSplitPlaneStrategy & BALANCED_RAYS) 
    185         { 
    186                 mCostNormalizer += mBalancedRaysFactor; 
    187                 Debug << "balanced rays "; 
    188         } 
    189         if (mSplitPlaneStrategy & PVS) 
    190         { 
    191                 mCostNormalizer += mPvsFactor; 
    192                 Debug << "pvs"; 
    193         } 
    194  
     134         
    195135 
    196136        mSplitCandidates = new vector<SortableEntry>; 
    … …  
    199139} 
    200140 
    201 VspBspTree::VspBspTree(): 
    202 mRoot(NULL), 
    203 mUseAreaForPvs(false), 
    204 mCostNormalizer(Limits::Small), 
    205 mViewCellsManager(NULL), 
    206 mOutOfBoundsCell(NULL), 
    207 mStoreRays(false), 
    208 mRenderCostWeight(0.5), 
    209 mUseRandomAxis(false), 
    210 mTimeStamp(1), 
    211 mEpsilon(1e-6f) 
    212 { 
    213 } 
    214  
    215 BspViewCell *VspBspTree::GetOutOfBoundsCell() 
     141 
     142BspViewCell *VspOspTree::GetOutOfBoundsCell() 
    216143{ 
    217144        return mOutOfBoundsCell; 
    … …  
    219146 
    220147 
    221 BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell() 
     148BspViewCell *VspOspTree::GetOrCreateOutOfBoundsCell() 
    222149{ 
    223150        if (!mOutOfBoundsCell) 
    … …  
    232159 
    233160 
    234 const BspTreeStatistics &VspBspTree::GetStatistics() const 
     161const BspTreeStatistics &VspOspTree::GetStatistics() const 
    235162{ 
    236163        return mBspStats; 
    … …  
    238165 
    239166 
    240 VspBspTree::~VspBspTree() 
     167VspOspTree::~VspOspTree() 
    241168{ 
    242169        DEL_PTR(mRoot); 
    … …  
    244171} 
    245172 
    246  
    247 int VspBspTree::AddMeshToPolygons(Mesh *mesh, 
    248                                                                   PolygonContainer &polys, 
    249                                                                   MeshInstance *parent) 
    250 { 
    251         FaceContainer::const_iterator fi; 
    252  
    253         // copy the face data to polygons 
    254         for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi) 
    255         { 
    256                 Polygon3 *poly = new Polygon3((*fi), mesh); 
    257  
    258                 if (poly->Valid(mEpsilon)) 
    259                 { 
    260                         poly->mParent = parent; // set parent intersectable 
    261                         polys.push_back(poly); 
    262                 } 
    263                 else 
    264                         DEL_PTR(poly); 
    265         } 
    266         return (int)mesh->mFaces.size(); 
    267 } 
    268  
    269  
    270 int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells, 
    271                                                                  PolygonContainer &polys, 
    272                                                                  int maxObjects) 
    273 { 
    274         int limit = (maxObjects > 0) ? 
    275                 Min((int)viewCells.size(), maxObjects) : (int)viewCells.size(); 
    276  
    277         int polysSize = 0; 
    278  
    279         for (int i = 0; i < limit; ++ i) 
    280         { 
    281                 if (viewCells[i]->GetMesh()) // copy the mesh data to polygons 
    282                 { 
    283                         mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb 
    284                         polysSize += 
    285                                 AddMeshToPolygons(viewCells[i]->GetMesh(), 
    286                                                                   polys, 
    287                                                                   viewCells[i]); 
    288                 } 
    289         } 
    290  
    291         return polysSize; 
    292 } 
    293  
    294  
    295 int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects, 
    296                                                                  PolygonContainer &polys, 
    297                                                                  int maxObjects) 
    298 { 
    299         int limit = (maxObjects > 0) ? 
    300                 Min((int)objects.size(), maxObjects) : (int)objects.size(); 
    301  
    302         for (int i = 0; i < limit; ++i) 
    303         { 
    304                 Intersectable *object = objects[i];//*it; 
    305                 Mesh *mesh = NULL; 
    306  
    307                 switch (object->Type()) // extract the meshes 
    308                 { 
    309                 case Intersectable::MESH_INSTANCE: 
    310                         mesh = dynamic_cast<MeshInstance *>(object)->GetMesh(); 
    311                         break; 
    312                 case Intersectable::VIEW_CELL: 
    313                         mesh = dynamic_cast<ViewCell *>(object)->GetMesh(); 
    314                         break; 
    315                 case Intersectable::TRANSFORMED_MESH_INSTANCE: 
    316                         { 
    317                                 TransformedMeshInstance *mi = dynamic_cast<TransformedMeshInstance *>(object); 
    318  
    319                                 if (!mi->GetMesh()) 
    320                                         break; 
    321  
    322                                 mesh = new Mesh(*mi->GetMesh()); 
    323  
    324                                 Matrix4x4 m; 
    325                                 mi->GetWorldTransform(m); 
    326  
    327                                 mesh->ApplyTransformation(m); 
    328  
    329                 break; 
    330                         } 
    331                 default: 
    332                         Debug << "intersectable type not supported" << endl; 
    333                         break; 
    334                 } 
    335  
    336         if (mesh) // copy the mesh data to polygons 
    337                 { 
    338                         mBox.Include(object->GetBox()); // add to BSP tree aabb 
    339                         AddMeshToPolygons(mesh, polys, NULL); 
    340  
    341                         // cleanup 
    342                         if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE) 
    343                                 DEL_PTR(mesh); 
    344                 } 
    345         } 
    346  
    347         return (int)polys.size(); 
    348 } 
    349  
    350  
    351 void VspBspTree::Construct(const VssRayContainer &sampleRays, 
     173void VspOspTree::Construct(const VssRayContainer &sampleRays, 
    352174                                                   AxisAlignedBox3 *forcedBoundingBox) 
    353175{ 
    … …  
    371193        int numObj = 0; 
    372194 
    373         //-- extract polygons intersected by the rays 
    374         for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 
    375         { 
    376                 VssRay *ray = *rit; 
    377  
    378                 if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) && 
    379                         ray->mTerminationObject &&  
    380                         !ray->mTerminationObject->Mailed()) 
    381                 { 
    382                         ray->mTerminationObject->Mail(); 
    383                         MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject); 
    384                         AddMeshToPolygons(obj->GetMesh(), polys, obj); 
    385                         ++ numObj; 
    386  
    387                         //-- compute bounding box 
    388                         if (!forcedBoundingBox) 
    389                                 mBox.Include(ray->mTermination); 
    390                 } 
    391  
    392                 if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) && 
    393                         ray->mOriginObject &&  
    394                         !ray->mOriginObject->Mailed()) 
    395                 { 
    396                         ray->mOriginObject->Mail(); 
    397                         MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject); 
    398                         AddMeshToPolygons(obj->GetMesh(), polys, obj); 
    399                         ++ numObj; 
    400  
    401                         //-- compute bounding box 
    402                         if (!forcedBoundingBox) 
    403                                 mBox.Include(ray->mOrigin); 
    404                 } 
    405         } 
    406          
    407         Debug << "maximal pvs (i.e., pvs still considered as valid) : "  
    408                   << mViewCellsManager->GetMaxPvsSize() << endl; 
    409  
    410195        //-- store rays 
    411196        for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 
    … …  
    430215        } 
    431216 
    432         // normalize 
    433         if (mUseAreaForPvs) 
    434                 mTermMinProbability *= mBox.SurfaceArea();  
    435         else  
    436                 mTermMinProbability *= mBox.GetVolume(); 
    437  
    438         // throw out unnecessary polygons 
    439         PreprocessPolygons(polys); 
    440  
    441         mBspStats.polys = (int)polys.size(); 
     217        mTermMinProbability *= mBox.GetVolume(); 
     218 
    442219        mGlobalCostMisses = 0; 
    443220 
    444221        cout << "finished" << endl; 
    445222 
    446         Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from " 
    447                   << (int)sampleRays.size() << " rays in " 
    448                   << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl; 
    449  
    450223        // use split cost priority queue 
    451         if (mUseSplitCostQueue) 
    452         { 
    453                 ConstructWithSplitQueue(polys, rays); 
    454         } 
    455         else 
    456         { 
    457                 Construct(polys, rays); 
    458         } 
    459  
    460         // clean up polygons 
    461         CLEAR_CONTAINER(polys); 
     224        Construct(rays); 
    462225} 
    463226 
    464227 
    465228// TODO: return memory usage in MB 
    466 float VspBspTree::GetMemUsage() const 
     229float VspOspTree::GetMemUsage() const 
    467230{ 
    468231        return (float) 
    469                  (sizeof(VspBspTree) +  
     232                 (sizeof(VspOspTree) +  
    470233                  mBspStats.Leaves() * sizeof(BspLeaf) +  
    471234                  mCreatedViewCells * sizeof(BspViewCell) + 
    … …  
    476239 
    477240 
    478  
    479 void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays) 
    480 { 
    481         VspBspTraversalQueue tQueue; 
     241void VspOspTree::Construct(RayInfoContainer *rays) 
     242{ 
     243        VspOspSplitQueue tQueue; 
    482244 
    483245        mRoot = new BspLeaf(); 
    484246 
    485         // constrruct root node geometry 
    486         BspNodeGeometry *geom = new BspNodeGeometry(); 
    487         ConstructGeometry(mRoot, *geom); 
    488  
    489         const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume(); 
    490  
    491         VspBspTraversalData tData(mRoot, 
    492                                                           new PolygonContainer(polys), 
     247        const float prop = mBox.GetVolume(); 
     248 
     249        VspOspTraversalData tData(mRoot, 
    493250                                                          0, 
    494251                                                          rays, 
    495252                              ComputePvsSize(*rays), 
    496253                                                          prop, 
    497                                                           geom); 
    498  
    499         EvalPriority(tData); 
    500  
    501  
    502         // first node is kd node, i.e. an axis aligned box 
    503         if (1) 
    504         tData.mIsKdNode = true; 
    505         else 
    506                 tData.mIsKdNode = false; 
    507  
    508         tQueue.push(tData); 
    509  
    510  
    511         mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume(); 
    512         mTotalPvsSize = tData.mPvs; 
    513          
    514         mSubdivisionStats  
    515                         << "#ViewCells\n1" <<  endl 
    516                         << "#RenderCostDecrease\n0" << endl  
    517                         << "#TotalRenderCost\n" << mTotalCost << endl 
    518                         << "#AvgRenderCost\n" << mTotalPvsSize << endl; 
    519  
    520         Debug << "total cost: " << mTotalCost << endl; 
    521          
    522          
    523         mBspStats.Start(); 
    524         cout << "Constructing vsp bsp tree ... \n"; 
    525  
    526         long startTime = GetTime();      
    527         int nLeaves = 500; 
    528         int nViewCells = 500; 
    529  
    530         // used for intermediate time measurements and progress 
    531         long interTime = GetTime();      
    532  
    533         mOutOfMemory = false; 
    534  
    535         mCreatedViewCells = 0; 
    536          
    537         while (!tQueue.empty()) 
    538         { 
    539                 tData = tQueue.top(); 
    540             tQueue.pop();                
    541  
    542                 if (0 && !mOutOfMemory) 
    543                 { 
    544                         float mem = GetMemUsage(); 
    545  
    546                         if (mem > mMaxMemory) 
    547                         { 
    548                                 mOutOfMemory = true; 
    549                                 Debug << "memory limit reached: " << mem << endl; 
    550                         } 
    551                 } 
    552  
    553                 // subdivide leaf node 
    554                 BspNode *r = Subdivide(tQueue, tData); 
    555  
    556                 if (r == mRoot) 
    557                         Debug << "VSP BSP tree construction time spent at root: " 
    558                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 
    559  
    560                 if (mBspStats.Leaves() >= nLeaves) 
    561                 { 
    562                         nLeaves += 500; 
    563  
    564                         cout << "leaves=" << mBspStats.Leaves() << endl; 
    565                         Debug << "needed " 
    566                                   << TimeDiff(interTime, GetTime())*1e-3  
    567                                   << " secs to create 500 view cells" << endl; 
    568                         interTime = GetTime(); 
    569                 } 
    570  
    571                 if (mCreatedViewCells >= nViewCells) 
    572                 { 
    573                         nViewCells += 500; 
    574  
    575                         cout << "generated " << mCreatedViewCells << " viewcells" << endl; 
    576                 } 
    577         } 
    578  
    579         Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl; 
    580         cout << "finished\n"; 
    581  
    582         mBspStats.Stop(); 
    583 } 
    584  
    585  
    586  
    587 void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys,  
    588                                                                                           RayInfoContainer *rays) 
    589 { 
    590         VspBspSplitQueue tQueue; 
    591  
    592         mRoot = new BspLeaf(); 
    593  
    594         // constrruct root node geometry 
    595         BspNodeGeometry *geom = new BspNodeGeometry(); 
    596         ConstructGeometry(mRoot, *geom); 
    597  
    598         const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume(); 
    599  
    600         VspBspTraversalData tData(mRoot, 
    601                                                           new PolygonContainer(polys), 
    602                                                           0, 
    603                                                           rays, 
    604                               ComputePvsSize(*rays), 
    605                                                           prop, 
    606                                                           geom); 
     254                                                          mBox); 
    607255 
    608256 
    609257        // compute first split candidate 
    610         VspBspSplitCandidate splitCandidate; 
     258        VspOspSplitCandidate splitCandidate; 
    611259        EvalSplitCandidate(tData, splitCandidate); 
    612260 
    … …  
    697345 
    698346 
    699 bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const 
     347bool VspOspTree::LocalTerminationCriteriaMet(const VspOspTraversalData &data) const 
    700348{ 
    701349        return 
    … …  
    708356 
    709357 
    710 bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const 
     358bool VspOspTree::GlobalTerminationCriteriaMet(const VspOspTraversalData &data) const 
    711359{ 
    712360        return 
    … …  
    718366 
    719367 
    720  
    721 BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue, 
    722                                                            VspBspTraversalData &tData) 
    723 { 
    724         BspNode *newNode = tData.mNode; 
    725  
    726         if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData)) 
    727         { 
    728                 PolygonContainer coincident; 
    729  
    730                 VspBspTraversalData tFrontData; 
    731                 VspBspTraversalData tBackData; 
    732  
    733                 // create new interior node and two leaf nodes 
    734                 // or return leaf as it is (if maxCostRatio missed) 
    735                 int splitAxis; 
    736                 bool splitFurther = true; 
    737                 int maxCostMisses = tData.mMaxCostMisses; 
    738                  
    739                 Plane3 splitPlane; 
    740                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    741                  
    742                 // choose next split plane 
    743                 if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis)) 
    744                 { 
    745                         ++ maxCostMisses; 
    746  
    747                         if (maxCostMisses > mTermMissTolerance) 
    748                         { 
    749                                 // terminate branch because of max cost 
    750                                 ++ mBspStats.maxCostNodes; 
    751                                 splitFurther = false; 
    752                         } 
    753                 } 
    754          
    755                 // if this a valid split => subdivide this node further 
    756                 if (splitFurther) //-- continue subdivision 
    757                 { 
    758                         newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident); 
    759  
    760                         if (splitAxis < 3) 
    761                                 ++ mBspStats.splits[splitAxis]; 
    762                         else 
    763                                 ++ mBspStats.polySplits; 
    764  
    765                         // if it was a kd node (i.e., a box) and the split axis is axis aligned, it is still a kd node 
    766                         tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3)); 
    767                         tFrontData.mAxis = tBackData.mAxis = splitAxis; 
    768  
    769                         // how often was max cost ratio missed in this branch? 
    770                         tFrontData.mMaxCostMisses = maxCostMisses; 
    771                         tBackData.mMaxCostMisses = maxCostMisses; 
    772  
    773                         EvalPriority(tFrontData); 
    774                         EvalPriority(tBackData); 
    775  
    776                         // evaluate subdivision stats 
    777                         if (1) 
    778                         { 
    779                                 float cFront = (float)tFrontData.mPvs * tFrontData.mProbability; 
    780                                 float cBack = (float)tBackData.mPvs * tBackData.mProbability; 
    781                                 float cData = (float)tData.mPvs * tData.mProbability;; 
    782  
    783                 float costDecr = (cFront + cBack - cData) / mBox.GetVolume(); 
    784  
    785                                 mTotalCost += costDecr; 
    786                                 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs; 
    787  
    788                                 mSubdivisionStats  
    789                                                 << "#ViewCells\n" << mBspStats.Leaves() << endl 
    790                                                 << "#RenderCostDecrease\n" << -costDecr << endl  
    791                                                 << "#TotalRenderCost\n" << mTotalCost << endl 
    792                                                 << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl; 
    793                         } 
    794  
    795                         // push the children on the stack 
    796                         tQueue.push(tFrontData); 
    797                         tQueue.push(tBackData); 
    798  
    799                         // delete old leaf node 
    800                         DEL_PTR(tData.mNode); 
    801                 } 
    802         } 
    803  
    804         //-- terminate traversal and create new view cell 
    805         if (newNode->IsLeaf()) 
    806         { 
    807                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode); 
    808                 BspViewCell *viewCell = new BspViewCell(); 
    809                  
    810                 leaf->SetViewCell(viewCell); 
    811          
    812                 //-- update pvs 
    813                 int conSamp = 0; 
    814                 float sampCon = 0.0f; 
    815                 AddToPvs(leaf, *tData.mRays, sampCon, conSamp); 
    816  
    817                 // update scalar pvs size lookup 
    818                 mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize()); 
    819          
    820  
    821                 mBspStats.contributingSamples += conSamp; 
    822                 mBspStats.sampleContributions +=(int) sampCon; 
    823  
    824                 //-- store additional info 
    825                 if (mStoreRays) 
    826                 { 
    827                         RayInfoContainer::const_iterator it, it_end = tData.mRays->end(); 
    828                         for (it = tData.mRays->begin(); it != it_end; ++ it) 
    829                         { 
    830                                 (*it).mRay->Ref();                       
    831                                 leaf->mVssRays.push_back((*it).mRay); 
    832                         } 
    833                 } 
    834  
    835                 // should I check here? 
    836                 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize())) 
    837                 { 
    838                         viewCell->SetValid(false); 
    839                         leaf->SetTreeValid(false); 
    840                         PropagateUpValidity(leaf); 
    841  
    842                         ++ mBspStats.invalidLeaves; 
    843                 } 
    844                  
    845         viewCell->mLeaf = leaf; 
    846  
    847                 if (mUseAreaForPvs) 
    848                         viewCell->SetArea(tData.mProbability); 
    849                 else 
    850                         viewCell->SetVolume(tData.mProbability); 
    851  
    852                 leaf->mProbability = tData.mProbability; 
    853  
    854                 EvaluateLeafStats(tData);                
    855         } 
    856  
    857         //-- cleanup 
    858         tData.Clear(); 
    859  
    860         return newNode; 
    861 } 
    862  
    863368// subdivide using a split plane queue 
    864 BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue, 
    865                                                            VspBspSplitCandidate &splitCandidate) 
    866 { 
    867         VspBspTraversalData &tData = splitCandidate.mParentData; 
     369BspNode *VspOspTree::Subdivide(VspOspSplitQueue &tQueue, 
     370                                                           VspOspSplitCandidate &splitCandidate) 
     371{ 
     372        VspOspTraversalData &tData = splitCandidate.mParentData; 
    868373 
    869374        BspNode *newNode = tData.mNode; 
    … …  
    871376        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData)) 
    872377        {        
    873                 PolygonContainer coincident; 
    874  
    875                 VspBspTraversalData tFrontData; 
    876                 VspBspTraversalData tBackData; 
     378                VspOspTraversalData tFrontData; 
     379                VspOspTraversalData tBackData; 
    877380 
    878381                //-- continue subdivision 
    879382                 
    880383                // create new interior node and two leaf node 
    881                 const Plane3 splitPlane = splitCandidate.mSplitPlane; 
     384                //TODO 
     385                const Plane3 splitPlane;// = splitCandidate.mSplitPlane; 
    882386                                 
    883                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident); 
    884          
    885                 const int splitAxis = splitCandidate.mSplitAxis; 
     387                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData); 
     388         
    886389                const int maxCostMisses = splitCandidate.mMaxCostMisses; 
    887390 
    888                 if (splitAxis < 3) 
    889                         ++ mBspStats.splits[splitAxis]; 
    890                 else 
    891                         ++ mBspStats.polySplits; 
    892  
    893                 tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3)); 
    894                 tFrontData.mAxis = tBackData.mAxis = splitAxis; 
    895391 
    896392                // how often was max cost ratio missed in this branch? 
    … …  
    922418         
    923419                //-- push the new split candidates on the stack 
    924                 VspBspSplitCandidate frontCandidate; 
    925                 VspBspSplitCandidate backCandidate; 
     420                VspOspSplitCandidate frontCandidate; 
     421                VspOspSplitCandidate backCandidate; 
    926422 
    927423                EvalSplitCandidate(tFrontData, frontCandidate); 
    … …  
    969465                viewCell->mLeaf = leaf; 
    970466 
    971                 if (mUseAreaForPvs) 
    972                         viewCell->SetArea(tData.mProbability); 
    973                 else 
    974                         viewCell->SetVolume(tData.mProbability); 
    975  
     467                viewCell->SetVolume(tData.mProbability); 
    976468        leaf->mProbability = tData.mProbability; 
    977469 
    … …  
    986478 
    987479 
    988 void VspBspTree::EvalPriority(VspBspTraversalData &tData) const 
    989 { 
    990     switch (mNodePriorityQueueType)  
    991         { 
    992         case BREATH_FIRST: 
    993                 tData.mPriority = (float)-tData.mDepth; 
    994                 break; 
    995         case DEPTH_FIRST: 
    996                 tData.mPriority = (float)tData.mDepth; 
    997                 break; 
    998         default: 
    999                 tData.mPriority = tData.mPvs * tData.mProbability; 
    1000                 //Debug << "priority: " << tData.mPriority << endl; 
    1001                 break; 
    1002         } 
    1003 } 
    1004  
    1005  
    1006 void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData, 
    1007                                                                         VspBspSplitCandidate &splitData) 
    1008 { 
    1009         VspBspTraversalData frontData; 
    1010         VspBspTraversalData backData; 
     480void VspOspTree::EvalSplitCandidate(VspOspTraversalData &tData, 
     481                                                                        VspOspSplitCandidate &splitData) 
     482{ 
     483        VspOspTraversalData frontData; 
     484        VspOspTraversalData backData; 
    1011485 
    1012486        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    1013487 
    1014488        // compute locally best split plane 
    1015     bool success = SelectPlane(splitData.mSplitPlane, leaf, tData,  
    1016                                                            frontData, backData, splitData.mSplitAxis); 
    1017  
    1018         // TODO: reuse 
    1019         DEL_PTR(frontData.mGeometry); 
    1020         DEL_PTR(backData.mGeometry); 
    1021          
     489        // TODO 
     490    const bool success =0;/// SelectPlane(splitData.mSplitPlane, tData,  
     491//                                                                       frontData, backData); 
     492        //TODO 
    1022493        // compute global decrease in render cost 
    1023         splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData); 
     494        splitData.mRenderCost = 0;//EvalRenderCostDecrease(splitData.mSplitPlane, tData); 
    1024495        splitData.mParentData = tData; 
    1025496        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 
    … …  
    1027498 
    1028499 
    1029 BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane, 
    1030                                                                            VspBspTraversalData &tData, 
    1031                                                                            VspBspTraversalData &frontData, 
    1032                                                                            VspBspTraversalData &backData, 
    1033                                                                            PolygonContainer &coincident) 
     500BspInterior *VspOspTree::SubdivideNode(const Plane3 &splitPlane, 
     501                                                                           VspOspTraversalData &tData, 
     502                                                                           VspOspTraversalData &frontData, 
     503                                                                           VspOspTraversalData &backData) 
    1034504{ 
    1035505        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 
    … …  
    1037507        //-- the front and back traversal data is filled with the new values 
    1038508        frontData.mDepth = tData.mDepth + 1; 
    1039         frontData.mPolygons = new PolygonContainer(); 
    1040509        frontData.mRays = new RayInfoContainer(); 
    1041510         
    1042511        backData.mDepth = tData.mDepth + 1; 
    1043         backData.mPolygons = new PolygonContainer(); 
    1044512        backData.mRays = new RayInfoContainer(); 
    1045513         
    … …  
    1059527         
    1060528        // if geometry was not already computed 
    1061         if (!frontData.mGeometry && !backData.mGeometry) 
    1062         { 
    1063                 frontData.mGeometry = new BspNodeGeometry(); 
    1064                 backData.mGeometry = new BspNodeGeometry(); 
    1065  
    1066                 tData.mGeometry->SplitGeometry(*frontData.mGeometry, 
    1067                                                                            *backData.mGeometry, 
    1068                                                                            splitPlane, 
    1069                                                                            mBox, 
    1070                                                                            //0.0f); 
    1071                                                                            mEpsilon); 
    1072                  
    1073                 if (mUseAreaForPvs) 
    1074                 { 
    1075                         frontData.mProbability = frontData.mGeometry->GetArea(); 
    1076                         backData.mProbability = backData.mGeometry->GetArea(); 
    1077                 } 
    1078                 else 
    1079                 { 
    1080                         frontData.mProbability = frontData.mGeometry->GetVolume(); 
    1081                         backData.mProbability = tData.mProbability - frontData.mProbability; 
    1082  
    1083                         // should never come here: wrong volume !!! 
    1084                         if (0) 
    1085                         { 
    1086                                 if (frontData.mProbability < -0.00001) 
    1087                                         Debug << "fatal error f: " << frontData.mProbability << endl; 
    1088                                 if (backData.mProbability < -0.00001) 
    1089                                         Debug << "fatal error b: " << backData.mProbability << endl; 
    1090  
    1091                                 // clamp because of precision issues 
    1092                                 if (frontData.mProbability < 0) frontData.mProbability = 0; 
    1093                                 if (backData.mProbability < 0) backData.mProbability = 0; 
    1094                         } 
    1095                 } 
    1096         } 
    1097  
    1098          
    1099     // subdivide polygons 
    1100         SplitPolygons(splitPlane, 
    1101                                   *tData.mPolygons, 
    1102                       *frontData.mPolygons, 
    1103                                   *backData.mPolygons, 
    1104                                   coincident); 
    1105  
    1106  
    1107  
    1108         /////////////////////////////////////// 
     529        // TODO 
     530 
     531#if TODO 
     532        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,  
     533                                                         frontData.mBoundingBox, backData.mBoundingBox); 
     534 
     535#endif 
     536 
     537        frontData.mProbability = frontData.mBoundingBox.GetVolume(); 
     538        backData.mProbability = tData.mProbability - frontData.mProbability; 
     539 
     540         
     541    /////////////////////////////////////////// 
    1109542        // subdivide further 
    1110543 
    … …  
    1149582        interior->mTimeStamp = mTimeStamp ++; 
    1150583         
    1151  
    1152         //DEL_PTR(leaf); 
    1153584        return interior; 
    1154585} 
    1155586 
    1156587 
    1157 void VspBspTree::AddToPvs(BspLeaf *leaf, 
     588void VspOspTree::AddToPvs(BspLeaf *leaf, 
    1158589                                                  const RayInfoContainer &rays, 
    1159590                                                  float &sampleContributions, 
    … …  
    1200631 
    1201632 
    1202 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays,  
     633void VspOspTree::SortSplitCandidates(const RayInfoContainer &rays,  
    1203634                                                                         const int axis,  
    1204635                                                                         float minBand,  
    … …  
    1251682 
    1252683 
    1253 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays, 
     684float VspOspTree::BestCostRatioHeuristics(const RayInfoContainer &rays, 
    1254685                                                                                  const AxisAlignedBox3 &box, 
    1255686                                                                                  const int pvsSize, 
    … …  
    1413844        if (splitPlaneFound) 
    1414845        { 
    1415                 ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small); 
     846                ratio = newRenderCost / (oldRenderCost + Limits::Small); 
    1416847        } 
    1417848        //if (axis != 1) 
    … …  
    1423854 
    1424855 
    1425 float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane, 
    1426                                                                                  const VspBspTraversalData &tData, 
    1427                                                                                  int &axis, 
    1428                                                                                  BspNodeGeometry **frontGeom, 
    1429                                                                                  BspNodeGeometry **backGeom, 
    1430                                                                                  float &pFront, 
    1431                                                                                  float &pBack, 
    1432                                                                                  const bool isKdNode) 
     856float VspOspTree::SelectPlane(const VspOspTraversalData &tData, 
     857                                                          AxisAlignedPlane &plane, 
     858                                                          float &pFront, 
     859                                                          float &pBack) 
    1433860{ 
    1434861        float nPosition[3]; 
    … …  
    1437864        float nProbBack[3]; 
    1438865 
    1439         BspNodeGeometry *nFrontGeom[3]; 
    1440         BspNodeGeometry *nBackGeom[3]; 
    1441  
    1442         // set to NULL, so I can find out which gemetry was stored 
    1443         for (int i = 0; i < 3; ++ i) 
    1444         { 
    1445                 nFrontGeom[i] = NULL; 
    1446                 nBackGeom[i] = NULL; 
    1447         } 
    1448  
    1449866        // create bounding box of node geometry 
    1450         AxisAlignedBox3 box; 
    1451                  
    1452         //TODO: for kd split geometry already is box => only take minmax vertices 
    1453         if (1) 
    1454         { 
    1455                 // get bounding box from geometry 
    1456                 tData.mGeometry->GetBoundingBox(box); 
    1457         } 
    1458         else 
    1459         { 
    1460                 box.Initialize(); 
    1461                 RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end(); 
    1462  
    1463                 for(ri = tData.mRays->begin(); ri < ri_end; ++ ri) 
    1464                         box.Include((*ri).ExtrapTermination()); 
    1465         } 
    1466  
     867        AxisAlignedBox3 box = tData.mBoundingBox; 
     868                 
    1467869        int sAxis = 0; 
    1468         int bestAxis; 
    1469  
    1470         // if max cost ratio is exceeded, take split along longest axis instead 
    1471         const float maxCostRatioForArbitraryAxis = 0.9f; 
    1472  
    1473         if (mUseDrivingAxisForMaxCost) 
    1474                 bestAxis = box.Size().DrivingAxis(); 
    1475         else 
    1476                 bestAxis = -1; 
     870        int bestAxis = -1; 
    1477871 
    1478872#if 0 
    … …  
    1493887                sAxis = box.Size().DrivingAxis(); 
    1494888 
    1495                  
    1496         //Debug << "use special axis: " << useSpecialAxis << endl; 
    1497         //Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis(); 
    1498  
    1499         for (axis = 0; axis < 3 ; ++ axis) 
     889 
     890        for (int axis = 0; axis < 3 ; ++ axis) 
    1500891        { 
    1501892                if (!useSpecialAxis || (axis == sAxis)) 
    … …  
    1512903                                                                                        nPosition[axis]);                        
    1513904                        } 
    1514                          
    1515                         //-- split plane position is spatial median 
    1516  
    1517  
    1518                         // also use median split if cost ratio very low as 
    1519                         // there are not enough visibility cues 
    1520                         //if (!mUseCostHeuristics || (nCostRatio[axis] > maxCostRatioForHeur)) 
    1521                         else  
    1522                         { 
    1523  
     905                        else //-- split plane position is spatial median 
     906                        { 
    1524907                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 
    1525                                 Vector3 normal(0,0,0); normal[axis] = 1.0f; 
    1526  
    1527                                 // allows faster split because we have axis aligned kd tree boxes 
    1528                                 if (isKdNode) 
    1529                                 { 
    1530                                         nCostRatio[axis] = EvalAxisAlignedSplitCost(tData, 
    1531                                                                                                                                 box, 
    1532                                                                                                                                 axis, 
    1533                                                                                                                                 nPosition[axis], 
    1534                                                                                                                                 nProbFront[axis],  
    1535                                                                                                                                 nProbBack[axis]); 
    1536                                          
    1537                                         Vector3 pos; 
    1538                                          
    1539                                         // create back geometry from box 
    1540                                         // NOTE: the geometry is saved when possible 
    1541                                         pos = box.Max(); pos[axis] = nPosition[axis]; 
    1542                                         AxisAlignedBox3 bBox(box.Min(), pos); 
    1543                                         PolygonContainer fPolys; 
    1544                                         bBox.ExtractPolys(fPolys); 
    1545  
    1546                                         nBackGeom[axis] = new BspNodeGeometry(fPolys); 
    1547          
    1548                                         //-- create front geometry from box 
    1549                                         pos = box.Min(); pos[axis] = nPosition[axis]; 
    1550                                         AxisAlignedBox3 fBox(pos, box.Max()); 
    1551  
    1552                                         PolygonContainer bPolys; 
    1553                                         fBox.ExtractPolys(bPolys); 
    1554                                         nFrontGeom[axis] = new BspNodeGeometry(bPolys); 
    1555                                 } 
    1556                                 else 
    1557                                 { 
    1558                                         nFrontGeom[axis] = new BspNodeGeometry(); 
    1559                                         nBackGeom[axis] = new BspNodeGeometry(); 
    1560  
    1561                                         nCostRatio[axis] =  
    1562                                                 EvalSplitPlaneCost(Plane3(normal, nPosition[axis]),  
    1563                                                                                    tData, *nFrontGeom[axis], *nBackGeom[axis], 
    1564                                                                                    nProbFront[axis], nProbBack[axis]); 
    1565                                 } 
     908 
     909                                nCostRatio[axis] = EvalSplitCost(tData, 
     910                                                                                                 box, 
     911                                                                                                 axis, 
     912                                                                                                 nPosition[axis], 
     913                                                                                                 nProbFront[axis],  
     914                                                                                                 nProbBack[axis]); 
    1566915                        } 
    1567916                                                 
    1568                          
    1569                         if (mUseDrivingAxisForMaxCost) 
    1570                         { 
    1571                                 // we take longest axis split if cost ratio exceeds threshold 
    1572                                 if (nCostRatio[axis] < min(maxCostRatioForArbitraryAxis, nCostRatio[bestAxis])) 
    1573                                 { 
    1574                                         bestAxis = axis; 
    1575                                 } 
    1576                                 else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
    1577                                         Debug << "taking split along longest axis (" << bestAxis << ") instead of  (" << axis << ")" << endl; 
    1578                                  
    1579                         } 
    1580                         else 
    1581                         { 
    1582                                 if (bestAxis == -1) 
    1583                                 { 
    1584                                         bestAxis = axis; 
    1585                                 } 
    1586                                 else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
    1587                                 { 
    1588                                         bestAxis = axis; 
    1589                                 } 
     917                        if (bestAxis == -1) 
     918                        { 
     919                                bestAxis = axis; 
     920                        } 
     921                        else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
     922                        { 
     923                                bestAxis = axis; 
    1590924                        }  
    1591925                } 
    … …  
    1593927 
    1594928        //-- assign values 
    1595         axis = bestAxis; 
     929        plane.mAxis = bestAxis; 
    1596930        pFront = nProbFront[bestAxis]; 
    1597931        pBack = nProbBack[bestAxis]; 
    1598932 
    1599         // assign best split nodes geometry  
    1600         *frontGeom = nFrontGeom[bestAxis]; 
    1601         *backGeom = nBackGeom[bestAxis]; 
    1602  
    1603         // and delete other geometry 
    1604         DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]); 
    1605         DEL_PTR(nBackGeom[(bestAxis + 2) % 3]); 
    1606  
    1607         //-- split plane 
    1608     Vector3 normal(0,0,0); normal[bestAxis] = 1; 
    1609         plane = Plane3(normal, nPosition[bestAxis]); 
    1610  
    1611         //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl; 
    1612         //Debug << "!!!!!!!!!!!!!!" << endl; 
     933        //-- split plane position 
     934    plane.mPosition = nPosition[bestAxis]; 
     935 
    1613936        return nCostRatio[bestAxis]; 
    1614937} 
    1615938 
    1616939 
    1617 bool VspBspTree::SelectPlane(Plane3 &bestPlane, 
    1618                                                          BspLeaf *leaf, 
    1619                                                          VspBspTraversalData &data,                                                       
    1620                                                          VspBspTraversalData &frontData, 
    1621                                                          VspBspTraversalData &backData, 
    1622                                                          int &splitAxis) 
    1623 { 
    1624         // HACK matt: subdivide regularily to certain depth 
    1625         if (data.mDepth < 0)     
    1626         { 
    1627                 cout << "d: " << data.mDepth << endl; 
    1628                 // return axis aligned split 
    1629                 AxisAlignedBox3 box; 
    1630                 box.Initialize(); 
    1631          
    1632                 // create bounding box of region 
    1633                 data.mGeometry->GetBoundingBox(box); 
    1634          
    1635                 const int axis = box.Size().DrivingAxis(); 
    1636                 const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f; 
    1637  
    1638                 Vector3 norm(0,0,0); norm[axis] = 1.0f; 
    1639                 bestPlane = Plane3(norm, position); 
    1640                 splitAxis = axis; 
    1641                 return true; 
    1642         } 
    1643  
    1644         // simplest strategy: just take next polygon 
    1645         if (mSplitPlaneStrategy & RANDOM_POLYGON) 
    1646         { 
    1647         if (!data.mPolygons->empty()) 
    1648                 { 
    1649                         const int randIdx =  
    1650                                 (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1)); 
    1651                         Polygon3 *nextPoly = (*data.mPolygons)[randIdx]; 
    1652  
    1653                         bestPlane = nextPoly->GetSupportingPlane(); 
    1654                         return true; 
    1655                 } 
    1656         } 
    1657  
    1658         //-- use heuristics to find appropriate plane 
    1659  
    1660         // intermediate plane 
    1661         Plane3 plane; 
    1662         float lowestCost = MAX_FLOAT; 
    1663          
    1664         // decides if the first few splits should be only axisAligned 
    1665         const bool onlyAxisAligned  =  
    1666                 (mSplitPlaneStrategy & AXIS_ALIGNED) && 
    1667                 ((int)data.mRays->size() > mTermMinRaysForAxisAligned) && 
    1668                 ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned); 
    1669          
    1670         const int limit = onlyAxisAligned ? 0 :  
    1671                 Min((int)data.mPolygons->size(), mMaxPolyCandidates); 
    1672  
    1673         float candidateCost; 
    1674  
    1675         int maxIdx = (int)data.mPolygons->size(); 
    1676  
    1677         for (int i = 0; i < limit; ++ i) 
    1678         { 
    1679                 // the already taken candidates are stored behind maxIdx 
    1680                 // => assure that no index is taken twice 
    1681                 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 
    1682                 Polygon3 *poly = (*data.mPolygons)[candidateIdx]; 
    1683  
    1684                 // swap candidate to the end to avoid testing same plane 
    1685                 std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]); 
    1686                 //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)]; 
    1687  
    1688                 // evaluate current candidate 
    1689                 BspNodeGeometry fGeom, bGeom; 
    1690                 float fArea, bArea; 
    1691                 plane = poly->GetSupportingPlane(); 
    1692                 candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea); 
    1693                  
    1694                 if (candidateCost < lowestCost) 
    1695                 { 
    1696                         bestPlane = plane; 
    1697                         lowestCost = candidateCost; 
    1698                 } 
    1699         } 
    1700  
    1701         //-- evaluate axis aligned splits 
    1702         int axis; 
    1703         BspNodeGeometry *fGeom, *bGeom; 
    1704         float pFront, pBack; 
    1705  
    1706         candidateCost = 99999999.0f; 
    1707  
    1708         // option: axis aligned split only if no polygon available 
    1709         if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty()) 
    1710         { 
    1711                 candidateCost = SelectAxisAlignedPlane(plane,  
    1712                                                                                            data,  
    1713                                                                                            axis, 
    1714                                                                                            &fGeom,  
    1715                                                                                            &bGeom,  
    1716                                                                                            pFront,  
    1717                                                                                            pBack, 
    1718                                                                                            data.mIsKdNode);       
    1719         } 
    1720  
    1721         splitAxis = 3; 
    1722  
    1723         if (candidateCost < lowestCost) 
    1724         {        
    1725                 bestPlane = plane; 
    1726                 lowestCost = candidateCost; 
    1727                 splitAxis = axis; 
    1728          
    1729                 // assign already computed values 
    1730                 // we can do this because we always save the 
    1731                 // computed values from the axis aligned splits          
    1732  
    1733                 if (fGeom && bGeom) 
    1734                 { 
    1735                         frontData.mGeometry = fGeom; 
    1736                         backData.mGeometry = bGeom; 
    1737          
    1738                         frontData.mProbability = pFront; 
    1739                         backData.mProbability = pBack; 
    1740                 } 
    1741         } 
    1742         else 
    1743         { 
    1744                 DEL_PTR(fGeom); 
    1745                 DEL_PTR(bGeom); 
    1746         } 
    1747      
    1748 #ifdef _DEBUG 
    1749         Debug << "plane lowest cost: " << lowestCost << endl; 
    1750 #endif 
    1751  
    1752         // exeeded relative max cost ratio 
    1753         if (lowestCost > mTermMaxCostRatio) 
    1754         { 
    1755                 return false; 
    1756         } 
    1757  
    1758         return true; 
    1759 } 
    1760  
    1761  
    1762 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 
    1763 { 
    1764         const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
    1765  
    1766         const Vector3 minPt = rays[candidateIdx].ExtrapOrigin(); 
    1767         const Vector3 maxPt = rays[candidateIdx].ExtrapTermination(); 
    1768  
    1769         const Vector3 pt = (maxPt + minPt) * 0.5; 
    1770         const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir()); 
    1771  
    1772         return Plane3(normal, pt); 
    1773 } 
    1774  
    1775  
    1776 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const 
    1777 { 
    1778         Vector3 pt[3]; 
    1779  
    1780         int idx[3]; 
    1781         int cmaxT = 0; 
    1782         int cminT = 0; 
    1783         bool chooseMin = false; 
    1784  
    1785         for (int j = 0; j < 3; ++ j) 
    1786         { 
    1787                 idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1)); 
    1788  
    1789                 if (idx[j] >= (int)rays.size()) 
    1790                 { 
    1791                         idx[j] -= (int)rays.size(); 
    1792  
    1793                         chooseMin = (cminT < 2); 
    1794                 } 
    1795                 else 
    1796                         chooseMin = (cmaxT < 2); 
    1797  
    1798                 RayInfo rayInf = rays[idx[j]]; 
    1799                 pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination(); 
    1800         } 
    1801  
    1802         return Plane3(pt[0], pt[1], pt[2]); 
    1803 } 
    1804  
    1805  
    1806 Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const 
    1807 { 
    1808         Vector3 pt[3]; 
    1809  
    1810         int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
    1811         int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 
    1812  
    1813         // check if rays different 
    1814         if (idx1 == idx2) 
    1815                 idx2 = (idx2 + 1) % (int)rays.size(); 
    1816  
    1817         const RayInfo ray1 = rays[idx1]; 
    1818         const RayInfo ray2 = rays[idx2]; 
    1819  
    1820         // normal vector of the plane parallel to both lines 
    1821         const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir())); 
    1822  
    1823         // vector from line 1 to line 2 
    1824         const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin(); 
    1825  
    1826         // project vector on normal to get distance 
    1827         const float dist = DotProd(vd, norm); 
    1828  
    1829         // point on plane lies halfway between the two planes 
    1830         const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5; 
    1831  
    1832         return Plane3(norm, planePt); 
    1833 } 
    1834  
    1835  
    1836 inline void VspBspTree::GenerateUniqueIdsForPvs() 
     940inline void VspOspTree::GenerateUniqueIdsForPvs() 
    1837941{ 
    1838942        Intersectable::NewMail(); sBackId = Intersectable::sMailId; 
    … …  
    1842946 
    1843947 
    1844 float VspBspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane, 
    1845                                                                                  const VspBspTraversalData &data) const 
     948float VspOspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane, 
     949                                                                                 const VspOspTraversalData &data) const 
    1846950{ 
    1847951        float pvsFront = 0; 
    … …  
    1874978        BspNodeGeometry geomFront; 
    1875979        BspNodeGeometry geomBack; 
    1876  
    1877         // construct child geometry with regard to the candidate split plane 
    1878         data.mGeometry->SplitGeometry(geomFront, 
    1879                                                                   geomBack, 
    1880                                                                   candidatePlane, 
    1881                                                                   mBox, 
    1882                                                                   //0.0f); 
    1883                                                                   mEpsilon); 
    1884  
    1885         if (!mUseAreaForPvs) // use front and back cell areas to approximate volume 
    1886         { 
    1887                 pFront = geomFront.GetVolume(); 
    1888                 pBack = pOverall - pFront; 
    1889  
    1890                 // something is wrong with the volume 
    1891                 if ((pFront < 0.0) || (pBack < 0.0)) 
    1892                 { 
    1893                         Debug << "ERROR in volume:\n" 
    1894                                   << "volume f :" << pFront << " b: " << pBack << " p: " << pOverall  
    1895                                   << ", real volume f: " << pFront << " b: " << geomBack.GetVolume() 
    1896                                   << ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl; 
    1897                 } 
    1898         } 
    1899         else 
    1900         { 
    1901                 pFront = geomFront.GetArea(); 
    1902                 pBack = geomBack.GetArea(); 
    1903         } 
    1904          
     980         
     981        pFront = geomFront.GetVolume(); 
     982        pBack = pOverall - pFront; 
     983 
     984                 
    1905985 
    1906986        // -- pvs rendering heuristics 
    … …  
    19211001 
    19221002#if 1 
    1923         // take render cost of node into account 
     1003        // take render cost of node into account to avoid being stuck in a local minimum 
    19241004        const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume(); 
    1925         //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl; 
    1926         //return 0.5f * renderCostDecrease + 0.5f * normalizedOldRenderCost; 
    19271005        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost; 
    19281006#else 
    … …  
    19321010 
    19331011 
    1934 float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane, 
    1935                                                                          const VspBspTraversalData &data, 
    1936                                                                          BspNodeGeometry &geomFront, 
    1937                                                                          BspNodeGeometry &geomBack, 
    1938                                                                          float &pFront, 
    1939                                                                          float &pBack) const 
    1940 { 
    1941         float cost = 0; 
    1942  
    1943         float totalPvs = 0; 
    1944         float pvsFront = 0; 
    1945         float pvsBack = 0; 
    1946          
    1947         // probability that view point lies in back / front node 
    1948         float pOverall = 0; 
    1949         pFront = 0; 
    1950         pBack = 0; 
    1951  
    1952  
    1953         int limit; 
    1954         bool useRand; 
    1955  
    1956         // create unique ids for pvs heuristics 
    1957         GenerateUniqueIdsForPvs(); 
    1958  
    1959         // choose test rays randomly if too much 
    1960         if ((int)data.mRays->size() > mMaxTests) 
    1961         { 
    1962                 useRand = true; 
    1963                 limit = mMaxTests; 
    1964         } 
    1965         else 
    1966         { 
    1967                 useRand = false; 
    1968                 limit = (int)data.mRays->size(); 
    1969         } 
    1970          
    1971         for (int i = 0; i < limit; ++ i) 
    1972         { 
    1973                 const int testIdx = useRand ?  
    1974                         (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i; 
    1975                 RayInfo rayInf = (*data.mRays)[testIdx]; 
    1976  
    1977                 float t; 
    1978                 VssRay *ray = rayInf.mRay; 
    1979                 const int cf = rayInf.ComputeRayIntersection(candidatePlane, t); 
    1980  
    1981                 // find front and back pvs for origing and termination object 
    1982                 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs); 
    1983                 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 
    1984         } 
    1985  
    1986         // construct child geometry with regard to the candidate split plane 
    1987         bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront, 
    1988                                                                                                                   geomBack, 
    1989                                                                                                                   candidatePlane, 
    1990                                                                                                                   mBox, 
    1991                                                                                                                   //0.0f); 
    1992                                                                                                                   mEpsilon); 
    1993  
    1994         pOverall = data.mProbability; 
    1995  
    1996         if (!mUseAreaForPvs) // use front and back cell areas to approximate volume 
    1997         { 
    1998                 pFront = geomFront.GetVolume(); 
    1999                 pBack = pOverall - pFront; 
    2000                  
    2001                 // HACK: precision issues possible for unbalanced split => don't take this split! 
    2002                 if (1 &&  
    2003                         (!splitSuccessFull || (pFront <= 0) || (pBack <= 0) ||  
    2004                         !geomFront.Valid() || !geomBack.Valid())) 
    2005                 { 
    2006                         //Debug << "error f: " << pFront << " b: " << pBack << endl; 
    2007                         // high penalty for this split 
    2008                         return 99999.9f; 
    2009                 } 
    2010         } 
    2011         else 
    2012         { 
    2013                 pFront = geomFront.GetArea(); 
    2014                 pBack = geomBack.GetArea(); 
    2015         } 
    2016          
    2017  
    2018         // -- pvs rendering heuristics 
    2019         const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 
    2020         const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 
    2021  
    2022         // only render cost heuristics or combined with standard deviation 
    2023         const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit); 
    2024     const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit); 
    2025         const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit); 
    2026                          
    2027         const float oldRenderCost = pOverall * penaltyOld; 
    2028         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack; 
    2029  
    2030         float oldCost, newCost; 
    2031  
    2032         // only render cost 
    2033         if (1) 
    2034         { 
    2035                 oldCost = oldRenderCost; 
    2036                 newCost = newRenderCost; 
    2037         } 
    2038         else // also considering standard deviation 
    2039         { 
    2040                 // standard deviation is difference of back and front pvs 
    2041                 const float expectedCost = 0.5f * (penaltyFront + penaltyBack); 
    2042  
    2043                 const float newDeviation = 0.5f *  
    2044                         fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost); 
    2045  
    2046                 const float oldDeviation = penaltyOld; 
    2047  
    2048                 newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation; 
    2049                 oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation; 
    2050         } 
    2051  
    2052         cost += mPvsFactor * newCost / (oldCost + Limits::Small); 
    2053                  
    2054  
    2055 #ifdef _DEBUG 
    2056         Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall 
    2057                   << " frontpvs: " << pvsFront << " pFront: " << pFront 
    2058                   << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl; 
    2059         Debug << "cost: " << cost << endl; 
    2060 #endif 
    2061  
    2062         return cost; 
    2063 } 
    2064  
    2065  
    2066 int VspBspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,  
    2067                                                                                 ViewCellContainer &viewCells) const 
    2068 { 
    2069         stack<bspNodePair> nodeStack; 
    2070         BspNodeGeometry *rgeom = new BspNodeGeometry(); 
    2071  
    2072         ConstructGeometry(mRoot, *rgeom); 
    2073  
    2074         nodeStack.push(bspNodePair(mRoot, rgeom)); 
    2075    
    2076         ViewCell::NewMail(); 
    2077  
    2078         while (!nodeStack.empty())  
    2079         { 
    2080                 BspNode *node = nodeStack.top().first; 
    2081                 BspNodeGeometry *geom = nodeStack.top().second; 
    2082                 nodeStack.pop(); 
    2083  
    2084                 const int side = geom->ComputeIntersection(box); 
    2085                  
    2086                 switch (side) 
    2087                 { 
    2088                 case -1: 
    2089                         // node geometry is contained in box 
    2090                         CollectViewCells(node, true, viewCells, true); 
    2091                         break; 
    2092  
    2093                 case 0: 
    2094                         if (node->IsLeaf()) 
    2095                         { 
    2096                                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 
    2097                          
    2098                                 if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid()) 
    2099                                 { 
    2100                                         leaf->GetViewCell()->Mail(); 
    2101                                         viewCells.push_back(leaf->GetViewCell()); 
    2102                                 } 
    2103                         } 
    2104                         else  
    2105                         { 
    2106                                 BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    2107                          
    2108                                 BspNode *first = interior->GetFront(); 
    2109                                 BspNode *second = interior->GetBack(); 
    2110              
    2111                                 BspNodeGeometry *firstGeom = new BspNodeGeometry(); 
    2112                                 BspNodeGeometry *secondGeom = new BspNodeGeometry(); 
    2113  
    2114                                 geom->SplitGeometry(*firstGeom, 
    2115                                                                         *secondGeom, 
    2116                                                                         interior->GetPlane(), 
    2117                                                                         mBox, 
    2118                                                                         //0.0000001f); 
    2119                                                                         mEpsilon); 
    2120  
    2121                                 nodeStack.push(bspNodePair(first, firstGeom)); 
    2122                                 nodeStack.push(bspNodePair(second, secondGeom)); 
    2123                         } 
    2124                          
    2125                         break; 
    2126                 default: 
    2127                         // default: cull 
    2128                         break; 
    2129                 } 
    2130                  
    2131                 DEL_PTR(geom); 
    2132                  
    2133         } 
    2134  
    2135         return (int)viewCells.size(); 
    2136 } 
    2137  
    2138  
    2139 float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data, 
    2140                                                                                    const AxisAlignedBox3 &box, 
    2141                                                                                    const int axis, 
    2142                                                                                    const float &position,                                                                                  
    2143                                                                                    float &pFront, 
    2144                                                                                    float &pBack) const 
     1012 
     1013float VspOspTree::EvalSplitCost(const VspOspTraversalData &data, 
     1014                                                                const AxisAlignedBox3 &box, 
     1015                                                                const int axis, 
     1016                                                                const float &position,                                                                             
     1017                                                                float &pFront, 
     1018                                                                float &pBack) const 
    21451019{ 
    21461020        float pvsTotal = 0; 
    … …  
    21581032        for(rit = data.mRays->begin(); rit != rit_end; ++ rit) 
    21591033        { 
    2160                 //if (!(*rit).mRay->IsActive()) continue; 
    2161  
    21621034                // determine the side of this ray with respect to the plane 
    21631035                float t; 
    … …  
    21751047                 
    21761048        pOverall = data.mProbability; 
    2177  
    2178         if (!mUseAreaForPvs) 
    2179         {   // volume 
    2180                 pBack = pFront = pOverall * 0.5f; 
    2181                  
    2182 #if 0 
    2183                 // box length substitute for probability 
    2184                 const float minBox = box.Min(axis); 
    2185                 const float maxBox = box.Max(axis); 
    2186  
    2187                 pBack = position - minBox; 
    2188                 pFront = maxBox - position; 
    2189                 pOverall = maxBox - minBox; 
    2190 #endif 
    2191         } 
    2192         else //-- area substitute for probability 
    2193         { 
    2194                 const int axis2 = (axis + 1) % 3; 
    2195                 const int axis3 = (axis + 2) % 3; 
    2196  
    2197                 const float faceArea =  
    2198                         (box.Max(axis2) - box.Min(axis2)) * 
    2199                         (box.Max(axis3) - box.Min(axis3)); 
    2200  
    2201                 pBack = pFront = pOverall * 0.5f + faceArea; 
    2202         } 
    2203  
     1049        pBack = pFront = pOverall * 0.5f; 
     1050         
     1051         
    22041052#ifdef _DEBUG 
    22051053        Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl; 
    … …  
    22151063 
    22161064 
    2217 void VspBspTree::AddObjToPvs(Intersectable *obj, 
     1065void VspOspTree::AddObjToPvs(Intersectable *obj, 
    22181066                                                         const int cf, 
    22191067                                                         float &frontPvs, 
    … …  
    22681116 
    22691117 
    2270 void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,  
     1118void VspOspTree::CollectLeaves(vector<BspLeaf *> &leaves,  
    22711119                                                           const bool onlyUnmailed, 
    22721120                                                           const int maxPvsSize) const 
    … …  
    23021150 
    23031151 
    2304 AxisAlignedBox3 VspBspTree::GetBoundingBox() const 
     1152AxisAlignedBox3 VspOspTree::GetBoundingBox() const 
    23051153{ 
    23061154        return mBox; 
    … …  
    23081156 
    23091157 
    2310 BspNode *VspBspTree::GetRoot() const 
     1158BspNode *VspOspTree::GetRoot() const 
    23111159{ 
    23121160        return mRoot; 
    … …  
    23141162 
    23151163 
    2316 void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data) 
     1164void VspOspTree::EvaluateLeafStats(const VspOspTraversalData &data) 
    23171165{ 
    23181166        // the node became a leaf -> evaluate stats for leafs 
    … …  
    23701218 
    23711219 
    2372 int VspBspTree::CastRay(Ray &ray) 
     1220int VspOspTree::CastRay(Ray &ray) 
    23731221{ 
    23741222        int hits = 0; 
    … …  
    24391287                        if (!leaf->GetViewCell()->Mailed()) 
    24401288                        { 
    2441                                 //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf)); 
     1289                                //ray.bspIntersections.push_back(Ray::VspOspIntersection(maxt, leaf)); 
    24421290                                leaf->GetViewCell()->Mail(); 
    24431291                                ++ hits; 
    … …  
    24681316 
    24691317 
    2470 void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const 
     1318void VspOspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const 
    24711319{ 
    24721320        ViewCell::NewMail(); 
    … …  
    24761324 
    24771325 
    2478 void VspBspTree::CollapseViewCells() 
     1326void VspOspTree::CollapseViewCells() 
    24791327{ 
    24801328// TODO 
    … …  
    25311379 
    25321380 
    2533 void VspBspTree::CollectRays(VssRayContainer &rays) 
     1381void VspOspTree::CollectRays(VssRayContainer &rays) 
    25341382{ 
    25351383        vector<BspLeaf *> leaves; 
    … …  
    25481396 
    25491397 
    2550 void VspBspTree::ValidateTree() 
     1398void VspOspTree::ValidateTree() 
    25511399{ 
    25521400        stack<BspNode *> nodeStack; 
    … …  
    25911439 
    25921440 
    2593 void VspBspTree::CollectViewCells(BspNode *root, 
     1441void VspOspTree::CollectViewCells(BspNode *root, 
    25941442                                                                  bool onlyValid, 
    25951443                                                                  ViewCellContainer &viewCells, 
    … …  
    26351483 
    26361484 
    2637 void VspBspTree::PreprocessPolygons(PolygonContainer &polys) 
    2638 { 
    2639         // preprocess: throw out polygons coincident to the view space box (not needed) 
    2640         PolygonContainer boxPolys; 
    2641         mBox.ExtractPolys(boxPolys); 
    2642         vector<Plane3> boxPlanes; 
    2643  
    2644         PolygonContainer::iterator pit, pit_end = boxPolys.end(); 
    2645  
    2646         // extract planes of box 
    2647         // TODO: can be done more elegantly than first extracting polygons 
    2648         // and take their planes 
    2649         for (pit = boxPolys.begin(); pit != pit_end; ++ pit) 
    2650         { 
    2651                 boxPlanes.push_back((*pit)->GetSupportingPlane()); 
    2652         } 
    2653  
    2654         pit_end = polys.end(); 
    2655  
    2656         for (pit = polys.begin(); pit != pit_end; ++ pit) 
    2657         { 
    2658                 vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end(); 
    2659                  
    2660                 for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit) 
    2661                 { 
    2662                         const int cf = (*pit)->ClassifyPlane(*bit, mEpsilon); 
    2663  
    2664                         if (cf == Polygon3::COINCIDENT) 
    2665                         { 
    2666                                 DEL_PTR(*pit); 
    2667                                 //Debug << "coincident!!" << endl; 
    2668                         } 
    2669                 } 
    2670         } 
    2671  
    2672         // remove deleted entries 
    2673         for (int i = 0; i < (int)polys.size(); ++ i) 
    2674         { 
    2675                 while (!polys[i] && (i < (int)polys.size())) 
    2676                 { 
    2677                         swap(polys[i], polys.back()); 
    2678                         polys.pop_back(); 
    2679                 } 
    2680         } 
    2681 } 
    2682  
    2683  
    2684 float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const 
    2685 { 
    2686         float len = 0; 
    2687  
    2688         RayInfoContainer::const_iterator it, it_end = rays.end(); 
    2689  
    2690         for (it = rays.begin(); it != it_end; ++ it) 
    2691                 len += (*it).SegmentLength(); 
    2692  
    2693         return len; 
    2694 } 
    2695  
    2696  
    2697 int VspBspTree::SplitRays(const Plane3 &plane, 
     1485int VspOspTree::SplitRays(const Plane3 &plane, 
    26981486                                                  RayInfoContainer &rays, 
    26991487                                                  RayInfoContainer &frontRays, 
    … …  
    27251513                        { 
    27261514                                //-- split ray 
    2727                                 //  test if start point behind or in front of plane 
     1515                                //-- test if start point behind or in front of plane 
    27281516                                const int side = plane.Side(bRay.ExtrapOrigin()); 
    27291517 
    … …  
    27501538 
    27511539 
    2752 void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const 
    2753 { 
    2754         BspNode *lastNode; 
    2755  
    2756         do 
    2757         { 
    2758                 lastNode = n; 
    2759  
    2760                 // want to get planes defining geometry of this node => don't take 
    2761                 // split plane of node itself 
    2762                 n = n->GetParent(); 
    2763  
    2764                 if (n) 
    2765                 { 
    2766                         BspInterior *interior = dynamic_cast<BspInterior *>(n); 
    2767                         Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane(); 
    2768  
    2769             if (interior->GetBack() != lastNode) 
    2770                                 halfSpace.ReverseOrientation(); 
    2771  
    2772                         halfSpaces.push_back(halfSpace); 
    2773                 } 
    2774         } 
    2775         while (n); 
    2776 } 
    2777  
    2778  
    2779 void VspBspTree::ConstructGeometry(BspNode *n, 
    2780                                                                    BspNodeGeometry &geom) const 
    2781 { 
    2782         vector<Plane3> halfSpaces; 
    2783         ExtractHalfSpaces(n, halfSpaces); 
    2784  
    2785         PolygonContainer candidatePolys; 
    2786         vector<Plane3> candidatePlanes; 
    2787  
    2788         vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end(); 
    2789  
    2790         // bounded planes are added to the polygons 
    2791         for (pit = halfSpaces.begin(); pit != pit_end; ++ pit) 
    2792         { 
    2793                 Polygon3 *p = GetBoundingBox().CrossSection(*pit); 
    2794  
    2795                 if (p->Valid(mEpsilon)) 
    2796                 { 
    2797                         candidatePolys.push_back(p); 
    2798                         candidatePlanes.push_back(*pit); 
    2799                 } 
    2800         } 
    2801  
    2802         // add faces of bounding box (also could be faces of the cell) 
    2803         for (int i = 0; i < 6; ++ i) 
    2804         { 
    2805                 VertexContainer vertices; 
    2806  
    2807                 for (int j = 0; j < 4; ++ j) 
    2808                         vertices.push_back(mBox.GetFace(i).mVertices[j]); 
    2809  
    2810                 Polygon3 *poly = new Polygon3(vertices); 
    2811  
    2812                 candidatePolys.push_back(poly); 
    2813                 candidatePlanes.push_back(poly->GetSupportingPlane()); 
    2814         } 
    2815  
    2816         for (int i = 0; i < (int)candidatePolys.size(); ++ i) 
    2817         { 
    2818                 // polygon is split by all other planes 
    2819                 for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j) 
    2820                 { 
    2821                         if (i == j) // polygon and plane are coincident 
    2822                                 continue; 
    2823  
    2824                         VertexContainer splitPts; 
    2825                         Polygon3 *frontPoly, *backPoly; 
    2826  
    2827                         const int cf = 
    2828                                 candidatePolys[i]->ClassifyPlane(halfSpaces[j], 
    2829                                                                                                  mEpsilon); 
    2830  
    2831                         switch (cf) 
    2832                         { 
    2833                                 case Polygon3::SPLIT: 
    2834                                         frontPoly = new Polygon3(); 
    2835                                         backPoly = new Polygon3(); 
    2836  
    2837                                         candidatePolys[i]->Split(halfSpaces[j], 
    2838                                                                                          *frontPoly, 
    2839                                                                                          *backPoly, 
    2840                                                                                          mEpsilon); 
    2841  
    2842                                         DEL_PTR(candidatePolys[i]); 
    2843  
    2844                                         if (backPoly->Valid(mEpsilon)) 
    2845                                                 candidatePolys[i] = backPoly; 
    2846                                         else 
    2847                                                 DEL_PTR(backPoly); 
    2848  
    2849                                         // outside, don't need this 
    2850                                         DEL_PTR(frontPoly); 
    2851                                         break; 
    2852                                 // polygon outside of halfspace 
    2853                                 case Polygon3::FRONT_SIDE: 
    2854                                         DEL_PTR(candidatePolys[i]); 
    2855                                         break; 
    2856                                 // just take polygon as it is 
    2857                                 case Polygon3::BACK_SIDE: 
    2858                                 case Polygon3::COINCIDENT: 
    2859                                 default: 
    2860                                         break; 
    2861                         } 
    2862                 } 
    2863  
    2864                 if (candidatePolys[i]) 
    2865                 { 
    2866                         geom.Add(candidatePolys[i], candidatePlanes[i]); 
    2867                         //      geom.mPolys.push_back(candidates[i]); 
    2868                 } 
    2869         } 
    2870 } 
    2871  
    2872  
    2873 void VspBspTree::ConstructGeometry(ViewCell *vc,  
    2874                                                                    BspNodeGeometry &vcGeom) const 
    2875 { 
    2876         ViewCellContainer leaves; 
    2877          
    2878         mViewCellsTree->CollectLeaves(vc, leaves); 
    2879  
    2880         ViewCellContainer::const_iterator it, it_end = leaves.end(); 
    2881  
    2882         for (it = leaves.begin(); it != it_end; ++ it) 
    2883         { 
    2884                 BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf; 
    2885                  
    2886                 ConstructGeometry(l, vcGeom); 
    2887         } 
    2888 } 
    2889  
    2890  
    2891 int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
     1540int VspOspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors, 
    28921541                                                          const bool onlyUnmailed) const 
    28931542{ 
    2894         stack<bspNodePair> nodeStack; 
    2895          
    2896         BspNodeGeometry nodeGeom; 
    2897         ConstructGeometry(n, nodeGeom); 
    2898 //      const float eps = 0.5f; 
    2899         const float eps = 0.01f; 
    2900         // split planes from the root to this node 
    2901         // needed to verify that we found neighbor leaf 
    2902         // TODO: really needed? 
    2903         vector<Plane3> halfSpaces; 
    2904         ExtractHalfSpaces(n, halfSpaces); 
    2905  
    2906  
    2907         BspNodeGeometry *rgeom = new BspNodeGeometry(); 
    2908         ConstructGeometry(mRoot, *rgeom); 
    2909  
    2910         nodeStack.push(bspNodePair(mRoot, rgeom)); 
    2911  
    2912         while (!nodeStack.empty()) 
    2913         { 
    2914                 BspNode *node = nodeStack.top().first; 
    2915                 BspNodeGeometry *geom = nodeStack.top().second; 
    2916          
    2917                 nodeStack.pop(); 
    2918  
    2919                 if (node->IsLeaf()) 
    2920                 { 
    2921                         // test if this leaf is in valid view space 
    2922                         if (node->TreeValid() && 
    2923                                 (node != n) &&  
    2924                                 (!onlyUnmailed || !node->Mailed())) 
    2925                         { 
    2926                                 bool isAdjacent = true; 
    2927  
    2928                                 if (1) 
    2929                                 { 
    2930                                         // test all planes of current node if still adjacent 
    2931                                         for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i) 
    2932                                         { 
    2933                                                 const int cf = 
    2934                                                         Polygon3::ClassifyPlane(geom->GetPolys(), 
    2935                                                                                                         halfSpaces[i], 
    2936                                                                                                         eps); 
    2937  
    2938                                                 if (cf == Polygon3::FRONT_SIDE) 
    2939                                                 { 
    2940                                                         isAdjacent = false; 
    2941                                                 } 
    2942                                         } 
    2943                                 } 
    2944                                 else 
    2945                                 { 
    2946                                         // TODO: why is this wrong?? 
    2947                                         // test all planes of current node if still adjacent 
    2948                                         for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i) 
    2949                                         { 
    2950                                                 Polygon3 *poly = nodeGeom.GetPolys()[i]; 
    2951  
    2952                                                 const int cf = 
    2953                                                         Polygon3::ClassifyPlane(geom->GetPolys(), 
    2954                                                                                                         poly->GetSupportingPlane(), 
    2955                                                                                                         eps); 
    2956  
    2957                                                 if (cf == Polygon3::FRONT_SIDE) 
    2958                                                 { 
    2959                                                         isAdjacent = false; 
    2960                                                 } 
    2961                                         } 
    2962                                 } 
    2963                                 // neighbor was found 
    2964                                 if (isAdjacent) 
    2965                                 {        
    2966                                         neighbors.push_back(dynamic_cast<BspLeaf *>(node)); 
    2967                                 } 
    2968                         } 
    2969                 } 
    2970                 else 
    2971                 { 
    2972                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    2973  
    2974                         const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(), 
    2975                                                                                                    interior->GetPlane(), 
    2976                                                                                                    eps); 
    2977                          
    2978                         BspNode *front = interior->GetFront(); 
    2979                         BspNode *back = interior->GetBack(); 
    2980              
    2981                         BspNodeGeometry *fGeom = new BspNodeGeometry(); 
    2982                         BspNodeGeometry *bGeom = new BspNodeGeometry(); 
    2983  
    2984                         geom->SplitGeometry(*fGeom, 
    2985                                                                 *bGeom, 
    2986                                                                 interior->GetPlane(), 
    2987                                                                 mBox, 
    2988                                                                 //0.0000001f); 
    2989                                                                 eps); 
    2990                  
    2991                         if (cf == Polygon3::BACK_SIDE) 
    2992                         { 
    2993                                 nodeStack.push(bspNodePair(interior->GetBack(), bGeom)); 
    2994                                 DEL_PTR(fGeom); 
    2995                         } 
    2996                         else 
    2997                         { 
    2998                                 if (cf == Polygon3::FRONT_SIDE) 
    2999                                 { 
    3000                                         nodeStack.push(bspNodePair(interior->GetFront(), fGeom)); 
    3001                                         DEL_PTR(bGeom); 
    3002                                 } 
    3003                                 else 
    3004                                 {       // random decision 
    3005                                         nodeStack.push(bspNodePair(front, fGeom)); 
    3006                                         nodeStack.push(bspNodePair(back, bGeom)); 
    3007                                 } 
    3008                         } 
    3009                 } 
    3010          
    3011                 DEL_PTR(geom); 
    3012         } 
    3013  
    3014         return (int)neighbors.size(); 
    3015 } 
    3016  
    3017  
    3018  
    3019 int VspBspTree::FindApproximateNeighbors(BspNode *n,  
    3020                                                                                  vector<BspLeaf *> &neighbors, 
    3021                                                                                  const bool onlyUnmailed) const 
    3022 { 
    3023         stack<bspNodePair> nodeStack; 
    3024          
    3025         BspNodeGeometry nodeGeom; 
    3026         ConstructGeometry(n, nodeGeom); 
    3027          
    3028         float eps = 0.01f; 
    3029         // split planes from the root to this node 
    3030         // needed to verify that we found neighbor leaf 
    3031         // TODO: really needed? 
    3032         vector<Plane3> halfSpaces; 
    3033         ExtractHalfSpaces(n, halfSpaces); 
    3034  
    3035  
    3036         BspNodeGeometry *rgeom = new BspNodeGeometry(); 
    3037         ConstructGeometry(mRoot, *rgeom); 
    3038  
    3039         nodeStack.push(bspNodePair(mRoot, rgeom)); 
    3040  
    3041         while (!nodeStack.empty()) 
    3042         { 
    3043                 BspNode *node = nodeStack.top().first; 
    3044                 BspNodeGeometry *geom = nodeStack.top().second; 
    3045          
    3046                 nodeStack.pop(); 
    3047  
    3048                 if (node->IsLeaf()) 
    3049                 { 
    3050                         // test if this leaf is in valid view space 
    3051                         if (node->TreeValid() && 
    3052                                 (node != n) &&  
    3053                                 (!onlyUnmailed || !node->Mailed())) 
    3054                         { 
    3055                                 bool isAdjacent = true; 
    3056  
    3057                                 // neighbor was found 
    3058                                 if (isAdjacent) 
    3059                                 {        
    3060                                         neighbors.push_back(dynamic_cast<BspLeaf *>(node)); 
    3061                                 } 
    3062                         } 
    3063                 } 
    3064                 else 
    3065                 { 
    3066                         BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    3067  
    3068                         const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(), 
    3069                                                                                                    interior->GetPlane(), 
    3070                                                                                                    eps); 
    3071                          
    3072                         BspNode *front = interior->GetFront(); 
    3073                         BspNode *back = interior->GetBack(); 
    3074              
    3075                         BspNodeGeometry *fGeom = new BspNodeGeometry(); 
    3076                         BspNodeGeometry *bGeom = new BspNodeGeometry(); 
    3077  
    3078                         geom->SplitGeometry(*fGeom, 
    3079                                                                 *bGeom, 
    3080                                                                 interior->GetPlane(), 
    3081                                                                 mBox, 
    3082                                                                 //0.0000001f); 
    3083                                                                 eps); 
    3084                  
    3085                         if (cf == Polygon3::BACK_SIDE) 
    3086                         { 
    3087                                 nodeStack.push(bspNodePair(interior->GetBack(), bGeom)); 
    3088                                 DEL_PTR(fGeom); 
    3089                                 } 
    3090                         else 
    3091                         { 
    3092                                 if (cf == Polygon3::FRONT_SIDE) 
    3093                                 { 
    3094                                         nodeStack.push(bspNodePair(interior->GetFront(), fGeom)); 
    3095                                         DEL_PTR(bGeom); 
    3096                                 } 
    3097                                 else 
    3098                                 {       // random decision 
    3099                                         nodeStack.push(bspNodePair(front, fGeom)); 
    3100                                         nodeStack.push(bspNodePair(back, bGeom)); 
    3101                                 } 
    3102                         } 
    3103                 } 
    3104          
    3105                 DEL_PTR(geom); 
    3106         } 
    3107  
    3108         return (int)neighbors.size(); 
    3109 } 
    3110  
    3111  
    3112  
    3113 BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace) 
    3114 { 
     1543        // TODO 
     1544        return 0; 
     1545} 
     1546 
     1547 
     1548BspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &halfspace) 
     1549{ 
     1550#if TODO 
    31151551    stack<BspNode *> nodeStack; 
    31161552        nodeStack.push(mRoot); 
    … …  
    31571593                } 
    31581594        } 
    3159  
     1595#endif 
    31601596        return NULL; 
    31611597} 
    31621598 
    31631599 
    3164 BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed) 
     1600BspLeaf *VspOspTree::GetRandomLeaf(const bool onlyUnmailed) 
    31651601{ 
    31661602        stack<BspNode *> nodeStack; 
    … …  
    31981634 
    31991635 
    3200 int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const 
     1636int VspOspTree::ComputePvsSize(const RayInfoContainer &rays) const 
    32011637{ 
    32021638        int pvsSize = 0; 
    … …  
    32321668 
    32331669 
    3234 float VspBspTree::GetEpsilon() const 
     1670float VspOspTree::GetEpsilon() const 
    32351671{ 
    32361672        return mEpsilon; 
    … …  
    32381674 
    32391675 
    3240 int VspBspTree::SplitPolygons(const Plane3 &plane, 
    3241                                                           PolygonContainer &polys, 
    3242                                                           PolygonContainer &frontPolys, 
    3243                                                           PolygonContainer &backPolys, 
    3244                                                           PolygonContainer &coincident) const 
    3245 { 
    3246         int splits = 0; 
    3247  
    3248         PolygonContainer::const_iterator it, it_end = polys.end(); 
    3249  
    3250         for (it = polys.begin(); it != polys.end(); ++ it)       
    3251         { 
    3252                 Polygon3 *poly = *it; 
    3253  
    3254                 // classify polygon 
    3255                 const int cf = poly->ClassifyPlane(plane, mEpsilon); 
    3256  
    3257                 switch (cf) 
    3258                 { 
    3259                         case Polygon3::COINCIDENT: 
    3260                                 coincident.push_back(poly); 
    3261                                 break; 
    3262                         case Polygon3::FRONT_SIDE: 
    3263                                 frontPolys.push_back(poly); 
    3264                                 break; 
    3265                         case Polygon3::BACK_SIDE: 
    3266                                 backPolys.push_back(poly); 
    3267                                 break; 
    3268                         case Polygon3::SPLIT: 
    3269                                 backPolys.push_back(poly); 
    3270                                 frontPolys.push_back(poly); 
    3271                                 ++ splits; 
    3272                                 break; 
    3273                         default: 
    3274                 Debug << "SHOULD NEVER COME HERE\n"; 
    3275                                 break; 
    3276                 } 
    3277         } 
    3278  
    3279         return splits; 
    3280 } 
    3281  
    3282  
    3283 int VspBspTree::CastLineSegment(const Vector3 &origin, 
     1676 
     1677int VspOspTree::CastLineSegment(const Vector3 &origin, 
    32841678                                                                const Vector3 &termination, 
    32851679                                                                ViewCellContainer &viewcells) 
    … …  
    33871781 
    33881782 
    3389  
    3390 int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const 
    3391 { 
    3392         std::deque<BspNode *> path1; 
    3393         BspNode *p1 = n1; 
    3394  
    3395         // create path from node 1 to root 
    3396         while (p1) 
    3397         { 
    3398                 if (p1 == n2) // second node on path 
    3399                         return (int)path1.size(); 
    3400  
    3401                 path1.push_front(p1); 
    3402                 p1 = p1->GetParent(); 
    3403         } 
    3404  
    3405         int depth = n2->GetDepth(); 
    3406         int d = depth; 
    3407  
    3408         BspNode *p2 = n2; 
    3409  
    3410         // compare with same depth 
    3411         while (1) 
    3412         { 
    3413                 if ((d < (int)path1.size()) && (p2 == path1[d])) 
    3414                         return (depth - d) + ((int)path1.size() - 1 - d); 
    3415  
    3416                 -- d; 
    3417                 p2 = p2->GetParent(); 
    3418         } 
    3419  
    3420         return 0; // never come here 
    3421 } 
    3422  
    3423  
    3424 BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed) 
     1783BspNode *VspOspTree::CollapseTree(BspNode *node, int &collapsed) 
    34251784{ 
    34261785// TODO 
    … …  
    34641823 
    34651824 
    3466 int VspBspTree::CollapseTree() 
     1825int VspOspTree::CollapseTree() 
    34671826{ 
    34681827        int collapsed = 0; 
    … …  
    34781837 
    34791838 
    3480 void VspBspTree::RepairViewCellsLeafLists() 
     1839void VspOspTree::RepairViewCellsLeafLists() 
    34811840{ 
    34821841// TODO 
    … …  
    35211880 
    35221881 
    3523 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair; 
    3524  
    3525  
    3526 int VspBspTree::CastBeam(Beam &beam) 
    3527 { 
    3528     stack<bspNodePair> nodeStack; 
    3529         BspNodeGeometry *rgeom = new BspNodeGeometry(); 
    3530         ConstructGeometry(mRoot, *rgeom); 
    3531  
    3532         nodeStack.push(bspNodePair(mRoot, rgeom)); 
    3533    
    3534         ViewCell::NewMail(); 
    3535  
    3536         while (!nodeStack.empty())  
    3537         { 
    3538                 BspNode *node = nodeStack.top().first; 
    3539                 BspNodeGeometry *geom = nodeStack.top().second; 
    3540                 nodeStack.pop(); 
    3541                  
    3542                 AxisAlignedBox3 box; 
    3543                 geom->GetBoundingBox(box); 
    3544  
    3545                 const int side = beam.ComputeIntersection(box); 
    3546                  
    3547                 switch (side)  
    3548                 { 
    3549                 case -1: 
    3550                         CollectViewCells(node, true, beam.mViewCells, true); 
    3551                         break; 
    3552                 case 0: 
    3553                          
    3554                         if (node->IsLeaf()) 
    3555                         { 
    3556                                 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 
    3557                          
    3558                                 if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid()) 
    3559                                 { 
    3560                                         leaf->GetViewCell()->Mail(); 
    3561                                         beam.mViewCells.push_back(leaf->GetViewCell()); 
    3562                                 } 
    3563                         } 
    3564                         else  
    3565                         { 
    3566                                 BspInterior *interior = dynamic_cast<BspInterior *>(node); 
    3567                          
    3568                                 BspNode *first = interior->GetFront(); 
    3569                                 BspNode *second = interior->GetBack(); 
    3570              
    3571                                 BspNodeGeometry *firstGeom = new BspNodeGeometry(); 
    3572                                 BspNodeGeometry *secondGeom = new BspNodeGeometry(); 
    3573  
    3574                                 geom->SplitGeometry(*firstGeom, 
    3575                                                                         *secondGeom, 
    3576                                                                         interior->GetPlane(), 
    3577                                                                         mBox, 
    3578                                                                         //0.0000001f); 
    3579                                                                         mEpsilon); 
    3580  
    3581                                 // decide on the order of the nodes 
    3582                                 if (DotProd(beam.mPlanes[0].mNormal,  
    3583                                         interior->GetPlane().mNormal) > 0) 
    3584                                 { 
    3585                                         swap(first, second); 
    3586                                         swap(firstGeom, secondGeom); 
    3587                                 } 
    3588  
    3589                                 nodeStack.push(bspNodePair(first, firstGeom)); 
    3590                                 nodeStack.push(bspNodePair(second, secondGeom)); 
    3591                         } 
    3592                          
    3593                         break; 
    3594                 default: 
    3595                         // default: cull 
    3596                         break; 
    3597                 } 
    3598                  
    3599                 DEL_PTR(geom); 
    3600                  
    3601         } 
    3602  
    3603         return (int)beam.mViewCells.size(); 
    3604 } 
    3605  
    3606  
    3607 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm) 
    3608 { 
    3609         mViewCellsManager = vcm; 
    3610 } 
    3611  
    3612  
    3613 int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves, 
    3614                                                                            vector<MergeCandidate> &candidates) 
    3615 { 
    3616         BspLeaf::NewMail(); 
    3617          
    3618         vector<BspLeaf *>::const_iterator it, it_end = leaves.end(); 
    3619  
    3620         int numCandidates = 0; 
    3621  
    3622         // find merge candidates and push them into queue 
    3623         for (it = leaves.begin(); it != it_end; ++ it) 
    3624         { 
    3625                 BspLeaf *leaf = *it; 
    3626                  
    3627                 // the same leaves must not be part of two merge candidates 
    3628                 leaf->Mail(); 
    3629                  
    3630                 vector<BspLeaf *> neighbors; 
    3631                  
    3632                 // appoximate neighbor search has slightl relaxed constraints 
    3633                 if (1) 
    3634                         FindNeighbors(leaf, neighbors, true); 
    3635                 else 
    3636                         FindApproximateNeighbors(leaf, neighbors, true); 
    3637  
    3638                 vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end(); 
    3639  
    3640                 // TODO: test if at least one ray goes from one leaf to the other 
    3641                 for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
    3642                 { 
    3643                         if ((*nit)->GetViewCell() != leaf->GetViewCell()) 
    3644                         { 
    3645                                 MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell()); 
    3646  
    3647                                 // dont't merge view cells if they are empty and not front and back leaf of the same parent 
    3648                                 // in the tree? 
    3649                                 if (mEmptyViewCellsMergeAllowed || 
    3650                                         !leaf->GetViewCell()->GetPvs().Empty() ||  
    3651                                         !(*nit)->GetViewCell()->GetPvs().Empty() || 
    3652                     leaf->IsSibling(*nit)) 
    3653                                 { 
    3654                                         candidates.push_back(mc); 
    3655                                 } 
    3656  
    3657                                 ++ numCandidates; 
    3658                                 if ((numCandidates % 1000) == 0) 
    3659                                 { 
    3660                                         cout << "collected " << numCandidates << " merge candidates" << endl; 
    3661                                 } 
    3662                         } 
    3663                 } 
    3664         } 
    3665  
    3666         Debug << "merge queue: " << (int)candidates.size() << endl; 
    3667         Debug << "leaves in queue: " << numCandidates << endl; 
    3668          
    3669  
    3670         return (int)leaves.size(); 
    3671 } 
    3672  
    3673  
    3674 int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays,  
    3675                                                                            vector<MergeCandidate> &candidates) 
    3676 { 
    3677         ViewCell::NewMail(); 
    3678         long startTime = GetTime(); 
    3679          
    3680         map<BspLeaf *, vector<BspLeaf*> > neighborMap; 
    3681         ViewCellContainer::const_iterator iit; 
    3682  
    3683         int numLeaves = 0; 
    3684          
    3685         BspLeaf::NewMail(); 
    3686  
    3687         for (int i = 0; i < (int)rays.size(); ++ i) 
    3688         {   
    3689                 VssRay *ray = rays[i]; 
    3690          
    3691                 // traverse leaves stored in the rays and compare and  
    3692                 // merge consecutive leaves (i.e., the neighbors in the tree) 
    3693                 if (ray->mViewCells.size() < 2) 
    3694                         continue; 
    3695 //TODO viewcellhierarchy 
    3696                 iit = ray->mViewCells.begin(); 
    3697                 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++)); 
    3698                 BspLeaf *leaf = bspVc->mLeaf; 
    3699                  
    3700                 // traverse intersections  
    3701                 // consecutive leaves are neighbors => add them to queue 
    3702                 for (; iit != ray->mViewCells.end(); ++ iit) 
    3703                 { 
    3704                         // next pair 
    3705                         BspLeaf *prevLeaf = leaf; 
    3706                         bspVc = dynamic_cast<BspViewCell *>(*iit); 
    3707             leaf = bspVc->mLeaf; 
    3708  
    3709                         // view space not valid or same view cell 
    3710                         if (!leaf->TreeValid() || !prevLeaf->TreeValid() || 
    3711                                 (leaf->GetViewCell() == prevLeaf->GetViewCell())) 
    3712                                 continue; 
    3713  
    3714                 vector<BspLeaf *> &neighbors = neighborMap[leaf]; 
    3715                          
    3716                         bool found = false; 
    3717  
    3718                         // both leaves inserted in queue already => 
    3719                         // look if double pair already exists 
    3720                         if (leaf->Mailed() && prevLeaf->Mailed()) 
    3721                         { 
    3722                                 vector<BspLeaf *>::const_iterator it, it_end = neighbors.end(); 
    3723                                  
    3724                 for (it = neighbors.begin(); !found && (it != it_end); ++ it) 
    3725                                         if (*it == prevLeaf) 
    3726                                                 found = true; // already in queue 
    3727                         } 
    3728                  
    3729                         if (!found) 
    3730                         { 
    3731                                 // this pair is not in map yet 
    3732                                 // => insert into the neighbor map and the queue 
    3733                                 neighbors.push_back(prevLeaf); 
    3734                                 neighborMap[prevLeaf].push_back(leaf); 
    3735  
    3736                                 leaf->Mail(); 
    3737                                 prevLeaf->Mail(); 
    3738                  
    3739                                 MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell()); 
    3740                                  
    3741                                 candidates.push_back(mc); 
    3742  
    3743                                 if (((int)candidates.size() % 1000) == 0) 
    3744                                 { 
    3745                                         cout << "collected " << (int)candidates.size() << " merge candidates" << endl; 
    3746                                 } 
    3747                         } 
    3748         } 
    3749         } 
    3750  
    3751         Debug << "neighbormap size: " << (int)neighborMap.size() << endl; 
    3752         Debug << "merge queue: " << (int)candidates.size() << endl; 
    3753         Debug << "leaves in queue: " << numLeaves << endl; 
    3754  
    3755  
    3756         //-- collect the leaves which haven't been found by ray casting 
    3757         if (0) 
    3758         { 
    3759                 cout << "finding additional merge candidates using geometry" << endl; 
    3760                 vector<BspLeaf *> leaves; 
    3761                 CollectLeaves(leaves, true); 
    3762                 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl; 
    3763                 CollectMergeCandidates(leaves, candidates); 
    3764         } 
    3765  
    3766         return numLeaves; 
    3767 } 
    3768  
    3769  
    3770  
    3771  
    3772 ViewCell *VspBspTree::GetViewCell(const Vector3 &point, const bool active) 
     1882 
     1883ViewCell *VspOspTree::GetViewCell(const Vector3 &point, const bool active) 
    37731884{ 
    37741885        if (mRoot == NULL) 
    … …  
    38091920 
    38101921 
    3811 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const 
     1922bool VspOspTree::ViewPointValid(const Vector3 &viewPoint) const 
    38121923{ 
    38131924        BspNode *node = mRoot; 
    … …  
    38391950 
    38401951 
    3841 void VspBspTree::PropagateUpValidity(BspNode *node) 
     1952void VspOspTree::PropagateUpValidity(BspNode *node) 
    38421953{ 
    38431954        const bool isValid = node->TreeValid(); 
    … …  
    38681979 
    38691980#if ZIPPED_VIEWCELLS 
    3870 bool VspBspTree::Export(ogzstream &stream) 
     1981bool VspOspTree::Export(ogzstream &stream) 
    38711982#else 
    3872 bool VspBspTree::Export(ofstream &stream) 
     1983bool VspOspTree::Export(ofstream &stream) 
    38731984#endif 
    38741985{ 
    … …  
    38781989} 
    38791990 
     1991 
    38801992#if ZIPPED_VIEWCELLS 
    3881 void VspBspTree::ExportNode(BspNode *node, ogzstream &stream) 
     1993void VspOspTree::ExportNode(BspNode *node, ogzstream &stream) 
    38821994#else 
    3883 void VspBspTree::ExportNode(BspNode *node, ofstream &stream) 
     1995void VspOspTree::ExportNode(BspNode *node, ofstream &stream) 
    38841996#endif 
    38851997{ 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

    r1002 r1006  
    1 #ifndef _VspBspTree_H__ 
    2 #define _VspBspTree_H__ 
     1#ifndef _VspOspTree_H__ 
     2#define _VspOspTree_H__ 
    33 
    44#include "Mesh.h" 
    … …  
    3131 
    3232/** 
    33         This is a view space partitioning specialised BSPtree.   
    34         There are no polygon splits, but we split the sample rays.  
    35         The candidates for the next split plane are evaluated only  
    36         by checking the sampled visibility information.  
    37         The polygons are employed merely as candidates for the next split planes. 
     33        This class implements a structure holding two different hierarchies, 
     34        one for object space partitioning and one for view space partitioning. 
     35 
     36        The object space and the view space are subdivided using a cost heuristics. 
     37        If an object space split or a view space split is chosen is also evaluated 
     38        based on the heuristics.  
     39         
     40        The view space heuristics is evaluated by weighting and adding the pvss of the back and 
     41        front node of each specific split. unlike for the standalone method vspbsp tree, 
     42        the pvs of an object would not be the pvs of single object but that of all objects 
     43        which are contained in the same leaf of the object subdivision. This could be done 
     44        by storing the pointer to the object space partition parent, which would allow access to all children. 
     45        Another possibility is to include traced kd-cells in the ray casing process. 
     46 
     47        Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object. 
     48        the contribution to an object to the pvs is the number of view cells it can be seen from. 
     49 
     50 
     51        There is a potential efficiency problem involved in a sense that once a certain type 
     52        of split is chosen for view space / object space, the candidates for the next split of  
     53        object space / view space must be reevaluated. 
     54         
    3855*/ 
    39 class VspBspTree  
     56class VspOspTree  
    4057{ 
    4158        friend class ViewCellsParseHandlers; 
    4259        friend class VspBspViewCellsManager; 
     60 
    4361public: 
    4462         
     63        /** A definition for an axis aligned plane. 
     64        */ 
     65        struct AxisAlignedPlane 
     66        { 
     67        public: 
     68                int mAxis; 
     69                float mPosition; 
     70        }; 
     71 
    4572        /** Additional data which is passed down the BSP tree during traversal. 
    4673        */ 
    47         class VspBspTraversalData 
     74        class VspOspTraversalData 
    4875        {   
    4976        public: 
    5077                /// the current node 
    5178                BspNode *mNode; 
    52                 /// polygonal data for splitting 
    53                 PolygonContainer *mPolygons; 
    5479                /// current depth 
    5580                int mDepth; 
    … …  
    5883                /// the probability that this node contains view point 
    5984                float mProbability; 
    60                 /// geometry of node as induced by planes 
    61                 BspNodeGeometry *mGeometry; 
     85                /// the bounding box of the node 
     86                AxisAlignedBox3 mBoundingBox; 
    6287                /// pvs size 
    6388                int mPvs; 
    6489                /// how often this branch has missed the max-cost ratio 
    6590                int mMaxCostMisses; 
    66                 /// if this node is a kd-node (i.e., boundaries are axis aligned 
    67                 bool mIsKdNode; 
    6891                // current axis 
    6992                int mAxis; 
    … …  
    80103 
    81104 
    82                 VspBspTraversalData(): 
     105                VspOspTraversalData(): 
    83106                mNode(NULL), 
    84                 mPolygons(NULL), 
    85107                mDepth(0), 
    86108                mRays(NULL), 
    87109                mPvs(0), 
    88110                mProbability(0.0), 
    89                 mGeometry(NULL), 
    90111                mMaxCostMisses(0),  
    91                 mIsKdNode(false), 
    92112                mPriority(0), 
    93113                mAxis(0) 
    94114                {} 
    95115                 
    96                 VspBspTraversalData(BspNode *node,  
    97                                                         PolygonContainer *polys,  
     116                VspOspTraversalData(BspNode *node,  
    98117                                                        const int depth,  
    99118                                                        RayInfoContainer *rays, 
    100119                                                        const int pvs, 
    101120                                                        const float p, 
    102                                                         BspNodeGeometry *geom):  
     121                                                        const AxisAlignedBox3 &box):  
    103122                mNode(node),  
    104                 mPolygons(polys),  
    105123                mDepth(depth),  
    106124                mRays(rays), 
    107125                mPvs(pvs), 
    108126                mProbability(p), 
    109                 mGeometry(geom), 
     127                mBoundingBox(box), 
    110128                mMaxCostMisses(0), 
    111                 mIsKdNode(false), 
    112129                mPriority(0), 
    113130                mAxis(0) 
    114131                {} 
    115132 
    116                 VspBspTraversalData(PolygonContainer *polys,  
     133                VspOspTraversalData(PolygonContainer *polys,  
    117134                                                        const int depth,  
    118135                                                        RayInfoContainer *rays, 
    119                                                         BspNodeGeometry *geom):  
     136                                                        const AxisAlignedBox3 &box):  
    120137                mNode(NULL),  
    121                 mPolygons(polys),  
    122138                mDepth(depth),  
    123139                mRays(rays), 
    124140                mPvs(0), 
    125141                mProbability(0), 
    126                 mGeometry(geom), 
    127142                mMaxCostMisses(0), 
    128                 mIsKdNode(false), 
    129                 mAxis(0) 
     143                mAxis(0), 
     144                mBoundingBox(box) 
    130145                {} 
    131146 
    … …  
    141156                void Clear() 
    142157                { 
    143                         DEL_PTR(mPolygons); 
    144158                        DEL_PTR(mRays); 
    145                         DEL_PTR(mGeometry); 
    146                 } 
    147  
    148                 friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b) 
     159                } 
     160 
     161                friend bool operator<(const VspOspTraversalData &a, const VspOspTraversalData &b) 
    149162                { 
    150163                        return a.GetCost() < b.GetCost(); 
    … …  
    153166         
    154167 
    155         typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue; 
    156          
    157          
    158         struct VspBspSplitCandidate 
     168        typedef std::priority_queue<VspOspTraversalData> VspOspTraversalQueue; 
     169         
     170         
     171        struct VspOspSplitCandidate 
    159172        {   
    160                 /// the current node 
    161                 Plane3 mSplitPlane; 
    162                 /// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned) 
    163                 int mSplitAxis; 
     173                /// the current plane 
     174                AxisAlignedPlane mSplitPlane; 
    164175                /// the number of misses of max cost ratio until this split 
    165176                int mMaxCostMisses; 
    166  
    167                 // parent data 
    168                 VspBspTraversalData mParentData; 
    169                 // cost of applying this split 
     177                /// parent data 
     178                VspOspTraversalData mParentData; 
     179                /// cost of applying this split 
    170180                float mRenderCost; 
    171181 
    172                 VspBspSplitCandidate(): mRenderCost(0)  
     182                VspOspSplitCandidate(): mRenderCost(0)  
    173183                {}; 
    174184 
    175                 VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData):  
     185                VspOspSplitCandidate(const AxisAlignedPlane &plane, const VspOspTraversalData &tData):  
    176186                mSplitPlane(plane), mParentData(tData), mRenderCost(0) 
    177187                {} 
    … …  
    189199                } 
    190200 
    191                 friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b) 
     201                friend bool operator<(const VspOspSplitCandidate &a, const VspOspSplitCandidate &b) 
    192202                { 
    193203                        return a.GetCost() < b.GetCost(); 
    … …  
    195205    }; 
    196206 
    197         typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue; 
     207        typedef std::priority_queue<VspOspSplitCandidate> VspOspSplitQueue; 
    198208 
    199209        /** Default constructor creating an empty tree. 
    200210        */  
    201         VspBspTree(); 
    202  
    203          
    204         /** Constructor creating an empty tree. Loads parameters  
    205                 from an environment file. 
    206         */  
    207         VspBspTree(Environment *env); 
     211        VspOspTree(); 
    208212 
    209213        /** Default destructor. 
    210214        */ 
    211         ~VspBspTree(); 
     215        ~VspOspTree(); 
    212216 
    213217        /** Returns BSP Tree statistics. 
    … …  
    252256        int CastRay(Ray &ray); 
    253257 
    254         /// bsp tree construction types 
    255         enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES}; 
    256258 
    257259        /** finds neighbouring leaves of this tree node. 
    … …  
    260262                                          vector<BspLeaf *> &neighbors,  
    261263                                          const bool onlyUnmailed) const; 
    262  
    263         /** Constructs geometry associated with the half space intersections  
    264                 leading to this node. 
    265         */ 
    266         void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const; 
    267          
    268         /** Construct geometry of view cell. 
    269         */ 
    270         void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const; 
    271264 
    272265        /** Returns random leaf of BSP tree. 
    … …  
    400393        /** faster evaluation of split plane cost for kd axis aligned cells. 
    401394        */ 
    402         float EvalAxisAlignedSplitCost(const VspBspTraversalData &data, 
    403                                                                    const AxisAlignedBox3 &box, 
    404                                                                    const int axis, 
    405                                                                    const float &position, 
    406                                                                    float &pFront, 
    407                                                                    float &pBack) const; 
     395        float EvalSplitCost(const VspOspTraversalData &data, 
     396                                                const AxisAlignedBox3 &box, 
     397                                                const int axis, 
     398                                                const float &position, 
     399                                                float &pFront, 
     400                                                float &pBack) const; 
    408401 
    409402        /** Evaluates candidate for splitting. 
    410403        */ 
    411         void EvalSplitCandidate(VspBspTraversalData &tData, VspBspSplitCandidate &splitData); 
     404        void EvalSplitCandidate(VspOspTraversalData &tData, VspOspSplitCandidate &splitData); 
    412405 
    413406        /** Computes priority of the traversal data and stores it in tData. 
    414407        */ 
    415         void EvalPriority(VspBspTraversalData &tData) const; 
     408        void EvalPriority(VspOspTraversalData &tData) const; 
    416409 
    417410        /** Evaluates render cost decrease of next split. 
    418411        */ 
    419412        float EvalRenderCostDecrease(const Plane3 &candidatePlane, 
    420                                                                  const VspBspTraversalData &data) const; 
     413                                                                 const VspOspTraversalData &data) const; 
    421414 
    422415        /** Constructs tree using the split priority queue. 
    423416        */ 
    424         void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays); 
     417        void Construct(RayInfoContainer *rays); 
    425418 
    426419        /** Collects view cells in the subtree under root. 
    … …  
    451444        /** Evaluates tree stats in the BSP tree leafs. 
    452445        */ 
    453         void EvaluateLeafStats(const VspBspTraversalData &data); 
     446        void EvaluateLeafStats(const VspOspTraversalData &data); 
    454447 
    455448        /** Subdivides node with respect to the traversal data. 
    … …  
    458451                @returns new root of the subtree 
    459452        */ 
    460         BspNode *Subdivide(VspBspTraversalQueue &tStack,  
    461                                            VspBspTraversalData &tData); 
    462  
    463         BspNode *Subdivide(VspBspSplitQueue &tQueue, 
    464                                            VspBspSplitCandidate &splitCandidate); 
    465  
    466         /** Constructs the tree from the given traversal data. 
    467                 @param polys stores set of polygons on which subdivision may be based 
    468                 @param rays storesset of rays on which subdivision may be based 
    469         */ 
    470         void Construct(const PolygonContainer &polys, RayInfoContainer *rays); 
    471  
    472         /** Selects the best possible splitting plane.  
    473                 @param plane returns the split plane 
    474                 @param leaf the leaf to be split 
    475                 @param polys the polygon list on which the split decition is based 
    476                 @param rays ray container on which selection may be based 
    477                 @note the polygons can be reordered in the process 
    478                 @returns true if the cost of the split is under maxCostRatio 
    479  
    480         */ 
    481         bool SelectPlane(Plane3 &plane,  
    482                                          BspLeaf *leaf,  
    483                                          VspBspTraversalData &data, 
    484                                          VspBspTraversalData &frontData, 
    485                                          VspBspTraversalData &backData, 
    486                                          int &splitAxis); 
    487          
    488         /** Strategies where the effect of the split plane is tested 
    489             on all input rays. 
    490  
    491                 @returns the cost of the candidate split plane 
    492         */ 
    493         float EvalSplitPlaneCost(const Plane3 &candidatePlane,  
    494                                                          const VspBspTraversalData &data, 
    495                                                          BspNodeGeometry &geomFront, 
    496                                                          BspNodeGeometry &geomBack, 
    497                                                          float &pFront, 
    498                                                          float &pBack) const; 
    499  
     453        BspNode *Subdivide(VspOspSplitQueue &tQueue, 
     454                                           VspOspSplitCandidate &splitCandidate); 
     455 
     456         
    500457        /** Subdivides leaf. 
    501458                @param leaf the leaf to be subdivided 
    … …  
    513470 
    514471        BspInterior *SubdivideNode(const Plane3 &splitPlane, 
    515                                                            VspBspTraversalData &tData, 
    516                                                            VspBspTraversalData &frontData, 
    517                                VspBspTraversalData &backData, 
    518                                                            PolygonContainer &coincident); 
    519  
    520         /** Extracts the meshes of the objects and adds them to polygons.  
    521                 Adds object aabb to the aabb of the tree. 
    522                 @param maxPolys the maximal number of objects to be stored as polygons 
    523                 @returns the number of polygons 
    524         */ 
    525         int AddToPolygonSoup(const ObjectContainer &objects,  
    526                                                  PolygonContainer &polys,  
    527                                                  int maxObjects = 0); 
    528  
    529         /** Extracts the meshes of the view cells and and adds them to polygons. 
    530                 Adds view cell aabb to the aabb of the tree. 
    531                 @param maxPolys the maximal number of objects to be stored as polygons 
    532                 @returns the number of polygons 
    533         */ 
    534         int AddToPolygonSoup(const ViewCellContainer &viewCells,  
    535                                                  PolygonContainer &polys,  
    536                                                  int maxObjects = 0); 
    537  
    538         /** Extract polygons of this mesh and add to polygon container. 
    539                 @param mesh the mesh that drives the polygon construction 
    540                 @param parent the parent intersectable this polygon is constructed from 
    541                 @returns number of polygons 
    542         */ 
    543         int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 
     472                                                           VspOspTraversalData &tData, 
     473                                                           VspOspTraversalData &frontData, 
     474                               VspOspTraversalData &backData); 
    544475 
    545476        /** Selects an axis aligned for the next split. 
    546477                @returns cost for this split 
    547478        */ 
    548         float SelectAxisAlignedPlane(Plane3 &plane,  
    549                                                                  const VspBspTraversalData &tData, 
    550                                                                  int &axis, 
    551                                                                  BspNodeGeometry **frontGeom, 
    552                                                                  BspNodeGeometry **backGeom, 
    553                                                                  float &pFront, 
    554                                                                  float &pBack, 
    555                                                                  const bool useKdSplit); 
     479        float SelectPlane(const VspOspTraversalData &tData, 
     480                                          AxisAlignedPlane &plane, 
     481                                          float &pFront, 
     482                                          float &pBack); 
    556483 
    557484        /** Sorts split candidates for surface area heuristics for axis aligned splits. 
    … …  
    573500                                                                  float &position); 
    574501 
    575         /** Selects an axis aligned split plane. 
    576                 @Returns true if split is valied 
    577         */ 
    578         bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const; 
    579  
    580502        /** Subdivides the rays into front and back rays according to the split plane. 
    581503                 
    … …  
    593515                                  RayInfoContainer &backRays) const; 
    594516 
    595  
    596         /** Extracts the split planes representing the space bounded by node n. 
    597         */ 
    598         void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const; 
    599  
    600517        /** Adds the object to the pvs of the front and back leaf with a given classification. 
    601518 
    … …  
    618535        /** Returns true if tree can be terminated. 
    619536        */ 
    620         inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const; 
     537        inline bool LocalTerminationCriteriaMet(const VspOspTraversalData &data) const; 
    621538 
    622539        /** Returns true if global tree can be terminated. 
    623540        */ 
    624         inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const; 
    625  
    626         /** Computes accumulated ray lenght of this rays. 
    627         */ 
    628         float AccumulatedRayLength(const RayInfoContainer &rays) const; 
    629  
    630         /** Splits polygons with respect to the split plane. 
    631  
    632                 @param plane the split plane 
    633                 @param polys the polygons to be split. the polygons are consumed and 
    634                            distributed to the containers frontPolys, backPolys, coincident. 
    635                 @param frontPolys returns the polygons in the front of the split plane 
    636                 @param backPolys returns the polygons in the back of the split plane 
    637                 @param coincident returns the polygons coincident to the split plane 
    638  
    639                 @returns the number of splits    
    640         */ 
    641         int SplitPolygons(const Plane3 &plane, 
    642                                           PolygonContainer &polys,  
    643                                           PolygonContainer &frontPolys,  
    644                                           PolygonContainer &backPolys,  
    645                                           PolygonContainer &coincident) const; 
     541        inline bool GlobalTerminationCriteriaMet(const VspOspTraversalData &data) const; 
    646542 
    647543        /** Adds ray sample contributions to the PVS. 
    … …  
    655551                                  int &contributingSamples); 
    656552 
    657  
    658  
    659  
    660  
    661          
    662         /** Take 3 ray endpoints, where two are minimum and one a maximum 
    663                 point or the other way round. 
    664         */ 
    665         Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const; 
    666  
    667         /** Take plane normal as plane normal and the midpoint of the ray. 
    668                 PROBLEM: does not resemble any point where visibility is  
    669                 likely to change 
    670         */ 
    671         Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const; 
    672  
    673         /** Fit the plane between the two lines so that the plane  
    674                 has equal shortest distance to both lines. 
    675         */ 
    676         Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const; 
    677    
    678         /** Collects candidates for merging. 
    679                 @param leaves the leaves to be merged 
    680                 @returns number of leaves in queue 
    681         */ 
    682         int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates); 
    683  
    684         /** Collects candidates for the merge in the merge queue. 
    685                 @returns number of leaves in queue 
    686         */ 
    687         int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates); 
    688          
    689         /** Preprocesses polygons and throws out all polygons which are coincident to 
    690                 the view space box faces (they can be problematic). 
    691         */ 
    692         void PreprocessPolygons(PolygonContainer &polys); 
    693          
    694553        /** Propagates valid flag up the tree. 
    695554        */ 
    … …  
    707566        /** Returns estimated memory usage of tree. 
    708567        */ 
    709         //float GetMemUsage(const VspBspTraversalQueue &tstack) const; 
    710568        float GetMemUsage() const; 
    711569 
    712570 
     571protected: 
     572 
     573        ViewCellsManager *mViewCellsManager; 
     574        vector<SortableEntry> *mSplitCandidates; 
    713575 
    714576        /// Pointer to the root of the tree 
    … …  
    716578                 
    717579        BspTreeStatistics mBspStats; 
    718  
    719         /// Strategies for choosing next split plane. 
    720         enum {NO_STRATEGY = 0, 
    721                   RANDOM_POLYGON = 1,  
    722                   AXIS_ALIGNED = 2, 
    723                   LEAST_RAY_SPLITS = 256, 
    724                   BALANCED_RAYS = 512, 
    725                   PVS = 1024 
    726                 }; 
     580         
     581        /// View cell corresponding to the space outside the valid view space 
     582        BspViewCell *mOutOfBoundsCell; 
    727583 
    728584        /// box around the whole view domain 
    729585        AxisAlignedBox3 mBox; 
    730586 
    731         bool mUseCostHeuristics; 
     587 
     588 
     589        //-- local termination 
    732590 
    733591        /// minimal number of rays before subdivision termination 
    … …  
    741599        /// maximal contribution per ray 
    742600        float mTermMaxRayContribution; 
    743         /// minimal accumulated ray length 
    744         float mTermMinAccRayLength; 
    745  
    746         //HACK 
    747         int mTermMinPolygons; 
    748  
    749         float mTermMinGlobalCostRatio; 
    750         int mTermGlobalCostMissTolerance; 
    751  
    752         int mGlobalCostMisses; 
    753  
    754         bool mUseSplitCostQueue; 
    755         //-- termination criteria for axis aligned split 
    756  
    757         /// minimal number of rays for axis aligned split 
    758         int mTermMinRaysForAxisAligned; 
    759         // max ray contribution 
    760         float mTermMaxRayContriForAxisAligned; 
    761  
    762         /// strategy to get the best split plane 
    763         int mSplitPlaneStrategy; 
    764         /// number of candidates evaluated for the next split plane 
    765         int mMaxPolyCandidates; 
    766         /// number of candidates for split planes evaluated using the rays 
    767         int mMaxRayCandidates; 
    768         /// balancing factor for PVS criterium 
    769         float mCtDivCi; 
    770  
    771         bool mUseDrivingAxisForMaxCost; 
    772         //-- axis aligned split criteria 
    773         float mAxisAlignedCtDivCi; 
    774         /// spezifies the split border of the axis aligned split 
    775         float mAxisAlignedSplitBorder; 
    776  
    777601        /// maximal acceptable cost ratio 
    778602        float mTermMaxCostRatio; 
    … …  
    780604        int mTermMissTolerance; 
    781605 
    782         //-- factors guiding the split plane heuristics 
    783         float mLeastRaySplitsFactor; 
    784         float mBalancedRaysFactor; 
    785         float mPvsFactor; 
    786  
    787         /// if area or volume should be used for PVS heuristics 
    788         bool mUseAreaForPvs; 
    789         /// tolerance for polygon split 
    790         float mEpsilon; 
    791         /// maximal number of test rays used to evaluate candidate split plane 
    792         int mMaxTests; 
    793         /// normalizes different bsp split plane criteria 
    794         float mCostNormalizer; 
     606 
     607        //-- global criteria 
     608        float mTermMinGlobalCostRatio; 
     609        int mTermGlobalCostMissTolerance; 
     610        int mGlobalCostMisses; 
     611 
    795612        /// maximal number of view cells 
    796613        int mMaxViewCells; 
    797          
    798         ofstream  mSubdivisionStats; 
    799  
    800         // if rays should be stored in leaves 
    801         bool mStoreRays; 
    802          
    803         /// if only driving axis should be used for split 
    804         bool mOnlyDrivingAxis; 
    805  
    806         ViewCellsManager *mViewCellsManager; 
    807  
    808         vector<SortableEntry> *mSplitCandidates; 
    809  
    810          
    811         float mRenderCostWeight; 
    812         /// View cell corresponding to the space outside the valid view space 
    813         BspViewCell *mOutOfBoundsCell; 
    814  
    815614        /// maximal tree memory 
    816615        float mMaxMemory; 
    817616        /// the tree is out of memory 
    818617        bool mOutOfMemory; 
    819          
    820         float mTotalCost; 
    821         int mTotalPvsSize; 
    822  
    823         float mMinBand; 
    824         float mMaxBand; 
    825  
    826         //int mSplits; 
    827         /// subdivision stats output file 
    828         ofstream mSubdivsionStats; 
     618 
     619 
     620 
     621        //-- split heuristics based parameters 
     622         
     623        bool mUseCostHeuristics; 
     624        /// balancing factor for PVS criterium 
     625        float mCtDivCi;  
     626        /// if only driving axis should be used for split 
     627        bool mOnlyDrivingAxis; 
    829628        /// if random split axis should be used 
    830629        bool mUseRandomAxis; 
    831         /// use polygon split whenever there are polys left 
    832         bool mUsePolygonSplitIfAvailable; 
     630        /// if vsp bsp tree should simulate octree 
     631        bool mCirculatingAxis; 
     632        /// minimal relative position where the split axis can be placed 
     633        float mMinBand; 
     634        /// maximal relative position where the split axis can be placed 
     635        float mMaxBand; 
     636 
     637 
    833638        /// current time stamp (used for keeping split history) 
    834639        int mTimeStamp; 
     640        // if rays should be stored in leaves 
     641        bool mStoreRays; 
     642 
     643        /// epsilon for geometric comparisons 
     644        float mEpsilon; 
     645 
     646        /// if we should use breath first priority for the splits 
     647        int mNodePriorityQueueType; 
     648 
     649        // priority queue strategy 
     650        enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED}; 
     651 
     652 
     653        /// subdivision stats output file 
     654        ofstream  mSubdivisionStats; 
     655        /// keeps track of cost during subdivision 
     656        float mTotalCost; 
     657        /// keeps track of overall pvs size during subdivision 
     658        int mTotalPvsSize; 
    835659        /// number of currenly generated view cells 
    836660        int mCreatedViewCells; 
    837         /// if vsp bsp tree should simulate octree 
    838         bool mCirculatingAxis; 
    839  
    840         /// if we should use breath first priority for the splits 
    841         int mNodePriorityQueueType; 
    842  
    843         bool mEmptyViewCellsMergeAllowed; 
    844  
    845         // priority queue strategy 
    846         enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED}; 
     661 
    847662private: 
    848663 

  • GTP/trunk/Lib/Vis/Preprocessing/src/X3dExporter.cpp

    r1004 r1006  
    99#include "Polygon3.h" 
    1010#include "VssRay.h" 
    11 #include "VspKdTree.h" 
     11//#include "VspOspTree.h" 
    1212#include "VssTree.h" 
    1313#include "VspBspTree.h" 
    … …  
    3333  stream.close(); 
    3434} 
    35  
    36  
    37 //  bool 
    38 //  X3dExporter::ExportRays(const vector<Ray> &rays, 
    39 //                                                                                              const float length, 
    40 //                                                                                              const RgbColor &color) 
    41 //  { 
    42 //    vector<Ray>::const_iterator ri = rays.begin(); 
    43 //    stream<<"<Shape>"<<endl; 
    44 //    stream<<"<Appearance>"<<endl; 
    45 //    stream<<"<Material ambientColor=\""<<color.r<<" "<<color.g<<" "<<color.b<< 
    46 //      "\" />"<<endl; 
    47 //    stream<<"</Appearance>"<<endl; 
    48    
    49 //    stream<<"<IndexedLineSet coordIndex=\""<<endl; 
    50  
    51 //    int index = 0; 
    52 //    for (; ri != rays.end(); ri++) { 
    53 //      stream<<index<<" "<<index+1<<" -1\n"; 
    54 //      index+=2; 
    55 //    } 
    56    
    57 //    stream<<"\" >"<<endl; 
    58    
    59 //    stream<<"<Coordinate  point=\""<<endl; 
    60    
    61 //    ri = rays.begin(); 
    62 //    for (; ri != rays.end(); ri++) { 
    63 //      Vector3 a = (*ri).GetLoc(); 
    64      
    65 //      Vector3 b; 
    66 //      if (length < 0) 
    67 //        b = (*ri).GetLoc() - length*(*ri).GetDir(); 
    68 //      else 
    69 //        if ((*ri).intersections.size()==0) 
    70 //      b = (*ri).GetLoc() + length*(*ri).GetDir(); 
    71 //        else 
    72 //      b = (*ri).Extrap((*ri).intersections[0].mT); 
    73      
    74 //      stream<<a.x<<" "<<a.y<<" "<<a.z<<" ,"; 
    75 //      stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n"; 
    76 //    } 
    77    
    78 //    stream<<"\" >"<<endl; 
    79 //    stream<<"</Coordinate>"<<endl; 
    80 //    stream<<"</IndexedLineSet>"<<endl; 
    81 //    stream<<"</Shape>"<<endl; 
    82 //    return true; 
    83 //  } 
    8435 
    8536 
    … …  
    459410 
    460411 
     412 
    461413void X3dExporter::ExportPolygons(const PolygonContainer &polys) 
    462414{ 
    … …  
    535487        stream << "</Shape>" << endl; 
    536488} 
     489 
    537490 
    538491bool 
    … …  
    561514} 
    562515 
     516 
    563517bool 
    564518X3dExporter::ExportBspTree(const BspTree &tree) 
    … …  
    584538} 
    585539 
    586 bool X3dExporter::ExportVspKdTree(const VspKdTree &tree, const int maxPvs) 
     540#if 0 
     541bool X3dExporter::ExportVspOspTree(const VspOspTree &tree, const int maxPvs) 
    587542{ 
    588543        stack<VspKdNode *> tStack; 
    … …  
    654609        return true; 
    655610} 
    656  
     611#endif 
    657612 
    658613bool X3dExporter::ExportKdTree(const KdTree &tree) 
    … …  
    696651  ExportMesh(mesh); 
    697652  delete mesh; 
     653 
    698654  return true; 
    699         // TODO 
    700         return true; 
    701655} 
    702656 

  • GTP/trunk/Lib/Vis/Preprocessing/src/X3dExporter.h

    r1001 r1006  
    5959                                 const Vector3 direction 
    6060                                 ); 
    61  
     61#if VSP_OPS 
    6262  bool 
    63   ExportVspKdTree(const VspKdTree &tree, const int maxPvs); 
    64  
     63  ExportVspOspTree(const VspOspTree &tree, const int maxPvs); 
     64#endif 
    6565  bool ExportBspTree(const BspTree &tree); 
    6666 
Note: See TracChangeset for help on using the changeset viewer.