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

Revision 1687, 58.2 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#include "HierarchyManager.h"
20
21
22namespace GtpVisibilityPreprocessor {
23
24
25#define PROBABILIY_IS_BV_VOLUME 1
26#define USE_FIXEDPOINT_T 0
27#define USE_VOLUMES_FOR_HEURISTICS 1
28
29int BvhNode::sMailId = 10000; //2147483647;
30int BvhNode::sReservedMailboxes = 1;
31
32BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
33
34
35/// sorting operator
36inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
37{
38        return obj1->mId < obj2->mId;
39}
40
41
42/***************************************************************/
43/*              class BvhNode implementation                   */
44/***************************************************************/
45
46BvhNode::BvhNode():
47mParent(NULL),
48mMailbox(0),
49mRenderCostDecr(0),
50mMemoryIncr(0),
51mPvsEntriesIncr(0),
52mTimeStamp(0)
53{
54}
55
56BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
57mParent(NULL),
58mBoundingBox(bbox),
59mMailbox(0),
60mMemoryIncr(0),
61mPvsEntriesIncr(0),
62mTimeStamp(0)
63{
64}
65
66
67BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
68mBoundingBox(bbox),
69mParent(parent),
70mMailbox(0),
71mMemoryIncr(0),
72mPvsEntriesIncr(0),
73mTimeStamp(0)
74{
75}
76
77
78bool BvhNode::IsRoot() const
79{
80        return mParent == NULL;
81}
82
83
84BvhInterior *BvhNode::GetParent()
85{
86        return mParent;
87}
88
89
90void BvhNode::SetParent(BvhInterior *parent)
91{
92        mParent = parent;
93}
94
95
96
97/******************************************************************/
98/*              class BvhInterior implementation                  */
99/******************************************************************/
100
101
102BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
103BvhNode(bbox), mSubdivisionCandidate(NULL)
104{
105}
106
107
108BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
109BvhNode(bbox, parent)
110{
111}
112
113
114BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox,
115                                 BvhInterior *parent,
116                                 const int numObjects):
117BvhNode(bbox, parent)
118{
119        mObjects.reserve(numObjects);
120}
121
122
123bool BvhLeaf::IsLeaf() const
124{
125        return true;
126}
127
128
129BvhLeaf::~BvhLeaf()
130{
131}
132
133
134void BvhLeaf::CollectObjects(ObjectContainer &objects)
135{
136        ObjectContainer::const_iterator oit, oit_end = mObjects.end();
137        for (oit = mObjects.begin(); oit != oit_end; ++ oit)
138        {
139                objects.push_back(*oit);
140        }
141}
142
143/******************************************************************/
144/*              class BvhInterior implementation                  */
145/******************************************************************/
146
147
148BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
149BvhNode(bbox), mFront(NULL), mBack(NULL)
150{
151}
152
153
154BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
155BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
156{
157}
158
159
160void BvhInterior::ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild)
161{
162        if (mBack == oldChild)
163                mBack = newChild;
164        else
165                mFront = newChild;
166}
167
168
169bool BvhInterior::IsLeaf() const
170{
171        return false;
172}
173
174
175BvhInterior::~BvhInterior()
176{
177        DEL_PTR(mFront);
178        DEL_PTR(mBack);
179}
180
181
182void BvhInterior::SetupChildLinks(BvhNode *front, BvhNode *back)
183{
184    mBack = back;
185    mFront = front;
186}
187
188
189void BvhInterior::CollectObjects(ObjectContainer &objects)
190{
191        mFront->CollectObjects(objects);
192        mBack->CollectObjects(objects);
193}
194
195
196/*******************************************************************/
197/*                  class BvHierarchy implementation               */
198/*******************************************************************/
199
200
201BvHierarchy::BvHierarchy():
202mRoot(NULL),
203mTimeStamp(1)
204{
205        ReadEnvironment();
206        mSubdivisionCandidates = new SortableEntryContainer;
207        for (int i = 0; i < 3; ++ i)
208                mSortedObjects[i] = NULL;
209}
210
211
212BvHierarchy::~BvHierarchy()
213{
214        // delete kd intersectables
215        BvhIntersectableMap::iterator it, it_end = mBvhIntersectables.end();
216
217        for (it = mBvhIntersectables.begin(); it != mBvhIntersectables.end(); ++ it)
218        {
219                DEL_PTR((*it).second);
220        }
221
222        DEL_PTR(mSubdivisionCandidates);
223
224        for (int i = 0; i < 3; ++ i)
225        {
226                DEL_PTR(mSortedObjects[i]);
227        }
228        mSubdivisionStats.close();
229}
230
231
232void BvHierarchy::ReadEnvironment()
233{
234        bool randomize = false;
235        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
236        if (randomize)
237                Randomize(); // initialise random generator for heuristics
238
239
240        ////////////////////////////////////
241        //-- termination criteria for autopartition
242
243        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
244        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
245        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
246        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
247        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minProbability", mTermMinProbability);
248       
249        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
250
251
252        //////////////////////////////
253        //-- max cost ratio for early tree termination
254
255        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
256        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
257                mTermMinGlobalCostRatio);
258        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance",
259                mTermGlobalCostMissTolerance);
260
261
262        //////////////////////////////
263        //-- factors for subdivision heuristics
264
265        // if only the driving axis is used for splits
266        Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
267        Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
268        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
269        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);
270
271    char subdivisionStatsLog[100];
272        Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
273        mSubdivisionStats.open(subdivisionStatsLog);
274
275        Environment::GetSingleton()->GetFloatValue(
276                "BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
277       
278        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
279        Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
280       
281
282        mUseBboxAreaForSah = true;
283
284        /////////////
285        //-- debug output
286
287        Debug << "******* Bvh hierarchy options ******** " << endl;
288    Debug << "max depth: " << mTermMaxDepth << endl;
289        Debug << "min probabiliy: " << mTermMinProbability<< endl;
290        Debug << "min objects: " << mTermMinObjects << endl;
291        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
292        Debug << "miss tolerance: " << mTermMissTolerance << endl;
293        Debug << "max leaves: " << mTermMaxLeaves << endl;
294        Debug << "randomize: " << randomize << endl;
295        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
296        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
297        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
298        Debug << "max memory: " << mMaxMemory << endl;
299        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
300        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
301        Debug << "split borders: " << mSplitBorder << endl;
302        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
303        Debug << "use global sort: " << mUseGlobalSorting << endl;
304        Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
305
306        Debug << endl;
307}
308
309
310void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
311{
312        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
313        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
314        {
315                (*oit)->mBvhLeaf = leaf;
316        }
317}
318
319
320static int CountRays(const ObjectContainer &objects)
321{
322        int nRays = 0;
323
324        ObjectContainer::const_iterator oit, oit_end = objects.end();
325
326        for (oit = objects.begin(); oit != oit_end; ++ oit)
327        {
328                nRays += (int)(*oit)->mVssRays.size();
329        }
330
331        return nRays;
332}
333                                                                       
334
335BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
336                                                                                BvhTraversalData &frontData,
337                                                                                BvhTraversalData &backData)
338{
339        const BvhTraversalData &tData = sc.mParentData;
340        BvhLeaf *leaf = tData.mNode;
341        AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
342
343        // update stats: we have two new leaves
344        mBvhStats.nodes += 2;
345
346        if (tData.mDepth > mBvhStats.maxDepth)
347        {
348                mBvhStats.maxDepth = tData.mDepth;
349        }
350
351        // add the new nodes to the tree
352        BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
353       
354
355        //////////////////
356        //-- create front and back leaf
357
358        AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
359        AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
360
361        BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
362        BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
363
364        BvhInterior *parent = leaf->GetParent();
365
366        // replace a link from node's parent
367        if (parent)
368        {
369                parent->ReplaceChildLink(leaf, node);
370                node->SetParent(parent);
371        }
372        else // no parent => this node is the root
373        {
374                mRoot = node;
375        }
376
377        // and setup child links
378        node->SetupChildLinks(front, back);
379
380        ++ mBvhStats.splits;
381
382
383        ////////////////////////////////////////
384        //-- fill  front and back traversal data with the new values
385
386        frontData.mDepth = backData.mDepth = tData.mDepth + 1;
387
388        frontData.mNode = front;
389        backData.mNode = back;
390
391        back->mObjects = sc.mBackObjects;
392        front->mObjects = sc.mFrontObjects;
393
394        // if the number of rays is too low, no assumptions can be made
395        // (=> switch to surface area heuristics?)
396        frontData.mNumRays = CountRays(sc.mFrontObjects);
397        backData.mNumRays = CountRays(sc.mBackObjects);
398
399        AssociateObjectsWithLeaf(back);
400        AssociateObjectsWithLeaf(front);
401   
402#if PROBABILIY_IS_BV_VOLUME
403        // volume of bvh (= probability that this bvh can be seen)
404        frontData.mProbability = fbox.GetVolume();
405        backData.mProbability = bbox.GetVolume();
406#else
407        // compute probability of this node being visible,
408        // i.e., volume of the view cells that can see this node
409        frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
410        backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
411#endif
412
413    // how often was max cost ratio missed in this branch?
414        frontData.mMaxCostMisses = sc.GetMaxCostMisses();
415        backData.mMaxCostMisses = sc.GetMaxCostMisses();
416       
417        // set the time stamp so the order of traversal can be reconstructed
418        node->mTimeStamp = mHierarchyManager->mTimeStamp ++;
419               
420        // assign the objects in sorted order
421        if (mUseGlobalSorting)
422        {
423                AssignSortedObjects(sc, frontData, backData);
424        }
425       
426        // return the new interior node
427        return node;
428}
429
430
431BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
432                                                                SubdivisionCandidate *splitCandidate,
433                                                                const bool globalCriteriaMet)
434{
435        BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
436        BvhTraversalData &tData = sc->mParentData;
437
438        BvhNode *currentNode = tData.mNode;
439
440        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
441        {       
442                //////////////
443                //-- continue subdivision
444
445                BvhTraversalData tFrontData;
446                BvhTraversalData tBackData;
447                       
448                // create new interior node and two leaf node
449                currentNode = SubdivideNode(*sc, tFrontData, tBackData);
450       
451                // decrease the weighted average cost of the subdivisoin
452                mTotalCost -= sc->GetRenderCostDecrease();
453                mPvsEntries += sc->GetPvsEntriesIncr();
454
455                // subdivision statistics
456                if (1) PrintSubdivisionStats(*sc);
457
458
459                ///////////////////////////
460                //-- push the new split candidates on the queue
461               
462                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
463                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
464
465                EvalSubdivisionCandidate(*frontCandidate);
466                EvalSubdivisionCandidate(*backCandidate);
467       
468                // cross reference
469                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
470                tBackData.mNode->SetSubdivisionCandidate(backCandidate);
471
472                //cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
473                tQueue.Push(frontCandidate);
474                tQueue.Push(backCandidate);
475        }
476
477        /////////////////////////////////
478        //-- node is a leaf => terminate traversal
479
480        if (currentNode->IsLeaf())
481        {
482                /////////////////////
483                //-- store additional info
484                EvaluateLeafStats(tData);
485       
486                const bool mStoreRays = true;
487                if (mStoreRays)
488                {
489                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(currentNode);
490                        CollectRays(leaf->mObjects, leaf->mVssRays);
491                }
492               
493                //////////////////////////////////////
494               
495                // this leaf is no candidate for splitting anymore
496                // => detach subdivision candidate
497                tData.mNode->SetSubdivisionCandidate(NULL);
498                // detach node so we don't delete it with the traversal data
499                tData.mNode = NULL;
500        }
501       
502        return currentNode;
503}
504
505
506void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate,
507                                                                                   bool computeSplitPlane)
508{
509        if (computeSplitPlane)
510        {
511                const bool sufficientSamples = splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;
512
513                const bool useVisibiliyBasedHeuristics =
514                        !mUseSah &&
515                        (mHierarchyManager->GetViewSpaceSubdivisionType() == HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
516                        sufficientSamples;
517
518                // compute best object partition
519                const float ratio =     SelectObjectPartition(splitCandidate.mParentData,
520                                                                                                  splitCandidate.mFrontObjects,
521                                                                                                  splitCandidate.mBackObjects,
522                                                                                                  useVisibiliyBasedHeuristics);
523       
524                // cost ratio violated?
525                const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
526
527                const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
528
529                splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? previousMisses + 1 : previousMisses);
530
531        }
532
533        BvhLeaf *leaf = splitCandidate.mParentData.mNode;
534
535        const float oldProp = EvalViewCellsVolume(leaf->mObjects);
536        const float oldRenderCost = EvalRenderCost(leaf->mObjects);
537               
538        // compute global decrease in render cost
539        const float newRenderCost = EvalRenderCost(splitCandidate.mFrontObjects) +
540                                                                EvalRenderCost(splitCandidate.mBackObjects);
541
542        const float renderCostDecr = oldRenderCost - newRenderCost;
543       
544        splitCandidate.SetRenderCostDecrease(renderCostDecr);
545
546        // increase in pvs entries
547        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
548        splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
549
550#ifdef _DEBUG
551        Debug << "old render cost: " << oldRenderCost << endl;
552        Debug << "new render cost: " << newRenderCost << endl;
553        Debug << "render cost decrease: " << renderCostDecr << endl;
554#endif
555
556        float priority;
557
558        // surface area heuristics is used when there is no view space subdivision available.
559        // In order to have some prioritized traversal, use this formula instead
560        if (mHierarchyManager->GetViewSpaceSubdivisionType() ==
561                HierarchyManager::NO_VIEWSPACE_SUBDIV)
562        {
563                ////////////////
564                //-- surface area heuristics
565
566                const AxisAlignedBox3 box = EvalBoundingBox(leaf->mObjects);
567                const float area = box.SurfaceArea();
568                const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
569
570                priority = (float)leaf->mObjects.size() * area / viewSpaceArea;
571        }
572        else
573        {
574                // take render cost of node into account
575                // otherwise danger of being stuck in a local minimum!
576                const float factor = mRenderCostDecreaseWeight;
577                priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
578
579                if (mHierarchyManager->mConsiderMemory2)
580                {
581                        priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mHierarchyManager->mMemoryConst);
582                }
583        }
584
585        // compute global decrease in render cost
586        splitCandidate.SetPriority(priority);
587}
588
589
590int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
591{
592        const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
593       
594        const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
595        const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);
596
597        return fPvsSize + bPvsSize - oldPvsSize;
598}
599
600
601inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
602{
603        return ( 0
604                        || ((int)data.mNode->mObjects.size() <= mTermMinObjects)
605                        //|| (data.mProbability <= mTermMinProbability)
606                        || (data.mNumRays <= mTermMinRays)
607                 );
608}
609
610
611inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
612{
613        // note: tracking for global cost termination
614        // does not make much sense for interleaved vsp / osp partition
615        // as it is the responsibility of the hierarchy manager
616
617        const bool terminationCriteriaMet =
618                (0
619                || (mBvhStats.Leaves() >= mTermMaxLeaves)
620                //|| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
621                //|| mOutOfMemory
622                );
623
624#ifdef _DEBUG
625        if (terminationCriteriaMet)
626        {
627                Debug << "bvh global termination criteria met:" << endl;
628                Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
629                Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
630        }
631#endif
632        return terminationCriteriaMet;
633}
634
635
636void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
637{
638        // the node became a leaf -> evaluate stats for leafs
639        BvhLeaf *leaf = data.mNode;
640       
641        ++ mCreatedLeaves;
642
643       
644        if (data.mProbability <= mTermMinProbability)
645        {
646                ++ mBvhStats.minProbabilityNodes;
647        }
648
649        ////////////////////////////////////////////
650        // depth related stuff
651
652        if (data.mDepth < mBvhStats.minDepth)
653        {
654                mBvhStats.minDepth = data.mDepth;
655        }
656
657        if (data.mDepth >= mTermMaxDepth)
658        {
659        ++ mBvhStats.maxDepthNodes;
660        }
661
662        // accumulate depth to compute average depth
663        mBvhStats.accumDepth += data.mDepth;
664
665
666        ////////////////////////////////////////////
667        // objects related stuff
668
669        // note: this number should always accumulate to the total number of objects
670        mBvhStats.objectRefs += (int)leaf->mObjects.size();
671
672        if ((int)leaf->mObjects.size() <= mTermMinObjects)
673        {
674             ++ mBvhStats.minObjectsNodes;
675        }
676
677        if (leaf->mObjects.empty())
678        {
679                ++ mBvhStats.emptyNodes;
680        }
681
682        if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
683        {
684                mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
685        }
686
687        if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
688        {
689                mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
690        }
691
692        ////////////////////////////////////////////
693        // ray related stuff
694
695        // note: this number should always accumulate to the total number of rays
696        mBvhStats.rayRefs += data.mNumRays;
697       
698        if (data.mNumRays <= mTermMinRays)
699        {
700             ++ mBvhStats.minRaysNodes;
701        }
702
703        if (data.mNumRays > mBvhStats.maxRayRefs)
704        {
705                mBvhStats.maxRayRefs = data.mNumRays;
706        }
707
708        if (data.mNumRays < mBvhStats.minRayRefs)
709        {
710                mBvhStats.minRayRefs = data.mNumRays;
711        }
712
713#if 0
714        cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size()
715                 << " rays: " << data.mNumRays << " rays / objects "
716                 << (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
717#endif
718}
719
720
721#if 0
722
723/// compute object boundaries using spatial mid split
724float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
725                                                                                        const int axis,
726                                                                                        ObjectContainer &objectsFront,
727                                                                                        ObjectContainer &objectsBack)
728{
729        const float maxBox = tData.mBoundingBox.Max(axis);
730        const float minBox = tData.mBoundingBox.Min(axis);
731
732        float midPoint = (maxBox + minBox) * 0.5f;
733
734        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
735       
736        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
737        {
738                Intersectable *obj = *oit;
739                const AxisAlignedBox3 box = obj->GetBox();
740
741                const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
742
743                // object mailed => belongs to back objects
744                if (objMid < midPoint)
745                {
746                        objectsBack.push_back(obj);
747                }
748                else
749                {
750                        objectsFront.push_back(obj);
751                }
752        }
753
754        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
755        const float newRenderCost =
756                EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
757
758        const float ratio = newRenderCost / oldRenderCost;
759        return ratio;
760}
761
762#else
763
764/// compute object partition by getting balanced objects on the left and right side
765float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
766                                                                                        const int axis,
767                                                                                        ObjectContainer &objectsFront,
768                                                                                        ObjectContainer &objectsBack)
769{
770        PrepareLocalSubdivisionCandidates(tData, axis);
771       
772        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
773
774        int i = 0;
775        const int border = (int)tData.mNode->mObjects.size() / 2;
776
777    for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
778        {
779                Intersectable *obj = (*cit).mObject;
780
781                // object mailed => belongs to back objects
782                if (i < border)
783                {
784                        objectsBack.push_back(obj);
785                }
786                else
787                {
788                        objectsFront.push_back(obj);
789                }
790        }
791
792        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
793        const float newRenderCost = EvalRenderCost(objectsFront) + EvalRenderCost(objectsBack);
794
795        const float ratio = newRenderCost / oldRenderCost;
796        return ratio;
797}
798#endif
799
800
801float BvHierarchy::EvalSah(const BvhTraversalData &tData,
802                                                   const int axis,
803                                                   ObjectContainer &objectsFront,
804                                                   ObjectContainer &objectsBack)
805{
806        // go through the lists, count the number of objects left and right
807        // and evaluate the following cost funcion:
808        // C = ct_div_ci  + (ol + or)/queries
809        PrepareLocalSubdivisionCandidates(tData, axis);
810
811        int objectsLeft = 0, objectsRight = (int)tData.mNode->mObjects.size();
812 
813        const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
814
815        const float minBox = nodeBbox.Min(axis);
816        const float maxBox = nodeBbox.Max(axis);
817        const float boxArea = nodeBbox.SurfaceArea();
818
819        float minSum = 1e20f;
820 
821        float minBorder = maxBox;
822        float maxBorder = minBox;
823        float areaLeft = 0, areaRight = 0;
824
825        SortableEntryContainer::const_iterator currentPos =
826                mSubdivisionCandidates->begin();
827       
828        vector<float> bordersRight;
829
830        if (mUseBboxAreaForSah)
831        {
832                // we keep track of both borders of the bounding boxes =>
833                // store the events in descending order
834
835                bordersRight.resize(mSubdivisionCandidates->size());
836
837                SortableEntryContainer::reverse_iterator rcit =
838                        mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
839       
840                vector<float>::reverse_iterator rbit = bordersRight.rbegin();
841       
842                for (; rcit != rcit_end; ++ rcit, ++ rbit)
843                {
844                        Intersectable *obj = (*rcit).mObject;
845                        const AxisAlignedBox3 obox = obj->GetBox();
846
847                        if (obox.Min(axis) < minBorder)
848                        {
849                                minBorder = obox.Min(axis);
850                        }
851
852                        (*rbit) = minBorder;
853                }
854        }
855
856        // temporary surface areas
857        float al = 0;
858        float ar = boxArea;
859
860        vector<float>::const_iterator bit = bordersRight.begin();
861        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
862
863        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
864        {
865                Intersectable *obj = (*cit).mObject;
866
867                ++ objectsLeft;
868                -- objectsRight;
869
870                const AxisAlignedBox3 obox = obj->GetBox();
871
872                if (mUseBboxAreaForSah)
873                {
874                        AxisAlignedBox3 lbox = nodeBbox;
875                        AxisAlignedBox3 rbox = nodeBbox;
876       
877                        // the borders of the bounding boxes have changed
878                        if (obox.Max(axis) > maxBorder)
879                        {
880                                maxBorder = obox.Max(axis);
881                        }
882
883                        minBorder = (*bit);
884
885                        lbox.SetMax(axis, maxBorder);
886                        rbox.SetMin(axis, minBorder);
887       
888                        al = lbox.SurfaceArea();
889                        ar = rbox.SurfaceArea();
890                }
891                else
892                {
893                        // just add up areas of the objects itself
894                        // (as we are not sampling volumetric visibility,
895                        // this should provide better heuristics
896                        const float area = obj->GetArea();//obox.SurfaceArea();
897
898                        al += area;
899                        ar -= area;
900                }
901
902                const float sum = objectsLeft * al + objectsRight * ar;
903     
904                /*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
905                         << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
906                cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
907            cout << "cost= " << sum << endl;
908*/
909                if (sum < minSum)
910                {
911                        minSum = sum;
912                        areaLeft = al;
913                        areaRight = ar;
914                        // objects belong to left side now
915                        for (; currentPos != (cit + 1); ++ currentPos);
916                }
917        }
918
919
920        ////////////////////////////////////////////
921        //-- assign object to front and back volume
922
923        // belongs to back bv
924        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
925                objectsBack.push_back((*cit).mObject);
926       
927        // belongs to front bv
928        for (cit = currentPos; cit != cit_end; ++ cit)
929                objectsFront.push_back((*cit).mObject);
930
931        float oldCost = (float)tData.mNode->mObjects.size();
932        float newCost = minSum / boxArea;
933        float ratio = newCost / oldCost;
934 
935#ifdef _DEBUG
936        cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
937                 << (int)tData.mNode->mObjects.size() << ")\t area=("
938                 << areaLeft << "," << areaRight << ")" << endl
939                 << "cost= " << minSum << endl;
940#endif
941
942  return ratio;
943}
944
945
946static bool PrepareOutput(const int axis,
947                                                  const int leaves,
948                                                  ofstream &sumStats,
949                                                  ofstream &vollStats,
950                                                  ofstream &volrStats)
951{
952        if ((axis == 0) && (leaves > 0) && (leaves < 90))
953        {
954                char str[64];   
955                sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
956                sumStats.open(str);
957                sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
958                vollStats.open(str);
959                sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
960                volrStats.open(str);
961        }
962
963        return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
964}
965
966
967static void PrintHeuristics(const int objectsRight,
968                                                        const float sum,
969                                                        const float volLeft,
970                                                        const float volRight,
971                                                        const float viewSpaceVol,
972                                                        ofstream &sumStats,
973                                                        ofstream &vollStats,
974                                                        ofstream &volrStats)
975{
976        sumStats
977                << "#Position\n" << objectsRight << endl
978                << "#Sum\n" << sum / viewSpaceVol << endl
979                << "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
980
981        vollStats
982                << "#Position\n" << objectsRight << endl
983                << "#Vol\n" << volLeft / viewSpaceVol << endl;
984
985        volrStats
986                << "#Position\n" << objectsRight << endl
987                << "#Vol\n" << volRight / viewSpaceVol << endl;
988}
989
990
991float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
992                                                                                   const int axis,
993                                                                                   ObjectContainer &objectsFront,
994                                                                                   ObjectContainer &objectsBack)
995{
996        ////////////////////////////////////////////////////////////////
997        // go through the lists, count the number of objects left and right
998        // and evaluate the cost funcion
999
1000        // prepare the heuristics by setting mailboxes and counters.
1001        const float totalVol = PrepareHeuristics(tData, axis);
1002       
1003        // local helper variables
1004        float volLeft = 0;
1005        float volRight = totalVol;
1006        int nObjectsLeft = 0;
1007        const int nTotalObjects = (int)tData.mNode->mObjects.size();
1008        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1009
1010        SortableEntryContainer::const_iterator backObjectsStart =
1011                mSubdivisionCandidates->begin();
1012
1013        /////////////////////////////////
1014        //-- the parameters for the current optimum
1015
1016        float volBack = volLeft;
1017        float volFront = volRight;
1018        float newRenderCost = nTotalObjects * totalVol;
1019
1020#ifdef _DEBUG
1021        ofstream sumStats;
1022        ofstream vollStats;
1023        ofstream volrStats;
1024
1025        const bool printStats =
1026                PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
1027#endif
1028
1029        ///////////////////////////////////////////////////
1030        //-- the sweep heuristics
1031        //-- traverse through events and find best split plane
1032
1033        SortableEntryContainer::const_iterator cit, cit_end = cit_end = mSubdivisionCandidates->end();
1034
1035        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
1036        {
1037                Intersectable *object = (*cit).mObject;
1038       
1039                // evaluate change in l and r volume
1040                // voll = view cells that see only left node (i.e., left pvs)
1041                // volr = view cells that see only right node (i.e., right pvs)
1042                EvalHeuristicsContribution(object, volLeft, volRight);
1043
1044                ++ nObjectsLeft;
1045                const int nObjectsRight = nTotalObjects - nObjectsLeft;
1046
1047                // the heuristics
1048            const float sum = volLeft * (float)nObjectsLeft +
1049                                                  volRight * (float)nObjectsRight;
1050
1051#ifdef _DEBUG
1052                if (printStats)
1053                {
1054                        PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
1055                                                        sumStats, vollStats, volrStats);
1056                }
1057#endif
1058
1059                if (sum < newRenderCost)
1060                {
1061                        newRenderCost = sum;
1062
1063                        volBack = volLeft;
1064                        volFront = volRight;
1065
1066                        // objects belongs to left side now
1067                        for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
1068                }
1069        }
1070
1071        ////////////////////////////////////////////
1072        //-- assign object to front and back volume
1073
1074        // belongs to back bv
1075        for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
1076        {
1077                objectsBack.push_back((*cit).mObject);
1078        }
1079        // belongs to front bv
1080        for (cit = backObjectsStart; cit != cit_end; ++ cit)
1081        {
1082                objectsFront.push_back((*cit).mObject);
1083        }
1084
1085        // render cost of the old parent
1086        const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
1087        // the relative cost ratio
1088        const float ratio = newRenderCost / oldRenderCost;
1089
1090#ifdef _DEBUG
1091        Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
1092                  << "back pvs: " << (int)objectsBack.size() << " front pvs: " << (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl
1093                  << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
1094                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
1095                  << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
1096#endif
1097
1098        return ratio;
1099}
1100
1101
1102void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
1103                                                                                                        const int axis)                                                                                 
1104{
1105        //-- insert object queries
1106        ObjectContainer *objects =
1107                mUseGlobalSorting ? tData.mSortedObjects[axis] : &tData.mNode->mObjects;
1108
1109        CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
1110}
1111
1112
1113void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
1114                                                                                                  SortableEntryContainer **subdivisionCandidates,
1115                                                                                                  const bool sort,
1116                                                                                                  const int axis)
1117{
1118        (*subdivisionCandidates)->clear();
1119
1120        // compute requested size and look if subdivision candidate has to be recomputed
1121        const int requestedSize = (int)objects.size() * 2;
1122       
1123        // creates a sorted split candidates array
1124        if ((*subdivisionCandidates)->capacity() > 500000 &&
1125                requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
1126        {
1127        delete (*subdivisionCandidates);
1128                (*subdivisionCandidates) = new SortableEntryContainer;
1129        }
1130
1131        (*subdivisionCandidates)->reserve(requestedSize);
1132
1133        ObjectContainer::const_iterator oit, oit_end = objects.end();
1134
1135        for (oit = objects.begin(); oit < oit_end; ++ oit)
1136        {
1137                Intersectable *object = *oit;
1138                const AxisAlignedBox3 &box = object->GetBox();
1139                const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
1140
1141                (*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
1142        }
1143
1144        if (sort)
1145        {       // no presorted candidate list
1146                stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
1147        }
1148}
1149
1150
1151const BvhStatistics &BvHierarchy::GetStatistics() const
1152{
1153        return mBvhStats;
1154}
1155
1156
1157float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
1158{       
1159        BvhLeaf *leaf = tData.mNode;
1160        float vol = 0;
1161
1162    // sort so we can use a sweep from right to left
1163        PrepareLocalSubdivisionCandidates(tData, axis);
1164       
1165        // collect and mark the view cells as belonging to front pvs
1166        ViewCellContainer viewCells;
1167        CollectViewCells(tData.mNode->mObjects, viewCells, true);
1168                       
1169        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1170        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1171        {
1172#if USE_VOLUMES_FOR_HEURISTICS
1173                const float volIncr = (*vit)->GetVolume();
1174#else
1175                const float volIncr = 1.0f;
1176#endif
1177                vol += volIncr;
1178        }
1179
1180        // we will mail view cells switching to the back side
1181        ViewCell::NewMail();
1182       
1183        return vol;
1184}
1185
1186///////////////////////////////////////////////////////////
1187
1188
1189void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
1190                                                                                         float &volLeft,
1191                                                                                         float &volRight)
1192{
1193        // collect all view cells associated with this objects
1194        // (also multiple times, if they are pierced by several rays)
1195        ViewCellContainer viewCells;
1196        const bool useMailboxing = false;
1197
1198        CollectViewCells(obj, viewCells, useMailboxing);
1199
1200        // classify view cells and compute volume contri accordingly
1201        // possible view cell classifications:
1202        // view cell mailed => view cell can be seen from left child node
1203        // view cell counter > 0 view cell can be seen from right child node
1204        // combined: view cell volume belongs to both nodes
1205        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1206       
1207        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1208        {
1209                // view cells can also be seen from left child node
1210                ViewCell *viewCell = *vit;
1211#if USE_VOLUMES_FOR_HEURISTICS
1212                const float vol = viewCell->GetVolume();
1213#else
1214                const float vol = 1.0f;
1215#endif
1216                if (!viewCell->Mailed())
1217                {
1218                        viewCell->Mail();
1219                        // we now see view cell from both nodes
1220                        // => add volume to left node
1221                        volLeft += vol;
1222                }
1223
1224                // last reference into the right node
1225                if (-- viewCell->mCounter == 0)
1226                {       
1227                        // view cell was previously seen from both nodes  =>
1228                        // remove volume from right node
1229                        volRight -= vol;
1230                }
1231        }
1232}
1233
1234
1235void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
1236{
1237        mViewCellsManager = vcm;
1238}
1239
1240
1241AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
1242{
1243        return mBoundingBox;
1244}
1245
1246
1247float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
1248                                                                                 ObjectContainer &frontObjects,
1249                                                                                 ObjectContainer &backObjects,
1250                                                                                 bool useVisibilityBasedHeuristics)
1251{
1252        ObjectContainer nFrontObjects[3];
1253        ObjectContainer nBackObjects[3];
1254        float nCostRatio[3];
1255
1256        int sAxis = 0;
1257        int bestAxis = -1;
1258
1259        if (mOnlyDrivingAxis)
1260        {
1261                const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
1262                sAxis = box.Size().DrivingAxis();
1263        }
1264       
1265        ////////////////////////////////////
1266        //-- evaluate split cost for all three axis
1267       
1268        for (int axis = 0; axis < 3; ++ axis)
1269        {
1270                if (!mOnlyDrivingAxis || (axis == sAxis))
1271                {
1272                        if (mUseCostHeuristics)
1273                        {
1274                                //////////////////////////////////
1275                //-- split objects using heuristics
1276                               
1277                                if (useVisibilityBasedHeuristics)
1278                                {
1279                                        //cout << "v rays: " << tData.mNumRays << " " << endl;
1280                                        ///////////
1281                                        //-- heuristics using objects weighted by view cells volume
1282                                        nCostRatio[axis] =
1283                                                EvalLocalCostHeuristics(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1284                                }
1285                                else
1286                                {       cout << "e rays: " << tData.mNumRays << " ";
1287                                        //////////////////
1288                                        //-- view cells not constructed yet     => use surface area heuristic                   
1289                                        nCostRatio[axis] =
1290                                                EvalSah(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1291                                }
1292                        }
1293                        else
1294                        {
1295                                //-- split objects using some simple criteria
1296                                nCostRatio[axis] =
1297                                        EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1298                        }
1299
1300                        if (bestAxis == -1)
1301                        {
1302                                bestAxis = axis;
1303                        }
1304                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
1305                        {
1306                                bestAxis = axis;
1307                        }
1308                }
1309        }
1310
1311    ////////////////
1312        //-- assign values
1313
1314        frontObjects = nFrontObjects[bestAxis];
1315        backObjects = nBackObjects[bestAxis];
1316
1317        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1318        return nCostRatio[bestAxis];
1319}
1320
1321
1322int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
1323{
1324        int nRays = 0;
1325        VssRayContainer::const_iterator rit, rit_end = rays.end();
1326
1327        VssRay::NewMail();
1328
1329    for (rit = rays.begin(); rit != rays.end(); ++ rit)
1330        {
1331                VssRay *ray = (*rit);
1332
1333                if (ray->mTerminationObject)
1334                {
1335                        ray->mTerminationObject->mVssRays.push_back(ray);
1336                        if (!ray->Mailed())
1337                        {
1338                                ray->Mail();
1339                                ++ nRays;
1340                        }
1341                }
1342#if COUNT_ORIGIN_OBJECTS
1343                if (ray->mOriginObject)
1344                {
1345                        ray->mOriginObject->mVssRays.push_back(ray);
1346
1347                        if (!ray->Mailed())
1348                        {
1349                                ray->Mail();
1350                                ++ nRays;
1351                        }
1352                }
1353#endif
1354        }
1355
1356        return nRays;
1357}
1358
1359
1360void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
1361{
1362        const float costDecr =
1363                sc.GetRenderCostDecrease();// / mHierarchyManager->GetViewSpaceBox().GetVolume();       
1364
1365        mSubdivisionStats
1366                        << "#Leaves\n" << mBvhStats.Leaves() << endl
1367                        << "#RenderCostDecrease\n" << costDecr << endl
1368                        << "#TotalRenderCost\n" << mTotalCost << endl
1369                        << "#EntriesInPvs\n" << mPvsEntries << endl;
1370}
1371
1372
1373void BvHierarchy::CollectRays(const ObjectContainer &objects,
1374                                                          VssRayContainer &rays) const
1375{
1376        VssRay::NewMail();
1377        ObjectContainer::const_iterator oit, oit_end = objects.end();
1378
1379        // evaluate reverse pvs and view cell volume on left and right cell
1380        // note: should I take all leaf objects or rather the objects hit by rays?
1381        for (oit = objects.begin(); oit != oit_end; ++ oit)
1382        {
1383                Intersectable *obj = *oit;
1384                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
1385
1386                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
1387                {
1388                        VssRay *ray = (*rit);
1389
1390                        if (!ray->Mailed())
1391                        {
1392                                ray->Mail();
1393                                rays.push_back(ray);
1394                        }
1395                }
1396        }
1397}
1398
1399
1400float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
1401{       
1402        if (0 &&
1403                (mHierarchyManager->GetViewSpaceSubdivisionType() ==
1404                HierarchyManager::NO_VIEWSPACE_SUBDIV))
1405        {
1406                ////////////////
1407                //-- surface area heuristics
1408
1409                if (objects.empty())
1410                        return 0.0f;
1411
1412                const AxisAlignedBox3 box = EvalBoundingBox(objects);
1413                const float area = box.SurfaceArea();
1414                const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
1415
1416                return (float)objects.size() * area / viewSpaceArea;
1417        }
1418        else
1419        {       ///////////////
1420                //-- render cost heuristics
1421
1422                const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1423
1424                // probability that view point lies in a view cell which sees this node
1425                const float p = EvalViewCellsVolume(objects) / viewSpaceVol;   
1426
1427                return (float)objects.size() * p;
1428        }
1429}
1430
1431
1432AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
1433                                                                                         const AxisAlignedBox3 *parentBox) const
1434{
1435        // if there are no objects in this box, box size is set to parent box size.
1436        // Question: Invalidate box instead?
1437        if (parentBox && objects.empty())
1438                return *parentBox;
1439
1440        AxisAlignedBox3 box;
1441        box.Initialize();
1442
1443        ObjectContainer::const_iterator oit, oit_end = objects.end();
1444
1445        for (oit = objects.begin(); oit != oit_end; ++ oit)
1446        {
1447                Intersectable *obj = *oit;
1448                // grow bounding box to include all objects
1449                box.Include(obj->GetBox());
1450        }
1451
1452        return box;
1453}
1454
1455
1456void BvHierarchy::CollectLeaves(vector<BvhLeaf *> &leaves) const
1457{
1458        stack<BvhNode *> nodeStack;
1459        nodeStack.push(mRoot);
1460
1461        while (!nodeStack.empty())
1462        {
1463                BvhNode *node = nodeStack.top();
1464                nodeStack.pop();
1465
1466                if (node->IsLeaf())
1467                {
1468                        BvhLeaf *leaf = (BvhLeaf *)node;
1469                        leaves.push_back(leaf);
1470                }
1471                else
1472                {
1473                        BvhInterior *interior = (BvhInterior *)node;
1474
1475                        nodeStack.push(interior->GetBack());
1476                        nodeStack.push(interior->GetFront());
1477                }
1478        }
1479}
1480
1481
1482AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1483{
1484        return node->GetBoundingBox();
1485}
1486
1487
1488void BvHierarchy::CollectViewCells(const ObjectContainer &objects,
1489                                                                   ViewCellContainer &viewCells,
1490                                                                   const bool setCounter) const
1491{
1492        // no view cells yet
1493        if (0 && mHierarchyManager->GetViewSpaceSubdivisionType() ==
1494                HierarchyManager::NO_VIEWSPACE_SUBDIV)
1495                return;
1496
1497        ViewCell::NewMail();
1498        ObjectContainer::const_iterator oit, oit_end = objects.end();
1499
1500        // loop through all object and collect view cell pvs of this node
1501        for (oit = objects.begin(); oit != oit_end; ++ oit)
1502        {
1503                CollectViewCells(*oit, viewCells, true, setCounter);
1504        }
1505}
1506
1507
1508void BvHierarchy::CollectViewCells(Intersectable *obj,
1509                                                                   ViewCellContainer &viewCells,
1510                                                                   const bool useMailBoxing,
1511                                                                   const bool setCounter) const
1512{
1513        VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
1514
1515        for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
1516        {
1517                VssRay *ray = (*rit);
1518                ViewCellContainer tmpViewCells;
1519       
1520                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1521
1522                // matt: probably slow to allocate memory for view cells every time
1523                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1524
1525                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1526                {
1527                        ViewCell *vc = *vit;
1528
1529                        // store view cells
1530                        if (!useMailBoxing || !vc->Mailed())
1531                        {
1532                                if (useMailBoxing)
1533                                {
1534                                        vc->Mail();
1535                                        if (setCounter)
1536                                        {
1537                                                vc->mCounter = 0;
1538                                        }
1539                                }
1540                                viewCells.push_back(vc);
1541                        }
1542                       
1543                        if (setCounter)
1544                        {
1545                                ++ vc->mCounter;
1546                        }
1547                }
1548        }
1549}
1550
1551
1552int BvHierarchy::CountViewCells(Intersectable *obj) const
1553{
1554        int result = 0;
1555       
1556        VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
1557
1558        for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
1559        {
1560                VssRay *ray = (*rit);
1561                ViewCellContainer tmpViewCells;
1562       
1563                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1564               
1565                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1566                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1567                {
1568                        ViewCell *vc = *vit;
1569
1570                        // store view cells
1571                        if (!vc->Mailed())
1572                        {
1573                                vc->Mail();
1574                                ++ result;
1575                        }
1576                }
1577        }
1578
1579        return result;
1580}
1581
1582
1583int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
1584{
1585        // no view cells yet
1586        if (0 && mHierarchyManager->GetViewSpaceSubdivisionType() ==
1587                HierarchyManager::NO_VIEWSPACE_SUBDIV)
1588                return 1;
1589
1590        int nViewCells = 0;
1591
1592        ViewCell::NewMail();
1593
1594        ObjectContainer::const_iterator oit, oit_end = objects.end();
1595
1596        // loop through all object and collect view cell pvs of this node
1597        for (oit = objects.begin(); oit != oit_end; ++ oit)
1598        {
1599                nViewCells += CountViewCells(*oit);
1600        }
1601
1602        return nViewCells;
1603}
1604
1605
1606void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1607                                                                                 vector<SubdivisionCandidate *> &dirtyList,
1608                                                                                 const bool onlyUnmailed)
1609{
1610        BvhTraversalData &tData = sc->mParentData;
1611        BvhLeaf *node = tData.mNode;
1612       
1613        ViewCellContainer viewCells;
1614        ViewCell::NewMail();
1615        CollectViewCells(node->mObjects, viewCells, true);
1616
1617        if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
1618       
1619        // split candidates handling
1620        // these view cells  are thrown into dirty list
1621        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1622
1623        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1624        {
1625        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1626                VspLeaf *leaf = vc->mLeaves[0];
1627       
1628                SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
1629               
1630                // is this leaf still a split candidate?
1631                if (candidate && (!onlyUnmailed || !candidate->Mailed()))
1632                {
1633                        candidate->Mail();
1634                        dirtyList.push_back(candidate);
1635                }
1636        }
1637}
1638
1639
1640BvhNode *BvHierarchy::GetRoot() const
1641{
1642        return mRoot;
1643}
1644
1645
1646bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
1647{
1648        ObjectContainer::const_iterator oit =
1649                lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1650                               
1651        // objects sorted by id
1652        if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1653        {
1654                return true;
1655        }
1656        else
1657        {
1658                return false;
1659        }
1660}
1661
1662
1663BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
1664{
1665        // rather use the simple version
1666        if (!object)
1667                return NULL;
1668       
1669        return object->mBvhLeaf;
1670       
1671        ///////////////////////////////////////
1672        // start from root of tree
1673       
1674        if (node == NULL)
1675                node = mRoot;
1676       
1677        vector<BvhLeaf *> leaves;
1678
1679        stack<BvhNode *> nodeStack;
1680        nodeStack.push(node);
1681 
1682        BvhLeaf *leaf = NULL;
1683 
1684        while (!nodeStack.empty()) 
1685        {
1686                BvhNode *node = nodeStack.top();
1687                nodeStack.pop();
1688       
1689                if (node->IsLeaf())
1690                {
1691                        leaf = dynamic_cast<BvhLeaf *>(node);
1692
1693                        if (IsObjectInLeaf(leaf, object))
1694                        {
1695                                return leaf;
1696                        }
1697                }
1698                else   
1699                {       
1700                        // find point
1701                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1702       
1703                        if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
1704                        {
1705                                nodeStack.push(interior->GetBack());
1706                        }
1707                       
1708                        // search both sides as we are using bounding volumes
1709                        if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
1710                        {
1711                                nodeStack.push(interior->GetFront());
1712                        }
1713                }
1714        }
1715 
1716        return leaf;
1717}
1718
1719
1720BvhIntersectable *BvHierarchy::GetOrCreateBvhIntersectable(BvhNode *node)
1721{
1722        // search nodes
1723        std::map<BvhNode *, BvhIntersectable *>::const_iterator it
1724                = mBvhIntersectables.find(node);
1725
1726        if (it != mBvhIntersectables.end())
1727        {
1728                return (*it).second;
1729        }
1730
1731        // not in map => create new entry
1732        BvhIntersectable *bvhObj = new BvhIntersectable(node);
1733        mBvhIntersectables[node] = bvhObj;
1734
1735        return bvhObj;
1736}
1737
1738
1739bool BvHierarchy::Export(OUT_STREAM &stream)
1740{
1741        ExportNode(mRoot, stream);
1742
1743        return true;
1744}
1745
1746
1747void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
1748{
1749        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1750        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1751        {
1752                stream << (*oit)->GetId() << " ";
1753        }
1754}
1755
1756
1757void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
1758{
1759        if (node->IsLeaf())
1760        {
1761                BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
1762                const AxisAlignedBox3 box = leaf->GetBoundingBox();
1763                stream << "<Leaf"
1764                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1765                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
1766                           << " objects=\"";
1767               
1768                //-- export objects
1769                ExportObjects(leaf, stream);
1770               
1771                stream << "\" />" << endl;
1772        }
1773        else
1774        {       
1775                BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1776                const AxisAlignedBox3 box = interior->GetBoundingBox();
1777
1778                stream << "<Interior"
1779                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1780                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
1781                           << "\">" << endl;
1782
1783                ExportNode(interior->GetBack(), stream);
1784                ExportNode(interior->GetFront(), stream);
1785
1786                stream << "</Interior>" << endl;
1787        }
1788}
1789
1790
1791float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
1792{
1793        float vol = 0;
1794
1795        ViewCellContainer viewCells;
1796        CollectViewCells(objects, viewCells);
1797
1798        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1799
1800        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1801        {
1802                vol += (*vit)->GetVolume();
1803        }
1804
1805        return vol;
1806}
1807
1808
1809void BvHierarchy::Initialise(const ObjectContainer &objects)
1810{
1811        ///////
1812        //-- create new root
1813
1814        AxisAlignedBox3 box = EvalBoundingBox(objects);
1815        BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
1816        bvhleaf->mObjects = objects;
1817        mRoot = bvhleaf;
1818
1819        // compute bounding box from objects
1820        mBoundingBox = mRoot->GetBoundingBox();
1821
1822        // associate root with current objects
1823        AssociateObjectsWithLeaf(bvhleaf);
1824}
1825
1826
1827/*
1828Mesh *BvHierarchy::MergeLeafToMesh()
1829void BvHierarchy::MergeLeavesToMeshes()
1830{
1831        vector<BvhLeaf *> leaves;
1832        CollectLeaves(leaves);
1833
1834        vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
1835
1836        for (lit = leaves.begin(); lit != lit_end; ++ lit)
1837        {
1838                Mesh *mesh = MergeLeafToMesh(*lit);
1839        }
1840}*/
1841
1842
1843SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
1844                                                                                                           const ObjectContainer &objects)
1845{
1846        ///////////////////////////////////////
1847        //-- we assume that we have objects sorted by their id =>
1848        //-- we don't have to sort them here and an binary search
1849        //-- for identifying if a object is in a leaf.
1850       
1851        mBvhStats.Reset();
1852        mBvhStats.Start();
1853        mBvhStats.nodes = 1;
1854               
1855        // store pointer to this tree
1856        BvhSubdivisionCandidate::sBvHierarchy = this;
1857       
1858        // root and bounding box was already constructed
1859        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);
1860
1861        // multiply termination criterium for comparison,
1862        // so it can be set between zero and one and
1863        // no division is necessary during traversal
1864
1865#if PROBABILIY_IS_BV_VOLUME
1866        mTermMinProbability *= mBoundingBox.GetVolume();
1867        // probability that bounding volume is seen
1868        const float prop = GetBoundingBox().GetVolume();
1869#else
1870        mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
1871        // probability that volume is "seen" from the view cells
1872        const float prop = EvalViewCellsVolume(objects);
1873#endif
1874
1875        // only rays intersecting objects in node are interesting
1876        const int nRays = AssociateObjectsWithRays(sampleRays);
1877        //Debug << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
1878
1879        // create bvh traversal data
1880        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
1881
1882        // create sorted object lists for the first data
1883        if (mUseGlobalSorting)
1884        {
1885                AssignInitialSortedObjectList(oData);
1886        }
1887       
1888
1889        ///////////////////
1890        //-- add first candidate for object space partition     
1891
1892        BvhSubdivisionCandidate *oSubdivisionCandidate = new BvhSubdivisionCandidate(oData);
1893
1894        // evaluate priority
1895        EvalSubdivisionCandidate(*oSubdivisionCandidate);
1896        bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
1897
1898        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1899        mTotalCost = (float)objects.size() * prop / viewSpaceVol;
1900        mPvsEntries = CountViewCells(objects);
1901
1902        PrintSubdivisionStats(*oSubdivisionCandidate);
1903       
1904        return oSubdivisionCandidate;
1905}
1906
1907
1908void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData)
1909{
1910        // we sort the objects as a preprocess so they don't have
1911        // to be sorted for each split
1912        for (int i = 0; i < 3; ++ i)
1913        {
1914                // create new objects
1915                if (!mSortedObjects[i])
1916                {
1917                        mSortedObjects[i] = new SortableEntryContainer();
1918                        CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i);
1919                }
1920
1921                // copy list into traversal data list
1922                tData.mSortedObjects[i] = new ObjectContainer();
1923                tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size());
1924
1925                SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();
1926
1927                for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
1928                {
1929                        tData.mSortedObjects[i]->push_back((*oit).mObject);
1930                }
1931        }
1932}
1933
1934
1935void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
1936                                                                          BvhTraversalData &frontData,
1937                                                                          BvhTraversalData &backData)
1938{
1939        Intersectable::NewMail();
1940
1941        // we sorted the objects as a preprocess so they don't have
1942        // to be sorted for each split
1943        ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
1944
1945        for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
1946        {
1947                (*fit)->Mail();
1948        }
1949
1950        for (int i = 0; i < 3; ++ i)
1951        {
1952                frontData.mSortedObjects[i] = new ObjectContainer();
1953                backData.mSortedObjects[i] = new ObjectContainer();
1954
1955                frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
1956                backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
1957
1958                ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
1959
1960                for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
1961                {
1962                        if ((*oit)->Mailed())
1963                        {
1964                                frontData.mSortedObjects[i]->push_back(*oit);
1965                        }
1966                        else
1967                        {
1968                                backData.mSortedObjects[i]->push_back(*oit);
1969                        }
1970                }
1971        }
1972}
1973
1974
1975SubdivisionCandidate *BvHierarchy::Reset(const VssRayContainer &sampleRays,
1976                                                                                 const ObjectContainer &objects)
1977{
1978        // reset stats
1979        mBvhStats.Reset();
1980        mBvhStats.Start();
1981        mBvhStats.nodes = 1;
1982
1983        // reset root
1984        DEL_PTR(mRoot);
1985       
1986        BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
1987        bvhleaf->mObjects = objects;
1988        mRoot = bvhleaf;
1989       
1990#if PROBABILIY_IS_BV_VOLUME
1991        mTermMinProbability *= mBoundingBox.GetVolume();
1992        // probability that bounding volume is seen
1993        const float prop = GetBoundingBox().GetVolume();
1994#else
1995        mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
1996        // probability that volume is "seen" from the view cells
1997        const float prop = EvalViewCellsVolume(objects);
1998#endif
1999
2000        const int nRays = CountRays(objects);
2001        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);
2002
2003        // create bvh traversal data
2004        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2005
2006        AssignInitialSortedObjectList(oData);
2007       
2008
2009        ///////////////////
2010        //-- add first candidate for object space partition     
2011
2012        BvhSubdivisionCandidate *oSubdivisionCandidate =
2013                new BvhSubdivisionCandidate(oData);
2014
2015        EvalSubdivisionCandidate(*oSubdivisionCandidate);
2016        bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2017
2018        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2019        mTotalCost = (float)objects.size() * prop / viewSpaceVol;
2020
2021        PrintSubdivisionStats(*oSubdivisionCandidate);
2022
2023        return oSubdivisionCandidate;
2024}
2025
2026
2027void BvhStatistics::Print(ostream &app) const
2028{
2029        app << "=========== BvHierarchy statistics ===============\n";
2030
2031        app << setprecision(4);
2032
2033        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
2034
2035        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
2036
2037        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
2038
2039        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
2040
2041        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
2042
2043        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
2044                << maxCostNodes * 100 / (double)Leaves() << endl;
2045
2046        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
2047                << minProbabilityNodes * 100 / (double)Leaves() << endl;
2048
2049
2050        //////////////////////////////////////////////////
2051       
2052        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
2053                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
2054       
2055        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
2056
2057        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
2058
2059        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
2060
2061       
2062        ////////////////////////////////////////////////////////
2063       
2064        app << "#N_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
2065                << minObjectsNodes * 100 / (double)Leaves() << endl;
2066
2067        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
2068
2069        app << "#N_MINOBJECTREFS  ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
2070
2071        app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
2072       
2073        app << "#N_PAVGOBJECTSLEAVES  ( average object refs / leaf)\n" << AvgObjectRefs() << endl;
2074
2075
2076        ////////////////////////////////////////////////////////
2077       
2078        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with mininum rays )\n"
2079                << minRaysNodes * 100 / (double)Leaves() << endl;
2080
2081        app << "#N_MAXRAYREFS  ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";
2082
2083        app << "#N_MINRAYREFS  ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
2084       
2085        app << "#N_PAVGRAYLEAVES  ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
2086       
2087        app << "#N_PAVGRAYCONTRIBLEAVES  ( Average ray contribution)\n" <<
2088                rayRefs / (double)objectRefs << endl;
2089
2090        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<<
2091                maxRayContriNodes * 100 / (double)Leaves() << endl;
2092
2093        app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
2094
2095        app << "========== END OF BvHierarchy statistics ==========\n";
2096}
2097
2098
2099// TODO: return memory usage in MB
2100float BvHierarchy::GetMemUsage() const
2101{
2102        return (float)(sizeof(BvHierarchy)
2103                                   + mBvhStats.Leaves() * sizeof(BvhLeaf)
2104                                   + mBvhStats.Interior() * sizeof(BvhInterior)
2105                                   ) / float(1024 * 1024);
2106}
2107
2108
2109BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
2110                                                                           SubdivisionCandidate *splitCandidate)
2111{
2112        BvhSubdivisionCandidate *sc =
2113                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
2114        BvhTraversalData &tData = sc->mParentData;
2115
2116        BvhNode *currentNode = tData.mNode;
2117        BvhNode *oldNode = (BvhNode *)splitCandidate->mEvaluationHack;
2118
2119        if (!oldNode->IsLeaf())
2120        {       
2121                //////////////
2122                //-- continue subdivision
2123
2124                BvhTraversalData tFrontData;
2125                BvhTraversalData tBackData;
2126                       
2127                BvhInterior *oldInterior = dynamic_cast<BvhInterior *>(oldNode);
2128               
2129                oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
2130                oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
2131               
2132                // evaluate the changes in render cost and pvs entries
2133                EvalSubdivisionCandidate(*sc, false);
2134
2135                // create new interior node and two leaf node
2136                currentNode = SubdivideNode(*sc, tFrontData, tBackData);
2137       
2138                oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
2139                oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
2140cout << "here5" << endl;
2141                ///////////////////////////
2142                //-- push the new split candidates on the queue
2143               
2144                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
2145                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
2146
2147                frontCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
2148                backCandidate->SetPriority((float)-oldInterior->GetBack()->mTimeStamp);
2149
2150                frontCandidate->mEvaluationHack = oldInterior->GetFront();
2151                backCandidate->mEvaluationHack = oldInterior->GetBack();
2152
2153                // cross reference
2154                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
2155                tBackData.mNode->SetSubdivisionCandidate(backCandidate);
2156
2157                //cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
2158                tQueue.Push(frontCandidate);
2159                tQueue.Push(backCandidate);
2160        }
2161
2162        /////////////////////////////////
2163        //-- node is a leaf => terminate traversal
2164
2165        if (currentNode->IsLeaf())
2166        {
2167                // this leaf is no candidate for splitting anymore
2168                // => detach subdivision candidate
2169                tData.mNode->SetSubdivisionCandidate(NULL);
2170                // detach node so we don't delete it with the traversal data
2171                tData.mNode = NULL;
2172        }
2173       
2174        return currentNode;
2175}
2176
2177
2178}
Note: See TracBrowser for help on using the repository browser.