source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp @ 1237

Revision 1237, 10.4 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "HierarchyManager.h"
8#include "Mesh.h"
9#include "common.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellsManager.h"
17#include "Beam.h"
18#include "KdTree.h"
19#include "KdIntersectable.h"
20#include "VspTree.h"
21#include "OspTree.h"
22
23
24namespace GtpVisibilityPreprocessor {
25
26
27#define USE_FIXEDPOINT_T 0
28
29
30/*******************************************************************/
31/*              class HierarchyManager implementation              */
32/*******************************************************************/
33
34
35HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
36mVspTree(vspTree), mOspTree(ospTree)
37{
38        // cross references
39        mVspTree.mOspTree = &ospTree;
40        mOspTree.mVspTree = &vspTree;
41
42        char subdivisionStatsLog[100];
43        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
44                subdivisionStatsLog);
45        mSubdivisionStats.open(subdivisionStatsLog);
46}
47
48
49SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
50{
51        SubdivisionCandidate *splitCandidate = mTQueue.Top();
52        mTQueue.Pop();
53
54        return splitCandidate;
55}
56
57
58void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
59                                                                                   const ObjectContainer &objects,
60                                                                                   AxisAlignedBox3 *forcedViewSpace,
61                                                                                   RayInfoContainer &viewSpaceRays,
62                                                                                   RayInfoContainer &objectSpaceRays)
63{
64        SubdivisionCandidate *vsc =
65                mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
66        mTQueue.Push(vsc);
67
68        SubdivisionCandidate *osc =
69                mOspTree.PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);
70
71        mTQueue.Push(osc);
72}
73
74
75void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
76{
77        const float costDecr = tData.GetRenderCostDecrease();
78
79        //mTotalCost -= costDecr;
80        // mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
81
82        AddSubdivisionStats(mOspTree.mOspStats.Leaves() + mVspTree.mVspStats.Leaves(),
83                                                costDecr,
84                                                mTotalCost
85                                                );
86}
87
88
89void HierarchyManager::AddSubdivisionStats(const int splits,
90                                                                                   const float renderCostDecr,
91                                                                                   const float totalRenderCost)
92{
93        mSubdivisionStats
94                        << "#Splits\n" << splits << endl
95                        << "#RenderCostDecrease\n" << renderCostDecr << endl
96                        << "#TotalRenderCost\n" << totalRenderCost << endl;
97                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
98}
99
100
101bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
102{
103        // TODO matt: make virtual by creating superclasss for traveral data
104        return candidate->GlobalTerminationCriteriaMet();
105}
106
107
108void HierarchyManager::Construct(const VssRayContainer &sampleRays,
109                                                                 const ObjectContainer &objects,
110                                                                 AxisAlignedBox3 *forcedViewSpace)
111{
112        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
113        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
114
115        // prepare vsp and osp trees for traversal
116        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
117
118        mVspTree.mVspStats.Reset();
119        mVspTree.mVspStats.Start();
120
121        cout << "Constructing view space / object space tree ... \n";
122        const long startTime = GetTime();       
123       
124        RunConstruction(true);
125
126        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
127
128        mVspTree.mVspStats.Stop();
129}
130
131
132bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
133{
134        const bool globalTerminationCriteriaMet =
135                        GlobalTerminationCriteriaMet(sc);
136
137        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
138
139        if (vspSplit)
140        {
141                VspNode *n = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
142        }
143        else
144        {
145                KdNode *n = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
146        }
147       
148        return !globalTerminationCriteriaMet;
149}
150
151
152void HierarchyManager::RunConstruction(const bool repair)
153{
154        int numNodes = 0;
155
156        while (!FinishedConstruction())
157        {
158                SubdivisionCandidate *splitCandidate = NextSubdivisionCandidate();
159           
160                mTotalCost -= splitCandidate->GetRenderCostDecrease();
161
162                // cost ratio of cost decrease / totalCost
163                const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
164
165                if (costRatio < mTermMinGlobalCostRatio)
166                        ++ mGlobalCostMisses;
167       
168                /*Debug << "\n**********" << endl
169                          << "total cost: " << mTotalCost << " render cost decr: "
170                          << splitCandidate->GetRenderCostDecrease()
171                          << " cost ratio: " << costRatio << endl << endl;*/
172
173                //-- subdivide leaf node
174
175                if (SubdivideSubdivisionCandidate(splitCandidate))
176                {
177                        // subdivision successful
178                        EvalSubdivisionStats(*splitCandidate);
179               
180                        // reevaluate candidates affected by the split
181                        // for view space splits, this would be object space splits
182                        // and other way round
183                        if (repair)
184                                RepairQueue();
185
186                        cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
187                }
188
189                DEL_PTR(splitCandidate);
190        }
191}
192
193
194void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
195                                                                  const ObjectContainer &objects,
196                                                                  AxisAlignedBox3 *forcedViewSpace)
197{
198        // rays clipped in view space and in object space
199        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
200        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
201
202
203        /////////////////////////////////////////////////////////////
204        // view space space partition
205        /////////////////////////////////////////////////////////////
206
207#if 0
208        // makes no sense otherwise because only one kd cell available
209        // during view space partition
210        const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
211        const bool savedStoreMethod = mVspTree.mStoreKdPvs;
212       
213        mVspTree.mUseKdPvsForHeuristics = false;
214        mVspTree.mStoreKdPvs = false;
215#endif
216
217        SubdivisionCandidate *vsc =
218                mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
219
220        // add to queue
221        mTQueue.Push(vsc);
222
223        long startTime = GetTime();
224        cout << "starting vsp contruction ... " << endl;
225
226        mVspTree.mVspStats.Reset();
227        mVspTree.mVspStats.Start();
228
229        int i = 0;
230
231        // all objects can be seen from everywhere
232        mTotalCost = (float)dynamic_cast<VspTree::VspSubdivisionCandidate *>(vsc)->mParentData.mPvs;
233
234        const bool repairQueue = false;
235
236        // process view space candidates
237        RunConstruction(repairQueue);
238
239        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
240        mVspTree.mVspStats.Stop();
241       
242
243
244        /////////////////////////////////////////////////////////////
245        // object space partition
246        /////////////////////////////////////////////////////////////
247
248
249        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
250        cout << "starting osp contruction ... " << endl;
251
252        // start with one big kd cell - all objects can be seen from everywhere
253        // note: only true for view space = object space
254
255        // compute first candidate
256        SubdivisionCandidate *osc =
257                mOspTree.PrepareConstruction(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
258
259        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
260        mTotalCost = mOspTree.mTotalCost;
261
262    mTQueue.Push(osc);
263
264        mOspTree.mOspStats.Reset();
265        mOspTree.mOspStats.Start();
266
267        startTime = GetTime();
268       
269        // process object space candidates
270        RunConstruction(repairQueue);
271       
272        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
273
274        mOspTree.mOspStats.Stop();
275
276        float rc = mOspTree.EvalRenderCost(sampleRays);
277
278        Debug << "here47 My render cost evalulation: " << rc << endl;
279
280#if 0
281        // reset parameters
282        mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
283        mVspTree.mStoreKdPvs = savedStoreMethod;
284#endif
285}
286
287
288void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
289                                                                  const ObjectContainer &objects,
290                                                                  AxisAlignedBox3 *forcedViewSpace)
291{
292        // only view space partition
293        // object kd tree is taken for osp
294
295        mVspTree.mVspStats.Reset();
296        mVspTree.mVspStats.Start();
297
298        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
299       
300        SubdivisionCandidate *sc =
301                mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
302
303        mTQueue.Push(sc);
304
305        cout << "starting vsp contruction ... " << endl;
306
307        long startTime = GetTime();
308
309        RunConstruction(false);
310
311        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
312        mVspTree.mVspStats.Stop();
313}
314
315
316bool HierarchyManager::FinishedConstruction() const
317{
318        return mTQueue.Empty();
319}
320
321
322void HierarchyManager::CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList)
323{       
324        // we have either a object space or view space split
325        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
326        {
327                VspTree::VspSubdivisionCandidate *sc =
328                        dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
329
330                mVspTree.CollectDirtyCandidates(sc, dirtyList);
331        }
332        else // object space split
333        {                       
334                OspTree::OspSubdivisionCandidate *sc =
335                        dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
336
337                mOspTree.CollectDirtyCandidates(sc, dirtyList);
338        }
339}
340
341
342void HierarchyManager::RepairQueue()
343{
344        // TODO
345        // for each update of the view space partition:
346        // the candidates from object space partition which
347        // have been afected by the view space split (the kd split candidates
348        // which saw the view cell which was split) must be reevaluated
349        // (maybe not locally, just reinsert them into the queue)
350        //
351        // vice versa for the view cells
352        // for each update of the object space partition
353        // reevaluate split candidate for view cells which saw the split kd cell
354        //
355        // the priority queue update can be solved by implementing a binary heap
356        // (explicit data structure, binary tree)
357        // *) inserting and removal is efficient
358        // *) search is not efficient => store queue position with each
359        // split candidate
360
361        // collect list of "dirty" candidates
362        vector<SubdivisionCandidate *> dirtyList;
363        CollectDirtyCandidates(dirtyList);
364       
365        //-- reevaluate the dirty list
366        vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
367
368        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
369        {
370                SubdivisionCandidate* sc = *sit;
371
372                mTQueue.Erase(sc);
373
374                // reevaluate
375                sc->EvalPriority();
376
377                // reinsert
378                mTQueue.Push(sc);
379        }
380}
381
382}
Note: See TracBrowser for help on using the repository browser.