Changeset 1779 for GTP/trunk/Lib/Vis


Ignore:
Timestamp:
11/22/06 10:49:09 (18 years ago)
Author:
mattausch
Message:

warning: this version contains bugs!!

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

Legend:

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

    r1778 r1779  
    4141 
    4242/// sorting operator 
    43 inline static bool ilt2(Intersectable *obj1, Intersectable *obj2) 
     43inline static bool smallerSize(Intersectable *obj1, Intersectable *obj2) 
    4444{ 
    4545        return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea(); 
     
    221221BvHierarchy::BvHierarchy(): 
    222222mRoot(NULL), 
    223 mTimeStamp(1) 
     223mTimeStamp(1), 
     224mIsInitialSubdivision(false) 
    224225{ 
    225226        ReadEnvironment(); 
    226227        mSubdivisionCandidates = new SortableEntryContainer; 
    227         for (int i = 0; i < 4; ++ i) 
    228                 mSortedObjects[i] = NULL; 
     228//      for (int i = 0; i < 4; ++ i) 
     229//              mSortedObjects[i] = NULL; 
    229230} 
    230231 
     
    236237 
    237238        // delete the presorted objects 
    238         for (int i = 0; i < 4; ++ i) 
     239        /*for (int i = 0; i < 4; ++ i) 
    239240        { 
    240241                DEL_PTR(mSortedObjects[i]); 
    241         } 
     242        }*/ 
    242243         
    243244        // delete the tree 
     
    249250{ 
    250251        bool randomize = false; 
    251         Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize); 
     252        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.randomize", randomize); 
    252253          
    253254        // initialise random generator for heuristics 
     
    290291        mSubdivisionStats.open(subdivisionStatsLog); 
    291292 
    292         Environment::GetSingleton()->GetFloatValue( 
    293                 "BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight); 
    294         Environment::GetSingleton()->GetBoolValue( 
    295                 "BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting); 
     293        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight); 
     294        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting); 
    296295        Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility); 
    297296        Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests); 
    298  
     297        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useInitialSubdivision", mApplyInitialPartition); 
     298         
     299        mApplyInitialPartition = true; 
    299300        //mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell)); 
    300301        //mMemoryConst = (float)sizeof(BvhLeaf); 
     
    326327        Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl; 
    327328        Debug << "bvh mem const: " << mMemoryConst << endl; 
    328  
     329        Debug << "apply initial partition: " << mApplyInitialPartition << endl; 
    329330        Debug << endl; 
    330331} 
     
    457458                                                                const bool globalCriteriaMet) 
    458459{ 
    459         BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate); 
     460        BvhSubdivisionCandidate *sc =  
     461                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate); 
    460462        BvhTraversalData &tData = sc->mParentData; 
    461463 
     
    484486                //-- push the new split candidates on the queue 
    485487                 
    486                 BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData); 
    487                 BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData); 
     488                BvhSubdivisionCandidate *frontCandidate =  
     489                                new BvhSubdivisionCandidate(tFrontData); 
     490                BvhSubdivisionCandidate *backCandidate =  
     491                                new BvhSubdivisionCandidate(tBackData); 
    488492 
    489493                EvalSubdivisionCandidate(*frontCandidate); 
     
    519523 
    520524 
     525float BvHierarchy::EvalPriority(const BvhSubdivisionCandidate &splitCandidate, 
     526                                                                const float renderCostDecr, 
     527                                                                const float oldRenderCost) const 
     528{ 
     529        float priority; 
     530 
     531        if (mIsInitialSubdivision) 
     532        { 
     533                priority = (float)-splitCandidate.mParentData.mDepth; 
     534                return priority; 
     535        } 
     536 
     537        BvhLeaf *leaf = splitCandidate.mParentData.mNode; 
     538 
     539        // surface area heuristics is used when there is  
     540        // no view space subdivision available.  
     541        // In order to have some prioritized traversal,  
     542        // we use this formula instead 
     543        if (mHierarchyManager->GetViewSpaceSubdivisionType() ==  
     544                HierarchyManager::NO_VIEWSPACE_SUBDIV) 
     545        { 
     546                priority = EvalSahCost(leaf); 
     547        } 
     548        else 
     549        { 
     550                // take render cost of node into account  
     551                // otherwise danger of being stuck in a local minimum! 
     552                const float factor = mRenderCostDecreaseWeight; 
     553 
     554                priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost; 
     555                 
     556                if (mHierarchyManager->mConsiderMemory) 
     557                { 
     558                        priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst); 
     559                } 
     560        } 
     561 
     562        // hack: don't allow empty splits to be taken 
     563        if (splitCandidate.mFrontObjects.empty() || splitCandidate.mBackObjects.empty()) 
     564                priority = 0; 
     565 
     566        return priority; 
     567} 
     568 
     569 
    521570void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate,  
    522571                                                                                   bool computeSplitPlane) 
     
    543592                const int previousMisses = splitCandidate.mParentData.mMaxCostMisses; 
    544593 
    545                 splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? previousMisses + 1 : previousMisses); 
    546  
     594                splitCandidate.SetMaxCostMisses( 
     595                        maxCostRatioViolated ? previousMisses + 1 : previousMisses); 
    547596        } 
    548597 
     
    570619#endif 
    571620 
    572         float priority; 
    573  
    574         // surface area heuristics is used when there is  
    575         // no view space subdivision available.  
    576         // In order to have some prioritized traversal,  
    577         // we use this formula instead 
    578         if (mHierarchyManager->GetViewSpaceSubdivisionType() ==  
    579                 HierarchyManager::NO_VIEWSPACE_SUBDIV) 
    580         { 
    581                 priority = EvalSahCost(leaf); 
    582         } 
    583         else 
    584         { 
    585                 // take render cost of node into account  
    586                 // otherwise danger of being stuck in a local minimum! 
    587                 const float factor = mRenderCostDecreaseWeight; 
    588  
    589                 if (1) 
    590                 { 
    591                         priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost; 
    592                         if (mHierarchyManager->mConsiderMemory) 
    593                         { 
    594                                 priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst); 
    595                         } 
    596                 } 
    597                 else 
    598                 { 
    599                         if (!mHierarchyManager->mConsiderMemory) 
    600                         { 
    601                                 priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost; 
    602                         } 
    603                         else 
    604                         { 
    605                                 const float ratio =  
    606                                         renderCostDecr / ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst); 
    607  
    608                                 priority = factor * ratio + (1.0f - factor) * oldRenderCost; 
    609                         } 
    610                 } 
    611         } 
    612  
    613         // hack: don't allow empty splits to be taken 
    614         if (splitCandidate.mFrontObjects.empty() || splitCandidate.mBackObjects.empty()) 
    615                 priority = 0; 
     621        const float priority = EvalPriority(splitCandidate,  
     622                                                                                oldRenderCost,  
     623                                                                                renderCostDecr); 
     624         
    616625        // compute global decrease in render cost 
    617626        splitCandidate.SetPriority(priority); 
     
    630639 
    631640 
    632 inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const 
     641inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const 
    633642{ 
    634643        const bool terminationCriteriaMet = 
    635644                        (0 
    636                         || ((int)data.mNode->mObjects.size() <= 1)//mTermMinObjects) 
     645                        || ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects) 
    637646                        //|| (data.mProbability <= mTermMinProbability) 
    638647                        //|| (data.mNumRays <= mTermMinRays) 
     
    643652        { 
    644653                cout << "bvh local termination criteria met:" << endl; 
    645                 cout << "objects: " << data.mNode->mObjects.size() << " " << mTermMinObjects << endl; 
     654                cout << "objects: " << tData.mNode->mObjects.size() << " " << mTermMinObjects << endl; 
    646655        } 
    647656#endif 
     
    11681177                                                                                   ObjectContainer &objectsBack) 
    11691178{ 
    1170         /////////////////////////////////////////////////////// 
    1171         //-- go through the lists, count the number of objects left  
    1172         //-- and right and evaluate the cost funcion 
    1173  
    1174         // prepare the heuristics by setting mailboxes and counters. 
     1179        ///////////////////////////////////////////// 
     1180        //-- go through the lists, count the number of objects  
     1181        //-- left and right and evaluate the cost funcion 
     1182 
     1183        // prepare the heuristics by setting mailboxes and counters 
    11751184        const float totalVol = PrepareHeuristics(tData, axis); 
    11761185         
     
    11831192        float nObjectsRight = nTotalObjects; 
    11841193 
    1185         const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume(); 
     1194        const float viewSpaceVol =  
     1195                mViewCellsManager->GetViewSpaceBox().GetVolume(); 
    11861196 
    11871197        SortableEntryContainer::const_iterator backObjectsStart =  
     
    12281238                nObjectsRight -= rc; 
    12291239                 
    1230                 const bool noValidSplit = ((nObjectsLeft <= Limits::Small) || (nObjectsRight <= Limits::Small)); 
     1240                // split is only valid if #objects on left and right is not zero 
     1241                const bool noValidSplit = ((nObjectsLeft <= Limits::Small) ||  
     1242                                                                   (nObjectsRight <= Limits::Small)); 
    12311243 
    12321244                // the heuristics 
     
    12541266        } 
    12551267 
    1256         //////////////////////////////////////////// 
     1268        //////////////////////////////////////// 
    12571269        //-- assign object to front and back volume 
    12581270 
     
    14421454                                                                                 bool useVisibilityBasedHeuristics) 
    14431455{ 
     1456        if (mIsInitialSubdivision) 
     1457        { 
     1458                ApplyInititialSplit(tData,  
     1459                                                        frontObjects,  
     1460                                                        backObjects); 
     1461 
     1462                return 0; 
     1463        } 
     1464         
     1465 
    14441466        ObjectContainer nFrontObjects[3]; 
    14451467        ObjectContainer nBackObjects[3]; 
     
    16321654 
    16331655 
    1634 float BvHierarchy::EvalSahCost(BvhLeaf *leaf) 
     1656float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const 
    16351657{ 
    16361658        //////////////// 
     
    20632085 
    20642086 
    2065 SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays, 
    2066                                                                                                            const ObjectContainer &objects) 
     2087void BvHierarchy::PrepareConstruction(SplitQueue &tQueue, 
     2088                                                                          const VssRayContainer &sampleRays, 
     2089                                                                          const ObjectContainer &objects) 
    20672090{ 
    20682091        /////////////////////////////////////// 
     
    21052128        if (mUseGlobalSorting) 
    21062129        { 
    2107                 AssignInitialSortedObjectList(oData); 
     2130                AssignInitialSortedObjectList(oData, objects); 
    21082131        } 
    21092132         
     
    21122135        //-- add first candidate for object space partition      
    21132136 
    2114         BvhSubdivisionCandidate *oSubdivisionCandidate = new BvhSubdivisionCandidate(oData); 
     2137        BvhSubdivisionCandidate *oSubdivisionCandidate =  
     2138                new BvhSubdivisionCandidate(oData); 
    21152139 
    21162140        // evaluate priority 
     
    21232147        PrintSubdivisionStats(*oSubdivisionCandidate); 
    21242148         
    2125         return oSubdivisionCandidate; 
    2126 } 
    2127  
    2128  
    2129 void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData) 
     2149        if (mApplyInitialPartition) 
     2150        { 
     2151                ApplyInitialSubdivision(oSubdivisionCandidate, tQueue);          
     2152        } 
     2153        else 
     2154        { 
     2155                tQueue.Push(oSubdivisionCandidate); 
     2156        } 
     2157} 
     2158 
     2159 
     2160void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData, 
     2161                                                                                                const ObjectContainer &objects) 
    21302162{ 
    21312163        // we sort the objects as a preprocess so they don't have 
     
    21332165        for (int i = 0; i < 3; ++ i) 
    21342166        { 
    2135                 // create new objects 
    2136                 if (!mSortedObjects[i]) 
    2137                 { 
    2138                         mSortedObjects[i] = new SortableEntryContainer(); 
    2139                         CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i); 
    2140                 } 
    2141  
     2167                SortableEntryContainer *sortedObjects = new SortableEntryContainer(); 
     2168 
     2169                CreateLocalSubdivisionCandidates(objects,  
     2170                                                                             &sortedObjects,  
     2171                                                                                 true,  
     2172                                                                                 i); 
     2173                 
    21422174                // copy list into traversal data list 
    21432175                tData.mSortedObjects[i] = new ObjectContainer(); 
    2144                 tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size()); 
    2145  
    2146                 SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end(); 
    2147  
    2148                 for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit) 
     2176                tData.mSortedObjects[i]->reserve((int)objects.size()); 
     2177 
     2178                SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end(); 
     2179 
     2180                for (oit = sortedObjects->begin(); oit != oit_end; ++ oit) 
    21492181                { 
    21502182                        tData.mSortedObjects[i]->push_back((*oit).mObject); 
    21512183                } 
    2152         } 
    2153  
    2154         // create new objects 
    2155         if (!mSortedObjects[3]) 
    2156         { 
    2157                 mSortedObjects[3] = new SortableEntryContainer(); 
    2158         } 
    2159 /* 
     2184 
     2185                delete sortedObjects; 
     2186        } 
     2187 
    21602188        // last sorted list: by size 
    21612189        tData.mSortedObjects[3] = new ObjectContainer(); 
    2162         tData.mSortedObjects[3]->reserve((int)mSortedObjects[i]->size()); 
    2163  
    2164         SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end(); 
    2165  
    2166         for (oit = mSortedObjects[3]->begin(); oit != oit_end; ++ oit) 
    2167         { 
    2168                 tData.mSortedObjects[3]->push_back((*oit).mObject); 
    2169         } 
    2170 */ 
     2190        tData.mSortedObjects[3]->reserve((int)objects.size()); 
     2191 
     2192        *(tData.mSortedObjects[3]) = objects; 
     2193 
     2194        stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize); 
    21712195} 
    21722196 
     
    22122236 
    22132237 
    2214 SubdivisionCandidate *BvHierarchy::Reset(const VssRayContainer &sampleRays,  
    2215                                                                                  const ObjectContainer &objects) 
     2238void BvHierarchy::Reset(SplitQueue &tQueue, 
     2239                                                const VssRayContainer &sampleRays,  
     2240                                                const ObjectContainer &objects) 
    22162241{ 
    22172242        // reset stats 
     
    22432268        BvhTraversalData oData(bvhLeaf, 0, prop, nRays); 
    22442269 
    2245         AssignInitialSortedObjectList(oData); 
     2270        AssignInitialSortedObjectList(oData, objects); 
    22462271         
    22472272 
     
    22602285        PrintSubdivisionStats(*oSubdivisionCandidate); 
    22612286 
    2262         return oSubdivisionCandidate; 
     2287        tQueue.Push(oSubdivisionCandidate); 
    22632288} 
    22642289 
     
    24732498 
    24742499 
    2475 void BvHierarchy::InititialSubdivision(ObjectContainer &objects) 
    2476 { 
    2477         /*std::stable_sort(objects.begin(), objects.end(), ilt2); 
    2478         ObjectContainer::iterator oit; 
    2479  
    2480         stack<BvhLeaf *> tStack; 
    2481  
    2482         while (!tStack.empty()) 
    2483         { 
    2484                 BvhLeaf *leaf = tStack.top(); 
    2485  
    2486                 if (!InitialTerminationCriteriaMet(leaf)) 
    2487                 { 
    2488                         ChooseSplitIndex(objects, oit); 
    2489                         SubdivideLeaf(leaf, oit); 
    2490                 } 
    2491         }*/ 
    2492 } 
    2493  
    2494  
    2495 void BvHierarchy::ChooseSplitIndex(const ObjectContainer &objects,  
    2496                                                                    ObjectContainer::const_iterator &oit) 
    2497 { 
    2498         ObjectContainer::const_iterator oit2, oit2_end = objects.end(); 
     2500void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate, 
     2501                                                                                  SplitQueue &tQueue) 
     2502{ 
     2503        mIsInitialSubdivision = true; 
     2504 
     2505        SplitQueue tempQueue; 
     2506 
     2507        while (!tempQueue.Empty()) 
     2508        { 
     2509                SubdivisionCandidate *candidate = tQueue.Top(); 
     2510                tQueue.Pop(); 
     2511 
     2512                BvhSubdivisionCandidate *bsc =  
     2513                        dynamic_cast<BvhSubdivisionCandidate *>(candidate); 
     2514 
     2515                const bool globalCriteriaMet =  
     2516                        GlobalTerminationCriteriaMet(bsc->mParentData); 
     2517 
     2518                if (!InitialTerminationCriteriaMet(bsc->mParentData)) 
     2519                { 
     2520                        BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet); 
     2521 
     2522                        // not needed anymore 
     2523                        delete bsc; 
     2524                } 
     2525                else // initial preprocessing  finished for this candidate 
     2526                { 
     2527                        tQueue.Push(bsc); 
     2528                } 
     2529        } 
     2530 
     2531        mIsInitialSubdivision = false; 
     2532} 
     2533 
     2534 
     2535void BvHierarchy::ApplyInititialSplit(const BvhTraversalData &tData, 
     2536                                                                          ObjectContainer &frontObjects, 
     2537                                      ObjectContainer &backObjects) 
     2538{ 
     2539        ObjectContainer *objects = tData.mSortedObjects[3]; 
     2540 
     2541        ObjectContainer::const_iterator oit, oit_end = objects->end(); 
    24992542     
    25002543        float maxAreaDiff = 0.0f; 
    25012544 
    2502         for (oit2 = objects.begin(); oit2 != (objects.end() - 1); ++ oit2) 
    2503         { 
    2504                 Intersectable *obj = *oit2; 
    2505                 Intersectable *obj2 = *(oit2 + 1); 
     2545        ObjectContainer::const_iterator backObjectsStart = objects->begin(); 
     2546 
     2547    for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit) 
     2548        { 
     2549                Intersectable *objS = *oit; 
     2550                Intersectable *objL = *(oit + 1); 
    25062551                 
    25072552                const float areaDiff =  
    2508                         fabs(obj->GetBox().SurfaceArea() - obj2->GetBox().SurfaceArea()); 
     2553                        fabs(objS->GetBox().SurfaceArea() - objL->GetBox().SurfaceArea()); 
    25092554 
    25102555                if (areaDiff > maxAreaDiff) 
    25112556                { 
    25122557                        maxAreaDiff = areaDiff; 
    2513                         oit = oit2; 
    2514                 } 
    2515         } 
    2516 } 
    2517  
    2518  
    2519 bool BvHierarchy::InitialTerminationCriteriaMet(BvhLeaf *leaf) const 
    2520 { 
    2521         if (((int)leaf->mObjects.size() < mInititialObjectsSize) || 
    2522                 (leaf->mObjects.back()->GetBox().SurfaceArea() < mMinInitialSurfaceArea)) 
    2523  
    2524         { 
    2525                 return true;  
    2526         } 
    2527  
    2528         return false; 
    2529 } 
    2530  
    2531  
    2532 } 
     2558                        backObjectsStart = oit + 1; 
     2559                } 
     2560        } 
     2561 
     2562        // belongs to back bv 
     2563        for (oit = objects->begin(); oit != backObjectsStart; ++ oit) 
     2564        { 
     2565                backObjects.push_back(*oit); 
     2566        } 
     2567 
     2568        // belongs to front bv 
     2569        for (oit = backObjectsStart; oit != oit_end; ++ oit) 
     2570        { 
     2571                frontObjects.push_back(*oit); 
     2572        } 
     2573} 
     2574 
     2575 
     2576bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const 
     2577{ 
     2578        return (0 
     2579                    || ((int)tData.mNode->mObjects.size() < mInititialObjectsSize) 
     2580                        || (tData.mNode->mObjects.back()->GetBox().SurfaceArea() < mMinInitialSurfaceArea) 
     2581                        ); 
     2582} 
     2583 
     2584 
     2585} 
  • GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h

    r1778 r1779  
    685685                                  ObjectContainer &objectsBack); 
    686686 
    687         /** Computes priority of the traversal data and stores it in tData. 
    688         */ 
    689         void EvalPriority(BvhTraversalData &tData) const; 
    690687 
    691688        /** Evaluates render cost of the bv induced by these objects 
     
    755752                                                                                                 const bool sort, 
    756753                                                                                                 const int axis); 
     754 
     755        float EvalPriority(const BvhSubdivisionCandidate &splitCandidate, 
     756                                           const float renderCostDecr, 
     757                                           const float oldRenderCost) const; 
    757758 
    758759        /** Computes object partition with the best cost according to the heurisics. 
     
    788789        /** Evaluates cost for a leaf given the surface area heuristics. 
    789790        */ 
    790         float EvalSahCost(BvhLeaf *leaf); 
     791        float EvalSahCost(BvhLeaf *leaf) const; 
    791792 
    792793        //////////////////////////////////////////////// 
     
    862863                the first subdivision candidate. 
    863864        */ 
    864         SubdivisionCandidate *PrepareConstruction(const VssRayContainer &sampleRays, 
    865                                                                                           const ObjectContainer &objects); 
     865        void PrepareConstruction(SplitQueue &tQueue, 
     866                                                         const VssRayContainer &sampleRays, 
     867                                                         const ObjectContainer &objects); 
    866868 
    867869        /** Resets bv hierarchy. E.g. deletes root and resets stats. 
    868870        */ 
    869         SubdivisionCandidate *Reset(const VssRayContainer &rays,  
    870                                                                 const ObjectContainer &objects); 
     871        void Reset(SplitQueue &tQueue, 
     872                           const VssRayContainer &rays,  
     873                           const ObjectContainer &objects); 
    871874 
    872875        /** Evaluates volume of view cells that see the objects. 
     
    876879        /** Assigns or newly creates initial list of sorted objects. 
    877880        */ 
    878         void AssignInitialSortedObjectList(BvhTraversalData &tData); 
     881        void AssignInitialSortedObjectList(BvhTraversalData &tData, 
     882                                                                           const ObjectContainer &objects); 
    879883 
    880884        /** Assigns sorted objects to front and back data. 
     
    890894 
    891895 
    892         /////////////////////////////////// 
     896        //////////////////// 
    893897        // initial subdivision 
    894898 
     
    896900                some criteria (size, shader) 
    897901        */ 
    898         void InititialSubdivision(ObjectContainer &objects); 
    899  
    900         void ChooseSplitIndex(const ObjectContainer &objects,  
    901                                                   ObjectContainer::const_iterator &oit); 
    902  
    903         bool InitialTerminationCriteriaMet(BvhLeaf *leaf) const; 
     902        void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate, 
     903                                                                 SplitQueue &tQueue); 
     904 
     905        void ApplyInititialSplit(const BvhTraversalData &tData, 
     906                                                         ObjectContainer &frontObjects, 
     907                                                         ObjectContainer &backObjects); 
     908 
     909        bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const; 
     910 
    904911        float mMinInitialSurfaceArea; 
    905 int mInititialObjectsSize; 
     912        int mInititialObjectsSize; 
     913 
    906914protected: 
    907915         
     
    990998        bool mUseBboxAreaForSah; 
    991999 
    992         SortableEntryContainer *mSortedObjects[4]; 
     1000        //SortableEntryContainer *mSortedObjects[4]; 
    9931001 
    9941002        int mMinRaysForVisibility; 
     
    9971005        float mMemoryConst; 
    9981006 
     1007        bool mIsInitialSubdivision; 
     1008 
     1009        bool mApplyInitialPartition; 
     1010 
    9991011        int mMaxTests; 
    10001012}; 
  • GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp

    r1771 r1779  
    24882488                                        "bvh_construction_use_global_sorting=", 
    24892489                                        "true"); 
     2490         
     2491        RegisterOption("BvHierarchy.Construction.useInitialSubdivisio", 
     2492                                        optBool, 
     2493                                        "bvh_construction_use_initial_subdivision=", 
     2494                                        "false"); 
    24902495 
    24912496        RegisterOption("BvHierarchy.minRaysForVisibility", 
  • GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp

    r1778 r1779  
    416416        const int maxSteps = mMaxStepsOfSameType; 
    417417 
    418         SubdivisionCandidate *osc =  
    419                 PrepareObjectSpaceSubdivision(sampleRays, objects); 
    420         objectSpaceQueue.Push(osc); 
    421  
     418        PrepareObjectSpaceSubdivision(objectSpaceQueue, sampleRays, objects); 
     419         
    422420        ///////////////////////// 
    423421        // calulcate initial object space splits 
     
    437435 
    438436        // create view space 
    439         SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects); 
    440         viewSpaceQueue.Push(vsc); 
     437        PrepareViewSpaceSubdivision(viewSpaceQueue, sampleRays, objects); 
    441438 
    442439        dirtyList.clear(); 
     
    589586                // prepare vsp tree for traversal 
    590587        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
    591                 SubdivisionCandidate *vspSc =  
    592                         PrepareViewSpaceSubdivision(sampleRays, objects); 
    593  
    594                 mTQueue.Push(vspSc); 
     588                 
     589                PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects); 
    595590        } 
    596591         
     
    599594        { 
    600595                mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType; 
    601                 SubdivisionCandidate *ospSc = 
    602                         PrepareObjectSpaceSubdivision(sampleRays, objects); 
    603                 mTQueue.Push(ospSc); 
     596                PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects); 
    604597        } 
    605598 
     
    619612 
    620613 
    621 SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays, 
    622                                                                                                                                         const ObjectContainer &objects) 
     614void HierarchyManager::PrepareViewSpaceSubdivision(SplitQueue &tQueue, 
     615                                                                                                   const VssRayContainer &sampleRays, 
     616                                                                                                   const ObjectContainer &objects) 
    623617{ 
    624618        cout << "\npreparing view space hierarchy construction ... " << endl; 
     
    628622 
    629623        RayInfoContainer *viewSpaceRays = new RayInfoContainer(); 
    630         SubdivisionCandidate *vsc =  
    631                 mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays); 
     624        mVspTree->PrepareConstruction(tQueue, sampleRays, *viewSpaceRays); 
    632625 
    633626        ///////// 
     
    635628 
    636629        mHierarchyStats.mTotalCost = mVspTree->mTotalCost; 
    637          
    638630        cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl; 
    639  
    640         return vsc; 
    641631} 
    642632 
     
    669659 
    670660 
    671 SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
    672                                                                                                                                           const ObjectContainer &objects) 
     661void HierarchyManager::PrepareObjectSpaceSubdivision(SplitQueue &tQueue, 
     662                                                                                                         const VssRayContainer &sampleRays, 
     663                                                                                                         const ObjectContainer &objects) 
    673664{ 
    674665        // hack: reset global cost misses 
     
    677668        if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV) 
    678669        { 
    679                 return PrepareOspTree(sampleRays, objects); 
     670                return PrepareOspTree(tQueue, sampleRays, objects); 
    680671        } 
    681672        else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV) 
    682673        { 
    683                 return PrepareBvHierarchy(sampleRays, objects); 
    684         } 
    685          
    686         return NULL; 
    687 } 
    688  
    689  
    690 SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays, 
    691                                                                                                                    const ObjectContainer &objects) 
     674                return PrepareBvHierarchy(tQueue, sampleRays, objects); 
     675        } 
     676} 
     677 
     678 
     679void HierarchyManager::PrepareBvHierarchy(SplitQueue &tQueue, 
     680                                                                                  const VssRayContainer &sampleRays, 
     681                                                                                  const ObjectContainer &objects) 
    692682{ 
    693683        const long startTime = GetTime(); 
     
    696686         
    697687        // compute first candidate 
    698         SubdivisionCandidate *sc = 
    699                 mBvHierarchy->PrepareConstruction(sampleRays, objects); 
     688        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects); 
    700689 
    701690        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
     
    704693        cout << "finished bv hierarchy preparation in "  
    705694                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl; 
    706           
    707         return sc; 
    708 } 
    709  
    710  
    711 SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays, 
    712                                                                                                            const ObjectContainer &objects) 
     695} 
     696 
     697 
     698void HierarchyManager::PrepareOspTree(SplitQueue &tQueue, 
     699                                                                          const VssRayContainer &sampleRays, 
     700                                                                          const ObjectContainer &objects) 
    713701{ 
    714702        cout << "starting osp tree construction ... " << endl; 
     
    720708 
    721709        // compute first candidate 
    722         SubdivisionCandidate *osc = 
    723                 mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays); 
     710        mOspTree->PrepareConstruction(tQueue, sampleRays, objects, *objectSpaceRays); 
    724711 
    725712        mHierarchyStats.mTotalCost = mOspTree->mTotalCost; 
    726713        Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl; 
    727          
    728     return osc; 
    729714} 
    730715 
     
    919904                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl; 
    920905 
    921                         SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects); 
     906                        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects); 
    922907                         
    923908                        cout << "reseting queue ... "; 
    924909                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair); 
    925910                        cout << "finished" << endl; 
    926  
    927                         mTQueue.Push(ospSc); 
    928911                } 
    929912 
     
    937920                                 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl; 
    938921 
    939                         SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects); 
     922                        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects); 
    940923 
    941924                        cout << "reseting queue ... "; 
    942925                        ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair); 
    943926                        cout << "finished" << endl; 
    944  
    945                         // push view space candidate                     
    946                         mTQueue.Push(vspSc); 
    947927                } 
    948928 
     
    1014994 
    1015995 
    1016 SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,  
    1017                                                                                                                                         const ObjectContainer &objects) 
     996void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue, 
     997                                                                                                   const VssRayContainer &sampleRays,  
     998                                                                                                   const ObjectContainer &objects) 
    1018999{        
    10191000        SubdivisionCandidate *firstCandidate; 
     
    10341015                        mBvHierarchy->Initialise(objects); 
    10351016         
    1036                         firstCandidate = mBvHierarchy->Reset(sampleRays, objects); 
     1017                        mBvHierarchy->Reset(tQueue, sampleRays, objects); 
    10371018 
    10381019                        mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost; 
     
    10551036                // TODO 
    10561037        default: 
    1057                 firstCandidate = NULL; 
    10581038                break; 
    10591039        } 
    1060  
    1061         return firstCandidate; 
    1062 } 
    1063  
    1064  
    1065 SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,  
    1066                                                                                                                                   const ObjectContainer &objects, 
    1067                                                                                                                                   AxisAlignedBox3 *forcedViewSpace) 
     1040} 
     1041 
     1042 
     1043void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue, 
     1044                                                                                                 const VssRayContainer &sampleRays,  
     1045                                                                                                 const ObjectContainer &objects, 
     1046                                                                                                 AxisAlignedBox3 *forcedViewSpace) 
    10681047{ 
    10691048        ViewCellsManager *vm = mVspTree->mViewCellsManager; 
     
    10781057        mVspTree->Initialise(sampleRays, forcedViewSpace); 
    10791058         
     1059        ////////// 
    10801060        //-- reset stats 
    1081     mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1; 
    1082          
    1083         SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects); 
     1061    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes(); 
     1062                //-mVspTree->mVspStats.nodes + 1; 
     1063         
     1064        PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects); 
    10841065         
    10851066        mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries; 
    10861067        mHierarchyStats.mRenderCostDecrease = 0; 
    10871068 
    1088         mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte(); 
     1069        mHierarchyStats.mMemory =  
     1070                (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte(); 
    10891071 
    10901072        // evaluate new stats before first subdivsiion 
    10911073        EvalSubdivisionStats(); 
    1092  
    1093         return vsc; 
    10941074} 
    10951075 
     
    11191099        mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV; 
    11201100 
    1121         SubdivisionCandidate *osc =  
    1122                 PrepareObjectSpaceSubdivision(sampleRays, objects); 
    1123         mTQueue.Push(osc); 
     1101        PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects); 
    11241102 
    11251103        ////////////////////////// 
     
    11411119 
    11421120                // subdivide object space first 
    1143                 osc = ResetObjectSpaceSubdivision(sampleRays, objects); 
    1144                 mTQueue.Push(osc); 
     1121                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects); 
    11451122 
    11461123                // process object space candidates 
     
    11631140                // subdivide view space with respect to the objects 
    11641141 
    1165                 SubdivisionCandidate *vspVc =  
    1166                         ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace); 
    1167                 mTQueue.Push(vspVc); 
    1168  
     1142                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace); 
     1143                 
    11691144                // view space subdivision constructed 
    11701145                mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType; 
     
    12291204 
    12301205                // subdivide object space first 
    1231                 SubdivisionCandidate *ospVc =  
    1232                         ResetObjectSpaceSubdivision(sampleRays, objects); 
     1206                ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects); 
    12331207         
    12341208                // set the number of leaves 'evaluated' from the previous methods 
    12351209                // we go for the same numbers, but we try to optimize both subdivisions 
    12361210                mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves; 
    1237                 mTQueue.Push(ospVc); 
    12381211 
    12391212                // process object space candidates 
     
    12521225                // subdivide view space with respect to the objects 
    12531226 
    1254                 SubdivisionCandidate *vspVc =  
    1255                         ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace); 
     1227                ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace); 
    12561228 
    12571229                mVspTree->mMaxViewCells = maxViewSpaceLeaves; 
    1258                 mTQueue.Push(vspVc); 
    12591230 
    12601231                // process view space candidates 
     
    20462017                                                                                   const string &filename) 
    20472018{ 
     2019#if 0 
    20482020        VspTree *oldVspTree = mVspTree; 
    20492021        ViewCellsManager *vm = mVspTree->mViewCellsManager; 
     
    20752047         
    20762048        SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays); 
    2077         SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects); 
     2049        mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects); 
    20782050 
    20792051    firstVsp->mEvaluationHack = oldVspRoot; 
     
    20842056 
    20852057        tQueue.Push(firstVsp); 
    2086         tQueue.Push(firstBvh); 
    2087  
     2058         
    20882059        ExportStats(stats, tQueue, objects); 
    20892060 
     
    21142085                mBvHierarchy->AssociateObjectsWithLeaf(*bit); 
    21152086        } 
     2087#endif 
    21162088} 
    21172089 
  • GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h

    r1764 r1779  
    304304                first split candidates. 
    305305        */ 
    306         SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
    307                                                                                                                 const ObjectContainer &objects); 
     306        void PrepareObjectSpaceSubdivision(SplitQueue &tQueue, 
     307                                                                           const VssRayContainer &sampleRays, 
     308                                                                           const ObjectContainer &objects); 
    308309 
    309310 
     
    412413        /** Prepare bv hierarchy for subdivision 
    413414        */ 
    414         SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays, 
    415                                                                            const ObjectContainer &objects); 
     415        void PrepareBvHierarchy(SplitQueue &tQueue, 
     416                                                        const VssRayContainer &sampleRays, 
     417                                                        const ObjectContainer &objects); 
    416418 
    417419        /** Prepare object space kd tree for subdivision. 
    418420        */ 
    419         SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays, 
    420                                                                    const ObjectContainer &objects); 
     421        void PrepareOspTree(SplitQueue &tQueue, 
     422                                                const VssRayContainer &sampleRays, 
     423                                                const ObjectContainer &objects); 
    421424 
    422425        /** Prepare view space subdivision and add candidate to queue. 
    423426        */ 
    424         SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays, 
    425                                                                                                           const ObjectContainer &objects); 
     427        void PrepareViewSpaceSubdivision(SplitQueue &tQueue, 
     428                                                                         const VssRayContainer &sampleRays, 
     429                                                                         const ObjectContainer &objects); 
    426430 
    427431        /** Was object space subdivision already constructed? 
     
    488492                so construction can be restarted. 
    489493        */ 
    490         SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays,  
    491                                                                                                           const ObjectContainer &objects); 
    492  
    493         SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays,  
    494                                                                                                         const ObjectContainer &objects, 
    495                                                                                                         AxisAlignedBox3 *forcedViewSpace); 
     494        void ResetObjectSpaceSubdivision(SplitQueue &tQueue, 
     495                                                                         const VssRayContainer &rays,  
     496                                                                         const ObjectContainer &objects); 
     497 
     498        void ResetViewSpaceSubdivision(SplitQueue &tQueue, 
     499                                                                   const VssRayContainer &rays,  
     500                                                                   const ObjectContainer &objects, 
     501                                                                   AxisAlignedBox3 *forcedViewSpace); 
    496502 
    497503 
    498504        /////////////////////////// 
    499505 
    500         void ExportStats(ofstream &stats, SplitQueue &tQueue, const ObjectContainer &objects); 
     506        void ExportStats(ofstream &stats,  
     507                                         SplitQueue &tQueue,  
     508                                         const ObjectContainer &objects); 
    501509 
    502510        void CollectBestSet(const int maxSplits, 
  • GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.cpp

    r1740 r1779  
    23742374 
    23752375 
    2376 SubdivisionCandidate * OspTree::PrepareConstruction(const VssRayContainer &sampleRays, 
    2377                                                                                                         const ObjectContainer &objects, 
    2378                                                                                                         RayInfoContainer &rays) 
     2376void OspTree::PrepareConstruction(SplitQueue &tQueue, 
     2377                                                                  const VssRayContainer &sampleRays, 
     2378                                                                  const ObjectContainer &objects, 
     2379                                                                  RayInfoContainer &rays) 
    23792380{ 
    23802381        // store pointer to this tree 
     
    24212422        EvalSubdivisionStats(*oSubdivisionCandidate); 
    24222423 
    2423         return oSubdivisionCandidate; 
     2424        tQueue.Push(oSubdivisionCandidate); 
    24242425} 
    24252426 
  • GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.h

    r1758 r1779  
    740740 
    741741        void SubtractObjectContribution(KdLeaf *leaf, 
    742                                                                         Intersectable * obj, 
     742                                                                        Intersectable *obj, 
    743743                                                                        ViewCellContainer &touchedViewCells, 
    744744                                                                        float &renderCost); 
    745745 
    746         SubdivisionCandidate *PrepareConstruction(const VssRayContainer &sampleRays, 
    747                                                                                           const ObjectContainer &objects, 
    748                                                                                           RayInfoContainer &rays); 
     746        void PrepareConstruction(SplitQueue &tQueue, 
     747                                                         const VssRayContainer &sampleRays, 
     748                                                         const ObjectContainer &objects, 
     749                             RayInfoContainer &rays); 
    749750 
    750751 
  • GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp

    r1772 r1779  
    883883                samples.push_back(new VssRay(origin, termination, sourceObj, termObj)); 
    884884        } 
    885  
    886885#endif 
     886 
    887887        samplesIn.close(); 
    888888 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp

    r1772 r1779  
    28842884 
    28852885 
    2886 SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays, 
    2887                                                                                                    RayInfoContainer &rays) 
     2886void VspTree::PrepareConstruction(SplitQueue &tQueue, 
     2887                                                                  const VssRayContainer &sampleRays, 
     2888                                                                  RayInfoContainer &rays) 
    28882889{        
    28892890        mVspStats.Reset(); 
     
    29392940        EvalSubdivisionStats(*splitCandidate); 
    29402941 
    2941         return splitCandidate; 
     2942        tQueue.Push(splitCandidate); 
    29422943} 
    29432944 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h

    r1765 r1779  
    10101010        void EvalSubdivisionStats(const SubdivisionCandidate &tData); 
    10111011 
    1012         SubdivisionCandidate *PrepareConstruction( 
    1013                 const VssRayContainer &sampleRays, 
    1014                 RayInfoContainer &rays); 
     1012        void PrepareConstruction(SplitQueue &tQueue, 
     1013                                                         const VssRayContainer &sampleRays, 
     1014                                                         RayInfoContainer &rays); 
    10151015 
    10161016        /** Evaluates pvs contribution of this ray. 
Note: See TracChangeset for help on using the changeset viewer.