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

Revision 1286, 41.9 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "BvHierarchy.h"
6#include "ViewCell.h"
7#include "Plane3.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 "VspTree.h"
19
20
21namespace GtpVisibilityPreprocessor {
22
23
24#define USE_FIXEDPOINT_T 0
25
26static float debugVol = 0;
27int BvhNode::sMailId = 0;
28BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
29
30
31inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
32{
33        return obj1->mId < obj2->mId;
34}
35
36
37/***************************************************************/
38/*              class BvhNode implementation                   */
39/***************************************************************/
40
41BvhNode::BvhNode(): mParent(NULL)
42{
43}
44
45BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
46mBoundingBox(bbox)
47{
48}
49
50
51BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
52mBoundingBox(bbox), mParent(parent)
53{
54}
55
56
57bool BvhNode::IsRoot() const
58{
59        return mParent == NULL;
60}
61
62
63BvhInterior *BvhNode::GetParent()
64{
65        return mParent;
66}
67
68
69void BvhNode::SetParent(BvhInterior *parent)
70{
71        mParent = parent;
72}
73
74
75
76/******************************************************************/
77/*              class BvhInterior implementation                  */
78/******************************************************************/
79
80
81BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
82BvhNode(bbox)
83{
84}
85
86
87BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
88BvhNode(bbox, parent)
89{
90}
91
92
93BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent, const int numObjects):
94BvhNode(bbox, parent)
95{
96        mObjects.reserve(numObjects);
97}
98
99
100bool BvhLeaf::IsLeaf() const
101{
102        return true;
103}
104
105
106BvhLeaf::~BvhLeaf()
107{
108}
109
110
111/******************************************************************/
112/*              class BvhInterior implementation                  */
113/******************************************************************/
114
115
116BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
117BvhNode(bbox)
118{
119}
120
121
122BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
123BvhNode(bbox, parent)
124{
125}
126
127
128void BvhInterior::ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild)
129{
130        if (mBack == oldChild)
131                mBack = newChild;
132        else
133                mFront = newChild;
134}
135
136
137bool BvhInterior::IsLeaf() const
138{
139        return false;
140}
141
142
143BvhInterior::~BvhInterior()
144{
145        DEL_PTR(mFront);
146        DEL_PTR(mBack);
147}
148
149
150void BvhInterior::SetupChildLinks(BvhNode *front, BvhNode *back)
151{
152    mBack = back;
153    mFront = front;
154}
155
156
157
158/*******************************************************************/
159/*                  class BvHierarchy implementation               */
160/*******************************************************************/
161
162
163BvHierarchy::BvHierarchy():
164mRoot(NULL),
165mTimeStamp(1)
166{
167        ReadEnvironment();
168        mSubdivisionCandidates = new vector<SortableEntry>;
169}
170
171
172BvHierarchy::~BvHierarchy()
173{
174        // delete kd intersectables
175        BvhIntersectableMap::iterator it, it_end = mBvhIntersectables.end();
176
177        for (it = mBvhIntersectables.begin(); it != mBvhIntersectables.end(); ++ it)
178        {
179                DEL_PTR((*it).second);
180        }
181
182        DEL_PTR(mSubdivisionCandidates);
183
184        mSubdivisionStats.close();
185}
186
187
188void BvHierarchy::ReadEnvironment()
189{
190        bool randomize = false;
191        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
192        if (randomize)
193                Randomize(); // initialise random generator for heuristics
194
195        //-- termination criteria for autopartition
196        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
197        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
198        Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
199        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinVolume);
200       
201        Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
202       
203        //-- max cost ratio for early tree termination
204        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
205
206        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio",
207                mTermMinGlobalCostRatio);
208       
209
210        //-- factors for bsp tree split plane heuristics
211        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
212
213        //-- partition criteria
214        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
215
216        // if only the driving axis is used for axis aligned split
217        Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
218        Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
219        Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
220
221
222        char subdivisionStatsLog[100];
223        Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
224        mSubdivisionStats.open(subdivisionStatsLog);
225
226        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
227        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
228       
229
230        //-- debug output
231
232        Debug << "******* Bvh hierarchy options ******** " << endl;
233
234    Debug << "max depth: " << mTermMaxDepth << endl;
235        Debug << "min probabiliy: " << mTermMinVolume<< endl;
236        Debug << "min objects: " << mTermMinObjects << endl;
237        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
238        Debug << "miss tolerance: " << mTermMissTolerance << endl;
239        Debug << "max leaves: " << mTermMaxLeaves << endl;
240
241        Debug << "randomize: " << randomize << endl;
242
243        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
244        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
245        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
246        Debug << "max memory: " << mMaxMemory << endl;
247        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
248        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
249       
250        Debug << "split borders: " << mSplitBorder << endl;
251        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
252        Debug << endl;
253}
254
255
256void AssociateObjectsWithLeaf(BvhLeaf *leaf)
257{
258        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
259        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
260        {
261                (*oit)->mBvhLeaf = leaf;
262        }
263}
264
265
266BvhInterior *BvHierarchy::SubdivideNode(const ObjectContainer &frontObjects,
267                                                                                const ObjectContainer &backObjects,
268                                                                                const BvhTraversalData &tData,
269                                                                                BvhTraversalData &frontData,
270                                                                                BvhTraversalData &backData)
271{
272        BvhLeaf *leaf = tData.mNode;
273       
274        // two new leaves
275    mBvhStats.nodes += 2;
276
277        // add the new nodes to the tree
278        BvhInterior *node = new BvhInterior(tData.mBoundingBox, leaf->GetParent());
279
280
281        //-- the front and back traversal data is filled with the new values
282
283        frontData.mDepth = backData.mDepth = tData.mDepth + 1;
284               
285        // frontData.mRays = new RayInfoContainer();
286        // backData.mRays = new RayInfoContainer();
287
288        frontData.mBoundingBox = ComputeBoundingBox(frontObjects);
289        backData.mBoundingBox = ComputeBoundingBox(backObjects);
290        //RemoveParentViewCellsPvs(leaf, *tData.mRays);
291
292
293        /////////////
294        //-- create front and back leaf
295
296        BvhLeaf *back = new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
297        BvhLeaf *front = new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());
298
299        BvhInterior *parent = leaf->GetParent();
300
301
302        // replace a link from node's parent
303        if (parent)
304        {
305                parent->ReplaceChildLink(leaf, node);
306                node->SetParent(parent);
307        }
308        else // new root
309        {
310                mRoot = node;
311        }
312
313        // and setup child links
314        node->SetupChildLinks(front, back);
315
316        ++ mBvhStats.splits;
317
318        //UpdateViewCellsPvs(front, *frontData.mRays);
319        //UpdateViewCellsPvs(back, *backData.mRays);
320
321        ////////////////////////////////////
322
323        //ProcessMultipleRefs(front);
324    //ProcessMultipleRefs(back);
325
326        frontData.mNode = front;
327        backData.mNode = back;
328
329        back->mObjects = backObjects;
330        front->mObjects = frontObjects;
331
332        AssociateObjectsWithLeaf(back);
333        AssociateObjectsWithLeaf(front);
334   
335
336        // compute probability, i.e., volume of seen view cells
337        frontData.mVolume = frontData.mBoundingBox.GetVolume();
338        backData.mVolume =  backData.mBoundingBox.GetVolume();
339
340        return node;
341}
342
343
344BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
345                                                                SubdivisionCandidate *splitCandidate,
346                                                                const bool globalCriteriaMet)
347{
348        BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
349        BvhTraversalData &tData = sc->mParentData;
350
351        BvhNode *newNode = tData.mNode;
352
353        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
354        {       
355                BvhTraversalData tFrontData;
356                BvhTraversalData tBackData;
357
358                //-- continue subdivision
359               
360                // create new interior node and two leaf node
361                newNode = SubdivideNode(sc->mFrontObjects,
362                                                                sc->mBackObjects,
363                                                                tData,
364                                                                tFrontData,
365                                                                tBackData);
366       
367                const int maxCostMisses = sc->mMaxCostMisses;
368
369        // how often was max cost ratio missed in this branch?
370                tFrontData.mMaxCostMisses = maxCostMisses;
371                tBackData.mMaxCostMisses = maxCostMisses;
372               
373                mTotalCost -= sc->GetRenderCostDecrease();
374
375                // subdivision statistics
376                if (1) EvalSubdivisionStats(*sc);
377
378                //-- push the new split candidates on the queue
379               
380                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
381                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
382
383                EvalSubdivisionCandidate(*frontCandidate);
384                EvalSubdivisionCandidate(*backCandidate);
385
386                tQueue.Push(frontCandidate);
387                tQueue.Push(backCandidate);
388
389                // delete old leaf node
390                DEL_PTR(tData.mNode);
391        }
392
393
394        //-- terminate traversal
395        if (newNode->IsLeaf())
396        {
397                EvaluateLeafStats(tData);
398       
399                const bool mStoreRays= true;
400
401                //-- store additional info
402                if (mStoreRays)
403                {
404                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(newNode);
405                        CollectRays(leaf->mObjects, leaf->mVssRays);
406                }
407        }
408       
409        //-- cleanup
410        tData.Clear();
411       
412        return newNode;
413}
414
415
416void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate)
417{
418        ObjectContainer frontObjects, backObjects;
419
420        // compute best object partition
421        const float ratio =
422                SelectObjectPartition(splitCandidate.mParentData, frontObjects, backObjects);
423
424        const bool success = ratio < mTermMaxCostRatio;
425
426        float oldRenderCost;
427
428        // compute global decrease in render cost
429        const float renderCostDecr = EvalRenderCostDecrease(frontObjects,
430                                                                                                                backObjects,
431                                                                                                                splitCandidate.mParentData,
432                                                                                                                oldRenderCost);
433
434        splitCandidate.SetRenderCostDecrease(renderCostDecr);
435
436#if 0
437        const float priority = (float)-data.mDepth;
438#else   
439        // take render cost of node into account
440        // otherwise danger of being stuck in a local minimum!!
441        const float factor = mRenderCostDecreaseWeight;
442        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
443
444#endif
445
446        // compute global decrease in render cost
447        splitCandidate.SetPriority(priority);
448
449        splitCandidate.mMaxCostMisses =
450                success ? splitCandidate.mParentData.mMaxCostMisses :
451        splitCandidate.mParentData.mMaxCostMisses + 1;
452}
453
454
455inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
456{
457        // matt: TODO
458        return (
459                //(data.mNode->mObjects.size() < mTermMinObjects) ||
460                //(data.mProbability <= mTermMinProbability) ||
461                (data.mDepth >= mTermMaxDepth)
462                 );
463}
464
465
466inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
467{
468        // matt: TODO
469        return (
470                (mBvhStats.Leaves() >= mTermMaxLeaves)
471                //mOutOfMemory ||
472                //(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
473                );
474}
475
476
477void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
478{
479        // the node became a leaf -> evaluate stats for leafs
480        BvhLeaf *leaf = data.mNode;
481       
482        ++ mCreatedLeaves;
483
484        if (data.mDepth >= mTermMaxDepth)
485        {
486        ++ mBvhStats.maxDepthNodes;
487                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
488        }
489
490        if (data.mVolume <= mTermMinVolume)
491                ++ mBvhStats.minProbabilityNodes;
492       
493        // accumulate depth to compute average depth
494        mBvhStats.accumDepth += data.mDepth;
495 
496        //      if ((int)(leaf->mObjects.size()) < mTermMinCost)
497        //     ++ mOspStats.minCostNodes;
498 
499        if ((int)(leaf->mObjects.size()) > mBvhStats.maxObjectRefs)
500                mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
501}
502
503
504float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
505                                                                                   const int axis,
506                                                                                   ObjectContainer &objectsFront,
507                                                                                   ObjectContainer &objectsBack)
508{
509        // the relative cost ratio
510        float ratio = 99999999.0f;
511
512        // go through the lists, count the number of objects left and right
513        // and evaluate the following cost funcion:
514        // C = ct_div_ci  + (ol + or)/queries
515       
516        const float minBox = tData.mBoundingBox.Min(axis);
517        const float maxBox = tData.mBoundingBox.Max(axis);
518
519        const float sizeBox = maxBox - minBox;
520
521        float minBand = minBox + mSplitBorder * (maxBox - minBox);
522        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
523
524        //-- sort so we can use a sweep
525        SortSubdivisionCandidates(tData, axis, minBand, maxBand);
526
527        float totalVol = PrepareHeuristics(tData);
528        float voll = 0;
529        float volr = totalVol;
530
531        /// this is kind of a reverse pvs
532        const int totalObjects = (int)tData.mNode->mObjects.size();
533       
534        int objectsl = 0;
535        int objectsr = totalObjects;
536
537        float sum = (float)totalVol * objectsr;
538
539
540        bool splitPlaneFound = false;
541
542        /////////////////////////////////
543        // the parameters for the current optimum
544
545        float volBack = voll;
546        float volFront = volr;
547
548        int nObjectsBack = objectsl;
549        int nObjectsFront = objectsr;
550       
551        float minSum = 1e20f;
552
553        /////////////////////////////
554
555        debugVol = 0;
556        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
557
558        /////////////////////////////
559        // the sweep heuristics
560
561        // mail the objects on the left side
562        Intersectable::NewMail();
563       
564        //-- traverse through events and find best split plane
565        vector<SortableEntry>::const_iterator ci, ci_end = mSubdivisionCandidates->end();
566
567        for (ci = mSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
568        {
569                Intersectable *object = (*ci).mObject;
570
571                EvalHeuristicsContribution(tData.mNode, *ci, voll, volr, objectsl);
572                objectsr = totalObjects - objectsl;
573
574                // Note: sufficient to compare size of bounding boxes of front and back side?
575
576                if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
577                {
578                        // voll = view cells that see only left node (i.e., left pvs)
579                        // volr = view cells that see only right node (i.e., right pvs)
580                        // rest = view cells that see both nodes (i.e., total pvs)
581            sum = voll * objectsl + volr * objectsr + (totalVol - voll - volr) * totalObjects;
582
583                        float currentPos;
584                       
585                        // HACK: current positition is BETWEEN visibility events
586                        if (1 && ((ci + 1) != ci_end))
587                                currentPos = ((*ci).mPos + (*(ci + 1)).mPos) * 0.5f;
588                        else
589                                currentPos = (*ci).mPos;                       
590
591                        if ((totalVol - voll - volr - debugVol) / viewSpaceVol > 0.0001)
592                                Debug << "front and back volume: " << (totalVol - voll - volr) / viewSpaceVol << " error: " << (totalVol - voll - volr - debugVol) / viewSpaceVol << endl;
593#if 0                           
594                        Debug << "pos: " << currentPos
595                                 << "\t (pvsl: " << pvsl << ", pvsr: " << pvsr << ")"
596                                 << "\t (voll: " << voll << ", volr: " << volr << ")"
597                                 << "\t (vcl: " << vcl << ", vcr: " << vcr << ", nvc: " << numViewCells << ")"
598                                 << "\t sum: " << sum << endl;
599                               
600#endif
601                        if (sum < minSum)
602                        {
603                                splitPlaneFound = true;
604
605                                minSum = sum;
606
607                                nObjectsBack = objectsl;
608                                nObjectsFront = objectsr;
609                               
610                                volBack = voll;
611                                volFront = volr;
612                        }
613                }
614        }
615       
616        //-- compute cost
617        const float frontAndBackVol = totalVol - volFront - volBack;
618
619        const float oldRenderCost = (float)totalObjects * totalVol + Limits::Small;
620        const float newRenderCost = (float)nObjectsFront * volFront +
621                                                                (float)nObjectsBack * volBack +
622                                                                (float)totalObjects * frontAndBackVol;
623
624        if (splitPlaneFound)
625        {
626                ratio = newRenderCost / oldRenderCost;
627        }
628
629        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos="
630        //        << position << " t=" << (position - minBox) / (maxBox - minBox)
631        //      << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
632
633        Debug << "\n§§§§ eval local cost §§§§" << endl
634                  << "back pvs: " << nObjectsBack << " front pvs: " << nObjectsFront << " total pvs: " << totalObjects << endl
635                  << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
636                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
637                  << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
638
639        if (oldRenderCost < newRenderCost)
640                Debug << "\nwarning!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
641
642        // assign objects
643        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
644
645        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
646        {
647                Intersectable *obj = *oit;
648
649                if (obj->Mailed()) // belongs to back objects
650                        objectsBack.push_back(obj);
651                else
652                        objectsFront.push_back(obj);
653        }
654
655        return ratio;
656}
657
658
659void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
660                                                                          const int axis,
661                                                                          float minBand,
662                                                                          float maxBand)
663
664{
665        mSubdivisionCandidates->clear();
666
667        //RayInfoContainer *rays = tData.mRays;
668        BvhLeaf *leaf = tData.mNode;
669
670        // compute requested size
671        int requestedSize = 0;
672        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
673        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
674                requestedSize += 2 + (int)(*oit)->mVssRays.size() * 2;
675       
676        // creates a sorted split candidates array
677        if (mSubdivisionCandidates->capacity() > 500000 &&
678                requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
679        {
680        delete mSubdivisionCandidates;
681                mSubdivisionCandidates = new vector<SortableEntry>;
682        }
683
684        mSubdivisionCandidates->reserve(requestedSize);
685
686        float pos;
687
688        //-- insert object queries
689        //-- These queries can induce a change in pvs size.
690        //-- Note that they cannot induce a change in view cell volume, as
691        //-- there is no ray associated with these events!!
692
693        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
694        {
695                Intersectable *obj = *oit;
696               
697                Intersectable *object = *oit;
698                const AxisAlignedBox3 box = object->GetBox();
699
700                mSubdivisionCandidates->push_back(
701                        SortableEntry(SortableEntry::OBJECT,
702                                                  box.Min(axis),
703                                                  object,
704                                                  NULL)
705                                                  );
706
707
708                //-- insert ray queries
709                //-- we are intersested only in rays which intersect an object that
710                //-- is part of the kd node because they can induce a change in view cell
711                //-- volume on the left and the right part.
712                //-- Note that they cannot induce a change in pvs size!!
713               
714                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
715
716                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
717                {
718                        VssRay *ray = (*rit);
719                        const bool positive = ray->HasPosDir(axis);
720       
721                        pos = ray->mTermination[axis];
722
723                        mSubdivisionCandidates->push_back(
724                                SortableEntry(SortableEntry::VIEWCELLS,
725                                pos,
726                                ray->mTerminationObject,
727                                ray)
728                                );
729                }
730        }
731
732        stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
733}
734
735
736const BvhStatistics &BvHierarchy::GetStatistics() const
737{
738        return mBvhStats;
739}
740
741
742void BvHierarchy::EvalRayContribution(const VssRay &ray,
743                                                                          float &volLeft,
744                                                                          float &volRight)
745{
746        ViewCellContainer viewCells;
747        mVspTree->GetViewCells(ray, viewCells);
748
749        /// classify view cells and compute volume contri accordingly
750        /// possible view cell classifications:
751        /// view cell mailed => view cell can be seen from left child node
752        /// view cell counter > 0 view cell can be seen from right child node
753        /// combined: view cell volume belongs to both nodes
754        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
755       
756        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
757        {
758                // view cells can also be seen from left child node
759                ViewCell *viewCell = *vit;
760
761                const float vol = viewCell->GetVolume();
762
763                if (!viewCell->Mailed())
764                {
765                        viewCell->Mail();
766
767                        // we now see view cell from both nodes
768                        // => remove ref to right child node
769                        volRight -= vol;
770                        debugVol += vol;
771                }
772
773                // last reference into the right node
774                if (-- viewCell->mCounter == 0)
775                {
776                        // view cell was previously seen from both nodes  =>
777                        // contributes only to left node now
778                        volLeft += vol;
779                        debugVol -= vol;
780                }
781        }
782}
783
784
785float BvHierarchy::PrepareHeuristics(const VssRay &ray)
786{
787        float vol = 0;
788
789        ViewCellContainer viewCells;
790        mVspTree->GetViewCells(ray, viewCells);
791       
792        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
793
794        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
795        {
796                ViewCell *vc = (*vit);
797
798                if (!vc->Mailed())
799                {
800                        //Debug << "single vol: "<< vc->GetVolume() << endl;
801                        vc->Mail();
802                        vc->mCounter = 0;
803                        vol += vc->GetVolume();
804                }
805               
806                // view cell volume already added => just increase counter
807                ++ vc->mCounter;
808        }
809
810        return vol;
811}
812
813
814float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData)
815{       
816        float vol = 0;
817        debugVol = 0;
818       
819        ViewCell::NewMail();
820
821        BvhLeaf *leaf = tData.mNode;
822
823        VssRayContainer rays;
824        CollectRays(leaf->mObjects, rays);
825
826        VssRayContainer::const_iterator rit, rit_end = rays.end();
827
828        for (rit = rays.begin(); rit < rit_end; ++ rit)
829        {
830                VssRay *ray = (*rit);
831
832                const float volContri = PrepareHeuristics(*ray);
833
834                // if hitpoint with one of the objects is inside this node, we
835                // evaluate the volume of the view cells seen by this ray
836                if (ray->mTerminationObject)
837                {
838            vol += volContri;
839                }
840
841                // count double if both hit points are within the kd node
842                if (0 && ray->mOriginObject)
843                {
844                        vol += volContri;
845                }
846        }
847
848        return vol;
849}
850///////////////////////////////////////////////////////////
851
852
853void BvHierarchy::EvalHeuristicsContribution(BvhLeaf *leaf,
854                                                                                         const SortableEntry &ci,
855                                                                                         float &volLeft,
856                                                                                         float &volRight,
857                                                                                         int &objectsLeft)
858{
859        Intersectable *obj = ci.mObject;
860        VssRay *ray = ci.mRay;
861
862        // switch between different types of events
863        switch (ci.mType)
864        {
865                case SortableEntry::OBJECT:
866                        cout << "o";
867                        ci.mObject->Mail();
868                        ++ objectsLeft;
869                        break;
870
871                // compute volume contribution from view cells
872                case SortableEntry::VIEWCELLS:
873                        cout << "v";
874                        // process ray if the hit point with termination / origin object
875                        // is inside this kd leaf
876                        EvalRayContribution(*ray, volLeft, volRight);
877                        break;
878
879                default:
880                        cout << "should not come here" << endl;
881                        break;
882        }
883        //cout << "vol left: " << volLeft << " vol right " << volRight << endl;
884}
885
886
887void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
888{
889        mViewCellsManager = vcm;
890}
891
892
893AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
894{
895        return mBoundingBox;
896}
897
898
899float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
900                                                                                 ObjectContainer &frontObjects,
901                                                                                 ObjectContainer &backObjects)
902{
903        ObjectContainer nFrontObjects[3];
904        ObjectContainer nBackObjects[3];
905
906        float nCostRatio[3];
907
908        // create bounding box of node geometry
909        AxisAlignedBox3 box = tData.mBoundingBox;
910               
911        int sAxis = 0;
912        int bestAxis = -1;
913
914        if (mOnlyDrivingAxis)
915        {
916                sAxis = box.Size().DrivingAxis();
917        }
918       
919        // -- evaluate split cost for all three axis
920       
921        for (int axis = 0; axis < 3; ++ axis)
922        {
923                if (!mOnlyDrivingAxis || (axis == sAxis))
924                {
925                        if (1 || mUseCostHeuristics)
926                        {
927                                //-- partition objects using heuristics
928                               
929                                nCostRatio[axis] =
930                                        EvalLocalCostHeuristics(
931                                                                                        tData,
932                                                                                        axis,
933                                                                                        nFrontObjects[axis],
934                                                                                        nBackObjects[axis]);                   
935                        }
936                        if (bestAxis == -1)
937                        {
938                                bestAxis = axis;
939                        }
940                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
941                        {
942                                bestAxis = axis;
943                        }
944                }
945        }
946
947        //-- assign values
948       
949        frontObjects = nFrontObjects[bestAxis];
950        backObjects = nFrontObjects[bestAxis];
951
952        Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
953        return nCostRatio[bestAxis];
954}
955
956
957void BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays)
958{
959
960        VssRayContainer::const_iterator rit, rit_end = rays.end();
961
962    for (rit = rays.begin(); rit != rays.end(); ++ rit)
963        {
964                VssRay *ray = (*rit);
965
966                if (ray->mTerminationObject)
967                {
968                        ray->mTerminationObject->mVssRays.push_back(ray);
969                }
970
971                if (0 && ray->mOriginObject)
972                {
973                        ray->mOriginObject->mVssRays.push_back(ray);
974                }
975        }
976}
977
978
979void BvHierarchy::EvalSubdivisionStats(const SubdivisionCandidate &sc)
980{
981        const float costDecr = sc.GetRenderCostDecrease();
982
983        AddSubdivisionStats(mBvhStats.Leaves(),
984                                                costDecr,
985                                                mTotalCost
986                                                );
987}
988
989
990void BvHierarchy::AddSubdivisionStats(const int leaves,
991                                                                          const float renderCostDecr,
992                                                                          const float totalRenderCost)
993{
994        mSubdivisionStats
995                        << "#Leaves\n" << leaves << endl
996                        << "#RenderCostDecrease\n" << renderCostDecr << endl
997                        << "#TotalRenderCost\n" << totalRenderCost << endl;
998                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
999}
1000
1001
1002void BvHierarchy::CollectRays(const ObjectContainer &objects,
1003                                                          VssRayContainer &rays) const
1004{
1005        VssRay::NewMail();
1006       
1007        ObjectContainer::const_iterator oit, oit_end = objects.end();
1008
1009        // evaluate reverse pvs and view cell volume on left and right cell
1010        // note: should I take all leaf objects or rather the objects hit by rays?
1011        for (oit = objects.begin(); oit != oit_end; ++ oit)
1012        {
1013                Intersectable *obj = *oit;
1014               
1015                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
1016
1017                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
1018                {
1019                        VssRay *ray = (*rit);
1020
1021                        if (!ray->Mailed())
1022                        {
1023                                ray->Mail();
1024                                rays.push_back(ray);
1025                        }
1026                }
1027        }
1028}
1029
1030
1031void BvHierarchy::MailViewCells(const ObjectContainer &objects,
1032                                                                const bool isFront,
1033                                                                ViewCellContainer &collectedViewCells) const
1034{
1035        VssRayContainer rays;
1036        CollectRays(objects, rays);
1037       
1038        VssRayContainer::const_iterator rit, rit_end = rays.end();
1039
1040        for (rit = rays.begin(); rit < rit_end; ++ rit)
1041        {
1042                VssRay *ray = (*rit);
1043
1044                // view cell is assigned to left and / or right child
1045                ViewCellContainer viewCells;
1046                mVspTree->GetViewCells(*ray, viewCells);
1047                       
1048                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1049
1050                // mail view cell
1051                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1052                {
1053                        ViewCell *vc = *vit;
1054
1055                        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1056                                collectedViewCells.push_back(vc);
1057
1058                        if (isFront)
1059                        {
1060                                if (!vc->Mailed())
1061                                        vc->Mail();
1062                        }
1063                        else
1064                        {
1065                                if (!vc->Mailed())
1066                                        vc->Mail(1);
1067                                else
1068                                        vc->Mail(2);
1069                        }
1070                }                               
1071        }
1072}
1073
1074
1075float BvHierarchy::EvalRenderCostDecrease(const ObjectContainer &objectsFront,
1076                                                                                  const ObjectContainer &objectsBack,
1077                                                                                  const BvhTraversalData &tData,
1078                                                                                  float &normalizedOldRenderCost) const
1079{
1080        // probability that view point lies in back / front node
1081        float pOverall = 0;
1082        float pFront = 0;
1083        float pBack = 0;
1084        float pFrontAndBack = 0;
1085
1086        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
1087
1088        BvhLeaf *leaf = tData.mNode;
1089       
1090        // sum up volume seen from the objects of left and right children
1091        // => the volume is the weight for the render cost equation
1092        ViewCell::NewMail(3);
1093
1094        ViewCellContainer collectedViewCells;
1095        MailViewCells(objectsFront, true, collectedViewCells);
1096        MailViewCells(objectsBack, false, collectedViewCells);
1097
1098        ViewCellContainer::const_iterator vit, vit_end = collectedViewCells.end();
1099
1100        // evaluate view cells volume contribution with respect to the mail id
1101        for (vit = collectedViewCells.begin(); vit != vit_end; ++ vit)
1102        {
1103                AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
1104        }
1105
1106        const int totalObjects = (int)leaf->mObjects.size();
1107        const int nObjectsFront = (int)objectsFront.size();
1108        const int nObjectsBack = (int)objectsBack.size();
1109
1110        // these are non-overlapping sets
1111        pOverall = pFront + pBack + pFrontAndBack;
1112
1113        //-- pvs rendering heuristics
1114        const float oldRenderCost = pOverall * totalObjects;
1115        const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack + totalObjects * pFrontAndBack;
1116
1117        // normalize volume with view space volume
1118        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1119
1120        Debug << "\n(((( eval render cost decrease ))))" << endl
1121                  << "back objects: " << nObjectsBack << " front objects " << nObjectsFront << " total objects: " << totalObjects << endl
1122                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
1123                  << " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1124                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
1125                  << "render cost decrease: " << renderCostDecrease << endl;
1126
1127        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1128
1129        if (oldRenderCost < newRenderCost * 0.99)
1130                Debug << "\nwarning2!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
1131       
1132        return renderCostDecrease;
1133}
1134
1135
1136AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects)
1137{
1138        AxisAlignedBox3 box;
1139        box.Initialize();
1140
1141        ObjectContainer::const_iterator oit, oit_end = objects.end();
1142
1143        //-- compute bounding box
1144        for (oit = objects.begin(); oit != oit_end; ++ oit)
1145        {
1146                Intersectable *obj = *oit;
1147
1148                // compute bounding box of view space
1149                mBoundingBox.Include(obj->GetBox());
1150        }
1151        return box;
1152       
1153}
1154
1155
1156void BvHierarchy::CollectLeaves(vector<BvhLeaf *> &leaves) const
1157{
1158        stack<BvhNode *> nodeStack;
1159        nodeStack.push(mRoot);
1160
1161        while (!nodeStack.empty())
1162        {
1163                BvhNode *node = nodeStack.top();
1164                nodeStack.pop();
1165                if (node->IsLeaf())
1166                {
1167                        BvhLeaf *leaf = (BvhLeaf *)node;
1168                        leaves.push_back(leaf);
1169                }
1170                else
1171                {
1172                        BvhInterior *interior = (BvhInterior *)node;
1173
1174                        nodeStack.push(interior->GetBack());
1175                        nodeStack.push(interior->GetFront());
1176                }
1177        }
1178}
1179
1180
1181AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1182{
1183        return node->GetBoundingBox();
1184}
1185
1186
1187void BvHierarchy::CollectViewCells(BvhLeaf *leaf, ViewCellContainer &viewCells)
1188{
1189        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1190
1191        ViewCell::NewMail();
1192
1193        // loop through all object and collect view cell pvs of this node
1194        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1195        {
1196                Intersectable *obj = *oit;
1197
1198                ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
1199
1200                for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
1201                {
1202            ViewCell *vc = (*vit).first;
1203
1204                        if (!vc->Mailed())
1205                        {
1206                                vc->Mail();
1207                                viewCells.push_back(vc);
1208                        }
1209                }
1210        }
1211}
1212
1213
1214void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1215                                                                                 vector<SubdivisionCandidate *> &dirtyList)
1216{
1217        BvhTraversalData &tData = sc->mParentData;
1218        BvhLeaf *node = tData.mNode;
1219       
1220        ViewCell::NewMail();
1221
1222        ViewCellContainer viewCells;
1223        ViewCellContainer tmpViewCells;
1224
1225        VssRayContainer rays;
1226        CollectRays(node->mObjects, rays);
1227
1228        VssRayContainer::const_iterator rit, rit_end = rays.end();
1229
1230        // find all view cells associated with the rays, add them to view cells
1231        for (rit = rays.begin(); rit != rit_end; ++ rit)
1232        {
1233                VssRay *ray = (*rit);
1234                mVspTree->GetViewCells(*ray, tmpViewCells);
1235
1236                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1237
1238                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1239                {
1240                        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1241
1242                        if (!vc->Mailed())
1243                        {
1244                                vc->Mail();
1245                                viewCells.push_back(vc);
1246                        }
1247                }
1248        }
1249
1250
1251        // split candidates holding this view cells
1252        // are thrown into dirty list
1253        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1254
1255        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1256        {
1257                VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1258
1259                VspLeaf *leaf = vc->mLeaf;
1260                dirtyList.push_back(leaf->GetSubdivisionCandidate());
1261        }
1262}
1263
1264
1265BvhNode *BvHierarchy::GetRoot() const
1266{
1267        return mRoot;
1268}
1269
1270
1271bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
1272{
1273        ObjectContainer::const_iterator oit =
1274                lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1275                               
1276        // objects sorted by id
1277        if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1278        {
1279                return true;
1280        }
1281        else
1282        {
1283                return false;
1284        }
1285}
1286
1287
1288BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
1289{
1290        // rather use the simple version
1291        return object->mBvhLeaf;
1292
1293        ///////////////////////////////////////
1294        // start from root of tree
1295        if (node == NULL)
1296        {
1297                node = mRoot;
1298        }
1299
1300        vector<BvhLeaf *> leaves;
1301
1302        stack<BvhNode *> nodeStack;
1303        nodeStack.push(node);
1304 
1305        BvhLeaf *leaf = NULL;
1306 
1307        while (!nodeStack.empty()) 
1308        {
1309                BvhNode *node = nodeStack.top();
1310                nodeStack.pop();
1311       
1312                if (node->IsLeaf())
1313                {
1314                        leaf = dynamic_cast<BvhLeaf *>(node);
1315
1316                        if (IsObjectInLeaf(leaf, object))
1317                                return leaf;
1318                }
1319                else   
1320                {       
1321                        // find point
1322                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1323       
1324                        if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
1325                        {
1326                                nodeStack.push(interior->GetBack());
1327                        }
1328                       
1329                        // search both sides as we are using bounding volumes
1330                        if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
1331                        {
1332                                nodeStack.push(interior->GetFront());
1333                        }
1334                }
1335        }
1336 
1337        return leaf;
1338}
1339
1340
1341BvhIntersectable *BvHierarchy::GetOrCreateBvhIntersectable(BvhNode *node)
1342{
1343        // search nodes
1344        std::map<BvhNode *, BvhIntersectable *>::
1345                const_iterator it = mBvhIntersectables.find(node);
1346
1347        if (it != mBvhIntersectables.end())
1348        {
1349                return (*it).second;
1350        }
1351
1352        // not in map => create new entry
1353        BvhIntersectable *bvhObj = new BvhIntersectable(node);
1354        mBvhIntersectables[node] = bvhObj;
1355
1356        return bvhObj;
1357}
1358
1359
1360void BvHierarchy::AddViewCellVolumeContri(ViewCell *vc,
1361                                                                                  float &frontVol,
1362                                                                                  float &backVol,
1363                                                                                  float &frontAndBackVol) const
1364{
1365        if (vc->Mailed())
1366        {
1367                frontVol += vc->GetVolume();
1368        }
1369        else if (vc->Mailed(1))
1370        {
1371                backVol += vc->GetVolume();
1372        }
1373        else if (vc->Mailed(2))
1374        {
1375                frontAndBackVol += vc->GetVolume();
1376        }
1377}
1378
1379/*
1380int BvHierarchy::UpdateViewCellsPvs(BvhLeaf *leaf,
1381                                                                const RayInfoContainer &rays) const
1382
1383{
1384        MailablePvsData::NewMail();
1385       
1386        ViewCellContainer touchedViewCells;
1387        CollectTouchedViewCells(rays, touchedViewCells);
1388
1389        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1390
1391        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
1392        {
1393                Intersectable *obj = *oit;
1394                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1395
1396                // traverse through view cells and classify them according
1397                // to them being seen from to back / front / front and back node
1398                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1399                {
1400                        ViewCell *vc = *vit;
1401                        float contri;
1402                        AddViewCellToObjectPvs(obj, vc, contri, true);
1403                }
1404        }
1405
1406        return 0;
1407}
1408
1409
1410int BvHierarchy::RemoveParentViewCellsPvs(BvhLeaf *leaf,
1411                                                                          const RayInfoContainer &rays
1412                                                                          ) const
1413
1414{
1415        MailablePvsData::NewMail();
1416       
1417        ViewCellContainer touchedViewCells;
1418        CollectTouchedViewCells(rays, touchedViewCells);
1419
1420        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1421
1422        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1423        {
1424                Intersectable *obj = *oit;
1425
1426                // traverse through view cells and classify them according
1427                // to them being seen from to back / front / front and back node
1428        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1429
1430                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1431                {
1432                        ViewCell *vc = *vit;
1433                       
1434                        MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
1435
1436                        if (vdata && !vdata->Mailed())
1437                        {
1438                                vdata->Mail();
1439                                obj->mViewCellPvs.RemoveSample(vc, 1);
1440                        }
1441                }
1442        }
1443
1444        return 0;
1445}
1446*/
1447
1448bool BvHierarchy::Export(OUT_STREAM &stream)
1449{
1450        ExportNode(mRoot, stream);
1451
1452        return true;
1453}
1454
1455
1456void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
1457{
1458        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1459        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1460        {
1461                stream << (*oit)->GetId() << " ";
1462        }
1463}
1464
1465
1466void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
1467{
1468        if (node->IsLeaf())
1469        {
1470                BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
1471
1472                stream << "<Leaf"
1473                           << " min=\"" << leaf->GetBoundingBox().Min()
1474                           << " max=\"" << leaf->GetBoundingBox().Max()
1475                           << " objects=\"";
1476               
1477                //-- export objects
1478                ExportObjects(leaf, stream);
1479               
1480                stream << "\" />" << endl;
1481        }
1482        else
1483        {       
1484                BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1485       
1486                stream << "<Interior"
1487                           << " min=\"" << interior->GetBoundingBox().Min()
1488                           << " max=\"" << interior->GetBoundingBox().Max()
1489                           << "\">" << endl;
1490
1491                ExportNode(interior->GetBack(), stream);
1492                ExportNode(interior->GetFront(), stream);
1493
1494                stream << "</Interior>" << endl;
1495        }
1496}
1497
1498
1499float BvHierarchy::EvalViewCellsVolume(BvhLeaf *leaf) const
1500{
1501        float vol = 0;
1502
1503        VssRayContainer rays;
1504        CollectRays(leaf->mObjects, rays);
1505
1506        ViewCell::NewMail();
1507
1508        VssRayContainer::const_iterator rit, rit_end = rays.end();
1509
1510        for (rit = rays.begin(); rit < rit_end; ++ rit)
1511        {
1512                VssRay *ray = (*rit);
1513       
1514                ViewCellContainer viewCells;
1515                mVspTree->GetViewCells(*ray, viewCells);
1516       
1517                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1518
1519                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1520                {
1521                        ViewCell *vc = (*vit);
1522
1523                        if (!vc->Mailed())
1524                        {
1525                                //Debug << "single vol: "<< vc->GetVolume() << endl;
1526                                vc->Mail();
1527                                vol += vc->GetVolume();
1528                        }
1529                }
1530        }
1531
1532        return vol;
1533}
1534
1535
1536SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
1537                                                                                                           ObjectContainer &objects,
1538                                                                                                           AxisAlignedBox3 *forcedObjectSpace
1539                                                                                                           //, RayInfoContainer &rays
1540                                                                                                           )
1541{
1542        // store pointer to this tree
1543        BvhSubdivisionCandidate::sBvHierarchy = this;
1544        mBvhStats.nodes = 1;
1545
1546        // compute bounding box from objects
1547        if (forcedObjectSpace)
1548                mBoundingBox = *forcedObjectSpace;
1549        else
1550                mBoundingBox = ComputeBoundingBox(objects);
1551
1552        mTermMinVolume *= mBoundingBox.GetVolume();
1553        mGlobalCostMisses = 0;
1554
1555        // sort objects by id in order to have sorted objects in
1556        // the leaf nodes
1557        stable_sort(objects.begin(), objects.end(), ilt);
1558
1559        //-- create new root
1560
1561        BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
1562        bvhleaf->mObjects = objects;
1563        mRoot = bvhleaf;
1564
1565        // only rays intersecting objects in node are interesting
1566        AssociateObjectsWithRays(sampleRays);
1567        // associate root with current objects
1568        AssociateObjectsWithLeaf(bvhleaf);
1569
1570        //-- add first candidate for object space partition
1571
1572        // create osp traversal data
1573        BvhTraversalData oData(bvhleaf, 0, mBoundingBox.GetVolume());
1574
1575        //-- first split candidate
1576        BvhSubdivisionCandidate *oSubdivisionCandidate =
1577                new BvhSubdivisionCandidate(oData);
1578
1579        //UpdateViewCellsPvs(kdleaf, rays);
1580
1581        EvalSubdivisionCandidate(*oSubdivisionCandidate);
1582
1583// probabilty is voume of all "seen" view cells
1584#if 1
1585        const float prop = EvalViewCellsVolume(bvhleaf);
1586#else
1587        const float prop = GetBoundingBox().GetVolume();
1588#endif
1589        mTotalCost = (float)objects.size() * prop /
1590                mVspTree->GetBoundingBox().GetVolume();
1591
1592        EvalSubdivisionStats(*oSubdivisionCandidate);
1593
1594        return oSubdivisionCandidate;
1595}
1596
1597
1598bool BvHierarchy::AddLeafToPvs(BvhLeaf *leaf,
1599                                                           ViewCell *vc,
1600                                                           const float pdf,
1601                                                           float &contribution)
1602{
1603        // add kd intersecable to pvs
1604        BvhIntersectable *bvhObj = GetOrCreateBvhIntersectable(leaf);
1605       
1606        return vc->AddPvsSample(bvhObj, pdf, contribution);
1607}
1608
1609
1610void BvhStatistics::Print(ostream &app) const
1611{
1612        app << "=========== OspTree statistics ===============\n";
1613
1614        app << setprecision(4);
1615
1616        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
1617
1618        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
1619
1620        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1621
1622        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1623
1624        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
1625
1626       
1627        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
1628                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
1629
1630        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n"
1631                << minPvsNodes * 100 / (double)Leaves() << endl;
1632
1633        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
1634                << maxCostNodes * 100 / (double)Leaves() << endl;
1635
1636        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
1637                << minProbabilityNodes * 100 / (double)Leaves() << endl;
1638
1639        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
1640
1641        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
1642
1643        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
1644
1645        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
1646
1647        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
1648
1649        //app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
1650       
1651        app << "========== END OF VspTree statistics ==========\n";
1652}
1653
1654
1655}
Note: See TracBrowser for help on using the repository browser.