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

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