Changeset 462 for trunk/VUT


Ignore:
Timestamp:
12/13/05 17:28:02 (19 years ago)
Author:
mattausch
Message:

worked on vsp kd view cells

Location:
trunk/VUT/GtpVisibilityPreprocessor
Files:
21 edited

Legend:

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

    r452 r462  
    2525 
    2626VssPreprocessor { 
    27         samplesPerPass  10000 
    28         initialSamples 100000 
    29         vssSamples 300000 
    30         vssSamplesPerPass 10000 
     27        samplesPerPass  100000 
     28        initialSamples 1000000 
     29        vssSamples 3000000 
     30        vssSamplesPerPass 100000 
    3131        useImportanceSampling true 
    3232} 
     
    153153         
    154154        height 5.0 
    155         maxViewCells 0 
     155        maxViewCells 5000 
    156156         
    157157        PostProcessing { 
     
    284284        Termination { 
    285285                maxDepth                40 
    286                 minPvs                  40 
    287                 minRays                 100 
     286                minPvs                  90 
     287                minRays                 10 
    288288                minSize                 0.1 
    289289                maxCostRatio            999.0 
     
    297297        #splitType      heuristics 
    298298        ct_div_ci       0.0 
     299         
     300        # maximal cost for merging a view cell 
     301        maxCostRatio 1.4 
    299302} 
    300303 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r448 r462  
    13951395  RegisterOption("VspKdTree.Construction.samples", 
    13961396                 optInt, 
    1397                  "-vsp_construction_samples=", 
     1397                 "-vsp_kd_construction_samples=", 
    13981398                 "100000"); 
     1399 
     1400  RegisterOption("VspKdTree.maxCostRatio", 
     1401                 optFloat, 
     1402                 "-vsp_kd_max_cost_ratio=", 
     1403                 "1.5"); 
    13991404 
    14001405  RegisterOption("VspKdTree.Termination.maxDepth",  
  • trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

    r459 r462  
    119119                                 const Vector3 direction) = 0; 
    120120 
     121  virtual bool  
     122  ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0) = 0; 
     123 
    121124  void SetExportRayDensity(const bool d) { mExportRayDensity = d; } 
    122125   
  • trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

    r403 r462  
    502502int 
    503503KdTree::CastRay( 
    504                                                                 Ray &ray 
    505                                                                 ) 
     504                                Ray &ray 
     505                                ) 
    506506{ 
    507507  int hits = 0; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

    r448 r462  
    2323Preprocessor::~Preprocessor() 
    2424{ 
     25        DEL_PTR(mViewCellsManager); 
     26 
    2527        DEL_PTR(mBspTree); 
    2628        DEL_PTR(mKdTree); 
    2729        DEL_PTR(mVspKdTree); 
    2830        DEL_PTR(mVspBspTree); 
    29         DEL_PTR(mViewCellsManager); 
    3031} 
    3132 
  • trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

    r449 r462  
    239239} 
    240240 
    241 /********************************************************/ 
    242 /*     class BspRenderSimulator implementation          */ 
    243 /********************************************************/ 
     241/**********************************************************/ 
     242/*       class BspRenderSimulator implementation          */ 
     243/**********************************************************/ 
    244244 
    245245VspBspRenderSimulator::VspBspRenderSimulator(VspBspTree *vspBspTree): 
  • trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

    r459 r462  
    627627 
    628628  //-- several visualizations and statistics 
    629   Debug << "===== Final view cells statistics ==========" << endl; 
    630  
    631629  mViewCellsManager->PrintStatistics(Debug); 
    632630 
  • trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

    r452 r462  
    398398         
    399399        //-- several visualizations and statistics 
    400         Debug << "===== Final view cells statistics ==========" << endl; 
    401  
    402400        mViewCellsManager->PrintStatistics(Debug); 
    403401 
     
    412410         
    413411        mViewCellsManager->Visualize(objects, mSampleRays);      
    414      
     412    
    415413        return true; 
    416414} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

    r439 r462  
    44#include "MeshKdTree.h" 
    55#include "Triangle3.h" 
     6#include <time.h> 
     7#include <iomanip> 
    68 
    79ViewCell::ViewCell(): MeshInstance(NULL), mPiercingRays(0) 
     
    3234        mPassingRays.AddRay(ray, contributions); 
    3335} 
     36 
     37/************************************************************************/ 
     38/*                class ViewCellsStatistics implementation              */ 
     39/************************************************************************/ 
     40 
     41void ViewCellsStatistics::Print(ostream &app) const 
     42{ 
     43        app << "=========== View Cells Statistics ===============\n"; 
     44 
     45        app << setprecision(4); 
     46 
     47        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n"; 
     48 
     49        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl; 
     50 
     51        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl; 
     52 
     53        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl; 
     54 
     55        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl; 
     56 
     57        app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl; 
     58 
     59        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl; 
     60 
     61        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl; 
     62 
     63        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl; 
     64         
     65        app << "========== End of View Cells Statistics ==========\n"; 
     66} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

    r454 r462  
    55#include "Containers.h" 
    66#include "Ray.h" 
    7  
     7#include "Statistics.h" 
    88//namespace GtpVisibilityPreprocessor { 
    99   
     
    1313class BspLeaf; 
    1414class VspKdTree; 
    15 class VspKdTreeLeaf; 
     15class VspKdLeaf; 
     16 
    1617 
    1718/** 
     
    2223public: 
    2324        ViewCell(); 
     25         
    2426        /** Constructor taking a mesh representing the shape of the viewcell. 
    2527        */ 
    2628        ViewCell(Mesh *mesh); 
     29 
     30 
     31        virtual ~ViewCell() {} 
    2732        /** Returns Pvs.  
    2833        */ 
     
    6772        ViewCell(mesh), mVspKdLeaves(0) {} 
    6873 
    69         float GetSize() {return 0;} 
     74        float GetSize() {return mSize;} 
    7075        void SetSize(float size) {mSize = size;} 
    7176 
    7277        /// Leaves which hold this view cell. 
    73         vector<VspKdTreeLeaf *> mVspKdLeaves; 
     78        vector<VspKdLeaf *> mVspKdLeaves; 
    7479 
    7580protected: 
    7681        float mSize; 
    7782}; 
     83 
     84class ViewCellsStatistics: public StatisticsBase 
     85{ 
     86public: 
     87 
     88        /// number of view cells 
     89        int viewCells; 
     90 
     91        /// size of the PVS 
     92        int pvs; 
     93   
     94        /// largest PVS of all view cells 
     95        int maxPvs; 
     96 
     97        /// smallest PVS of all view cells 
     98        int minPvs; 
     99 
     100        /// view cells with empty PVS 
     101        int emptyPvs; 
     102 
     103        /// number of leaves covering the view space 
     104        int leaves; 
     105 
     106        /// largest number of leaves covered by one view cell   
     107        int maxLeaves; 
     108 
     109    // Constructor 
     110        ViewCellsStatistics()  
     111        { 
     112                Reset(); 
     113        } 
     114 
     115        double AvgLeaves() const {return (double)leaves / (double)viewCells;}; 
     116        double AvgPvs() const {return (double)pvs / (double)viewCells;}; 
     117   
     118        void Reset()  
     119        { 
     120                viewCells = 0;   
     121                pvs = 0;   
     122                maxPvs = 0; 
     123 
     124                minPvs = 999999; 
     125                emptyPvs = 0; 
     126                leaves = 0; 
     127                maxLeaves = 0; 
     128        } 
     129 
     130        void Print(ostream &app) const; 
     131 
     132        friend ostream &operator<<(ostream &s, const ViewCellsStatistics &stat)  
     133        { 
     134                stat.Print(s); 
     135                return s; 
     136        }   
     137}; 
     138 
    78139#endif 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

    r452 r462  
    99#include "AxisAlignedBox3.h" 
    1010#include <stack> 
    11 #include <time.h> 
    12 #include <iomanip> 
     11 
    1312#include "Exporter.h" 
    1413#include "Plane3.h" 
     
    19071906} 
    19081907 
    1909 void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const 
    1910 { 
    1911         stat.Reset(); 
     1908void BspTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const 
     1909{ 
     1910        vcStat.Reset(); 
    19121911 
    19131912        stack<BspNode *> nodeStack; 
     
    19261925                if (node->IsLeaf())  
    19271926                { 
    1928                         ++ stat.bspLeaves; 
     1927                        ++ vcStat.leaves; 
    19291928 
    19301929                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell; 
     
    19341933                                viewCell->Mail(); 
    19351934                                 
    1936                                 ++ stat.viewCells; 
     1935                                ++ vcStat.viewCells; 
    19371936                                const int pvsSize = viewCell->GetPvs().GetSize(); 
    19381937 
    1939                 stat.pvs += pvsSize; 
     1938                vcStat.pvs += pvsSize; 
    19401939 
    19411940                                if (pvsSize < 1) 
    1942                                         ++ stat.emptyPvs; 
    1943  
    1944                                 if (pvsSize > stat.maxPvs) 
    1945                                         stat.maxPvs = pvsSize; 
    1946  
    1947                                 if (pvsSize < stat.minPvs) 
    1948                                         stat.minPvs = pvsSize; 
    1949  
    1950                                 if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves) 
    1951                                         stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();            
     1941                                        ++ vcStat.emptyPvs; 
     1942 
     1943                                if (pvsSize > vcStat.maxPvs) 
     1944                                        vcStat.maxPvs = pvsSize; 
     1945 
     1946                                if (pvsSize < vcStat.minPvs) 
     1947                                        vcStat.minPvs = pvsSize; 
     1948 
     1949                                if ((int)viewCell->mBspLeaves.size() > vcStat.maxLeaves) 
     1950                                        vcStat.maxLeaves = (int)viewCell->mBspLeaves.size();             
    19521951                        } 
    19531952                } 
     
    24122411} 
    24132412 
    2414 void BspViewCellsStatistics::Print(ostream &app) const 
    2415 { 
    2416         app << "===== BspViewCells statistics ===============\n"; 
    2417  
    2418         app << setprecision(4); 
    2419  
    2420         //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n"; 
    2421  
    2422         app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl; 
    2423  
    2424         app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl; 
    2425  
    2426         app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl; 
    2427  
    2428         app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl; 
    2429  
    2430         app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl; 
    2431  
    2432         app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl; 
    2433  
    2434         app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl; 
    2435  
    2436         app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl; 
    2437          
    2438         app << "===== END OF BspViewCells statistics ==========\n"; 
    2439 } 
    24402413 
    24412414/*************************************************************/ 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

    r448 r462  
    1818class AxisAlignedBox3; 
    1919class Ray; 
     20class ViewCellsStatistics; 
    2021 
    2122class BspNodeGeometry 
     
    157158}; 
    158159 
    159 class BspViewCellsStatistics: public StatisticsBase 
    160 { 
    161 public: 
    162  
    163         /// number of view cells 
    164         int viewCells; 
    165  
    166         /// size of the PVS 
    167         int pvs; 
    168    
    169         /// largest PVS of all view cells 
    170         int maxPvs; 
    171  
    172         /// smallest PVS of all view cells 
    173         int minPvs; 
    174  
    175         /// view cells with empty PVS 
    176         int emptyPvs; 
    177  
    178         /// number of bsp leaves covering the view space 
    179         int bspLeaves; 
    180  
    181         /// largest number of leaves covered by one view cell   
    182         int maxBspLeaves; 
    183  
    184     // Constructor 
    185         BspViewCellsStatistics()  
    186         { 
    187                 Reset(); 
    188         } 
    189  
    190         double AvgBspLeaves() const {return (double)bspLeaves / (double)viewCells;}; 
    191         double AvgPvs() const {return (double)pvs / (double)viewCells;}; 
    192    
    193         void Reset()  
    194         { 
    195                 viewCells = 0;   
    196                 pvs = 0;   
    197                 maxPvs = 0; 
    198  
    199                 minPvs = 999999; 
    200                 emptyPvs = 0; 
    201                 bspLeaves = 0; 
    202                 maxBspLeaves = 0; 
    203         } 
    204  
    205         void Print(ostream &app) const; 
    206  
    207         friend ostream &operator<<(ostream &s, const BspViewCellsStatistics &stat)  
    208         { 
    209                 stat.Print(s); 
    210                 return s; 
    211         }   
    212 }; 
    213160 
    214161/** 
     
    499446        /** Traverses tree and counts all view cells as well as their PVS size. 
    500447        */ 
    501         void EvaluateViewCellsStats(BspViewCellsStatistics &stat) const; 
     448        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 
    502449 
    503450        /** Returns view cell corresponding to unbounded space. 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

    r453 r462  
    154154ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const 
    155155{ 
     156        // generate merged view cell 
    156157        ViewCell *vc = GenerateViewCell(); 
     158 
    157159        // merge pvs 
    158160        vc->GetPvs().Merge(front.GetPvs(), back.GetPvs()); 
    159161 
    160         // merge ray sets 
     162        //-- merge ray sets 
    161163        stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end()); 
    162164        stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end()); 
     
    223225   mRenderSimulator = new BspRenderSimulator(bspTree); 
    224226   InitRenderSimulator(); 
     227} 
     228 
     229 
     230BspViewCellsManager::~BspViewCellsManager() 
     231{ 
     232        ViewCellContainer vc; 
     233        mBspTree->CollectViewCells(vc); 
     234 
     235        CLEAR_CONTAINER(vc); 
    225236} 
    226237 
     
    336347        int pvsSize = 0; 
    337348 
    338         BspViewCellsStatistics vcStats; 
     349        ViewCellsStatistics vcStats; 
    339350        mBspTree->EvaluateViewCellsStats(vcStats); 
    340351        Debug << "original view cell partition:\n" << vcStats << endl; 
     
    438449 
    439450        //-- recount pvs 
    440         BspViewCellsStatistics vcStats; 
     451        ViewCellsStatistics vcStats; 
    441452        mBspTree->EvaluateViewCellsStats(vcStats); 
    442453 
     
    721732                return false; 
    722733 
    723         // change view cells of all leaves associated with the 
    724         // previous view cells 
    725  
     734        //-- change pointer to view cells of all leaves associated with the previous view cells 
    726735        BspViewCell *fVc = front->GetViewCell(); 
    727736        BspViewCell *bVc = back->GetViewCell(); 
     
    774783void BspViewCellsManager::PrintStatistics(ostream &s) const 
    775784{ 
    776         BspViewCellsStatistics vcStats; 
     785        ViewCellsStatistics vcStats; 
    777786        mBspTree->EvaluateViewCellsStats(vcStats); 
    778787        s << vcStats << endl; 
     
    973982/**********************************************************************/ 
    974983 
    975 VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples): 
     984VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree,  
     985                                                                                         int constructionSamples): 
    976986ViewCellsManager(constructionSamples),  
    977987mVspKdTree(vspKdTree) 
    978988{ 
    979989   mRenderSimulator = new VspKdRenderSimulator(vspKdTree); 
     990   mVspKdTree->SetViewCellsManager(this); 
     991 
    980992   InitRenderSimulator(); 
    981993} 
     994 
     995 
     996VspKdViewCellsManager::~VspKdViewCellsManager() 
     997{ 
     998        ViewCellContainer vc; 
     999        mVspKdTree->CollectViewCells(vc); 
     1000 
     1001        CLEAR_CONTAINER(vc); 
     1002} 
     1003 
    9821004 
    9831005int VspKdViewCellsManager::Construct(const ObjectContainer &objects,  
     
    10151037                return 0; 
    10161038 
    1017         //if (castRay) 
    1018                 //mVspKdTree->CastRay(ray); 
     1039        if (castRay) 
     1040                mVspKdTree->CastRay(ray); 
    10191041 
    10201042        int sampleContributions = 0; 
    10211043 
    10221044        return sampleContributions; 
     1045} 
     1046 
     1047ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const 
     1048{ 
     1049        return new VspKdViewCell(mesh); 
    10231050} 
    10241051 
     
    10291056                return 0; 
    10301057 
    1031         return 0; 
     1058        return mVspKdTree->MergeLeaves(); 
    10321059} 
    10331060 
     
    10431070                Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");  
    10441071                //exporter->SetWireframe(); 
    1045                 exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize); 
    1046  
    1047                 Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl; 
     1072                //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize); 
     1073                exporter->ExportVspKdTree(*mVspKdTree); 
    10481074 
    10491075                if (0)  
     
    10731099        } 
    10741100 
     1101        //-- export single leaves 
    10751102        if (1) 
    10761103        { 
    1077                 vector<VspKdTreeLeaf *> leafContainer; 
    1078  
     1104                vector<VspKdLeaf *> leafContainer; 
    10791105                mVspKdTree->CollectLeaves(leafContainer); 
    10801106 
     
    10861112 
    10871113                        // export geometry 
    1088                         VspKdTreeLeaf *leaf = leafContainer[Random((int)leafContainer.size())];  
     1114                        VspKdLeaf *leaf = leafContainer[Random((int)leafContainer.size())];  
    10891115                        AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 
    10901116 
     
    11161142                }                        
    11171143        } 
     1144 
     1145        // evaluate maximal pvs 
     1146        ViewCellsStatistics vcStats; 
     1147        mVspKdTree->EvaluateViewCellsStats(vcStats); 
     1148         
     1149        //-- export final view cells 
     1150        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");  
     1151        //exporter->SetWireframe(); 
     1152        //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs); 
     1153        exporter->ExportVspKdTreeViewCells(*mVspKdTree); 
     1154 
     1155        Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl; 
     1156 
     1157        if (0)  
     1158                exporter->ExportGeometry(objects); 
     1159 
     1160        bool exportRays = false; 
     1161 
     1162        if (exportRays)  
     1163        { 
     1164                int raysSize = 2000; 
     1165                float prob = raysSize / (float)sampleRays.size(); 
     1166                 
     1167                exporter->SetWireframe(); 
     1168                         
     1169                RayContainer rays; 
     1170                 
     1171                for (int i = 0; i < sampleRays.size(); ++ i) 
     1172                { 
     1173                        if (RandomValue(0,1) < prob) 
     1174                                rays.push_back(sampleRays[i]); 
     1175                } 
     1176                exporter->ExportRays(rays, 1000, RgbColor(1, 0, 0)); 
     1177        } 
     1178 
     1179        delete exporter; 
    11181180} 
    11191181 
     
    11251187void VspKdViewCellsManager::PrintStatistics(ostream &s) const 
    11261188{ 
     1189        ViewCellsStatistics vcStats; 
     1190 
     1191        mVspKdTree->EvaluateViewCellsStats(vcStats); 
     1192        Debug << vcStats << endl; 
    11271193} 
    11281194 
     
    11411207} 
    11421208 
     1209 
     1210 
     1211VspBspViewCellsManager::~VspBspViewCellsManager() 
     1212{ 
     1213        ViewCellContainer vc; 
     1214        mVspBspTree->CollectViewCells(vc); 
     1215 
     1216        CLEAR_CONTAINER(vc); 
     1217} 
     1218 
    11431219bool VspBspViewCellsManager::ViewCellsConstructed() const 
    11441220{ 
    11451221        return mVspBspTree->GetRoot() != NULL; 
    11461222} 
     1223 
    11471224 
    11481225ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const 
     
    12471324 
    12481325         
    1249         BspViewCellsStatistics vcStats; 
     1326        ViewCellsStatistics vcStats; 
    12501327        mVspBspTree->EvaluateViewCellsStats(vcStats); 
    12511328        Debug << "original view cell partition:\n" << vcStats << endl; 
     
    13401417 
    13411418        //-- recount pvs 
    1342         BspViewCellsStatistics vcStats; 
     1419        ViewCellsStatistics vcStats; 
    13431420        mVspBspTree->EvaluateViewCellsStats(vcStats); 
    13441421 
     
    16281705void VspBspViewCellsManager::PrintStatistics(ostream &s) const 
    16291706{ 
    1630         BspViewCellsStatistics vcStats; 
     1707        ViewCellsStatistics vcStats; 
    16311708        mVspBspTree->EvaluateViewCellsStats(vcStats); 
    16321709        s << vcStats << endl; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

    r452 r462  
    3939        ViewCellsManager(); 
    4040 
    41         ~ViewCellsManager(); 
     41        virtual ~ViewCellsManager(); 
    4242 
    4343        /** Constructs view cell container with a given number of samples. 
     
    221221        void PrintStatistics(ostream &s) const; 
    222222 
     223        ~BspViewCellsManager(); 
    223224protected: 
    224225 
     
    303304        VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples); 
    304305 
     306        ~VspKdViewCellsManager(); 
     307 
    305308        int Construct(const ObjectContainer &objects,  
    306309                                  const VssRayContainer &rays, 
     
    321324        virtual void PrintStatistics(ostream &s) const; 
    322325 
     326        ViewCell *GenerateViewCell(Mesh *mesh) const; 
     327 
    323328protected: 
    324329 
     
    338343 
    339344        VspBspViewCellsManager(VspBspTree *tree, int constructionSamples); 
     345 
     346        ~VspBspViewCellsManager(); 
    340347 
    341348        int Construct(const ObjectContainer &objects,  
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

    r452 r462  
    12201220} 
    12211221 
    1222 void VspBspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const 
     1222void VspBspTree::EvaluateViewCellsStats(ViewCellsStatistics &stat) const 
    12231223{ 
    12241224        stat.Reset(); 
     
    12391239                if (node->IsLeaf())  
    12401240                { 
    1241                         ++ stat.bspLeaves; 
     1241                        ++ stat.leaves; 
    12421242 
    12431243                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell(); 
     
    12611261                                        stat.minPvs = pvsSize; 
    12621262 
    1263                                 if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves) 
    1264                                         stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();            
     1263                                if ((int)viewCell->mBspLeaves.size() > stat.maxLeaves) 
     1264                                        stat.maxLeaves = (int)viewCell->mBspLeaves.size();               
    12651265                        } 
    12661266                } 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

    r448 r462  
    1919class AxisAlignedBox3; 
    2020class Ray; 
     21class ViewCellsStatistics; 
    2122 
    2223/*class BspNodeGeometry; 
    2324class BspTreeStatistics; 
    24 class BspViewCellsStatistics; 
     25class ViewCellsStatistics; 
    2526class BspNode; 
    2627class BspLeaf; 
     
    196197        /** Traverses tree and counts all view cells as well as their PVS size. 
    197198        */ 
    198         void EvaluateViewCellsStats(BspViewCellsStatistics &stat) const; 
     199        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 
    199200 
    200201 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

    r453 r462  
    2525#include "Ray.h" 
    2626#include "RayInfo.h" 
     27#include "ViewCell.h" 
    2728#include "ViewCellsManager.h" 
    28 #include "ViewCell.h" 
     29#include "ViewCellBsp.h" 
    2930 
    3031// Static variables 
    31 int VspKdTreeLeaf::mailID = 0; 
     32int VspKdLeaf::sMailId = 0; 
     33int MergeCandidate::sMaxPvsSize = 150; 
     34 
    3235 
    3336#define USE_FIXEDPOINT_T 0 
     
    7073 
    7174/**************************************************************/ 
    72 /*                class VspKdTreeNode implementation          */ 
     75/*                class VspKdNode implementation          */ 
    7376/**************************************************************/ 
    7477 
    7578// Inline constructor 
    76 VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p): 
     79VspKdNode::VspKdNode(VspKdInterior *p): 
    7780mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)  
    7881{} 
    7982 
    80 VspKdTreeNode::~VspKdTreeNode()  
     83VspKdNode::~VspKdNode()  
    8184{}; 
    8285 
    83 inline VspKdTreeInterior *VspKdTreeNode::GetParent() const 
     86inline VspKdInterior *VspKdNode::GetParent() const 
    8487{ 
    8588        return mParent; 
    8689} 
    8790 
    88 inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p) 
     91inline void VspKdNode::SetParent(VspKdInterior *p) 
    8992{ 
    9093        mParent = p; 
    9194} 
    9295 
    93 bool VspKdTreeNode::IsLeaf() const  
     96bool VspKdNode::IsLeaf() const  
    9497{  
    9598        return mAxis == -1;  
    9699} 
    97100   
    98 int VspKdTreeNode::GetAccessTime()  
     101int VspKdNode::GetAccessTime()  
    99102{ 
    100103        return 0x7FFFFFF; 
     
    102105 
    103106/**************************************************************/ 
    104 /*                VspKdTreeInterior implementation            */ 
     107/*                VspKdInterior implementation            */ 
    105108/**************************************************************/ 
    106109 
    107 VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p): 
    108 VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1) 
    109 { 
    110 } 
    111  
    112 int VspKdTreeInterior::GetAccessTime() 
     110VspKdInterior::VspKdInterior(VspKdInterior *p): 
     111VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1) 
     112{ 
     113} 
     114 
     115int VspKdInterior::GetAccessTime() 
    113116{ 
    114117        return mLastAccessTime; 
    115118} 
    116119 
    117 void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f)  
     120void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f)  
    118121{ 
    119122        mBack = b; 
     
    123126} 
    124127 
    125 void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode *oldChild,  
    126                                                                                  VspKdTreeNode *newChild) 
     128void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,  
     129                                                                                 VspKdNode *newChild) 
    127130{ 
    128131        if (mBack == oldChild) 
     
    132135} 
    133136 
    134 int VspKdTreeInterior::Type() const   
     137int VspKdInterior::Type() const   
    135138{  
    136139        return EInterior;  
    137140} 
    138141   
    139 VspKdTreeInterior::~VspKdTreeInterior() 
     142VspKdInterior::~VspKdInterior() 
    140143{ 
    141144        DEL_PTR(mBack); 
     
    143146} 
    144147   
    145 void VspKdTreeInterior::Print(ostream &s) const  
     148void VspKdInterior::Print(ostream &s) const  
    146149{ 
    147150        switch (mAxis) 
     
    161164} 
    162165         
    163 int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)  
     166int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)  
    164167{ 
    165168        return rayData.ComputeRayIntersection(mAxis, mPosition, t); 
    166169} 
    167170 
    168 VspKdTreeNode *VspKdTreeInterior::GetBack() const 
     171VspKdNode *VspKdInterior::GetBack() const 
    169172{ 
    170173        return mBack; 
    171174} 
    172175 
    173 VspKdTreeNode *VspKdTreeInterior::GetFront() const 
     176VspKdNode *VspKdInterior::GetFront() const 
    174177{ 
    175178        return mFront; 
     
    178181 
    179182/**************************************************************/ 
    180 /*              class VspKdTreeLeaf implementation            */ 
     183/*              class VspKdLeaf implementation            */ 
    181184/**************************************************************/ 
    182 VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,      const int nRays): 
    183 VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL) 
     185 
     186 
     187VspKdLeaf::VspKdLeaf(VspKdInterior *p,  const int nRays): 
     188VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL) 
    184189{ 
    185190        mRays.reserve(nRays); 
    186191} 
    187192 
    188 VspKdTreeLeaf::~VspKdTreeLeaf()  
    189 {} 
    190  
    191 int VspKdTreeLeaf::Type() const   
     193VspKdLeaf::~VspKdLeaf()  
     194{ 
     195} 
     196 
     197int VspKdLeaf::Type() const   
    192198{  
    193199        return ELeaf;  
    194200} 
    195201 
    196 void VspKdTreeLeaf::Print(ostream &s) const  
     202void VspKdLeaf::Print(ostream &s) const  
    197203{ 
    198204        s << endl << "L: r = " << (int)mRays.size() << endl; 
    199205}; 
    200206 
    201 void VspKdTreeLeaf::AddRay(const RayInfo &data)  
     207void VspKdLeaf::AddRay(const RayInfo &data)  
    202208{ 
    203209        mValidPvs = false; 
     
    206212} 
    207213 
    208 int VspKdTreeLeaf::GetPvsSize() const  
     214int VspKdLeaf::GetPvsSize() const  
    209215{ 
    210216        return mPvsSize; 
    211217} 
    212218 
    213 void VspKdTreeLeaf::SetPvsSize(const int s)  
     219void VspKdLeaf::SetPvsSize(const int s)  
    214220{ 
    215221        mPvsSize = s; 
    216222} 
    217223 
    218 void VspKdTreeLeaf::Mail() 
     224void VspKdLeaf::Mail() 
    219225{  
    220         mMailbox = mailID;  
    221 } 
    222  
    223 void VspKdTreeLeaf::NewMail()  
     226        mMailbox = sMailId;  
     227} 
     228 
     229void VspKdLeaf::NewMail()  
    224230{  
    225         ++ mailID;  
    226 } 
    227  
    228 bool VspKdTreeLeaf::Mailed() const  
     231        ++ sMailId;  
     232} 
     233 
     234bool VspKdLeaf::Mailed() const  
    229235{  
    230         return mMailbox == mailID;  
    231 } 
    232  
    233 bool VspKdTreeLeaf::Mailed(const int mail)  
    234 { 
    235         return mMailbox >= mailID + mail; 
    236 } 
    237  
    238 float VspKdTreeLeaf::GetAvgRayContribution() const  
     236        return mMailbox == sMailId;  
     237} 
     238 
     239bool VspKdLeaf::Mailed(const int mail) const 
     240{ 
     241        return mMailbox == mail; 
     242} 
     243 
     244int VspKdLeaf::GetMailbox() const 
     245{ 
     246        return mMailbox; 
     247} 
     248 
     249float VspKdLeaf::GetAvgRayContribution() const  
    239250{ 
    240251        return GetPvsSize() / ((float)mRays.size() + Limits::Small); 
    241252} 
    242253 
    243 float VspKdTreeLeaf::GetSqrRayContribution() const  
     254float VspKdLeaf::GetSqrRayContribution() const  
    244255{ 
    245256        return sqr(GetAvgRayContribution()); 
    246257} 
    247258 
    248 RayInfoContainer &VspKdTreeLeaf::GetRays() 
     259RayInfoContainer &VspKdLeaf::GetRays() 
    249260{ 
    250261        return mRays; 
    251262} 
    252263 
    253 void VspKdTreeLeaf::ExtractPvs(ObjectContainer &objects) const 
     264void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const 
    254265{ 
    255266        RayInfoContainer::const_iterator it, it_end = mRays.end(); 
     
    264275} 
    265276 
    266 void VspKdTreeLeaf::GetRays(VssRayContainer &rays) 
     277void VspKdLeaf::GetRays(VssRayContainer &rays) 
    267278{ 
    268279        RayInfoContainer::const_iterator it, it_end = mRays.end(); 
     
    272283} 
    273284 
    274 ViewCell *VspKdTreeLeaf::GetViewCell() 
     285VspKdViewCell *VspKdLeaf::GetViewCell() 
    275286{ 
    276287        return mViewCell; 
    277288} 
    278289 
    279 /*********************************************************/ 
    280 /*            class VspKdTree implementation             */ 
    281 /*********************************************************/ 
    282  
    283  
    284 VspKdTree::VspKdTree(): mOnlyDrivingAxis(true) 
    285 {          
    286         environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth); 
    287         environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs); 
    288         environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays); 
    289         environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution); 
    290         environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio); 
    291         environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize); 
    292  
    293         mTermMinSize = sqr(mTermMinSize); 
    294  
    295         environment->GetFloatValue("VspKdTree.epsilon", mEpsilon); 
    296         environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi); 
    297          
    298         environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory); 
    299         environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory); 
    300      
    301         environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold); 
    302         environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth); 
    303  
    304         // split type 
    305         char sname[128]; 
    306         environment->GetStringValue("VspKdTree.splitType", sname); 
    307         string name(sname); 
    308                  
    309         Debug << "======= vsp kd tree options ========" << endl; 
    310         Debug << "max depth: "<< mTermMaxDepth << endl; 
    311         Debug << "min pvs: "<< mTermMinPvs << endl; 
    312         Debug << "min rays: "<< mTermMinRays << endl; 
    313         Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 
    314         Debug << "max cost ratio: "<< mTermMaxCostRatio << endl; 
    315         Debug << "min size: "<<mTermMinSize << endl; 
    316  
    317         if (name.compare("regular") == 0) 
    318         { 
    319                 Debug << "using regular split" << endl; 
    320                 splitType = ESplitRegular; 
    321         } 
    322         else 
    323         { 
    324                 if (name.compare("heuristic") == 0) 
    325                 { 
    326                         Debug << "using heuristic split" << endl; 
    327                         splitType = ESplitHeuristic; 
    328                 } 
    329                 else  
    330                 { 
    331                         cerr << "Invalid VspKdTree split type " << name << endl; 
    332                         exit(1); 
    333                 } 
    334         } 
    335  
    336         mRoot = NULL; 
    337  
    338         mSplitCandidates = new vector<SortableEntry>; 
    339 } 
    340  
    341  
    342 VspKdTree::~VspKdTree() 
    343 { 
    344         DEL_PTR(mRoot); 
    345         DEL_PTR(mSplitCandidates); 
    346 } 
    347  
    348 void VspKdStatistics::Print(ostream &app) const 
    349 { 
    350         app << "===== VspKdTree statistics ===============\n"; 
    351  
    352         app << "#N_RAYS ( Number of rays )\n" 
    353                 << rays << endl; 
    354    
    355         app << "#N_INITPVS ( Initial PVS size )\n" 
    356                 << initialPvsSize << endl; 
    357    
    358         app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; 
    359  
    360         app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n"; 
    361  
    362         app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; 
    363    
    364         for (int i=0; i<7; i++) 
    365                 app << splits[i] <<" "; 
    366         app << endl; 
    367  
    368         app << "#N_RAYREFS ( Number of rayRefs )\n" << 
    369                 rayRefs << "\n"; 
    370  
    371         app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" << 
    372                 rayRefs / (double)rays << "\n"; 
    373  
    374         app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" << 
    375                 rayRefs / (double)Leaves() << "\n"; 
    376  
    377         app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" << 
    378                 maxRayRefs << "\n"; 
    379  
    380   //  app << setprecision(4); 
    381  
    382         app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" << 
    383                 maxDepthNodes * 100 / (double)Leaves() << endl; 
    384  
    385         app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" << 
    386                 minPvsNodes * 100 / (double)Leaves() << endl; 
    387  
    388         app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" << 
    389                 minRaysNodes * 100 / (double)Leaves() << endl; 
    390  
    391         app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<< 
    392                 minSizeNodes * 100 / (double)Leaves() << endl; 
    393  
    394         app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" << 
    395                 maxRayContribNodes * 100 / (double)Leaves() << endl; 
    396  
    397         app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<< 
    398                 addedRayRefs << endl; 
    399  
    400         app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<< 
    401                 removedRayRefs << endl; 
    402  
    403         //  app << setprecision(4); 
    404  
    405         app << "#N_MAXPVS ( Maximal PVS size / leaf)\n" 
    406                 << maxPvsSize << endl; 
    407  
    408         app << "#N_CTIME  ( Construction time [s] )\n" 
    409                 << Time() << " \n"; 
    410  
    411         app << "===== END OF VspKdTree statistics ==========\n"; 
    412 } 
    413  
    414  
    415 void 
    416 VspKdTreeLeaf::UpdatePvsSize() 
     290void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell) 
     291{ 
     292        mViewCell = viewCell; 
     293} 
     294 
     295 
     296void VspKdLeaf::UpdatePvsSize() 
    417297{ 
    418298        if (!mValidPvs)  
     
    449329} 
    450330 
    451  
    452 void 
    453 VspKdTree::Construct(const VssRayContainer &rays, 
    454                                          AxisAlignedBox3 *forcedBoundingBox) 
     331/*********************************************************/ 
     332/*            class VspKdTree implementation             */ 
     333/*********************************************************/ 
     334 
     335 
     336 
     337VspKdTree::VspKdTree(): mOnlyDrivingAxis(true) 
     338{          
     339        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth); 
     340        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs); 
     341        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays); 
     342        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution); 
     343        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio); 
     344        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize); 
     345 
     346        mTermMinSize = sqr(mTermMinSize); 
     347 
     348        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon); 
     349        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi); 
     350         
     351        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory); 
     352        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory); 
     353     
     354        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold); 
     355        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth); 
     356 
     357        environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio); 
     358        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
     359 
     360        MergeCandidate::sMaxPvsSize = 300; // TODO: add option 
     361 
     362        // split type 
     363        char sname[128]; 
     364        environment->GetStringValue("VspKdTree.splitType", sname); 
     365        string name(sname); 
     366                 
     367        Debug << "======= vsp kd tree options ========" << endl; 
     368        Debug << "max depth: "<< mTermMaxDepth << endl; 
     369        Debug << "min pvs: "<< mTermMinPvs << endl; 
     370        Debug << "min rays: "<< mTermMinRays << endl; 
     371        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 
     372        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl; 
     373        Debug << "min size: "<<mTermMinSize << endl; 
     374 
     375        if (name.compare("regular") == 0) 
     376        { 
     377                Debug << "using regular split" << endl; 
     378                splitType = ESplitRegular; 
     379        } 
     380        else 
     381        { 
     382                if (name.compare("heuristic") == 0) 
     383                { 
     384                        Debug << "using heuristic split" << endl; 
     385                        splitType = ESplitHeuristic; 
     386                } 
     387                else  
     388                { 
     389                        cerr << "Invalid VspKdTree split type " << name << endl; 
     390                        exit(1); 
     391                } 
     392        } 
     393 
     394        mRoot = NULL; 
     395 
     396        mSplitCandidates = new vector<SortableEntry>; 
     397} 
     398 
     399 
     400VspKdTree::~VspKdTree() 
     401{ 
     402        DEL_PTR(mRoot); 
     403        DEL_PTR(mSplitCandidates); 
     404} 
     405 
     406void VspKdStatistics::Print(ostream &app) const 
     407{ 
     408        app << "===== VspKdTree statistics ===============\n"; 
     409 
     410        app << "#N_RAYS ( Number of rays )\n" 
     411                << rays << endl; 
     412   
     413        app << "#N_INITPVS ( Initial PVS size )\n" 
     414                << initialPvsSize << endl; 
     415   
     416        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; 
     417 
     418        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n"; 
     419 
     420        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; 
     421   
     422        for (int i=0; i<7; i++) 
     423                app << splits[i] <<" "; 
     424        app << endl; 
     425 
     426        app << "#N_RAYREFS ( Number of rayRefs )\n" << 
     427                rayRefs << "\n"; 
     428 
     429        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" << 
     430                rayRefs / (double)rays << "\n"; 
     431 
     432        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" << 
     433                rayRefs / (double)Leaves() << "\n"; 
     434 
     435        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" << 
     436                maxRayRefs << "\n"; 
     437 
     438  //  app << setprecision(4); 
     439 
     440        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" << 
     441                maxDepthNodes * 100 / (double)Leaves() << endl; 
     442 
     443        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" << 
     444                minPvsNodes * 100 / (double)Leaves() << endl; 
     445 
     446        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" << 
     447                minRaysNodes * 100 / (double)Leaves() << endl; 
     448 
     449        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<< 
     450                minSizeNodes * 100 / (double)Leaves() << endl; 
     451 
     452        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" << 
     453                maxRayContribNodes * 100 / (double)Leaves() << endl; 
     454 
     455        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<< 
     456                addedRayRefs << endl; 
     457 
     458        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<< 
     459                removedRayRefs << endl; 
     460 
     461        //  app << setprecision(4); 
     462 
     463        app << "#N_( Maximal PVS size / leaf)\n" 
     464                << maxPvsSize << endl; 
     465 
     466        app << "#N_CTIME  ( Construction time [s] )\n" 
     467                << Time() << " \n"; 
     468 
     469        app << "===== END OF VspKdTree statistics ==========\n"; 
     470} 
     471 
     472 
     473void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const 
     474{ 
     475        stack<VspKdNode *> nodeStack; 
     476        nodeStack.push(mRoot); 
     477 
     478        ViewCell::NewMail(); 
     479 
     480        while (!nodeStack.empty())  
     481        { 
     482                VspKdNode *node = nodeStack.top(); 
     483                nodeStack.pop(); 
     484 
     485                if (node->IsLeaf())  
     486                { 
     487                        ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 
     488 
     489                        if (!viewCell->Mailed())  
     490                        { 
     491                                viewCell->Mail(); 
     492                                viewCells.push_back(viewCell); 
     493                        } 
     494                } 
     495                else  
     496                { 
     497                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     498 
     499                        nodeStack.push(interior->GetFront()); 
     500                        nodeStack.push(interior->GetBack()); 
     501                } 
     502        } 
     503} 
     504 
     505void VspKdTree::Construct(const VssRayContainer &rays, 
     506                                                  AxisAlignedBox3 *forcedBoundingBox) 
    455507{ 
    456508        mStat.Start(); 
     
    459511        DEL_PTR(mRoot); 
    460512 
    461         mRoot = new VspKdTreeLeaf(NULL, (int)rays.size()); 
     513        mRoot = new VspKdLeaf(NULL, (int)rays.size()); 
    462514 
    463515        // first construct a leaf that will get subdivided 
    464         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(mRoot); 
     516        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot); 
    465517         
    466518        mStat.nodes = 1; 
     
    523575 
    524576 
    525 VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata) 
    526 { 
    527         VspKdTreeNode *result = NULL; 
     577VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata) 
     578{ 
     579        VspKdNode *result = NULL; 
    528580 
    529581        priority_queue<TraversalData> tStack; 
     
    562614                tStack.pop();     
    563615                 
    564                 VspKdTreeNode *node = SubdivideNode((VspKdTreeLeaf *) data.mNode, 
     616                VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode, 
    565617                                                                                        data.mBox, backBox,     frontBox); 
    566618                if (result == NULL) 
     
    569621                if (!node->IsLeaf())  
    570622                { 
    571                         VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node); 
     623                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
    572624 
    573625                        // push the children on the stack 
     
    586638 
    587639// returns selected plane for subdivision 
    588 int VspKdTree::SelectPlane(VspKdTreeLeaf *leaf, 
     640int VspKdTree::SelectPlane(VspKdLeaf *leaf, 
    589641                                                   const AxisAlignedBox3 &box, 
    590642                                                   float &position, 
     
    641693 
    642694                                                         
    643 float VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf, 
     695float VspKdTree::EvalCostRatio(VspKdLeaf *leaf, 
    644696                                                           const int axis, 
    645697                                                           const float position, 
     
    711763} 
    712764 
    713 float VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf, 
     765float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf, 
    714766                                                                          int &axis, 
    715767                                                                          float &position, 
     
    772824} 
    773825 
    774 float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf, 
     826float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf, 
    775827                                                                                int &axis, 
    776828                                                                                float &position, 
     
    895947} 
    896948 
    897 void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node, 
     949void VspKdTree::SortSplitCandidates(VspKdLeaf *node, 
    898950                                                                        const int axis) 
    899951{ 
     
    930982{ 
    931983        // the node became a leaf -> evaluate stats for leafs 
    932         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode); 
     984        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode); 
    933985 
    934986        if (leaf->GetPvsSize() > mStat.maxPvsSize) 
     
    9561008 
    9571009 
    958 inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf,  
     1010inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,  
    9591011                                                                                          const AxisAlignedBox3 &box) const 
    9601012{ 
    9611013        return ((leaf->GetPvsSize() < mTermMinPvs) ||  
    9621014                    (leaf->mRays.size() < mTermMinRays) || 
    963                         (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) || 
     1015                        //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) || 
    9641016                        (leaf->mDepth >= mTermMaxDepth) ||  
    9651017                        (SqrMagnitude(box.Size()) <= mTermMinSize)); 
     
    9671019 
    9681020 
    969 VspKdTreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf, 
     1021VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf, 
    9701022                                                                                const AxisAlignedBox3 &box, 
    9711023                                                                                AxisAlignedBox3 &backBBox, 
     
    10051057 
    10061058        // add the new nodes to the tree 
    1007         VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent); 
     1059        VspKdInterior *node = new VspKdInterior(leaf->mParent); 
    10081060 
    10091061        node->mAxis = axis; 
     
    10141066        frontBBox = box; 
    10151067 
    1016         VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack); 
     1068        VspKdLeaf *back = new VspKdLeaf(node, raysBack); 
    10171069        back->SetPvsSize(pvsBack); 
    1018         VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront); 
     1070        VspKdLeaf *front = new VspKdLeaf(node, raysFront); 
    10191071        front->SetPvsSize(pvsFront); 
    10201072 
     
    10251077        node->SetupChildLinks(back, front); 
    10261078         
    1027         if (axis <= VspKdTreeNode::SPLIT_Z)  
     1079        if (axis <= VspKdNode::SPLIT_Z)  
    10281080        { 
    10291081                backBBox.SetMax(axis, position); 
     
    11101162int VspKdTree::ReleaseMemory(const int time) 
    11111163{ 
    1112         stack<VspKdTreeNode *> tstack; 
     1164        stack<VspKdNode *> tstack; 
    11131165 
    11141166        // find a node in the tree which subtree will be collapsed 
     
    11201172        while (!tstack.empty()) 
    11211173        { 
    1122                 VspKdTreeNode *node = tstack.top(); 
     1174                VspKdNode *node = tstack.top(); 
    11231175                tstack.pop(); 
    11241176     
    11251177                if (!node->IsLeaf())  
    11261178                { 
    1127                         VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node); 
     1179                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
    11281180                        // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl; 
    11291181                        if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)  
     
    11561208 
    11571209 
    1158 VspKdTreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf, 
     1210VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf, 
    11591211                                                                                const float sizeThreshold) 
    11601212{ 
    1161         VspKdTreeNode *node = leaf; 
     1213        VspKdNode *node = leaf; 
    11621214 
    11631215        AxisAlignedBox3 leafBBox = GetBBox(leaf); 
     
    11881240                                                   VssRayContainer &add) 
    11891241{ 
    1190         VspKdTreeLeaf::NewMail(); 
     1242        VspKdLeaf::NewMail(); 
    11911243 
    11921244        // schedule rays for removal 
     
    12181270 
    12191271void VspKdTree::RemoveRay(VssRay *ray, 
    1220                                                   vector<VspKdTreeLeaf *> *affectedLeaves, 
     1272                                                  vector<VspKdLeaf *> *affectedLeaves, 
    12211273                                                  const bool removeAllScheduledRays) 
    12221274{ 
     
    12431295                        // remove the ray from the leaf 
    12441296                        // find the ray in the leaf and swap it with the last ray... 
    1245                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.mNode; 
     1297                        VspKdLeaf *leaf = (VspKdLeaf *)data.mNode; 
    12461298       
    12471299                        if (!leaf->Mailed())  
     
    13291381                        // remove the ray from the leaf 
    13301382                        // find the ray in the leaf and swap it with the last ray 
    1331                         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode); 
     1383                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode); 
    13321384 
    13331385                        leaf->AddRay(data.mRayData); 
     
    13401392                                                                         stack<RayTraversalData> &tstack) 
    13411393{ 
    1342         VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(data.mNode); 
    1343    
    1344         if (in->mAxis <= VspKdTreeNode::SPLIT_Z)  
     1394        VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode); 
     1395   
     1396        if (in->mAxis <= VspKdNode::SPLIT_Z)  
    13451397        { 
    13461398            // determine the side of this ray with respect to the plane 
     
    13871439 
    13881440 
    1389 int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time) 
     1441int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time) 
    13901442{ 
    13911443        // first count all rays in the subtree 
    13921444        // use mail 1 for this purpose 
    1393         stack<VspKdTreeNode *> tstack; 
     1445        stack<VspKdNode *> tstack; 
    13941446         
    13951447        int rayCount = 0; 
     
    14131465                ++ collapsedNodes; 
    14141466                 
    1415                 VspKdTreeNode *node = tstack.top(); 
     1467                VspKdNode *node = tstack.top(); 
    14161468                tstack.pop(); 
    14171469                if (node->IsLeaf())  
    14181470                { 
    1419                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node; 
     1471                        VspKdLeaf *leaf = (VspKdLeaf *) node; 
    14201472                         
    14211473                        for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
     
    14331485                else  
    14341486                { 
    1435                         tstack.push(((VspKdTreeInterior *)node)->GetFront()); 
    1436                         tstack.push(((VspKdTreeInterior *)node)->GetBack()); 
     1487                        tstack.push(((VspKdInterior *)node)->GetFront()); 
     1488                        tstack.push(((VspKdInterior *)node)->GetBack()); 
    14371489                } 
    14381490        } 
     
    14411493 
    14421494        // create a new node that will hold the rays 
    1443         VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount); 
     1495        VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount); 
    14441496         
    14451497        if (newLeaf->mParent) 
     
    14501502        while (!tstack.empty())  
    14511503        { 
    1452                 VspKdTreeNode *node = tstack.top(); 
     1504                VspKdNode *node = tstack.top(); 
    14531505                tstack.pop(); 
    14541506 
    14551507                if (node->IsLeaf())  
    14561508                { 
    1457                         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node); 
     1509                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    14581510 
    14591511                        for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
     
    14761528                else  
    14771529                { 
    1478                         VspKdTreeInterior *interior =  
    1479                                 dynamic_cast<VspKdTreeInterior *>(node); 
     1530                        VspKdInterior *interior =  
     1531                                dynamic_cast<VspKdInterior *>(node); 
    14801532                        tstack.push(interior->GetBack()); 
    14811533                        tstack.push(interior->GetFront()); 
     
    14861538        DEL_PTR(sroot); 
    14871539   
    1488         // for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin(); 
     1540        // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin(); 
    14891541    //      ri != newleaf->mRays.end(); ++ ri) 
    14901542        //     (*ri).ray->UnMail(2); 
     
    15101562 
    15111563 
    1512 int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const 
    1513 { 
    1514         stack<VspKdTreeNode *> tstack; 
     1564int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const 
     1565{ 
     1566        stack<VspKdNode *> tstack; 
    15151567        tstack.push(mRoot); 
    15161568 
     
    15201572        while (!tstack.empty())  
    15211573        { 
    1522                 VspKdTreeNode *node = tstack.top(); 
     1574                VspKdNode *node = tstack.top(); 
    15231575                tstack.pop(); 
    15241576     
    15251577          if (node->IsLeaf())  
    15261578                { 
    1527                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node; 
     1579                        VspKdLeaf *leaf = (VspKdLeaf *)node; 
    15281580                        for (RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    15291581                                 ri != leaf->mRays.end(); ++ ri) 
     
    15521604                else  
    15531605                { 
    1554                         VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node); 
     1606                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
    15551607         
    15561608                        if (in->mAxis < 3)  
     
    15781630                                                                                         float &avgRayContribution) 
    15791631{ 
    1580         stack<VspKdTreeNode *> tstack; 
     1632        stack<VspKdNode *> tstack; 
    15811633        tstack.push(mRoot); 
    15821634         
     
    15891641        while (!tstack.empty())  
    15901642        { 
    1591                 VspKdTreeNode *node = tstack.top(); 
     1643                VspKdNode *node = tstack.top(); 
    15921644                tstack.pop(); 
    15931645                if (node->IsLeaf())  
    15941646                { 
    15951647                        leaves++; 
    1596                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node; 
     1648                        VspKdLeaf *leaf = (VspKdLeaf *)node; 
    15971649                        float c = leaf->GetAvgRayContribution(); 
    15981650 
     
    16051657                }  
    16061658                else { 
    1607                         VspKdTreeInterior *in = (VspKdTreeInterior *)node; 
     1659                        VspKdInterior *in = (VspKdInterior *)node; 
    16081660                        // both nodes for directional splits 
    16091661                        tstack.push(in->GetFront()); 
     
    16211673                                                        SimpleRayContainer &rays) 
    16221674{ 
    1623         stack<VspKdTreeNode *> tstack; 
     1675        stack<VspKdNode *> tstack; 
    16241676        tstack.push(mRoot); 
    16251677         
    16261678        while (!tstack.empty())  
    16271679        { 
    1628                 VspKdTreeNode *node = tstack.top(); 
     1680                VspKdNode *node = tstack.top(); 
    16291681                tstack.pop(); 
    16301682                 
    16311683                if (node->IsLeaf())  
    16321684                { 
    1633                         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node); 
     1685                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    16341686 
    16351687                        float c = leaf->GetAvgRayContribution(); 
     
    16491701                else  
    16501702                { 
    1651                         VspKdTreeInterior *in =  
    1652                                 dynamic_cast<VspKdTreeInterior *>(node); 
     1703                        VspKdInterior *in =  
     1704                                dynamic_cast<VspKdInterior *>(node); 
    16531705                        // both nodes for directional splits 
    16541706                        tstack.push(in->GetFront()); 
     
    16631715float VspKdTree::GetAvgPvsSize() 
    16641716{ 
    1665         stack<VspKdTreeNode *> tstack; 
     1717        stack<VspKdNode *> tstack; 
    16661718        tstack.push(mRoot); 
    16671719 
     
    16711723        while (!tstack.empty())  
    16721724        { 
    1673                 VspKdTreeNode *node = tstack.top(); 
     1725                VspKdNode *node = tstack.top(); 
    16741726                tstack.pop(); 
    16751727                 
    16761728                if (node->IsLeaf())  
    16771729                { 
    1678                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node; 
     1730                        VspKdLeaf *leaf = (VspKdLeaf *)node; 
    16791731                        // update pvs size 
    16801732                        leaf->UpdatePvsSize(); 
     
    16841736                else  
    16851737                { 
    1686                         VspKdTreeInterior *in = (VspKdTreeInterior *)node; 
     1738                        VspKdInterior *in = (VspKdInterior *)node; 
    16871739                        // both nodes for directional splits 
    16881740                        tstack.push(in->GetFront()); 
     
    16941746} 
    16951747 
    1696 VspKdTreeNode *VspKdTree::GetRoot() const 
     1748VspKdNode *VspKdTree::GetRoot() const 
    16971749{ 
    16981750        return mRoot; 
    16991751} 
    17001752 
    1701 AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const 
     1753AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const 
    17021754{ 
    17031755        if (node->mParent == NULL) 
     
    17051757 
    17061758        if (!node->IsLeaf()) 
    1707                 return (dynamic_cast<VspKdTreeInterior *>(node))->mBox; 
     1759                return (dynamic_cast<VspKdInterior *>(node))->mBox; 
    17081760 
    17091761        if (node->mParent->mAxis >= 3) 
     
    17401792        return  
    17411793                (sizeof(VspKdTree) +  
    1742                  mStat.Leaves() * sizeof(VspKdTreeLeaf) + 
    1743                  mStat.Interior() * sizeof(VspKdTreeInterior) + 
     1794                 mStat.Leaves() * sizeof(VspKdLeaf) + 
     1795                 mStat.Interior() * sizeof(VspKdInterior) + 
    17441796                 mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f); 
    17451797} 
     
    17501802} 
    17511803 
    1752 int VspKdTree::ComputePvsSize(VspKdTreeNode *node,  
     1804int VspKdTree::ComputePvsSize(VspKdNode *node,  
    17531805                                                          const RayInfoContainer &globalRays) const 
    17541806{ 
     
    17661818} 
    17671819 
    1768 void VspKdTree::CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const 
    1769 { 
    1770         stack<VspKdTreeNode *> nodeStack; 
     1820void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const 
     1821{ 
     1822        stack<VspKdNode *> nodeStack; 
    17711823        nodeStack.push(mRoot); 
    17721824 
    17731825        while (!nodeStack.empty())  
    17741826        { 
    1775                 VspKdTreeNode *node = nodeStack.top(); 
     1827                VspKdNode *node = nodeStack.top(); 
    17761828                 
    17771829                nodeStack.pop(); 
     
    17791831                if (node->IsLeaf())  
    17801832                { 
    1781                         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node); 
     1833                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    17821834                        leaves.push_back(leaf); 
    17831835                }  
    17841836                else  
    17851837                { 
    1786                         VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node); 
     1838                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
    17871839 
    17881840                        nodeStack.push(interior->GetBack()); 
     
    17921844} 
    17931845 
    1794 int VspKdTree::FindNeighbors(VspKdTreeLeaf *n, 
    1795                                                          vector<VspKdTreeLeaf *> &neighbors, 
     1846int VspKdTree::FindNeighbors(VspKdLeaf *n, 
     1847                                                         vector<VspKdLeaf *> &neighbors, 
    17961848                                                         bool onlyUnmailed) 
    17971849{ 
    1798         stack<VspKdTreeNode *> nodeStack; 
     1850        stack<VspKdNode *> nodeStack; 
    17991851   
    18001852        nodeStack.push(mRoot); 
     
    18041856        while (!nodeStack.empty())  
    18051857        { 
    1806                 VspKdTreeNode *node = nodeStack.top(); 
     1858                VspKdNode *node = nodeStack.top(); 
    18071859                nodeStack.pop(); 
    18081860 
    18091861                if (node->IsLeaf())  
    18101862                { 
    1811                         VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node); 
     1863                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    18121864 
    18131865                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))  
     
    18161868                else  
    18171869                { 
    1818                         VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node); 
     1870                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
    18191871 
    18201872                        if (interior->mPosition > box.Max(interior->mAxis)) 
     
    18371889} 
    18381890 
    1839 void VspKdTree::MergeLeaves() 
    1840 { 
    1841         vector<VspKdTreeLeaf *> leaves; 
    1842         priority_queue<LeafPair> mergeCandidates; 
    1843         vector<VspKdTreeLeaf *> neighbors; 
    1844  
     1891 
     1892 
     1893void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm) 
     1894{ 
     1895        mViewCellsManager = vcm; 
     1896} 
     1897 
     1898 
     1899int VspKdTree::CastRay(Ray &ray) 
     1900{ 
     1901        int hits = 0; 
     1902   
     1903        stack<RayTraversalData> tStack; 
     1904   
     1905        float maxt = 1e6; 
     1906        float mint = 0; 
     1907 
     1908        Intersectable::NewMail(); 
     1909 
     1910        if (!mBox.GetMinMaxT(ray, &mint, &maxt)) 
     1911                return 0; 
     1912 
     1913        if (mint < 0) 
     1914                mint = 0; 
     1915   
     1916        maxt += Limits::Threshold; 
     1917   
     1918        Vector3 entp = ray.Extrap(mint); 
     1919        Vector3 extp = ray.Extrap(maxt); 
     1920   
     1921        VspKdNode *node = mRoot; 
     1922        VspKdNode *farChild; 
     1923 
     1924        float position; 
     1925        int axis; 
     1926   
     1927        while (1)  
     1928        { 
     1929                if (!node->IsLeaf())  
     1930                { 
     1931                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
     1932                        position = in->mPosition; 
     1933                        axis = in->mAxis; 
     1934 
     1935                        if (entp[axis] <= position)  
     1936                        { 
     1937                                if (extp[axis] <= position)  
     1938                                { 
     1939                                        node = in->mBack; 
     1940                                        // cases N1,N2,N3,P5,Z2,Z3 
     1941                                        continue; 
     1942                                } else  
     1943                                { 
     1944                                        // case N4 
     1945                                        node = in->mBack; 
     1946                                        farChild = in->mFront; 
     1947                                } 
     1948                        } 
     1949                        else  
     1950                        { 
     1951                                if (position <= extp[axis])  
     1952                                { 
     1953                                        node = in->mFront; 
     1954                                        // cases P1,P2,P3,N5,Z1 
     1955                                        continue; 
     1956                                }  
     1957                                else  
     1958                                { 
     1959                                        node = in->mFront; 
     1960                                        farChild = in->mBack; 
     1961                                        // case P4 
     1962                                } 
     1963                        } 
     1964 
     1965                        // $$ modification 3.5.2004 - hints from Kamil Ghais 
     1966                        // case N4 or P4 
     1967                        float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis); 
     1968                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO 
     1969                        extp = ray.GetLoc() + ray.GetDir()*tdist; 
     1970                        maxt = tdist; 
     1971                }  
     1972                else  
     1973                { 
     1974                        // compute intersection with all objects in this leaf 
     1975                        /*KdLeaf *leaf = (KdLeaf *) node; 
     1976                        if (ray.mFlags & Ray::STORE_KDLEAVES) 
     1977                                ray.kdLeaves.push_back(leaf); 
     1978                         
     1979                        ObjectContainer::const_iterator mi; 
     1980                        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++)  
     1981                        { 
     1982                                Intersectable *object = *mi; 
     1983                                if (!object->Mailed() )  
     1984                                { 
     1985                                        object->Mail(); 
     1986                                        if (ray.mFlags & Ray::STORE_TESTED_OBJECTS) 
     1987                                                ray.testedObjects.push_back(object); 
     1988                                        hits += object->CastRay(ray); 
     1989                                } 
     1990                        } 
     1991                         
     1992                        if (hits && ray.GetType() == Ray::LOCAL_RAY) 
     1993                                if (ray.intersections[0].mT <= maxt) 
     1994                                        break; 
     1995                         
     1996                        // get the next node from the stack 
     1997                        if (tStack.empty()) 
     1998                                break; 
     1999                         
     2000                        entp = extp; 
     2001                        mint = maxt; 
     2002                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
     2003                                break; 
     2004                         
     2005                        RayTraversalData &s  = tStack.top(); 
     2006                        node = s.mNode; 
     2007                        extp = s.mExitPoint; 
     2008                        maxt = s.mMaxT; 
     2009                        tStack.pop(); 
     2010                        */ 
     2011                } 
     2012        } 
     2013         
     2014        return hits; 
     2015} 
     2016 
     2017 
     2018void VspKdTree::GenerateViewCell(VspKdLeaf *leaf) 
     2019{ 
     2020        RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end(); 
     2021 
     2022        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell()); 
     2023        leaf->SetViewCell(vc); 
     2024 
     2025        vc->SetSize(GetBBox(leaf).GetVolume()); 
     2026        vc->mVspKdLeaves.push_back(leaf); 
     2027 
     2028        for (it = leaf->GetRays().begin(); it != it_end; ++ it) 
     2029        { 
     2030                VssRay *ray = (*it).mRay; 
     2031 
     2032                if (ray->mTerminationObject) 
     2033                        vc->GetPvs().AddSample(ray->mTerminationObject); 
     2034                 
     2035                if (ray->mOriginObject) 
     2036                        vc->GetPvs().AddSample(ray->mOriginObject); 
     2037        } 
     2038} 
     2039 
     2040 
     2041void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const 
     2042{ 
     2043        vcStat.Reset(); 
     2044 
     2045        stack<VspKdNode *> nodeStack; 
     2046        nodeStack.push(mRoot); 
     2047 
     2048        ViewCell::NewMail(); 
     2049 
     2050        // exclude root cell 
     2051        //mRootCell->Mail(); 
     2052 
     2053        while (!nodeStack.empty())  
     2054        { 
     2055                VspKdNode *node = nodeStack.top(); 
     2056                nodeStack.pop(); 
     2057 
     2058                if (node->IsLeaf())  
     2059                { 
     2060                        ++ vcStat.leaves; 
     2061 
     2062                        VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 
     2063 
     2064                        if (!viewCell->Mailed())  
     2065                        { 
     2066                                viewCell->Mail(); 
     2067                                 
     2068                                ++ vcStat.viewCells; 
     2069                                const int pvsSize = viewCell->GetPvs().GetSize(); 
     2070 
     2071                vcStat.pvs += pvsSize; 
     2072 
     2073                                if (pvsSize < 1) 
     2074                                        ++ vcStat.emptyPvs; 
     2075 
     2076                                if (pvsSize > vcStat.maxPvs) 
     2077                                        vcStat.maxPvs = pvsSize; 
     2078 
     2079                                if (pvsSize < vcStat.minPvs) 
     2080                                        vcStat.minPvs = pvsSize; 
     2081 
     2082                                if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves) 
     2083                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();           
     2084                        } 
     2085                } 
     2086                else  
     2087                { 
     2088                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     2089 
     2090                        nodeStack.push(interior->GetFront()); 
     2091                        nodeStack.push(interior->GetBack()); 
     2092                } 
     2093        } 
     2094} 
     2095 
     2096 
     2097bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2) 
     2098{ 
     2099        //-- change pointer to view cells of all leaves associated with the previous view cells 
     2100        VspKdViewCell *fVc = l1->GetViewCell(); 
     2101        VspKdViewCell *bVc = l2->GetViewCell(); 
     2102 
     2103        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>( 
     2104                mViewCellsManager->MergeViewCells(*fVc, *bVc)); 
     2105 
     2106        // if merge was unsuccessful 
     2107        if (!vc) return false; 
     2108 
     2109        // set new size of view cell 
     2110        vc->SetSize(fVc->GetSize() + bVc->GetSize()); 
     2111 
     2112        vector<VspKdLeaf *> fLeaves = fVc->mVspKdLeaves; 
     2113        vector<VspKdLeaf *> bLeaves = bVc->mVspKdLeaves; 
     2114 
     2115        vector<VspKdLeaf *>::const_iterator it; 
     2116 
     2117        //-- change view cells of all the other leaves the view cell belongs to 
     2118        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it) 
     2119        { 
     2120                (*it)->SetViewCell(vc); 
     2121                vc->mVspKdLeaves.push_back(*it); 
     2122        } 
     2123 
     2124        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it) 
     2125        { 
     2126                (*it)->SetViewCell(vc); 
     2127                vc->mVspKdLeaves.push_back(*it); 
     2128        } 
     2129 
     2130        // clean up old view cells 
     2131        DEL_PTR(fVc); 
     2132        DEL_PTR(bVc); 
     2133 
     2134        return true; 
     2135} 
     2136 
     2137 
     2138 
     2139int VspKdTree::MergeLeaves() 
     2140{ 
     2141        vector<VspKdLeaf *> leaves; 
     2142        priority_queue<MergeCandidate> mergeQueue; 
     2143         
     2144        // collect the leaves, e.g., the "voxels" that will build the view cells 
    18452145        CollectLeaves(leaves); 
    18462146 
    1847         VspKdTreeLeaf::NewMail(); 
    1848  
    1849         vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end(); 
    1850  
    1851  
     2147        int vcSize = (int)leaves.size(); 
     2148 
     2149        VspKdLeaf::NewMail(); 
     2150 
     2151        vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end(); 
     2152 
     2153        // generate view cells 
    18522154        for (it = leaves.begin(); it != it_end; ++ it) 
    1853         { 
    1854                 VspKdTreeLeaf *leaf = *it; 
    1855  
     2155                GenerateViewCell(*it); 
     2156 
     2157        // find merge candidates and push them into queue 
     2158        for (it = leaves.begin(); it != it_end; ++ it) 
     2159        { 
     2160                VspKdLeaf *leaf = *it; 
     2161                 
     2162                // no leaf is part of two merge candidates 
    18562163                if (!leaf->Mailed()) 
    18572164                { 
     2165                        leaf->Mail(); 
     2166 
     2167                        vector<VspKdLeaf *> neighbors; 
    18582168                        FindNeighbors(leaf, neighbors, true); 
    18592169 
    1860                         vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end(); 
    1861  
    1862                         for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit) 
    1863                                 mergeCandidates.push(LeafPair(leaf, *nit)); 
     2170                        vector<VspKdLeaf *>::const_iterator nit,  
     2171                                nit_end = neighbors.end(); 
     2172 
     2173                        for (nit = neighbors.begin(); nit != nit_end; ++ nit) 
     2174                                mergeQueue.push(MergeCandidate(leaf, *nit)); 
     2175                } 
     2176        } 
     2177 
     2178        int merged = 0; 
     2179 
     2180        float savedMaxCostRatio = 0; 
     2181 
     2182        Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl; 
     2183 
     2184        // use priority queue to merge leaves 
     2185        while (!mergeQueue.empty() &&  
     2186                   ((mMaxViewCells < vcSize) || 
     2187                    (mergeQueue.top().GetMergeCost() < mMaxCostRatio))) 
     2188        { 
     2189                ViewCell::NewMail(); 
     2190 
     2191                Debug << "=====================" << endl; 
     2192                MergeCandidate mc = mergeQueue.top(); 
     2193                mergeQueue.pop(); 
     2194                 
     2195                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 
     2196                // both view cells the same! 
     2197                { 
     2198                        Debug << "same view cell!!" << endl; 
     2199                        -- vcSize; 
     2200 
     2201                        continue; 
     2202                } 
     2203 
     2204                if (mc.Valid()) 
     2205                { 
     2206                        mc.GetLeaf1()->GetViewCell()->Mail(); 
     2207                        mc.GetLeaf2()->GetViewCell()->Mail(); 
    18642208                         
    1865                         leaf->Mail(); 
    1866                 } 
    1867         } 
    1868 } 
    1869  
     2209                        Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl; 
     2210                        savedMaxCostRatio = mc.GetMergeCost(); 
     2211 
     2212                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 
     2213                         
     2214                        ++ merged; 
     2215                        -- vcSize; 
     2216                } 
     2217                // merge candidate not valid, because one of the leaves was already 
     2218                // merged with another one 
     2219                else  
     2220                { 
     2221                        Debug << "not valid " << mc.GetMergeCost() << endl; 
     2222                         
     2223                        // validate and reinsert into queue 
     2224                        mc.SetValid(); 
     2225                        Debug << "ag. valid " << mc.GetMergeCost() << endl; 
     2226 
     2227                        mergeQueue.push(mc); 
     2228                } 
     2229        } 
     2230 
     2231        if (mergeQueue.empty()) 
     2232                Debug << "empty queue" << endl; 
     2233         
     2234        Debug << "max cost ratio: " << savedMaxCostRatio << endl; 
     2235 
     2236        return merged; 
     2237} 
    18702238 
    18712239 
     
    18752243 
    18762244 
    1877 MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2): 
    1878 mLeaf1(l1), mLeaf2(l2) 
    1879 {} 
    1880  
    1881 float MergeCandidate::EvaluateMergeCost() const 
    1882 { 
    1883         // pvs difference 
    1884         VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell()); 
    1885         VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell()); 
     2245MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2): 
     2246mMergeCost(0), 
     2247mLeaf1(l1), 
     2248mLeaf2(l2), 
     2249mLeaf1Id(l1->GetViewCell()->mMailbox), 
     2250mLeaf2Id(l2->GetViewCell()->mMailbox) 
     2251{ 
     2252        EvalMergeCost(); 
     2253} 
     2254 
     2255 
     2256void MergeCandidate::EvalMergeCost() 
     2257{ 
     2258        // compute pvs differences 
     2259        VspKdViewCell *vc1 = mLeaf1->GetViewCell(); 
     2260        VspKdViewCell *vc2 = mLeaf2->GetViewCell(); 
     2261         
     2262        //VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell()); 
     2263        //VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell()); 
    18862264 
    18872265        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 
    1888          
    1889         //const int diff2 = vc2->GetPvs().Diff(vc1->GetPvs()); 
    1890         //const float simDiff = (float)max(diff1, diff2); 
    1891  
     2266        const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 
     2267 
     2268        //-- compute ratio of old cost  
     2269        //-- (added size of left and right view cell times pvs size) 
     2270        //-- to new rendering cost (size of merged view cell times pvs size) 
    18922271        const float oldCost =  
    1893                 vc1->GetSize() * vc1->GetPvs().GetSize() +  
    1894                 vc2->GetSize() * vc2->GetPvs().GetSize(); 
    1895  
    1896         const float mergedPvsCost =  
    1897                 (diff1 + vc1->GetPvs().GetSize()) * 
    1898                 (vc1->GetSize() + vc2->GetSize()); 
    1899  
    1900         return mergedPvsCost / oldCost; 
    1901 } 
     2272                (float)vc1->GetPvs().GetSize() * vc1->GetSize() +  
     2273                (float)vc2->GetPvs().GetSize() * vc2->GetSize(); 
     2274 
     2275        const float newCost =  
     2276                (float)vcPvs * (vc1->GetSize() + vc2->GetSize()); 
     2277 
     2278        mMergeCost = newCost / oldCost; 
     2279 
     2280        Debug << "******************************" << endl; 
     2281        Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl; 
     2282        if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 
     2283                mMergeCost += 1.0; 
     2284 
     2285        Debug << "old cost: " << oldCost << endl; 
     2286        Debug << "new cost: " << newCost << endl; 
     2287} 
     2288 
     2289void MergeCandidate::SetLeaf1(VspKdLeaf *l) 
     2290{ 
     2291        mLeaf1 = l; 
     2292} 
     2293 
     2294void MergeCandidate::SetLeaf2(VspKdLeaf *l) 
     2295{ 
     2296        mLeaf2 = l; 
     2297} 
     2298 
     2299VspKdLeaf *MergeCandidate::GetLeaf1() 
     2300{ 
     2301        return mLeaf1; 
     2302} 
     2303 
     2304VspKdLeaf *MergeCandidate::GetLeaf2() 
     2305{ 
     2306        return mLeaf2; 
     2307} 
     2308 
     2309bool MergeCandidate::Valid() const 
     2310{        
     2311        //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl; 
     2312        //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl; 
     2313 
     2314        return  
     2315                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&  
     2316                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id); 
     2317} 
     2318 
     2319float MergeCandidate::GetMergeCost() const 
     2320{ 
     2321        return mMergeCost; 
     2322} 
     2323 
     2324void MergeCandidate::SetValid() 
     2325{ 
     2326        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; 
     2327        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox; 
     2328         
     2329        EvalMergeCost(); 
     2330} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

    r454 r462  
    3434#include "Containers.h" 
    3535 
    36 class VspKdTreeLeaf; 
     36class VspKdLeaf; 
     37class ViewCellsManager; 
     38class VspKdViewCell; 
     39class ViewCellsStatistics; 
     40 
    3741 
    3842/** 
     
    4246 
    4347public: 
    44         VspKdTreeLeaf *mLeaf1; 
    45         VspKdTreeLeaf *mLeaf2; 
    46  
    47         MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2); 
     48 
     49        MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2); 
    4850 
    4951        /** Computes PVS difference between the leaves. 
     
    5153        //int ComputePvsDifference() const; 
    5254 
    53         /** Evaluates the merge costs of this leaf. 
    54         */ 
    55         float EvaluateMergeCost() const; 
    56  
    57         friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)  
     55        /** If this merge pair is still valid. 
     56        */ 
     57        bool Valid() const; 
     58 
     59        /** Sets this merge candidate to be valid. 
     60        */ 
     61        void SetValid(); 
     62 
     63        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 
    5864        { 
    59                 return leafa.EvaluateMergeCost() < leafb.EvaluateMergeCost(); 
     65                return leafb.GetMergeCost() < leafa.GetMergeCost(); 
    6066        } 
     67 
     68        void SetLeaf1(VspKdLeaf *l); 
     69        void SetLeaf2(VspKdLeaf *l); 
     70 
     71        VspKdLeaf *GetLeaf1(); 
     72        VspKdLeaf *GetLeaf2(); 
     73 
     74        /** Merge cost of this candidate pair. 
     75        */ 
     76        float GetMergeCost() const; 
     77 
     78        /// maximal pvs size 
     79        static int sMaxPvsSize; 
     80 
     81protected: 
     82         
     83        /** Evaluates the merge costs of the leaves. 
     84        */ 
     85        void EvalMergeCost(); 
     86 
     87        int mLeaf1Id; 
     88        int mLeaf2Id; 
     89 
     90        float mMergeCost; 
     91         
     92        VspKdLeaf *mLeaf1; 
     93        VspKdLeaf *mLeaf2; 
    6194}; 
    6295 
     
    142175 
    143176 
    144 class VspKdTreeInterior; 
     177class VspKdInterior; 
    145178 
    146179 
    147180/** Abstract superclass of Vsp-Kd-Tree nodes. 
    148181*/ 
    149 class VspKdTreeNode 
     182class VspKdNode 
    150183{ 
    151184public: 
     
    157190        /** Constructs new interior node from the parent node. 
    158191        */ 
    159         inline VspKdTreeNode(VspKdTreeInterior *p); 
     192        inline VspKdNode(VspKdInterior *p); 
    160193 
    161194        /** Destroys this node and the subtree. 
    162195        */ 
    163         virtual ~VspKdTreeNode(); 
     196        virtual ~VspKdNode(); 
    164197 
    165198        /** Type of the node (Einterior or ELeaf) 
     
    181214        /** Returns parent node. 
    182215        */ 
    183         VspKdTreeInterior *GetParent() const; 
     216        VspKdInterior *GetParent() const; 
    184217 
    185218        /** Sets parent node. 
    186219        */ 
    187         void SetParent(VspKdTreeInterior *p); 
     220        void SetParent(VspKdInterior *p); 
    188221 
    189222protected: 
     
    192225   
    193226        /// link to the parent 
    194         VspKdTreeInterior *mParent; 
     227        VspKdInterior *mParent; 
    195228 
    196229        enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ}; 
     
    206239// KD-tree node - interior node 
    207240// -------------------------------------------------------------- 
    208 class VspKdTreeInterior: public VspKdTreeNode 
     241class VspKdInterior: public VspKdNode 
    209242{ 
    210243public: 
     
    213246        /** Constructs new interior node from parent node. 
    214247        */ 
    215         VspKdTreeInterior(VspKdTreeInterior *p); 
     248        VspKdInterior(VspKdInterior *p); 
    216249                         
    217250        virtual int GetAccessTime(); 
     
    219252        virtual int Type() const; 
    220253   
    221         virtual ~VspKdTreeInterior(); 
     254        virtual ~VspKdInterior(); 
    222255     
    223256        virtual void Print(ostream &s) const; 
     
    225258        /** Returns back child. 
    226259        */ 
    227         inline VspKdTreeNode *GetBack() const; 
     260        inline VspKdNode *GetBack() const; 
    228261        /** Returns front child. 
    229262        */ 
    230         inline VspKdTreeNode *GetFront() const; 
     263        inline VspKdNode *GetFront() const; 
    231264 
    232265protected: 
     
    234267        /** Sets pointers to back child and front child. 
    235268        */ 
    236         void SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f); 
     269        void SetupChildLinks(VspKdNode *b, VspKdNode *f); 
    237270 
    238271        /** Replaces the pointer to oldChild with a pointer to newChild. 
    239272        */ 
    240         void ReplaceChildLink(VspKdTreeNode *oldChild, VspKdTreeNode *newChild); 
     273        void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild); 
    241274  
    242275        /** Computes intersection of the ray with the node boundaries. 
     
    248281 
    249282        // pointers to children 
    250         VspKdTreeNode *mBack; 
    251         VspKdTreeNode *mFront; 
     283        VspKdNode *mBack; 
     284        VspKdNode *mFront; 
    252285 
    253286        // the bbox of the node 
     
    263296// KD-tree node - leaf node 
    264297// -------------------------------------------------------------- 
    265 class VspKdTreeLeaf: public VspKdTreeNode 
     298class VspKdLeaf: public VspKdNode 
    266299{ 
    267300public: 
     
    272305                @param nRays preallocates memory to store this number of rays 
    273306        */ 
    274         VspKdTreeLeaf(VspKdTreeInterior *p,     const int nRays); 
    275          
    276         virtual ~VspKdTreeLeaf(); 
     307        VspKdLeaf(VspKdInterior *p,     const int nRays); 
     308         
     309        virtual ~VspKdLeaf(); 
    277310 
    278311        virtual int Type() const;   
     
    317350        bool Mailed() const; 
    318351   
    319         bool Mailed(const int mail); 
    320  
     352        /** Returns true if mail equals the leaf mail box. 
     353        */ 
     354        bool Mailed(const int mail) const; 
     355 
     356        void SetViewCell(VspKdViewCell *viewCell); 
     357 
     358        /** Returns mail box of this leaf. 
     359        */ 
     360        int GetMailbox() const; 
     361 
     362        /** Returns view cell associated with this leaf. 
     363        */ 
     364        VspKdViewCell *GetViewCell(); 
     365 
     366        //////////////////////////////////////////// 
     367         
    321368        static void NewMail(); 
    322369 
    323         static int mailID; 
    324  
    325         /** Returns view cell. 
    326         */ 
    327         ViewCell *GetViewCell(); 
     370        static int sMailId; 
     371 
    328372 
    329373protected: 
     
    337381   
    338382        RayInfoContainer mRays; 
     383         
     384        /// true if mPvsSize is valid => PVS does not have to be updated 
    339385        bool mValidPvs; 
    340386 
    341         ViewCell *mViewCell; 
     387        /// the view cell associated with this leaf 
     388        VspKdViewCell *mViewCell; 
     389 
    342390private: 
     391        /// stores PVS size so we have to evaluate PVS size only once 
    343392        int mPvsSize; 
    344393}; 
     
    380429        struct TraversalData 
    381430        {   
    382                 VspKdTreeNode *mNode; 
     431                VspKdNode *mNode; 
    383432                AxisAlignedBox3 mBox; 
    384433                int mDepth; 
     
    387436                TraversalData() {} 
    388437 
    389                 TraversalData(VspKdTreeNode *n, const float p): 
     438                TraversalData(VspKdNode *n, const float p): 
    390439                mNode(n)//, mPriority(p) 
    391440                {} 
    392441 
    393                 TraversalData(VspKdTreeNode *n, const AxisAlignedBox3 &b, const int d): 
     442                TraversalData(VspKdNode *n,     const AxisAlignedBox3 &b, const int d): 
    394443                mNode(n), mBox(b), mDepth(d) {} 
    395444     
     
    406455                { 
    407456                        // return a.node->queries.size() < b.node->queries.size(); 
    408                         VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.mNode; 
    409                         VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.mNode; 
     457                        VspKdLeaf *leafa = (VspKdLeaf *) a.mNode; 
     458                        VspKdLeaf *leafb = (VspKdLeaf *) b.mNode; 
    410459#if 0 
    411460                        return 
     
    446495  { 
    447496          RayInfo mRayData; 
    448           VspKdTreeNode *mNode; 
     497          VspKdNode *mNode; 
    449498       
    450499          RayTraversalData() {} 
    451500           
    452           RayTraversalData(VspKdTreeNode *n, const RayInfo &data): 
     501          RayTraversalData(VspKdNode *n, const RayInfo &data): 
    453502          mRayData(data), mNode(n) {} 
    454503  }; 
     
    464513        /** Returns bounding box of the specified node. 
    465514        */ 
    466         AxisAlignedBox3 GetBBox(VspKdTreeNode *node) const; 
     515        AxisAlignedBox3 GetBBox(VspKdNode *node) const; 
    467516 
    468517        const VspKdStatistics &GetStatistics() const; 
     
    470519        /** Get the root of the tree. 
    471520        */ 
    472         VspKdTreeNode *GetRoot() const; 
     521        VspKdNode *GetRoot() const; 
    473522 
    474523        /** Returns average PVS size in tree. 
     
    484533        /** Collects leaves of this tree. 
    485534        */ 
    486         void CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const; 
     535        void CollectLeaves(vector<VspKdLeaf *> &leaves) const; 
    487536 
    488537        /** Merges leaves of this tree according to some criteria. 
    489538        */ 
    490         void MergeLeaves(); 
     539        int MergeLeaves(); 
    491540 
    492541        /** Finds neighbours of this node. 
     
    495544                @param onlyUnmailed if only unmailed neighbors are collected 
    496545        */ 
    497         int FindNeighbors(VspKdTreeLeaf *n,  
    498                                           vector<VspKdTreeLeaf *> &neighbors,  
     546        int FindNeighbors(VspKdLeaf *n,  
     547                                          vector<VspKdLeaf *> &neighbors,  
    499548                                          bool onlyUnmailed); 
     549 
     550         
     551        /** Sets pointer to view cells manager. 
     552        */ 
     553        void SetViewCellsManager(ViewCellsManager *vcm); 
     554 
     555        /** A ray is cast possible intersecting the tree. 
     556                @param the ray that is cast. 
     557                @returns the number of intersections with objects stored in the tree. 
     558        */ 
     559        int CastRay(Ray &ray); 
     560 
     561        /** Collects view cells generated by this tree. 
     562        */ 
     563        void CollectViewCells(ViewCellContainer &viewCells) const; 
     564 
     565        /** Traverses tree and counts all view cells as well as their PVS size. 
     566        */ 
     567        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 
    500568 
    501569protected: 
     
    506574        virtual void AddRays(VssRayContainer &add); 
    507575 
    508         VspKdTreeNode *Locate(const Vector3 &v); 
    509          
    510         VspKdTreeNode *SubdivideNode(VspKdTreeLeaf *leaf, 
     576        VspKdNode *Locate(const Vector3 &v); 
     577         
     578        VspKdNode *SubdivideNode(VspKdLeaf *leaf, 
    511579                                                                 const AxisAlignedBox3 &box, 
    512580                                                                 AxisAlignedBox3 &backBox, 
    513581                                                                 AxisAlignedBox3 &frontBox); 
    514582         
    515         VspKdTreeNode *Subdivide(const TraversalData &tdata); 
    516          
    517         int SelectPlane(VspKdTreeLeaf *leaf, 
     583        VspKdNode *Subdivide(const TraversalData &tdata); 
     584         
     585        int SelectPlane(VspKdLeaf *leaf, 
    518586                                        const AxisAlignedBox3 &box, 
    519587                                        float &position, 
     
    523591                                        int &pvsFront); 
    524592 
    525         void SortSplitCandidates(VspKdTreeLeaf *node, 
     593        void SortSplitCandidates(VspKdLeaf *node, 
    526594                                                         const int axis);        
    527595   
    528         float BestCostRatioHeuristic(VspKdTreeLeaf *node, 
     596        float BestCostRatioHeuristic(VspKdLeaf *node, 
    529597                                                                 int &axis, 
    530598                                                                 float &position, 
     
    534602                                                                 int &pvsFront); 
    535603 
    536         float BestCostRatioRegular(VspKdTreeLeaf *node,  
     604        float BestCostRatioRegular(VspKdLeaf *node,  
    537605                                                           int &axis, 
    538606                                                           float &position, 
     
    542610                                                           int &pvsFront); 
    543611         
    544         float EvalCostRatio(VspKdTreeLeaf *node, 
     612        float EvalCostRatio(VspKdLeaf *node, 
    545613                                                const int axis, 
    546614                                                const float position, 
     
    551619 
    552620 
    553         VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf, 
     621        VspKdNode * SubdivideLeaf(VspKdLeaf *leaf, 
    554622                                                                  const float SAThreshold); 
    555623 
    556624        void RemoveRay(VssRay *ray, 
    557                                    vector<VspKdTreeLeaf *> *affectedLeaves, 
     625                                   vector<VspKdLeaf *> *affectedLeaves, 
    558626                                   const bool removeAllScheduledRays); 
    559627 
     
    568636        int     GetRootPvsSize() const; 
    569637         
    570         int     GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const; 
     638        int     GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const; 
    571639 
    572640        void GetRayContributionStatistics(float &minRayContribution, 
     
    580648                @returns number of collapsed rays. 
    581649        */ 
    582         int CollapseSubtree(VspKdTreeNode *sroot, const int time); 
     650        int CollapseSubtree(VspKdNode *sroot, const int time); 
    583651         
    584652        int ReleaseMemory(const int time); 
    585653 
    586         bool TerminationCriteriaMet(const VspKdTreeLeaf *leaf,  
     654        bool TerminationCriteriaMet(const VspKdLeaf *leaf,  
    587655                                                                const AxisAlignedBox3 &box) const; 
    588656 
     
    590658                @returns PVS size of the intersection of this node bounding box with the rays. 
    591659        */ 
    592         int ComputePvsSize(VspKdTreeNode *node, const RayInfoContainer &globalRays) const; 
    593  
     660        int ComputePvsSize(VspKdNode *node,  
     661                                           const RayInfoContainer &globalRays) const; 
     662 
     663 
     664        /** Generates view cell for this leaf taking the ray contributions. 
     665        */ 
     666        void GenerateViewCell(VspKdLeaf *leaf); 
     667 
     668        /** Merges view cells of the two leaves. 
     669        */ 
     670        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2); 
     671 
     672         
    594673protected: 
    595674         
     
    597676        ///////////////////////////// 
    598677        // The core pointer 
    599         VspKdTreeNode *mRoot; 
     678        VspKdNode *mRoot; 
    600679   
    601680        ///////////////////////////// 
     
    615694         
    616695        // type of the splitting to use for the tree construction 
    617         enum {ESplitRegular, ESplitHeuristic }; 
     696        enum {ESplitRegular, ESplitHeuristic}; 
    618697        int splitType; 
    619698         
     
    637716        vector<SortableEntry> *mSplitCandidates; 
    638717         
     718        ViewCellsManager *mViewCellsManager; 
     719 
     720        /// maximal cost ratio of a merge 
     721        float mMaxCostRatio; 
     722 
    639723        ///////////////////////////// 
    640724        // Construction parameters 
     
    658742        float mTermMaxRayContribution; 
    659743 
     744        /// if only the "driving axis", i.e., the axis with the biggest extent 
     745        /// should be used for subdivision 
    660746        bool mOnlyDrivingAxis; 
    661747 
    662         typedef std::pair<VspKdTreeLeaf *, VspKdTreeLeaf *> LeafPair; 
     748        /// maximal numbers of view cells 
     749        int mMaxViewCells; 
    663750 
    664751        ///////////////////////////// 
     
    667754 
    668755 
    669 #endif // __LSDS_KDTREE_H__ 
    670  
     756#endif // __VSP_KDTREE_H__ 
     757 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r452 r462  
    578578 
    579579  //-- several visualizations and statistics 
    580   Debug << "===== Final view cells statistics ==========" << endl; 
    581  
    582580  mViewCellsManager->PrintStatistics(Debug); 
    583581 
  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

    r459 r462  
    593593bool X3dExporter::ExportVspKdTree(const VspKdTree &tree, const int maxPvs) 
    594594{ 
    595         stack<VspKdTreeNode *> tStack; 
     595        stack<VspKdNode *> tStack; 
    596596 
    597597        tStack.push(tree.GetRoot()); 
     
    604604        while (!tStack.empty())  
    605605        { 
    606                 VspKdTreeNode *node = tStack.top(); 
     606                VspKdNode *node = tStack.top(); 
    607607     
    608608                tStack.pop(); 
     
    634634                        if (maxPvs > 0) 
    635635                        { 
    636                                 VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node); 
     636                                VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    637637 
    638638                                mForcedMaterial.mDiffuseColor.b = 1.0f; 
     
    650650                else   
    651651                { 
    652                         VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node); 
     652                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
    653653                        tStack.push(interior->GetFront()); 
    654654                        tStack.push(interior->GetBack()); 
     
    658658        //ExportMesh(mesh); 
    659659        //DEL_PTR(mesh); 
     660 
     661        return true; 
     662} 
     663 
     664bool X3dExporter::ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs) 
     665{ 
     666        ViewCellContainer vc; 
     667 
     668        //if (maxPvs > 0) 
     669        mUseForcedMaterial = true; 
     670 
     671        tree.CollectViewCells(vc); 
     672 
     673        ViewCellContainer::const_iterator it, it_end = vc.end(); 
     674 
     675        for (it = vc.begin(); it != it_end; ++ it) 
     676        { 
     677                VspKdViewCell *viewCell = dynamic_cast<VspKdViewCell *>(*it); 
     678 
     679                if (maxPvs > 0) 
     680                {                        
     681                        mForcedMaterial.mDiffuseColor.b = 1.0f; 
     682                         
     683                        const float importance = (float)viewCell->GetPvs().GetSize() / (float)maxPvs; 
     684                        mForcedMaterial.mDiffuseColor.r = importance; 
     685                        mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r; 
     686                } 
     687                else  
     688                        mForcedMaterial = RandomMaterial(); 
     689 
     690                ExportVspKdTreeViewCell(tree, *viewCell); 
     691        } 
     692 
     693        return true; 
     694} 
     695 
     696bool X3dExporter::ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc) 
     697{ 
     698        vector<VspKdLeaf *>::const_iterator it, it_end = vc.mVspKdLeaves.end(); 
     699 
     700        for (it = vc.mVspKdLeaves.begin(); it != it_end; ++ it) 
     701                ExportBox(tree.GetBBox(*it)); 
    660702 
    661703        return true; 
  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

    r459 r462  
    2121class VspBspTree; 
    2222class BspNode; 
     23class VspKdViewCell; 
     24 
    2325 
    2426class X3dExporter : public Exporter 
     
    5557                                 ); 
    5658 
    57   bool  
     59  bool 
    5860  ExportVspKdTree(const VspKdTree &tree, const int maxPvs); 
    5961 
     
    6163 
    6264  bool 
    63   ExportScene(SceneGraphNode *root)  
     65  ExportScene(SceneGraphNode *root) 
    6466  { 
    6567    ExportSceneNode(root); 
    6668    return true; 
    6769  } 
    68    
    69   virtual void  
     70 
     71  virtual void 
    7072  ExportPolygon(Polygon3 *poly); 
    7173 
    72   virtual void  
     74  virtual void 
    7375  ExportPolygons(const PolygonContainer &polys); 
    7476 
     
    8587  ExportMesh(Mesh *mesh); 
    8688 
    87   virtual void  
     89  virtual void 
    8890  ExportViewCell(ViewCell *viewCell); 
    8991 
    90   virtual void  
     92  virtual void 
    9193  ExportViewCells(const ViewCellContainer &viewCells); 
    9294 
    93   virtual void  
     95  virtual void 
    9496  ExportGeometry(const ObjectContainer &objects); 
    9597 
     
    102104                         const RgbColor &color = RgbColor(1,1,1)); 
    103105 
    104   virtual void  
     106  virtual void 
    105107  ExportBspSplitPlanes(const BspTree &tree); 
    106    
    107   virtual void  
     108 
     109  virtual void 
    108110  ExportBspSplits(const BspTree &tree, const bool exportDepth); 
    109111 
     
    114116  ExportBspViewCellPartition(const BspTree &tree, const int maxPvs = 0); 
    115117 
    116   virtual void  
     118  virtual void 
    117119  ExportBspLeaves(const BspTree &tree, const int maxPvs = 0); 
    118120 
    119121 
    120   virtual void  
     122  virtual void 
    121123  ExportBspSplits(const VspBspTree &tree, const bool exportDepth); 
    122124 
    123125  virtual void 
    124126  ExportBspViewCellPartition(const VspBspTree &tree, const int maxPvs = 0); 
     127 
     128  virtual bool 
     129  ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0); 
    125130 
    126131protected: 
     
    135140  bool 
    136141  ExportBspTreeRayDensity(const BspTree &tree); 
    137    
     142 
    138143  void 
    139144  AddBoxToMesh(const AxisAlignedBox3 &box, 
     
    141146 
    142147  void ExportBspNodeSplits(BspNode *root, 
    143                                                    const AxisAlignedBox3 &box,  
     148                                                   const AxisAlignedBox3 &box, 
    144149                                                   const bool exportDepth, 
     150                                                   const bool epsilon); 
    145151 
     152  bool ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc); 
    146153 
    147                                                    const bool epsilon); 
    148154 
    149155  void ExportViewpoint(const Vector3 &point, const Vector3 &direction); 
    150156 
    151157}; 
    152   
     158 
    153159 
    154160 
Note: See TracChangeset for help on using the changeset viewer.