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

Revision 1272, 39.9 KB checked in by bittner, 18 years ago (diff)

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