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

Revision 1345, 42.2 KB checked in by mattausch, 18 years ago (diff)

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