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

Revision 1941, 74.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#define USE_VOLUMES_FOR_HEURISTICS 1
28
29  //int BvhNode::sMailId = 10000; //2147483647;
30  //int 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/// sorting operator
43inline static bool smallerSize(Intersectable *obj1, Intersectable *obj2)
44{
45        return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea();
46}
47
48
49
50/***************************************************************/
51/*              class BvhNode implementation                   */
52/***************************************************************/
53
54BvhNode::BvhNode():
55mParent(NULL),
56mTimeStamp(0),
57mRenderCost(-1)
58
59{
60       
61}
62
63BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
64mParent(NULL),
65mBoundingBox(bbox),
66mTimeStamp(0),
67mRenderCost(-1)
68{
69}
70
71
72BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
73mBoundingBox(bbox),
74mParent(parent),
75mTimeStamp(0),
76mRenderCost(-1)
77{
78}
79
80
81bool BvhNode::IsRoot() const
82{
83        return mParent == NULL;
84}
85
86
87BvhInterior *BvhNode::GetParent()
88{
89        return mParent;
90}
91
92
93void BvhNode::SetParent(BvhInterior *parent)
94{
95        mParent = parent;
96}
97
98
99int BvhNode::GetRandomEdgePoint(Vector3 &point,
100                                                                Vector3 &normal)
101{
102        // get random edge
103        const int idx = Random(12);
104        Vector3 a, b;
105        mBoundingBox.GetEdge(idx, &a, &b);
106       
107        const float w = RandomValue(0.0f, 1.0f);
108
109        point = a * w + b * (1.0f - w);
110
111        // TODO
112        normal = Vector3(0);
113
114        return idx;
115}
116
117
118
119/******************************************************************/
120/*              class BvhInterior implementation                  */
121/******************************************************************/
122
123
124BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
125BvhNode(bbox),
126mSubdivisionCandidate(NULL),
127mGlList(0)
128{
129  mActiveNode = this;
130}
131
132
133BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
134  BvhNode(bbox, parent),
135  mGlList(0)
136 
137{
138        mActiveNode = this;
139}
140
141
142BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox,
143                                 BvhInterior *parent,
144                                 const int numObjects):
145  BvhNode(bbox, parent),
146  mGlList(0)
147
148{
149        mObjects.reserve(numObjects);
150        mActiveNode = this;
151}
152
153
154bool BvhLeaf::IsLeaf() const
155{
156        return true;
157}
158
159
160BvhLeaf::~BvhLeaf()
161{
162}
163
164
165void BvhLeaf::CollectObjects(ObjectContainer &objects)
166{
167        ObjectContainer::const_iterator oit, oit_end = mObjects.end();
168        for (oit = mObjects.begin(); oit != oit_end; ++ oit)
169        {
170                objects.push_back(*oit);
171        }
172}
173
174/******************************************************************/
175/*              class BvhInterior implementation                  */
176/******************************************************************/
177
178
179BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
180BvhNode(bbox), mFront(NULL), mBack(NULL)
181{
182}
183
184
185BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
186BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
187{
188}
189
190
191void BvhInterior::ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild)
192{
193        if (mBack == oldChild)
194                mBack = newChild;
195        else
196                mFront = newChild;
197}
198
199
200bool BvhInterior::IsLeaf() const
201{
202        return false;
203}
204
205
206BvhInterior::~BvhInterior()
207{
208        DEL_PTR(mFront);
209        DEL_PTR(mBack);
210}
211
212
213void BvhInterior::SetupChildLinks(BvhNode *front, BvhNode *back)
214{
215    mBack = back;
216    mFront = front;
217}
218
219
220void BvhInterior::CollectObjects(ObjectContainer &objects)
221{
222        mFront->CollectObjects(objects);
223        mBack->CollectObjects(objects);
224}
225
226
227/*******************************************************************/
228/*                  class BvHierarchy implementation               */
229/*******************************************************************/
230
231
232BvHierarchy::BvHierarchy():
233mRoot(NULL),
234mTimeStamp(1),
235mIsInitialSubdivision(false)
236{
237        ReadEnvironment();
238        mSubdivisionCandidates = new SortableEntryContainer;
239//      for (int i = 0; i < 4; ++ i)
240//              mSortedObjects[i] = NULL;
241}
242
243
244BvHierarchy::~BvHierarchy()
245{
246        // delete the local subdivision candidates
247        DEL_PTR(mSubdivisionCandidates);
248
249        // delete the presorted objects
250        /*for (int i = 0; i < 4; ++ i)
251        {
252                DEL_PTR(mSortedObjects[i]);
253        }*/
254       
255        // delete the tree
256        DEL_PTR(mRoot);
257}
258
259
260void BvHierarchy::ReadEnvironment()
261{
262        bool randomize = false;
263        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.randomize", randomize);
264         
265        // initialise random generator for heuristics
266        if (randomize)
267                Randomize();
268
269        //////////////////////////////
270        //-- termination criteria for autopartition
271
272        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
273        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
274        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
275        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
276        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minProbability", mTermMinProbability);
277    Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
278
279
280        //////////////////////////////
281        //-- max cost ratio for early tree termination
282
283        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
284        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
285                mTermMinGlobalCostRatio);
286        Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance",
287                mTermGlobalCostMissTolerance);
288
289
290        //////////////////////////////
291        //-- factors for subdivision heuristics
292
293        // if only the driving axis is used for splits
294        Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
295        Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
296        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
297        Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);
298
299    char subdivisionStatsLog[100];
300        Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
301        mSubdivisionStats.open(subdivisionStatsLog);
302
303        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
304        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
305        Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
306        Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);
307        Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useInitialSubdivision", mApplyInitialPartition);
308        Environment::GetSingleton()->GetIntValue("BvHierarchy.Construction.Initial.minObjects", mInitialMinObjects);
309        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.Initial.maxAreaRatio", mInitialMaxAreaRatio);
310        Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.Initial.minArea", mInitialMinArea);
311
312        //mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
313        //mMemoryConst = (float)sizeof(BvhLeaf);
314        mMemoryConst = 16;//(float)sizeof(ObjectContainer);
315
316    mUseBboxAreaForSah = true;
317
318        /////////////
319        //-- debug output
320
321        Debug << "******* Bvh hierarchy options ******** " << endl;
322    Debug << "max depth: " << mTermMaxDepth << endl;
323        Debug << "min probabiliy: " << mTermMinProbability<< endl;
324        Debug << "min objects: " << mTermMinObjects << endl;
325        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
326        Debug << "miss tolerance: " << mTermMissTolerance << endl;
327        Debug << "max leaves: " << mTermMaxLeaves << endl;
328        Debug << "randomize: " << randomize << endl;
329        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
330        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
331        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
332        Debug << "max memory: " << mMaxMemory << endl;
333        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
334        Debug << "use surface area heuristics: " << mUseSah << endl;
335        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
336        Debug << "split borders: " << mSplitBorder << endl;
337        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
338        Debug << "use global sort: " << mUseGlobalSorting << endl;
339        Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
340        Debug << "bvh mem const: " << mMemoryConst << endl;
341        Debug << "apply initial partition: " << mApplyInitialPartition << endl;
342        Debug << "min objects: " << mInitialMinObjects << endl;
343        Debug << "max area ratio: " << mInitialMaxAreaRatio << endl;
344        Debug << "min area: " << mInitialMinArea << endl;
345
346        Debug << endl;
347}
348
349
350void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
351{
352        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
353
354        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
355        {
356                (*oit)->mBvhLeaf = leaf;
357        }
358}
359
360
361static int CountRays(const ObjectContainer &objects)
362{
363        int nRays = 0;
364
365        ObjectContainer::const_iterator oit, oit_end = objects.end();
366
367        for (oit = objects.begin(); oit != oit_end; ++ oit)
368        {
369                nRays += (int)(*oit)->GetOrCreateRays()->size();
370        }
371
372        return nRays;
373}
374                                                                       
375float BvHierarchy::GetViewSpaceVolume() const
376{
377        return mViewCellsManager->GetViewSpaceBox().GetVolume();
378}
379
380
381BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
382                                                                                BvhTraversalData &frontData,
383                                                                                BvhTraversalData &backData)
384{
385        const BvhTraversalData &tData = sc.mParentData;
386        BvhLeaf *leaf = tData.mNode;
387
388        AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
389
390        // update stats: we have two new leaves
391        mBvhStats.nodes += 2;
392
393        if (tData.mDepth > mBvhStats.maxDepth)
394        {
395                mBvhStats.maxDepth = tData.mDepth;
396        }
397
398        // add the new nodes to the tree
399        BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
400       
401
402        //////////////////
403        //-- create front and back leaf
404
405        AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
406        AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
407
408        BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
409        BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
410
411        BvhInterior *parent = leaf->GetParent();
412
413        // replace a link from node's parent
414        if (parent)
415        {
416                parent->ReplaceChildLink(leaf, node);
417                node->SetParent(parent);
418        }
419        else // no parent => this node is the root
420        {
421                mRoot = node;
422        }
423
424        // and setup child links
425        node->SetupChildLinks(front, back);
426
427        ++ mBvhStats.splits;
428
429
430        ////////////////////////////////////////
431        //-- fill front and back traversal data with the new values
432
433        frontData.mDepth = backData.mDepth = tData.mDepth + 1;
434
435        frontData.mNode = front;
436        backData.mNode = back;
437
438        back->mObjects = sc.mBackObjects;
439        front->mObjects = sc.mFrontObjects;
440
441        // if the number of rays is too low, no assumptions can be made
442        // (=> switch to surface area heuristics?)
443        frontData.mNumRays = CountRays(sc.mFrontObjects);
444        backData.mNumRays = CountRays(sc.mBackObjects);
445
446        AssociateObjectsWithLeaf(back);
447        AssociateObjectsWithLeaf(front);
448   
449        //-- compute pvs correction to cope with undersampling
450        frontData.mPvs = (float)CountViewCells(front->mObjects);
451        backData.mPvs = (float)CountViewCells(back->mObjects);
452
453        frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
454        backData.mCorrectedPvs = sc.mCorrectedBackPvs;
455
456        // compute probability of this node being visible,
457        // i.e., volume of the view cells that can see this node
458        frontData.mVolume = EvalViewCellsVolume(sc.mFrontObjects) / GetViewSpaceVolume();
459        backData.mVolume = EvalViewCellsVolume(sc.mBackObjects) / GetViewSpaceVolume();
460
461        frontData.mCorrectedVolume = sc.mCorrectedFrontVolume;
462        backData.mCorrectedVolume = sc.mCorrectedBackVolume;
463
464    // how often was max cost ratio missed in this branch?
465        frontData.mMaxCostMisses = sc.GetMaxCostMisses();
466        backData.mMaxCostMisses = sc.GetMaxCostMisses();
467
468        // set the time stamp so the order of traversal can be reconstructed
469        node->SetTimeStamp(mHierarchyManager->mTimeStamp ++);
470               
471        // assign the objects in sorted order
472        if (mUseGlobalSorting)
473        {
474                AssignSortedObjects(sc, frontData, backData);
475        }
476       
477        // return the new interior node
478        return node;
479}
480
481
482BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
483                                                                SubdivisionCandidate *splitCandidate,
484                                                                const bool globalCriteriaMet)
485{
486        BvhSubdivisionCandidate *sc =
487                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
488        BvhTraversalData &tData = sc->mParentData;
489
490        BvhNode *currentNode = tData.mNode;
491
492        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
493        {       
494                //////////////
495                //-- continue subdivision
496
497                BvhTraversalData tFrontData;
498                BvhTraversalData tBackData;
499                       
500                // create new interior node and two leaf node
501                currentNode = SubdivideNode(*sc, tFrontData, tBackData);
502       
503                // decrease the weighted average cost of the subdivisoin
504                mTotalCost -= sc->GetRenderCostDecrease();
505                mPvsEntries += sc->GetPvsEntriesIncr();
506
507                // subdivision statistics
508                if (1) PrintSubdivisionStats(*sc);
509
510
511                ///////////////////////////
512                //-- push the new split candidates on the queue
513               
514                BvhSubdivisionCandidate *frontCandidate =
515                                new BvhSubdivisionCandidate(tFrontData);
516                BvhSubdivisionCandidate *backCandidate =
517                                new BvhSubdivisionCandidate(tBackData);
518               
519                EvalSubdivisionCandidate(*frontCandidate);
520                EvalSubdivisionCandidate(*backCandidate);
521       
522                // cross reference
523                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
524                tBackData.mNode->SetSubdivisionCandidate(backCandidate);
525
526                //cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
527                tQueue.Push(frontCandidate);
528                tQueue.Push(backCandidate);
529        }
530
531        /////////////////////////////////
532        //-- node is a leaf => terminate traversal
533
534        if (currentNode->IsLeaf())
535        {
536                /////////////////////
537                //-- store additional info
538                EvaluateLeafStats(tData);
539       
540                // this leaf is no candidate for splitting anymore
541                // => detach subdivision candidate
542                tData.mNode->SetSubdivisionCandidate(NULL);
543                // detach node so we don't delete it with the traversal data
544                tData.mNode = NULL;
545        }
546       
547        return currentNode;
548}
549
550
551float BvHierarchy::EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
552                                                                const float renderCostDecr,
553                                                                const float oldRenderCost) const
554{
555        float priority;
556
557        if (mIsInitialSubdivision)
558        {
559                priority = (float)-splitCandidate.mParentData.mDepth;
560                return priority;
561        }
562
563        BvhLeaf *leaf = splitCandidate.mParentData.mNode;
564
565        // surface area heuristics is used when there is
566        // no view space subdivision available.
567        // In order to have some prioritized traversal,
568        // we use this formula instead
569        if (mHierarchyManager->GetViewSpaceSubdivisionType() ==
570                HierarchyManager::NO_VIEWSPACE_SUBDIV)
571        {
572                priority = EvalSahCost(leaf);
573        }
574        else
575        {
576                // take render cost of node into account
577                // otherwise danger of being stuck in a local minimum!
578                const float factor = mRenderCostDecreaseWeight;
579
580                priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
581               
582                if (mHierarchyManager->mConsiderMemory)
583                {
584                        priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
585                }
586        }
587
588        // hack: don't allow empty splits to be taken
589        if (splitCandidate.mFrontObjects.empty() || splitCandidate.mBackObjects.empty())
590                priority = 0;
591
592        return priority;
593}
594
595
596static float AvgRayContribution(const int pvs, const int nRays)
597{
598        return (float)pvs / ((float)nRays + Limits::Small);
599}
600
601
602void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate,
603                                                                                   bool computeSplitPlane)
604{
605        if (computeSplitPlane)
606        {
607                const bool sufficientSamples =
608                        splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;
609
610                const bool useVisibiliyBasedHeuristics =
611                                        !mUseSah &&
612                                        (mHierarchyManager->GetViewSpaceSubdivisionType() ==
613                                        HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
614                                        sufficientSamples;
615
616                // compute best object partition
617                const float ratio =     SelectObjectPartition(splitCandidate.mParentData,
618                                                                                                  splitCandidate.mFrontObjects,
619                                                                                                  splitCandidate.mBackObjects,
620                                                                                                  useVisibiliyBasedHeuristics);
621       
622                // cost ratio violated?
623                const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
624                const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
625
626                splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
627                                                                                previousMisses + 1 : previousMisses);
628        }
629
630        const BvhTraversalData &tData = splitCandidate.mParentData;
631        BvhLeaf *leaf = tData.mNode;
632
633        // avg contribution of a ray to a pvs
634        const float pvs = (float)CountViewCells(leaf->mObjects);
635        const float avgRayContri = AvgRayContribution((int)pvs, tData.mNumRays);
636
637        // high avg ray contri, the result is influenced by undersampling
638        splitCandidate.SetAvgRayContribution(avgRayContri);
639        const float viewSpaceVol =  GetViewSpaceVolume();
640
641        const float oldVolume = EvalViewCellsVolume(leaf->mObjects) / viewSpaceVol;
642        const float oldRatio = (tData.mVolume) > 0 ? oldVolume / tData.mVolume : 1;
643        const float parentVol = tData.mCorrectedVolume * oldRatio;
644
645        // this leaf is a pvs entry in all the view cells
646        // that see one of the objects.
647        const float frontVol = EvalViewCellsVolume(splitCandidate.mFrontObjects) / viewSpaceVol;
648        const float backVol = EvalViewCellsVolume(splitCandidate.mBackObjects) / viewSpaceVol;
649
650        splitCandidate.mCorrectedFrontVolume =
651                mHierarchyManager->EvalCorrectedPvs(frontVol, parentVol, avgRayContri);
652       
653        splitCandidate.mCorrectedBackVolume =
654                mHierarchyManager->EvalCorrectedPvs(backVol, parentVol, avgRayContri);
655       
656        const float relfrontCost = splitCandidate.mCorrectedFrontVolume *
657                EvalAbsCost(splitCandidate.mFrontObjects);
658        const float relBackCost =  splitCandidate.mCorrectedBackVolume *
659                EvalAbsCost(splitCandidate.mBackObjects);
660        const float relParentCost = parentVol * EvalAbsCost(leaf->mObjects);
661
662        // compute global decrease in render cost
663        const float newRenderCost = relfrontCost + relBackCost;
664        const float renderCostDecr = relParentCost - newRenderCost;
665       
666        splitCandidate.SetRenderCostDecrease(renderCostDecr);
667
668        // increase in pvs entries
669        const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, avgRayContri);
670        splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
671
672        if (0)
673        cout << "bvh volume cost"
674                 << " avg ray contri: " << avgRayContri << " ratio: " << oldRatio
675                 << " parent: " << parentVol << " old vol: " << oldVolume
676                 << " frontvol: " << frontVol << " corr. " << splitCandidate.mCorrectedFrontVolume
677                 << " backvol: " << backVol << " corr. " << splitCandidate.mCorrectedBackVolume << endl;
678
679#ifdef GTP_DEBUG
680        Debug << "old render cost: " << oldRenderCost << endl;
681        Debug << "new render cost: " << newRenderCost << endl;
682        Debug << "render cost decrease: " << renderCostDecr << endl;
683#endif
684
685        float priority = EvalPriority(splitCandidate,
686                                                                  renderCostDecr,
687                                                                  relParentCost);
688
689        // compute global decrease in render cost
690        splitCandidate.SetPriority(priority);
691}
692
693
694int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate,
695                                                                        const float avgRayContri) const
696{
697        const float oldPvsSize = (float)CountViewCells(splitCandidate.mParentData.mNode->mObjects);
698        const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ? oldPvsSize / splitCandidate.mParentData.mPvs : 1;
699
700        const float parentPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
701
702        const int frontViewCells = CountViewCells(splitCandidate.mFrontObjects);
703        const int backViewCells = CountViewCells(splitCandidate.mBackObjects);
704       
705        splitCandidate.mCorrectedFrontPvs =
706                mHierarchyManager->EvalCorrectedPvs((float)frontViewCells, parentPvs, avgRayContri);
707        splitCandidate.mCorrectedBackPvs =
708                mHierarchyManager->EvalCorrectedPvs((float)backViewCells, parentPvs, avgRayContri);
709
710        if (0)
711        cout << "bvh pvs"
712                 << " avg ray contri: " << avgRayContri << " ratio: " << oldPvsRatio
713                 << " parent: " << parentPvs << " " << " old vol: " << oldPvsSize
714                 << " frontpvs: " << frontViewCells << " corr. " << splitCandidate.mCorrectedFrontPvs
715                 << " backpvs: " << frontViewCells << " corr. " << splitCandidate.mCorrectedBackPvs << endl;
716
717        return (int)(splitCandidate.mCorrectedFrontPvs + splitCandidate.mCorrectedBackPvs - parentPvs);
718}
719
720
721inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const
722{
723        const bool terminationCriteriaMet =
724                        (0
725                        || ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects)
726                        //|| (data.mProbability <= mTermMinProbability)
727                        //|| (data.mNumRays <= mTermMinRays)
728                 );
729
730#ifdef _DEBUG
731        if (terminationCriteriaMet)
732        {
733                cout << "bvh local termination criteria met:" << endl;
734                cout << "objects: " << (int)tData.mNode->mObjects.size() << " " << mTermMinObjects << endl;
735        }
736#endif
737        return terminationCriteriaMet;
738}
739
740
741inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
742{
743        // note: tracking for global cost termination
744        // does not make much sense for interleaved vsp / osp partition
745        // as it is the responsibility of the hierarchy manager
746
747        const bool terminationCriteriaMet =
748                (0
749                || (mBvhStats.Leaves() >= mTermMaxLeaves)
750                //|| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
751                //|| mOutOfMemory
752                );
753
754#ifdef GTP_DEBUG
755        if (terminationCriteriaMet)
756        {
757                Debug << "bvh global termination criteria met:" << endl;
758                Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
759                Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
760        }
761#endif
762        return terminationCriteriaMet;
763}
764
765
766void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
767{
768        // the node became a leaf -> evaluate stats for leafs
769        BvhLeaf *leaf = data.mNode;
770       
771        ++ mCreatedLeaves;
772
773       
774        /*if (data.mProbability <= mTermMinProbability)
775        {
776                ++ mBvhStats.minProbabilityNodes;
777        }*/
778
779        ////////////////////////////////////////////
780        // depth related stuff
781
782        if (data.mDepth < mBvhStats.minDepth)
783        {
784                mBvhStats.minDepth = data.mDepth;
785        }
786
787        if (data.mDepth >= mTermMaxDepth)
788        {
789        ++ mBvhStats.maxDepthNodes;
790        }
791
792        // accumulate depth to compute average depth
793        mBvhStats.accumDepth += data.mDepth;
794
795
796        ////////////////////////////////////////////
797        // objects related stuff
798
799        // note: the sum should alwaysbe total number of objects for bvh
800        mBvhStats.objectRefs += (int)leaf->mObjects.size();
801
802        if ((int)leaf->mObjects.size() <= mTermMinObjects)
803        {
804             ++ mBvhStats.minObjectsNodes;
805        }
806
807        if (leaf->mObjects.empty())
808        {
809                ++ mBvhStats.emptyNodes;
810        }
811
812        if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
813        {
814                mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
815        }
816
817        if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
818        {
819                mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
820        }
821
822        ////////////////////////////////////////////
823        // ray related stuff
824
825        // note: this number should always accumulate to the total number of rays
826        mBvhStats.rayRefs += data.mNumRays;
827       
828        if (data.mNumRays <= mTermMinRays)
829        {
830             ++ mBvhStats.minRaysNodes;
831        }
832
833        if (data.mNumRays > mBvhStats.maxRayRefs)
834        {
835                mBvhStats.maxRayRefs = data.mNumRays;
836        }
837
838        if (data.mNumRays < mBvhStats.minRayRefs)
839        {
840                mBvhStats.minRayRefs = data.mNumRays;
841        }
842
843#ifdef _DEBUG
844        cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size()
845                 << " rays: " << data.mNumRays << " rays / objects "
846                 << (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
847#endif
848}
849
850
851#if 0
852
853/// compute object boundaries using spatial mid split
854float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
855                                                                                        const int axis,
856                                                                                        ObjectContainer &objectsFront,
857                                                                                        ObjectContainer &objectsBack)
858{
859        const float maxBox = tData.mBoundingBox.Max(axis);
860        const float minBox = tData.mBoundingBox.Min(axis);
861
862        float midPoint = (maxBox + minBox) * 0.5f;
863
864        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
865       
866        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
867        {
868                Intersectable *obj = *oit;
869                const AxisAlignedBox3 box = obj->GetBox();
870
871                const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
872
873                // object mailed => belongs to back objects
874                if (objMid < midPoint)
875                {
876                        objectsBack.push_back(obj);
877                }
878                else
879                {
880                        objectsFront.push_back(obj);
881                }
882        }
883
884        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
885        const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
886
887        const float ratio = newRenderCost / oldRenderCost;
888        return ratio;
889}
890
891#else
892
893/// compute object partition by getting balanced objects on the left and right side
894float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
895                                                                                        const int axis,
896                                                                                        ObjectContainer &objectsFront,
897                                                                                        ObjectContainer &objectsBack)
898{
899        PrepareLocalSubdivisionCandidates(tData, axis);
900       
901        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
902
903        int i = 0;
904        const int border = (int)tData.mNode->mObjects.size() / 2;
905
906    for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
907        {
908                Intersectable *obj = (*cit).mObject;
909
910                // object mailed => belongs to back objects
911                if (i < border)
912                {
913                        objectsBack.push_back(obj);
914                }
915                else
916                {
917                        objectsFront.push_back(obj);
918                }
919        }
920
921#if 1
922        const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
923#else
924        const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
925        const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
926
927        const float cost = newRenderCost / oldRenderCost;
928#endif
929
930        return cost;
931}
932#endif
933
934#if 1
935
936float BvHierarchy::EvalSah(const BvhTraversalData &tData,
937                                                   const int axis,
938                                                   ObjectContainer &objectsFront,
939                                                   ObjectContainer &objectsBack)
940{
941        // go through the lists, count the number of objects left and right
942        // and evaluate the following cost funcion:
943        // C = ct_div_ci  + (ol + or) / queries
944        PrepareLocalSubdivisionCandidates(tData, axis);
945
946        const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
947        float objectsLeft = 0, objectsRight = totalRenderCost;
948 
949        const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
950        const float boxArea = nodeBbox.SurfaceArea();
951
952        float minSum = 1e20f;
953 
954        float minBorder = nodeBbox.Max(axis);
955        float maxBorder = nodeBbox.Min(axis);
956
957        float areaLeft = 0, areaRight = 0;
958
959        SortableEntryContainer::const_iterator currentPos =
960                mSubdivisionCandidates->begin();
961       
962        vector<float> bordersRight;
963
964        // we keep track of both borders of the bounding boxes =>
965        // store the events in descending order
966
967        bordersRight.resize(mSubdivisionCandidates->size());
968
969        SortableEntryContainer::reverse_iterator rcit =
970                mSubdivisionCandidates->rbegin(), rcit_end =
971                mSubdivisionCandidates->rend();
972
973        vector<float>::reverse_iterator rbit = bordersRight.rbegin();
974
975        for (; rcit != rcit_end; ++ rcit, ++ rbit)
976        {
977                Intersectable *obj = (*rcit).mObject;
978                const AxisAlignedBox3 obox = obj->GetBox();
979
980                if (obox.Min(axis) < minBorder)
981                {
982                        minBorder = obox.Min(axis);
983                }
984
985                (*rbit) = minBorder;
986        }
987
988        // temporary surface areas
989        float al = 0;
990        float ar = boxArea;
991
992        vector<float>::const_iterator bit = bordersRight.begin();
993        SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
994
995        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
996        {
997                Intersectable *obj = (*cit).mObject;
998
999                const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1000               
1001                objectsLeft += renderCost;
1002                objectsRight -= renderCost;
1003
1004                const AxisAlignedBox3 obox = obj->GetBox();
1005
1006                // the borders of the bounding boxes have changed
1007                if (obox.Max(axis) > maxBorder)
1008                {
1009                        maxBorder = obox.Max(axis);
1010                }
1011
1012                minBorder = (*bit);
1013
1014                AxisAlignedBox3 lbox = nodeBbox;
1015                AxisAlignedBox3 rbox = nodeBbox;
1016
1017                lbox.SetMax(axis, maxBorder);
1018                rbox.SetMin(axis, minBorder);
1019
1020                al = lbox.SurfaceArea();
1021                ar = rbox.SurfaceArea();
1022
1023                const bool noValidSplit = ((objectsLeft <= Limits::Small) || (objectsRight <= Limits::Small));
1024                const float sum = noValidSplit ? 1e25f : objectsLeft * al + objectsRight * ar;
1025     
1026                /*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
1027                         << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
1028                cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
1029            cout << "cost= " << sum << endl;*/
1030       
1031                if (sum < minSum)
1032                {       
1033                        minSum = sum;
1034                        areaLeft = al;
1035                        areaRight = ar;
1036
1037                        // objects belong to left side now
1038                        for (; currentPos != (cit + 1); ++ currentPos);
1039                }
1040        }
1041
1042        ////////////
1043        //-- assign object to front and back volume
1044
1045        // belongs to back bv
1046        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1047                objectsBack.push_back((*cit).mObject);
1048       
1049        // belongs to front bv
1050        for (cit = currentPos; cit != cit_end; ++ cit)
1051                objectsFront.push_back((*cit).mObject);
1052
1053        float newCost = minSum / boxArea;
1054        float ratio = newCost / totalRenderCost;
1055 
1056#ifdef GTP_DEBUG
1057        cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1058                 << (int)tData.mNode->mObjects.size() << ")\t area=("
1059                 << areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1060                 << "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1061#endif
1062
1063        return ratio;
1064}
1065
1066#else
1067
1068float BvHierarchy::EvalSah(const BvhTraversalData &tData,
1069                                                   const int axis,
1070                                                   ObjectContainer &objectsFront,
1071                                                   ObjectContainer &objectsBack)
1072{
1073        // go through the lists, count the number of objects left and right
1074        // and evaluate the following cost funcion:
1075        // C = ct_div_ci  + (ol + or) / queries
1076        PrepareLocalSubdivisionCandidates(tData, axis);
1077
1078        const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
1079        float objectsLeft = 0, objectsRight = totalRenderCost;
1080 
1081        const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
1082
1083        const float minBox = nodeBbox.Min(axis);
1084        const float maxBox = nodeBbox.Max(axis);
1085        const float boxArea = nodeBbox.SurfaceArea();
1086
1087        float minSum = 1e20f;
1088 
1089        Vector3 minBorder = nodeBbox.Max();
1090        Vector3 maxBorder = nodeBbox.Min();
1091
1092        float areaLeft = 0, areaRight = 0;
1093
1094        SortableEntryContainer::const_iterator currentPos =
1095                mSubdivisionCandidates->begin();
1096       
1097        vector<Vector3> bordersRight;
1098
1099        // we keep track of both borders of the bounding boxes =>
1100        // store the events in descending order
1101        bordersRight.resize(mSubdivisionCandidates->size());
1102
1103        SortableEntryContainer::reverse_iterator rcit =
1104                mSubdivisionCandidates->rbegin(), rcit_end =
1105                mSubdivisionCandidates->rend();
1106
1107        vector<Vector3>::reverse_iterator rbit = bordersRight.rbegin();
1108
1109        for (; rcit != rcit_end; ++ rcit, ++ rbit)
1110        {
1111                Intersectable *obj = (*rcit).mObject;
1112                const AxisAlignedBox3 obox = obj->GetBox();
1113
1114                for (int i = 0; i < 3; ++ i)
1115                {
1116                        if (obox.Min(i) < minBorder[i])
1117                        {
1118                                minBorder[i] = obox.Min(i);
1119                        }
1120                }
1121
1122                (*rbit) = minBorder;
1123        }
1124
1125        // temporary surface areas
1126        float al = 0;
1127        float ar = boxArea;
1128
1129        vector<Vector3>::const_iterator bit = bordersRight.begin();
1130        SortableEntryContainer::const_iterator cit, cit_end =
1131                mSubdivisionCandidates->end();
1132
1133        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
1134        {
1135                Intersectable *obj = (*cit).mObject;
1136
1137                const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1138               
1139                objectsLeft += renderCost;
1140                objectsRight -= renderCost;
1141
1142                const AxisAlignedBox3 obox = obj->GetBox();
1143
1144                AxisAlignedBox3 lbox = nodeBbox;
1145                AxisAlignedBox3 rbox = nodeBbox;
1146       
1147                // the borders of the left bounding box have changed
1148                for (int i = 0; i < 3; ++ i)
1149                {
1150                        if (obox.Max(i) > maxBorder[i])
1151                        {
1152                                maxBorder[i] = obox.Max(i);
1153                        }
1154                }
1155
1156                minBorder = (*bit);
1157
1158                lbox.SetMax(maxBorder);
1159                rbox.SetMin(minBorder);
1160
1161                al = lbox.SurfaceArea();
1162                ar = rbox.SurfaceArea();
1163       
1164                const bool noValidSplit = ((objectsLeft <= Limits::Small) || (objectsRight <= Limits::Small));
1165                const float sum =  noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
1166     
1167                /*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
1168                         << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
1169                cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
1170            cout << "cost= " << sum << endl;*/
1171       
1172                if (sum < minSum)
1173                {       
1174                        minSum = sum;
1175                        areaLeft = al;
1176                        areaRight = ar;
1177
1178                        // objects belong to left side now
1179                        for (; currentPos != (cit + 1); ++ currentPos);
1180                }
1181        }
1182
1183        /////////////
1184        //-- assign object to front and back volume
1185
1186        // belongs to back bv
1187        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1188                objectsBack.push_back((*cit).mObject);
1189       
1190        // belongs to front bv
1191        for (cit = currentPos; cit != cit_end; ++ cit)
1192                objectsFront.push_back((*cit).mObject);
1193
1194        float newCost = minSum / boxArea;
1195        float ratio = newCost / totalRenderCost;
1196 
1197#ifdef GTP_DEBUG
1198        cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1199                 << (int)tData.mNode->mObjects.size() << ")\t area=("
1200                 << areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1201                 << "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1202#endif
1203
1204        return ratio;
1205}
1206
1207#endif
1208
1209static bool PrepareOutput(const int axis,
1210                                                  const int leaves,
1211                                                  ofstream &sumStats,
1212                                                  ofstream &vollStats,
1213                                                  ofstream &volrStats)
1214{
1215        if ((axis == 0) && (leaves > 0) && (leaves < 90))
1216        {
1217                char str[64];   
1218                sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
1219                sumStats.open(str);
1220                sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
1221                vollStats.open(str);
1222                sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
1223                volrStats.open(str);
1224        }
1225
1226        return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
1227}
1228
1229
1230static void PrintHeuristics(const float objectsRight,
1231                                                        const float sum,
1232                                                        const float volLeft,
1233                                                        const float volRight,
1234                                                        const float viewSpaceVol,
1235                                                        ofstream &sumStats,
1236                                                        ofstream &vollStats,
1237                                                        ofstream &volrStats)
1238{
1239        sumStats
1240                << "#Position\n" << objectsRight << endl
1241                << "#Sum\n" << sum / viewSpaceVol << endl
1242                << "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;
1243
1244        vollStats
1245                << "#Position\n" << objectsRight << endl
1246                << "#Vol\n" << volLeft / viewSpaceVol << endl;
1247
1248        volrStats
1249                << "#Position\n" << objectsRight << endl
1250                << "#Vol\n" << volRight / viewSpaceVol << endl;
1251}
1252
1253
1254float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
1255                                                                                   const int axis,
1256                                                                                   ObjectContainer &objectsFront,
1257                                                                                   ObjectContainer &objectsBack)
1258{
1259        /////////////////////////////////////////////
1260        //-- go through the lists, count the number of objects
1261        //-- left and right and evaluate the cost funcion
1262
1263        // prepare the heuristics by setting mailboxes and counters
1264        const float totalVol = PrepareHeuristics(tData, axis);
1265       
1266        // local helper variables
1267        float volLeft = 0;
1268        float volRight = totalVol;
1269       
1270        const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
1271        float nObjectsLeft = 0;
1272        float nObjectsRight = nTotalObjects;
1273
1274        const float viewSpaceVol =
1275                mViewCellsManager->GetViewSpaceBox().GetVolume();
1276
1277        SortableEntryContainer::const_iterator backObjectsStart =
1278                mSubdivisionCandidates->begin();
1279
1280        /////////////////////////////////
1281        //-- the parameters for the current optimum
1282
1283        float volBack = volLeft;
1284        float volFront = volRight;
1285        float newRenderCost = nTotalObjects * totalVol;
1286
1287#ifdef GTP_DEBUG
1288        ofstream sumStats;
1289        ofstream vollStats;
1290        ofstream volrStats;
1291
1292        const bool printStats = PrepareOutput(axis,
1293                                                                                  mBvhStats.Leaves(),
1294                                                                                  sumStats,
1295                                                                                  vollStats,
1296                                                                                  volrStats);
1297#endif
1298
1299        ///////////////////////
1300        //-- the sweep heuristics
1301        //-- traverse through events and find best split plane
1302
1303        SortableEntryContainer::const_iterator cit,
1304                cit_end = cit_end = mSubdivisionCandidates->end();
1305
1306        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
1307        {
1308                Intersectable *object = (*cit).mObject;
1309       
1310                // evaluate change in l and r volume
1311                // voll = view cells that see only left node (i.e., left pvs)
1312                // volr = view cells that see only right node (i.e., right pvs)
1313                EvalHeuristicsContribution(object, volLeft, volRight);
1314
1315                const float rc = mViewCellsManager->EvalRenderCost(object);
1316
1317                nObjectsLeft += rc;
1318                nObjectsRight -= rc;
1319               
1320                // split is only valid if #objects on left and right is not zero
1321                const bool noValidSplit = ((nObjectsLeft <= Limits::Small) ||
1322                                                                   (nObjectsRight <= Limits::Small));
1323
1324                // the heuristics
1325            const float sum = noValidSplit ?
1326                        1e25f : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;
1327
1328#ifdef GTP_DEBUG
1329                if (printStats)
1330                {
1331                        PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
1332                                                        sumStats, vollStats, volrStats);
1333                }
1334#endif
1335
1336                if (sum < newRenderCost)
1337                {
1338                        newRenderCost = sum;
1339
1340                        volBack = volLeft;
1341                        volFront = volRight;
1342
1343                        // objects belongs to left side now
1344                        for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
1345                }
1346        }
1347
1348        ////////////////////////////////////////
1349        //-- assign object to front and back volume
1350
1351        // belongs to back bv
1352        for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
1353        {
1354                objectsBack.push_back((*cit).mObject);
1355        }
1356        // belongs to front bv
1357        for (cit = backObjectsStart; cit != cit_end; ++ cit)
1358        {
1359                objectsFront.push_back((*cit).mObject);
1360        }
1361
1362        // render cost of the old parent
1363        const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
1364        // the relative cost ratio
1365        const float ratio = newRenderCost / oldRenderCost;
1366
1367#ifdef GTP_DEBUG
1368        Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
1369                  << "back pvs: " << (int)objectsBack.size() << " front pvs: "
1370                  << (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl
1371                  << "back p: " << volBack / viewSpaceVol << " front p "
1372                  << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
1373                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: "
1374                  << newRenderCost / viewSpaceVol << endl
1375                  << "render cost decrease: "
1376                  << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
1377#endif
1378
1379        return ratio;
1380}
1381
1382
1383void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
1384                                                                                                        const int axis)                                                                                 
1385{
1386        //-- insert object queries
1387        ObjectContainer *objects = mUseGlobalSorting ?
1388                tData.mSortedObjects[axis] : &tData.mNode->mObjects;
1389
1390        CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
1391}
1392
1393
1394void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
1395                                                                                                  SortableEntryContainer **subdivisionCandidates,
1396                                                                                                  const bool sort,
1397                                                                                                  const int axis)
1398{
1399        (*subdivisionCandidates)->clear();
1400
1401        // compute requested size and look if subdivision candidate has to be recomputed
1402        const int requestedSize = (int)objects.size() * 2;
1403       
1404        // creates a sorted split candidates array
1405        if ((*subdivisionCandidates)->capacity() > 500000 &&
1406                requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
1407        {
1408        delete (*subdivisionCandidates);
1409                (*subdivisionCandidates) = new SortableEntryContainer;
1410        }
1411
1412        (*subdivisionCandidates)->reserve(requestedSize);
1413
1414        ObjectContainer::const_iterator oit, oit_end = objects.end();
1415
1416        for (oit = objects.begin(); oit < oit_end; ++ oit)
1417        {
1418                Intersectable *object = *oit;
1419                const AxisAlignedBox3 &box = object->GetBox();
1420                const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
1421
1422                (*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
1423        }
1424
1425        if (sort)
1426        {       // no presorted candidate list
1427                stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
1428        }
1429}
1430
1431
1432const BvhStatistics &BvHierarchy::GetStatistics() const
1433{
1434        return mBvhStats;
1435}
1436
1437
1438float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData,
1439                                                                         const int axis)
1440{       
1441        BvhLeaf *leaf = tData.mNode;
1442        float vol = 0;
1443
1444    // sort so we can use a sweep from right to left
1445        PrepareLocalSubdivisionCandidates(tData, axis);
1446       
1447        // collect and mark the view cells as belonging to front pvs
1448        ViewCellContainer viewCells;
1449
1450        const int numRays = CollectViewCells(tData.mNode->mObjects, viewCells, true, true);
1451        //cout << "number of rays: " << numRays << endl;
1452
1453        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1454        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1455        {
1456#if USE_VOLUMES_FOR_HEURISTICS
1457                const float volIncr = (*vit)->GetVolume();
1458#else
1459                const float volIncr = 1.0f;
1460#endif
1461                vol += volIncr;
1462        }
1463
1464        // we will mail view cells switching to the back side
1465        ViewCell::NewMail();
1466       
1467        return vol;
1468}
1469
1470///////////////////////////////////////////////////////////
1471
1472
1473void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
1474                                                                                         float &volLeft,
1475                                                                                         float &volRight)
1476{
1477        // collect all view cells associated with this objects
1478        // (also multiple times, if they are pierced by several rays)
1479        ViewCellContainer viewCells;
1480        const bool useMailboxing = false;
1481
1482        CollectViewCells(obj, viewCells, useMailboxing, false, true);
1483
1484        // classify view cells and compute volume contri accordingly
1485        // possible view cell classifications:
1486        // view cell mailed => view cell can be seen from left child node
1487        // view cell counter > 0 view cell can be seen from right child node
1488        // combined: view cell volume belongs to both nodes
1489        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1490       
1491        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1492        {
1493                // view cells can also be seen from left child node
1494                ViewCell *viewCell = *vit;
1495#if USE_VOLUMES_FOR_HEURISTICS
1496                const float vol = viewCell->GetVolume();
1497#else
1498                const float vol = 1.0f;
1499#endif
1500                if (!viewCell->Mailed())
1501                {
1502                        viewCell->Mail();
1503                        // we now see view cell from both nodes
1504                        // => add volume to left node
1505                        volLeft += vol;
1506                }
1507
1508                // last reference into the right node
1509                if (-- viewCell->mCounter == 0)
1510                {       
1511                        // view cell was previously seen from both nodes  =>
1512                        // remove volume from right node
1513                        volRight -= vol;
1514                }
1515        }
1516}
1517
1518
1519void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
1520{
1521        mViewCellsManager = vcm;
1522}
1523
1524
1525AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
1526{
1527        return mBoundingBox;
1528}
1529
1530
1531float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
1532                                                                                 ObjectContainer &frontObjects,
1533                                                                                 ObjectContainer &backObjects,
1534                                                                                 bool useVisibilityBasedHeuristics)
1535{
1536        if (mIsInitialSubdivision)
1537        {
1538                ApplyInitialSplit(tData, frontObjects, backObjects);
1539                return 0;
1540        }
1541
1542        ObjectContainer nFrontObjects[3];
1543        ObjectContainer nBackObjects[3];
1544        float nCostRatio[3];
1545
1546        int sAxis = 0;
1547        int bestAxis = -1;
1548
1549        if (mOnlyDrivingAxis)
1550        {
1551                const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
1552                sAxis = box.Size().DrivingAxis();
1553        }
1554
1555        // if #rays high consider only use a subset of the rays for
1556        // visibility based heuristics
1557        VssRay::NewMail();
1558
1559        if ((mMaxTests < tData.mNumRays) &&      mUseCostHeuristics && useVisibilityBasedHeuristics)
1560        {
1561                VssRayContainer rays;
1562
1563                // maximal 2 objects share the same ray
1564                rays.reserve(tData.mNumRays * 2);
1565                CollectRays(tData.mNode->mObjects, rays);
1566
1567                const float prop = (float)mMaxTests / (float)rays.size();
1568
1569                VssRayContainer::const_iterator rit, rit_end = rays.end();
1570
1571                // mail rays which will not be considered
1572                for (rit = rays.begin(); rit != rit_end; ++ rit)
1573                {
1574                        if (Random(1.0f) > prop)
1575                        {
1576                                (*rit)->Mail();
1577                        }
1578                }               
1579        }
1580
1581        ////////////////////////////////////
1582        //-- evaluate split cost for all three axis
1583       
1584        for (int axis = 0; axis < 3; ++ axis)
1585        {
1586                if (!mOnlyDrivingAxis || (axis == sAxis))
1587                {
1588                        if (mUseCostHeuristics)
1589                        {
1590                                //////////////////////////////////
1591                //-- split objects using heuristics
1592                               
1593                                if (useVisibilityBasedHeuristics)
1594                                {
1595                                        ///////////
1596                                        //-- heuristics using objects weighted by view cells volume
1597                                        nCostRatio[axis] =
1598                                                EvalLocalCostHeuristics(tData,
1599                                                                                                axis,
1600                                                                                                nFrontObjects[axis],
1601                                                                                                nBackObjects[axis]);
1602                                }
1603                                else
1604                                {       
1605                                        //////////////////
1606                                        //-- view cells not constructed yet     => use surface area heuristic                   
1607                                        nCostRatio[axis] = EvalSah(tData,
1608                                                                                           axis,
1609                                                                                           nFrontObjects[axis],
1610                                                                                           nBackObjects[axis]);
1611                                }
1612                        }
1613                        else
1614                        {
1615                                //-- split objects using some simple criteria
1616                                nCostRatio[axis] =
1617                                        EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1618                        }
1619
1620                        // no good results for degenerate axis split
1621                        if (1 &&
1622                                (tData.mNode->GetBoundingBox().Size(axis) < 0.0001))//Limits::Small))
1623                        {
1624                                nCostRatio[axis] += 9999;
1625                        }
1626
1627                        if ((bestAxis == -1) || (nCostRatio[axis] < nCostRatio[bestAxis]))
1628                        {
1629                                bestAxis = axis;
1630                        }
1631                }
1632        }
1633
1634    ////////////////
1635        //-- assign values
1636
1637        frontObjects = nFrontObjects[bestAxis];
1638        backObjects = nBackObjects[bestAxis];
1639
1640        //cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1641        return nCostRatio[bestAxis];
1642}
1643
1644
1645int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
1646{
1647        int nRays = 0;
1648        VssRayContainer::const_iterator rit, rit_end = rays.end();
1649
1650        VssRay::NewMail();
1651
1652    for (rit = rays.begin(); rit != rays.end(); ++ rit)
1653        {
1654                VssRay *ray = (*rit);
1655
1656                if (ray->mTerminationObject)
1657                {
1658                        ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
1659                        if (!ray->Mailed())
1660                        {
1661                                ray->Mail();
1662                                ++ nRays;
1663                        }
1664                }
1665
1666#if COUNT_ORIGIN_OBJECTS
1667
1668                if (ray->mOriginObject)
1669                {
1670                        ray->mOriginObject->GetOrCreateRays()->push_back(ray);
1671
1672                        if (!ray->Mailed())
1673                        {
1674                                ray->Mail();
1675                                ++ nRays;
1676                        }
1677                }
1678#endif
1679        }
1680
1681        return nRays;
1682}
1683
1684
1685void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
1686{
1687        const float costDecr = sc.GetRenderCostDecrease();     
1688
1689        mSubdivisionStats
1690                        << "#Leaves\n" << mBvhStats.Leaves() << endl
1691                        << "#RenderCostDecrease\n" << costDecr << endl
1692                        << "#TotalRenderCost\n" << mTotalCost << endl
1693                        << "#EntriesInPvs\n" << mPvsEntries << endl;
1694}
1695
1696
1697void BvHierarchy::CollectRays(const ObjectContainer &objects,
1698                                                          VssRayContainer &rays) const
1699{
1700        VssRay::NewMail();
1701        ObjectContainer::const_iterator oit, oit_end = objects.end();
1702
1703        // evaluate reverse pvs and view cell volume on left and right cell
1704        // note: should I take all leaf objects or rather the objects hit by rays?
1705        for (oit = objects.begin(); oit != oit_end; ++ oit)
1706        {
1707                Intersectable *obj = *oit;
1708                VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1709
1710                for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1711                {
1712                        VssRay *ray = (*rit);
1713
1714                        if (!ray->Mailed())
1715                        {
1716                                ray->Mail();
1717                                rays.push_back(ray);
1718                        }
1719                }
1720        }
1721}
1722
1723
1724float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)// const
1725{
1726#if USE_BETTER_RENDERCOST_EST
1727        ObjectContainer::const_iterator oit, oit_end = objects.end();
1728
1729        for (oit = objects.begin(); oit != oit_end; ++ oit)
1730        {
1731                objRenderCost += ViewCellsManager::GetRendercost(*oit);
1732        }
1733#else
1734        return (float)objects.size();
1735#endif
1736}
1737
1738
1739float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const
1740{
1741        ////////////////
1742        //-- surface area heuristics
1743
1744        if (leaf->mObjects.empty())
1745                return 0.0f;
1746
1747        const AxisAlignedBox3 box = GetBoundingBox(leaf);
1748        const float area = box.SurfaceArea();
1749        const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
1750
1751        return EvalAbsCost(leaf->mObjects) * area / viewSpaceArea;
1752}
1753
1754
1755float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
1756{       
1757        ///////////////
1758        //-- render cost heuristics
1759
1760        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1761
1762        // probability that view point lies in a view cell which sees this node
1763        const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
1764    const float objRenderCost = EvalAbsCost(objects);
1765       
1766        return objRenderCost * p;
1767}
1768
1769
1770float BvHierarchy::EvalProb(const ObjectContainer &objects) const
1771{       
1772        ///////////////
1773        //-- render cost heuristics
1774
1775        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1776
1777        // probability that view point lies in a view cell which sees this node
1778        return EvalViewCellsVolume(objects) / viewSpaceVol;
1779}
1780
1781
1782AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
1783                                                                                         const AxisAlignedBox3 *parentBox) const
1784{
1785        // if there are no objects in this box, box size is set to parent box size.
1786        // Question: Invalidate box instead?
1787        if (parentBox && objects.empty())
1788                return *parentBox;
1789
1790        AxisAlignedBox3 box;
1791        box.Initialize();
1792
1793        ObjectContainer::const_iterator oit, oit_end = objects.end();
1794
1795        for (oit = objects.begin(); oit != oit_end; ++ oit)
1796        {
1797                Intersectable *obj = *oit;
1798                // grow bounding box to include all objects
1799                box.Include(obj->GetBox());
1800        }
1801
1802        return box;
1803}
1804
1805
1806void BvHierarchy::CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const
1807{
1808        stack<BvhNode *> nodeStack;
1809        nodeStack.push(root);
1810
1811        while (!nodeStack.empty())
1812        {
1813                BvhNode *node = nodeStack.top();
1814                nodeStack.pop();
1815
1816                if (node->IsLeaf())
1817                {
1818                        BvhLeaf *leaf = (BvhLeaf *)node;
1819                        leaves.push_back(leaf);
1820                }
1821                else
1822                {
1823                        BvhInterior *interior = (BvhInterior *)node;
1824
1825                        nodeStack.push(interior->GetBack());
1826                        nodeStack.push(interior->GetFront());
1827                }
1828        }
1829}
1830
1831
1832AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1833{
1834        return node->GetBoundingBox();
1835}
1836
1837
1838int BvHierarchy::CollectViewCells(const ObjectContainer &objects,
1839                                                                  ViewCellContainer &viewCells,
1840                                                                  const bool setCounter,
1841                                                                  const bool onlyUnmailedRays) const
1842{
1843        ViewCell::NewMail();
1844        ObjectContainer::const_iterator oit, oit_end = objects.end();
1845
1846        int numRays = 0;
1847        // loop through all object and collect view cell pvs of this node
1848        for (oit = objects.begin(); oit != oit_end; ++ oit)
1849        {
1850                // always use only mailed objects
1851                numRays += CollectViewCells(*oit, viewCells, true, setCounter, onlyUnmailedRays);
1852        }
1853
1854        return numRays;
1855}
1856
1857
1858int BvHierarchy::CollectViewCells(Intersectable *obj,
1859                                                                  ViewCellContainer &viewCells,
1860                                                                  const bool useMailBoxing,
1861                                                                  const bool setCounter,
1862                                                                  const bool onlyUnmailedRays) const
1863{
1864        VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1865
1866        int numRays = 0;
1867
1868        for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1869        {
1870                VssRay *ray = (*rit);
1871
1872                if (onlyUnmailedRays && ray->Mailed())
1873                {
1874                        continue;
1875                }
1876
1877                ++ numRays;
1878
1879                ViewCellContainer tmpViewCells;
1880                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1881
1882                // matt: probably slow to allocate memory for view cells every time
1883                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1884
1885                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1886                {
1887                        ViewCell *vc = *vit;
1888
1889                        // store view cells
1890                        if (!useMailBoxing || !vc->Mailed())
1891                        {
1892                                if (useMailBoxing) // => view cell not mailed
1893                                {
1894                                        vc->Mail();
1895                                        if (setCounter)
1896                                        {
1897                                                vc->mCounter = 0;
1898                                        }
1899                                }
1900
1901                                viewCells.push_back(vc);
1902                        }
1903                       
1904                        if (setCounter)
1905                        {
1906                                ++ vc->mCounter;
1907                        }
1908                }
1909        }
1910
1911        return numRays;
1912}
1913
1914
1915int BvHierarchy::CountViewCells(Intersectable *obj) const
1916{
1917        int result = 0;
1918       
1919        VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1920
1921        for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1922        {
1923                VssRay *ray = (*rit);
1924                ViewCellContainer tmpViewCells;
1925       
1926                mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1927               
1928                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1929                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1930                {
1931                        ViewCell *vc = *vit;
1932
1933                        // store view cells
1934                        if (!vc->Mailed())
1935                        {
1936                                vc->Mail();
1937                                ++ result;
1938                        }
1939                }
1940        }
1941
1942        return result;
1943}
1944
1945
1946int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
1947{
1948        int nViewCells = 0;
1949        ViewCell::NewMail();
1950        ObjectContainer::const_iterator oit, oit_end = objects.end();
1951
1952        // loop through all object and collect view cell pvs of this node
1953        for (oit = objects.begin(); oit != oit_end; ++ oit)
1954        {
1955                nViewCells += CountViewCells(*oit);
1956        }
1957
1958        return nViewCells;
1959}
1960
1961
1962void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1963                                                                                 vector<SubdivisionCandidate *> &dirtyList,
1964                                                                                 const bool onlyUnmailed)
1965{
1966        BvhTraversalData &tData = sc->mParentData;
1967        BvhLeaf *node = tData.mNode;
1968       
1969        ViewCellContainer viewCells;
1970        //ViewCell::NewMail();
1971        int numRays = CollectViewCells(node->mObjects, viewCells, false, false);
1972
1973        if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
1974       
1975        // split candidates handling
1976        // these view cells  are thrown into dirty list
1977        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1978
1979        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1980        {
1981        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1982                VspLeaf *leaf = vc->mLeaves[0];
1983       
1984                SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
1985               
1986                // is this leaf still a split candidate?
1987                if (candidate && (!onlyUnmailed || !candidate->Mailed()))
1988                {
1989                        candidate->Mail();
1990                        candidate->SetDirty(true);
1991                        dirtyList.push_back(candidate);
1992                }
1993        }
1994}
1995
1996
1997BvhNode *BvHierarchy::GetRoot() const
1998{
1999        return mRoot;
2000}
2001
2002
2003bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
2004{
2005        ObjectContainer::const_iterator oit =
2006                lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
2007                               
2008        // objects sorted by id
2009        if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
2010        {
2011                return true;
2012        }
2013        else
2014        {
2015                return false;
2016        }
2017}
2018
2019
2020BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
2021{
2022        // rather use the simple version
2023        if (!object)
2024                return NULL;
2025        return object->mBvhLeaf;
2026       
2027        ///////////////////////////////////////
2028        // start from root of tree
2029       
2030        if (node == NULL)
2031                node = mRoot;
2032       
2033        vector<BvhLeaf *> leaves;
2034
2035        stack<BvhNode *> nodeStack;
2036        nodeStack.push(node);
2037 
2038        BvhLeaf *leaf = NULL;
2039 
2040        while (!nodeStack.empty()) 
2041        {
2042                BvhNode *node = nodeStack.top();
2043                nodeStack.pop();
2044       
2045                if (node->IsLeaf())
2046                {
2047                        leaf = dynamic_cast<BvhLeaf *>(node);
2048
2049                        if (IsObjectInLeaf(leaf, object))
2050                        {
2051                                return leaf;
2052                        }
2053                }
2054                else   
2055                {       
2056                        // find point
2057                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
2058       
2059                        if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
2060                        {
2061                                nodeStack.push(interior->GetBack());
2062                        }
2063                       
2064                        // search both sides as we are using bounding volumes
2065                        if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
2066                        {
2067                                nodeStack.push(interior->GetFront());
2068                        }
2069                }
2070        }
2071 
2072        return leaf;
2073}
2074
2075
2076bool BvHierarchy::Export(OUT_STREAM &stream)
2077{
2078        ExportNode(mRoot, stream);
2079
2080        return true;
2081}
2082
2083
2084void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
2085{
2086        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2087
2088        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2089        {
2090                stream << (*oit)->GetId() << " ";
2091        }
2092}
2093
2094
2095void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
2096{
2097        if (node->IsLeaf())
2098        {
2099                BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
2100                const AxisAlignedBox3 box = leaf->GetBoundingBox();
2101                stream << "<Leaf"
2102                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2103                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
2104                           << " objects=\"";
2105               
2106                //-- export objects
2107                // tmp matt
2108                if (1) ExportObjects(leaf, stream);
2109               
2110                stream << "\" />" << endl;
2111        }
2112        else
2113        {       
2114                BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
2115                const AxisAlignedBox3 box = interior->GetBoundingBox();
2116
2117                stream << "<Interior"
2118                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2119                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
2120                           << "\">" << endl;
2121
2122                ExportNode(interior->GetBack(), stream);
2123                ExportNode(interior->GetFront(), stream);
2124
2125                stream << "</Interior>" << endl;
2126        }
2127}
2128
2129
2130float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
2131{
2132        float vol = 0;
2133
2134        ViewCellContainer viewCells;
2135       
2136        // we have to account for all view cells that can
2137        // be seen from the objects
2138        int numRays = CollectViewCells(objects, viewCells, false, false);
2139
2140        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2141
2142        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2143        {
2144                vol += (*vit)->GetVolume();
2145        }
2146
2147        return vol;
2148}
2149
2150
2151void BvHierarchy::Initialise(const ObjectContainer &objects)
2152{
2153        AxisAlignedBox3 box = EvalBoundingBox(objects);
2154
2155        ///////
2156        //-- create new root
2157
2158        BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
2159        bvhleaf->mObjects = objects;
2160        mRoot = bvhleaf;
2161
2162        // compute bounding box from objects
2163        mBoundingBox = mRoot->GetBoundingBox();
2164
2165        // associate root with current objects
2166        AssociateObjectsWithLeaf(bvhleaf);
2167}
2168
2169
2170/*
2171Mesh *BvHierarchy::MergeLeafToMesh()
2172{
2173        vector<BvhLeaf *> leaves;
2174        CollectLeaves(leaves);
2175
2176        vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2177
2178        for (lit = leaves.begin(); lit != lit_end; ++ lit)
2179        {
2180                Mesh *mesh = MergeLeafToMesh(*lit);
2181        }
2182}*/
2183
2184
2185void BvHierarchy::PrepareConstruction(SplitQueue &tQueue,
2186                                                                          const VssRayContainer &sampleRays,
2187                                                                          const ObjectContainer &objects)
2188{
2189        ///////////////////////////////////////
2190        //-- we assume that we have objects sorted by their id =>
2191        //-- we don't have to sort them here and an binary search
2192        //-- for identifying if a object is in a leaf.
2193       
2194        mBvhStats.Reset();
2195        mBvhStats.Start();
2196        mBvhStats.nodes = 1;
2197               
2198        // store pointer to this tree
2199        BvhSubdivisionCandidate::sBvHierarchy = this;
2200       
2201        // root and bounding box was already constructed
2202        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);
2203
2204        // only rays intersecting objects in node are interesting
2205        const int nRays = AssociateObjectsWithRays(sampleRays);
2206        //cout << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
2207
2208        // probability that volume is "seen" from the view cells
2209        const float prop = EvalViewCellsVolume(objects) / GetViewSpaceVolume();
2210
2211        // create bvh traversal data
2212        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2213       
2214        // create sorted object lists for the first data
2215        if (mUseGlobalSorting)
2216        {
2217                AssignInitialSortedObjectList(oData, objects);
2218        }
2219       
2220
2221        ///////////////////
2222        //-- add first candidate for object space partition     
2223
2224        mTotalCost = EvalRenderCost(objects);
2225        mPvsEntries = CountViewCells(objects);
2226
2227        oData.mCorrectedPvs = oData.mPvs = (float)mPvsEntries;
2228        oData.mCorrectedVolume = oData.mVolume = prop;
2229       
2230        BvhSubdivisionCandidate *oSubdivisionCandidate =
2231                new BvhSubdivisionCandidate(oData);
2232
2233        bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2234
2235        if (mApplyInitialPartition)
2236        {
2237                vector<SubdivisionCandidate *> candidateContainer;
2238
2239                mIsInitialSubdivision = true;
2240               
2241                // evaluate priority
2242                EvalSubdivisionCandidate(*oSubdivisionCandidate);
2243                PrintSubdivisionStats(*oSubdivisionCandidate);
2244
2245                ApplyInitialSubdivision(oSubdivisionCandidate, candidateContainer);             
2246
2247                mIsInitialSubdivision = false;
2248
2249                vector<SubdivisionCandidate *>::const_iterator cit, cit_end = candidateContainer.end();
2250
2251                for (cit = candidateContainer.begin(); cit != cit_end; ++ cit)
2252                {
2253                        BvhSubdivisionCandidate *sCandidate = dynamic_cast<BvhSubdivisionCandidate *>(*cit);
2254                       
2255                        // reevaluate priority
2256                        EvalSubdivisionCandidate(*sCandidate);
2257                        tQueue.Push(sCandidate);
2258                }
2259        }
2260        else
2261        {
2262                // evaluate priority
2263                EvalSubdivisionCandidate(*oSubdivisionCandidate);
2264                PrintSubdivisionStats(*oSubdivisionCandidate);
2265
2266                tQueue.Push(oSubdivisionCandidate);
2267        }
2268               
2269        cout << "size of initial bv subdivision: " << GetStatistics().Leaves() << endl;
2270}
2271
2272
2273void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData,
2274                                                                                                const ObjectContainer &objects)
2275{
2276        // we sort the objects as a preprocess so they don't have
2277        // to be sorted for each split
2278        for (int i = 0; i < 3; ++ i)
2279        {
2280                SortableEntryContainer *sortedObjects = new SortableEntryContainer();
2281
2282                CreateLocalSubdivisionCandidates(objects,
2283                                                                             &sortedObjects,
2284                                                                                 true,
2285                                                                                 i);
2286               
2287                // copy list into traversal data list
2288                tData.mSortedObjects[i] = new ObjectContainer();
2289                tData.mSortedObjects[i]->reserve((int)objects.size());
2290
2291                SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
2292
2293                for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
2294                {
2295                        tData.mSortedObjects[i]->push_back((*oit).mObject);
2296                }
2297
2298                delete sortedObjects;
2299        }
2300
2301        // last sorted list: by size
2302        tData.mSortedObjects[3] = new ObjectContainer();
2303        tData.mSortedObjects[3]->reserve((int)objects.size());
2304
2305        *(tData.mSortedObjects[3]) = objects;
2306        stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
2307}
2308
2309
2310void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
2311                                                                          BvhTraversalData &frontData,
2312                                                                          BvhTraversalData &backData)
2313{
2314        Intersectable::NewMail();
2315
2316        // we sorted the objects as a preprocess so they don't have
2317        // to be sorted for each split
2318        ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
2319
2320        for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
2321        {
2322                (*fit)->Mail();
2323        }
2324
2325        for (int i = 0; i < 4; ++ i)
2326        {
2327                frontData.mSortedObjects[i] = new ObjectContainer();
2328                backData.mSortedObjects[i] = new ObjectContainer();
2329
2330                frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2331                backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2332
2333                ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
2334
2335                for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
2336                {
2337                        if ((*oit)->Mailed())
2338                        {
2339                                frontData.mSortedObjects[i]->push_back(*oit);
2340                        }
2341                        else
2342                        {
2343                                backData.mSortedObjects[i]->push_back(*oit);
2344                        }
2345                }
2346        }
2347}
2348
2349
2350void BvHierarchy::Reset(SplitQueue &tQueue,
2351                                                const VssRayContainer &sampleRays,
2352                                                const ObjectContainer &objects)
2353{
2354        // reset stats
2355        mBvhStats.Reset();
2356        mBvhStats.Start();
2357        mBvhStats.nodes = 1;
2358
2359        // reset root
2360        DEL_PTR(mRoot);
2361       
2362        BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
2363        bvhleaf->mObjects = objects;
2364        mRoot = bvhleaf;
2365       
2366        //mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2367        // probability that volume is "seen" from the view cells
2368        const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2369        const float prop = EvalViewCellsVolume(objects);
2370
2371        const int nRays = CountRays(objects);
2372        BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);
2373
2374        // create bvh traversal data
2375        BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2376
2377        AssignInitialSortedObjectList(oData, objects);
2378       
2379
2380        ///////////////////
2381        //-- add first candidate for object space partition     
2382
2383        BvhSubdivisionCandidate *oSubdivisionCandidate =
2384                new BvhSubdivisionCandidate(oData);
2385
2386        EvalSubdivisionCandidate(*oSubdivisionCandidate);
2387        bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2388
2389        mTotalCost = (float)objects.size() * prop;
2390
2391        PrintSubdivisionStats(*oSubdivisionCandidate);
2392
2393        tQueue.Push(oSubdivisionCandidate);
2394}
2395
2396
2397void BvhStatistics::Print(ostream &app) const
2398{
2399        app << "=========== BvHierarchy statistics ===============\n";
2400
2401        app << setprecision(4);
2402
2403        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
2404
2405        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
2406
2407        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
2408
2409        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
2410
2411        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
2412
2413        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
2414                << maxCostNodes * 100 / (double)Leaves() << endl;
2415
2416        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
2417                << minProbabilityNodes * 100 / (double)Leaves() << endl;
2418
2419
2420        //////////////////////////////////////////////////
2421       
2422        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
2423                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
2424       
2425        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
2426
2427        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
2428
2429        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
2430
2431       
2432        ////////////////////////////////////////////////////////
2433       
2434        app << "#N_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
2435                << minObjectsNodes * 100 / (double)Leaves() << endl;
2436
2437        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
2438
2439        app << "#N_MINOBJECTREFS  ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
2440
2441        app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
2442       
2443        app << "#N_PAVGOBJECTSLEAVES  ( average object refs / leaf)\n" << AvgObjectRefs() << endl;
2444
2445
2446        ////////////////////////////////////////////////////////
2447       
2448        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with mininum rays )\n"
2449                << minRaysNodes * 100 / (double)Leaves() << endl;
2450
2451        app << "#N_MAXRAYREFS  ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";
2452
2453        app << "#N_MINRAYREFS  ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
2454       
2455        app << "#N_PAVGRAYLEAVES  ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
2456       
2457        app << "#N_PAVGRAYCONTRIBLEAVES  ( Average ray contribution)\n" <<
2458                rayRefs / (double)objectRefs << endl;
2459
2460        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<<
2461                maxRayContriNodes * 100 / (double)Leaves() << endl;
2462
2463        app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
2464
2465        app << "========== END OF BvHierarchy statistics ==========\n";
2466}
2467
2468
2469// TODO: return memory usage in MB
2470float BvHierarchy::GetMemUsage() const
2471{
2472        return (float)(sizeof(BvHierarchy)
2473                                   + mBvhStats.Leaves() * sizeof(BvhLeaf)
2474                                   + mBvhStats.Interior() * sizeof(BvhInterior)
2475                                   ) / float(1024 * 1024);
2476}
2477
2478
2479void BvHierarchy::SetActive(BvhNode *node) const
2480{
2481        vector<BvhLeaf *> leaves;
2482
2483        // sets the pointers to the currently active view cells
2484        CollectLeaves(node, leaves);
2485        vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2486
2487        for (lit = leaves.begin(); lit != lit_end; ++ lit)
2488        {
2489                (*lit)->SetActiveNode(node);
2490        }
2491}
2492
2493
2494BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
2495                                                                           SubdivisionCandidate *splitCandidate)
2496{
2497        BvhSubdivisionCandidate *sc =
2498                dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
2499        BvhTraversalData &tData = sc->mParentData;
2500
2501        BvhNode *currentNode = tData.mNode;
2502        BvhNode *oldNode = (BvhNode *)splitCandidate->mEvaluationHack;
2503
2504        if (!oldNode->IsLeaf())
2505        {       
2506                //////////////
2507                //-- continue subdivision
2508
2509                BvhTraversalData tFrontData;
2510                BvhTraversalData tBackData;
2511                       
2512                BvhInterior *oldInterior = dynamic_cast<BvhInterior *>(oldNode);
2513               
2514                sc->mFrontObjects.clear();
2515                sc->mBackObjects.clear();
2516
2517                oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
2518                oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
2519               
2520                // evaluate the changes in render cost and pvs entries
2521                EvalSubdivisionCandidate(*sc, false);
2522
2523                // create new interior node and two leaf node
2524                currentNode = SubdivideNode(*sc, tFrontData, tBackData);
2525       
2526                //oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
2527                //oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
2528               
2529                //oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
2530                //oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
2531               
2532                ///////////////////////////
2533                //-- push the new split candidates on the queue
2534               
2535                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
2536                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
2537
2538                frontCandidate->SetPriority((float)-oldInterior->GetFront()->GetTimeStamp());
2539                backCandidate->SetPriority((float)-oldInterior->GetBack()->GetTimeStamp());
2540
2541                frontCandidate->mEvaluationHack = oldInterior->GetFront();
2542                backCandidate->mEvaluationHack = oldInterior->GetBack();
2543
2544                // cross reference
2545                tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
2546                tBackData.mNode->SetSubdivisionCandidate(backCandidate);
2547
2548                //cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
2549                tQueue.Push(frontCandidate);
2550                tQueue.Push(backCandidate);
2551        }
2552
2553        /////////////////////////////////
2554        //-- node is a leaf => terminate traversal
2555
2556        if (currentNode->IsLeaf())
2557        {
2558                // this leaf is no candidate for splitting anymore
2559                // => detach subdivision candidate
2560                tData.mNode->SetSubdivisionCandidate(NULL);
2561                // detach node so we don't delete it with the traversal data
2562                tData.mNode = NULL;
2563        }
2564       
2565        return currentNode;
2566}
2567
2568
2569void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box,
2570                                                                 ObjectContainer &objects)
2571{
2572  stack<BvhNode *> nodeStack;
2573 
2574  nodeStack.push(mRoot);
2575
2576  while (!nodeStack.empty()) {
2577        BvhNode *node = nodeStack.top();
2578       
2579        nodeStack.pop();
2580        if (node->IsLeaf()) {
2581          BvhLeaf *leaf = (BvhLeaf *)node;
2582          if (Overlap(box, leaf->GetBoundingBox())) {
2583                Intersectable *object = leaf;
2584                if (!object->Mailed()) {
2585                  object->Mail();
2586                  objects.push_back(object);
2587                }
2588          }
2589        }
2590        else
2591          {
2592                BvhInterior *interior = (BvhInterior *)node;
2593                if (Overlap(box, interior->GetBoundingBox())) {
2594                  bool pushed = false;
2595                  if (!interior->GetFront()->Mailed()) {
2596                        nodeStack.push(interior->GetFront());
2597                        pushed = true;
2598                  }
2599                  if (!interior->GetBack()->Mailed()) {
2600                        nodeStack.push(interior->GetBack());
2601                        pushed = true;
2602                  }
2603                  // avoid traversal of this node in the next query
2604                  if (!pushed)
2605                        interior->Mail();
2606                }
2607          }
2608  }
2609}
2610
2611
2612void BvHierarchy::CreateUniqueObjectIds()
2613{
2614        stack<BvhNode *> nodeStack;
2615        nodeStack.push(mRoot);
2616
2617        int currentId = 0;
2618        while (!nodeStack.empty())
2619        {
2620                BvhNode *node = nodeStack.top();
2621                nodeStack.pop();
2622
2623                node->SetId(currentId ++);
2624
2625                if (!node->IsLeaf())
2626                {
2627                        BvhInterior *interior = (BvhInterior *)node;
2628
2629                        nodeStack.push(interior->GetFront());
2630                        nodeStack.push(interior->GetBack());
2631                }
2632        }
2633}
2634
2635
2636void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
2637                                                                                  vector<SubdivisionCandidate *> &candidateContainer)
2638{
2639        SplitQueue tempQueue;
2640        tempQueue.Push(firstCandidate);
2641
2642        while (!tempQueue.Empty())
2643        {
2644                SubdivisionCandidate *candidate = tempQueue.Top();
2645                tempQueue.Pop();
2646
2647                BvhSubdivisionCandidate *bsc =
2648                        dynamic_cast<BvhSubdivisionCandidate *>(candidate);
2649
2650                if (!InitialTerminationCriteriaMet(bsc->mParentData))
2651                {
2652                        const bool globalCriteriaMet = GlobalTerminationCriteriaMet(bsc->mParentData);
2653               
2654                        BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet);
2655
2656                        // not needed anymore
2657                        delete bsc;
2658                }
2659                else // initial preprocessing  finished for this candidate
2660                {
2661                        // add to candidate container
2662                        candidateContainer.push_back(bsc);
2663                }
2664        }
2665}
2666
2667
2668void BvHierarchy::ApplyInitialSplit(const BvhTraversalData &tData,
2669                                                                        ObjectContainer &frontObjects,
2670                                                                        ObjectContainer &backObjects)
2671{
2672        ObjectContainer *objects = tData.mSortedObjects[3];
2673
2674        ObjectContainer::const_iterator oit, oit_end = objects->end();
2675   
2676        float maxAreaDiff = -1.0f;
2677
2678        ObjectContainer::const_iterator backObjectsStart = objects->begin();
2679
2680        for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit)
2681        {
2682                Intersectable *objS = *oit;
2683                Intersectable *objL = *(oit + 1);
2684               
2685                const float areaDiff =
2686                                objL->GetBox().SurfaceArea() - objS->GetBox().SurfaceArea();
2687
2688                if (areaDiff > maxAreaDiff)
2689                {
2690                        maxAreaDiff = areaDiff;
2691                        backObjectsStart = oit + 1;
2692                }
2693        }
2694
2695        // belongs to back bv
2696        for (oit = objects->begin(); oit != backObjectsStart; ++ oit)
2697        {
2698                frontObjects.push_back(*oit);
2699        }
2700
2701        // belongs to front bv
2702        for (oit = backObjectsStart; oit != oit_end; ++ oit)
2703        {
2704                backObjects.push_back(*oit);
2705        }
2706       
2707        cout << "front: " << (int)frontObjects.size() << " back: " << (int)backObjects.size() << " "
2708                 << backObjects.front()->GetBox().SurfaceArea() - frontObjects.back()->GetBox().SurfaceArea() << endl;
2709}
2710
2711
2712inline static float AreaRatio(Intersectable *smallObj, Intersectable *largeObj)
2713{
2714        const float areaSmall = smallObj->GetBox().SurfaceArea();
2715        const float areaLarge = largeObj->GetBox().SurfaceArea();
2716
2717        return areaSmall / (areaLarge - areaSmall + Limits::Small);
2718}
2719
2720
2721bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const
2722{
2723        const bool terminationCriteriaMet =
2724                        (0
2725                    || ((int)tData.mNode->mObjects.size() < mInitialMinObjects)
2726                        || (tData.mNode->mObjects.back()->GetBox().SurfaceArea() < mInitialMinArea)
2727                        || (AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) > mInitialMaxAreaRatio)
2728                        );
2729
2730        cout << "criteria met: "<< terminationCriteriaMet << "\n"
2731                 << "size: " << (int)tData.mNode->mObjects.size() << " max: " << mInitialMinObjects << endl
2732                 << "ratio: " << AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) << " max: " << mInitialMaxAreaRatio << endl
2733                 << "area: " << tData.mNode->mObjects.back()->GetBox().SurfaceArea() << " max: " << mInitialMinArea << endl << endl;
2734
2735        return terminationCriteriaMet;
2736}
2737
2738
2739// HACK
2740float BvHierarchy::GetRenderCostIncrementially(BvhNode *node) const
2741{
2742        if (node->mRenderCost < 0)
2743        {
2744                //cout <<"p";
2745                if (node->IsLeaf())
2746                {
2747                        BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
2748                        node->mRenderCost = EvalAbsCost(leaf->mObjects);
2749                }
2750                else
2751                {
2752                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
2753               
2754                        node->mRenderCost = GetRenderCostIncrementially(interior->GetFront()) +
2755                                                                GetRenderCostIncrementially(interior->GetBack());
2756                }
2757        }
2758
2759        return node->mRenderCost;
2760}
2761
2762
2763void BvHierarchy::Compress()
2764{
2765}
2766
2767
2768}
Note: See TracBrowser for help on using the repository browser.