Changeset 1093 for GTP/trunk


Ignore:
Timestamp:
07/07/06 01:55:19 (18 years ago)
Author:
mattausch
Message:
 
Location:
GTP/trunk/Lib/Vis/Preprocessing/src
Files:
2 edited

Legend:

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

    r1089 r1093  
    35193519 
    35203520 
    3521 } 
     3521void HierarchyManager::RepairQueue() 
     3522{ 
     3523        // TODO 
     3524        // for each update of the view space partition: 
     3525        // the candidates from object space partition which 
     3526        // have been afected by the view space split (the kd split candidates 
     3527        // which saw the view cell which was split) must be reevaluated  
     3528        // (maybe not locally, just reinsert them into the queue) 
     3529        // 
     3530        // vice versa for the view cells 
     3531        // for each update of the object space partition 
     3532        // reevaluate split candidate for view cells which saw the split kd cell 
     3533        //  
     3534        // the priority queue update can be solved by implementing a binary heap 
     3535        // (explicit data structure, binary tree) 
     3536        // *) inserting and removal is efficient 
     3537        // *) search is not efficient => store pointer to queue element with each 
     3538        // split candidate 
     3539 
     3540        vector<SplitCandidate *> candidates; 
     3541 
     3542        while (!mTQueue.empty()) 
     3543        { 
     3544                SplitCandidate *candidate = mTQueue.top(); 
     3545                mTQueue.pop(); 
     3546 
     3547                candidates.push_back(candidate); 
     3548        } 
     3549 
     3550        // Reinsert 
     3551 
     3552} 
     3553 
     3554 
     3555 
     3556/********************************************************/ 
     3557/*             SplitHeap implementation                 */ 
     3558/********************************************************/ 
     3559 
     3560 
     3561SplitHeap::SplitHeap():mRoot(NULL) 
     3562{} 
     3563 
     3564void SplitHeap::Push(SplitCandidate *candidate) 
     3565{ 
     3566        InsertTail(candidate); 
     3567 
     3568        // Swap until heap constaints fullfilled 
     3569        while (HeapViolated(candidate)) 
     3570        { 
     3571                Swap(candidate, candidate->mParent); 
     3572        } 
     3573} 
     3574 
     3575 
     3576void SplitHeap::InsertTail(SplitCandidate *candidate) 
     3577{ 
     3578} 
     3579 
     3580 
     3581bool SplitHeap::HeapViolated(SplitCandidate *candidate) 
     3582{ 
     3583        return true; 
     3584} 
     3585         
     3586SplitCandidate *SplitHeap::Pop() 
     3587{ 
     3588 
     3589        return mRoot; 
     3590} 
     3591 
     3592void SplitHeap::Remove(SplitCandidate *candidate) 
     3593{ 
     3594} 
     3595 
     3596} 
  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

    r1089 r1093  
    6363        float mPriority; 
    6464         
     65        /// pointers used for building up heap 
     66        SplitCandidate *mParent; 
     67        SplitCandidate *mLeft; 
     68        SplitCandidate *mRight; 
     69 
    6570        SplitCandidate(): mPriority(0)  
    6671        {}; 
     
    17001705        SplitCandidate *NextSplitCandidate(); 
    17011706 
    1702  
     1707        void RepairQueue(); 
    17031708 
    17041709        AxisAlignedBox3 mBoundingBox; 
     
    17151720}; 
    17161721 
     1722/** Implements a heap for split candidates. 
     1723*/ 
     1724class SplitHeap 
     1725{ 
     1726        SplitHeap(); 
     1727 
     1728        void Push(SplitCandidate *candidate); 
     1729     
     1730        SplitCandidate *Pop(); 
     1731 
     1732        void Remove(SplitCandidate *candidate); 
     1733 
     1734        void InsertTail(SplitCandidate *candidate); 
     1735     
     1736        bool HeapViolated(SplitCandidate *candidate); 
     1737 
     1738        SplitCandidate *mRoot; 
     1739}; 
     1740 
    17171741} 
    17181742 
    1719  
    17201743#endif 
Note: See TracChangeset for help on using the changeset viewer.