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

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