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

Revision 1314, 38.1 KB checked in by mattausch, 18 years ago (diff)

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