Changeset 1093 for GTP/trunk/Lib/Vis/Preprocessing

Timestamp:

07/07/06 01:55:19 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• VspOspTree.cpp (modified) (1 diff)
• VspOspTree.h (modified) (3 diffs)

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

@@ -3519 +3519 @@
 
 
-}
+void HierarchyManager::RepairQueue()
+{
+        // TODO
+        // for each update of the view space partition:
+        // the candidates from object space partition which
+        // have been afected by the view space split (the kd split candidates
+        // which saw the view cell which was split) must be reevaluated 
+        // (maybe not locally, just reinsert them into the queue)
+        //
+        // vice versa for the view cells
+        // for each update of the object space partition
+        // reevaluate split candidate for view cells which saw the split kd cell
+        // 
+        // the priority queue update can be solved by implementing a binary heap
+        // (explicit data structure, binary tree)
+        // *) inserting and removal is efficient
+        // *) search is not efficient => store pointer to queue element with each
+        // split candidate
+
+        vector<SplitCandidate *> candidates;
+
+        while (!mTQueue.empty())
+        {
+                SplitCandidate *candidate = mTQueue.top();
+                mTQueue.pop();
+
+                candidates.push_back(candidate);
+        }
+
+        // Reinsert
+
+}
+
+
+
+/********************************************************/
+/*             SplitHeap implementation                 */
+/********************************************************/
+
+
+SplitHeap::SplitHeap():mRoot(NULL)
+{}
+
+void SplitHeap::Push(SplitCandidate *candidate)
+{
+        InsertTail(candidate);
+
+        // Swap until heap constaints fullfilled
+        while (HeapViolated(candidate))
+        {
+                Swap(candidate, candidate->mParent);
+        }
+}
+
+
+void SplitHeap::InsertTail(SplitCandidate *candidate)
+{
+}
+
+
+bool SplitHeap::HeapViolated(SplitCandidate *candidate)
+{
+        return true;
+}
+        
+SplitCandidate *SplitHeap::Pop()
+{
+
+        return mRoot;
+}
+
+void SplitHeap::Remove(SplitCandidate *candidate)
+{
+}
+
+}

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

@@ -63 +63 @@
         float mPriority;
         
+        /// pointers used for building up heap
+        SplitCandidate *mParent;
+        SplitCandidate *mLeft;
+        SplitCandidate *mRight;
+
         SplitCandidate(): mPriority(0) 
         {};
@@ -1700 +1705 @@
         SplitCandidate *NextSplitCandidate();
 
-
+        void RepairQueue();
 
         AxisAlignedBox3 mBoundingBox;
@@ -1715 +1720 @@
 };
 
+/** Implements a heap for split candidates.
+*/
+class SplitHeap
+{
+        SplitHeap();
+
+        void Push(SplitCandidate *candidate);
+    
+        SplitCandidate *Pop();
+
+        void Remove(SplitCandidate *candidate);
+
+        void InsertTail(SplitCandidate *candidate);
+    
+        bool HeapViolated(SplitCandidate *candidate);
+
+        SplitCandidate *mRoot;
+};
+
 }
 
-
 #endif