Changeset 465


Ignore:
Timestamp:
12/14/05 19:17:40 (19 years ago)
Author:
mattausch
Message:

worked on vspkd leaves merge, implemented post merge collapse

Location:
trunk/VUT
Files:
9 edited

Legend:

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

    r462 r465  
    1313#;../data/vienna/vienna-plane.x3d 
    1414#       filename ../data/vienna/viewcells-25-sel.x3d 
    15         filename ../data/atlanta/atlanta2.x3d 
     15#       filename ../data/atlanta/atlanta2.x3d 
    1616#       filename ../data/soda/soda.dat 
    17 #       filename ../data/soda/soda5.dat 
     17        filename ../data/soda/soda5.dat 
    1818} 
    1919 
     
    2626VssPreprocessor { 
    2727        samplesPerPass  100000 
    28         initialSamples 1000000 
    29         vssSamples 3000000 
     28        initialSamples 500000 
     29        vssSamples 200000 
    3030        vssSamplesPerPass 100000 
    3131        useImportanceSampling true 
     
    3838 
    3939        maxDepth        40 
    40         minPvs          3 
    41         minRays         100 
     40        minPvs          30 
     41        minRays         1000 
    4242        minSize         0.001 
    43         maxCostRatio    2.0 
     43        maxCostRatio    0.9 
    4444        maxRayContribution 0.05 
    4545         
    4646        maxTotalMemory  200 
    47         maxStaticMemory 100 
     47        maxStaticMemory 20 
    4848 
    4949        splitType regular 
     
    284284        Termination { 
    285285                maxDepth                40 
    286                 minPvs                  90 
    287                 minRays                 10 
     286                minPvs                  5 
     287                minRays                 500 
    288288                minSize                 0.1 
    289289                maxCostRatio            999.0 
     
    299299         
    300300        # maximal cost for merging a view cell 
    301         maxCostRatio 1.4 
     301        PostProcess { 
     302                maxCostRatio 5000000 
     303                minViewCells 100 
     304                maxPvsSize   50000 
     305        } 
    302306} 
    303307 
  • trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

    r464 r465  
    13981398                 "100000"); 
    13991399 
    1400   RegisterOption("VspKdTree.maxCostRatio", 
    1401                  optFloat, 
    1402                  "-vsp_kd_max_cost_ratio=", 
    1403                  "1.5"); 
    1404  
    14051400  RegisterOption("VspKdTree.Termination.maxDepth",  
    14061401                optInt,  
     
    14801475          "vsp_min_colldepth=",  
    14811476          "4"); 
    1482    
     1477 
     1478  RegisterOption("VspKdTree.PostProcess.maxCostRatio", 
     1479                 optFloat, 
     1480                 "-vsp_kd_post_process_max_cost_ratio=", 
     1481                 "1.5"); 
     1482 
     1483  RegisterOption("VspKdTree.PostProcess.minViewCells",  
     1484          optInt,  
     1485          "vsp_term_post_process_min_view_cells=",  
     1486          "1000"); 
     1487 
     1488  RegisterOption("VspKdTree.PostProcess.maxPvsSize",  
     1489          optInt,  
     1490          "vsp_term_post_process_max_pvs_size=",  
     1491          "100"); 
     1492 
    14831493  /************************************************************************************/ 
    14841494  /*                   VSS Preprocessor cells related options                         */ 
  • trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

    r463 r465  
    338338 
    339339 
    340 /********************************************************/ 
    341 /*     class BspRenderSimulator implementation          */ 
    342 /********************************************************/ 
     340/*************************************************************/ 
     341/*        class VspKdRenderSimulator implementation          */ 
     342/*************************************************************/ 
    343343 
    344344 
     
    358358 
    359359SimulationStatistics VspKdRenderSimulator::SimulateRendering() 
    360 { 
    361         SimulationStatistics simStat; 
     360{SimulationStatistics simStat; 
    362361 
    363362        simStat.Reset(); 
    364363        simStat.Start(); 
    365364 
    366         // TODO 
     365        Real renderTime = 0; 
     366         
     367        // overhead for loading the PVS of the view cells 
     368        float loadPvsOverhead = 0; 
     369        // probability that view point lies in a view cell 
     370        float pInVcTotal = 0; 
     371 
     372        // total probability that a view cell border is crossed 
     373/*      const float pCrossVcTotal = mVspBspTree->GetBoundingBox().SurfaceArea(); 
     374 
     375        // collect all view cells 
     376        ViewCellContainer viewCells; 
     377        mVspBspTree->CollectViewCells(viewCells); 
     378 
     379        ViewCellContainer::const_iterator it, it_end = viewCells.end(); 
     380 
     381        // surface area substitute for probability 
     382        PolygonContainer geom; 
     383float overallarea = 0; 
     384        for (it = viewCells.begin(); it != it_end; ++ it) 
     385        { 
     386                // compute view cell area 
     387                mVspBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(*it), geom); 
     388 
     389                const float area = Polygon3::GetArea(geom); 
     390                if (area < 0.0001) 
     391                        Debug << "warning, area: " << area << endl; 
     392                CLEAR_CONTAINER(geom); 
     393 
     394                // area substitute for view point probability 
     395                float pInVc = area; 
     396                                 
     397                // compute render time of PVS times probability that view point is in view cell 
     398                float vcCost = pInVc * RenderPvs(*(*it), mObjRenderCost); 
     399                //Debug << "p: " << pInVc << " rendercost: " << RenderPvs(*(*it), mObjRenderCost) << endl; 
     400                renderTime += vcCost; 
     401 
     402                if (vcCost > simStat.maxCost) 
     403                        simStat.maxCost = vcCost; 
     404                else if (vcCost < simStat.minCost) 
     405                        simStat.minCost = vcCost; 
     406 
     407                // probability that a view cell border is crossed 
     408                float pCrossVc = area * mMoveSpeed; 
     409 
     410                // crossing the border of a view cell is also depending on the move speed 
     411                loadPvsOverhead += pCrossVc * mVcOverhead; 
     412overallarea += area; 
     413                pInVcTotal += pInVc; 
     414        } 
     415        Debug << "overall area: " << overallarea << endl; 
     416         
     417        renderTime /= pInVcTotal; 
     418        loadPvsOverhead /= pCrossVcTotal; 
     419 
     420        simStat.avgRtWithoutOverhead = renderTime; 
     421        simStat.avgRenderTime = renderTime + loadPvsOverhead; 
     422         
     423        simStat.maxCost /= pInVcTotal; 
     424        simStat.minCost /= pInVcTotal; 
     425 
    367426        simStat.Stop(); 
    368  
     427*/ 
    369428        return simStat; 
    370429} 
    371430 
    372431Real VspKdRenderSimulator::RenderPvs(ViewCell &viewCell,  
    373                                                                           float objRenderTime) const 
     432                                                                         float objRenderTime) const 
    374433{ 
    375434        return 0; // TODO 
  • trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

    r463 r465  
    10371037                return 0; 
    10381038 
    1039         if (castRay) 
    1040                 mVspKdTree->CastRay(ray); 
     1039//      if (castRay) 
     1040//              mVspKdTree->CastRay(ray); 
    10411041 
    10421042        int sampleContributions = 0; 
     
    10641064        if (!ViewCellsConstructed()) 
    10651065                return; 
     1066 
     1067        bool exportRays = true; 
    10661068 
    10671069        //-- export tree leaves 
     
    10731075                exporter->ExportVspKdTree(*mVspKdTree); 
    10741076 
    1075                 if (0)  
     1077                if (1)  
    10761078                        exporter->ExportGeometry(objects); 
    1077  
    1078                 bool exportRays = false; 
    10791079 
    10801080                if (exportRays)  
     
    11491149        //-- export final view cells 
    11501150        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");  
    1151         //exporter->SetWireframe(); 
     1151        exporter->SetWireframe(); 
    11521152        //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs); 
    11531153        exporter->ExportVspKdTreeViewCells(*mVspKdTree); 
    11541154 
    1155         Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl; 
    1156  
    1157         if (0)  
     1155        if (1)  
     1156        { 
     1157                exporter->SetFilled(); 
    11581158                exporter->ExportGeometry(objects); 
    1159  
    1160         bool exportRays = false; 
    1161  
     1159        } 
    11621160        if (exportRays)  
    11631161        { 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

    r463 r465  
    4444        if (!object) 
    4545                return; 
    46                  
    47         if (side <= 0)  
    48         { 
    49                 if (!object->Mailed() && !object->Mailed(2))  
     46 
     47        if (side <= 0) 
     48        { 
     49                if (!object->Mailed() && !object->Mailed(2)) 
    5050                { 
    5151                        ++ pvsBack; 
     
    5757                } 
    5858        } 
    59          
     59 
    6060        if (side >= 0) 
    6161        { 
    62                 if (!object->Mailed(1) && !object->Mailed(2))  
     62                if (!object->Mailed(1) && !object->Mailed(2)) 
    6363                { 
    6464                        ++ pvsFront; 
     
    7878// Inline constructor 
    7979VspKdNode::VspKdNode(VspKdInterior *p): 
    80 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)  
     80mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 
    8181{} 
    8282 
    83 VspKdNode::~VspKdNode()  
     83VspKdNode::~VspKdNode() 
    8484{}; 
    8585 
     
    9494} 
    9595 
    96 bool VspKdNode::IsLeaf() const  
    97 {  
    98         return mAxis == -1;  
    99 } 
    100    
    101 int VspKdNode::GetAccessTime()  
     96bool VspKdNode::IsLeaf() const 
     97{ 
     98        return mAxis == -1; 
     99} 
     100 
     101int VspKdNode::GetAccessTime() 
    102102{ 
    103103        return 0x7FFFFFF; 
     
    118118} 
    119119 
    120 void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f)  
     120void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 
    121121{ 
    122122        mBack = b; 
     
    126126} 
    127127 
    128 void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,  
     128void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 
    129129                                                                                 VspKdNode *newChild) 
    130130{ 
     
    135135} 
    136136 
    137 int VspKdInterior::Type() const   
    138 {  
    139         return EInterior;  
    140 } 
    141    
     137int VspKdInterior::Type() const 
     138{ 
     139        return EInterior; 
     140} 
     141 
    142142VspKdInterior::~VspKdInterior() 
    143143{ 
     
    145145        DEL_PTR(mFront); 
    146146} 
    147    
    148 void VspKdInterior::Print(ostream &s) const  
     147 
     148void VspKdInterior::Print(ostream &s) const 
    149149{ 
    150150        switch (mAxis) 
     
    163163        mFront->Print(s); 
    164164} 
    165          
    166 int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)  
     165 
     166int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
    167167{ 
    168168        return rayData.ComputeRayIntersection(mAxis, mPosition, t); 
     
    191191} 
    192192 
    193 VspKdLeaf::~VspKdLeaf()  
    194 { 
    195 } 
    196  
    197 int VspKdLeaf::Type() const   
    198 {  
    199         return ELeaf;  
    200 } 
    201  
    202 void VspKdLeaf::Print(ostream &s) const  
     193VspKdLeaf::~VspKdLeaf() 
     194{ 
     195} 
     196 
     197int VspKdLeaf::Type() const 
     198{ 
     199        return ELeaf; 
     200} 
     201 
     202void VspKdLeaf::Print(ostream &s) const 
    203203{ 
    204204        s << endl << "L: r = " << (int)mRays.size() << endl; 
    205205}; 
    206206 
    207 void VspKdLeaf::AddRay(const RayInfo &data)  
     207void VspKdLeaf::AddRay(const RayInfo &data) 
    208208{ 
    209209        mValidPvs = false; 
     
    212212} 
    213213 
    214 int VspKdLeaf::GetPvsSize() const  
     214int VspKdLeaf::GetPvsSize() const 
    215215{ 
    216216        return mPvsSize; 
    217217} 
    218218 
    219 void VspKdLeaf::SetPvsSize(const int s)  
     219void VspKdLeaf::SetPvsSize(const int s) 
    220220{ 
    221221        mPvsSize = s; 
     
    223223 
    224224void VspKdLeaf::Mail() 
    225 {  
    226         mMailbox = sMailId;  
    227 } 
    228  
    229 void VspKdLeaf::NewMail()  
    230 {  
    231         ++ sMailId;  
    232 } 
    233  
    234 bool VspKdLeaf::Mailed() const  
    235 {  
    236         return mMailbox == sMailId;  
     225{ 
     226        mMailbox = sMailId; 
     227} 
     228 
     229void VspKdLeaf::NewMail() 
     230{ 
     231        ++ sMailId; 
     232} 
     233 
     234bool VspKdLeaf::Mailed() const 
     235{ 
     236        return mMailbox == sMailId; 
    237237} 
    238238 
     
    247247} 
    248248 
    249 float VspKdLeaf::GetAvgRayContribution() const  
     249float VspKdLeaf::GetAvgRayContribution() const 
    250250{ 
    251251        return GetPvsSize() / ((float)mRays.size() + Limits::Small); 
    252252} 
    253253 
    254 float VspKdLeaf::GetSqrRayContribution() const  
     254float VspKdLeaf::GetSqrRayContribution() const 
    255255{ 
    256256        return sqr(GetAvgRayContribution()); 
     
    296296void VspKdLeaf::UpdatePvsSize() 
    297297{ 
    298         if (!mValidPvs)  
     298        if (!mValidPvs) 
    299299        { 
    300300                Intersectable::NewMail(); 
    301301                int pvsSize = 0; 
    302                 for(RayInfoContainer::iterator ri = mRays.begin();  
     302                for(RayInfoContainer::iterator ri = mRays.begin(); 
    303303                        ri != mRays.end(); ++ ri) 
    304304                { 
    305                         if ((*ri).mRay->IsActive())  
     305                        if ((*ri).mRay->IsActive()) 
    306306                        { 
    307307                                Intersectable *object; 
    308308#if BIDIRECTIONAL_RAY 
    309309                                object = (*ri).mRay->mOriginObject; 
    310                          
    311                                 if (object && !object->Mailed())  
     310 
     311                                if (object && !object->Mailed()) 
    312312                                { 
    313313                                        ++ pvsSize; 
     
    316316#endif 
    317317                                object = (*ri).mRay->mTerminationObject; 
    318                                 if (object && !object->Mailed())  
     318                                if (object && !object->Mailed()) 
    319319                                { 
    320320                                        ++ pvsSize; 
     
    336336 
    337337VspKdTree::VspKdTree(): mOnlyDrivingAxis(true) 
    338 {          
     338{ 
    339339        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth); 
    340340        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs); 
     
    348348        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon); 
    349349        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi); 
    350          
     350 
    351351        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory); 
    352352        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory); 
    353      
     353 
    354354        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold); 
    355355        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth); 
    356356 
    357         environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio); 
    358         environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
    359  
    360         MergeCandidate::sMaxPvsSize = 300; // TODO: add option 
     357        //environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 
     358 
     359        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMinViewCells); 
     360        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMaxCostRatio); 
     361        environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize", 
     362                                                         MergeCandidate::sMaxPvsSize); 
    361363 
    362364        // split type 
     
    364366        environment->GetStringValue("VspKdTree.splitType", sname); 
    365367        string name(sname); 
    366                  
     368 
    367369        Debug << "======= vsp kd tree options ========" << endl; 
    368370        Debug << "max depth: "<< mTermMaxDepth << endl; 
     
    385387                        splitType = ESplitHeuristic; 
    386388                } 
    387                 else  
     389                else 
    388390                { 
    389391                        cerr << "Invalid VspKdTree split type " << name << endl; 
     
    410412        app << "#N_RAYS ( Number of rays )\n" 
    411413                << rays << endl; 
    412    
     414 
    413415        app << "#N_INITPVS ( Initial PVS size )\n" 
    414416                << initialPvsSize << endl; 
    415    
     417 
    416418        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; 
    417419 
     
    419421 
    420422        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; 
    421    
     423 
    422424        for (int i=0; i<7; i++) 
    423425                app << splits[i] <<" "; 
     
    478480        ViewCell::NewMail(); 
    479481 
    480         while (!nodeStack.empty())  
     482        while (!nodeStack.empty()) 
    481483        { 
    482484                VspKdNode *node = nodeStack.top(); 
    483485                nodeStack.pop(); 
    484486 
    485                 if (node->IsLeaf())  
     487                if (node->IsLeaf()) 
    486488                { 
    487489                        ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 
    488490 
    489                         if (!viewCell->Mailed())  
     491                        if (!viewCell->Mailed()) 
    490492                        { 
    491493                                viewCell->Mail(); 
     
    493495                        } 
    494496                } 
    495                 else  
     497                else 
    496498                { 
    497499                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     
    507509{ 
    508510        mStat.Start(); 
    509   
     511 
    510512        mMaxMemory = mMaxStaticMemory; 
    511513        DEL_PTR(mRoot); 
     
    515517        // first construct a leaf that will get subdivided 
    516518        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot); 
    517          
     519 
    518520        mStat.nodes = 1; 
    519521        mBox.Initialize(); 
     
    528530                mBox.Include((*ri)->GetOrigin()); 
    529531                        if ((*ri)->mTerminationObject) 
    530                                 mBox.Include((*ri)->GetTermination());  
     532                                mBox.Include((*ri)->GetTermination()); 
    531533                } 
    532534 
     
    537539                //leaf->AddRay(RayInfo(*ri)); 
    538540                VssRay *ray = *ri; 
    539                  
     541 
    540542                float minT, maxT; 
    541543 
     
    544546                { 
    545547                        float len = ray->Length(); 
    546                          
    547                         if (!len)  
     548 
     549                        if (!len) 
    548550                                len = Limits::Small; 
    549                  
    550                         leaf->AddRay(RayInfo(ray, minT / len, maxT / len));  
    551                 } 
    552         } 
    553          
     551 
     552                        leaf->AddRay(RayInfo(ray, minT / len, maxT / len)); 
     553                } 
     554        } 
     555 
    554556        mStat.rays = (int)leaf->mRays.size(); 
    555557        leaf->UpdatePvsSize(); 
    556          
     558 
    557559        mStat.initialPvsSize = leaf->GetPvsSize(); 
    558          
     560 
    559561        // Subdivide(); 
    560562        mRoot = Subdivide(TraversalData(leaf, mBox, 0)); 
    561563 
    562         if (mSplitCandidates)  
     564        if (mSplitCandidates) 
    563565        { 
    564566                // force release of this vector 
     
    566568                mSplitCandidates = new vector<SortableEntry>; 
    567569        } 
    568    
     570 
    569571        mStat.Stop(); 
    570572 
     
    581583        priority_queue<TraversalData> tStack; 
    582584        //stack<TraversalData> tStack; 
    583    
     585 
    584586        tStack.push(tdata); 
    585587 
    586588        AxisAlignedBox3 backBox; 
    587589        AxisAlignedBox3 frontBox; 
    588    
     590 
    589591        int lastMem = 0; 
    590592 
    591         while (!tStack.empty())  
     593        while (!tStack.empty()) 
    592594        { 
    593595                float mem = GetMemUsage(); 
    594                  
    595                 if (lastMem / 10 != ((int)mem) / 10)  
     596 
     597                if (lastMem / 10 != ((int)mem) / 10) 
    596598                { 
    597599                        Debug << mem << " MB" << endl; 
    598600                } 
    599601                lastMem = (int)mem; 
    600                  
    601                 if (1 && mem > mMaxMemory)  
     602 
     603                if (1 && mem > mMaxMemory) 
    602604                { 
    603605                        Debug << "memory limit reached: " << mem << endl; 
    604606                        // count statistics on unprocessed leafs 
    605                         while (!tStack.empty())  
     607                        while (!tStack.empty()) 
    606608                        { 
    607609                                EvaluateLeafStats(tStack.top()); 
     
    610612                        break; 
    611613                } 
    612      
     614 
    613615                TraversalData data = tStack.top(); 
    614                 tStack.pop();     
    615                  
     616                tStack.pop(); 
     617 
    616618                VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode, 
    617619                                                                                        data.mBox, backBox,     frontBox); 
    618620                if (result == NULL) 
    619621                        result = node; 
    620      
    621                 if (!node->IsLeaf())  
     622 
     623                if (!node->IsLeaf()) 
    622624                { 
    623625                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     
    626628                        tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1)); 
    627629                        tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1)); 
    628                 }  
    629                 else  
     630                } 
     631                else 
    630632                { 
    631633                        EvaluateLeafStats(data); 
     
    649651        int axis = 0; 
    650652        float costRatio = 0; 
    651          
    652         if (splitType == ESplitRegular)  
     653 
     654        if (splitType == ESplitRegular) 
    653655        { 
    654656                costRatio = BestCostRatioRegular(leaf, 
     
    659661                                                                                 pvsBack, 
    660662                                                                                 pvsFront); 
    661         }  
     663        } 
    662664        else if (splitType == ESplitHeuristic) 
    663665        { 
    664666                        costRatio = BestCostRatioHeuristic(leaf, 
    665                                                                                            axis,         
     667                                                                                           axis, 
    666668                                                                                           position, 
    667669                                                                                           raysBack, 
     
    670672                                                                                           pvsFront); 
    671673        } 
    672         else  
     674        else 
    673675        { 
    674676                cerr << "VspKdTree: Unknown split heuristics\n"; 
     
    676678        } 
    677679 
    678         if (costRatio > mTermMaxCostRatio)  
     680        if (costRatio > mTermMaxCostRatio) 
    679681        { 
    680682                Debug << "Too big cost ratio " << costRatio << endl; 
     
    683685 
    684686        if (0) 
    685                 Debug << "pvs=" << leaf->mPvsSize  
    686                           << " rays=" << (int)leaf->mRays.size()  
    687                           << " rc=" << leaf->GetAvgRayContribution()  
     687                Debug << "pvs=" << leaf->mPvsSize 
     688                          << " rays=" << (int)leaf->mRays.size() 
     689                          << " rc=" << leaf->GetAvgRayContribution() 
    688690                          << " axis=" << axis << endl; 
    689          
     691 
    690692        return axis; 
    691693} 
    692694 
    693695 
    694                                                          
     696 
    695697float VspKdTree::EvalCostRatio(VspKdLeaf *leaf, 
    696698                                                           const int axis, 
     
    709711 
    710712        Intersectable::NewMail(3); 
    711          
     713 
    712714        // eval pvs size 
    713715        int pvsSize = leaf->GetPvsSize(); 
     
    719721                        ri != leaf->mRays.end(); ++ ri) 
    720722                { 
    721  if (!(*ri).mRay->IsActive())  
     723 if (!(*ri).mRay->IsActive()) 
    722724                                                                continue; 
    723                                                                  
     725 
    724726                                                                // determine the side of this ray with respect to the plane 
    725727                                                                float t; 
    726728                                                                int side = (*ri).ComputeRayIntersection(axis, position, t); 
    727729                //                              (*ri).mRay->mSide = side; 
    728                          
     730 
    729731                if (side <= 0) 
    730732                        ++ raysBack; 
    731                                  
     733 
    732734                if (side >= 0) 
    733735                        ++ raysFront; 
    734                                  
     736 
    735737                AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront); 
    736         }        
     738        } 
    737739 
    738740        if (0) 
     
    743745                return sum / oldCost; 
    744746        } 
    745         else  
     747        else 
    746748        { 
    747749                AxisAlignedBox3 box = GetBBox(leaf); 
    748          
     750 
    749751                float minBox = box.Min(axis); 
    750752                float maxBox = box.Max(axis); 
    751753                float sizeBox = maxBox - minBox; 
    752                  
     754 
    753755                // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position); 
    754756                const float sum = pvsBack * (position - minBox) + pvsFront * (maxBox - position); 
    755757 
    756758                newCost = mCtDivCi + sum  / sizeBox; 
    757          
     759 
    758760                //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl; 
    759761                //  float oldCost = leaf->mRays.size(); 
    760762                const float oldCost = (float)pvsSize; 
    761                  
     763 
    762764                return newCost / oldCost; 
    763765        } 
     
    778780        float nCostRatio[3]; 
    779781        int bestAxis = -1; 
    780          
     782 
    781783        AxisAlignedBox3 sBox = GetBBox(leaf); 
    782784 
    783785        const int sAxis = sBox.Size().DrivingAxis(); 
    784786 
    785         for (axis = 0; axis < 3; ++ axis)  
    786         { 
    787                 if (!mOnlyDrivingAxis || axis == sAxis)  
    788                 { 
    789                          
     787        for (axis = 0; axis < 3; ++ axis) 
     788        { 
     789                if (!mOnlyDrivingAxis || axis == sAxis) 
     790                { 
     791 
    790792                        nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis]) * 0.5f; 
    791                                                  
     793 
    792794                        nCostRatio[axis] = EvalCostRatio(leaf, 
    793795                                                                                         axis, 
     
    803805                        else if (nCostRatio[axis] < nCostRatio[bestAxis]) 
    804806                        { 
    805                                 /*Debug << "pvs front " << nPvsBack[axis]  
     807                                /*Debug << "pvs front " << nPvsBack[axis] 
    806808                                          << " pvs back " << nPvsFront[axis] 
    807809                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/ 
    808810                                bestAxis = axis; 
    809811                        } 
    810                          
     812 
    811813                } 
    812814        } 
     
    821823        pvsBack = nPvsBack[bestAxis]; 
    822824        pvsFront = nPvsFront[bestAxis]; 
    823          
     825 
    824826        return nCostRatio[bestAxis]; 
    825827} 
     
    835837        AxisAlignedBox3 box = GetBBox(leaf); 
    836838        //      AxisAlignedBox3 dirBox = GetDirBBox(node); 
    837          
     839 
    838840        axis = box.Size().DrivingAxis(); 
    839                  
     841 
    840842        SortSplitCandidates(leaf, axis); 
    841    
     843 
    842844        // go through the lists, count the number of objects left and right 
    843845        // and evaluate the following cost funcion: 
    844846        // C = ct_div_ci  + (ql*rl + qr*rr)/queries 
    845          
     847 
    846848        int rl = 0, rr = (int)leaf->mRays.size(); 
    847849        int pl = 0, pr = leaf->GetPvsSize(); 
     
    850852        float maxBox = box.Max(axis); 
    851853        float sizeBox = maxBox - minBox; 
    852          
     854 
    853855        float minBand = minBox + 0.1f*(maxBox - minBox); 
    854856        float maxBand = minBox + 0.9f*(maxBox - minBox); 
    855          
     857 
    856858        float sum = rr*sizeBox; 
    857859        float minSum = 1e20f; 
    858          
     860 
    859861        Intersectable::NewMail(); 
    860862 
     
    866868                { 
    867869                        Intersectable *object = (*ri).mRay->mTerminationObject; 
    868                          
     870 
    869871                        if (object) 
    870                                 if (!object->Mailed())  
     872                                if (!object->Mailed()) 
    871873                                { 
    872874                                        object->Mail(); 
    873875                                        object->mCounter = 1; 
    874                                 }  
     876                                } 
    875877                                else 
    876878                                        ++ object->mCounter; 
    877879                } 
    878880        } 
    879          
     881 
    880882        Intersectable::NewMail(); 
    881          
     883 
    882884        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin(); 
    883                 ci < mSplitCandidates->end(); ++ ci)  
     885                ci < mSplitCandidates->end(); ++ ci) 
    884886        { 
    885887                VssRay *ray; 
    886                          
    887                 switch ((*ci).type)  
    888                 { 
    889                         case SortableEntry::ERayMin:  
     888 
     889                switch ((*ci).type) 
     890                { 
     891                        case SortableEntry::ERayMin: 
    890892                                { 
    891893                                        ++ rl; 
    892894                                        ray = (VssRay *) (*ci).data; 
    893895                                        Intersectable *object = ray->mTerminationObject; 
    894                                         if (object && !object->Mailed())  
     896                                        if (object && !object->Mailed()) 
    895897                                        { 
    896898                                                object->Mail(); 
     
    899901                                        break; 
    900902                                } 
    901                         case SortableEntry::ERayMax:  
     903                        case SortableEntry::ERayMax: 
    902904                                { 
    903905                                        -- rr; 
    904                                          
     906 
    905907                                        ray = (VssRay *) (*ci).data; 
    906908                                        Intersectable *object = ray->mTerminationObject; 
    907                                          
     909 
    908910                                        if (object) 
    909911                                        { 
     
    911913                                                -- pr; 
    912914                                        } 
    913                                                  
     915 
    914916                                        break; 
    915917                                } 
    916918                } 
    917                          
    918                 if ((*ci).value > minBand && (*ci).value < maxBand)  
     919 
     920                if ((*ci).value > minBand && (*ci).value < maxBand) 
    919921                { 
    920922                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value); 
    921                  
     923 
    922924                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; 
    923925                        // cout<<"cost= "<<sum<<endl; 
    924                          
    925                         if (sum < minSum)  
     926 
     927                        if (sum < minSum) 
    926928                        { 
    927929                                minSum = sum; 
    928930                                position = (*ci).value; 
    929                          
     931 
    930932                                raysBack = rl; 
    931933                                raysFront = rr; 
    932                          
     934 
    933935                                pvsBack = pl; 
    934936                                pvsFront = pr; 
    935                                  
     937 
    936938                        } 
    937939                } 
     
    941943        float newCost = mCtDivCi + minSum / sizeBox; 
    942944        float ratio = newCost / oldCost; 
    943    
     945 
    944946        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox) 
    945947        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl; 
    946          
     948 
    947949        return ratio; 
    948950} 
     
    952954{ 
    953955        mSplitCandidates->clear(); 
    954    
     956 
    955957        int requestedSize = 2 * (int)(node->mRays.size()); 
    956958        // creates a sorted split candidates array 
    957959        if (mSplitCandidates->capacity() > 500000 && 
    958                 requestedSize < (int)(mSplitCandidates->capacity()/10) )  
     960                requestedSize < (int)(mSplitCandidates->capacity()/10) ) 
    959961        { 
    960962        DEL_PTR(mSplitCandidates); 
    961963                mSplitCandidates = new vector<SortableEntry>; 
    962964        } 
    963    
     965 
    964966        mSplitCandidates->reserve(requestedSize); 
    965967 
    966         // insert all queries  
     968        // insert all queries 
    967969        for(RayInfoContainer::const_iterator ri = node->mRays.begin(); 
    968                 ri < node->mRays.end(); ++ ri)  
     970                ri < node->mRays.end(); ++ ri) 
    969971        { 
    970972                bool positive = (*ri).mRay->HasPosDir(axis); 
    971                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,  
     973                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
    972974                                                                                                  (*ri).ExtrapOrigin(axis), (void *)&*ri)); 
    973                  
     975 
    974976                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
    975977                                                                                                  (*ri).ExtrapTermination(axis), (void *)&*ri)); 
    976978        } 
    977          
     979 
    978980        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end()); 
    979981} 
     
    994996        if (data.mDepth >= mTermMaxDepth) 
    995997                ++ mStat.maxDepthNodes; 
    996    
     998 
    997999        if (leaf->GetPvsSize() < mTermMinPvs) 
    9981000                ++ mStat.minPvsNodes; 
     
    10031005        if (leaf->GetAvgRayContribution() > mTermMaxRayContribution) 
    10041006                ++ mStat.maxRayContribNodes; 
    1005          
    1006         if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)  
     1007 
     1008        if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize) 
    10071009                ++ mStat.minSizeNodes; 
    10081010} 
    10091011 
    10101012 
    1011 inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,  
     1013inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 
    10121014                                                                                          const AxisAlignedBox3 &box) const 
    10131015{ 
    1014         return ((leaf->GetPvsSize() < mTermMinPvs) ||  
     1016        return ((leaf->GetPvsSize() < mTermMinPvs) || 
    10151017                    (leaf->mRays.size() < mTermMinRays) || 
    10161018                        //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) || 
    1017                         (leaf->mDepth >= mTermMaxDepth) ||  
     1019                        (leaf->mDepth >= mTermMaxDepth) || 
    10181020                        (SqrMagnitude(box.Size()) <= mTermMinSize)); 
    10191021} 
     
    10271029        if (TerminationCriteriaMet(leaf, box)) 
    10281030        { 
    1029                 if (1 && leaf->mDepth >= mTermMaxDepth)  
     1031                if (1 && leaf->mDepth >= mTermMaxDepth) 
    10301032                { 
    10311033                        Debug << "Warning: max depth reached depth=" << (int)leaf->mDepth<<" rays=" << (int)leaf->mRays.size() << endl; 
     
    10331035                } 
    10341036                //Debug << "depth: " << (int)leaf->mDepth << " pvs: " << leaf->GetPvsSize() << " rays: " << leaf->mRays.size() << endl; 
    1035                  
     1037 
    10361038                return leaf; 
    10371039        } 
    1038          
     1040 
    10391041        float position; 
    10401042        // first count ray sides 
     
    10431045        int pvsBack; 
    10441046        int pvsFront; 
    1045          
     1047 
    10461048        // select subdivision axis 
    10471049        const int axis = SelectPlane(leaf, box, position, raysBack, raysFront, pvsBack, pvsFront); 
     
    10491051        //Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<       pvsFront << endl; 
    10501052 
    1051         if (axis == -1)  
     1053        if (axis == -1) 
    10521054        { 
    10531055                return leaf; 
    10541056        } 
    1055    
     1057 
    10561058        mStat.nodes += 2; 
    10571059        //++ mStat.splits[axis]; 
     
    10631065        node->mPosition = position; 
    10641066        node->mBox = box; 
    1065            
     1067 
    10661068        backBBox = box; 
    10671069        frontBBox = box; 
     
    10771079        // and setup child links 
    10781080        node->SetupChildLinks(back, front); 
    1079          
    1080         if (axis <= VspKdNode::SPLIT_Z)  
     1081 
     1082        if (axis <= VspKdNode::SPLIT_Z) 
    10811083        { 
    10821084                backBBox.SetMax(axis, position); 
    10831085                frontBBox.SetMin(axis, position); 
    1084                  
     1086 
    10851087                for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    1086                                 ri != leaf->mRays.end(); ++ ri)  
    1087                 { 
    1088                         if ((*ri).mRay->IsActive())  
     1088                                ri != leaf->mRays.end(); ++ ri) 
     1089                { 
     1090                        if ((*ri).mRay->IsActive()) 
    10891091                        { 
    10901092                                // first unref ray from the former leaf 
     
    10941096                                int side = node->ComputeRayIntersection(*ri, t); 
    10951097 
    1096                                 if (side == 0)  
     1098                                if (side == 0) 
    10971099                                { 
    1098                                         if ((*ri).mRay->HasPosDir(axis))  
     1100                                        if ((*ri).mRay->HasPosDir(axis)) 
    10991101                                        { 
    11001102                                                back->AddRay(RayInfo((*ri).mRay, 
     
    11041106                                                                                          t, 
    11051107                                                                                          (*ri).mMaxT)); 
    1106                                         }  
    1107                                         else  
     1108                                        } 
     1109                                        else 
    11081110                                        { 
    11091111                                                back->AddRay(RayInfo((*ri).mRay, 
     
    11141116                                                                                          t)); 
    11151117                                        } 
    1116                                 }  
     1118                                } 
    11171119                                else 
    1118                                         if (side == 1)  
     1120                                        if (side == 1) 
    11191121                                                front->AddRay(*ri); 
    11201122                                        else 
     
    11231125                                (*ri).mRay->Unref(); 
    11241126                } 
    1125         }  
    1126         else  
     1127        } 
     1128        else 
    11271129        { 
    11281130                // rays front/back 
    1129      
     1131 
    11301132        for (RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    1131                         ri != leaf->mRays.end(); ++ ri)  
    1132                 { 
    1133                         if ((*ri).mRay->IsActive())  
     1133                        ri != leaf->mRays.end(); ++ ri) 
     1134                { 
     1135                        if ((*ri).mRay->IsActive()) 
    11341136                        { 
    11351137                                // first unref ray from the former leaf 
     
    11411143                                else 
    11421144                                        side = -1; 
    1143                                  
     1145 
    11441146                                if (side == 1) 
    11451147                                        front->AddRay(*ri); 
    11461148                                else 
    1147                                         back->AddRay(*ri);               
    1148                         }  
     1149                                        back->AddRay(*ri); 
     1150                        } 
    11491151                        else 
    11501152                                (*ri).mRay->Unref(); 
    11511153                } 
    11521154        } 
    1153          
     1155 
    11541156        // update stats 
    11551157        mStat.rayRefs -= (int)leaf->mRays.size(); 
     
    11751177                VspKdNode *node = tstack.top(); 
    11761178                tstack.pop(); 
    1177      
    1178                 if (!node->IsLeaf())  
     1179 
     1180                if (!node->IsLeaf()) 
    11791181                { 
    11801182                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
    11811183                        // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl; 
    1182                         if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)  
     1184                        if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) 
    11831185                        { 
    11841186                                released = CollapseSubtree(node, time); 
    11851187                                break; 
    11861188                        } 
    1187                         if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())  
     1189                        if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime()) 
    11881190                        { 
    11891191                                tstack.push(in->GetFront()); 
    11901192                                tstack.push(in->GetBack()); 
    1191                         }  
    1192                         else  
     1193                        } 
     1194                        else 
    11931195                        { 
    11941196                                tstack.push(in->GetBack()); 
     
    11981200        } 
    11991201 
    1200         while (tstack.empty())  
     1202        while (tstack.empty()) 
    12011203        { 
    12021204                // could find node to collaps... 
     
    12041206                break; 
    12051207        } 
    1206    
     1208 
    12071209        return released; 
    12081210} 
     
    12181220        static int pass = 0; 
    12191221        ++ pass; 
    1220          
     1222 
    12211223        // check if we should perform a dynamic subdivision of the leaf 
    12221224        if (// leaf->mRays.size() > (unsigned)termMinCost && 
    1223                 (leaf->GetPvsSize() >= mTermMinPvs) &&  
     1225                (leaf->GetPvsSize() >= mTermMinPvs) && 
    12241226                (SqrMagnitude(leafBBox.Size()) > sizeThreshold) ) 
    12251227        { 
    12261228        // memory check and release 
    1227                 if (GetMemUsage() > mMaxTotalMemory)  
     1229                if (GetMemUsage() > mMaxTotalMemory) 
    12281230                        ReleaseMemory(pass); 
    1229                  
     1231 
    12301232                AxisAlignedBox3 backBBox, frontBBox; 
    12311233 
     
    12451247        // schedule rays for removal 
    12461248        for(VssRayContainer::const_iterator ri = remove.begin(); 
    1247                 ri != remove.end(); ++ ri)  
    1248         { 
    1249                 (*ri)->ScheduleForRemoval();   
     1249                ri != remove.end(); ++ ri) 
     1250        { 
     1251                (*ri)->ScheduleForRemoval(); 
    12501252        } 
    12511253 
    12521254        int inactive = 0; 
    12531255 
    1254         for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)  
     1256        for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri) 
    12551257        { 
    12561258                if ((*ri)->ScheduledForRemoval()) 
     
    12631265 
    12641266        //  cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl; 
    1265         for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)  
     1267        for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri) 
    12661268        { 
    12671269                AddRay(*ri); 
     
    12771279 
    12781280        tstack.push(RayTraversalData(mRoot, RayInfo(ray))); 
    1279    
     1281 
    12801282        RayTraversalData data; 
    12811283 
    12821284        // cout<<"Number of ray refs = "<<ray->RefCount()<<endl; 
    1283         while (!tstack.empty())  
     1285        while (!tstack.empty()) 
    12841286        { 
    12851287                data = tstack.top(); 
    12861288                tstack.pop(); 
    12871289 
    1288                 if (!data.mNode->IsLeaf())  
     1290                if (!data.mNode->IsLeaf()) 
    12891291                { 
    12901292                        // split the set of rays in two groups intersecting the 
    12911293                        // two subtrees 
    12921294                        TraverseInternalNode(data, tstack); 
    1293         }  
    1294                 else  
     1295        } 
     1296                else 
    12951297                { 
    12961298                        // remove the ray from the leaf 
    12971299                        // find the ray in the leaf and swap it with the last ray... 
    12981300                        VspKdLeaf *leaf = (VspKdLeaf *)data.mNode; 
    1299        
    1300                         if (!leaf->Mailed())  
     1301 
     1302                        if (!leaf->Mailed()) 
    13011303                        { 
    13021304                                leaf->Mail(); 
    1303                                  
     1305 
    13041306                                if (affectedLeaves) 
    13051307                                        affectedLeaves->push_back(leaf); 
    1306          
    1307                                 if (removeAllScheduledRays)  
     1308 
     1309                                if (removeAllScheduledRays) 
    13081310                                { 
    13091311                                        int tail = (int)leaf->mRays.size() - 1; 
    13101312 
    1311                                         for (int i=0; i < (int)(leaf->mRays.size()); ++ i)  
     1313                                        for (int i=0; i < (int)(leaf->mRays.size()); ++ i) 
    13121314                                        { 
    1313                                                 if (leaf->mRays[i].mRay->ScheduledForRemoval())  
     1315                                                if (leaf->mRays[i].mRay->ScheduledForRemoval()) 
    13141316                                                { 
    13151317                                                        // find a ray to replace it with 
    1316                                                         while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())  
     1318                                                        while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval()) 
    13171319                                                        { 
    13181320                                                                ++ mStat.removedRayRefs; 
    13191321                                                                leaf->mRays[tail].mRay->Unref(); 
    13201322                                                                leaf->mRays.pop_back(); 
    1321                                                                  
     1323 
    13221324                                                                -- tail; 
    13231325                                                        } 
    1324                                                          
     1326 
    13251327                                                        if (tail < i) 
    13261328                                                                break; 
    1327                
     1329 
    13281330                                                        ++ mStat.removedRayRefs; 
    1329                
     1331 
    13301332                                                        leaf->mRays[i].mRay->Unref(); 
    13311333                                                        leaf->mRays[i] = leaf->mRays[tail]; 
     
    13361338                                } 
    13371339                        } 
    1338        
     1340 
    13391341                        if (!removeAllScheduledRays) 
    1340                                 for (int i=0; i < (int)leaf->mRays.size(); i++)  
     1342                                for (int i=0; i < (int)leaf->mRays.size(); i++) 
    13411343                                { 
    1342                                         if (leaf->mRays[i].mRay == ray)  
     1344                                        if (leaf->mRays[i].mRay == ray) 
    13431345                                        { 
    13441346                                                ++ mStat.removedRayRefs; 
     
    13531355        } 
    13541356 
    1355         if (ray->RefCount() != 0)  
     1357        if (ray->RefCount() != 0) 
    13561358        { 
    13571359                cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl; 
     
    13641366{ 
    13651367        stack<RayTraversalData> tstack; 
    1366    
     1368 
    13671369        tstack.push(RayTraversalData(mRoot, RayInfo(ray))); 
    1368    
     1370 
    13691371        RayTraversalData data; 
    1370    
    1371         while (!tstack.empty())  
     1372 
     1373        while (!tstack.empty()) 
    13721374        { 
    13731375                data = tstack.top(); 
    13741376                tstack.pop(); 
    13751377 
    1376                 if (!data.mNode->IsLeaf())  
     1378                if (!data.mNode->IsLeaf()) 
    13771379                { 
    13781380                        TraverseInternalNode(data, tstack); 
    1379                 }  
    1380                 else  
     1381                } 
     1382                else 
    13811383                { 
    13821384                        // remove the ray from the leaf 
     
    13901392} 
    13911393 
    1392 void VspKdTree::TraverseInternalNode(RayTraversalData &data,  
     1394void VspKdTree::TraverseInternalNode(RayTraversalData &data, 
    13931395                                                                         stack<RayTraversalData> &tstack) 
    13941396{ 
    13951397        VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode); 
    1396    
    1397         if (in->mAxis <= VspKdNode::SPLIT_Z)  
     1398 
     1399        if (in->mAxis <= VspKdNode::SPLIT_Z) 
    13981400        { 
    13991401            // determine the side of this ray with respect to the plane 
    1400  float t;  
     1402 float t; 
    14011403 int side = in->ComputeRayIntersection(data.mRayData, t); 
    1402      
    1403                 if (side == 0)  
    1404                 { 
    1405                         if (data.mRayData.mRay->HasPosDir(in->mAxis))  
    1406                         { 
    1407                                 tstack.push(RayTraversalData(in->GetBack(),  
     1404 
     1405                if (side == 0) 
     1406                { 
     1407                        if (data.mRayData.mRay->HasPosDir(in->mAxis)) 
     1408                        { 
     1409                                tstack.push(RayTraversalData(in->GetBack(), 
    14081410                                                        RayInfo(data.mRayData.mRay, data.mRayData.mMinT, t))); 
    1409                                  
     1411 
    14101412                                tstack.push(RayTraversalData(in->GetFront(), 
    14111413                                                        RayInfo(data.mRayData.mRay, t, data.mRayData.mMaxT))); 
    1412          
    1413                         }  
    1414                         else  
     1414 
     1415                        } 
     1416                        else 
    14151417                        { 
    14161418                                tstack.push(RayTraversalData(in->GetBack(), 
     
    14291431                        else 
    14301432                                tstack.push(RayTraversalData(in->GetBack(), data.mRayData)); 
    1431         }  
    1432         else  
     1433        } 
     1434        else 
    14331435        { 
    14341436                // directional split 
     
    14461448        // use mail 1 for this purpose 
    14471449        stack<VspKdNode *> tstack; 
    1448          
     1450 
    14491451        int rayCount = 0; 
    14501452        int totalRayCount = 0; 
     
    14621464        tstack.push(sroot); 
    14631465        VssRay::NewMail(); 
    1464          
    1465         while (!tstack.empty())  
     1466 
     1467        while (!tstack.empty()) 
    14661468        { 
    14671469                ++ collapsedNodes; 
    1468                  
     1470 
    14691471                VspKdNode *node = tstack.top(); 
    14701472                tstack.pop(); 
    1471                 if (node->IsLeaf())  
     1473                if (node->IsLeaf()) 
    14721474                { 
    14731475                        VspKdLeaf *leaf = (VspKdLeaf *) node; 
    1474                          
     1476 
    14751477                        for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    1476                                         ri != leaf->mRays.end(); ++ ri)  
     1478                                        ri != leaf->mRays.end(); ++ ri) 
    14771479                        { 
    14781480                                ++ totalRayCount; 
    1479                                  
    1480                                 if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed())  
     1481 
     1482                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) 
    14811483                                { 
    14821484                                        (*ri).mRay->Mail(); 
     
    14841486                                } 
    14851487                        } 
    1486                 }  
    1487                 else  
     1488                } 
     1489                else 
    14881490                { 
    14891491                        tstack.push(((VspKdInterior *)node)->GetFront()); 
     
    14911493                } 
    14921494        } 
    1493    
     1495 
    14941496        VssRay::NewMail(); 
    14951497 
    14961498        // create a new node that will hold the rays 
    14971499        VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount); 
    1498          
     1500 
    14991501        if (newLeaf->mParent) 
    15001502                newLeaf->mParent->ReplaceChildLink(sroot, newLeaf); 
     
    15021504        tstack.push(sroot); 
    15031505 
    1504         while (!tstack.empty())  
     1506        while (!tstack.empty()) 
    15051507        { 
    15061508                VspKdNode *node = tstack.top(); 
    15071509                tstack.pop(); 
    15081510 
    1509                 if (node->IsLeaf())  
     1511                if (node->IsLeaf()) 
    15101512                { 
    15111513                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    15121514 
    15131515                        for(RayInfoContainer::iterator ri = leaf->mRays.begin(); 
    1514                                         ri != leaf->mRays.end(); ++ ri)  
    1515                         { 
    1516                                 // unref this ray from the old node              
    1517                                 if ((*ri).mRay->IsActive())  
     1516                                        ri != leaf->mRays.end(); ++ ri) 
     1517                        { 
     1518                                // unref this ray from the old node 
     1519                                if ((*ri).mRay->IsActive()) 
    15181520                                { 
    15191521                                        (*ri).mRay->Unref(); 
    1520                                         if (!(*ri).mRay->Mailed())  
     1522                                        if (!(*ri).mRay->Mailed()) 
    15211523                                        { 
    15221524                                                (*ri).mRay->Mail(); 
    15231525                                                newLeaf->AddRay(*ri); 
    15241526                                        } 
    1525                                 }  
     1527                                } 
    15261528                                else 
    15271529                                        (*ri).mRay->Unref(); 
    15281530                        } 
    1529                 }  
    1530                 else  
    1531                 { 
    1532                         VspKdInterior *interior =  
     1531                } 
     1532                else 
     1533                { 
     1534                        VspKdInterior *interior = 
    15331535                                dynamic_cast<VspKdInterior *>(node); 
    15341536                        tstack.push(interior->GetBack()); 
     
    15361538                } 
    15371539        } 
    1538    
     1540 
    15391541        // delete the node and all its children 
    15401542        DEL_PTR(sroot); 
    1541    
     1543 
    15421544        // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin(); 
    15431545    //      ri != newleaf->mRays.end(); ++ ri) 
     
    15501552        mStat.nodes -= collapsedNodes - 1; 
    15511553        mStat.rayRefs -= totalRayCount - rayCount; 
    1552    
     1554 
    15531555#if DEBUG_COLLAPSE 
    15541556        cout << "collapsed nodes" << collapsedNodes << endl; 
     
    15711573        Intersectable::NewMail(); 
    15721574        int pvsSize = 0; 
    1573          
    1574         while (!tstack.empty())  
     1575 
     1576        while (!tstack.empty()) 
    15751577        { 
    15761578                VspKdNode *node = tstack.top(); 
    15771579                tstack.pop(); 
    1578      
    1579           if (node->IsLeaf())  
     1580 
     1581          if (node->IsLeaf()) 
    15801582                { 
    15811583                        VspKdLeaf *leaf = (VspKdLeaf *)node; 
     
    15831585                                 ri != leaf->mRays.end(); ++ ri) 
    15841586                        { 
    1585                                 if ((*ri).mRay->IsActive())  
     1587                                if ((*ri).mRay->IsActive()) 
    15861588                                { 
    15871589                                        Intersectable *object; 
    15881590#if BIDIRECTIONAL_RAY 
    15891591                                        object = (*ri).mRay->mOriginObject; 
    1590                                          
    1591                                         if (object && !object->Mailed())  
     1592 
     1593                                        if (object && !object->Mailed()) 
    15921594                                        { 
    15931595                                                ++ pvsSize; 
     
    15961598#endif 
    15971599                                        object = (*ri).mRay->mTerminationObject; 
    1598                                         if (object && !object->Mailed())  
     1600                                        if (object && !object->Mailed()) 
    15991601                                        { 
    16001602                                                ++ pvsSize; 
     
    16021604                                        } 
    16031605                                } 
    1604                         }  
    1605                 } 
    1606                 else  
     1606                        } 
     1607                } 
     1608                else 
    16071609                { 
    16081610                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
    1609          
    1610                         if (in->mAxis < 3)  
     1611 
     1612                        if (in->mAxis < 3) 
    16111613                        { 
    16121614                                if (box.Max(in->mAxis) >= in->mPosition) 
    16131615                                        tstack.push(in->GetFront()); 
    1614                                  
     1616 
    16151617                                if (box.Min(in->mAxis) <= in->mPosition) 
    16161618                                        tstack.push(in->GetBack()); 
    1617                         }  
    1618                         else  
     1619                        } 
     1620                        else 
    16191621                        { 
    16201622                                // both nodes for directional splits 
     
    16341636        stack<VspKdNode *> tstack; 
    16351637        tstack.push(mRoot); 
    1636          
     1638 
    16371639        minRayContribution = 1.0f; 
    16381640        maxRayContribution = 0.0f; 
     
    16411643        int leaves = 0; 
    16421644 
    1643         while (!tstack.empty())  
     1645        while (!tstack.empty()) 
    16441646        { 
    16451647                VspKdNode *node = tstack.top(); 
    16461648                tstack.pop(); 
    1647                 if (node->IsLeaf())  
     1649                if (node->IsLeaf()) 
    16481650                { 
    16491651                        leaves++; 
     
    16561658                                minRayContribution = c; 
    16571659                        sumRayContribution += c; 
    1658                          
    1659                 }  
     1660 
     1661                } 
    16601662                else { 
    16611663                        VspKdInterior *in = (VspKdInterior *)node; 
     
    16651667                } 
    16661668        } 
    1667          
     1669 
    16681670        Debug << "sum=" << sumRayContribution << endl; 
    16691671        Debug << "leaves=" << leaves << endl; 
     
    16771679        stack<VspKdNode *> tstack; 
    16781680        tstack.push(mRoot); 
    1679          
    1680         while (!tstack.empty())  
     1681 
     1682        while (!tstack.empty()) 
    16811683        { 
    16821684                VspKdNode *node = tstack.top(); 
    16831685                tstack.pop(); 
    1684                  
    1685                 if (node->IsLeaf())  
     1686 
     1687                if (node->IsLeaf()) 
    16861688                { 
    16871689                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
     
    16911693                        //                      cout<<num<<" "; 
    16921694 
    1693                         for (int i=0; i < num; i++)  
     1695                        for (int i=0; i < num; i++) 
    16941696                        { 
    16951697                                Vector3 origin = GetBBox(leaf).GetRandomPoint(); 
     
    16991701                                rays.push_back(SimpleRay(origin, direction));*/ 
    17001702                        } 
    1701                          
    1702                 }  
    1703                 else  
    1704                 { 
    1705                         VspKdInterior *in =  
     1703 
     1704                } 
     1705                else 
     1706                { 
     1707                        VspKdInterior *in = 
    17061708                                dynamic_cast<VspKdInterior *>(node); 
    17071709                        // both nodes for directional splits 
     
    17221724        int sumPvs = 0; 
    17231725        int leaves = 0; 
    1724          
    1725         while (!tstack.empty())  
     1726 
     1727        while (!tstack.empty()) 
    17261728        { 
    17271729                VspKdNode *node = tstack.top(); 
    17281730                tstack.pop(); 
    1729                  
    1730                 if (node->IsLeaf())  
     1731 
     1732                if (node->IsLeaf()) 
    17311733                { 
    17321734                        VspKdLeaf *leaf = (VspKdLeaf *)node; 
     
    17351737                        sumPvs += leaf->GetPvsSize(); 
    17361738                        leaves++; 
    1737                 }  
    1738                 else  
     1739                } 
     1740                else 
    17391741                { 
    17401742                        VspKdInterior *in = (VspKdInterior *)node; 
     
    17631765        if (node->mParent->mAxis >= 3) 
    17641766                return node->mParent->mBox; 
    1765      
     1767 
    17661768        AxisAlignedBox3 box(node->mParent->mBox); 
    17671769        if (node->mParent->GetFront() == node) 
     
    17731775} 
    17741776 
    1775 int     VspKdTree::GetRootPvsSize() const  
     1777int     VspKdTree::GetRootPvsSize() const 
    17761778{ 
    17771779        return GetPvsSize(mRoot, mBox); 
    17781780} 
    17791781 
    1780 const VspKdStatistics &VspKdTree::GetStatistics() const  
     1782const VspKdStatistics &VspKdTree::GetStatistics() const 
    17811783{ 
    17821784        return mStat; 
     
    17881790        UpdateRays(remove, add); 
    17891791} 
    1790   
     1792 
    17911793// return memory usage in MB 
    1792 float VspKdTree::GetMemUsage() const  
    1793 { 
    1794         return  
    1795                 (sizeof(VspKdTree) +  
     1794float VspKdTree::GetMemUsage() const 
     1795{ 
     1796        return 
     1797                (sizeof(VspKdTree) + 
    17961798                 mStat.Leaves() * sizeof(VspKdLeaf) + 
    17971799                 mStat.Interior() * sizeof(VspKdInterior) + 
    17981800                 mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f); 
    17991801} 
    1800          
    1801 float VspKdTree::GetRayMemUsage() const  
     1802 
     1803float VspKdTree::GetRayMemUsage() const 
    18021804{ 
    18031805        return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f); 
    18041806} 
    18051807 
    1806 int VspKdTree::ComputePvsSize(VspKdNode *node,  
     1808int VspKdTree::ComputePvsSize(VspKdNode *node, 
    18071809                                                          const RayInfoContainer &globalRays) const 
    18081810{ 
     
    18161818        for (it = globalRays.begin(); it != globalRays.end(); ++ it) 
    18171819                pvsSize += box.GetMinMaxT(*(*it).mRay, NULL, NULL); 
    1818          
     1820 
    18191821        return pvsSize; 
    18201822} 
     
    18251827        nodeStack.push(mRoot); 
    18261828 
    1827         while (!nodeStack.empty())  
     1829        while (!nodeStack.empty()) 
    18281830        { 
    18291831                VspKdNode *node = nodeStack.top(); 
    1830                  
     1832 
    18311833                nodeStack.pop(); 
    1832                  
    1833                 if (node->IsLeaf())  
     1834 
     1835                if (node->IsLeaf()) 
    18341836                { 
    18351837                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    18361838                        leaves.push_back(leaf); 
    1837                 }  
    1838                 else  
     1839                } 
     1840                else 
    18391841                { 
    18401842                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     
    18511853{ 
    18521854        stack<VspKdNode *> nodeStack; 
    1853    
     1855 
    18541856        nodeStack.push(mRoot); 
    18551857 
    18561858        AxisAlignedBox3 box = GetBBox(n); 
    18571859 
    1858         while (!nodeStack.empty())  
     1860        while (!nodeStack.empty()) 
    18591861        { 
    18601862                VspKdNode *node = nodeStack.top(); 
    18611863                nodeStack.pop(); 
    18621864 
    1863                 if (node->IsLeaf())  
     1865                if (node->IsLeaf()) 
    18641866                { 
    18651867                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
    18661868 
    1867                         if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))  
     1869                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
    18681870                                neighbors.push_back(leaf); 
    1869                 }  
    1870                 else  
     1871                } 
     1872                else 
    18711873                { 
    18721874                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     
    18781880                                if (interior->mPosition < box.Min(interior->mAxis)) 
    18791881                                        nodeStack.push(interior->mFront); 
    1880                                 else  
     1882                                else 
    18811883                                { 
    18821884                                        // random decision 
     
    19021904{ 
    19031905        int hits = 0; 
    1904    
     1906 
    19051907        stack<RayTraversalData> tStack; 
    1906    
     1908 
    19071909        float maxt = 1e6; 
    19081910        float mint = 0; 
     
    19151917        if (mint < 0) 
    19161918                mint = 0; 
    1917    
     1919 
    19181920        maxt += Limits::Threshold; 
    1919    
     1921 
    19201922        Vector3 entp = ray.Extrap(mint); 
    19211923        Vector3 extp = ray.Extrap(maxt); 
    1922    
     1924 
    19231925        VspKdNode *node = mRoot; 
    19241926        VspKdNode *farChild; 
     
    19261928        float position; 
    19271929        int axis; 
    1928    
    1929         while (1)  
    1930         { 
    1931                 if (!node->IsLeaf())  
     1930 
     1931        while (1) 
     1932        { 
     1933                if (!node->IsLeaf()) 
    19321934                { 
    19331935                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 
     
    19351937                        axis = in->mAxis; 
    19361938 
    1937                         if (entp[axis] <= position)  
    1938                         { 
    1939                                 if (extp[axis] <= position)  
     1939                        if (entp[axis] <= position) 
     1940                        { 
     1941                                if (extp[axis] <= position) 
    19401942                                { 
    19411943                                        node = in->mBack; 
    19421944                                        // cases N1,N2,N3,P5,Z2,Z3 
    19431945                                        continue; 
    1944                                 } else  
     1946                                } else 
    19451947                                { 
    19461948                                        // case N4 
     
    19491951                                } 
    19501952                        } 
    1951                         else  
    1952                         { 
    1953                                 if (position <= extp[axis])  
     1953                        else 
     1954                        { 
     1955                                if (position <= extp[axis]) 
    19541956                                { 
    19551957                                        node = in->mFront; 
    19561958                                        // cases P1,P2,P3,N5,Z1 
    19571959                                        continue; 
    1958                                 }  
    1959                                 else  
     1960                                } 
     1961                                else 
    19601962                                { 
    19611963                                        node = in->mFront; 
     
    19711973                        extp = ray.GetLoc() + ray.GetDir()*tdist; 
    19721974                        maxt = tdist; 
    1973                 }  
    1974                 else  
     1975                } 
     1976                else 
    19751977                { 
    19761978                        // compute intersection with all objects in this leaf 
     
    19781980                        if (ray.mFlags & Ray::STORE_KDLEAVES) 
    19791981                                ray.kdLeaves.push_back(leaf); 
    1980                          
     1982 
    19811983                        ObjectContainer::const_iterator mi; 
    1982                         for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++)  
     1984                        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++) 
    19831985                        { 
    19841986                                Intersectable *object = *mi; 
    1985                                 if (!object->Mailed() )  
     1987                                if (!object->Mailed() ) 
    19861988                                { 
    19871989                                        object->Mail(); 
     
    19911993                                } 
    19921994                        } 
    1993                          
     1995 
    19941996                        if (hits && ray.GetType() == Ray::LOCAL_RAY) 
    19951997                                if (ray.intersections[0].mT <= maxt) 
    19961998                                        break; 
    1997                          
     1999 
    19982000                        // get the next node from the stack 
    19992001                        if (tStack.empty()) 
    20002002                                break; 
    2001                          
     2003 
    20022004                        entp = extp; 
    20032005                        mint = maxt; 
    20042006                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 
    20052007                                break; 
    2006                          
     2008 
    20072009                        RayTraversalData &s  = tStack.top(); 
    20082010                        node = s.mNode; 
     
    20132015                } 
    20142016        } 
    2015          
     2017 
    20162018        return hits; 
    20172019} 
     
    20342036                if (ray->mTerminationObject) 
    20352037                        vc->GetPvs().AddSample(ray->mTerminationObject); 
    2036                  
     2038 
    20372039                if (ray->mOriginObject) 
    20382040                        vc->GetPvs().AddSample(ray->mOriginObject); 
     
    20502052        ViewCell::NewMail(); 
    20512053 
    2052         // exclude root cell 
    2053         //mRootCell->Mail(); 
    2054  
    2055         while (!nodeStack.empty())  
     2054        while (!nodeStack.empty()) 
    20562055        { 
    20572056                VspKdNode *node = nodeStack.top(); 
    20582057                nodeStack.pop(); 
    20592058 
    2060                 if (node->IsLeaf())  
     2059                if (node->IsLeaf()) 
    20612060                { 
    20622061                        ++ vcStat.leaves; 
     
    20642063                        VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 
    20652064 
    2066                         if (!viewCell->Mailed())  
     2065                        if (!viewCell->Mailed()) 
    20672066                        { 
    20682067                                viewCell->Mail(); 
    2069                                  
     2068 
    20702069                                ++ vcStat.viewCells; 
    20712070                                const int pvsSize = viewCell->GetPvs().GetSize(); 
     
    20832082 
    20842083                                if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves) 
    2085                                         vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();           
    2086                         } 
    2087                 } 
    2088                 else  
     2084                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size(); 
     2085                        } 
     2086                } 
     2087                else 
    20892088                { 
    20902089                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     
    20952094        } 
    20962095} 
     2096 
    20972097 
    20982098 
     
    21302130        } 
    21312131 
     2132        vc->Mail(); 
     2133 
    21322134        // clean up old view cells 
    21332135        DEL_PTR(fVc); 
     
    21432145        vector<VspKdLeaf *> leaves; 
    21442146        priority_queue<MergeCandidate> mergeQueue; 
    2145          
     2147 
    21462148        // collect the leaves, e.g., the "voxels" that will build the view cells 
    21472149        CollectLeaves(leaves); 
     
    21612163        { 
    21622164                VspKdLeaf *leaf = *it; 
    2163                  
     2165 
    21642166                // no leaf is part of two merge candidates 
    21652167                if (!leaf->Mailed()) 
     
    21702172                        FindNeighbors(leaf, neighbors, true); 
    21712173 
    2172                         vector<VspKdLeaf *>::const_iterator nit,  
     2174                        vector<VspKdLeaf *>::const_iterator nit, 
    21732175                                nit_end = neighbors.end(); 
    21742176 
     
    21802182        int merged = 0; 
    21812183 
    2182         float savedMaxCostRatio = 0; 
    2183  
    2184         Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl; 
     2184        //Debug << mMinViewCells << " " << mMaxCostRatio << endl; 
    21852185 
    21862186        // use priority queue to merge leaves 
    2187         while (!mergeQueue.empty() &&  
    2188                    ((mMaxViewCells < vcSize) || 
    2189                     (mergeQueue.top().GetMergeCost() < mMaxCostRatio))) 
    2190         { 
    2191                 ViewCell::NewMail(); 
    2192  
    2193                 Debug << "=====================" << endl; 
     2187        while (!mergeQueue.empty() && 
     2188                   (vcSize > mMinViewCells))// && 
     2189                   //(mergeQueue.top().GetMergeCost() < mMaxCostRatio)) 
     2190        { 
     2191                //Debug << mergeQueue.top().GetMergeCost() << " " << mMaxCostRatio << endl; 
    21942192                MergeCandidate mc = mergeQueue.top(); 
    21952193                mergeQueue.pop(); 
    2196                  
     2194 
     2195                // both view cells equal! 
    21972196                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 
    2198                 // both view cells the same! 
    2199                 { 
    2200                         Debug << "same view cell!!" << endl; 
    2201                         -- vcSize; 
    2202  
    22032197                        continue; 
    2204                 } 
    22052198 
    22062199                if (mc.Valid()) 
    22072200                { 
    2208                         mc.GetLeaf1()->GetViewCell()->Mail(); 
    2209                         mc.GetLeaf2()->GetViewCell()->Mail(); 
    2210                          
    2211                         Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl; 
    2212                         savedMaxCostRatio = mc.GetMergeCost(); 
    2213  
     2201                        ViewCell::NewMail(); 
    22142202                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 
    2215                          
     2203 
    22162204                        ++ merged; 
    22172205                        -- vcSize; 
     
    22192207                // merge candidate not valid, because one of the leaves was already 
    22202208                // merged with another one 
    2221                 else  
    2222                 { 
    2223                         Debug << "not valid " << mc.GetMergeCost() << endl; 
    2224                          
     2209                else 
     2210                { 
    22252211                        // validate and reinsert into queue 
    22262212                        mc.SetValid(); 
    2227                         Debug << "ag. valid " << mc.GetMergeCost() << endl; 
    2228  
    22292213                        mergeQueue.push(mc); 
    2230                 } 
    2231         } 
    2232  
    2233         if (mergeQueue.empty()) 
    2234                 Debug << "empty queue" << endl; 
    2235          
    2236         Debug << "max cost ratio: " << savedMaxCostRatio << endl; 
     2214                        //Debug << "validate " << mc.GetMergeCost() << endl; 
     2215                } 
     2216        } 
     2217 
     2218        // collapse tree according to view cell partition 
     2219        CollapseTree(mRoot); 
     2220 
     2221        // revalidate leaves 
     2222        ValidateViewCellLeaves(); 
     2223 
    22372224 
    22382225        return merged; 
     2226} 
     2227 
     2228 
     2229void VspKdTree::ValidateViewCellLeaves() 
     2230{ 
     2231        // list not valid anymore => clear 
     2232        stack<VspKdNode *> nodeStack; 
     2233        nodeStack.push(mRoot); 
     2234 
     2235        ViewCell::NewMail(); 
     2236 
     2237        while (!nodeStack.empty()) 
     2238        { 
     2239                VspKdNode *node = nodeStack.top(); 
     2240                nodeStack.pop(); 
     2241 
     2242                if (node->IsLeaf()) 
     2243                { 
     2244                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 
     2245 
     2246                        VspKdViewCell *viewCell = leaf->GetViewCell(); 
     2247 
     2248                        if (!viewCell->Mailed()) 
     2249                        { 
     2250                                Debug << "jhere2" << endl; 
     2251                                viewCell->mVspKdLeaves.clear(); 
     2252                                viewCell->Mail(); 
     2253                        } 
     2254 
     2255                        viewCell->mVspKdLeaves.push_back(leaf); 
     2256                } 
     2257                else 
     2258                { 
     2259                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     2260 
     2261                        nodeStack.push(interior->GetFront()); 
     2262                        nodeStack.push(interior->GetBack()); 
     2263                } 
     2264        } 
     2265} 
     2266 
     2267VspKdNode *VspKdTree::CollapseTree(VspKdNode *node) 
     2268{ 
     2269    if (node->IsLeaf()) 
     2270                return node; 
     2271 
     2272        Debug << "here554444" << endl; 
     2273        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 
     2274 
     2275        VspKdNode *front = CollapseTree(interior->GetFront()); 
     2276        VspKdNode *back = CollapseTree(interior->GetBack()); 
     2277 
     2278        if (front->IsLeaf() && back->IsLeaf()) 
     2279        { 
     2280                VspKdLeaf *frontLeaf = dynamic_cast<VspKdLeaf *>(front); 
     2281                VspKdLeaf *backLeaf = dynamic_cast<VspKdLeaf *>(back); 
     2282 
     2283                //-- collapse tree 
     2284                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell()) 
     2285                { 
     2286                        VspKdViewCell *vc = frontLeaf->GetViewCell(); 
     2287 
     2288                        VspKdLeaf *leaf = new VspKdLeaf(interior->GetParent(), 0); 
     2289                        leaf->SetViewCell(vc); 
     2290 
     2291                        // replace a link from node's parent 
     2292                        if (leaf->mParent) 
     2293                                leaf->mParent->ReplaceChildLink(node, leaf); 
     2294 
     2295                        delete interior; 
     2296 
     2297                        return leaf; 
     2298                } 
     2299        } 
     2300 
     2301        return node; 
    22392302} 
    22402303 
     
    22582321void MergeCandidate::EvalMergeCost() 
    22592322{ 
    2260         // compute pvs differences 
     2323        //-- compute pvs difference 
    22612324        VspKdViewCell *vc1 = mLeaf1->GetViewCell(); 
    22622325        VspKdViewCell *vc2 = mLeaf2->GetViewCell(); 
    2263          
    2264         //VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell()); 
    2265         //VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell()); 
    22662326 
    22672327        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 
    22682328        const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 
    22692329 
    2270         //-- compute ratio of old cost  
     2330        //-- compute ratio of old cost 
    22712331        //-- (added size of left and right view cell times pvs size) 
    22722332        //-- to new rendering cost (size of merged view cell times pvs size) 
    2273         const float oldCost =  
    2274                 (float)vc1->GetPvs().GetSize() * vc1->GetSize() +  
     2333        const float oldCost = 
     2334                (float)vc1->GetPvs().GetSize() * vc1->GetSize() + 
    22752335                (float)vc2->GetPvs().GetSize() * vc2->GetSize(); 
    22762336 
    2277         const float newCost =  
     2337        const float newCost = 
    22782338                (float)vcPvs * (vc1->GetSize() + vc2->GetSize()); 
    22792339 
    2280         mMergeCost = newCost / oldCost; 
    2281  
    2282         Debug << "******************************" << endl; 
    2283         Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl; 
    2284         if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 
    2285                 mMergeCost += 1.0; 
    2286  
    2287         Debug << "old cost: " << oldCost << endl; 
    2288         Debug << "new cost: " << newCost << endl; 
     2340        mMergeCost = newCost - oldCost; 
     2341 
     2342//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 
     2343//              mMergeCost += 1.0; 
    22892344} 
    22902345 
     
    23102365 
    23112366bool MergeCandidate::Valid() const 
    2312 {        
    2313         //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl; 
    2314         //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl; 
    2315  
    2316         return  
    2317                 (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&  
     2367{ 
     2368        return 
     2369                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
    23182370                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id); 
    23192371} 
     
    23282380        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; 
    23292381        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox; 
    2330          
     2382 
    23312383        EvalMergeCost(); 
    23322384} 
  • trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

    r463 r465  
    299299{ 
    300300public: 
     301 
    301302        friend class VspKdTree; 
    302303 
     
    670671        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2); 
    671672 
    672          
     673        /** Collapses the tree with respect to the view cell partition. 
     674                @returns node of type leaf if the node could be collapsed, this node otherwise 
     675        */ 
     676        VspKdNode *CollapseTree(VspKdNode *node); 
     677         
     678        /** Helper function revalidating the view cell leaf list after merge. 
     679        */ 
     680        void ValidateViewCellLeaves(); 
     681 
    673682protected: 
    674683         
     
    749758        int mMaxViewCells; 
    750759 
     760        /// minimal number of view cells 
     761        int mMinViewCells; 
     762 
    751763        ///////////////////////////// 
    752764        VspKdStatistics mStat;   
  • trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

    r462 r465  
    462462  cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl; 
    463463   
    464   ExportVssTree("vss-tree-100.x3d", vssTree, Vector3(1,0,0)); 
    465   ExportVssTree("vss-tree-001.x3d", vssTree, Vector3(0,0,1)); 
    466   ExportVssTree("vss-tree-101.x3d", vssTree, Vector3(1,0,1)); 
    467   ExportVssTree("vss-tree-101m.x3d", vssTree, Vector3(-1,0,-1)); 
    468  
    469   ExportVssTreeLeaves(vssTree, 10); 
     464  if (0) 
     465  { 
     466          ExportVssTree("vss-tree-100.x3d", vssTree, Vector3(1,0,0)); 
     467          ExportVssTree("vss-tree-001.x3d", vssTree, Vector3(0,0,1)); 
     468          ExportVssTree("vss-tree-101.x3d", vssTree, Vector3(1,0,1)); 
     469          ExportVssTree("vss-tree-101m.x3d", vssTree, Vector3(-1,0,-1)); 
     470          ExportVssTreeLeaves(vssTree, 10); 
     471  } 
    470472 
    471473  // viewcells->UpdatePVS(newVssRays); 
     
    543545 
    544546        /// compute view cell contribution of rays 
    545         mViewCellsManager->ComputeSampleContributions(passRays, 
     547/*      mViewCellsManager->ComputeSampleContributions(passRays, 
    546548                                                                                                  sampleContributions,  
    547549                                                                                                  contributingSamples); 
     
    560562                CLEAR_CONTAINER(passRays); 
    561563        } 
    562  
     564*/ 
    563565        samples+=num; 
    564566        float pvs = vssTree->GetAvgPvsSize(); 
     
    574576  } 
    575577 
     578  cout << "here" << endl; 
    576579  //-- post process view cells 
    577580  mViewCellsManager->PostProcess(objects, storedRays); 
  • trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

    r462 r465  
    357357    stream<<"<IndexedLineSet coordIndex=\""<<endl; 
    358358  else 
    359     stream<<"<IndexedFaceSet ccw=\"TRUE\" coordIndex=\""<<endl; 
     359    //stream<<"<IndexedFaceSet ccw=\"TRUE\" coordIndex=\""<<endl; 
     360        stream << "<IndexedFaceSet coordIndex=\"" << endl; 
    360361 
    361362  FaceContainer::const_iterator fi = mesh->mFaces.begin(); 
     
    431432        //-- create and write indices 
    432433        if (mWireframe) 
    433                 stream << "<IndexedLineSet ccw=\"TRUE\" coordIndex=\"" << endl; 
     434                stream<<"<IndexedLineSet coordIndex=\""<<endl; 
    434435        else 
    435                 stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl; 
    436  
     436                //stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl; 
     437                stream << "<IndexedFaceSet coordIndex=\"" << endl; 
    437438        int index = 0; 
    438439         
     
    497498        //-- create and write indices 
    498499        if (mWireframe) 
    499                 stream << "<IndexedLineSet ccw=\"TRUE\" coordIndex=\"" << endl; 
     500                stream<<"<IndexedLineSet coordIndex=\""<<endl; 
    500501        else 
    501                 stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl; 
     502                //stream << "<IndexedFaceSet ccw=\"TRUE\" coordIndex=\"" << endl; 
     503                stream << "<IndexedFaceSet coordIndex=\"" << endl; 
    502504 
    503505        int index = 0; 
Note: See TracChangeset for help on using the changeset viewer.