Ignore:
Timestamp:
10/16/06 15:11:13 (18 years ago)
Author:
mattausch
Message:

worked on gradient method

Location:
GTP/trunk/Lib/Vis/Preprocessing/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp

    r1624 r1625  
    113113        mSubdivisionStats.open(subdivisionStatsLog); 
    114114 
    115         mMinRenderCostDecrease = -1; 
     115        //mMinRenderCostDecrease = -1; 
    116116 
    117117        Debug << "******** Hierachy Manager Parameters ***********" << endl; 
     
    123123        Debug << "repair queue: " << mRepairQueue << endl; 
    124124        Debug << "number of multilevels: " << mNumMultiLevels << endl; 
    125         Debug << "min render cost " << mMinRenderCostDecrease << endl; 
     125        //Debug << "min render cost " << mMinRenderCostDecrease << endl; 
    126126        Debug << endl; 
    127127} 
     
    196196 
    197197 
    198 SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate() 
    199 { 
    200         SubdivisionCandidate *splitCandidate = mTQueue.Top(); 
    201         mTQueue.Pop(); 
     198SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue) 
     199{ 
     200        SubdivisionCandidate *splitCandidate = splitQueue.Top(); 
     201        splitQueue.Pop(); 
    202202 
    203203        return splitCandidate; 
     
    211211                                                mHierarchyStats.mRenderCostDecrease, 
    212212                                                mHierarchyStats.mTotalCost, 
    213                                                 mHierarchyStats.mPvsEntries 
     213                                                mHierarchyStats.mPvsEntries, 
     214                                                mHierarchyStats.mMemory, 
     215                                                1.0f / (mHierarchyStats.mTotalCost * mHierarchyStats.mMemory) 
    214216                                                ); 
    215217} 
     
    219221                                                                                   const float renderCostDecr, 
    220222                                                                                   const float totalRenderCost, 
    221                                                                                    const int pvsEntries) 
     223                                                                                   const int pvsEntries, 
     224                                                                                   const int memory, 
     225                                                                                   const float renderCostPerStorage) 
    222226{ 
    223227        mSubdivisionStats 
     
    225229                        << "#RenderCostDecrease\n" << renderCostDecr << endl  
    226230                        << "#TotalEntriesInPvs\n" << pvsEntries << endl 
    227                         << "#TotalRenderCost\n" << totalRenderCost << endl; 
     231                        << "#TotalRenderCost\n" << totalRenderCost << endl 
     232                        << "#Memory\n" << memory << endl 
     233                        << "#RcPerMb\n" << renderCostPerStorage << endl; 
    228234} 
    229235 
     
    236242                || (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance) 
    237243                || (candidate->GlobalTerminationCriteriaMet()) 
    238                 || (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease) 
     244                //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease) 
    239245                ); 
    240246 
     
    270276                                                                                         const ObjectContainer &objects, 
    271277                                                                                         AxisAlignedBox3 *forcedViewSpace) 
     278{ 
     279        mHierarchyStats.Reset(); 
     280        mHierarchyStats.Start(); 
     281         
     282        mHierarchyStats.mNodes = 2; 
     283         
     284        mHierarchyStats.mTotalCost = (float)objects.size(); 
     285        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl; 
     286 
     287        const long startTime = GetTime(); 
     288        cout << "Constructing view space / object space tree ... \n"; 
     289         
     290        // compute view space bounding box 
     291        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace); 
     292 
     293        // use sah for evaluating osp tree construction  
     294        // in the first iteration of the subdivision 
     295        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType; 
     296        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV; 
     297 
     298        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType; 
     299 
     300        SplitQueue objectSpaceQueue; 
     301        SplitQueue viewSpaceQueue; 
     302 
     303        int maxSteps = 200; // number of initial splits; 
     304        float renderCostDecr = 0; 
     305 
     306        // This method subdivides view space / object space  
     307        // in order to converge to some optimal cost for this partition 
     308        // start with object space partiton 
     309        // then optimizate view space partition for the current osp 
     310        // and vice versa until iteration depth is reached. 
     311 
     312        while (1) 
     313        { 
     314                // subdivide object space first 
     315                // for first round, use sah splits. Once view space partition 
     316                // has started, use render cost heuristics instead 
     317                SubdivisionCandidate *osc = ResetObjectSpaceSubdivision(sampleRays, objects); 
     318                objectSpaceQueue.Push(osc); 
     319 
     320                // process object space candidates using  
     321                // render queue for objects until slope of previous subdivision  
     322                // is reached 
     323                SubdivisionCandidateContainer ospContainer; 
     324 
     325                const int ospSteps = RunConstruction(objectSpaceQueue, ospContainer, renderCostDecr, maxSteps); 
     326            cout << ospSteps << " object space partition steps taken" << endl; 
     327 
     328                // use splits of one kind until rendercost slope is reached 
     329                renderCostDecr = mHierarchyStats.mRenderCostDecrease; 
     330                 
     331                // object space subdivision constructed 
     332                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
     333 
     334                /// Repair split queue 
     335                cout << "repairing queue ... " << endl; 
     336                 
     337                vector<SubdivisionCandidate *> dirtyList; 
     338 
     339                CollectDirtyCandidates(ospContainer, dirtyList); 
     340                RepairQueue(dirtyList, viewSpaceQueue); 
     341 
     342                cout << "finished repairing queue ... " << endl; 
     343                 
     344                CLEAR_CONTAINER(ospContainer); 
     345 
     346                ///////////////// 
     347                // subdivide view space with respect to the objects 
     348 
     349                SubdivisionCandidate *vsc = ResetViewSpaceSubdivision(sampleRays, objects); 
     350                viewSpaceQueue.Push(vsc); 
     351 
     352                SubdivisionCandidateContainer vspContainer; 
     353                // process view space candidates 
     354                const int vspSteps = RunConstruction(viewSpaceQueue, vspContainer, renderCostDecr, maxSteps); 
     355 
     356                cout << vspSteps << " object space partition steps taken" << endl; 
     357 
     358                // view space subdivision constructed 
     359                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
     360 
     361                // use splits of one kind until rendercost slope is reached 
     362                renderCostDecr = mHierarchyStats.mRenderCostDecrease; 
     363 
     364                /// Repair split queue 
     365                cout << "repairing queue ... " << endl; 
     366                 
     367                CollectDirtyCandidates(vspContainer, dirtyList); 
     368                RepairQueue(dirtyList, objectSpaceQueue); 
     369 
     370                cout << "finished repairing queue ... " << endl; 
     371 
     372                CLEAR_CONTAINER(vspContainer); 
     373        } 
     374         
     375        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
     376 
     377        mHierarchyStats.Stop(); 
     378        mVspTree->mVspStats.Stop(); 
     379 
     380        FinishObjectSpaceSubdivision(objects); 
     381} 
     382 
     383 
     384void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays, 
     385                                                                                        const ObjectContainer &objects, 
     386                                                                                        AxisAlignedBox3 *forcedViewSpace) 
     387{ 
     388        mHierarchyStats.Reset(); 
     389        mHierarchyStats.Start(); 
     390        mHierarchyStats.mNodes = 2; // two nodes for view space and object space 
     391 
     392        mHierarchyStats.mTotalCost = (float)objects.size(); 
     393        mHierarchyStats.mRenderCostDecrease = 0; 
     394 
     395        EvalSubdivisionStats(); 
     396        Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl; 
     397 
     398        const long startTime = GetTime(); 
     399        cout << "Constructing view space / object space tree ... \n"; 
     400         
     401        // compute view space bounding box 
     402        mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace); 
     403 
     404        // use objects for evaluating vsp tree construction in the first levels 
     405        // of the subdivision 
     406        mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType; 
     407        mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV; 
     408 
     409        mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType; 
     410        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV; 
     411 
     412        // start with view space subdivison immediately? 
     413        if (StartViewSpaceSubdivision()) 
     414        { 
     415                // prepare vsp tree for traversal 
     416                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
     417                PrepareViewSpaceSubdivision(sampleRays, objects); 
     418        } 
     419         
     420        // start object space subdivision immediately? 
     421        if (StartObjectSpaceSubdivision()) 
     422        { 
     423                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
     424                PrepareObjectSpaceSubdivision(sampleRays, objects); 
     425        } 
     426 
     427        // begin subdivision 
     428        RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace); 
     429         
     430        cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
     431 
     432        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
     433        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
     434 
     435        mHierarchyStats.Stop(); 
     436        mVspTree->mVspStats.Stop(); 
     437        FinishObjectSpaceSubdivision(objects); 
     438} 
     439 
     440 
     441SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays, 
     442                                                                                                                                        const ObjectContainer &objects) 
     443{ 
     444        cout << "\nstarting view space hierarchy construction ... " << endl; 
     445 
     446        // hack: reset global cost misses 
     447        mHierarchyStats.mGlobalCostMisses = 0; 
     448 
     449        RayInfoContainer *viewSpaceRays = new RayInfoContainer(); 
     450        SubdivisionCandidate *vsc =  
     451                mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays); 
     452 
     453        mHierarchyStats.mTotalCost = mVspTree->mTotalCost; 
     454        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl; 
     455 
     456        return vsc; 
     457} 
     458 
     459 
     460SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
     461                                                                                                                                          const ObjectContainer &objects) 
     462{ 
     463        // hack: reset global cost misses 
     464        mHierarchyStats.mGlobalCostMisses = 0; 
     465 
     466        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
     467        { 
     468                return PrepareOspTree(sampleRays, objects); 
     469        } 
     470        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
     471        { 
     472                return PrepareBvHierarchy(sampleRays, objects); 
     473        } 
     474         
     475        return NULL; 
     476} 
     477 
     478 
     479SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays, 
     480                                                                                                                   const ObjectContainer &objects) 
     481{ 
     482        const long startTime = GetTime(); 
     483 
     484        cout << "preparing bv hierarchy construction ... " << endl; 
     485         
     486        // compute first candidate 
     487        SubdivisionCandidate *sc = 
     488                mBvHierarchy->PrepareConstruction(sampleRays, objects); 
     489 
     490        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
     491        Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl; 
     492 
     493        cout << "finished bv hierarchy preparation in "  
     494                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
     495          
     496        return sc; 
     497} 
     498 
     499 
     500SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays, 
     501                                                                                                           const ObjectContainer &objects) 
     502{ 
     503        cout << "starting osp tree construction ... " << endl; 
     504 
     505        RayInfoContainer *objectSpaceRays = new RayInfoContainer(); 
     506 
     507        // start with one big kd cell - all objects can be seen from everywhere 
     508        // note: only true for view space = object space 
     509 
     510        // compute first candidate 
     511        SubdivisionCandidate *osc = 
     512                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays); 
     513 
     514        mHierarchyStats.mTotalCost = mOspTree->mTotalCost; 
     515        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl; 
     516         
     517    return osc; 
     518} 
     519 
     520 
     521bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,  
     522                                                                                                 SplitQueue &splitQueue, 
     523                                                                                                 const bool repairQueue) 
     524{ 
     525        // test if global termination criteria were met before this split 
     526        const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc); 
     527        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE); 
     528 
     529        bool success = false; 
     530 
     531        switch (sc->Type()) 
     532        { 
     533        case SubdivisionCandidate::VIEW_SPACE: 
     534                { 
     535                        VspNode *n = mVspTree->Subdivide(splitQueue, sc, terminationCriteriaMet); 
     536                        // check if termination criteria failed 
     537                        success = !n->IsLeaf(); 
     538                } 
     539                break; 
     540        case SubdivisionCandidate::OBJECT_SPACE: 
     541                { 
     542                        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
     543                        { 
     544                                KdNode *n = mOspTree->Subdivide(splitQueue, sc, terminationCriteriaMet); 
     545 
     546                                // local or global termination criteria failed 
     547                                success = !n->IsLeaf(); 
     548                        } 
     549                        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
     550                        { 
     551                                BvhNode *n = mBvHierarchy->Subdivide(splitQueue, sc, terminationCriteriaMet); 
     552 
     553                                // local or global termination criteria failed 
     554                                success = !n->IsLeaf();                                  
     555                        } 
     556                } 
     557                break; 
     558        default: 
     559                break; 
     560        } 
     561 
     562        if (!success) // split was not taken 
     563        { 
     564                return false; 
     565        } 
     566 
     567        /////////////// 
     568        //-- split was successful => update stats and queue 
     569 
     570    // cost ratio of cost decrease / totalCost 
     571        const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost; 
     572        //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl; 
     573         
     574        if (costRatio < mTermMinGlobalCostRatio) 
     575        { 
     576                ++ mHierarchyStats.mGlobalCostMisses; 
     577        } 
     578         
     579        mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease(); 
     580         
     581        cout << sc->Type() << " "; 
     582                 
     583        // update stats 
     584        mHierarchyStats.mNodes += 2; 
     585         
     586        const int pvsEntries = sc->GetPvsEntriesIncr(); 
     587        mHierarchyStats.mPvsEntries += pvsEntries; 
     588         
     589        //cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl; 
     590        mHierarchyStats.mMemory += 0; // TODO 
     591        mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease(); 
     592 
     593        // subdivision successful 
     594        EvalSubdivisionStats(); 
     595                 
     596        if (repairQueue)  
     597        { 
     598                // reevaluate candidates affected by the split for view space splits,  
     599                // this would be object space splits and other way round 
     600                vector<SubdivisionCandidate *> dirtyList; 
     601                CollectDirtyCandidates(sc, dirtyList); 
     602 
     603                RepairQueue(dirtyList, splitQueue); 
     604        } 
     605 
     606        return true; 
     607} 
     608 
     609 
     610int HierarchyManager::GetObjectSpaceSubdivisionDepth() const 
     611{ 
     612        int maxDepth = 0; 
     613 
     614        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
     615        { 
     616                maxDepth = mOspTree->mOspStats.maxDepth; 
     617        } 
     618        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
     619        { 
     620                maxDepth = mBvHierarchy->mBvhStats.maxDepth; 
     621        } 
     622 
     623        return maxDepth; 
     624} 
     625 
     626 
     627bool HierarchyManager::StartObjectSpaceSubdivision() const 
     628{ 
     629        // view space construction already started 
     630        if (ObjectSpaceSubdivisionConstructed()) 
     631                return false; 
     632 
     633        // start immediately with object space subdivision? 
     634        if (mStartWithObjectSpace) 
     635                return true; 
     636 
     637        // is the queue empty again? 
     638        if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty()) 
     639                return true; 
     640 
     641        // has the depth for subdivision been reached? 
     642        return  
     643                ((mConstructionType == INTERLEAVED) &&  
     644                 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth)); 
     645} 
     646 
     647 
     648bool HierarchyManager::StartViewSpaceSubdivision() const 
     649{ 
     650        // view space construction already started 
     651        if (ViewSpaceSubdivisionConstructed()) 
     652                return false; 
     653 
     654        // start immediately with view space subdivision? 
     655        if (!mStartWithObjectSpace) 
     656                return true; 
     657 
     658        // is the queue empty again? 
     659        if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty()) 
     660                return true; 
     661 
     662        // has the depth for subdivision been reached? 
     663        return  
     664                ((mConstructionType == INTERLEAVED) &&  
     665                 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth())); 
     666} 
     667 
     668 
     669void HierarchyManager::RunConstruction(const bool repairQueue, 
     670                                                                           const VssRayContainer &sampleRays, 
     671                                                                           const ObjectContainer &objects, 
     672                                                                           AxisAlignedBox3 *forcedViewSpace) 
     673{ 
     674        while (!FinishedConstruction()) 
     675        { 
     676                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);     
     677                         
     678                /////////////////// 
     679                //-- subdivide leaf node 
     680 
     681                ApplySubdivisionCandidate(sc, mTQueue, repairQueue); 
     682                                 
     683                // we use objects for evaluating vsp tree construction until  
     684                // a certain depth once a certain depth existiert ... 
     685                if (StartObjectSpaceSubdivision()) 
     686                { 
     687                        mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
     688 
     689                        cout << "\nstarting object space subdivision at depth "  
     690                                 << mVspTree->mVspStats.maxDepth << " ("  
     691                                 << mMinDepthForObjectSpaceSubdivion << ") " << endl; 
     692 
     693                        PrepareObjectSpaceSubdivision(sampleRays, objects); 
     694 
     695                        cout << "reseting queue ... "; 
     696                        ResetQueue(); 
     697                        cout << "finished" << endl; 
     698                } 
     699 
     700                if (StartViewSpaceSubdivision()) 
     701                { 
     702                        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
     703 
     704                        cout << "\nstarting view space subdivision at depth "  
     705                                 << GetObjectSpaceSubdivisionDepth() << " ("  
     706                                 << mMinDepthForViewSpaceSubdivion << ") " << endl; 
     707 
     708                        PrepareViewSpaceSubdivision(sampleRays, objects); 
     709 
     710                        cout << "reseting queue ... "; 
     711                        ResetQueue(); 
     712                        cout << "finished" << endl; 
     713                } 
     714 
     715                DEL_PTR(sc); 
     716        } 
     717} 
     718 
     719 
     720void HierarchyManager::RunConstruction(const bool repairQueue) 
     721{ 
     722        //int i = 0; 
     723        // main loop 
     724        while (!FinishedConstruction()) 
     725        { 
     726                SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);     
     727                         
     728                //////// 
     729                //-- subdivide leaf node of either type 
     730 
     731                ApplySubdivisionCandidate(sc, mTQueue, repairQueue); 
     732 
     733                DEL_PTR(sc); 
     734        } 
     735} 
     736 
     737 
     738int HierarchyManager::RunConstruction(SplitQueue &splitQueue, 
     739                                                                          SubdivisionCandidateContainer &chosenCandidates, 
     740                                                                          const float minRenderCostDecr, 
     741                                                                          const int maxSteps) 
     742{ 
     743        int steps = 0; 
     744 
     745        // main loop 
     746        while (!splitQueue.Empty() && ((steps ++) < maxSteps)) 
     747        { 
     748                SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);  
     749                 
     750                // minimum slope reached 
     751                if (sc->GetRenderCostDecrease() < minRenderCostDecr) 
     752                        break; 
     753 
     754                //////// 
     755                //-- subdivide leaf node of either type 
     756 
     757                const bool repairQueue = false; 
     758                ApplySubdivisionCandidate(sc, splitQueue, repairQueue); 
     759 
     760                chosenCandidates.push_back(sc); 
     761        } 
     762 
     763        return steps; 
     764} 
     765 
     766 
     767SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,  
     768                                                                                                                                        const ObjectContainer &objects) 
     769{        
     770        // no object space subdivision yet 
     771        if (!ObjectSpaceSubdivisionConstructed()) 
     772        { 
     773                return PrepareObjectSpaceSubdivision(sampleRays, objects); 
     774        } 
     775 
     776        SubdivisionCandidate *firstCandidate = NULL; 
     777 
     778        // object space partition constructed => reconstruct 
     779        switch (mObjectSpaceSubdivisionType) 
     780        { 
     781        case BV_BASED_OBJ_SUBDIV: 
     782                { 
     783                        cout << "\nreseting bv hierarchy" << endl; 
     784                        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl; 
     785         
     786                        SubdivisionCandidate *firstCandidate =  
     787                                mBvHierarchy->Reset(sampleRays, objects); 
     788 
     789                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
     790 
     791                        mHierarchyStats.mNodes = 2; 
     792                        mHierarchyStats.mPvsEntries = 0; 
     793                        mHierarchyStats.mRenderCostDecrease = 0; 
     794 
     795                        // evaluate stats before first subdivision 
     796                        EvalSubdivisionStats(); 
     797                } 
     798                break; 
     799 
     800        case KD_BASED_OBJ_SUBDIV: 
     801                // TODO 
     802                break; 
     803        default: 
     804                break; 
     805        } 
     806 
     807        return firstCandidate; 
     808} 
     809 
     810 
     811SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,  
     812                                                                                                                                  const ObjectContainer &objects) 
     813{ 
     814        ViewCellsManager *vc = mVspTree->mViewCellsManager; 
     815 
     816        // HACK: rather not destroy vsp tree 
     817        DEL_PTR(mVspTree); 
     818        mVspTree = new VspTree(); 
     819        mVspTree->mHierarchyManager = this; 
     820        mVspTree->mViewCellsManager = vc; 
     821 
     822        SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects); 
     823         
     824        mHierarchyStats.mNodes = 2; 
     825        mHierarchyStats.mPvsEntries = 0; 
     826        mHierarchyStats.mRenderCostDecrease = 0; 
     827 
     828        EvalSubdivisionStats(); 
     829 
     830        return vsc; 
     831} 
     832 
     833 
     834void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                     
     835                                                                                   const ObjectContainer &objects, 
     836                                                                                   AxisAlignedBox3 *forcedViewSpace) 
    272837{ 
    273838        mHierarchyStats.Reset(); 
     
    307872                mSubdivisionStats.open(subdivisionStatsLog); 
    308873 
    309                 float oldRenderCost = mHierarchyStats.mRenderCostDecrease; 
    310                 const bool isObjectSpace = true; 
    311  
    312                 // subdivide object space first 
    313                 ResetObjectSpaceSubdivision(sampleRays, objects); 
    314  
    315                 // process object space candidates using  
    316                 // render queue for objects 
    317                 RunConstruction(false, isObjectSpace, oldRenderCost); 
    318          
    319                 oldRenderCost = mHierarchyStats.mRenderCostDecrease; 
    320          
    321                 // object space subdivision constructed 
    322                 mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
    323  
    324                 cout << "iteration " << i << " of " << limit << " finished" << endl; 
    325  
    326                 mSubdivisionStats.close(); 
    327                  
    328                 sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i); 
    329                 mSubdivisionStats.open(subdivisionStatsLog); 
    330  
    331                 ///////////////// 
    332                 // subdivide view space with respect to the objects 
    333  
    334                 ResetViewSpaceSubdivision(sampleRays, objects); 
    335                  
    336                 // process view space candidates 
    337                 RunConstruction(false, !isObjectSpace, oldRenderCost); 
    338  
    339                 // view space subdivision constructed 
    340                 mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
    341          
    342                 cout << "iteration " << i << " of " << limit << " finished" << endl; 
    343  
    344                 mSubdivisionStats.close(); 
    345  
    346                 if ((i ++) >= limit) 
    347                         break; 
    348         } 
    349          
    350         cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
    351  
    352 /*#if _DEBUG 
    353         cout << "view space: " << GetViewSpaceBox() << endl; 
    354         cout << "object space:  " << GetObjectSpaceBox() << endl; 
    355 #endif*/ 
    356  
    357         mHierarchyStats.Stop(); 
    358         mVspTree->mVspStats.Stop(); 
    359         FinishObjectSpaceSubdivision(objects); 
    360 } 
    361  
    362  
    363  
    364 void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays, 
    365                                                                                         const ObjectContainer &objects, 
    366                                                                                         AxisAlignedBox3 *forcedViewSpace) 
    367 { 
    368         mHierarchyStats.Reset(); 
    369         mHierarchyStats.Start(); 
    370         mHierarchyStats.mNodes = 2; // two nodes for view space and object space 
    371  
    372         mHierarchyStats.mTotalCost = (float)objects.size(); 
    373         mHierarchyStats.mRenderCostDecrease = 0; 
    374  
    375         EvalSubdivisionStats(); 
    376         Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl; 
    377  
    378         const long startTime = GetTime(); 
    379         cout << "Constructing view space / object space tree ... \n"; 
    380          
    381         // compute view space bounding box 
    382         mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace); 
    383  
    384         // use objects for evaluating vsp tree construction in the first levels 
    385         // of the subdivision 
    386         mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType; 
    387         mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV; 
    388  
    389         mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType; 
    390         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV; 
    391  
    392         // start with view space subdivison immediately? 
    393         if (StartViewSpaceSubdivision()) 
    394         { 
    395                 // prepare vsp tree for traversal 
    396                 mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
    397                 PrepareViewSpaceSubdivision(sampleRays, objects); 
    398         } 
    399          
    400         // start object space subdivision immediately? 
    401         if (StartObjectSpaceSubdivision()) 
    402         { 
    403                 mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
    404                 PrepareObjectSpaceSubdivision(sampleRays, objects); 
    405         } 
    406  
    407         // begin subdivision 
    408         RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace); 
    409          
    410         cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
    411  
    412         mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
    413         mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
    414  
    415         mHierarchyStats.Stop(); 
    416         mVspTree->mVspStats.Stop(); 
    417         FinishObjectSpaceSubdivision(objects); 
    418 } 
    419  
    420  
    421 void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays, 
    422                                                                                                    const ObjectContainer &objects) 
    423 { 
    424         cout << "\nstarting view space hierarchy construction ... " << endl; 
    425         // hack: reset global cost misses 
    426         mHierarchyStats.mGlobalCostMisses = 0; 
    427          
    428         RayInfoContainer *viewSpaceRays = new RayInfoContainer(); 
    429         SubdivisionCandidate *vsc =  
    430                 mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays); 
    431  
    432         mHierarchyStats.mTotalCost = mVspTree->mTotalCost; 
    433         cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl; 
    434  
    435         mTQueue.Push(vsc); 
    436 } 
    437  
    438  
    439 void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
    440                                                                                                          const ObjectContainer &objects) 
    441 { 
    442         mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses 
    443  
    444         if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
    445         { 
    446                 PrepareOspTree(sampleRays, objects); 
    447         } 
    448         else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
    449         { 
    450                 PrepareBvHierarchy(sampleRays, objects); 
    451         } 
    452 } 
    453  
    454  
    455 void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays, 
    456                                                                                   const ObjectContainer &objects) 
    457 { 
    458         const long startTime = GetTime(); 
    459  
    460         cout << "preparing bv hierarchy construction ... " << endl; 
    461          
    462         // compute first candidate 
    463         SubdivisionCandidate *sc = 
    464                 mBvHierarchy->PrepareConstruction(sampleRays, objects); 
    465  
    466         mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
    467         Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl; 
    468  
    469     mTQueue.Push(sc); 
    470         cout << "finished bv hierarchy preparation in "  
    471                  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
    472 } 
    473  
    474  
    475 void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays, 
    476                                                                           const ObjectContainer &objects) 
    477 { 
    478         cout << "starting osp tree construction ... " << endl; 
    479  
    480         RayInfoContainer *objectSpaceRays = new RayInfoContainer(); 
    481  
    482         // start with one big kd cell - all objects can be seen from everywhere 
    483         // note: only true for view space = object space 
    484  
    485         // compute first candidate 
    486         SubdivisionCandidate *osc = 
    487                 mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays); 
    488  
    489         mHierarchyStats.mTotalCost = mOspTree->mTotalCost; 
    490         Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl; 
    491          
    492     mTQueue.Push(osc); 
    493 } 
    494  
    495  
    496 bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,  
    497                                                                                                  const bool repairQueue) 
    498 { 
    499         // test if global termination criteria were met before this split 
    500         const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc); 
    501         const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE); 
    502  
    503         bool success = false; 
    504  
    505         switch (sc->Type()) 
    506         { 
    507         case SubdivisionCandidate::VIEW_SPACE: 
    508                 { 
    509                         VspNode *n = mVspTree->Subdivide(mTQueue, sc, terminationCriteriaMet); 
    510                         // check if termination criteria failed 
    511                         success = !n->IsLeaf(); 
    512                 } 
    513                 break; 
    514         case SubdivisionCandidate::OBJECT_SPACE: 
    515                 { 
    516                         if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
    517                         { 
    518                                 KdNode *n = mOspTree->Subdivide(mTQueue, sc, terminationCriteriaMet); 
    519                                 // local or global termination criteria failed 
    520                                 success = !n->IsLeaf(); 
    521                         } 
    522                         else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
    523                         { 
    524                                 BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, terminationCriteriaMet); 
    525                                 // local or global termination criteria failed 
    526                                 success = !n->IsLeaf();                                  
    527                         } 
    528                 } 
    529                 break; 
    530         default: 
    531                 break; 
    532         } 
    533  
    534         if (!success) // split was not taken 
    535         { 
    536                 return false; 
    537         } 
    538  
    539         /////////////// 
    540         //-- split was successful => update stats and queue 
    541  
    542     // cost ratio of cost decrease / totalCost 
    543         const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost; 
    544         //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl; 
    545          
    546         if (costRatio < mTermMinGlobalCostRatio) 
    547         { 
    548                 ++ mHierarchyStats.mGlobalCostMisses; 
    549         } 
    550          
    551         mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease(); 
    552          
    553         cout << sc->Type() << " "; 
    554                  
    555         // update stats 
    556         mHierarchyStats.mNodes += 2; 
    557          
    558         const int pvsEntries = sc->GetPvsEntriesIncr(); 
    559         mHierarchyStats.mPvsEntries += pvsEntries; 
    560          
    561         //cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl; 
    562         mHierarchyStats.mMemory += 0; // TODO 
    563         mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease(); 
    564  
    565         // subdivision successful 
    566         EvalSubdivisionStats(); 
    567                  
    568         if (repairQueue)  
    569         { 
    570                 // reevaluate candidates affected by the split for view space splits,  
    571                 // this would be object space splits and other way round 
    572  
    573                 RepairQueue(sc); 
    574         } 
    575  
    576         return true; 
    577 } 
    578  
    579  
    580 int HierarchyManager::GetObjectSpaceSubdivisionDepth() const 
    581 { 
    582         int maxDepth = 0; 
    583  
    584         if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
    585         { 
    586                 maxDepth = mOspTree->mOspStats.maxDepth; 
    587         } 
    588         else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
    589         { 
    590                 maxDepth = mBvHierarchy->mBvhStats.maxDepth; 
    591         } 
    592  
    593         return maxDepth; 
    594 } 
    595  
    596  
    597 bool HierarchyManager::StartObjectSpaceSubdivision() const 
    598 { 
    599         // view space construction already started 
    600         if (ObjectSpaceSubdivisionConstructed()) 
    601                 return false; 
    602  
    603         // start immediately with object space subdivision? 
    604         if (mStartWithObjectSpace) 
    605                 return true; 
    606  
    607         // is the queue empty again? 
    608         if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty()) 
    609                 return true; 
    610  
    611         // has the depth for subdivision been reached? 
    612         return  
    613                 ((mConstructionType == INTERLEAVED) &&  
    614                  (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth)); 
    615 } 
    616  
    617  
    618 bool HierarchyManager::StartViewSpaceSubdivision() const 
    619 { 
    620         // view space construction already started 
    621         if (ViewSpaceSubdivisionConstructed()) 
    622                 return false; 
    623  
    624         // start immediately with view space subdivision? 
    625         if (!mStartWithObjectSpace) 
    626                 return true; 
    627  
    628         // is the queue empty again? 
    629         if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty()) 
    630                 return true; 
    631  
    632         // has the depth for subdivision been reached? 
    633         return  
    634                 ((mConstructionType == INTERLEAVED) &&  
    635                  (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth())); 
    636 } 
    637  
    638  
    639 void HierarchyManager::RunConstruction(const bool repairQueue, 
    640                                                                            const VssRayContainer &sampleRays, 
    641                                                                            const ObjectContainer &objects, 
    642                                                                            AxisAlignedBox3 *forcedViewSpace) 
    643 { 
    644         int i = 0; 
    645         while (!FinishedConstruction()) 
    646         { 
    647                 SubdivisionCandidate *sc = NextSubdivisionCandidate();     
    648                          
    649                 /////////////////// 
    650                 //-- subdivide leaf node 
    651  
    652                 ApplySubdivisionCandidate(sc, repairQueue); 
    653                                  
    654                 // we use objects for evaluating vsp tree construction until  
    655                 // a certain depth once a certain depth existiert ... 
    656                 if (StartObjectSpaceSubdivision()) 
    657                 { 
    658                         mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
    659  
    660                         cout << "\nstarting object space subdivision at depth "  
    661                                  << mVspTree->mVspStats.maxDepth << " ("  
    662                                  << mMinDepthForObjectSpaceSubdivion << ") " << endl; 
    663  
    664                         PrepareObjectSpaceSubdivision(sampleRays, objects); 
    665  
    666                         cout << "reseting queue ... "; 
    667                         ResetQueue(); 
    668                         cout << "finished" << endl; 
    669                 } 
    670  
    671                 if (StartViewSpaceSubdivision()) 
    672                 { 
    673                         mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
    674  
    675                         cout << "\nstarting view space subdivision at depth "  
    676                                  << GetObjectSpaceSubdivisionDepth() << " ("  
    677                                  << mMinDepthForViewSpaceSubdivion << ") " << endl; 
    678  
    679                         PrepareViewSpaceSubdivision(sampleRays, objects); 
    680  
    681                         cout << "reseting queue ... "; 
    682                         ResetQueue(); 
    683                         cout << "finished" << endl; 
    684                 } 
    685  
    686                 DEL_PTR(sc); 
    687         } 
    688 } 
    689  
    690  
    691 void HierarchyManager::RunConstruction(const bool repairQueue) 
    692 { 
    693         //int i = 0; 
    694         // main loop 
    695         while (!FinishedConstruction()) 
    696         { 
    697                 SubdivisionCandidate *sc = NextSubdivisionCandidate();     
    698                          
    699                 //////// 
    700                 //-- subdivide leaf node of either type 
    701                 ApplySubdivisionCandidate(sc, repairQueue); 
    702  
    703                 DEL_PTR(sc); 
    704         } 
    705 } 
    706  
    707  
    708 void HierarchyManager::RunConstruction(const bool isObjectSpace, 
    709                                                                            const float oldRenderCostDecr) 
    710 { 
    711         //int i = 0; 
    712         // main loop 
    713         while (!FinishedConstruction()) 
    714         { 
    715                 SubdivisionCandidate *sc = NextSubdivisionCandidate();     
    716                          
    717                 //////// 
    718                 //-- subdivide leaf node of either type 
    719                 ApplySubdivisionCandidate(sc, repairQueue); 
    720  
    721                 DEL_PTR(sc); 
    722         } 
    723 } 
    724  
    725  
    726 void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,  
    727                                                                                                    const ObjectContainer &objects) 
    728                                                                                                    //const bool startFromScratch) 
    729 {        
    730         // no object space subdivision yet 
    731         if (!ObjectSpaceSubdivisionConstructed()) 
    732         { 
    733                 return PrepareObjectSpaceSubdivision(sampleRays, objects); 
    734         } 
    735  
    736         // object space partition constructed => reconstruct 
    737         switch (mObjectSpaceSubdivisionType) 
    738         { 
    739         case BV_BASED_OBJ_SUBDIV: 
    740                 { 
    741                         cout << "\nreseting bv hierarchy" << endl; 
    742                         Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl; 
    743          
    744                         //if (startFromScratch) 
    745                         //{ 
    746                                 SubdivisionCandidate *firstCandidate =  
    747                                         mBvHierarchy->Reset(sampleRays, objects); 
    748  
    749                                 mTQueue.Push(firstCandidate); 
    750                                 mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
    751  
    752                                 mHierarchyStats.mNodes = 2; 
    753                                 mHierarchyStats.mPvsEntries = 0; 
    754                                 mHierarchyStats.mRenderCostDecrease = 0; 
    755  
    756                                 EvalSubdivisionStats(); 
    757                         /*} 
    758                         else 
    759                         { 
    760                         }*/ 
    761                 } 
    762                 break; 
    763  
    764         case KD_BASED_OBJ_SUBDIV: 
    765                 // TODO 
    766                 break; 
    767         default: 
    768                 break; 
    769         } 
    770 } 
    771  
    772  
    773 void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,  
    774                                                                                                  const ObjectContainer &objects) 
    775 { 
    776         ViewCellsManager *vc = mVspTree->mViewCellsManager; 
    777  
    778         // HACK: rather not destroy vsp tree 
    779         DEL_PTR(mVspTree); 
    780         mVspTree = new VspTree(); 
    781         mVspTree->mHierarchyManager = this; 
    782         mVspTree->mViewCellsManager = vc; 
    783  
    784         PrepareViewSpaceSubdivision(sampleRays, objects); 
    785          
    786         mHierarchyStats.mNodes = 2; 
    787         mHierarchyStats.mPvsEntries = 0; 
    788         mHierarchyStats.mRenderCostDecrease = 0; 
    789  
    790         EvalSubdivisionStats(); 
    791 } 
    792  
    793  
    794 void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,                                                                                     
    795                                                                                    const ObjectContainer &objects, 
    796                                                                                    AxisAlignedBox3 *forcedViewSpace) 
    797 { 
    798         mHierarchyStats.Reset(); 
    799         mHierarchyStats.Start(); 
    800         mHierarchyStats.mNodes = 2; 
    801          
    802         mHierarchyStats.mTotalCost = (float)objects.size(); 
    803         Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl; 
    804  
    805         const long startTime = GetTime(); 
    806         cout << "Constructing view space / object space tree ... \n"; 
    807          
    808         // compute view space bounding box 
    809         mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace); 
    810  
    811         // use sah for evaluating osp tree construction  
    812         // in the first iteration of the subdivision 
    813          
    814         mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType; 
    815         mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV; 
    816  
    817         mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType; 
    818         //mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV; 
    819  
    820         const int limit = mNumMultiLevels; 
    821         int i = 0; 
    822  
    823         // This method subdivides view space / object space  
    824         // in order to converge to some optimal cost for this partition 
    825         // start with object space partiton 
    826         // then optimizate view space partition for the current osp 
    827         // and vice versa until iteration depth is reached. 
    828         while (1) 
    829         { 
    830                 char subdivisionStatsLog[100]; 
    831                 sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i); 
    832                 mSubdivisionStats.open(subdivisionStatsLog); 
    833  
    834874                // subdivide object space first 
    835875 
     
    9611001 
    9621002 
    963 void HierarchyManager::RepairQueue(SubdivisionCandidate *sc) 
     1003void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,  
     1004                                                                                          SubdivisionCandidateContainer &dirtyList) 
     1005{ 
     1006        SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end(); 
     1007 
     1008        for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit) 
     1009        { 
     1010                // we have either a object space or view space split 
     1011                if ((*sit)->Type() == SubdivisionCandidate::VIEW_SPACE) 
     1012                { 
     1013                        CollectViewSpaceDirtyList(*sit, dirtyList); 
     1014                } 
     1015                else // object space split 
     1016                { 
     1017                        CollectObjectSpaceDirtyList(*sit, dirtyList); 
     1018                } 
     1019        } 
     1020} 
     1021 
     1022 
     1023void HierarchyManager::RepairQueue(const vector<SubdivisionCandidate *> &dirtyList,  
     1024                                                                   SplitQueue &splitQueue) 
    9641025{ 
    9651026        // for each update of the view space partition: 
     
    9811042        // collect list of "dirty" candidates 
    9821043        const long startTime = GetTime(); 
    983     
    984         vector<SubdivisionCandidate *> dirtyList; 
    985         CollectDirtyCandidates(sc, dirtyList); 
    986         if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... "; 
     1044        if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... "; 
    9871045         
    9881046 
     
    9971055                const float rcd = sc->GetRenderCostDecrease(); 
    9981056                 
    999                 mTQueue.Erase(sc); // erase from queue 
     1057                splitQueue.Erase(sc); // erase from queue 
    10001058                sc->EvalPriority(); // reevaluate 
    10011059                 
     
    10051063                          << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl; 
    10061064#endif   
    1007                 mTQueue.Push(sc); // reinsert 
     1065                splitQueue.Push(sc); // reinsert 
    10081066                cout << "."; 
    10091067        } 
    10101068 
    1011         long endTime = GetTime(); 
    1012         Real timeDiff = TimeDiff(startTime, endTime); 
     1069        const long endTime = GetTime(); 
     1070        const Real timeDiff = TimeDiff(startTime, endTime); 
     1071 
    10131072        mHierarchyStats.mRepairTime += timeDiff; 
    10141073 
     
    10241083        while (!mTQueue.Empty()) 
    10251084        { 
    1026                 SubdivisionCandidate *candidate = NextSubdivisionCandidate(); 
    1027                 candidate->EvalPriority(); // reevaluate 
     1085                SubdivisionCandidate *candidate = NextSubdivisionCandidate(mTQueue); 
     1086                 // reevaluate local split plane and priority 
     1087                candidate->EvalPriority(); 
    10281088                cout << "."; 
    10291089                mCandidateBuffer.push_back(candidate); 
  • GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h

    r1624 r1625  
    239239protected: 
    240240 
     241        /** Returns true if the global termination criteria were met. 
     242        */ 
    241243        bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const; 
    242244 
     
    244246                first split candidates. 
    245247        */ 
    246         void PrepareObjectSpaceSubdivision( 
    247                 const VssRayContainer &sampleRays, 
    248                 const ObjectContainer &objects); 
    249  
    250         void RunConstruction( 
    251                 const bool repairQueue, 
    252                 const VssRayContainer &sampleRays, 
    253                 const ObjectContainer &objects, 
    254                 AxisAlignedBox3 *forcedViewSpace); 
    255          
     248        SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
     249                                                                                                                const ObjectContainer &objects); 
     250 
     251 
     252        ////////////////////////////// 
     253        // the main loop 
     254        ////////////////////// 
     255 
     256        /** This is for interleaved construction / sequential construction. 
     257        */ 
     258        void RunConstruction(const bool repairQueue, 
     259                                                 const VssRayContainer &sampleRays, 
     260                                                 const ObjectContainer &objects, 
     261                                                 AxisAlignedBox3 *forcedViewSpace); 
     262         
     263        /** This is for interleaved construction using some objects  
     264                and some view space splits. 
     265        */ 
     266        int RunConstruction(SplitQueue &splitQueue, 
     267                                                SubdivisionCandidateContainer &chosenCandidates, 
     268                                                const float minRenderCostDecr, 
     269                                                const int maxSteps); 
     270 
     271        /** Default subdivision method. 
     272        */ 
    256273        void RunConstruction(const bool repairQueue); 
    257274                 
     275        //////////////////////////////////////////////// 
     276 
    258277        /** Evaluates the subdivision candidate and executes the split. 
    259278        */ 
    260         bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, const bool repairQueue); 
    261  
     279        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc,  
     280                                                                   SplitQueue &splitQueue, 
     281                                                                   const bool repairQueue); 
     282 
     283        /** Tests if hierarchy construction is finished. 
     284        */ 
    262285        bool FinishedConstruction() const; 
    263286 
    264         SubdivisionCandidate *NextSubdivisionCandidate(); 
    265  
    266         /** Repairs the dirty entries of the candidate queue. 
    267         */ 
    268         void RepairQueue(SubdivisionCandidate *sc); 
     287        /** Returns next subdivision candidate from the split queue. 
     288        */ 
     289        SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue); 
     290 
     291        /** Repairs the dirty entries of the subdivision candidate queue. The 
     292                list of entries is given in the dirty list. 
     293        */ 
     294        void RepairQueue(const vector<SubdivisionCandidate *> &dirtyList, SplitQueue &splitQueue); 
     295 
     296        /** Collect subdivision candidates which were affected by the splits from the 
     297                chosenCandidates list. 
     298        */  
     299        void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,  
     300                                                                SubdivisionCandidateContainer &dirtyList); 
    269301 
    270302        /** Collect the list of dirty candidates after the current  
    271303                subdivision candidate split. 
    272304        */ 
    273         void CollectDirtyCandidates( 
    274                 SubdivisionCandidate *sc, 
    275                 vector<SubdivisionCandidate *> &dirtyList); 
     305        void CollectDirtyCandidates(SubdivisionCandidate *sc, 
     306                                                                vector<SubdivisionCandidate *> &dirtyList); 
    276307 
    277308        /** Evaluate subdivision stats for log. 
     
    279310        void EvalSubdivisionStats(); 
    280311 
    281         void AddSubdivisionStats( 
    282                 const int splits, 
    283                 const float renderCostDecr, 
    284                 const float totalRenderCost, 
    285                 const int totalPvsEntries); 
    286  
    287         bool AddSampleToPvs( 
    288                 Intersectable *obj,  
    289                 const float pdf, 
    290                 float &contribution) const; 
    291  
    292         void CollectViewSpaceDirtyList( 
    293                 SubdivisionCandidate *sc, 
    294                 SubdivisionCandidateContainer &dirtyList); 
    295  
    296         void CollectObjectSpaceDirtyList( 
    297                 SubdivisionCandidate *sc, 
    298                 SubdivisionCandidateContainer &dirtyList); 
     312        void AddSubdivisionStats(const int splits, 
     313                                                         const float renderCostDecr, 
     314                                                         const float totalRenderCost, 
     315                                                         const int totalPvsEntries,  
     316                                                         const int memory, 
     317                                                         const float renderCostPerStorage); 
     318 
     319        bool AddSampleToPvs(Intersectable *obj,  
     320                                                const float pdf, 
     321                                                float &contribution) const; 
     322 
     323        /** Collect affected view space candidates. 
     324        */ 
     325        void CollectViewSpaceDirtyList(SubdivisionCandidate *sc, 
     326                                                                   SubdivisionCandidateContainer &dirtyList); 
     327 
     328        /** Collect affected object space candidates. 
     329        */ 
     330        void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc, 
     331                                                                         SubdivisionCandidateContainer &dirtyList); 
    299332                 
    300         void ExportOspTree( 
    301                 Exporter *exporter,  
    302                 const ObjectContainer &objects) const; 
    303  
     333        /** Export object space partition tree. 
     334        */ 
     335        void ExportOspTree(Exporter *exporter,  
     336                                           const ObjectContainer &objects) const; 
     337 
     338        /** Parse the environment variables. 
     339        */ 
    304340        void ParseEnvironment(); 
    305341 
     
    307343        bool StartViewSpaceSubdivision() const; 
    308344 
    309         void PrepareBvHierarchy( 
    310                 const VssRayContainer &sampleRays, 
    311                 const ObjectContainer &objects); 
    312  
    313         void PrepareOspTree( 
    314                 const VssRayContainer &sampleRays, 
    315                 const ObjectContainer &objects); 
    316  
    317         void PrepareViewSpaceSubdivision( 
    318                 const VssRayContainer &sampleRays, 
    319                 const ObjectContainer &objects); 
    320  
     345        //////////////////////////// 
     346        // Helper function for preparation of subdivision 
     347        /////// 
     348 
     349        /** Prepare bv hierarchy for subdivision 
     350        */ 
     351        SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays, 
     352                                                                           const ObjectContainer &objects); 
     353 
     354        /** Prepare object space kd tree for subdivision. 
     355        */ 
     356        SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays, 
     357                                                                   const ObjectContainer &objects); 
     358 
     359        /** Prepare view space subdivision and add candidate to queue. 
     360        */ 
     361        SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays, 
     362                                                                                                          const ObjectContainer &objects); 
     363 
     364        /** Was object space subdivision already constructed? 
     365        */ 
    321366        bool ObjectSpaceSubdivisionConstructed() const; 
     367         
     368        /** Was view space subdivision already constructed? 
     369        */ 
    322370        bool ViewSpaceSubdivisionConstructed() const; 
    323371 
     372        /** Reset the split queue, i.e., reevaluate the split candidates. 
     373        */ 
    324374    void ResetQueue(); 
    325375 
     376        /** After the suddivision has ended, do some final tasks. 
     377        */ 
    326378        void FinishObjectSpaceSubdivision(const ObjectContainer &objects) const; 
    327379 
     380        /** Returns depth of object space subdivision. 
     381        */ 
    328382        int GetObjectSpaceSubdivisionDepth() const; 
    329383 
     384        /** Construct object space partition interleaved with view space partition. 
     385                Each time the best object or view space candidate is selected 
     386                for the next split. 
     387        */ 
    330388        void ConstructInterleaved( 
    331389                const VssRayContainer &sampleRays, 
     
    333391                AxisAlignedBox3 *forcedViewSpace); 
    334392 
     393        /** Construct object space partition interleaved with view space partition. 
     394                The method chooses a number candidates of each type for subdivision. 
     395                The number is determined by the "gradient", i.e., the render cost decrease. 
     396                Once this render cost decrease is lower than the render cost decrease 
     397                for the splits of previous type, the method will stop current subdivision and 
     398                evaluate if view space or object space would be the beneficial for the  
     399                next number of split. 
     400        */ 
    335401        void ConstructInterleaved2( 
    336402                const VssRayContainer &sampleRays, 
     
    349415                so construction can be restarted. 
    350416        */ 
    351         void ResetObjectSpaceSubdivision( 
    352                 const VssRayContainer &rays,  
    353                 const ObjectContainer &objects); 
    354  
    355         void HierarchyManager::ResetViewSpaceSubdivision( 
    356                 const VssRayContainer &rays,  
    357                 const ObjectContainer &objects); 
     417        SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays,  
     418                                                                                                          const ObjectContainer &objects); 
     419 
     420        SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays,  
     421                                                                                                        const ObjectContainer &objects); 
    358422 
    359423 
     
    390454        /// object space partition kd tree 
    391455        OspTree *mOspTree; 
     456 
    392457        public: 
    393458        /// bounding volume hierarchy 
     
    409474        //////////////////// 
    410475 
    411         /// keeps track of cost during subdivision 
    412         //float mTotalCost; 
    413476        /// statistics about the hierarchy 
    414477        HierarchyStatistics mHierarchyStats; 
     
    417480        int mMinDepthForViewSpaceSubdivion; 
    418481         
    419         int mMinRenderCostDecrease; 
     482        //int mMinRenderCostDecrease; 
    420483 
    421484        ofstream mSubdivisionStats; 
Note: See TracChangeset for help on using the changeset viewer.