Ignore:
Timestamp:
07/07/06 16:14:33 (18 years ago)
Author:
mattausch
Message:
 
Location:
GTP/trunk/Lib/Vis/Preprocessing/src
Files:
1 added
2 edited
2 moved

Legend:

Unmodified
Added
Removed

  • GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.cpp

    r1097 r1099  
    1 /************************************************************************ 
    2  
    3   Heap data structure 
    4  
    5   Copyright (C) 1998 Michael Garland.  See "COPYING.txt" for details. 
    6    
    7   $Id: MxHeap.cxx,v 1.1 2002/09/24 16:53:54 wimmer Exp $ 
    8  
    9  ************************************************************************/ 
    10  
    11 //#include "stdmix.h" 
    12 #include "MxHeap.h" 
     1#include "MyHeap.h" 
    132 
    143 
    15 //////////////////////////////////////////////////////////////////////// 
    16 // 
    17 // Internal functions for manipulating the heap 
     4namespace GtpVisibilityPreprocessor { 
    185 
    19 inline void MxHeap::place(MxHeapable *x, unsigned int i) 
     6 
     7/*****************************************************************************/ 
     8/*                         MyHeap implementation                             * 
     9/*****************************************************************************/ 
     10 
     11 
     12 
     13inline void MyHeap::Place(Heapable *x, unsigned int i) 
    2014{ 
    21     ref(i) = x; 
    22     x->set_heap_pos(i); 
     15    mBuffer[i] = x; 
     16    x->SetHeapPos(i); 
    2317} 
    2418 
    25 void MxHeap::swap(unsigned int i, unsigned int j) 
     19 
     20void MyHeap::Swap(unsigned int i, unsigned int j) 
    2621{ 
    27     MxHeapable *tmp = ref(i); 
     22    Heapable *tmp = mBuffer[i]; 
    2823 
    29     place(ref(j), i); 
    30     place(tmp, j); 
     24    Place(mBuffer[j], i); 
     25    Place(tmp, j); 
    3126} 
    3227 
    33 void MxHeap::upheap(unsigned int i) 
     28 
     29void MyHeap::UpHeap(unsigned int i) 
    3430{ 
    35     MxHeapable *moving = ref(i); 
    36     uint index = i; 
    37     uint p = parent(i); 
     31    Heapable *moving = mBuffer[i]; 
     32    unsigned int index = i; 
     33    unsigned int p = Parent(i); 
    3834 
    39     while( index>0 && moving->heap_key() > ref(p)->heap_key() ) 
     35    while ((index > 0) && (moving->SetPriority() > mBuffer[p]->SetPriority())) 
    4036    { 
    41         place(ref(p), index); 
    42         index = p; 
    43         p = parent(p); 
     37                Place(mBuffer[p], index); 
     38                index = p; 
     39                p = Parent(p); 
    4440    } 
    4541 
    46     if( index != i ) 
    47         place(moving, index); 
     42    if (index != i) 
     43        { 
     44                Place(moving, index); 
     45        } 
    4846} 
    4947 
    50 void MxHeap::downheap(unsigned int i) 
     48 
     49void MyHeap::DownHeap(unsigned int i) 
    5150{ 
    52     MxHeapable *moving = ref(i); 
    53     uint index = i; 
    54     uint l = left(i); 
    55     uint r = right(i); 
    56     uint largest; 
     51    Heapable *moving = mBuffer[i]; 
    5752 
    58     while( l<length() ) 
    59     { 
    60         if( r<length() && ref(l)->heap_key() < ref(r)->heap_key() ) 
    61             largest = r; 
    62         else  
    63             largest = l; 
     53    unsigned int index = i; 
     54    unsigned int l = Left(i); 
     55    unsigned int r = Right(i); 
     56    unsigned int largest; 
    6457 
    65         if( moving->heap_key() < ref(largest)->heap_key() ) 
     58        while (l < (int)mBuffer.size()) 
    6659        { 
    67             place(ref(largest), index); 
    68             index = largest; 
    69             l = left(index); 
    70             r = right(index); 
     60                if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->SetPriority() < mBuffer[r]->SetPriority())) 
     61                        largest = r; 
     62                else  
     63                        largest = l; 
     64 
     65                if (moving->SetPriority() < mBuffer[largest]->SetPriority()) 
     66                { 
     67                        Place(mBuffer[largest], index); 
     68                        index = largest; 
     69                        l = Left(index); 
     70                        r = Right(index); 
     71                } 
     72                else 
     73                { 
     74                        break; 
     75                } 
    7176        } 
    72         else 
    73             break; 
    74     } 
    7577 
    76     if( index != i ) 
    77         place(moving, index); 
     78    if (index != i) 
     79        { 
     80                Place(moving, index); 
     81        } 
    7882} 
    7983 
    80 //////////////////////////////////////////////////////////////////////// 
    81 // 
    82 // Exported interface to the heap 
    83 // 
    8484 
    85 void MxHeap::insert(MxHeapable *t, float v) 
     85void MyHeap::Push(Heapable *t, float v) 
    8686{ 
    87     t->heap_key(v); 
     87    t->SetPriority(v); 
    8888 
    89     unsigned int i = add(t); 
    90     t->set_heap_pos(i); 
     89        unsigned int i = (unsigned int)mBuffer.size(); 
    9190 
    92     upheap(i); 
     91        t->SetHeapPos(i); 
     92        mBuffer.push_back(t); 
     93     
     94    UpHeap(i); 
    9395} 
    9496 
    95 void MxHeap::update(MxHeapable *t, float v) 
     97 
     98bool MyHeap::Update(Heapable *t, float v) 
    9699{ 
    97     SanityCheck( t->is_in_heap() ); 
    98     t->heap_key(v); 
     100    if (t->IsInHeap()) 
     101                return false; 
    99102 
    100     unsigned int i = t->get_heap_pos(); 
     103    t->SetPriority(v); 
    101104 
    102     if( i>0 && v>ref(parent(i))->heap_key() ) 
    103         upheap(i); 
     105    unsigned int i = t->GetHeapPos(); 
     106 
     107    if ((i > 0) && (v > mBuffer[Parent(i)]->SetPriority())) 
     108                UpHeap(i); 
    104109    else 
    105         downheap(i); 
     110                DownHeap(i); 
     111 
     112        return true; 
    106113} 
    107114 
    108 MxHeapable *MxHeap::extract() 
     115 
     116Heapable *MyHeap::Pop() 
    109117{ 
    110     if( length() < 1 ) return NULL; 
     118    if (mBuffer.empty())  
     119                return NULL; 
    111120 
    112     swap(0, length()-1); 
    113     MxHeapable *dead=drop(); 
     121    Swap(0, mBuffer.size() - 1); 
     122     
     123        Heapable *dead = mBuffer.back(); 
     124        mBuffer.pop_back(); 
    114125 
    115     downheap(0); 
    116     dead->not_in_heap(); 
     126    DownHeap(0); 
     127    dead->NotInHeap(); 
     128 
    117129    return dead; 
    118130} 
    119131 
    120 MxHeapable *MxHeap::remove(MxHeapable *t) 
     132 
     133Heapable *MyHeap::Erase(Heapable *t) 
    121134{ 
    122     if( !t->is_in_heap() ) return NULL; 
     135    if (!t->IsInHeap())  
     136                return NULL; 
    123137 
    124     int i = t->get_heap_pos(); 
    125     swap(i, length()-1); 
    126     drop(); 
    127     t->not_in_heap(); 
     138    int i = t->GetHeapPos(); 
    128139 
    129     if( ref(i)->heap_key() < t->heap_key() ) 
    130         downheap(i); 
    131     else 
    132         upheap(i); 
     140    Swap(i, mBuffer.size() - 1); 
     141 
     142        mBuffer.pop_back(); 
     143    t->NotInHeap(); 
     144 
     145    if (mBuffer[i]->SetPriority() < t->SetPriority()) 
     146                DownHeap(i); 
     147        else 
     148                UpHeap(i); 
    133149 
    134150    return t; 
    135151} 
     152} 

  • GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.h

    r1097 r1099  
    1 #ifndef MXHEAP_INCLUDED // -*- C++ -*- 
    2 #define MXHEAP_INCLUDED 
    3 #if !defined(__GNUC__) 
    4 #  pragma once 
    5 #endif 
     1#ifndef MYHEAP_H 
     2#define MYHEAP_H 
    63 
    7 /************************************************************************ 
     4#include <vector> 
    85 
    9   Heap 
     6/** This class implementas a heap  for 
     7        use as a priority queue. 
    108 
    11   Copyright (C) 1998 Michael Garland.  See "COPYING.txt" for details. 
    12    
    13   $Id: MxHeap.h,v 1.1 2002/09/24 16:53:54 wimmer Exp $ 
     9        The class aditionally implements efficient remove 
     10        of arbitrary elements. 
     11*/ 
    1412 
    15  ************************************************************************/ 
     13namespace GtpVisibilityPreprocessor { 
    1614 
    17 //#include "MxDynBlock.h" 
    18 typedef unsigned int uint; 
     15const static int NOT_IN_HEAP = -100; 
    1916 
    20 class MxHeapable 
     17class Heapable 
    2118{ 
    22 private: 
    23     float import; 
    24     int token; 
     19public: 
     20    Heapable() { NotInHeap(); HeapKey(0.0f); } 
    2521 
    26 public: 
    27     MxHeapable() { not_in_heap(); heap_key(0.0f); } 
     22    inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; } 
     23    inline void NotInHeap() { mPosition = NOT_IN_HEAP; } 
     24    inline int GetHeapPos() { return mPosition; } 
     25    inline void SetHeapPos(int t) { mPosition = t; } 
    2826 
    29     inline bool is_in_heap() { return token != -47; } 
    30     inline void not_in_heap() { token = -47; } 
    31     inline int get_heap_pos() { return token; } 
    32     inline void set_heap_pos(int t) { token=t; } 
     27    inline void  HeapKey(float k) { mPriority = k; } 
     28    inline float HeapKey() const  { return mPriority; } 
    3329 
    34     inline void  heap_key(float k) { import=k; } 
    35     inline float heap_key() const  { return import; } 
     30protected: 
     31 
     32    float mPriority; 
     33    int mPosition; 
    3634}; 
    3735 
    3836 
    39 class MxHeap// : private MxDynBlock<MxHeapable *> 
     37class MyHeap 
    4038{ 
    41 private: 
    42     void place(MxHeapable *x, unsigned int i); 
    43     void swap(unsigned int i, unsigned int j); 
     39public: 
     40    MyHeap() { } 
     41    MyHeap(unsigned int n) : mBuffer(n) { } 
    4442 
    45     unsigned int parent(unsigned int i) { return (i-1)/2; } 
    46     unsigned int left(unsigned int i) { return 2*i+1; } 
    47     unsigned int right(unsigned int i) { return 2*i+2; } 
     43    void Push(Heapable *t) { Push(t, t->HeapKey()); } 
     44    void Push(Heapable *, float); 
     45    bool Update(Heapable *t) { return Update(t, t->HeapKey()); } 
     46    bool Update(Heapable *, float); 
    4847 
    49     void upheap(unsigned int i); 
    50     void downheap(unsigned int i); 
     48    unsigned int Size() const { return (unsigned int)mBuffer.size(); } 
     49        bool Empty() const {return mBuffer.empty(); } 
     50    Heapable       *Item(unsigned int i)       { return mBuffer[i]; } 
     51    const Heapable *Item(unsigned int i) const { return mBuffer[i]; } 
     52    Heapable *Pop(); 
     53        Heapable *Top() { return (mBuffer.empty() ? (Heapable *)NULL : mBuffer.front()); } 
     54    Heapable *Erase(Heapable *); 
    5155 
    52 public: 
    53     MxHeap()/* : MxDynBlock<MxHeapable *>(8)*/ { } 
    54    // MxHeap(unsigned int n) : MxDynBlock<MxHeapable *>(n) { } 
     56protected: 
    5557 
    56     void insert(MxHeapable *t) { insert(t, t->heap_key()); } 
    57     void insert(MxHeapable *, float); 
    58     void update(MxHeapable *t) { update(t, t->heap_key()); } 
    59     void update(MxHeapable *, float); 
     58    void Place(Heapable *x, unsigned int i); 
     59    void Swap(unsigned int i, unsigned int j); 
    6060 
    61     unsigned int size() const { return length(); } 
    62     MxHeapable       *item(uint i)       { return ref(i); } 
    63     const MxHeapable *item(uint i) const { return ref(i); } 
    64     MxHeapable *extract(); 
    65     MxHeapable *top() { return (length()<1 ? (MxHeapable *)NULL : raw(0)); } 
    66     MxHeapable *remove(MxHeapable *); 
     61    unsigned int Parent(unsigned int i) { return (i-1)/2; } 
     62    unsigned int Left(unsigned int i) { return 2*i+1; } 
     63    unsigned int Right(unsigned int i) { return 2*i+2; } 
     64 
     65    void UpHeap(unsigned int i); 
     66    void DownHeap(unsigned int i); 
     67 
     68        std::vector<Heapable* > mBuffer; 
    6769}; 
    6870 
    69 // MXHEAP_INCLUDED 
     71} 
     72 
     73// MYHEAP_H 
    7074#endif 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

    r1097 r1099  
    3030int VspTree::sFrontAndBackId = 0; 
    3131 
    32  
     32VspTree *VspTree::VspSplitCandidate::sVspTree = NULL; 
     33OspTree *OspTree::OspSplitCandidate::sOspTree = NULL; 
    3334 
    3435// pvs penalty can be different from pvs size 
    … …  
    442443                                                                  AxisAlignedBox3 *forcedBoundingBox)  
    443444{ 
     445        // store pointer to this tree 
     446        VspSplitCandidate::sVspTree = this; 
     447 
    444448        mVspStats.nodes = 1; 
    445449         
    … …  
    574578         
    575579                //-- push the new split candidates on the queue 
    576                 VspSplitCandidate *frontCandidate = new VspSplitCandidate(); 
    577                 VspSplitCandidate *backCandidate = new VspSplitCandidate(); 
    578  
    579                 EvalSplitCandidate(tFrontData, *frontCandidate); 
    580                 EvalSplitCandidate(tBackData, *backCandidate); 
    581  
    582                 tQueue.push(frontCandidate); 
    583                 tQueue.push(backCandidate); 
     580                VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData); 
     581                VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData); 
     582 
     583                EvalSplitCandidate(*frontCandidate); 
     584                EvalSplitCandidate(*backCandidate); 
     585 
     586                tQueue.Push(frontCandidate); 
     587                tQueue.Push(backCandidate); 
    584588 
    585589                // delete old leaf node 
    … …  
    634638 
    635639 
    636 void VspTree::EvalSplitCandidate(VspTraversalData &tData, 
    637                                                                  VspSplitCandidate &splitCandidate) 
     640void VspTree::EvalSplitCandidate(VspSplitCandidate &splitCandidate) 
    638641{ 
    639642        float frontProb; 
    640643        float backProb; 
    641644         
    642         VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode); 
     645        VspLeaf *leaf = dynamic_cast<VspLeaf *>(splitCandidate.mParentData.mNode); 
    643646         
    644647        // compute locally best split plane 
    645648        const bool success =  
    646                 SelectSplitPlane(tData, splitCandidate.mSplitPlane,     frontProb, backProb); 
     649                SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb); 
    647650 
    648651        // compute global decrease in render cost 
    649         splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData); 
    650         splitCandidate.mParentData = tData; 
    651         splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 
     652        const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData); 
     653        splitCandidate.SetPriority(priority); 
     654        splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1; 
    652655 
    653656        //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl; 
    … …  
    25392542 
    25402543OspTree::OspTree(): 
    2541 mRoot(NULL) 
    2542 #if TODO 
    2543 mOutOfBoundsCell(NULL), 
    2544 mStoreRays(false), 
    2545 mUseRandomAxis(false), 
     2544mRoot(NULL), 
    25462545mTimeStamp(1) 
    2547 #endif 
    25482546{ 
    25492547#if TODO 
    … …  
    27512749                         
    27522750                //-- push the new split candidates on the queue 
    2753                 OspSplitCandidate *frontCandidate = new OspSplitCandidate(); 
    2754                 OspSplitCandidate *backCandidate = new OspSplitCandidate(); 
    2755  
    2756                 EvalSplitCandidate(tFrontData, *frontCandidate); 
    2757                 EvalSplitCandidate(tBackData, *backCandidate); 
    2758  
    2759                 tQueue.push(frontCandidate); 
    2760                 tQueue.push(backCandidate); 
     2751                OspSplitCandidate *frontCandidate = new OspSplitCandidate(tFrontData); 
     2752                OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData); 
     2753 
     2754                EvalSplitCandidate(*frontCandidate); 
     2755                EvalSplitCandidate(*backCandidate); 
     2756 
     2757                tQueue.Push(frontCandidate); 
     2758                tQueue.Push(backCandidate); 
    27612759 
    27622760                // delete old leaf node 
    … …  
    27792777 
    27802778 
    2781 void OspTree::EvalSplitCandidate(OspTraversalData &tData, 
    2782                                                                  OspSplitCandidate &splitCandidate) 
     2779void OspTree::EvalSplitCandidate(OspSplitCandidate &splitCandidate) 
    27832780{ 
    27842781        float frontProb; 
    27852782        float backProb; 
    27862783         
    2787         KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode); 
     2784        KdLeaf *leaf = dynamic_cast<KdLeaf *>(splitCandidate.mParentData.mNode); 
    27882785 
    27892786        // compute locally best split plane 
    27902787        const bool success =  
    2791                 SelectSplitPlane(tData, splitCandidate.mSplitPlane,     frontProb, backProb); 
     2788                SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb); 
    27922789 
    27932790        //TODO 
    27942791        // compute global decrease in render cost 
    2795         splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData); 
    2796         splitCandidate.mParentData = tData; 
    2797         splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 
     2792        splitCandidate.SetPriority(EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData)); 
     2793        splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1; 
    27982794} 
    27992795 
    … …  
    32633259                                                                  AxisAlignedBox3 *forcedBoundingBox)  
    32643260{ 
     3261        // store pointer to this tree 
     3262        OspSplitCandidate::sOspTree = this; 
     3263 
    32653264        mOspStats.nodes = 1; 
    32663265         
    … …  
    33313330SplitCandidate *HierarchyManager::NextSplitCandidate() 
    33323331{ 
    3333         SplitCandidate *splitCandidate = mTQueue.top(); 
     3332        SplitCandidate *splitCandidate = static_cast<SplitCandidate *>(mTQueue.Top()); 
    33343333        //Debug << "priority: " << splitCandidate->GetPriority() << endl; 
    3335         mTQueue.pop(); 
     3334        mTQueue.Pop(); 
    33363335 
    33373336        return splitCandidate; 
    … …  
    33983397 
    33993398        // compute first split candidate 
    3400         VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate(); 
    3401     mVspTree.EvalSplitCandidate(vData, *splitCandidate); 
    3402  
    3403         mTQueue.push(splitCandidate); 
     3399        VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate(vData); 
     3400    mVspTree.EvalSplitCandidate(*splitCandidate); 
     3401 
     3402        mTQueue.Push(splitCandidate); 
    34043403 
    34053404 
    … …  
    34273426 
    34283427        // compute first split candidate 
    3429         OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate(); 
    3430     mOspTree.EvalSplitCandidate(oData, *oSplitCandidate); 
    3431  
    3432         mTQueue.push(splitCandidate); 
     3428        OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate(oData); 
     3429    mOspTree.EvalSplitCandidate(*oSplitCandidate); 
     3430 
     3431        mTQueue.Push(splitCandidate); 
    34333432} 
    34343433 
    … …  
    34883487 
    34893488                //-- subdivide leaf node 
    3490                 //-- either a object space or view space split 
     3489                //-- we have either a object space or view space split 
    34913490                if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE) 
    34923491                { 
    … …  
    35153514bool HierarchyManager::FinishedConstruction() 
    35163515{ 
    3517         return mTQueue.empty(); 
    3518 } 
    3519  
    3520  
    3521 void HierarchyManager::RepairQueue() 
     3516        return mTQueue.Empty(); 
     3517} 
     3518 
     3519 
     3520void HierarchyManager::RepairQueue(const vector<SplitCandidate *> &dirtyList) 
    35223521{ 
    35233522        // TODO 
    … …  
    35353534        // (explicit data structure, binary tree) 
    35363535        // *) inserting and removal is efficient 
    3537         // *) search is not efficient => store pointer to queue element with each 
     3536        // *) search is not efficient => store queue position with each 
    35383537        // split candidate 
    35393538 
    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 } 
     3539        vector<SplitCandidate *>::const_iterator sit, sit_end = dirtyList.end(); 
     3540 
     3541        for (sit = dirtyList.begin(); sit != sit_end; ++ sit) 
     3542        { 
     3543                SplitCandidate* sc = *sit; 
     3544 
     3545                mTQueue.Erase(sc); 
     3546 
     3547                // reevaluate 
     3548                sc->EvalPriority(); 
     3549 
     3550                // reinsert 
     3551                mTQueue.Push(sc); 
     3552        } 
     3553} 
     3554 
     3555} 

  • GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

    r1097 r1099  
    1010#include "RayInfo.h" 
    1111#include "gzstream.h" 
    12 #include "mixkit/MxHeap.h" 
     12#include "FlexibleHeap.h" 
    1313 
    1414 
    … …  
    4848/** Candidate for a view space / object space split. 
    4949*/ 
    50 class SplitCandidate: public MxHeapable 
     50class SplitCandidate: public Heapable 
    5151{   
    5252public: 
    … …  
    6262 
    6363        /// priority of this split 
    64         float mPriority; 
    65          
    66         /// pointers used for building up heap 
    67         SplitCandidate *mParent; 
    68         SplitCandidate *mLeft; 
    69         SplitCandidate *mRight; 
    70  
    71         SplitCandidate(): mPriority(0)  
     64        //float mPriority; 
     65         
     66        SplitCandidate() 
    7267        {}; 
    7368 
    … …  
    7570        {} 
    7671 
     72        virtual void EvalPriority() = 0; 
    7773        virtual int Type() const = 0; 
    78  
    79         /** Returns cost of the traversal data. 
    80         */ 
    81         float GetPriority() const 
    82         { 
    83                 return mPriority; 
    84         } 
    85  
    86         /*friend bool operator<(const SplitCandidate &a, const SplitCandidate &b) 
    87         { 
    88                 return a.GetPriority() < b.GetPriority(); 
    89         }*/ 
    9074}; 
    9175 
    … …  
    462446 
    463447 
     448#if 0 
    464449typedef std::priority_queue<SplitCandidate *,  
    465450                                                        std::vector<SplitCandidate *>,  
    466451                                                        GtPriority<std::vector<SplitCandidate *>::value_type> > SplitQueue; 
    467  
    468 #if TODO 
    469 /** candidate for a view space split 
    470 */ 
    471 class OspSplitCandidate: public SplitCandidate 
    472 {   
    473         /// parent data 
    474         OspTraversalData mParentData; 
    475                  
    476         VspOspSplitCandidate(): mRenderCost(0)  
    477         {}; 
    478  
    479         int Type() const { return OSP_CANDIDATE; }  
    480  
    481         VspOspSplitCandidate(const AxisAlignedPlane &plane, const VspOspTraversalData &tData):  
    482         mSplitPlane(plane), mParentData(tData), mRenderCost(0) 
    483         {} 
    484 }; 
    485452#endif 
     453 
     454typedef FlexibleHeap<SplitCandidate *> SplitQueue; 
    486455 
    487456/** View Space Partitioning tree. 
    … …  
    588557        {   
    589558        public: 
     559                static VspTree* sVspTree; 
    590560                /// parent data 
    591561                VspTraversalData mParentData; 
    592562                 
    593                 VspSplitCandidate() 
     563                VspSplitCandidate(const VspTraversalData &tData): mParentData(tData) 
    594564                {}; 
    595565 
    596566                int Type() const { return VIEW_SPACE; } 
     567 
     568                void EvalPriority() 
     569                { 
     570                        sVspTree->EvalSplitCandidate(*this);     
     571                } 
    597572 
    598573                VspSplitCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):  
    … …  
    796771        /** Evaluates candidate for splitting. 
    797772        */ 
    798         void EvalSplitCandidate(VspTraversalData &tData, VspSplitCandidate &splitData); 
     773        void EvalSplitCandidate(VspSplitCandidate &splitData); 
    799774 
    800775        /** Evaluates render cost decrease of next split. 
    … …  
    12061181        {   
    12071182        public: 
     1183                static OspTree* sOspTree; 
     1184 
    12081185                /// parent data 
    12091186                OspTraversalData mParentData; 
    12101187                 
    1211                 OspSplitCandidate() 
     1188                OspSplitCandidate(const OspTraversalData &tData): mParentData(tData) 
    12121189                {}; 
    12131190 
    12141191                int Type() const { return VIEW_SPACE; } 
     1192         
     1193                void EvalPriority() 
     1194                { 
     1195                        sOspTree->EvalSplitCandidate(*this);     
     1196                } 
    12151197 
    12161198                OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData):  
    … …  
    13761358        /** Evaluates candidate for splitting. 
    13771359        */ 
    1378         void EvalSplitCandidate(OspTraversalData &tData, OspSplitCandidate &splitData); 
     1360        void EvalSplitCandidate(OspSplitCandidate &splitData); 
    13791361 
    13801362        /** Computes priority of the traversal data and stores it in tData. 
    … …  
    17061688        SplitCandidate *NextSplitCandidate(); 
    17071689 
    1708         void RepairQueue(); 
     1690        void RepairQueue(const vector<SplitCandidate *> &dirtyList); 
    17091691 
    17101692        AxisAlignedBox3 mBoundingBox; 
Note: See TracChangeset for help on using the changeset viewer.