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

Revision 1259, 40.2 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "BvHierarchy.h"
6#include "ViewCell.h"
7#include "Plane3.h"
8#include "Mesh.h"
9#include "common.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellsManager.h"
17#include "Beam.h"
18#include "VspTree.h"
19
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#ifdef _DEBUG
503        Debug << "BSP stats: "
504                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
505                  << "Prob: " << data.mProbability << " (min: " << mTermMinProbability << ")\n";
506#endif
507}
508
509
510float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
511                                                                                   const int axis,
512                                                                                   ObjectContainer &objectsFront,
513                                                                                   ObjectContainer &objectsBack)
514{
515        // the relative cost ratio
516        float ratio = 99999999.0f;
517
518        // go through the lists, count the number of objects left and right
519        // and evaluate the following cost funcion:
520        // C = ct_div_ci  + (ol + or)/queries
521       
522        const float minBox = tData.mBoundingBox.Min(axis);
523        const float maxBox = tData.mBoundingBox.Max(axis);
524
525        const float sizeBox = maxBox - minBox;
526
527        float minBand = minBox + mSplitBorder * (maxBox - minBox);
528        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
529
530        //-- sort so we can use a sweep
531        SortSubdivisionCandidates(tData, axis, minBand, maxBand);
532
533        int numViewCells;
534
535        float totalVol = PrepareHeuristics(tData);
536        float voll = 0;
537        float volr = totalVol;
538
539        /// this is kind of a reverse pvs
540        const int totalObjects = (int)tData.mNode->mObjects.size();
541       
542        int objectsl = 0;
543        int objectsr = totalObjects;
544
545        float sum = (float)totalVol * objectsr;
546
547
548        bool splitPlaneFound = false;
549
550        /////////////////////////////////
551        // the parameters for the current optimum
552
553        float volBack = voll;
554        float volFront = volr;
555
556        int nObjectsBack = objectsl;
557        int nObjectsFront = objectsr;
558       
559        float minSum = 1e20f;
560
561        /////////////////////////////
562
563        debugVol = 0;
564        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
565
566        /////////////////////////////
567        // the sweep heuristics
568
569        // mail the objects on the left side
570        Intersectable::NewMail();
571       
572        //-- traverse through events and find best split plane
573        vector<SortableEntry>::const_iterator ci, ci_end = mSubdivisionCandidates->end();
574
575        for (ci = mSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
576        {
577                Intersectable *object = (*ci).mObject;
578
579                EvalHeuristicsContribution(tData.mNode, *ci, voll, volr, objectsl);
580                objectsr = totalObjects - objectsl;
581
582                // Note: sufficient to compare size of bounding boxes of front and back side?
583
584                if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
585                {
586                        // voll = view cells that see only left node (i.e., left pvs)
587                        // volr = view cells that see only right node (i.e., right pvs)
588                        // rest = view cells that see both nodes (i.e., total pvs)
589            sum = voll * objectsl + volr * objectsr + (totalVol - voll - volr) * totalObjects;
590
591                        float currentPos;
592                       
593                        // HACK: current positition is BETWEEN visibility events
594                        if (1 && ((ci + 1) != ci_end))
595                                currentPos = ((*ci).mPos + (*(ci + 1)).mPos) * 0.5f;
596                        else
597                                currentPos = (*ci).mPos;                       
598
599                        if ((totalVol - voll - volr - debugVol) / viewSpaceVol > 0.0001)
600                                Debug << "front and back volume: " << (totalVol - voll - volr) / viewSpaceVol << " error: " << (totalVol - voll - volr - debugVol) / viewSpaceVol << endl;
601#if 0                           
602                        Debug << "pos: " << currentPos
603                                 << "\t (pvsl: " << pvsl << ", pvsr: " << pvsr << ")"
604                                 << "\t (voll: " << voll << ", volr: " << volr << ")"
605                                 << "\t (vcl: " << vcl << ", vcr: " << vcr << ", nvc: " << numViewCells << ")"
606                                 << "\t sum: " << sum << endl;
607                               
608#endif
609                        if (sum < minSum)
610                        {
611                                splitPlaneFound = true;
612
613                                minSum = sum;
614
615                                nObjectsBack = objectsl;
616                                nObjectsFront = objectsr;
617                               
618                                volBack = voll;
619                                volFront = volr;
620                        }
621                }
622        }
623       
624        //-- compute cost
625        const float frontAndBackVol = totalVol - volFront - volBack;
626
627        const float oldRenderCost = (float)totalObjects * totalVol + Limits::Small;
628        const float newRenderCost = (float)nObjectsFront * volFront +
629                                                                (float)nObjectsBack * volBack +
630                                                                (float)totalObjects * frontAndBackVol;
631
632        if (splitPlaneFound)
633        {
634                ratio = newRenderCost / oldRenderCost;
635        }
636
637        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos="
638        //        << position << " t=" << (position - minBox) / (maxBox - minBox)
639        //      << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
640
641        Debug << "\n§§§§ eval local cost §§§§" << endl
642                  << "back pvs: " << nObjectsBack << " front pvs: " << nObjectsFront << " total pvs: " << totalObjects << endl
643                  << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
644                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
645                  << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
646
647        if (oldRenderCost < newRenderCost)
648                Debug << "\nwarning!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
649
650        // assign objects
651        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
652
653        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
654        {
655                Intersectable *obj = *oit;
656
657                if (obj->Mailed()) // belongs to back objects
658                        objectsBack.push_back(obj);
659                else
660                        objectsFront.push_back(obj);
661        }
662
663        return ratio;
664}
665
666
667void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
668                                                                          const int axis,
669                                                                          float minBand,
670                                                                          float maxBand)
671
672{
673        mSubdivisionCandidates->clear();
674
675        //RayInfoContainer *rays = tData.mRays;
676        BvhLeaf *leaf = tData.mNode;
677
678        // compute requested size
679        int requestedSize = 0;
680        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
681        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
682                requestedSize += 2 + (int)(*oit)->mVssRays.size() * 2;
683       
684        // creates a sorted split candidates array
685        if (mSubdivisionCandidates->capacity() > 500000 &&
686                requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
687        {
688        delete mSubdivisionCandidates;
689                mSubdivisionCandidates = new vector<SortableEntry>;
690        }
691
692        mSubdivisionCandidates->reserve(requestedSize);
693
694        float pos;
695
696        //-- insert object queries
697        //-- These queries can induce a change in pvs size.
698        //-- Note that they cannot induce a change in view cell volume, as
699        //-- there is no ray associated with these events!!
700
701        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
702        {
703                Intersectable *obj = *oit;
704               
705                Intersectable *object = *oit;
706                const AxisAlignedBox3 box = object->GetBox();
707
708                mSubdivisionCandidates->push_back(
709                        SortableEntry(SortableEntry::OBJECT,
710                                                  box.Min(axis),
711                                                  object,
712                                                  NULL)
713                                                  );
714
715
716                //-- insert ray queries
717                //-- we are intersested only in rays which intersect an object that
718                //-- is part of the kd node because they can induce a change in view cell
719                //-- volume on the left and the right part.
720                //-- Note that they cannot induce a change in pvs size!!
721               
722                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
723
724                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
725                {
726                        VssRay *ray = (*rit);
727                        const bool positive = ray->HasPosDir(axis);
728       
729                        pos = ray->mTermination[axis];
730
731                        mSubdivisionCandidates->push_back(
732                                SortableEntry(SortableEntry::VIEWCELLS,
733                                pos,
734                                ray->mTerminationObject,
735                                ray)
736                                );
737                }
738        }
739
740        stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
741}
742
743
744const BvhStatistics &BvHierarchy::GetStatistics() const
745{
746        return mBvhStats;
747}
748
749
750void BvHierarchy::EvalRayContribution(const VssRay &ray,
751                                                                          float &volLeft,
752                                                                          float &volRight)
753{
754        ViewCellContainer viewCells;
755        mVspTree->GetViewCells(ray, viewCells);
756
757        /// classify view cells and compute volume contri accordingly
758        /// possible view cell classifications:
759        /// view cell mailed => view cell can be seen from left child node
760        /// view cell counter > 0 view cell can be seen from right child node
761        /// combined: view cell volume belongs to both nodes
762        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
763       
764        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
765        {
766                // view cells can also be seen from left child node
767                ViewCell *viewCell = *vit;
768
769                const float vol = viewCell->GetVolume();
770
771                if (!viewCell->Mailed())
772                {
773                        viewCell->Mail();
774
775                        // we now see view cell from both nodes
776                        // => remove ref to right child node
777                        volRight -= vol;
778                        debugVol += vol;
779                }
780
781                // last reference into the right node
782                if (-- viewCell->mCounter == 0)
783                {
784                        // view cell was previously seen from both nodes  =>
785                        // contributes only to left node now
786                        volLeft += vol;
787                        debugVol -= vol;
788                }
789        }
790}
791
792
793float BvHierarchy::PrepareHeuristics(const VssRay &ray)
794{
795        float vol = 0;
796
797        ViewCellContainer viewCells;
798        mVspTree->GetViewCells(ray, viewCells);
799       
800        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
801
802        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
803        {
804                ViewCell *vc = (*vit);
805
806                if (!vc->Mailed())
807                {
808                        //Debug << "single vol: "<< vc->GetVolume() << endl;
809                        vc->Mail();
810                        vc->mCounter = 0;
811                        vol += vc->GetVolume();
812                }
813               
814                // view cell volume already added => just increase counter
815                ++ vc->mCounter;
816        }
817
818        return vol;
819}
820
821
822float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData)
823{       
824        float vol = 0;
825        debugVol = 0;
826       
827        ViewCell::NewMail();
828
829        BvhLeaf *leaf = tData.mNode;
830
831        VssRayContainer rays;
832        CollectRays(leaf->mObjects, rays);
833
834        VssRayContainer::const_iterator rit, rit_end = rays.end();
835
836        for (rit = rays.begin(); rit < rit_end; ++ rit)
837        {
838                VssRay *ray = (*rit);
839
840                const float volContri = PrepareHeuristics(*ray);
841
842                // if hitpoint with one of the objects is inside this node, we
843                // evaluate the volume of the view cells seen by this ray
844                if (ray->mTerminationObject)
845                {
846            vol += volContri;
847                }
848
849                // count double if both hit points are within the kd node
850                if (0 && ray->mOriginObject)
851                {
852                        vol += volContri;
853                }
854        }
855
856        return vol;
857}
858///////////////////////////////////////////////////////////
859
860
861void BvHierarchy::EvalHeuristicsContribution(BvhLeaf *leaf,
862                                                                                         const SortableEntry &ci,
863                                                                                         float &volLeft,
864                                                                                         float &volRight,
865                                                                                         int &objectsLeft)
866{
867        Intersectable *obj = ci.mObject;
868        VssRay *ray = ci.mRay;
869
870        // switch between different types of events
871        switch (ci.mType)
872        {
873                case SortableEntry::OBJECT:
874                        cout << "o";
875                        ci.mObject->Mail();
876                        ++ objectsLeft;
877                        break;
878
879                // compute volume contribution from view cells
880                case SortableEntry::VIEWCELLS:
881                        cout << "v";
882                        // process ray if the hit point with termination / origin object
883                        // is inside this kd leaf
884                        EvalRayContribution(*ray, volLeft, volRight);
885                        break;
886
887                default:
888                        cout << "should not come here" << endl;
889                        break;
890        }
891        //cout << "vol left: " << volLeft << " vol right " << volRight << endl;
892}
893
894
895void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
896{
897        mViewCellsManager = vcm;
898}
899
900
901AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
902{
903        return mBoundingBox;
904}
905
906
907float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
908                                                                                 ObjectContainer &frontObjects,
909                                                                                 ObjectContainer &backObjects)
910{
911        ObjectContainer nFrontObjects[3];
912        ObjectContainer nBackObjects[3];
913
914        float nCostRatio[3];
915
916        // create bounding box of node geometry
917        AxisAlignedBox3 box = tData.mBoundingBox;
918               
919        int sAxis = 0;
920        int bestAxis = -1;
921
922        if (mOnlyDrivingAxis)
923        {
924                sAxis = box.Size().DrivingAxis();
925        }
926       
927        // -- evaluate split cost for all three axis
928       
929        for (int axis = 0; axis < 3; ++ axis)
930        {
931                if (!mOnlyDrivingAxis || (axis == sAxis))
932                {
933                        if (1 || mUseCostHeuristics)
934                        {
935                                //-- partition objects using heuristics
936                               
937                                nCostRatio[axis] =
938                                        EvalLocalCostHeuristics(
939                                                                                        tData,
940                                                                                        axis,
941                                                                                        nFrontObjects[axis],
942                                                                                        nBackObjects[axis]);                   
943                        }
944                        if (bestAxis == -1)
945                        {
946                                bestAxis = axis;
947                        }
948                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
949                        {
950                                bestAxis = axis;
951                        }
952                }
953        }
954
955        //-- assign values
956       
957        frontObjects = nFrontObjects[bestAxis];
958        backObjects = nFrontObjects[bestAxis];
959
960        Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
961        return nCostRatio[bestAxis];
962}
963
964
965void BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays)
966{
967
968        VssRayContainer::const_iterator rit, rit_end = rays.end();
969
970    for (rit = rays.begin(); rit != rays.end(); ++ rit)
971        {
972                VssRay *ray = (*rit);
973
974                if (ray->mTerminationObject)
975                {
976                        ray->mTerminationObject->mVssRays.push_back(ray);
977                }
978
979                if (0 && ray->mOriginObject)
980                {
981                        ray->mOriginObject->mVssRays.push_back(ray);
982                }
983        }
984}
985
986
987void BvHierarchy::EvalSubdivisionStats(const SubdivisionCandidate &sc)
988{
989        const float costDecr = sc.GetRenderCostDecrease();
990
991        AddSubdivisionStats(mBvhStats.Leaves(),
992                                                costDecr,
993                                                mTotalCost
994                                                );
995}
996
997
998void BvHierarchy::AddSubdivisionStats(const int leaves,
999                                                                          const float renderCostDecr,
1000                                                                          const float totalRenderCost)
1001{
1002        mSubdivisionStats
1003                        << "#Leaves\n" << leaves << endl
1004                        << "#RenderCostDecrease\n" << renderCostDecr << endl
1005                        << "#TotalRenderCost\n" << totalRenderCost << endl;
1006                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
1007}
1008
1009
1010void BvHierarchy::CollectRays(const ObjectContainer &objects,
1011                                                          VssRayContainer &rays) const
1012{
1013        VssRay::NewMail();
1014       
1015        ObjectContainer::const_iterator oit, oit_end = objects.end();
1016
1017        // evaluate reverse pvs and view cell volume on left and right cell
1018        // note: should I take all leaf objects or rather the objects hit by rays?
1019        for (oit = objects.begin(); oit != oit_end; ++ oit)
1020        {
1021                Intersectable *obj = *oit;
1022               
1023                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
1024
1025                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
1026                {
1027                        VssRay *ray = (*rit);
1028
1029                        if (!ray->Mailed())
1030                        {
1031                                ray->Mail();
1032                                rays.push_back(ray);
1033                        }
1034                }
1035        }
1036}
1037
1038
1039void BvHierarchy::MailViewCells(const ObjectContainer &objects,
1040                                                                const bool isFront,
1041                                                                ViewCellContainer &collectedViewCells) const
1042{
1043        VssRayContainer rays;
1044        CollectRays(objects, rays);
1045       
1046        VssRayContainer::const_iterator rit, rit_end = rays.end();
1047
1048        for (rit = rays.begin(); rit < rit_end; ++ rit)
1049        {
1050                VssRay *ray = (*rit);
1051
1052                // view cell is assigned to left and / or right child
1053                ViewCellContainer viewCells;
1054                mVspTree->GetViewCells(*ray, viewCells);
1055                       
1056                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1057
1058                // mail view cell
1059                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1060                {
1061                        ViewCell *vc = *vit;
1062
1063                        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1064                                collectedViewCells.push_back(vc);
1065
1066                        if (isFront)
1067                        {
1068                                if (!vc->Mailed())
1069                                        vc->Mail();
1070                        }
1071                        else
1072                        {
1073                                if (!vc->Mailed())
1074                                        vc->Mail(1);
1075                                else
1076                                        vc->Mail(2);
1077                        }
1078                }                               
1079        }
1080}
1081
1082
1083float BvHierarchy::EvalRenderCostDecrease(const ObjectContainer &objectsFront,
1084                                                                                  const ObjectContainer &objectsBack,
1085                                                                                  const BvhTraversalData &tData,
1086                                                                                  float &normalizedOldRenderCost) const
1087{
1088        // probability that view point lies in back / front node
1089        float pOverall = 0;
1090        float pFront = 0;
1091        float pBack = 0;
1092        float pFrontAndBack = 0;
1093
1094        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
1095
1096        BvhLeaf *leaf = tData.mNode;
1097       
1098        // sum up volume seen from the objects of left and right children
1099        // => the volume is the weight for the render cost equation
1100        ViewCell::NewMail(3);
1101
1102        ViewCellContainer collectedViewCells;
1103        MailViewCells(objectsFront, true, collectedViewCells);
1104        MailViewCells(objectsBack, false, collectedViewCells);
1105
1106        ViewCellContainer::const_iterator vit, vit_end = collectedViewCells.end();
1107
1108        // evaluate view cells volume contribution with respect to the mail id
1109        for (vit = collectedViewCells.begin(); vit != vit_end; ++ vit)
1110        {
1111                AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
1112        }
1113
1114        const int totalObjects = (int)leaf->mObjects.size();
1115        const int nObjectsFront = (int)objectsFront.size();
1116        const int nObjectsBack = (int)objectsBack.size();
1117
1118        // these are non-overlapping sets
1119        pOverall = pFront + pBack + pFrontAndBack;
1120
1121        //-- pvs rendering heuristics
1122        const float oldRenderCost = pOverall * totalObjects;
1123        const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack + totalObjects * pFrontAndBack;
1124
1125        // normalize volume with view space volume
1126        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1127
1128        Debug << "\n(((( eval render cost decrease ))))" << endl
1129                  << "back objects: " << nObjectsBack << " front objects " << nObjectsFront << " total objects: " << totalObjects << endl
1130                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
1131                  << " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1132                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
1133                  << "render cost decrease: " << renderCostDecrease << endl;
1134
1135        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1136
1137        if (oldRenderCost < newRenderCost * 0.99)
1138                Debug << "\nwarning2!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
1139       
1140        return renderCostDecrease;
1141}
1142
1143
1144AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects)
1145{
1146        AxisAlignedBox3 box;
1147        box.Initialize();
1148
1149        ObjectContainer::const_iterator oit, oit_end = objects.end();
1150
1151        //-- compute bounding box
1152        for (oit = objects.begin(); oit != oit_end; ++ oit)
1153        {
1154                Intersectable *obj = *oit;
1155
1156                // compute bounding box of view space
1157                mBoundingBox.Include(obj->GetBox());
1158        }
1159        return box;
1160       
1161}
1162
1163
1164void BvHierarchy::CollectLeaves(vector<BvhLeaf *> &leaves) const
1165{
1166        stack<BvhNode *> nodeStack;
1167        nodeStack.push(mRoot);
1168
1169        while (!nodeStack.empty())
1170        {
1171                BvhNode *node = nodeStack.top();
1172                nodeStack.pop();
1173                if (node->IsLeaf())
1174                {
1175                        BvhLeaf *leaf = (BvhLeaf *)node;
1176                        leaves.push_back(leaf);
1177                }
1178                else
1179                {
1180                        BvhInterior *interior = (BvhInterior *)node;
1181
1182                        nodeStack.push(interior->GetBack());
1183                        nodeStack.push(interior->GetFront());
1184                }
1185        }
1186}
1187
1188
1189AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1190{
1191        return node->GetBoundingBox();
1192}
1193
1194
1195void BvHierarchy::CollectViewCells(BvhLeaf *leaf, ViewCellContainer &viewCells)
1196{
1197        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1198
1199        ViewCell::NewMail();
1200
1201        // loop through all object and collect view cell pvs of this node
1202        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1203        {
1204                Intersectable *obj = *oit;
1205
1206                ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
1207
1208                for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
1209                {
1210            ViewCell *vc = (*vit).first;
1211
1212                        if (!vc->Mailed())
1213                        {
1214                                vc->Mail();
1215                                viewCells.push_back(vc);
1216                        }
1217                }
1218        }
1219}
1220
1221
1222void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1223                                                                                 vector<SubdivisionCandidate *> &dirtyList)
1224{
1225        BvhTraversalData &tData = sc->mParentData;
1226        BvhLeaf *node = tData.mNode;
1227       
1228        ViewCell::NewMail();
1229
1230        ViewCellContainer viewCells;
1231        ViewCellContainer tmpViewCells;
1232
1233        VssRayContainer rays;
1234        CollectRays(node->mObjects, rays);
1235
1236        VssRayContainer::const_iterator rit, rit_end = rays.end();
1237
1238        // find all view cells associated with the rays, add them to view cells
1239        for (rit = rays.begin(); rit != rit_end; ++ rit)
1240        {
1241                VssRay *ray = (*rit);
1242                mVspTree->GetViewCells(*ray, tmpViewCells);
1243
1244                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1245
1246                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1247                {
1248                        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1249
1250                        if (!vc->Mailed())
1251                        {
1252                                vc->Mail();
1253                                viewCells.push_back(vc);
1254                        }
1255                }
1256        }
1257
1258
1259        // split candidates holding this view cells
1260        // are thrown into dirty list
1261        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1262
1263        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1264        {
1265                VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1266
1267                VspLeaf *leaf = vc->mLeaf;
1268                dirtyList.push_back(leaf->GetSubdivisionCandidate());
1269        }
1270}
1271
1272
1273BvhNode *BvHierarchy::GetRoot() const
1274{
1275        return mRoot;
1276}
1277
1278
1279bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
1280{
1281        ObjectContainer::const_iterator oit =
1282                lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1283                               
1284        // objects sorted by id
1285        if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1286        {
1287                return true;
1288        }
1289        else
1290        {
1291                return false;
1292        }
1293}
1294
1295
1296BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
1297{
1298        // rather use the simple version
1299        return object->mBvhLeaf;
1300
1301        ///////////////////////////////////////
1302        // start from root of tree
1303        if (node == NULL)
1304        {
1305                node = mRoot;
1306        }
1307
1308        vector<BvhLeaf *> leaves;
1309
1310        stack<BvhNode *> nodeStack;
1311        nodeStack.push(node);
1312 
1313        BvhLeaf *leaf = NULL;
1314 
1315        while (!nodeStack.empty()) 
1316        {
1317                BvhNode *node = nodeStack.top();
1318                nodeStack.pop();
1319       
1320                if (node->IsLeaf())
1321                {
1322                        leaf = dynamic_cast<BvhLeaf *>(node);
1323
1324                        if (IsObjectInLeaf(leaf, object))
1325                                return leaf;
1326                }
1327                else   
1328                {       
1329                        // find point
1330                        BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1331       
1332                        if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
1333                        {
1334                                nodeStack.push(interior->GetBack());
1335                        }
1336                       
1337                        // search both sides as we are using bounding volumes
1338                        if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
1339                        {
1340                                nodeStack.push(interior->GetFront());
1341                        }
1342                }
1343        }
1344 
1345        return leaf;
1346}
1347
1348
1349BvhIntersectable *BvHierarchy::GetOrCreateBvhIntersectable(BvhNode *node)
1350{
1351        // search nodes
1352        std::map<BvhNode *, BvhIntersectable *>::
1353                const_iterator it = mBvhIntersectables.find(node);
1354
1355        if (it != mBvhIntersectables.end())
1356        {
1357                return (*it).second;
1358        }
1359
1360        // not in map => create new entry
1361        BvhIntersectable *bvhObj = new BvhIntersectable(node);
1362        mBvhIntersectables[node] = bvhObj;
1363
1364        return bvhObj;
1365}
1366
1367
1368void BvHierarchy::AddViewCellVolumeContri(ViewCell *vc,
1369                                                                                  float &frontVol,
1370                                                                                  float &backVol,
1371                                                                                  float &frontAndBackVol) const
1372{
1373        if (vc->Mailed())
1374        {
1375                frontVol += vc->GetVolume();
1376        }
1377        else if (vc->Mailed(1))
1378        {
1379                backVol += vc->GetVolume();
1380        }
1381        else if (vc->Mailed(2))
1382        {
1383                frontAndBackVol += vc->GetVolume();
1384        }
1385}
1386
1387/*
1388int BvHierarchy::UpdateViewCellsPvs(BvhLeaf *leaf,
1389                                                                const RayInfoContainer &rays) const
1390
1391{
1392        MailablePvsData::NewMail();
1393       
1394        ViewCellContainer touchedViewCells;
1395        CollectTouchedViewCells(rays, touchedViewCells);
1396
1397        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1398
1399        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
1400        {
1401                Intersectable *obj = *oit;
1402                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1403
1404                // traverse through view cells and classify them according
1405                // to them being seen from to back / front / front and back node
1406                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1407                {
1408                        ViewCell *vc = *vit;
1409                        float contri;
1410                        AddViewCellToObjectPvs(obj, vc, contri, true);
1411                }
1412        }
1413
1414        return 0;
1415}
1416
1417
1418int BvHierarchy::RemoveParentViewCellsPvs(BvhLeaf *leaf,
1419                                                                          const RayInfoContainer &rays
1420                                                                          ) const
1421
1422{
1423        MailablePvsData::NewMail();
1424       
1425        ViewCellContainer touchedViewCells;
1426        CollectTouchedViewCells(rays, touchedViewCells);
1427
1428        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1429
1430        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1431        {
1432                Intersectable *obj = *oit;
1433
1434                // traverse through view cells and classify them according
1435                // to them being seen from to back / front / front and back node
1436        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1437
1438                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1439                {
1440                        ViewCell *vc = *vit;
1441                       
1442                        MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
1443
1444                        if (vdata && !vdata->Mailed())
1445                        {
1446                                vdata->Mail();
1447                                obj->mViewCellPvs.RemoveSample(vc, 1);
1448                        }
1449                }
1450        }
1451
1452        return 0;
1453}
1454*/
1455
1456bool BvHierarchy::Export(OUT_STREAM &stream)
1457{
1458        ExportNode(mRoot, stream);
1459
1460        return true;
1461}
1462
1463
1464void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
1465{
1466        if (node->IsLeaf())
1467        {
1468                BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
1469
1470                stream << "<Leaf ";
1471                stream << "objects=\"";
1472               
1473                //-- export objects in kd leaves
1474                //if (mExportObjects) ExportObjects(leaf, stream);
1475               
1476                stream << "\" />" << endl;
1477                //stream << " </Leaf>" << endl;
1478        }
1479        else
1480        {       
1481                BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
1482       
1483                stream << "<Interior box=\"" << interior->GetBoundingBox() << "\">" << endl;
1484
1485                ExportNode(interior->GetBack(), stream);
1486                ExportNode(interior->GetFront(), stream);
1487
1488                stream << "</Interior>" << endl;
1489        }
1490}
1491
1492
1493float BvHierarchy::EvalViewCellsVolume(BvhLeaf *leaf) const
1494{
1495        float vol = 0;
1496
1497        VssRayContainer rays;
1498        CollectRays(leaf->mObjects, rays);
1499
1500        ViewCell::NewMail();
1501
1502        VssRayContainer::const_iterator rit, rit_end = rays.end();
1503
1504        for (rit = rays.begin(); rit < rit_end; ++ rit)
1505        {
1506                VssRay *ray = (*rit);
1507       
1508                ViewCellContainer viewCells;
1509                mVspTree->GetViewCells(*ray, viewCells);
1510       
1511                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1512
1513                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1514                {
1515                        ViewCell *vc = (*vit);
1516
1517                        if (!vc->Mailed())
1518                        {
1519                                //Debug << "single vol: "<< vc->GetVolume() << endl;
1520                                vc->Mail();
1521                                vol += vc->GetVolume();
1522                        }
1523                }
1524        }
1525
1526        return vol;
1527}
1528
1529
1530SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
1531                                                                                                           ObjectContainer &objects,
1532                                                                                                           AxisAlignedBox3 *forcedObjectSpace
1533                                                                                                           //, RayInfoContainer &rays
1534                                                                                                           )
1535{
1536        // store pointer to this tree
1537        BvhSubdivisionCandidate::sBvHierarchy = this;
1538        mBvhStats.nodes = 1;
1539
1540        // compute bounding box from objects
1541        if (forcedObjectSpace)
1542                mBoundingBox = *forcedObjectSpace;
1543        else
1544                mBoundingBox = ComputeBoundingBox(objects);
1545
1546        mTermMinVolume *= mBoundingBox.GetVolume();
1547        mGlobalCostMisses = 0;
1548
1549        // sort objects by id in order to have sorted objects in
1550        // the leaf nodes
1551        stable_sort(objects.begin(), objects.end(), ilt);
1552
1553        //-- create new root
1554
1555        BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
1556        bvhleaf->mObjects = objects;
1557        mRoot = bvhleaf;
1558
1559        // only rays intersecting objects in node are interesting
1560        AssociateObjectsWithRays(sampleRays);
1561        // associate root with current objects
1562        AssociateObjectsWithLeaf(bvhleaf);
1563
1564        //-- add first candidate for object space partition
1565
1566        // create osp traversal data
1567        BvhTraversalData oData(bvhleaf, 0, mBoundingBox.GetVolume());
1568
1569        //-- first split candidate
1570        BvhSubdivisionCandidate *oSubdivisionCandidate =
1571                new BvhSubdivisionCandidate(oData);
1572
1573        //UpdateViewCellsPvs(kdleaf, rays);
1574
1575        EvalSubdivisionCandidate(*oSubdivisionCandidate);
1576
1577// probabilty is voume of all "seen" view cells
1578#if 1
1579        const float prop = EvalViewCellsVolume(bvhleaf);
1580#else
1581        const float prop = GetBoundingBox().GetVolume();
1582#endif
1583        mTotalCost = (float)objects.size() * prop /
1584                mVspTree->GetBoundingBox().GetVolume();
1585
1586        EvalSubdivisionStats(*oSubdivisionCandidate);
1587
1588        return oSubdivisionCandidate;
1589}
1590
1591
1592bool BvHierarchy::AddLeafToPvs(BvhLeaf *leaf,
1593                                                           ViewCell *vc,
1594                                                           const float pdf,
1595                                                           float &contribution)
1596{
1597        // add kd intersecable to pvs
1598        BvhIntersectable *bvhObj = GetOrCreateBvhIntersectable(leaf);
1599       
1600        return vc->AddPvsSample(bvhObj, pdf, contribution);
1601}
1602
1603
1604}
Note: See TracBrowser for help on using the repository browser.