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

Revision 1286, 16.9 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#include "BvHierarchy.h"
23
24
25namespace GtpVisibilityPreprocessor {
26
27
28#define USE_FIXEDPOINT_T 0
29
30
31/*******************************************************************/
32/*              class HierarchyManager implementation              */
33/*******************************************************************/
34
35
36HierarchyManager::HierarchyManager(VspTree *vspTree,
37                                                                   const int objectSpaceSubdivisionType):
38mObjectSpaceSubdivisonType(objectSpaceSubdivisionType),
39mVspTree(vspTree),
40mOspTree(NULL),
41mBvHierarchy(NULL)
42{
43        switch(mObjectSpaceSubdivisonType)
44        {
45        case KD_BASED_OBJ_SUBDIV:
46                mOspTree = new OspTree();
47                mOspTree->mVspTree = mVspTree;
48                //mOspTree->mHierarchyManager = this;
49                Debug << "creating osp tree" << endl;
50                break;
51        case BV_BASED_OBJ_SUBDIV:
52        mBvHierarchy = new BvHierarchy();
53                mBvHierarchy->mVspTree = mVspTree;
54                //mBvHierarchy->mHierarchyManager = this;
55                Debug << "creating bv hierachy" << endl;
56                break;
57        default:
58                break;
59        }
60
61        if (mVspTree)
62                mVspTree->mHierarchyManager = this;
63
64        char subdivisionStatsLog[100];
65        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
66                subdivisionStatsLog);
67        mSubdivisionStats.open(subdivisionStatsLog);
68}
69
70
71HierarchyManager::HierarchyManager(VspTree *vspTree, KdTree *kdTree):
72mObjectSpaceSubdivisonType(KD_BASED_OBJ_SUBDIV),
73mVspTree(vspTree),
74mBvHierarchy(NULL)
75{
76        mOspTree = new OspTree(*kdTree);
77        mOspTree->mVspTree = mVspTree;
78
79        //mOspTree->mHierarchyManager = this;
80        Debug << "creating osp tree" << endl;
81
82        if (mVspTree)
83                mVspTree->mHierarchyManager = this;
84
85        char subdivisionStatsLog[100];
86        Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
87                subdivisionStatsLog);
88        mSubdivisionStats.open(subdivisionStatsLog);
89}
90
91
92HierarchyManager::~HierarchyManager()
93{
94        DEL_PTR(mOspTree);
95        //DEL_PTR(mVspTree);
96        DEL_PTR(mBvHierarchy);
97}
98
99
100void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
101{
102        mVspTree->SetViewCellsManager(vcm);
103
104        if (mOspTree)
105                mOspTree->SetViewCellsManager(vcm);
106        if (mBvHierarchy)
107                mBvHierarchy->SetViewCellsManager(vcm);
108}
109
110
111void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
112{
113        mVspTree->SetViewCellsTree(vcTree);
114}
115
116
117SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
118{
119        SubdivisionCandidate *splitCandidate = mTQueue.Top();
120        mTQueue.Pop();
121
122        return splitCandidate;
123}
124
125
126void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
127                                                                                   const ObjectContainer &objects,
128                                                                                   AxisAlignedBox3 *forcedViewSpace,
129                                                                                   RayInfoContainer &viewSpaceRays,
130                                                                                   RayInfoContainer &objectSpaceRays)
131{
132        SubdivisionCandidate *vsc =
133                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
134        mTQueue.Push(vsc);
135
136        SubdivisionCandidate *osc =
137                mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);
138
139        mTQueue.Push(osc);
140}
141
142
143void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
144{
145        const float costDecr = tData.GetRenderCostDecrease();
146
147        //mTotalCost -= costDecr;
148        //mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
149
150        AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
151                                                costDecr,
152                                                mTotalCost
153                                                );
154}
155
156
157void HierarchyManager::AddSubdivisionStats(const int splits,
158                                                                                   const float renderCostDecr,
159                                                                                   const float totalRenderCost)
160{
161        mSubdivisionStats
162                        << "#Splits\n" << splits << endl
163                        << "#RenderCostDecrease\n" << renderCostDecr << endl
164                        << "#TotalRenderCost\n" << totalRenderCost << endl;
165                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
166}
167
168
169bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
170{
171        // TODO matt: make virtual by creating superclasss for traveral data
172        return candidate->GlobalTerminationCriteriaMet();
173}
174
175
176void HierarchyManager::Construct(const VssRayContainer &sampleRays,
177                                                                 const ObjectContainer &objects,
178                                                                 AxisAlignedBox3 *forcedViewSpace)
179{
180        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
181        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
182
183        // prepare vsp and osp trees for traversal
184        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
185
186        mVspTree->mVspStats.Reset();
187        mVspTree->mVspStats.Start();
188
189        cout << "Constructing view space / object space tree ... \n";
190        const long startTime = GetTime();       
191       
192        RunConstruction(true);
193
194        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
195
196        mVspTree->mVspStats.Stop();
197}
198
199
200bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
201{
202        const bool globalTerminationCriteriaMet =
203                        GlobalTerminationCriteriaMet(sc);
204
205        const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
206
207        if (vspSplit)
208        {
209                VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
210        }
211        else
212        {
213                KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
214        }
215       
216        return !globalTerminationCriteriaMet;
217}
218
219
220void HierarchyManager::RunConstruction(const bool repair)
221{
222        int numNodes = 0;
223
224        while (!FinishedConstruction())
225        {
226                SubdivisionCandidate *splitCandidate = NextSubdivisionCandidate();
227           
228                mTotalCost -= splitCandidate->GetRenderCostDecrease();
229
230                // cost ratio of cost decrease / totalCost
231                const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
232
233                if (costRatio < mTermMinGlobalCostRatio)
234                        ++ mGlobalCostMisses;
235       
236                /*Debug << "\n**********" << endl
237                          << "total cost: " << mTotalCost << " render cost decr: "
238                          << splitCandidate->GetRenderCostDecrease()
239                          << " cost ratio: " << costRatio << endl << endl;*/
240
241                //-- subdivide leaf node
242
243                if (SubdivideSubdivisionCandidate(splitCandidate))
244                {
245                        // subdivision successful
246                        EvalSubdivisionStats(*splitCandidate);
247               
248                        // reevaluate candidates affected by the split
249                        // for view space splits, this would be object space splits
250                        // and other way round
251                        if (repair)
252                                RepairQueue();
253
254                        cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
255                }
256
257                DEL_PTR(splitCandidate);
258        }
259}
260
261
262void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
263                                                                  const ObjectContainer &objects,
264                                                                  AxisAlignedBox3 *forcedViewSpace)
265{
266        // construct only view space partition
267        // object kd tree is taken for osp
268
269        mVspTree->mVspStats.Reset();
270        mVspTree->mVspStats.Start();
271
272        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
273       
274        SubdivisionCandidate *sc =
275                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
276
277        mTQueue.Push(sc);
278
279        cout << "starting vsp construction ... " << endl;
280
281        long startTime = GetTime();
282
283        RunConstruction(false);
284
285        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
286        mVspTree->mVspStats.Stop();
287}
288
289
290bool HierarchyManager::FinishedConstruction() const
291{
292        return mTQueue.Empty();
293}
294
295
296void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
297{
298        switch (mObjectSpaceSubdivisonType)
299        {
300        case KD_BASED_OBJ_SUBDIV:
301                {
302                        OspTree::OspSubdivisionCandidate *sc =
303                                dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
304
305                        mOspTree->CollectDirtyCandidates(sc, dirtyList);
306                        break;
307                }
308        case BV_BASED_OBJ_SUBDIV:
309                {
310                        BvHierarchy::BvhSubdivisionCandidate *sc =
311                                dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
312
313                        mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
314                        break;
315                }
316        default:
317                break;
318        }
319}
320
321
322void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
323{
324        VspTree::VspSubdivisionCandidate *sc =
325                dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
326
327        mVspTree->CollectDirtyCandidates(sc, dirtyList);
328}
329
330
331void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
332{       
333        // we have either a object space or view space split
334        if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
335        {
336                CollectViewSpaceDirtyList(dirtyList);
337        }
338        else // object space split
339        {       
340                CollectObjectSpaceDirtyList(dirtyList);
341        }
342}
343
344
345void HierarchyManager::RepairQueue()
346{
347        // TODO
348        // for each update of the view space partition:
349        // the candidates from object space partition which
350        // have been afected by the view space split (the kd split candidates
351        // which saw the view cell which was split) must be reevaluated
352        // (maybe not locally, just reinsert them into the queue)
353        //
354        // vice versa for the view cells
355        // for each update of the object space partition
356        // reevaluate split candidate for view cells which saw the split kd cell
357        //
358        // the priority queue update can be solved by implementing a binary heap
359        // (explicit data structure, binary tree)
360        // *) inserting and removal is efficient
361        // *) search is not efficient => store queue position with each
362        // split candidate
363
364        // collect list of "dirty" candidates
365        vector<SubdivisionCandidate *> dirtyList;
366        CollectDirtyCandidates(dirtyList);
367       
368        //-- reevaluate the dirty list
369        vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
370
371        for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
372        {
373                SubdivisionCandidate* sc = *sit;
374
375                mTQueue.Erase(sc);
376
377                // reevaluate
378                sc->EvalPriority();
379
380                // reinsert
381                mTQueue.Push(sc);
382        }
383}
384
385
386void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
387{
388        // the type of the view cells hierarchy
389        switch (mObjectSpaceSubdivisonType)
390        {
391        case KD_BASED_OBJ_SUBDIV:
392                stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
393                mOspTree->Export(stream);
394                stream << endl << "</ObjectSpaceHierarchy>" << endl;
395                break;
396               
397        case BV_BASED_OBJ_SUBDIV:
398                stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
399                mBvHierarchy->Export(stream);
400                stream << endl << "</ObjectSpaceHierarchy>" << endl;
401                break;
402        }
403}
404
405
406bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
407                                                                          const Vector3 &hitPoint,
408                                                                          ViewCell *vc,
409                                                                          const float pdf,
410                                                                          float &contribution) const
411{
412        if (!obj) return false;
413
414        switch (mObjectSpaceSubdivisonType)
415        {
416        case NO_OBJ_SUBDIV:
417                // potentially visible objects
418                return vc->AddPvsSample(obj, pdf, contribution);
419
420        case KD_BASED_OBJ_SUBDIV:
421                {
422                        // potentially visible kd cells
423                        KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
424                        return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
425                }
426        case BV_BASED_OBJ_SUBDIV:
427                {
428                        BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
429                        return mBvHierarchy->AddLeafToPvs(leaf, vc, pdf, contribution);
430                }
431        default:
432                return false;
433        }
434}
435
436
437void HierarchyManager::PrintObjectSpaceHierarchyStatistics(ofstream &stream) const
438{
439        switch (mObjectSpaceSubdivisonType)
440        {
441        case KD_BASED_OBJ_SUBDIV:
442                {
443                        stream << mOspTree->GetStatistics();
444                        break;
445                }
446        case BV_BASED_OBJ_SUBDIV:
447                {
448                        stream << mBvHierarchy->GetStatistics();
449                        break;
450                }
451        default:
452                break;
453        }
454}
455
456
457void HierarchyManager::ExportObjectSpaceHierarchyForViz(const ObjectContainer &objects) const
458{
459        switch (mObjectSpaceSubdivisonType)
460        {
461        case KD_BASED_OBJ_SUBDIV:
462                {
463                        ExportOspTreeForViz(objects);
464                        break;
465                }
466        case BV_BASED_OBJ_SUBDIV:
467                {
468                        ExportBvhForViz(objects);
469                        break;
470                }
471        default:
472                break;
473        }
474}
475
476
477void HierarchyManager::ExportBvhForViz(const ObjectContainer &objects) const
478{
479}
480
481
482void HierarchyManager::ExportOspTreeForViz(const ObjectContainer &objects) const
483{
484        //-- export final object partition
485        Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
486               
487        if (exporter)
488        {
489                cout << "exporting object space partition ... ";
490
491                if (1) exporter->ExportGeometry(objects);
492                       
493#if 0           
494                // export rays
495                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
496#endif
497                exporter->SetWireframe();
498       
499                const int colorCode = 0;
500                const int maxPvs = 0;//mOspTree.GetStatistics().maxPvs;
501
502                exporter->ExportOspTree(*mOspTree, 0);
503                delete exporter;
504
505                cout << "finished" << endl;
506        }
507}
508
509
510void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
511                                                                  const ObjectContainer &objects,
512                                                                  AxisAlignedBox3 *forcedViewSpace)
513{
514        // rays clipped in view space and in object space
515        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
516       
517        /////////////////////////////////////////////////////////////
518        // view space space partition
519        /////////////////////////////////////////////////////////////
520
521        // use objects for evaluating vsp tree construction
522        const int savedobjectSpaceSubdivisionType = mObjectSpaceSubdivisonType;
523        mObjectSpaceSubdivisonType = NO_OBJ_SUBDIV;
524
525        SubdivisionCandidate *vsc =
526                mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
527       
528        // add to queue
529        mTQueue.Push(vsc);
530
531        long startTime = GetTime();
532        cout << "starting vsp construction ... " << endl;
533
534        mVspTree->mVspStats.Reset();
535        mVspTree->mVspStats.Start();
536
537        int i = 0;
538
539        // all objects can be seen from everywhere
540        mTotalCost = (float)dynamic_cast<VspTree::VspSubdivisionCandidate *>(vsc)->mParentData.mPvs;
541
542        const bool repairQueue = false;
543
544        // process view space candidates
545        RunConstruction(repairQueue);
546
547        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
548        mVspTree->mVspStats.Stop();
549
550        // reset subdivision type
551        mObjectSpaceSubdivisonType = savedobjectSpaceSubdivisionType;
552
553
554        /////////////////////////////////////////////////////////////
555        // object space partition
556        /////////////////////////////////////////////////////////////
557       
558       
559        switch (mObjectSpaceSubdivisonType)
560        {
561        case KD_BASED_OBJ_SUBDIV:
562                {
563                        ConstructOspTree(sampleRays, objects, forcedViewSpace);
564                        break;
565                }
566        case BV_BASED_OBJ_SUBDIV:
567                {
568                        ConstructBvHierarchy(sampleRays, objects, forcedViewSpace);
569                        break;
570                }
571        default:
572                break;
573        }
574}
575
576
577void HierarchyManager::ConstructBvHierarchy(const VssRayContainer &sampleRays,
578                                                                                        const ObjectContainer &objects,
579                                                                                        AxisAlignedBox3 *forcedViewSpace)
580
581{
582        Debug << "\n$$$$$$$$$ bv hierarchy construction $$$$$$$$$$\n" << endl;
583        cout << "starting bv hierarchy construction ... " << endl;
584
585        // start with one big kd cell - all objects can be seen from everywhere
586        // note: only true for view space = object space
587
588        ObjectContainer obj = objects;
589
590        // compute first candidate
591        SubdivisionCandidate *sc =
592                mBvHierarchy->PrepareConstruction(sampleRays, obj, forcedViewSpace);
593
594        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
595        mTotalCost = mOspTree->mTotalCost;
596
597    mTQueue.Push(sc);
598
599        mOspTree->mOspStats.Reset();
600        mOspTree->mOspStats.Start();
601
602        const long startTime = GetTime();
603        const bool repairQueue = false;
604
605        // process object space candidates
606        RunConstruction(repairQueue);
607       
608        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
609
610        mOspTree->mOspStats.Stop();
611
612        //////////////////////////
613        // matt: only for debugging purpose
614
615        const float rc = mOspTree->EvalRenderCost(sampleRays);
616
617        Debug << "My render cost evalulation: " << rc << endl;
618}
619
620
621void HierarchyManager::ConstructOspTree(const VssRayContainer &sampleRays,
622                                                                                const ObjectContainer &objects,
623                                                                                AxisAlignedBox3 *forcedViewSpace)
624
625{
626        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
627
628        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
629        cout << "starting osp tree construction ... " << endl;
630
631        // start with one big kd cell - all objects can be seen from everywhere
632        // note: only true for view space = object space
633
634        // compute first candidate
635        SubdivisionCandidate *osc =
636                mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
637
638        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
639        mTotalCost = mOspTree->mTotalCost;
640
641    mTQueue.Push(osc);
642
643        mOspTree->mOspStats.Reset();
644        mOspTree->mOspStats.Start();
645
646        const long startTime = GetTime();
647        const bool repairQueue = false;
648       
649        // process object space candidates
650        RunConstruction(repairQueue);
651       
652        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
653
654        mOspTree->mOspStats.Stop();
655
656        //////////////////////////
657        // matt: only for debugging purpose
658
659        const float rc = mOspTree->EvalRenderCost(sampleRays);
660
661        Debug << "My render cost evalulation: " << rc << endl;
662}
663
664}
Note: See TracBrowser for help on using the repository browser.