source: GTP/trunk/App/Demos/Vis/CHC_revisited/Bvh.cpp @ 2746

Revision 2746, 59.8 KB checked in by mattausch, 17 years ago (diff)
Line 
1#if TOIMPLEMENT
2
3#include <queue>
4#include <stack>
5#include "Bvh.h"
6#include "yare.h"
7#include "PerfTimer.h"
8#include "Camera.h"
9#include "Settings.h"
10#include "Context.h"
11#include "TriangleBvh.h"
12#include "NodeGeometry.h"
13#include "Viewer.h"
14
15
16#include <fstream>
17#include <iostream>
18#include <iomanip>
19
20#define INVALID_TEST ((unsigned int)-1)
21#define MAX_FLOAT 1e20f
22
23#define TYPE_INTERIOR -2
24#define TYPE_LEAF -3
25#define USE_TIGHTER_BOUNDS_FOR_ALL 0
26
27const static bool useVbos = true;
28unsigned int Bvh::sCurrentVboId = -1;
29
30using namespace std;
31
32
33
34/*
353 x---------x 2
36  |\         \
37  | \         \
38  |  \         \
39  |     4 x---------x 5
40  |   |         |
410 x   |     x 1 |
42   \  |         |
43    \ |         |
44     \|         |
45        7 x---------x 6             
46*/
47
48static unsigned int sIndices[] =       
49{7, // degenerated
50 7, 6, 4, 5, 3, 2, 0, 1,
51 1, 4, // degenerated
52 4, 3, 7, 0, 6, 1, 5, 2,
53 2 // degenerated
54};
55
56
57const static int sNumIndicesPerBox = 20;
58
59/*      Order of vertices
60        0 = (0, 0, 0)
61        1 = (1, 0, 0)
62        2 = (1, 1, 0)
63        3 = (0, 1, 0)
64        4 = (0, 1, 1)
65        5 = (1, 1, 1)
66        6 = (1, 0, 1)
67        7 = (0, 0, 1)
68*/
69
70
71BvhNode::BvhNode(BvhNode *parent):
72mParent(parent),
73mAxis(-1),
74mDepth(0),
75mPlaneMask(0),
76mPreferredPlane(0),
77mVizBox(NULL),
78mLastRenderedFrame(-999),
79mFirst(-1),
80mLast(-1),
81mNumTestNodes(1),
82mTestNodesIdx(-1),
83mIndicesPtr(-1)
84{
85}
86
87
88void BvhNode::ResetVisibility()
89{
90        mVisibility.Reset();
91        mMeasurements.Reset();
92
93        mLastRenderedFrame = -999;
94}
95
96
97BvhNode::~BvhNode()
98{
99        if (mVizBox) mVizBox->unref();
100}
101
102
103Box *BvhNode::GetOrCreateVizBox()
104{
105        if (!mVizBox)
106        {
107                mVizBox = new Box(mBox);
108                mVizBox->ref();
109        }
110
111        return mVizBox;
112}
113
114
115void BvhNode::VisibilityInfo::Reset()
116{
117        mIsVisible = false;
118        mIsFullyVisible = false;
119
120        mVisiblePixels = 0;
121        mAssumedVisibleFrames = 0;
122        mRemainingVisibleFrames = 0;
123
124        mLastVisitedFrame = -1;
125        mLastTestedFrame = -1;
126        mTurnedVisibleFrame = 0;
127
128        mTimesInvisible = 0;
129        mTimesTested = 0;
130        mTimesChangedClassification = 0;
131        mAvgChangedClassification = 0;
132        mIsFrustumCulled = false;
133
134        mLastTestedVisibleFrame = 0;
135        mIsNew = true;
136}
137
138
139void BvhNode::SetFullyVisible(const bool visible)
140{
141        mVisibility.mIsFullyVisible = visible;
142}
143
144
145BvhLeaf::~BvhLeaf()
146{
147        if (mTriangleBvh) delete mTriangleBvh;
148}
149
150
151/***********************************************************/
152/*                class Bvh implementation                 */
153/***********************************************************/
154
155
156
157Bvh::Bvh(const GeometryVector &geometry,
158                 DistanceSortedRenderAction *const renderer):
159mCamera(NULL),
160mFrameId(-1),
161mRoot(NULL),
162mVertices(NULL),
163mIndices(NULL),
164mUseTighterBoundsOnlyForLeafTests(false),
165mRenderer(renderer),
166mTestIndices(NULL),
167mCurrentIndicesPtr(0),
168mCollectTighterBoundsWithMaxLevel(true)
169{
170        mGeometry = new NodeGeometry*[geometry.size()];
171        mGeometrySize = geometry.size();
172
173        BoundingBox sceneBox;
174
175        // compute scene extent
176        for (size_t i = 0; i < mGeometrySize; ++ i)
177        {
178                mGeometry[i] = geometry[i];
179                sceneBox.combine(&mGeometry[i]->mBox);
180
181                mBvhStats.mTriangles += mGeometry[i]->mNumTriangles;
182        }
183
184
185        ////////
186        //-- create root
187
188        BvhLeaf *leaf = new BvhLeaf(NULL);
189        leaf->mDepth = 0;
190        leaf->mFirst = 0;
191        leaf->mLast = (int)geometry.size() - 1;
192        leaf->mBox = sceneBox;
193
194        OUT1("geometry in root: " << leaf->mLast);
195
196        mRoot = leaf;
197        mNumNodes = 1;
198
199        // parameters
200        mMaxGeometry = Settings::Global()->get_nvocc_bvh_max_objects();
201        mMaxTriangles = Settings::Global()->get_nvocc_bvh_max_triangles();
202        mMaxDepth = Settings::Global()->get_nvocc_bvh_max_depth();
203        mSplitType = Settings::Global()->get_nvocc_bvh_split_type();
204
205        float sceneArea = sceneBox.getSurface();
206        float minAreaRatio = Settings::Global()->get_nvocc_bvh_min_area();
207
208        mMinArea = minAreaRatio * sceneArea;
209
210        mMaxDepthForTestingChildren = Settings::Global()->get_nvocc_bvh_max_depth_for_testing_children();
211        mUseTighterBoundsOnlyForLeafTests = (Settings::Global()->get_nvocc_use_tighter_bounds() >= 1);
212       
213        mAreaRatioThreshold = Settings::Global()->get_nvocc_area_ratio_threshold();
214        mVolRatioThreshold = Settings::Global()->get_nvocc_vol_ratio_threshold();
215}
216
217
218Bvh::~Bvh()
219{
220        if (mVertices) delete []mVertices;
221        if (mIndices) delete [] mIndices;
222        if (mTestIndices) delete [] mTestIndices;
223        if (mGeometry) delete [] mGeometry;
224
225        if (mRoot) delete mRoot;
226}
227
228
229void Bvh::Construct()
230{
231        PerfTimer constructTimer;
232        constructTimer.Entry();
233
234        OUT1("Info: Constructing BVH");
235
236        mRoot = SubdivideLeaf((BvhLeaf *)mRoot, 0);
237
238        constructTimer.Exit();
239
240        OUT1("Info: Bvh done in " << constructTimer.TotalCount() << " seconds.");
241        OUT1("Info: Number Of BVH Nodes = " << mNumNodes);
242
243        // update stats on leaf nodes
244        UpdateNumLeaves(mRoot);
245       
246        mAvgDepth = 1.0f + log((float)GetNumLeaves()) / log(2.0f);
247
248        BvhLeafContainer leaves;
249        leaves.reserve(GetNumLeaves());
250        CollectLeaves(mRoot, leaves);
251
252        // compute tighter boundaries for the leaves
253        PostProcessLeaves(leaves);
254        // compute unique ids
255        ComputeIds();
256        /// pull up some data from the leaves
257        UpdateInteriors(mRoot);
258        // recompute the boundaries once
259        RecomputeBounds();
260        // do stats
261        ComputeBvhStats();
262
263        PrintBvhStats();
264}
265
266
267float Bvh::EvaluateSahCost(BvhLeaf *leaf, const int axis, const float position)
268{
269        // count triangles on the left / right
270        int left = 0;
271        int right = 0;
272        BoundingBox leftBox, rightBox;
273
274        const int candidates = std::max(50, (int)(leaf->CountPrimitives() / 20));
275
276        const float finc = leaf->CountPrimitives() / (float)candidates;
277
278        int i = leaf->mFirst;
279        float fi = leaf->mFirst + 0.5f;
280
281        BoundingBox box;
282
283        for (; i <= leaf->mLast;)
284        {
285                box = mGeometry[i]->GetBoundingBox();
286
287                if (box.getCenter()[axis] < position)
288                {
289                        ++ left;
290                        // update the box
291                        leftBox.combine(&box);
292                }
293                else
294                {
295                        ++ right;
296                        rightBox.combine(&box);
297                }
298                 
299                fi += finc;
300                i = (int)fi;
301        }
302
303        float bW = 1.0f;
304        float leftRatio = left / (float)leaf->CountPrimitives();
305        float rightRatio = right / (float)leaf->CountPrimitives();
306
307        float saLeft = 0.0f;
308        float saRight = 0.0f;
309
310        // not a valid split
311        if (!left || !right)
312                return 1e25f;
313
314        saLeft = leftBox.getSurface();
315        saRight = rightBox.getSurface();
316
317
318        return
319                saLeft  * ((1.0f - bW) + bW * leftRatio) +
320                saRight * ((1.0f - bW) + bW * rightRatio);
321}
322
323
324float Bvh::SelectPlaneSah(BvhLeaf *leaf, int &axis, float &minCost)
325{
326        minCost = MAX_FLOAT;
327        float bestPos = minCost;
328        int bestAxis = 0;
329
330        //  cout<<"Evaluating axis..."<<endl<<flush;
331
332        const int initialPlanes = 3;
333
334        // initiate the costs
335        for (axis = 0; axis < 3; ++ axis)
336        {
337                const float size = leaf->mBox.getUpper()[axis] - leaf->mBox.getLower()[axis];
338
339                for (int i = 0; i < initialPlanes; ++ i)
340                {
341                        const float pos = leaf->mBox.getLower()[axis] + (i + 1) * size / (initialPlanes + 1);
342                        const float cost = EvaluateSahCost(leaf, axis, pos);
343
344                        if (cost < minCost)
345                        {
346                                minCost = cost;
347                                bestPos = pos;
348                                bestAxis = axis;
349                        }
350                }
351        }
352
353        axis = bestAxis;
354
355        //  cout<<axis<<endl<<flush;
356        const float shrink = 0.5f;
357
358        // now hierarchically refine the initial interval
359        float size = shrink *
360                (leaf->mBox.getUpper()[axis] - leaf->mBox.getLower()[axis]) / (initialPlanes + 1);
361
362        const int steps = 4;
363        float cost;
364
365        for (int i = 0; i < steps; ++ i)
366        {
367                const float left = bestPos - size;
368                const float right = bestPos + size;
369
370                cost = EvaluateSahCost(leaf, axis, left);
371
372                if (cost < minCost)
373                {
374                        minCost = cost;
375                        bestPos = left;
376                }
377
378                cost = EvaluateSahCost(leaf, axis, right);
379
380                if (cost < minCost)
381                {
382                        minCost = cost;
383                        bestPos = right;
384                }
385
386                size = shrink * size;
387        }
388
389        //OUT1("best axis: " << axis << " " << bestPos << " " << minCost);
390
391        return bestPos;
392}
393
394
395void Bvh::ResizeVisibilityBuffers(const int maxSize)
396{
397        std::stack<BvhNode *> nodeStack;
398
399        nodeStack.push(mRoot);
400
401        while (!nodeStack.empty())
402        {
403                BvhNode *node = nodeStack.top();
404                nodeStack.pop();
405
406                static_cast<BvhLeaf *>(node)->mMeasurements.Reset();
407
408                if (!node->IsLeaf())
409                {
410                        BvhInterior *interior = static_cast<BvhInterior *>(node);
411                       
412                        nodeStack.push(interior->mBack);
413                        nodeStack.push(interior->mFront);
414                }
415        }
416}
417
418
419int Bvh::SortTriangles(BvhLeaf *leaf,
420                                           const int axis,
421                                           const float position)
422{
423        int i = leaf->mFirst;
424        int j = leaf->mLast;
425
426    while (1)
427        {
428                while (mGeometry[i]->GetBoundingBox().getCenter()[axis] < position)
429                        ++ i;
430       
431                while (position < mGeometry[j]->GetBoundingBox().getCenter()[axis])
432                        -- j;
433
434                if (i < j)
435                {
436                        std::swap(mGeometry[i], mGeometry[j]);
437                       
438                        ++ i;
439                        -- j;
440                }
441                else
442                {
443                        break;
444                }
445        }
446
447        return j;
448}
449
450
451int Bvh::SortTrianglesSpatialMedian(BvhLeaf *leaf, const int axis)
452{
453        // spatial median
454        float x = leaf->mBox.getCenter()[axis];
455
456        return SortTriangles(leaf, axis, x);
457}
458
459
460int Bvh::SortTrianglesObjectMedian(BvhLeaf *leaf, const int axis, float &pos)
461{
462        // Now distribute the objects into the subnodes
463        // Use QuickMedian sort
464        int l = leaf->mFirst;
465        int r = leaf->mLast;
466        int k = (l + r) / 2;
467
468        while (l < r)
469        {
470                int i = l;
471                int j = r;
472
473                // get some estimation of the pivot
474                pos = mGeometry[(l + r) / 2]->GetBoundingBox().getCenter()[axis];
475
476                while (1)
477                {
478                        while ((i  <= leaf->mLast) && (mGeometry[i]->GetBoundingBox().getCenter()[axis] < pos))
479                                ++ i;
480
481                        while((j >= leaf->mFirst) && (pos < mGeometry[j]->GetBoundingBox().getCenter()[axis]))
482                                -- j;
483
484                        if (i <= j)
485                        {
486                                std::swap(mGeometry[i], mGeometry[j]);
487                                ++ i;
488                                -- j;
489                        }
490                        else
491                        {
492                                break;
493                        }
494                }
495
496                // now check the extents
497                if (i >= k)
498                        r = j;
499                else
500                        l = i;
501        }
502
503        return k;
504}
505
506
507int Bvh::SortTrianglesSurfaceArea(BvhLeaf *leaf, const float sa)
508{
509        int i = leaf->mFirst;
510        int j = leaf->mLast;
511
512        while(1)
513        {
514                while ((i <= j) && (mGeometry[i]->GetBoundingBox().getSurface() < sa))
515                        ++ i;
516
517                while ((i <= j) && (sa < mGeometry[j]->GetBoundingBox().getSurface()))
518                        -- j;
519
520                if (i < j)
521                {
522                        swap(mGeometry[i], mGeometry[j]);
523                        ++ i;
524                        -- j;
525                }
526                else
527                        break;
528        }
529
530        return j;
531}
532
533
534bool Bvh::TerminationCriteriaMet(BvhLeaf *leaf) const
535{
536        const bool terminationCriteriaMet =
537                (leaf->mBox.getSurface() < mMinArea) ||
538                (leaf->CountPrimitives() <= mMaxGeometry) ||
539                (CountTriangles(leaf) <= mMaxTriangles) ||
540                (leaf->mDepth > mMaxDepth);
541
542        return terminationCriteriaMet;
543}
544
545
546BvhNode *Bvh::SubdivideLeaf(BvhLeaf *leaf, const int parentAxis)
547{
548        if (TerminationCriteriaMet(leaf))
549                return leaf;
550       
551        //int axis = leaf->mBox.MajorAxis();
552        int axis = (parentAxis + 1) % 3;
553
554        // position of the split in the partailly sorted array of triangles
555        // corresponding to this leaf
556        int split = -1;
557        const int scale = 20;
558
559        float pos = -1.0f;
560
561        // Spatial median subdivision
562        switch (mSplitType)
563        {
564        case SPATIAL_MEDIAN:
565                split = SortTrianglesSpatialMedian(leaf, axis);
566
567                if (
568                        ((split - leaf->mFirst) < leaf->CountPrimitives() / scale) ||
569                        ((leaf->mLast - split) < leaf->CountPrimitives() / scale) )
570                {
571                        split = SortTrianglesObjectMedian(leaf, axis, pos);
572                }
573
574                pos = leaf->mBox.getCenter()[axis];
575                break;
576        case OBJECT_MEDIAN:
577                // Object median subdivision: approximately the same number
578                // of objects on the left of the the splitting point.
579                split = SortTrianglesObjectMedian(leaf, axis, pos);
580                break;
581        case SAH:
582                {
583                        float cost;
584                        pos = SelectPlaneSah(leaf, axis, cost);
585
586                        if (pos != MAX_FLOAT)
587                        {
588                                split = SortTriangles(leaf, axis, pos);
589                        }
590
591                        if ((pos == MAX_FLOAT) || (split == leaf->mLast))
592                        {
593                                split = -1;
594                                split = SortTrianglesObjectMedian(leaf, axis, pos);
595                        }
596                }
597                break;
598        case SAH_OR_SIZE:
599                {
600                        // split by size instead
601                        const float saThreshold = 0.2f * leaf->GetBox().getSurface();
602                        split = SortTrianglesSurfaceArea(leaf, saThreshold);
603
604                        if ((split == leaf->mLast) || (split == leaf->mFirst - 1))
605                        {
606                                // use SAH
607                                float cost;
608                                pos = SelectPlaneSah(leaf, axis, cost);
609
610                                if (pos != MAX_FLOAT)
611                                        split = SortTriangles(leaf, axis, pos);
612                                else
613                                        split = SortTrianglesObjectMedian(leaf, axis, pos);
614                        }
615                        else
616                        {
617                                // note: no position is computed!!
618                                //OUT1("sorted by size");
619                        }
620                }
621                break;
622        default:
623                OUT1("should not come here");
624                break;
625        }
626
627        if (1 && ((split == leaf->mLast)))
628        {
629                // no reduction: we should never come here
630                OUT1("error: no reduction " << leaf->CountPrimitives() << " " << leaf->mFirst << " " << split << " " << leaf->mLast);
631                return leaf;
632        }
633
634        // create two more nodes
635        mNumNodes += 2;
636        BvhInterior *parent = new BvhInterior(leaf->GetParent());
637        BvhLeaf *front = new BvhLeaf(parent);
638       
639        parent->mAxis = axis;
640        parent->mBox = leaf->mBox;
641        parent->mDepth = leaf->mDepth;
642
643        parent->mBack = leaf;
644        parent->mFront = front;
645        parent->mPosition = pos;
646       
647        // now assign the triangles to the subnodes
648        front->mFirst = split + 1;
649        front->mLast = leaf->mLast;
650        front->mDepth = leaf->mDepth + 1;
651        leaf->mLast = split;
652        leaf->mDepth = front->mDepth;
653        leaf->mParent = parent;
654       
655        // reset box
656        leaf->mBox = BoundingBox();
657
658        UpdateLeafBox(static_cast<BvhLeaf *>(parent->mBack));
659        UpdateLeafBox(static_cast<BvhLeaf *>(parent->mFront));
660
661        // some output
662        const int n = 500;
663        if ((GetNumLeaves() % n) == n - 1)
664                OUT1("created " << GetNumLeaves() << " leaves");
665       
666#if VERBOSE_OUTPUT
667        OUT1("box: " << parent->mBox.getUpper() << " " << parent->mBox.getLower());
668        OUT1("depth: " << (int)parent->mDepth);
669        OUT1("axis: " << axis);
670        OUT1("bc="<<((BvhLeaf *)parent->mBack)->Count());
671        OUT1("fc="<<((BvhLeaf *)parent->mFront)->Count());
672        OUT1("back: " << parent->mBack->mBox.getSurface());
673        OUT1("front: " << parent->mFront->mBox.getSurface());
674#endif
675
676        // recursively continue subdivision
677        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis);
678        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis);
679
680        return parent;
681}
682
683
684void Bvh::UpdateLeafBox(BvhLeaf *leaf)
685{
686        for (int i = leaf->mFirst; i <= leaf->mLast; ++ i)
687        {
688                leaf->mBox.combine(&mGeometry[i]->mBox);
689        } // for
690}
691
692
693void Bvh::UpdateNumLeaves(BvhNode *node) const
694{
695        if (node->IsLeaf())
696        {
697                node->mNumLeaves = 1;
698        }
699        else
700        {
701                BvhNode *f = static_cast<BvhInterior *>(node)->GetFront();
702                BvhNode *b = static_cast<BvhInterior *>(node)->GetBack();
703
704                UpdateNumLeaves(f);
705                UpdateNumLeaves(b);
706
707                node->mNumLeaves = f->mNumLeaves + b->mNumLeaves;
708        }
709}
710
711
712void Bvh::UpdateBoxes(BvhNode *node)
713{
714        if (node->IsLeaf())
715        {
716                UpdateLeafBox(static_cast<BvhLeaf *>(node));
717        }
718        else
719        {
720                BvhInterior *interior = static_cast<BvhInterior *>(node);
721       
722                UpdateBoxes(interior->mBack);
723                UpdateBoxes(interior->mFront);
724
725                node->mBox = interior->mBack->mBox;
726                node->mBox.combine(&interior->mFront->mBox);
727        }
728}
729
730
731void Bvh::UpdateFullVisibility(BvhNode *node) const
732{               
733        // node not visited in this frame => no change
734        if (node->GetLastVisitedFrame() != mFrameId)
735                return;
736
737        // leaf node: terminate recursion
738        if (node->IsLeaf())
739        {
740                node->SetFullyVisible(node->IsVisible());       
741                return;
742        }
743
744        BvhInterior *interior = static_cast<BvhInterior *>(node);
745       
746        // recursive traversal
747        UpdateFullVisibility(interior->mBack);
748        UpdateFullVisibility(interior->mFront);
749       
750        interior->SetFullyVisible(interior->mBack->IsFullyVisible() &&
751                                                          interior->mFront->IsFullyVisible());
752}
753
754
755void Bvh::PullUpLastVisited(BvhNode *node, const int frameId) const
756{               
757        BvhNode *parent = node->GetParent();
758
759        while (parent && (parent->GetLastVisitedFrame() != frameId))
760        {
761                parent->SetLastVisitedFrame(frameId);
762                parent = parent->GetParent();
763        }
764}
765
766
767void Bvh::MakeParentsVisible(BvhNode *node)
768{
769        BvhNode *parent = node->GetParent();
770
771        while (parent && (!parent->IsVisible()))
772        {
773                parent->SetVisible(true);
774                parent = parent->GetParent();
775        }
776}
777
778
779void Bvh::CollectLeaves(BvhNode *node, BvhLeafContainer &leaves)
780{
781        stack<BvhNode *> tStack;
782        tStack.push(node);
783
784        while (!tStack.empty())
785        {
786                BvhNode *node = tStack.top();
787
788                tStack.pop();
789
790                if (!node->IsLeaf())
791                {
792                        BvhInterior *interior = static_cast<BvhInterior *>(node);
793
794                        tStack.push(interior->mFront);
795                        tStack.push(interior->mBack);
796                }
797                else
798                {
799                        leaves.push_back(static_cast<BvhLeaf *>(node));
800                }
801        }
802}
803
804
805void Bvh::CollectNodes(BvhNode *node, BvhNodeContainer &nodes)
806{
807        stack<BvhNode *> tStack;
808
809        tStack.push(node);
810
811        while (!tStack.empty())
812        {
813                BvhNode *node = tStack.top();
814                tStack.pop();
815
816                nodes.push_back(node);
817
818                if (!node->IsLeaf())
819                {
820                        BvhInterior *interior = static_cast<BvhInterior *>(node);
821
822                        tStack.push(interior->mFront);
823                        tStack.push(interior->mBack);
824                }
825        }
826}
827
828
829typedef pair<BvhNode *, int> tPair;
830
831void Bvh::CollectNodes(BvhNode *root,
832                                           const int depth,
833                                           HierarchyNodeContainer &nodes)
834{
835        stack<tPair> tStack;
836        tStack.push(tPair(root, 0));
837
838        while (!tStack.empty())
839        {
840                BvhNode *node = tStack.top().first;
841                const int d = tStack.top().second;
842
843                tStack.pop();
844
845                // found depth => take this node
846                if (d == depth)
847                {
848                        nodes.push_back(node);
849                }
850                else if (node->IsLeaf())
851                {
852                        // found leaf
853                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
854
855                        // there is no further subdivision on triangle level
856                        if (leaf->mTriangleBvh->GetNumNodes() == 1)
857                        {
858                                nodes.push_back(leaf);
859                        }
860                        else // more than a root => search in local bvh
861                        {
862                                leaf->mTriangleBvh->
863                                        CollectNodes(leaf->mTriangleBvh->GetRoot(), depth - d, nodes);
864                        }
865                }
866                else // interior
867                {
868                        BvhInterior *interior = static_cast<BvhInterior *>(node);
869
870                        tStack.push(tPair(interior->mFront, d + 1));
871                        tStack.push(tPair(interior->mBack, d + 1));
872                }
873        }
874}
875
876
877void Bvh::CollectAllNodes(BvhNode *node, HierarchyNodeContainer &nodes)
878{
879        BvhNodeContainer bvhNodes;
880
881        // collect nodes of geometry bvh
882        CollectNodes(mRoot, bvhNodes);
883
884       
885        // first collect nodes of object bvh
886        BvhNodeContainer::const_iterator lit, lit_end = bvhNodes.end();
887
888        for (lit = bvhNodes.begin(); lit != lit_end; ++ lit)
889        {
890                nodes.push_back(*lit);
891        }
892
893        // collect nodes of local bvh: all except roots,
894        // because they are equivalent to geometry bvh leaves
895        for (lit = bvhNodes.begin(); lit != lit_end; ++ lit)
896        {
897                if ((*lit)->IsLeaf())
898                {
899                        BvhLeaf *leaf = static_cast<BvhLeaf *>(*lit);
900
901                        TriangleBvhNodeContainer hnodes;
902                        leaf->mTriangleBvh->CollectNodes(leaf->mTriangleBvh->GetRoot(), hnodes);
903
904                        TriangleBvhNodeContainer::const_iterator hit, hit_end = hnodes.end();
905
906                        for (hit = hnodes.begin(); hit != hit_end; ++ hit)
907                        {
908                                TriangleBvhNode *n = *hit;
909
910                                // don't include root of local bvh - it has the same bounds as the leaves
911                                if (n != leaf->mTriangleBvh->GetRoot())
912                                        nodes.push_back(n);
913                        }
914                }
915        }
916}
917
918
919void Bvh::CollectVisibleLeaves(BvhNode *node, BvhLeafContainer &leaves)
920{
921        stack<BvhNode *> tStack;
922        tStack.push(node);
923
924        while (!tStack.empty())
925        {
926                BvhNode *node = tStack.top();
927                tStack.pop();
928
929                if (IsWithinViewFrustum(node))
930                {
931                        if (!node->IsLeaf())
932                        {
933                                BvhInterior *interior = static_cast<BvhInterior *>(node);
934
935                                tStack.push(interior->mFront);
936                                tStack.push(interior->mBack);
937                        }
938                        else
939                        {
940                                leaves.push_back(static_cast<BvhLeaf *>(node));
941                        }
942                }
943        }
944}
945
946
947BvhLeaf *Bvh::GetRandomLeaf(BvhNode *node)
948{
949        stack<BvhNode *> nodeStack;
950 
951        nodeStack.push(node);
952
953        int mask = rand();
954
955    while (!nodeStack.empty())
956        {
957                BvhNode *node = nodeStack.top();
958                nodeStack.pop();
959               
960                if (node->IsLeaf())
961                {
962                        // random leaf
963                        return static_cast<BvhLeaf *>(node);
964                }
965                else
966                {
967                        BvhInterior *interior = static_cast<BvhInterior *>(node);
968                       
969                        BvhNode *next;
970                       
971                        // random decision
972                        if (mask & 1)
973                                next = interior->mBack;
974                        else
975                                next = interior->mFront;
976
977                        mask = mask >> 1;
978
979                        nodeStack.push(next);
980                }
981        }
982 
983        // should never come here
984        return NULL;
985}
986
987
988BvhLeaf *Bvh::GetRandomVisibleLeaf(BvhNode *node)
989{
990        BvhLeafContainer leaves;
991        leaves.reserve(node->GetNumLeaves());
992
993        CollectVisibleLeaves(node, leaves);
994
995        if (leaves.empty())
996                return NULL;
997
998        const int r = (int)(((float)rand() / RAND_MAX) * ((float)leaves.size() - 0.5f));
999
1000        return leaves[r];
1001}
1002
1003
1004void Bvh::CollectGeometry(BvhNode *node, GeometryVector &geometry)
1005{
1006        //geometry.reserve(node->CountPrimitives());
1007
1008        for (int i = node->mFirst; i <= node->mLast; ++ i)
1009        {
1010                geometry.push_back(mGeometry[i]);
1011        }
1012}
1013
1014
1015NodeGeometry **Bvh::GetGeometry(BvhNode *node, int &geometrySize)
1016{
1017        geometrySize = node->CountPrimitives();
1018        return mGeometry + node->mFirst;
1019}
1020
1021
1022void Bvh::UpdateInteriors(BvhNode *node)
1023{
1024        if (!node->IsLeaf())
1025        {
1026                BvhInterior *interior = static_cast<BvhInterior *> (node);
1027               
1028                // update the indices of the geometry so we can render interiors as well
1029                UpdateInteriors(interior->GetBack());
1030                UpdateInteriors(interior->GetFront());
1031
1032                // update area
1033                interior->mFirst = min(interior->GetBack()->mFirst, interior->GetFront()->mFirst);
1034                interior->mLast = max(interior->GetBack()->mLast, interior->GetFront()->mLast);
1035       
1036                interior->mArea = interior->GetBack()->mArea + interior->GetFront()->mArea;
1037        }
1038}
1039
1040
1041int     Bvh::IsWithinViewFrustumLocal(BvhNode *node)
1042{
1043        bool bIntersect = false;
1044
1045        if (node->GetParent())
1046                node->mPlaneMask = node->GetParent()->mPlaneMask;
1047
1048
1049        ////////
1050        //-- do the view frustum culling for the planes [mPreferredPlane - 5]
1051
1052        for (int i = node->mPreferredPlane; i < 6; ++ i)
1053        {
1054                //-- do the test only if necessary
1055                if (node->mPlaneMask & (1 << i))
1056                {
1057                        //-- test the n-vertex
1058                        if (node->mBox.getDistance(mClipPlaneAABBVertexIndices[i][0], mFrustum.mClipPlane[i]) > 0.0f)
1059                        {
1060                                //-- outside
1061                                node->mPreferredPlane = i;
1062                                return 0;
1063                        }
1064
1065                        //-- test the p-vertex
1066                        if (node->mBox.getDistance(mClipPlaneAABBVertexIndices[i][1], mFrustum.mClipPlane[i]) <= 0.0f)
1067                        {
1068                                //-- completely inside: children don't need to check against this plane no more
1069                                node->mPlaneMask^=      1 << i;
1070                        }
1071                        else
1072                        {
1073                                bIntersect = true;
1074                        }
1075                }
1076        }
1077
1078        //////////
1079        //-- do the view frustum culling for the planes [0 - m_iPreferredPlane)
1080
1081        for (int i = 0; i < node->mPreferredPlane; ++ i)
1082        {
1083                // do the test only if necessary
1084                if (node->mPlaneMask & (1 << i))
1085                {
1086                        //-- test the n-vertex
1087                        if (node->mBox.getDistance(mClipPlaneAABBVertexIndices[i][0], mFrustum.mClipPlane[i]) > 0.0f)
1088                        {
1089                                // outside
1090                                node->mPreferredPlane = i;
1091                                return 0;
1092                        }
1093
1094                        //-- test the p-vertex
1095                        if (node->mBox.getDistance(mClipPlaneAABBVertexIndices[i][1], mFrustum.mClipPlane[i]) <= 0.0f)
1096                        {
1097                                // completely inside: children don't need to check against this plane no more
1098                                node->mPlaneMask^= 1 << i;
1099                        }
1100                        else
1101                        {
1102                                bIntersect = true;
1103                        }
1104                }
1105        }
1106
1107        return bIntersect ? -1 : 1;
1108}
1109
1110
1111int     Bvh::IsWithinViewFrustum(const BoundingBox &box, const int planeMask, const int preferredPlane)
1112{
1113        bool bIntersect = false;
1114
1115        ////////
1116        //-- do the view frustum culling for the planes [mPreferredPlane - 5]
1117
1118        for (int i = preferredPlane; i < 6; ++ i)
1119        {
1120                //-- do the test only if necessary
1121                if (planeMask & (1 << i))
1122                {
1123                        //-- test the n-vertex
1124                        if (box.getDistance(mClipPlaneAABBVertexIndices[i][0], mFrustum.mClipPlane[i]) > 0.0f)
1125                                return 0;
1126
1127                        //-- test the p-vertex
1128                        if (!(box.getDistance(mClipPlaneAABBVertexIndices[i][1], mFrustum.mClipPlane[i]) <= 0.0f))
1129                                bIntersect = true;
1130                }
1131        }
1132
1133        //////////
1134        //-- do the view frustum culling for the planes [0 - m_iPreferredPlane)
1135
1136        for (int i = 0; i < preferredPlane; ++ i)
1137        {
1138                // do the test only if necessary
1139                if (planeMask & (1 << i))
1140                {
1141                        //-- test the n-vertex
1142                        if (box.getDistance(mClipPlaneAABBVertexIndices[i][0], mFrustum.mClipPlane[i]) > 0.0f)
1143                                // outside
1144                                return 0;
1145
1146                        //-- test the p-vertex
1147                        if (!(box.getDistance(mClipPlaneAABBVertexIndices[i][1], mFrustum.mClipPlane[i]) <= 0.0f))
1148                                bIntersect = true;
1149                }
1150        }
1151
1152        return bIntersect ? -1 : 1;
1153}
1154
1155
1156int     Bvh::IsWithinViewFrustum(BvhNode *node)
1157{
1158        if (node->mCache.mLastFrustumTestedFrameId == mFrameId)
1159        {
1160                return node->mCache.mFrustumCulled;
1161        }
1162
1163        node->mCache.mLastFrustumTestedFrameId = mFrameId;
1164
1165        timeViewFrustumCulling.Entry();
1166       
1167        if (Settings::Global()->get_nvocc_use_tighter_bounds_for_frustum_culling())
1168        {
1169                const int intersect = IsWithinViewFrustumLocal(node);
1170
1171                if ((node->mNumTestNodes == 1) || (intersect != -1))
1172                {
1173                        //OUT1("x");
1174                        node->mCache.mFrustumCulled = intersect;
1175                }
1176                else
1177                {
1178                        // maybe intersecting one of the tighter boxes
1179                        node->mCache.mFrustumCulled = 0;
1180
1181                        for (int i = 0; i < node->mNumTestNodes; ++ i)
1182                        {
1183                                RenderableHierarchyNode *n = mTestNodes[node->mTestNodesIdx + i];
1184
1185                                if (IsWithinViewFrustum(n->GetBox(),
1186                                                                                node->mPlaneMask,
1187                                                                                node->mPreferredPlane))
1188                                {
1189                                        node->mCache.mFrustumCulled = -1;
1190                                        break;
1191                                }
1192                        }
1193                }
1194        }
1195        else
1196        {
1197                //OUT1("y");
1198                node->mCache.mFrustumCulled = IsWithinViewFrustumLocal(node);
1199        }
1200
1201        timeViewFrustumCulling.Exit();
1202
1203        return node->mCache.mFrustumCulled;
1204}
1205
1206
1207void Bvh::InitFrame(Camera *camera, const int currentFrameId, Viewer *viewer)
1208{
1209        // = 0011 1111 which means that at the beginning, all six planes have to frustum culled
1210        mRoot->mPlaneMask = 0x3f;
1211        mCamera = camera;
1212
1213        mFrameId = currentFrameId;
1214
1215        // to begin with, we must grab the plane equations of the six clipplanes of the viewfrustum
1216        Matrix4f matViewing, matProjectionView;
1217        Transform3D     transform;
1218
1219        camera->GetTransform(transform);
1220        transform.get(matViewing);
1221
1222        camera->GetProjectionMatrix(matProjectionView);
1223        matProjectionView *= matViewing;
1224
1225        Vec3f vec;
1226        float fInvLength;
1227
1228
1229        //////////
1230        //-- extract the plane equations
1231
1232        for (int i = 0; i < 4; ++ i)
1233        {
1234                mFrustum.mClipPlane[0][i] = matProjectionView[i][3] - matProjectionView[i][0];  // right plane
1235                mFrustum.mClipPlane[1][i] = matProjectionView[i][3] + matProjectionView[i][0];  // left plane
1236                mFrustum.mClipPlane[2][i] = matProjectionView[i][3] + matProjectionView[i][1];  // bottom plane
1237                mFrustum.mClipPlane[3][i] = matProjectionView[i][3] - matProjectionView[i][1];  // top plane
1238                mFrustum.mClipPlane[4][i] = matProjectionView[i][3] - matProjectionView[i][2];  // far plane
1239                mFrustum.mClipPlane[5][i] = matProjectionView[i][3] + matProjectionView[i][2];  // near plane
1240        }
1241
1242        ////////////
1243        //-- normalize the coefficients and find the indices of the n- and p-vertices
1244
1245        for (int i = 0; i < 6; ++ i)
1246        {
1247                // the clipping planes look outward the frustum,
1248                // so distances > 0 mean that a point is outside
1249                fInvLength      = -1.0f / sqrt( mFrustum.mClipPlane[i][0] * mFrustum.mClipPlane[i][0] +
1250                                                                        mFrustum.mClipPlane[i][1] * mFrustum.mClipPlane[i][1] +
1251                                                                        mFrustum.mClipPlane[i][2] * mFrustum.mClipPlane[i][2]);
1252
1253                mFrustum.mClipPlane[i][0] *= fInvLength;
1254                mFrustum.mClipPlane[i][1] *= fInvLength;
1255                mFrustum.mClipPlane[i][2] *= fInvLength;
1256                mFrustum.mClipPlane[i][3] *= fInvLength;
1257
1258                vec.x = mFrustum.mClipPlane[i][0];
1259                vec.y = mFrustum.mClipPlane[i][1];
1260                vec.z = mFrustum.mClipPlane[i][2];
1261
1262                // n-vertex
1263                mClipPlaneAABBVertexIndices[i][0] = BoundingBox::getIndexNearestVertex(vec);
1264                // p-vertex
1265                mClipPlaneAABBVertexIndices[i][1] = BoundingBox::getIndexFurthestVertex(vec);   
1266        }
1267
1268
1269        const float aspect = mCamera->GetAspect();
1270        const float fov = mCamera->GetFov();
1271       
1272        mScale = sqrt(aspect) * 2.0f * tan(fov * mypi / 180.0f);
1273
1274        mNearPlane = mCamera->GetRealViewDirection();
1275        mNearPlaneD = - mNearPlane * (mCamera->GetPosition() - Origin3f);
1276}
1277
1278
1279float Bvh::CalcDistance(BvhNode *node) const
1280{
1281        timeDistance.Entry();
1282
1283        float distance;
1284
1285#if USE_TIGHTER_BOUNDS_FOR_ALL
1286        float minDist = 1e25f;
1287
1288        //OUT1("testing " << mNumTestNodes << " nodes");
1289        for (int i = 0; i < node->mNumTestNodes; ++ i)
1290        {
1291                RenderableHierarchyNode *hnode = mTestNodes[node->mTestNodesIdx + i];
1292
1293                if(hnode->mCache.mLastDistanceTestedFrameId < mFrameId)
1294                {
1295                        hnode->mCache.mDistance =
1296                                hnode->GetBox().getMinVisibleDistance(mNearPlane, mNearPlaneD);
1297                        hnode->mCache.mLastDistanceTestedFrameId = mFrameId;
1298                }
1299
1300                if (hnode->mCache.mDistance < minDist)
1301                        minDist = hnode->mCache.mDistance;
1302        }
1303
1304        distance = minDist;
1305
1306#else
1307
1308        if(node->mCache.mLastDistanceTestedFrameId != mFrameId)
1309        {
1310                //OUT1("z " << node->mLastDistanceTestedFrameId  << " " << mFrameId);
1311                node->mCache.mDistance = node->GetBox().getMinVisibleDistance(mNearPlane, mNearPlaneD);
1312                node->mCache.mLastDistanceTestedFrameId = mFrameId;
1313        }
1314
1315        distance = node->mCache.mDistance;
1316#endif
1317
1318        timeDistance.Exit();
1319
1320        return distance;
1321}
1322
1323
1324float Bvh::GetSquareDistance(BvhNode *node) const
1325{
1326        timeDistance.Entry();
1327
1328        float distance;
1329
1330#if USE_TIGHTER_BOUNDS_FOR_ALL
1331        const Vector3f nearplane = mCamera->GetRealViewDirection();
1332        const float nearplaneD = - nearplane * (mCamera->GetPosition() - Origin3f);
1333
1334        float minDist = 1e25f;
1335       
1336        //OUT1("testing " << mNumTestNodes << " nodes");
1337        for (int i = 0; i < node->mNumTestNodes; ++ i)
1338        {
1339                RenderableHierarchyNode *hnode = mTestNodes[node->mTestNodesIdx + i];
1340                const float dist = GetMinSquareDistance(hnode->GetBox());
1341
1342                if (dist < minDist)
1343                        minDist = dist;
1344        }
1345
1346        distance = minDist;
1347#else
1348        distance = GetMinSquareDistance(node->GetBox());
1349#endif
1350
1351        timeDistance.Exit();
1352
1353        return distance;
1354}
1355
1356
1357float Bvh::GetMinSquareDistance(const BoundingBox &box) const
1358{
1359        float minDist = 1e25f;
1360
1361        const Point3f *pts = (const Point3f *)box.getVertexData();
1362        const Point3f pos = mCamera->GetPosition();
1363
1364        for (int i = 0; i < 8; ++ i)
1365        {
1366                const float newDist = DistanceSquared(pts[i], pos);
1367
1368                if (newDist < minDist)
1369                        minDist = newDist;
1370        }
1371
1372        return minDist;
1373}
1374
1375
1376bool Bvh::ExportBinTree(const string &filename)
1377{
1378        ofstream stream(filename.c_str(), ifstream::binary);
1379       
1380        if (!stream.is_open()) return false;
1381
1382        OUT1("exporting bvh");
1383
1384        std::queue<BvhNode *> tStack;
1385        tStack.push(mRoot);
1386
1387        while(!tStack.empty())
1388        {
1389                BvhNode *node = tStack.front();
1390                tStack.pop();
1391               
1392                if (node->IsLeaf())
1393                {
1394                        //OUT1("l");
1395                        ExportBinLeaf(stream, static_cast<BvhLeaf *>(node));
1396                }
1397                else
1398                {
1399                        //OUT1("i");
1400                        BvhInterior *interior = static_cast<BvhInterior *>(node);
1401
1402                        ExportBinInterior(stream, interior);
1403                       
1404                        tStack.push(interior->mFront);
1405                        tStack.push(interior->mBack);
1406                }
1407        }
1408
1409        OUT1("... finished");
1410
1411        return true;
1412}
1413
1414
1415void Bvh::ExportBinLeaf(ofstream &stream, BvhLeaf *leaf)
1416{
1417        int type = TYPE_LEAF;
1418        int first = leaf->mFirst;
1419        int last = leaf->mLast;
1420
1421        stream.write(reinterpret_cast<char *>(&type), sizeof(int));
1422        stream.write(reinterpret_cast<char *>(&first), sizeof(int));
1423        stream.write(reinterpret_cast<char *>(&last), sizeof(int));
1424}
1425
1426
1427void Bvh::ExportBinInterior(ofstream &stream, BvhInterior *interior)
1428{
1429        int type = TYPE_INTERIOR;
1430        stream.write(reinterpret_cast<char *>(&type), sizeof(int));
1431        stream.write(reinterpret_cast<char *>(&interior->mAxis), sizeof(char));
1432        stream.write(reinterpret_cast<char *>(&interior->mPosition), sizeof(float));
1433}
1434
1435
1436BvhLeaf *Bvh::ImportBinLeaf(ifstream &stream, BvhInterior *parent)
1437{
1438        BvhLeaf *leaf = new BvhLeaf(parent);
1439
1440        int first, last;
1441
1442        stream.read(reinterpret_cast<char *>(&first), sizeof(int));
1443        stream.read(reinterpret_cast<char *>(&last), sizeof(int));
1444
1445        leaf->mFirst = first;
1446        leaf->mLast = last;
1447
1448        return leaf;
1449}
1450
1451
1452BvhInterior *Bvh::ImportBinInterior(ifstream &stream, BvhInterior *parent)
1453{
1454        BvhInterior *interior = new BvhInterior(parent);
1455
1456        stream.read(reinterpret_cast<char *>(&interior->mAxis), sizeof(char));
1457        stream.read(reinterpret_cast<char *>(&interior->mPosition), sizeof(float));
1458
1459        return interior;
1460}
1461
1462
1463BvhNode *Bvh::LoadNextNode(ifstream &stream, BvhInterior *parent)
1464{
1465        int nodeType;
1466        stream.read(reinterpret_cast<char *>(&nodeType), sizeof(int));
1467
1468        if (nodeType == TYPE_LEAF)
1469        {
1470                //OUT1("l");
1471                return ImportBinLeaf(stream, static_cast<BvhInterior *>(parent));
1472        }
1473
1474        if (nodeType == TYPE_INTERIOR)
1475        {
1476                //OUT1("i");
1477                return ImportBinInterior(stream, static_cast<BvhInterior *>(parent));
1478        }
1479
1480        return NULL;
1481}
1482
1483
1484Bvh *Bvh::LoadFromFile(const string &filename, const GeometryVector &geom)
1485{
1486        // export binary version of mesh
1487        queue<BvhNode *> tStack;
1488        ifstream stream(filename.c_str(), ifstream::binary);
1489
1490        if (!stream.is_open()) return NULL;
1491
1492        OUT1("loading bvh");
1493        Bvh *bvh = new Bvh();
1494
1495        bvh->mGeometrySize = geom.size();
1496        bvh->mGeometry = new NodeGeometry*[bvh->mGeometrySize];
1497
1498        for (size_t i = 0; i < bvh->mGeometrySize; ++ i)
1499                bvh->mGeometry[i] = geom[i];
1500
1501        bvh->mRoot = bvh->LoadNextNode(stream, NULL);
1502
1503        tStack.push(bvh->mRoot);
1504        bvh->mNumNodes = 1;
1505
1506        while(!tStack.empty())
1507        {
1508                BvhNode *node = tStack.front();
1509                tStack.pop();
1510
1511                if (!node->IsLeaf())
1512                {
1513                        bvh->mNumNodes += 2;
1514
1515                        BvhInterior *interior = static_cast<BvhInterior *>(node);
1516
1517            BvhNode *front = bvh->LoadNextNode(stream, interior);
1518                        BvhNode *back = bvh->LoadNextNode(stream, interior);
1519       
1520                        interior->mFront = front;
1521                        interior->mBack = back;
1522
1523                        front->mDepth = interior->mDepth + 1;
1524                        back->mDepth = interior->mDepth + 1;
1525
1526                        tStack.push(front);                     
1527                        tStack.push(back);
1528                }
1529        }
1530
1531        OUT1("... finished loading " << bvh->mNumNodes << " nodes, updating boxes");
1532
1533        //adjust bounding boxes
1534        bvh->UpdateBoxes(bvh->mRoot);
1535        bvh->UpdateNumLeaves(bvh->mRoot);
1536
1537        // compute unique ids
1538        bvh->ComputeIds();
1539        // update the indices of the geometry so we can render interiors as well
1540        bvh->UpdateInteriors(bvh->mRoot);
1541        // do this once so at least the current node bounding box is tested
1542        bvh->RecomputeBounds();
1543
1544        return bvh;
1545}
1546
1547
1548float Bvh::ComputeScreenSpaceProjection(BvhNode *node) const
1549{
1550#if 0
1551        int projection = 0;
1552
1553        for (int i = 0; i < node->mNumTestNodes; ++ i)
1554        {
1555                RenderableHierarchyNode *n = mTestNodes[node->mTestNodesIdx + i];
1556
1557                if(hnode->.mCache.mLastProjectionFrameId < mFrameId)
1558                {
1559                        hnode->mCache.mProjection =
1560                                ComputeScreenSpaceProjection(hnode->GetBox());
1561                        hnode->mCache.mLastProjectionFrameId = mCurrentFrameId;
1562                }
1563               
1564                projection += hnode->mCache.mProjection;
1565        }
1566
1567        return projection;
1568
1569#else
1570
1571        if(node->mCache.mLastProjectionFrameId < mFrameId)
1572        {
1573                node->mCache.mProjection =
1574                        ComputeScreenSpaceProjection(node->GetBox());
1575                node->mCache.mLastProjectionFrameId = mFrameId;
1576        }
1577
1578        return node->mCache.mProjection;
1579#endif
1580}
1581
1582
1583float Bvh::ComputeScreenSpaceProjection(const BoundingBox &box) const
1584{
1585#if 0
1586        const float dist = CalcDistance(box);
1587#else
1588        //const float dist = sqrt(GetMinSquareDistance(box));
1589        const float dist = Distance(mCamera->GetPosition(), box.getCenter());
1590#endif
1591
1592        const float scale = dist ? dist * mScale : 1e-6;
1593        const float f = 1.0f / scale;
1594        const float coverage = f * f * box.getSurface() / 6.0f;
1595
1596#if 0
1597        OUT1("scale: " << scale);
1598        OUT1("box: " << box.getSurface());
1599        OUT1("aspect: " << aspect);
1600        OUT1("fov: " << fov);
1601        OUT1("tan: " << tan(fov * mypi / 180.0f));
1602        //OUT1("w: " << w << " h: " << h);
1603        OUT1("cov: " << coverage << " pix: " << coverage * w * h << " f: " << f);
1604#endif
1605        return coverage;
1606}
1607
1608
1609void Bvh::RenderBoundingBox(BvhNode *node)
1610{
1611#if 1
1612        static BvhNodeContainer dummy(1);
1613        dummy[0] = node;
1614        RenderBoundingBoxes(dummy);
1615#else
1616        RenderBoxIndividual(node);
1617#endif
1618}
1619
1620
1621void Bvh::RenderBoundingBoxImmediate(const BoundingBox &box, const bool restartStrip)
1622{
1623        const Point3f *pU = box.getUpperPtr();
1624        const Point3f *pL = box.getLowerPtr();
1625
1626        ///////////
1627        //-- render AABB as triangle strips
1628
1629        glVertex3f(pL->x, pL->y, pU->z);
1630        glVertex3f(pU->x, pL->y, pU->z);
1631        glVertex3f(pL->x, pU->y, pU->z);
1632        glVertex3f(pU->x, pU->y, pU->z);
1633        glVertex3f(pL->x, pU->y, pL->z);
1634        glVertex3f(pU->x, pU->y, pL->z);
1635        glVertex3f(pL->x, pL->y, pL->z);
1636        glVertex3f(pU->x, pL->y, pL->z);
1637
1638        glPrimitiveRestartNV();
1639
1640        //-- render second half of AABB
1641        glVertex3f(pL->x, pU->y, pU->z);
1642        glVertex3f(pL->x, pU->y, pL->z);
1643        glVertex3f(pL->x, pL->y, pU->z);
1644        glVertex3f(pL->x, pL->y, pL->z);
1645        glVertex3f(pU->x, pL->y, pU->z);
1646        glVertex3f(pU->x, pL->y, pL->z);
1647        glVertex3f(pU->x, pU->y, pU->z);
1648        glVertex3f(pU->x, pU->y, pL->z);
1649
1650       
1651        // restart for all but last node
1652        if (restartStrip)
1653        {
1654                glPrimitiveRestartNV();
1655        }
1656}
1657
1658
1659int Bvh::RenderBoundingBoxesImmediate(const BvhNodeContainer &nodes)
1660{
1661        timeSetup.Entry();
1662        int renderedBoxes = 0;
1663       
1664        glBegin(GL_TRIANGLE_STRIP);
1665
1666        BvhNodeContainer::const_iterator bit, bit_end = nodes.end();
1667
1668        for (bit = nodes.begin(); bit != bit_end; ++ bit)
1669        {
1670                BvhNode *node = *bit;
1671
1672                renderedBoxes += node->mNumTestNodes;
1673#if 0
1674                const bool restartStrip = false;
1675                RenderBoundingBoxImmediate(node->GetBox(), restartStrip);
1676#else
1677                //OUT1("nodes: " << node->mTestNodes.size() << " l: " << node->IsLeaf());
1678                for (int i = 0; i < node->mNumTestNodes; ++ i)
1679                {
1680                        RenderableHierarchyNode *testNode = mTestNodes[node->mTestNodesIdx + i];
1681                        const BoundingBox &box = testNode->GetBox();
1682
1683                        // restart for all but last node
1684                        const bool restartStrip = (bit != bit_end - 1) || (i != node->mNumTestNodes - 1);
1685
1686                        RenderBoundingBoxImmediate(box, restartStrip);
1687                }
1688#endif
1689        }
1690        glEnd();
1691        timeSetup.Exit();
1692
1693        return renderedBoxes;
1694}
1695
1696
1697int Bvh::RenderBoundingBoxes(const BvhNodeContainer &nodes)
1698{
1699        // always render in immediate mode if there is only one box to render
1700        if (((nodes.size() == 1) && (nodes[0]->mNumTestNodes == 1)) ||
1701                !Settings::Global()->get_nvocc_use_index_arrays())
1702        {       
1703                // render bounding boxes individually
1704                return RenderBoundingBoxesImmediate(nodes);
1705        }
1706        else
1707        {
1708                const int renderedBoxes =
1709                        PrepareBoundingBoxesWithDrawArrays(nodes);
1710                RenderBoundingBoxesWithDrawArrays(renderedBoxes);
1711
1712                return renderedBoxes;
1713        }
1714}
1715
1716
1717int Bvh::PrepareBoundingBoxesWithDrawArrays(const BvhNodeContainer &nodes)
1718{
1719        //////
1720        //-- for the first time we come here ...
1721
1722        if (!mIndices)
1723        {       // create list of indices
1724                CreateIndices();
1725        }
1726
1727        if (sCurrentVboId == -1)
1728        {       
1729                // prepare the vbo
1730                PrepareVertices();
1731        }
1732
1733        ///////////////
1734
1735        timeSetup.Entry();
1736
1737        int numNodes = 0;
1738
1739        BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
1740
1741        for (nit = nodes.begin(); nit != nit_end; ++ nit)
1742        {
1743                BvhNode *node = *nit;
1744
1745        const int numIndices = node->mNumTestNodes * sNumIndicesPerBox;
1746               
1747                // copy indices
1748                memcpy(mIndices + numNodes * sNumIndicesPerBox,
1749                           mTestIndices + node->mIndicesPtr,
1750#if 0 //ALIGN_INDICES
1751                           ((numIndices / 32) * 32 + 32) * sizeof(unsigned int));
1752#else
1753                           numIndices * sizeof(unsigned int));
1754#endif
1755                numNodes += node->mNumTestNodes;
1756        }
1757
1758        timeSetup.Exit();
1759
1760        return numNodes;
1761}
1762
1763
1764void Bvh::RenderBoundingBoxesWithDrawArrays(const int numNodes)
1765{
1766        //////
1767        //-- Rendering the vbo
1768
1769        timeIssueDrawElements.Entry();
1770
1771        if (useVbos)
1772                // set the vertex pointer to the vertex buffer
1773                glVertexPointer(3, GL_FLOAT, 0, (char *)NULL);         
1774        else
1775                glVertexPointer(3, GL_FLOAT, 0, mVertices);
1776
1777        // we do use the last or the first index (they are generate and only used to connect strips)
1778        const int numElements = numNodes * sNumIndicesPerBox - 1;
1779
1780        // don't render first degenerate index
1781        glDrawElements(GL_TRIANGLE_STRIP, numElements, GL_UNSIGNED_INT, mIndices + 1);
1782       
1783        timeIssueDrawElements.Exit();
1784}
1785
1786
1787#define ALIGN_INDICES 1
1788
1789void Bvh::CreateIndices()
1790{
1791        // collect bvh nodes
1792        BvhNodeContainer nodes;
1793        CollectNodes(mRoot, nodes);
1794
1795        OUT1("creating new indices");
1796
1797        int numMaxIndices = 0;
1798
1799        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
1800
1801        for (lit = nodes.begin(); lit != lit_end; ++ lit)
1802        {
1803                int offset = (*lit)->mNumTestNodes * sNumIndicesPerBox;
1804#if ALIGN_INDICES
1805                // align with 32
1806                offset = (offset / 32) * 32 + 32;
1807#endif
1808                numMaxIndices += offset;
1809        }
1810
1811
1812        OUT1("creating global indices buffer");
1813
1814        if (mIndices) delete [] mIndices;
1815        if (mTestIndices) delete [] mTestIndices;
1816
1817        // global buffer: create it once so we don't have
1818        // to allocate memory from the chunks of the node
1819        mIndices = new unsigned int[numMaxIndices];
1820
1821        // create new index buffer for the individual nodes
1822        mTestIndices = new unsigned int[numMaxIndices];
1823       
1824        mCurrentIndicesPtr = 0;
1825
1826        for (lit = nodes.begin(); lit != lit_end; ++ lit)
1827        {
1828                BvhNode *node = *lit;
1829               
1830                // resize array
1831                node->mIndicesPtr = mCurrentIndicesPtr;
1832
1833                int numIndices = 0;
1834
1835                // the bounding box of the test nodes are rendered instead of the root node
1836                // => store their indices
1837                for (int i = 0; i < node->mNumTestNodes; ++ i, numIndices += sNumIndicesPerBox)
1838                {
1839                        RenderableHierarchyNode *testNode = mTestNodes[node->mTestNodesIdx + i];
1840
1841                        // add indices to root node
1842                        for (int j = 0; j < sNumIndicesPerBox; ++ j)
1843                        {
1844                                mTestIndices[mCurrentIndicesPtr + numIndices + j] = sIndices[j] + testNode->GetId() * 8;
1845                        }
1846                }
1847
1848                // align with 32
1849#if ALIGN_INDICES
1850                const int offset = (numIndices / 32) * 32 + 32;
1851#else
1852                const int offset = numIndices;
1853#endif
1854                mCurrentIndicesPtr += offset;
1855        }
1856}
1857
1858
1859void Bvh::ComputeIds()
1860{
1861        // collect all nodes, also the nodes from local bvh
1862        // warning: root nodes local bvh are not in there, as they
1863        // are equivalent geometry bvh leaves
1864        HierarchyNodeContainer nodes;
1865        CollectAllNodes(mRoot, nodes);
1866
1867        // assign ids to all nodes of the "regular" hierarchy
1868        int i = 0;
1869        HierarchyNodeContainer::const_iterator lit, lit_end = nodes.end();
1870
1871        for (lit = nodes.begin(); lit != lit_end; ++ lit, ++ i)
1872        {
1873                (*lit)->SetId(i);
1874        }
1875}
1876
1877
1878void Bvh::PrepareVertices()
1879{
1880        // collect all nodes, also the nodes from local bvh
1881        // warning: root nodes local bvh are not in there, as they
1882        // are equivalent geometry bvh leaves
1883        HierarchyNodeContainer nodes;
1884
1885        nodes.reserve(GetNumNodes());
1886        CollectAllNodes(mRoot, nodes);
1887
1888        const unsigned int bufferSize = 8 * (int)nodes.size();
1889        mVertices = new Point3f[bufferSize];
1890       
1891        int i = 0;
1892       
1893        // store bounding box vertices
1894        HierarchyNodeContainer::const_iterator lit, lit_end = nodes.end();
1895
1896        for (lit = nodes.begin(); lit != lit_end; ++ lit, i += 8)
1897        {
1898                RenderableHierarchyNode *node = *lit;
1899                const Point3f *vertices = (const Point3f *)node->GetBox().getVertexData();
1900
1901                for (int j = 0; j < 8; ++ j)
1902                {       
1903                        ((Point3f *)mVertices)[node->GetId() * 8 + j] = vertices[j];
1904                }
1905        }
1906
1907        if (useVbos)
1908        {
1909                glGenBuffersARB(1, &sCurrentVboId);
1910                glBindBufferARB(GL_ARRAY_BUFFER_ARB, sCurrentVboId);
1911                glVertexPointer(3, GL_FLOAT, 0, (char *)NULL);
1912       
1913                glBufferDataARB(GL_ARRAY_BUFFER_ARB,
1914                                    bufferSize * sizeof(Point3f),
1915                                    mVertices,
1916                                                GL_STATIC_DRAW_ARB);
1917
1918                //glBindBufferARB(GL_ARRAY_BUFFER_ARB, 0);
1919
1920                // data handled by graphics driver from now on
1921                DELAPTR(mVertices);
1922
1923                OUT1("***** created vbos *********");
1924        }
1925        else
1926        {
1927                sCurrentVboId = 0;
1928        glVertexPointer(3, GL_FLOAT, 0, mVertices);
1929
1930                OUT1("created vertices");
1931        }
1932}
1933
1934
1935void Bvh::SetMaxDepthForTestingChildren(const int maxDepth)
1936{
1937        if (maxDepth != mMaxDepthForTestingChildren)
1938        {
1939                mMaxDepthForTestingChildren = maxDepth;
1940                RecomputeBounds();
1941        }
1942}
1943
1944
1945void Bvh::SetAreaRatioThresholdForTestingChildren(const float ratio)
1946{
1947        if (ratio != mAreaRatioThreshold)
1948        {
1949                mAreaRatioThreshold = ratio;
1950                RecomputeBounds();
1951        }
1952}
1953
1954
1955void Bvh::SetVolRatioThresholdForTestingChildren(const float ratio)
1956{
1957        if (ratio != mVolRatioThreshold)
1958        {
1959                mVolRatioThreshold = ratio;
1960                RecomputeBounds();
1961        }
1962}
1963
1964
1965void Bvh::SetUseTighterBoundsForTests(const bool tighterBoundsForTests)
1966{
1967        if (mUseTighterBoundsOnlyForLeafTests != tighterBoundsForTests)
1968        {
1969                mUseTighterBoundsOnlyForLeafTests = tighterBoundsForTests;
1970                RecomputeBounds();
1971        }
1972}
1973
1974
1975void Bvh::SetCollectTighterBoundsWithMaxLevel(bool t)
1976{
1977        if (mCollectTighterBoundsWithMaxLevel != t)
1978        {
1979                mCollectTighterBoundsWithMaxLevel = t;
1980                RecomputeBounds();
1981        }
1982}
1983
1984
1985void Bvh::RecomputeBounds()
1986{
1987        // clear old list
1988        mTestNodes.clear();
1989
1990        // collect all nodes
1991        BvhNodeContainer nodes;
1992        CollectNodes(mRoot, nodes);
1993
1994        OUT1("recomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren);
1995
1996        if (mCollectTighterBoundsWithMaxLevel)
1997                OUT1("creating tighter bounds using max level");
1998        else
1999                OUT1("creating tighter bounds using best set");
2000
2001        int success = 0;
2002        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
2003
2004        for (lit = nodes.begin(); lit != lit_end; ++ lit)
2005        {
2006                BvhNode *node = *lit;
2007
2008                if (mCollectTighterBoundsWithMaxLevel)
2009                {
2010                        //OUT1("creating tighter bounds using max level");
2011
2012                        // recreate list of nodes that will be tested as a proxy ...
2013                        if (CreateNodeRenderList(node))
2014                                ++ success;
2015                }
2016                else
2017                {
2018                        //OUT1("creating tighter bounds using best set");
2019
2020                        HierarchyNodeContainer hnodes;
2021                        CollectBestNodes(node, hnodes);
2022
2023                        // the new test nodes are added at the end of the vector
2024                        node->mTestNodesIdx = mTestNodes.size();
2025
2026                        HierarchyNodeContainer::const_iterator cit;
2027
2028                        // use the found nodes as nodes during the occlusion tests
2029                        for (cit = hnodes.begin(); cit != hnodes.end(); ++ cit)
2030                        {
2031                                RenderableHierarchyNode *child = *cit;
2032                                mTestNodes.push_back(child);
2033                        }
2034
2035                        node->mNumTestNodes = (int)hnodes.size();
2036                }
2037                //OUT1("testnodes: " << node->mNumTestNodes);
2038        }
2039
2040        const float p = 100.0f * (float)success / nodes.size();
2041
2042        OUT1("created tighter bounds for " << p << " percent of the nodes");
2043
2044        // recreate indices used for indirect mode rendering
2045        if (mIndices)
2046        {
2047                CreateIndices();
2048        }
2049}
2050
2051       
2052bool Bvh::CreateNodeRenderList(BvhNode *node)
2053{
2054        HierarchyNodeContainer children;
2055
2056        if (mUseTighterBoundsOnlyForLeafTests && !node->IsLeaf())
2057        {
2058                children.push_back(node);
2059        }
2060        else
2061        {
2062                // collect nodes that will be tested instead of the leaf node
2063                // in order to get a tighter bounding box test
2064                CollectNodes(node, mMaxDepthForTestingChildren, children);
2065        }
2066
2067
2068        // using the tighter bounds is not feasable in case
2069        // that the tighter bounds represent nearly the same projected area
2070        // as the old bounding box. Find this out using either volume or area
2071        // heuristics
2072
2073        float vol = 0;
2074        float area = 0;
2075
2076        HierarchyNodeContainer::const_iterator cit;
2077
2078        for (cit = children.begin(); cit != children.end(); ++ cit)
2079        {
2080                RenderableHierarchyNode *c = *cit;
2081
2082                area += c->GetBox().getSurface();
2083                vol += c->GetBox().getVolume();
2084        }
2085
2086        const float volRatio = vol / node->GetBox().getVolume();
2087        const float areaRatio = area / node->GetBox().getSurface();
2088       
2089        bool success;
2090
2091        if ((areaRatio < mAreaRatioThreshold) &&
2092                (volRatio < mVolRatioThreshold))
2093        {
2094                success = true;
2095        }
2096        else
2097        {
2098                // hack: only store node itself
2099                children.clear();
2100                children.push_back(node);
2101
2102                success = false;
2103        }
2104
2105        // the new test nodes are added at the end of the vector
2106        node->mTestNodesIdx = mTestNodes.size();
2107
2108        // use the found nodes as nodes during the occlusion tests
2109        for (cit = children.begin(); cit != children.end(); ++ cit)
2110        {
2111                RenderableHierarchyNode *child = *cit;
2112                mTestNodes.push_back(child);
2113        }
2114
2115        node->mNumTestNodes = (int)children.size();
2116
2117        return success;
2118}
2119
2120
2121void Bvh::ResetNodeClassifications()
2122{
2123        BvhNodeContainer nodes;
2124
2125        nodes.reserve(GetNumNodes());
2126        CollectNodes(mRoot, nodes);
2127
2128        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
2129
2130        for (lit = nodes.begin(); lit != lit_end; ++ lit)
2131        {
2132                (*lit)->ResetVisibility();
2133        }
2134}
2135
2136
2137int Bvh::PostProcessLeaves(BvhLeafContainer &leaves)
2138{
2139        OUT1("creating tighter bounds for leaves");
2140
2141        BvhLeafContainer::const_iterator lit, lit_end = leaves.end();
2142
2143        int i = 0;
2144        int tighter = 0;
2145
2146        for (lit = leaves.begin(); lit != lit_end; ++ lit, ++ i)
2147        {
2148                BvhLeaf *leaf = *lit;
2149
2150                int triangleCount;
2151                // collect the triangles from the stored geometry
2152                Point3f *triangles = CollectTriangles(leaf, triangleCount);
2153
2154                if (CreateTighterBoundsForLeaf(leaf, triangles, triangleCount))
2155                        ++ tighter;
2156
2157                leaf->mArea = ComputeGeometryArea(leaf, triangles, triangleCount);
2158
2159                delete [] triangles;
2160
2161                if (i % 1000 == 999)
2162                        OUT1(i << " leaves processed ");
2163        }
2164
2165        const float p = 100.0f * tighter / leaves.size();
2166        OUT1("created tighter bounds for " << p << " percent of the leaves");
2167
2168        return tighter;
2169}
2170
2171
2172bool Bvh::CreateTighterBoundsForLeaf(BvhLeaf *leaf, Point3f *triangles, const int triangleCount)
2173{
2174        // create a local bvh over the triangles
2175        if (leaf->mTriangleBvh) delete leaf->mTriangleBvh;
2176
2177        leaf->mTriangleBvh = new TriangleBvh((Triangle *)triangles, triangleCount);
2178
2179        const int maxDepth = Settings::Global()->get_nvocc_local_bvh_max_depth();
2180        const int maxTriangles = Settings::Global()->get_nvocc_local_bvh_max_triangles();
2181        const int minArea = Settings::Global()->get_nvocc_local_bvh_min_area();
2182        const int splitType = Settings::Global()->get_nvocc_local_bvh_split_type();
2183
2184        leaf->mTriangleBvh->SetMaxDepth(maxDepth);
2185        leaf->mTriangleBvh->SetMaxTriangles(maxTriangles);
2186        leaf->mTriangleBvh->SetMinAreaRatio(minArea);
2187        leaf->mTriangleBvh->SetSplitType(splitType);
2188       
2189        leaf->mTriangleBvh->SetVerboseOutput(false);
2190
2191        // construct
2192        leaf->mTriangleBvh->Construct();
2193
2194        return true;
2195}
2196
2197
2198float Bvh::ComputeGeometryArea(BvhLeaf *leaf, Point3f *triangles, const int triangleCount) const
2199{
2200        float area = 0;
2201
2202        for (int i = 0; i < triangleCount; ++ i)
2203        {
2204                area += ((Triangle *)triangles)[i].GetArea();
2205        }
2206
2207        return area;
2208}
2209
2210
2211Point3f *Bvh::CollectTriangles(BvhLeaf *leaf, int &triangleCount)
2212{
2213        // count triangles in the leaf
2214        triangleCount = 0;
2215
2216        for (int geomIdx = leaf->mFirst; geomIdx <= leaf->mLast; ++ geomIdx)
2217        {
2218                Shape3D *sh = static_cast<Shape3D *>(mGeometry[geomIdx]->GetNode());
2219                IndexedTriangleStripArray *strips = static_cast<IndexedTriangleStripArray *>(sh->getGeometry());
2220
2221                triangleCount += strips->getNumTriangles();
2222        }
2223
2224        Triangle *triangles = new Triangle[triangleCount];
2225        //OUT1("The leaf contains " << triangleCount << " triangles in " << (int)geometry.size() << " nodes");
2226
2227        int currentIdx = 0;
2228       
2229        for (int geomIdx = leaf->mFirst; geomIdx <= leaf->mLast; ++ geomIdx)
2230        {
2231                NodeGeometry *geom = mGeometry[geomIdx];
2232
2233                Shape3D *sh = static_cast<Shape3D *>(geom->GetNode());
2234               
2235                IndexedTriangleStripArray *strips =
2236                        static_cast<IndexedTriangleStripArray *>(sh->getGeometry());
2237
2238                // get indices of containted triangles (strips are converted before)
2239                int *indices;
2240       
2241                int tCount = strips->getNumTriangles();
2242                int indexCount = tCount * 3;
2243               
2244                // compute triangles from strips
2245                Point3f *coordinates = (Point3f *)strips->getCoordRef3f();
2246                strips->getTriangleCoordinateIndices(0, &indices, indexCount);
2247
2248                for (int i = 0; i < tCount; ++ i)
2249                {
2250                        triangles[i + currentIdx].mVertices[0] = coordinates[indices[i * 3 + 0]];
2251                        triangles[i + currentIdx].mVertices[1] = coordinates[indices[i * 3 + 1]];
2252                        triangles[i + currentIdx].mVertices[2] = coordinates[indices[i * 3 + 2]];
2253
2254                        if (geom->mMatId != NV_RenderPredictorRenderAction::NO_MAT)
2255                        {
2256                                const Matrix4f &m = mRenderer->app_mats[geom->mMatId];
2257                                Transform3D tf(m);
2258                                tf.transform(triangles[i + currentIdx].mVertices[0]);
2259                                tf.transform(triangles[i + currentIdx].mVertices[1]);
2260                                tf.transform(triangles[i + currentIdx].mVertices[2]);
2261                        }
2262                }
2263
2264                currentIdx += tCount;
2265        }
2266
2267        return (Point3f *)triangles;
2268}
2269
2270
2271int Bvh::CountTriangles(BvhLeaf *leaf) const
2272{
2273        int triangleCount = 0;
2274       
2275        for (int i = leaf->mFirst; i <= leaf->mLast; ++ i)
2276        {
2277                triangleCount += mGeometry[i]->mNumTriangles;
2278        }
2279
2280        return triangleCount;
2281}
2282
2283
2284void Bvh::ComputeBvhStats()
2285{
2286        std::stack<BvhNode *> nodeStack;
2287        nodeStack.push(mRoot);
2288
2289        while (!nodeStack.empty())
2290        {
2291                BvhNode *node = nodeStack.top();
2292                nodeStack.pop();
2293
2294                if (node->IsLeaf())
2295                {
2296                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
2297
2298                        mBvhStats.mLeafSA += leaf->mBox.getSurface();
2299                        mBvhStats.mLeafVol += leaf->mBox.getVolume();
2300
2301                        TriangleBvh::TriangleBvhStats tStats;
2302                        leaf->mTriangleBvh->GetBvhStats(tStats);
2303
2304                        mBvhStats.mBoundsLeafSA += tStats.mLeafSA;
2305                        mBvhStats.mBoundsInteriorSA += tStats.mInteriorSA;
2306
2307                        mBvhStats.mBoundsLeafVol += tStats.mLeafVol;
2308                        mBvhStats.mBoundsInteriorVol += tStats.mInteriorVol;
2309
2310                        mBvhStats.mBoundsLeavesCount += leaf->mTriangleBvh->GetNumLeaves();
2311                }
2312                else
2313                {
2314                        mBvhStats.mInteriorSA += node->mBox.getSurface();
2315                        mBvhStats.mInteriorVol += node->mBox.getVolume();
2316
2317                        BvhInterior *interior = static_cast<BvhInterior *>(node);
2318                       
2319                        nodeStack.push(interior->mBack);
2320                        nodeStack.push(interior->mFront);
2321                }
2322        }
2323
2324        mBvhStats.mGeometryRatio = mGeometrySize / (float)GetNumLeaves();
2325        mBvhStats.mTriangleRatio = mBvhStats.mTriangles / (float)GetNumLeaves();
2326}
2327
2328
2329void Bvh::PrintBvhStats() const
2330{
2331        //OUT1("triangle bvh surface " << mBvhStats.mBoundsLeafSA);
2332        //OUT1("triangle bvh volume " << mBvhStats.mBoundsLeafVol);
2333
2334        OUT1("bvh stats:");
2335        OUT1("interiorNodesSA = " << mBvhStats.mInteriorSA / mRoot->mBox.getSurface());
2336        OUT1("leafNodesSA = " << mBvhStats.mLeafSA / mRoot->mBox.getSurface());
2337        OUT1("interiorNodesVolume = " << mBvhStats.mInteriorVol / mRoot->mBox.getVolume());
2338        OUT1("leafNodesVolume = " << mBvhStats.mLeafVol / mRoot->mBox.getVolume() << "\n");
2339
2340        OUT1("boundsInteriorNodesSA = " << mBvhStats.mBoundsInteriorSA / mBvhStats.mLeafSA);
2341        OUT1("boundsLeafNodesSA = " << mBvhStats.mBoundsLeafSA / mBvhStats.mLeafSA);
2342        OUT1("boundsInteriorNodesVolume = " << mBvhStats.mBoundsInteriorVol / mBvhStats.mLeafVol);
2343        OUT1("boundsLeafNodesVolume = " << mBvhStats.mBoundsLeafVol / mBvhStats.mLeafVol << "\n");
2344
2345        OUT1("boundsLeaves: " <<  (float)mBvhStats.mBoundsLeavesCount / (float)GetNumLeaves() << "\n");
2346        OUT1("geometry per leaf: " <<  mBvhStats.mGeometryRatio);
2347        OUT1("triangles per leaf: " <<  mBvhStats.mTriangleRatio);
2348        OUT1("");
2349}
2350
2351
2352static void RenderBoxForViz(const BoundingBox &box)
2353{
2354        glBegin(GL_LINE_LOOP);
2355        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2356        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2357        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2358        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2359        glEnd();
2360
2361        glBegin(GL_LINE_LOOP);
2362        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2363        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2364        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2365        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2366        glEnd();
2367
2368        glBegin(GL_LINE_LOOP);
2369        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2370        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2371        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2372        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2373        glEnd();
2374
2375        glBegin(GL_LINE_LOOP);
2376        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2377        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2378        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2379        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2380        glEnd();
2381
2382        glBegin(GL_LINE_LOOP);
2383        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2384        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getLowerPtr()->z);
2385        glVertex3d(box.getUpperPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2386        glVertex3d(box.getLowerPtr()->x, box.getLowerPtr()->y, box.getUpperPtr()->z);
2387        glEnd();
2388
2389        glBegin(GL_LINE_LOOP);
2390        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2391        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getLowerPtr()->z);
2392        glVertex3d(box.getUpperPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2393        glVertex3d(box.getLowerPtr()->x, box.getUpperPtr()->y, box.getUpperPtr()->z);
2394
2395        glEnd();
2396}
2397
2398
2399void Bvh::RenderBoundingBoxesForViz(const int mode)
2400{
2401        BvhLeafContainer leaves;
2402        leaves.reserve(mRoot->GetNumLeaves());
2403
2404        CollectLeaves(mRoot, leaves);
2405
2406        BvhLeafContainer::const_iterator it, it_end = leaves.end();
2407
2408        for (it = leaves.begin(); it != it_end; ++ it)
2409        {
2410                BvhLeaf *leaf = *it;
2411
2412                if ((mode == 0) || (mode == 2))
2413                {
2414                        glColor3f(1.0f, 1.0f, 1.0f);
2415            RenderBoxForViz(leaf->GetBox());
2416                }
2417               
2418                if ((mode == 1) || (mode == 2))
2419                {
2420                        glColor3f(1.0f, 0, 0);
2421                        for (int i = 0; i < leaf->mNumTestNodes; ++ i)
2422                        {
2423                                RenderBoxForViz(mTestNodes[leaf->mTestNodesIdx + i]->GetBox());
2424                        }
2425                }
2426        }
2427}
2428
2429
2430int Bvh::CountTriangles(BvhNode *node) const
2431{
2432        int numTriangles = 0;
2433
2434        for (int i = node->mFirst; i <= node->mLast; ++ i)
2435        {
2436                numTriangles += mGeometry[i]->mNumTriangles;
2437        }
2438
2439        return numTriangles;
2440}
2441
2442
2443float Bvh::GetGeometryArea(BvhNode *node) const
2444{
2445        return node->mArea;
2446}
2447
2448
2449float Bvh::GetAvgDepth() const
2450{
2451        return mAvgDepth;
2452}
2453
2454
2455static float GetNodePriority(RenderableHierarchyNode *node)
2456{
2457        if (node->IsLeaf())
2458                return 0.0f;
2459
2460        float result;
2461
2462        if (node->GetType() == BVH_NODE)
2463        {
2464                BvhInterior *interior = static_cast<BvhInterior *>(node);
2465               
2466                // evaluate the priority of this node
2467                const float correctionFactor = 0.0f;
2468                //  1.0f*interior->box.FaceArea(node->axis);
2469
2470                result =
2471                        interior->GetBox().getSurface() -
2472                        (interior->GetBack()->GetBox().getSurface() + interior->GetFront()->GetBox().getSurface()) +
2473                        correctionFactor;
2474        }
2475        else
2476        {
2477                TriangleBvhInterior *interior = static_cast<TriangleBvhInterior *>(node);
2478               
2479                // evaluate the priority of this node
2480                const float correctionFactor = 0.0f;
2481                //  1.0f*interior->box.FaceArea(node->axis);
2482
2483                result =
2484                        interior->GetBox().getSurface() -
2485                        (interior->GetBack()->GetBox().getSurface() + interior->GetFront()->GetBox().getSurface()) +
2486                        correctionFactor;
2487        }
2488
2489        return result;
2490}
2491
2492
2493struct NodeEntry
2494{
2495        NodeEntry(RenderableHierarchyNode *node, float p): mNode(node), mPriority(p)
2496        {}
2497
2498        RenderableHierarchyNode *mNode;
2499        float mPriority;
2500};
2501
2502
2503bool operator<(const NodeEntry &a, const NodeEntry &b)
2504{
2505        return a.mPriority < b.mPriority;
2506}
2507
2508
2509void Bvh::CollectBestNodes(RenderableHierarchyNode *node, HierarchyNodeContainer &nodes)
2510{
2511        int maxNodes = 32;
2512        priority_queue<NodeEntry> nodeStack;
2513
2514        nodeStack.push(NodeEntry(node, GetNodePriority(node)));
2515        nodes.clear();
2516
2517        float SA = node->GetBox().getSurface();
2518        float saThreshold = 1.1f * SA;
2519        int numNodes = 1;
2520        OUT1(numNodes << " " << SA);
2521
2522        while (!nodeStack.empty() &&
2523                int(nodes.size() + nodeStack.size()) < maxNodes)
2524        {
2525                NodeEntry entry = nodeStack.top();
2526                nodeStack.pop();
2527
2528                RenderableHierarchyNode *current = entry.mNode;
2529
2530                if (current->IsLeaf())
2531                {
2532                        // check if there further subdivision on triangle level
2533                        if ((current->GetType() == BVH_NODE) && (((BvhLeaf *)current)->mTriangleBvh->GetNumNodes() > 1))
2534                        {
2535                                // push back the root of the local bvh
2536                                nodeStack.push(NodeEntry(((BvhLeaf *)current)->mTriangleBvh->GetRoot(), entry.mPriority));
2537                        }
2538                        else // terminate traversal
2539                        {
2540                                nodes.push_back(current);
2541                        }
2542                }
2543                else // interior node
2544                {
2545                        // surface area of child nodes
2546                        SA -= entry.mPriority;
2547               
2548                        // finish the search if we have too much fillrate increase
2549                        if (SA > saThreshold)
2550                        {
2551                                OUT1("break at " << SA << " > " << saThreshold);
2552                                nodes.push_back(current);
2553                        }
2554                        else
2555                        {
2556                                ++ numNodes;
2557
2558                                OUT1(numNodes << " " << SA << " " << entry.mPriority);
2559
2560                                if (current->GetType() == BVH_NODE)
2561                                {
2562                                        BvhInterior *interior = static_cast<BvhInterior *>(current);
2563
2564                                        nodeStack.push(NodeEntry(interior->GetBack(),
2565                                                GetNodePriority(interior->GetBack())));
2566                                        nodeStack.push(NodeEntry(interior->GetFront(),
2567                                                GetNodePriority(interior->GetFront())));
2568                                }
2569                                else
2570                                {
2571                                        TriangleBvhInterior *interior = static_cast<TriangleBvhInterior *>(current);
2572
2573                                        nodeStack.push(NodeEntry(interior->GetBack(),
2574                                                GetNodePriority(interior->GetBack())));
2575                                        nodeStack.push(NodeEntry(interior->GetFront(),
2576                                                GetNodePriority(interior->GetFront())));
2577                                }
2578                        }
2579                }
2580        }
2581
2582        while (!nodeStack.empty())
2583        {
2584                NodeEntry entry = nodeStack.top();
2585       
2586                nodeStack.pop();
2587                RenderableHierarchyNode *current = entry.mNode;
2588                nodes.push_back(current);
2589        }
2590}
2591
2592#endif
Note: See TracBrowser for help on using the repository browser.