source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.cpp @ 3127

Revision 3127, 35.1 KB checked in by mattausch, 16 years ago (diff)
Line 
1#include "Bvh.h"
2#include "Camera.h"
3#include "Plane3.h"
4#include "glInterface.h"
5#include "Triangle3.h"
6#include "SceneEntity.h"
7#include "Geometry.h"
8#include "RenderState.h"
9#include "Material.h"
10#include "gzstream.h"
11
12#include <queue>
13#include <stack>
14#include <fstream>
15#include <iostream>
16#include <iomanip>
17
18
19#ifdef _CRT_SET
20        #define _CRTDBG_MAP_ALLOC
21        #include <stdlib.h>
22        #include <crtdbg.h>
23
24        // redefine new operator
25        #define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
26        #define new DEBUG_NEW
27#endif
28
29#define INVALID_TEST ((unsigned int)-1)
30
31using namespace std;
32
33
34namespace CHCDemoEngine
35{
36
37int BvhNode::sCurrentState = 0;
38
39
40/*
413 x---------x 2
42  |\         \
43  | \         \
44  |  \         \
45  |     4 x---------x 5
46  |   |         |
470 x   |     x 1 |
48   \  |         |
49    \ |         |
50     \|         |
51        7 x---------x 6             
52*/
53
54static unsigned int sIndices[] =       
55{7, // degenerated
56 7, 6, 4, 5, 3, 2, 0, 1,
57 1, 4, // degenerated
58 4, 3, 7, 0, 6, 1, 5, 2,
59 2 // degenerated
60};
61
62
63const static int sNumIndicesPerBox = 20;
64
65/*      Order of vertices
66        0 = (0, 0, 0)
67        1 = (1, 0, 0)
68        2 = (1, 1, 0)
69        3 = (0, 1, 0)
70        4 = (0, 1, 1)
71        5 = (1, 1, 1)
72        6 = (1, 0, 1)
73        7 = (0, 0, 1)
74*/
75
76static Plane3 sNearPlane;
77static float sNear;
78static Frustum sFrustum;
79
80/// these values are valid for all nodes
81static int sClipPlaneAABBVertexIndices[12];
82
83#define ALIGN_INDICES
84
85
86BvhNode::BvhNode(BvhNode *parent):
87mParent(parent),
88mAxis(-1),
89mDepth(0),
90mFirst(-1),
91mLast(-1),
92mNumTestNodes(1),
93mTestNodesIdx(-1),
94mIndicesPtr(-1),
95mId(0),
96mIsMaxDepthForVirtualLeaf(false),
97mIsVirtualLeaf(false)
98{
99        for (int i = 0; i < NUM_STATES; ++ i)
100        {
101                mPlaneMask[i] = 0;
102                mPreferredPlane[i]= 0;
103                mLastRenderedFrame[i] = -1;
104        }
105}
106
107
108BvhNode::~BvhNode()
109{
110}
111
112
113void BvhNode::ResetVisibility()
114{
115        for (int i = 0; i < NUM_STATES; ++ i)
116        {
117                mVisibility[i].Reset();
118                mLastRenderedFrame[i] = -1;
119                mPlaneMask[i] = 0;
120                mPreferredPlane[i]= 0;
121        }
122}
123
124
125void BvhNode::VisibilityInfo::Reset()
126{
127        mIsVisible = false;
128        mAssumedVisibleFrameId = 0;
129        mLastVisitedFrame = -1;
130        mTimesInvisible = 0;
131        mIsFrustumCulled = false;
132        mIsNew = true;
133        mLastQueriedFrame = -1;
134}
135
136
137BvhInterior::~BvhInterior()
138{
139        DEL_PTR(mBack);
140        DEL_PTR(mFront);
141}
142
143
144BvhLeaf::~BvhLeaf()
145{
146}
147
148
149/**********************************************************/
150/*                class Bvh implementation                */
151/**********************************************************/
152
153
154
155inline AxisAlignedBox3 ComputeBoundingBox(SceneEntity **entities, int numEntities)
156{
157        AxisAlignedBox3 box;
158       
159        if (!numEntities)
160        {       // no box=> just initialize
161                box.Initialize();
162        }
163        else
164        {
165                box = entities[0]->GetWorldBoundingBox();
166
167                for (int i = 1; i < numEntities; ++ i)
168                {
169                        box.Include(entities[i]->GetWorldBoundingBox());
170                }
171        }
172
173        return box;
174}
175
176
177Bvh::Bvh()
178{
179        Init();
180}
181
182
183Bvh::Bvh(const SceneEntityContainer &staticEntities,
184                 const SceneEntityContainer &dynamicEntities)
185{
186        Init();
187
188        mGeometrySize = staticEntities.size() + dynamicEntities.size();
189        mGeometry = new SceneEntity*[mGeometrySize];
190
191        mStaticGeometrySize = staticEntities.size();
192        mDynamicGeometrySize = dynamicEntities.size();
193
194        for (size_t i = 0; i < mStaticGeometrySize; ++ i)
195        {
196                mGeometry[i] = staticEntities[i];
197        }
198
199        for (size_t i = 0; i < mDynamicGeometrySize; ++ i)
200        {
201                mGeometry[mStaticGeometrySize + i] = dynamicEntities[i];
202        }
203
204        cout << "max depth for testing children" << mMaxDepthForTestingChildren << endl;
205}
206
207
208Bvh::Bvh(const SceneEntityContainer &staticEntities,
209                 const SceneEntityContainer &dynamicEntities,
210                 int maxDepthForTestingChildren)
211{
212        Init();
213
214        mGeometrySize = staticEntities.size() + dynamicEntities.size();
215        mGeometry = new SceneEntity*[mGeometrySize];
216
217        mStaticGeometrySize = staticEntities.size();
218        mDynamicGeometrySize = dynamicEntities.size();
219
220        for (size_t i = 0; i < mStaticGeometrySize; ++ i)
221        {
222                mGeometry[i] = staticEntities[i];
223        }
224
225        for (size_t i = 0; i < mDynamicGeometrySize; ++ i)
226        {
227                mGeometry[mStaticGeometrySize + i] = dynamicEntities[i];
228        }
229
230        mMaxDepthForTestingChildren = maxDepthForTestingChildren;
231        cout << "max depth for testing children" << mMaxDepthForTestingChildren << endl;
232}
233
234
235Bvh::~Bvh()
236{
237        DEL_ARRAY_PTR(mVertices);
238        DEL_ARRAY_PTR(mIndices);
239        DEL_ARRAY_PTR(mTestIndices);
240        DEL_ARRAY_PTR(mGeometry);
241
242        if (mRoot) delete mRoot;
243        // delete vbo
244        glDeleteBuffersARB(1, &mVboId);
245}
246
247
248void Bvh::Init()
249{
250        mStaticRoot = NULL;
251        mDynamicRoot = NULL;
252        mRoot = NULL;
253
254        mVertices = NULL;
255        mIndices = NULL;
256        mTestIndices = NULL;
257        mCurrentIndicesPtr = 0;
258        mNumNodes = 0;
259       
260        // nodes are tested using the subnodes from 3 levels below
261        mMaxDepthForTestingChildren = 3;
262        mMaxDepthForTestingChildren = 0;
263        //mMaxDepthForTestingChildren = 4;
264
265        // the ratio of area between node and subnodes where
266        // testing the subnodes as proxy is still considered feasable
267        mAreaRatioThreshold = 2.0f;
268        //mAreaRatioThreshold = 1.4f;
269
270        mVboId = -1;
271
272        mMaxDepthForDynamicBranch = 10;
273}
274
275
276
277//////////////////////
278//-- functions that are used during the main traversal
279
280void Bvh::PullUpLastVisited(BvhNode *node, int frameId) const
281{               
282        BvhNode *parent = node->GetParent();
283
284        while (parent && (parent->GetLastVisitedFrame() != frameId))
285        {
286                parent->SetLastVisitedFrame(frameId);
287                parent = parent->GetParent();
288        }
289}
290
291
292void Bvh::MakeParentsVisible(BvhNode *node)
293{
294        BvhNode *parent = node->GetParent();
295
296        while (parent && (!parent->IsVisible()))
297        {
298                parent->SetVisible(true);
299                parent = parent->GetParent();
300        }
301}
302
303
304////////////////////////////////
305
306void Bvh::CollectLeaves(BvhNode *node, BvhLeafContainer &leaves)
307{
308        stack<BvhNode *> tStack;
309        tStack.push(node);
310
311        while (!tStack.empty())
312        {
313                BvhNode *node = tStack.top();
314
315                tStack.pop();
316
317                if (!node->IsLeaf())
318                {
319                        BvhInterior *interior = static_cast<BvhInterior *>(node);
320
321                        tStack.push(interior->mFront);
322                        tStack.push(interior->mBack);
323                }
324                else
325                {
326                        leaves.push_back(static_cast<BvhLeaf *>(node));
327                }
328        }
329}
330
331
332void Bvh::CollectNodes(BvhNode *node, BvhNodeContainer &nodes)
333{
334        stack<BvhNode *> tStack;
335
336        tStack.push(node);
337
338        while (!tStack.empty())
339        {
340                BvhNode *node = tStack.top();
341                tStack.pop();
342
343                nodes.push_back(node);
344
345                if (!node->IsLeaf())
346                {
347                        BvhInterior *interior = static_cast<BvhInterior *>(node);
348
349                        tStack.push(interior->mFront);
350                        tStack.push(interior->mBack);
351                }
352        }
353}
354
355
356typedef pair<BvhNode *, int> tPair;
357
358void Bvh::CollectNodes(BvhNode *root, BvhNodeContainer &nodes, int depth)
359{
360        stack<tPair> tStack;
361        tStack.push(tPair(root, 0));
362
363        while (!tStack.empty())
364        {
365                BvhNode *node = tStack.top().first;
366                const int d = tStack.top().second;
367
368                tStack.pop();
369
370                // found node in specified depth => take this node
371                if ((d == depth) || (node->IsLeaf()))
372                {
373                        nodes.push_back(node);
374                }
375                else
376                {
377                        BvhInterior *interior = static_cast<BvhInterior *>(node);
378
379                        tStack.push(tPair(interior->mFront, d + 1));
380                        tStack.push(tPair(interior->mBack, d + 1));
381                }
382        }
383}
384
385
386SceneEntity **Bvh::GetGeometry(BvhNode *node, int &geometrySize) const
387{
388        geometrySize = node->CountPrimitives();
389        return mGeometry + node->mFirst;
390}
391
392
393bool Bvh::TestPlane(BvhNode *node, int i, bool &bIntersect)
394{
395        // do the test only if necessary
396        if (!(node->mPlaneMask[BvhNode::sCurrentState] & (1 << i)))
397        {
398                return true;
399        }
400
401
402        ////////
403        //-- test the n-vertex
404               
405        if ((node->mBox.GetDistance(sClipPlaneAABBVertexIndices[i * 2 + 0], sFrustum.mClipPlanes[i]) > 0.0f))
406        {
407                // outside
408                node->mPreferredPlane[BvhNode::sCurrentState] = i;
409                return false;
410        }
411
412        ////////////
413        //-- test the p-vertex
414
415        if (node->mBox.GetDistance(sClipPlaneAABBVertexIndices[i * 2 + 1], sFrustum.mClipPlanes[i]) <= 0.0f)
416        {
417                // completely inside: children don't need to check against this plane no more
418                node->mPlaneMask[BvhNode::sCurrentState] ^= 1 << i;
419        }
420        else
421        {
422                bIntersect = true;
423        }
424       
425        return true;
426}
427
428
429int     Bvh::IsWithinViewFrustum(BvhNode *node)
430{
431        bool bIntersect = false;
432
433        if (node->GetParent())
434                node->mPlaneMask[BvhNode::sCurrentState] = node->GetParent()->mPlaneMask[BvhNode::sCurrentState];
435
436        ////////
437        //-- apply frustum culling for the planes with index mPreferredPlane to 6
438
439        for (int i = node->mPreferredPlane[BvhNode::sCurrentState]; i < 6; ++ i)
440                if (!TestPlane(node, i, bIntersect)) return 0;
441       
442
443        //////////
444        //-- apply frustum culling for the planes with index 0 to mPreferredPlane
445
446        for (int i = 0; i < node->mPreferredPlane[BvhNode::sCurrentState]; ++ i)
447                if (!TestPlane(node, i, bIntersect)) return 0;
448       
449        return bIntersect ? -1 : 1;
450}
451
452
453static void CalcNPVertexIndices(const Frustum &frustum, int *indices)
454{
455        for (int i = 0; i < 6; ++ i)
456        {
457                // n-vertex
458                indices[i * 2 + 0] = AxisAlignedBox3::GetIndexNearestVertex(frustum.mClipPlanes[i].mNormal);
459                // p-vertex
460                indices[i * 2 + 1] = AxisAlignedBox3::GetIndexFarthestVertex(frustum.mClipPlanes[i].mNormal);   
461        }
462}
463
464
465void Bvh::InitFrame(Camera *cam, RenderState *state)
466{
467        // = 0011 1111 which means that at the beginning, all six planes have to frustum culled
468        mRoot->mPlaneMask[BvhNode::sCurrentState] = 0x3f;
469
470        cam->CalcFrustum(sFrustum);
471        CalcNPVertexIndices(sFrustum, sClipPlaneAABBVertexIndices);
472
473        // store near plane
474        sNearPlane = Plane3(cam->GetDirection(), cam->GetPosition());
475        sNear = cam->GetNear();
476
477        // update dynamic part of the hierarchy
478        //if (!mDynamicEntities.empty())
479        if (mDynamicGeometrySize)
480        {
481                UpdateDynamicBranch(mDynamicRoot);
482                UpdateDynamicBounds(state);
483        }
484}
485
486
487void Bvh::UpdateDistance(BvhNode *node) const
488{
489        // q: should we use distance to center rather than the distance to the near plane?
490        // distance to near plane can also be used for checking near plane intersection
491        //node->mDistance = sNearPlane.Distance(node->GetBox().Center());
492        node->mDistance = node->GetBox().GetMinDistance(sNearPlane);
493}
494
495
496float Bvh::CalcMaxDistance(BvhNode *node) const
497{
498#if 1
499        return node->GetBox().GetMaxDistance(sNearPlane);
500
501#else
502        // use bounding boxes of geometry to determine max dist
503        float maxDist = .0f;
504
505        int geometrySize;
506        SceneEntity **entities = GetGeometry(node, geometrySize);
507
508        for (int i = 0; i < geometrySize; ++ i)
509        {
510                SceneEntity *ent = entities[i];
511                float dist = ent->GetWorldBoundingBox().GetMaxDistance(sNearPlane);
512
513                if (dist > maxDist) maxDist = dist;
514        }
515
516        return maxDist;
517#endif
518}
519
520
521void Bvh::RenderBounds(BvhNode *node, RenderState *state, bool useTightBounds)
522{
523        // hack: use dummy contayiner as wrapper in order to use multibox function
524        static BvhNodeContainer dummy(1);
525        dummy[0] = node;
526        RenderBounds(dummy, state, useTightBounds);
527}
528
529
530int Bvh::RenderBounds(const BvhNodeContainer &nodes,
531                                          RenderState *state,
532                                          bool useTightBounds)
533{
534        int renderedBoxes;
535
536        if (!useTightBounds)
537        {
538                // if not using tight bounds, rendering boxes in immediate mode
539                // is preferable to vertex arrays (less setup time)
540                BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
541                       
542                for (nit = nodes.begin(); nit != nit_end; ++ nit)
543                {
544                        RenderBoundingBoxImmediate((*nit)->GetBox());
545                }
546
547                renderedBoxes = (int)nodes.size();
548        }
549        else
550        {
551                renderedBoxes = PrepareBoundsWithDrawArrays(nodes);
552                RenderBoundsWithDrawArrays(renderedBoxes, state);
553        }
554
555        return renderedBoxes;
556}
557
558
559int Bvh::PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes)
560{
561        ///////////////////
562        //-- for the first time we come here => create vbo and indices
563
564        if (!mIndices)
565        {       
566                // create list of indices
567                CreateIndices();
568        }
569
570        if (mVboId == -1)
571        {       
572                // prepare the vbo
573                PrepareVertices();
574        }
575
576        ///////////////
577
578        int numNodes = 0;
579
580        BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
581
582        for (nit = nodes.begin(); nit != nit_end; ++ nit)
583        {
584                BvhNode *node = *nit;
585        const int numIndices = node->mNumTestNodes * sNumIndicesPerBox;
586               
587                // copy indices
588                memcpy(mIndices + numNodes * sNumIndicesPerBox,
589                           mTestIndices + node->mIndicesPtr,
590                           numIndices * sizeof(unsigned int));
591
592                numNodes += node->mNumTestNodes;
593        }
594
595        return numNodes;
596}
597
598
599void Bvh::RenderBoundsWithDrawArrays(int numNodes, RenderState *state)
600{
601        /////////
602        //-- Render the vbo
603
604        if (state->GetCurrentVboId() != mVboId)
605        {
606                glBindBufferARB(GL_ARRAY_BUFFER_ARB, mVboId);
607                // set the vertex pointer to the vertex buffer
608                glVertexPointer(3, GL_FLOAT, 0, (char *)NULL); 
609
610                state->SetCurrentVboId(mVboId);
611        }
612
613        // we do use the last or the first index (they are generate and only used to connect strips)
614        int numElements = numNodes * sNumIndicesPerBox - 1;
615        // don't render first degenerate index
616        glDrawElements(GL_TRIANGLE_STRIP, numElements, GL_UNSIGNED_INT, mIndices + 1);
617}
618
619
620void Bvh::CreateIndices()
621{
622        // collect bvh nodes
623        BvhNodeContainer nodes;
624        CollectNodes(mRoot, nodes);
625
626        cout << "creating new indices" << endl;
627
628        int numMaxIndices = 0;
629
630        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
631
632        for (lit = nodes.begin(); lit != lit_end; ++ lit)
633        {
634                int offset = (*lit)->mNumTestNodes * sNumIndicesPerBox;
635#ifdef ALIGN_INDICES
636                // align with 32 in order to speed up memcopy
637                offset = (offset / 32) * 32 + 32;
638#endif
639                numMaxIndices += offset;
640        }
641
642        cout << "creating global indices buffer" << endl;
643
644        if (mIndices) delete [] mIndices;
645        if (mTestIndices) delete [] mTestIndices;
646
647        // global buffer: create it once so we don't have
648        // to allocate memory from the chunks of the node
649        mIndices = new unsigned int[numMaxIndices];
650        // create new index buffer for the individual nodes
651        mTestIndices = new unsigned int[numMaxIndices];
652       
653        mCurrentIndicesPtr = 0;
654
655        for (lit = nodes.begin(); lit != lit_end; ++ lit)
656        {
657                BvhNode *node = *lit;
658               
659                // resize array
660                node->mIndicesPtr = mCurrentIndicesPtr;
661                int numIndices = 0;
662
663                // the bounding boxes of the test nodes are rendered instead of the node itself
664                // => store their indices
665                for (int i = 0; i < node->mNumTestNodes; ++ i, numIndices += sNumIndicesPerBox)
666                {
667                        BvhNode *testNode = mTestNodes[node->mTestNodesIdx + i];
668
669                        // add indices to root node
670                        for (int j = 0; j < sNumIndicesPerBox; ++ j)
671                        {
672                                mTestIndices[mCurrentIndicesPtr + numIndices + j] = sIndices[j] + testNode->GetId() * 8;
673                        }
674                }
675
676                // align with 32
677#ifdef ALIGN_INDICES
678                const int offset = (numIndices / 32) * 32 + 32;
679#else
680                const int offset = numIndices;
681#endif
682                mCurrentIndicesPtr += offset;
683        }
684}
685
686
687void Bvh::ComputeIds()
688{
689        // collect all nodes
690        BvhNodeContainer nodes;
691        //CollectNodes(mRoot, nodes);
692        // first collect dynamic nodes so we make sure that they are in the beginning
693        CollectNodes(mDynamicRoot, nodes);
694        // then collect static nodes
695        CollectNodes(mStaticRoot, nodes);
696        // also add root
697        nodes.push_back(mRoot);
698
699        // assign ids to all nodes of the hierarchy
700        int i = 0;
701        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
702
703        for (lit = nodes.begin(); lit != lit_end; ++ lit, ++ i)
704        {
705                (*lit)->SetId(i);
706        }
707}
708
709
710void Bvh::PrepareVertices()
711{
712        // collect all nodes
713        BvhNodeContainer nodes;
714
715        nodes.reserve(GetNumNodes());
716        // first collect dynamic nodes so we make sure that they are in the beginning
717        CollectNodes(mDynamicRoot, nodes);
718        // then collect static nodes
719        CollectNodes(mStaticRoot, nodes);
720        // also add root
721        nodes.push_back(mRoot);
722
723        const unsigned int bufferSize = 8 * (int)nodes.size();
724        mVertices = new Vector3[bufferSize];
725       
726        int i = 0;
727       
728        // store bounding box vertices
729        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
730
731        for (lit = nodes.begin(); lit != lit_end; ++ lit, i += 8)
732        {
733                BvhNode *node = *lit;
734
735                for (int j = 0; j < 8; ++ j)
736                        (static_cast<Vector3 *>(mVertices))[node->GetId() * 8 + j] = node->GetBox().GetVertex(j);
737        }
738
739        glGenBuffersARB(1, &mVboId);
740        glBindBufferARB(GL_ARRAY_BUFFER_ARB, mVboId);
741        glVertexPointer(3, GL_FLOAT, 0, (char *)NULL);
742       
743        glBufferDataARB(GL_ARRAY_BUFFER_ARB,
744                            bufferSize * sizeof(Vector3),
745                            mVertices,
746                                        //GL_STATIC_DRAW_ARB);
747                                        GL_DYNAMIC_DRAW_ARB);
748
749        glBindBufferARB(GL_ARRAY_BUFFER_ARB, 0);
750
751        // data handled by graphics driver from now on
752        DEL_ARRAY_PTR(mVertices);
753
754        cout << "******** created vbos for tighter bounds *********" << endl;
755}
756
757
758void Bvh::UpdateDynamicBounds(RenderState *state)
759{
760        // vbos not created yet
761        if (mVboId == -1) return;
762
763        // collect all nodes
764        static BvhNodeContainer nodes;
765        nodes.clear();
766        //nodes.reserve(GetNumNodes());
767        CollectNodes(mDynamicRoot, nodes);
768
769        const unsigned int bufferSize = 8 * (int)nodes.size();
770        if (!mVertices) mVertices = new Vector3[bufferSize];
771       
772        int i = 0;
773       
774        // store bounding box vertices
775        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
776
777        for (lit = nodes.begin(); lit != lit_end; ++ lit, i += 8)
778        {
779                BvhNode *node = *lit;
780
781                for (int j = 0; j < 8; ++ j)
782                        (static_cast<Vector3 *>(mVertices))[node->GetId() * 8 + j] = node->GetBox().GetVertex(j);
783        }
784       
785        if (state->GetCurrentVboId() != mVboId)
786        {
787                glBindBufferARB(GL_ARRAY_BUFFER_ARB, mVboId);
788                // set the vertex pointer to the vertex buffer
789                glVertexPointer(3, GL_FLOAT, 0, (char *)NULL); 
790                state->SetCurrentVboId(mVboId);
791        }
792
793        glBufferSubDataARB(GL_ARRAY_BUFFER_ARB, 0,
794                                           bufferSize * sizeof(Vector3),
795                                           mVertices);
796}
797
798
799void Bvh::SetMaxDepthForTestingChildren(int maxDepth)
800{
801        if (maxDepth != mMaxDepthForTestingChildren)
802        {
803                mMaxDepthForTestingChildren = maxDepth;
804                RecomputeBounds();
805        }
806}
807
808
809void Bvh::SetAreaRatioThresholdForTestingChildren(float ratio)
810{
811        if (ratio != mAreaRatioThreshold)
812        {
813                mAreaRatioThreshold = ratio;
814                RecomputeBounds();
815        }
816}
817
818
819void Bvh::RecomputeBounds()
820{
821        // collect all nodes
822        BvhNodeContainer nodes;
823        CollectNodes(mRoot, nodes);
824
825        cout << "recomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren << endl;
826
827        int success = 0;
828        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
829
830        for (lit = nodes.begin(); lit != lit_end; ++ lit)
831        {
832                BvhNode *node = *lit;
833
834                // recreate list of nodes that will be queried as a proxy
835                if (CreateNodeRenderList(node))
836                        ++ success;
837        }
838
839        float p = 100.0f * (float)success / nodes.size();
840        cout << "created tighter bounds for " << p << " percent of the nodes" << endl;
841
842        // recreate indices used for indirect mode rendering
843        if (mIndices) CreateIndices();
844}
845
846       
847bool Bvh::CreateNodeRenderList(BvhNode *node)
848{
849        BvhNodeContainer children;
850
851        // collect nodes that will be tested instead of the leaf node
852        // in order to get a tighter bounding box test
853        CollectNodes(node, children, mMaxDepthForTestingChildren);
854       
855
856        // using the tighter bounds is not feasable in case
857        // that the tighter bounds represent nearly the same projected area
858        // as the old bounding box. Test this property using either
859        // volume or area heuristics
860
861        float vol = 0;
862        float area = 0;
863
864        BvhNodeContainer::const_iterator cit;
865
866        for (cit = children.begin(); cit != children.end(); ++ cit)
867                area += (*cit)->GetBox().SurfaceArea();
868
869        const float areaRatio = area / node->GetBox().SurfaceArea();
870       
871        bool success;
872
873        if (areaRatio < mAreaRatioThreshold)
874                success = true;
875        else
876        {
877                // hack: only store node itself
878                children.clear();
879                children.push_back(node);
880
881                success = false;
882        }
883
884        // the new test nodes are added at the end of the vector
885        node->mTestNodesIdx = (int)mTestNodes.size();
886
887        // use the collected nodes as proxy for the occlusion tests
888        for (cit = children.begin(); cit != children.end(); ++ cit)
889        {
890                BvhNode *child = *cit;
891                mTestNodes.push_back(child);
892        }
893
894        node->mNumTestNodes = (int)children.size();
895
896        return success;
897}
898
899
900void Bvh::ResetNodeClassifications()
901{
902        BvhNodeContainer nodes;
903
904        nodes.reserve(GetNumNodes());
905        CollectNodes(mRoot, nodes);
906
907        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
908
909        for (lit = nodes.begin(); lit != lit_end; ++ lit)
910        {
911                (*lit)->ResetVisibility();
912        }
913}
914
915
916void Bvh::ComputeBvhStats(BvhNode *root, BvhStats &bvhStats)
917{
918        bvhStats.Reset();
919        std::stack<BvhNode *> nodeStack;
920        nodeStack.push(root);
921
922        int numVirtualLeaves = 0;
923        int numGeometry = 0;
924
925        while (!nodeStack.empty())
926        {
927                BvhNode *node = nodeStack.top();
928                nodeStack.pop();
929
930                if (node->IsVirtualLeaf())
931                {
932                        ++ numVirtualLeaves;
933                        numGeometry += node->CountPrimitives();
934
935                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
936
937                        bvhStats.mTriangles += CountTriangles(leaf);
938                        bvhStats.mLeafSA += leaf->mBox.SurfaceArea();
939                        bvhStats.mLeafVol += leaf->mBox.GetVolume();
940                }
941                else
942                {
943                        bvhStats.mInteriorSA += node->mBox.SurfaceArea();
944                        bvhStats.mInteriorVol += node->mBox.GetVolume();
945
946                        BvhInterior *interior = static_cast<BvhInterior *>(node);
947                       
948                        nodeStack.push(interior->mBack);
949                        nodeStack.push(interior->mFront);
950                }
951        }
952
953        bvhStats.mGeometryRatio = (float)numGeometry / numVirtualLeaves;
954        bvhStats.mTriangleRatio = (float)bvhStats.mTriangles / numVirtualLeaves;
955        bvhStats.mLeaves = numVirtualLeaves;
956}
957
958
959void Bvh::PrintBvhStats(const BvhStats &bvhStats) const
960{
961        cout << "\n============ BVH statistics =============" << endl;
962        cout << "interiorNodesSA = " << bvhStats.mInteriorSA / mRoot->mBox.SurfaceArea() << endl;
963        cout << "leafNodesSA = " << bvhStats.mLeafSA / mRoot->mBox.SurfaceArea() << endl;
964        cout << "interiorNodesVolume = " << bvhStats.mInteriorVol / mRoot->mBox.GetVolume() << endl;
965        cout << "leafNodesVolume = " << bvhStats.mLeafVol / mRoot->mBox.GetVolume() << endl;
966
967        cout << "geometry per leaf: " << bvhStats.mGeometryRatio << endl;
968        cout << "triangles per leaf: " << bvhStats.mTriangleRatio << endl;
969        cout << "===========================================" << endl << endl;
970}
971
972
973int Bvh::CountTriangles(BvhNode *node) const
974{
975        int numTriangles = 0;
976
977        for (int i = node->mFirst; i <= node->mLast; ++ i)
978        {
979                numTriangles += mGeometry[i]->CountNumTriangles(0);
980        }
981
982        return numTriangles;
983}
984
985
986float Bvh::GetArea(BvhNode *node) const
987{
988        return node->mArea;
989}
990
991
992void Bvh::UpdateNumLeaves(BvhNode *node) const
993{
994        if (node->IsLeaf())
995        {
996                node->mNumLeaves = 1;
997        }
998        else
999        {
1000                BvhNode *f = static_cast<BvhInterior *>(node)->GetFront();
1001                BvhNode *b = static_cast<BvhInterior *>(node)->GetBack();
1002
1003                UpdateNumLeaves(f);
1004                UpdateNumLeaves(b);
1005
1006                node->mNumLeaves = f->mNumLeaves + b->mNumLeaves;
1007        }
1008}
1009
1010
1011void Bvh::CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves)
1012{
1013        stack<BvhNode *> tStack;
1014        tStack.push(node);
1015
1016        while (!tStack.empty())
1017        {
1018                BvhNode *node = tStack.top();
1019                tStack.pop();
1020
1021                if (node->mIsVirtualLeaf)
1022                {
1023                        leaves.push_back(node);
1024                }
1025                else if (!node->IsLeaf())
1026                {
1027                        BvhInterior *interior = static_cast<BvhInterior *>(node);
1028
1029                        tStack.push(interior->mFront);
1030                        tStack.push(interior->mBack);
1031                }
1032        }
1033}
1034
1035
1036void Bvh::SetVirtualLeaves(int numTriangles)
1037{
1038        // first invalidate old virtual leaves
1039        BvhNodeContainer leaves;
1040        CollectVirtualLeaves(mRoot, leaves);
1041
1042        BvhNodeContainer::const_iterator bit, bit_end = leaves.end();
1043
1044        for (bit = leaves.begin(); bit != bit_end; ++ bit)
1045        {
1046                (*bit)->mIsVirtualLeaf = false;
1047        }
1048
1049        mNumVirtualNodes = 0;
1050        // assign new virtual leaves based on specified #triangles per leaf
1051        std::stack<BvhNode *> nodeStack;
1052        nodeStack.push(mRoot);
1053
1054        while (!nodeStack.empty())
1055        {
1056                BvhNode *node = nodeStack.top();
1057                nodeStack.pop();
1058
1059                ++ mNumVirtualNodes;
1060
1061                if (node->IsLeaf())
1062                {
1063                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
1064                        leaf->mIsVirtualLeaf = true;
1065                }
1066                else
1067                {
1068                        BvhInterior *interior = static_cast<BvhInterior *>(node);
1069
1070                        BvhNode *f = interior->mFront;
1071                        BvhNode *b = interior->mBack;
1072
1073                        if (node->mIsMaxDepthForVirtualLeaf ||
1074                                (CountTriangles(node) <= numTriangles))
1075                        {
1076                                 node->mIsVirtualLeaf = true;
1077                        }
1078                        else
1079                        {
1080                                nodeStack.push(interior->mBack);
1081                                nodeStack.push(interior->mFront);
1082                        }
1083                }
1084        }
1085
1086        /// Reset the node states
1087        ResetNodeClassifications();
1088}
1089
1090
1091void Bvh::ComputeMaxDepthForVirtualLeaves()
1092{
1093        // We initialize the maximal depth for virtual leaves
1094        // of this bvh, i.e., the nodes that are used as
1095        // leaves of the hierarchy during traversal.
1096
1097        // Initially they are set either
1098        // a) to the real leaves of the hierarchy or
1099        // b) the point where the subdivision on object level ends
1100        // and the subsequent nodes are just used to provide tighter bounds
1101        // (see article for the notations)
1102
1103        std::stack<BvhNode *> nodeStack;
1104        nodeStack.push(mRoot);
1105
1106        while (!nodeStack.empty())
1107        {
1108                BvhNode *node = nodeStack.top();
1109                nodeStack.pop();
1110
1111                if (node->IsLeaf())
1112                {
1113                        node->mIsMaxDepthForVirtualLeaf = true;
1114                }
1115                else
1116                {
1117                        BvhInterior *interior = static_cast<BvhInterior *>(node);
1118
1119                        BvhNode *f = interior->mFront;
1120                        BvhNode *b = interior->mBack;
1121
1122                        if ((f->mFirst == b->mFirst) && (f->mLast == b->mLast))
1123                        {
1124                                // point reached where beyond there would be no further reduction
1125                                // as both subtrees contain the same objects => stop here
1126                                // The tree beyond the current node is used to describe
1127                                // tighter bounds on the geometry contained  in it
1128                                node->mIsMaxDepthForVirtualLeaf = true;
1129                        }
1130                        else
1131                        {
1132                                nodeStack.push(f);
1133                                nodeStack.push(b);
1134                        }
1135                }
1136        }
1137}
1138
1139
1140// this function must be called once after hierarchy creation
1141void Bvh::PostProcess()
1142{
1143        CreateRoot();
1144
1145        ComputeMaxDepthForVirtualLeaves();
1146        // set virtual leaves for specified number of triangles
1147        SetVirtualLeaves(INITIAL_TRIANGLES_PER_VIRTUAL_LEAVES);
1148        /// for each node compute the number of leaves under this node
1149        UpdateNumLeaves(mRoot);
1150        // compute new ids
1151        ComputeIds();
1152        // specify bounds for occlusion tests
1153        RecomputeBounds();
1154
1155        mBox = mRoot->GetBox();
1156
1157        // compute and print stats
1158        ComputeBvhStats(mRoot, mBvhStats);
1159        PrintBvhStats(mBvhStats);
1160
1161        if (mDynamicGeometrySize)
1162        {
1163                BvhStats bvhStats;
1164                ComputeBvhStats(mDynamicRoot, bvhStats);
1165
1166                cout << "\n=========== Dynamic BVH statistics: =========" << endl;
1167                cout << "leaves = " << bvhStats.mLeaves << endl;
1168                cout << "interiorNodesSA = " << bvhStats.mInteriorSA << endl;
1169                cout << "leafNodesSA = " << bvhStats.mLeafSA << endl;
1170                cout << "interiorNodesVolume = " << bvhStats.mInteriorVol  << endl;
1171                cout << "leafNodesVolume = " << bvhStats.mLeafVol << endl;
1172
1173                cout << "geometry per leaf: " << bvhStats.mGeometryRatio << endl;
1174                cout << "triangles per leaf: " << bvhStats.mTriangleRatio << endl;
1175                cout << "=============================================" << endl << endl;
1176        }
1177}
1178
1179
1180void Bvh::RenderBoundingBoxImmediate(const AxisAlignedBox3 &box)
1181{
1182        const Vector3 l = box.Min();
1183        const Vector3 u = box.Max();
1184
1185        ///////////
1186        //-- render AABB as triangle strips
1187
1188        glBegin(GL_TRIANGLE_STRIP);
1189
1190        // render first half of AABB
1191        glVertex3f(l.x, l.y, u.z);
1192        glVertex3f(u.x, l.y, u.z);
1193        glVertex3f(l.x, u.y, u.z);
1194        glVertex3f(u.x, u.y, u.z);
1195        glVertex3f(l.x, u.y, l.z);
1196        glVertex3f(u.x, u.y, l.z);
1197        glVertex3f(l.x, l.y, l.z);
1198        glVertex3f(u.x, l.y, l.z);
1199
1200        glPrimitiveRestartNV();
1201
1202        // render second half of AABB
1203        glVertex3f(l.x, u.y, u.z);
1204        glVertex3f(l.x, u.y, l.z);
1205        glVertex3f(l.x, l.y, u.z);
1206        glVertex3f(l.x, l.y, l.z);
1207        glVertex3f(u.x, l.y, u.z);
1208        glVertex3f(u.x, l.y, l.z);
1209        glVertex3f(u.x, u.y, u.z);
1210        glVertex3f(u.x, u.y, l.z);
1211
1212        glEnd();
1213}
1214
1215
1216static void RenderBoxForViz(const AxisAlignedBox3 &box)
1217{
1218        glBegin(GL_LINE_LOOP);
1219        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1220        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1221        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1222        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1223        glEnd();
1224
1225        glBegin(GL_LINE_LOOP);
1226        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1227        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1228        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1229        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1230        glEnd();
1231
1232        glBegin(GL_LINE_LOOP);
1233        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1234        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1235        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1236        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1237        glEnd();
1238
1239        glBegin(GL_LINE_LOOP);
1240        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1241        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1242        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1243        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1244        glEnd();
1245
1246        glBegin(GL_LINE_LOOP);
1247        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1248        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1249        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1250        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1251        glEnd();
1252
1253        glBegin(GL_LINE_LOOP);
1254        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1255        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1256        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1257        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1258
1259        glEnd();
1260}
1261
1262
1263static Technique GetVizTechnique()
1264{
1265        Technique tech;
1266        tech.Init();
1267
1268        //tech.SetLightingEnabled(false);
1269        //tech.SetDepthWriteEnabled(false);
1270
1271        tech.SetEmmisive(RgbaColor(1.0f, 1.0f, 1.0f, 1.0f));
1272        tech.SetDiffuse(RgbaColor(1.0f, 1.0f, 1.0f, 1.0f));
1273        tech.SetAmbient(RgbaColor(1.0f, 1.0f, 1.0f, 1.0f));
1274
1275        return tech;
1276}
1277
1278
1279void Bvh::RenderBoundsForViz(BvhNode *node,
1280                                                         RenderState *state,
1281                                                         bool useTightBounds)
1282{
1283        Technique *oldTech = state->GetState();
1284        // we set a simple material
1285        static Technique boxMat = GetVizTechnique();
1286        boxMat.Render(state);
1287
1288        if (!useTightBounds)
1289        {
1290                RenderBoxForViz(node->GetBox());
1291                /*glPolygonMode(GL_FRONT, GL_LINE);
1292                RenderBoundingBoxImmediate(node->GetBox());
1293                glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);*/
1294        }
1295        else
1296        {
1297                for (int i = 0; i < node->mNumTestNodes; ++ i)
1298                {
1299                        RenderBoxForViz(mTestNodes[node->mTestNodesIdx + i]->GetBox());
1300                }
1301        }
1302
1303        if (oldTech) oldTech->Render(state);
1304}
1305
1306
1307
1308////////////////////////
1309//-- functions for construction of the dynamic hierarchy
1310
1311int Bvh::SortTriangles(BvhLeaf *leaf,
1312                                           int axis,
1313                                           float position
1314                                           )
1315{
1316        int i = leaf->mFirst;
1317        int j = leaf->mLast;
1318
1319    while (1)
1320        {
1321                while (mGeometry[i]->GetWorldCenter()[axis] < position) ++ i;
1322                while (position < mGeometry[j]->GetWorldCenter()[axis]) -- j;
1323
1324                // sorting finished
1325                if (i >= j) break;
1326
1327                // swap entities
1328                swap(mGeometry[i], mGeometry[j]);
1329                       
1330                ++ i;
1331                -- j;
1332        }
1333
1334        return j;
1335}
1336
1337
1338int Bvh::SortTrianglesSpatialMedian(BvhLeaf *leaf,
1339                                                                        int axis
1340                                                                        )
1341{
1342        // spatial median
1343        float m = leaf->mBox.Center()[axis];
1344        return SortTriangles(leaf, axis, m);
1345}
1346
1347
1348BvhNode *Bvh::SubdivideLeaf(BvhLeaf *leaf,
1349                                                        int parentAxis
1350                                                        )
1351{
1352        if (TerminationCriteriaMet(leaf))
1353        {
1354                //cout << "leaf constructed:" << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
1355                return leaf;
1356        }
1357
1358        //const int axis = (parentAxis + 1) % 3;
1359        const int axis = leaf->mBox.MajorAxis();
1360
1361        const int scale = 20;
1362
1363        // position of the split in the partailly sorted array of triangles
1364        // corresponding to this leaf
1365        int split = -1;
1366        float pos = -1.0f;
1367       
1368        // Spatial median subdivision
1369        split = SortTrianglesSpatialMedian(leaf, axis);
1370        pos = leaf->mBox.Center()[axis];
1371       
1372        if (split == leaf->mLast)
1373        {
1374                // no split could be achieved => just halve number of objects
1375                split = (leaf->mLast - leaf->mFirst) / 2;
1376                cerr << "no reduction " << leaf->CountPrimitives() << " " << leaf->mFirst << " " << leaf->mLast << endl;
1377        }
1378
1379        // create two more nodes
1380        mNumNodes += 2;
1381        BvhInterior *parent = new BvhInterior(leaf->GetParent());
1382        parent->mFirst = leaf->mFirst;
1383        parent->mLast = leaf->mLast;
1384       
1385        parent->mAxis = axis;
1386        parent->mBox = leaf->mBox;
1387        parent->mDepth = leaf->mDepth;
1388
1389        BvhLeaf *front = new BvhLeaf(parent);
1390
1391        parent->mBack = leaf;
1392        parent->mFront = front;
1393               
1394        // now assign the triangles to the subnodes
1395        front->mFirst = split + 1;
1396        front->mLast = leaf->mLast;
1397        front->mDepth = leaf->mDepth + 1;
1398
1399        leaf->mLast = split;
1400        leaf->mDepth = front->mDepth;
1401        leaf->mParent = parent;
1402       
1403        front->mBox = ComputeBoundingBox(mGeometry + front->mFirst, front->CountPrimitives());
1404        leaf->mBox = ComputeBoundingBox(mGeometry + leaf->mFirst, leaf->CountPrimitives());
1405
1406        // recursively continue subdivision
1407        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis);
1408        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis);
1409       
1410        return parent;
1411}
1412
1413
1414bool Bvh::TerminationCriteriaMet(BvhLeaf *leaf) const
1415{
1416        const bool criteriaMet =
1417                (leaf->mDepth > mMaxDepthForDynamicBranch) ||
1418                (leaf->CountPrimitives() == 1);
1419
1420        return criteriaMet;
1421}
1422
1423
1424void Bvh::UpdateDynamicBranch(BvhNode *node)
1425{
1426        if (node->IsLeaf())
1427        {
1428                int numEntities;
1429                SceneEntity **entities = GetGeometry(node, numEntities);
1430
1431                node->mBox = ComputeBoundingBox(entities, numEntities);
1432                //cout << "box: " << node->mBox << endl;
1433        }
1434        else
1435        {
1436                BvhNode *f = static_cast<BvhInterior *>(node)->GetFront();
1437                BvhNode *b = static_cast<BvhInterior *>(node)->GetBack();
1438
1439                UpdateDynamicBranch(f);
1440                UpdateDynamicBranch(b);
1441
1442                node->mBox = f->mBox;
1443                node->mBox.Include(b->mBox);
1444        }
1445}
1446
1447
1448void Bvh::CreateDynamicBranch()
1449{
1450        // the bvh has two main branches
1451        // a static branch (the old root), and adynamic branch
1452        // we create a 'dynamic' leaf which basically is a container
1453        // for all dynamic objects underneath
1454
1455        // the bounding boxes of the dynamic tree must be updated
1456        // once each frame in order to be able to incorporate
1457        // the movements of the objects within
1458
1459        DEL_PTR(mDynamicRoot);
1460
1461        BvhLeaf *l = new BvhLeaf(mRoot);
1462        mDynamicRoot = l;
1463
1464        l->mBox = ComputeBoundingBox(mGeometry + mStaticGeometrySize, (int)mDynamicGeometrySize);
1465
1466        l->mFirst = (int)mStaticGeometrySize;
1467        l->mLast = (int)mGeometrySize - 1;
1468        l->mArea = l->mBox.SurfaceArea();
1469       
1470        cout << "updating dynamic branch " << l->mFirst << " " << l->mLast << endl;
1471
1472        if (mDynamicGeometrySize)
1473                mDynamicRoot = SubdivideLeaf(l, 0);
1474}
1475
1476
1477bool Bvh::IntersectsNearPlane(BvhNode *node) const
1478{
1479        // note: we have problems with large scale object penetrating the near plane
1480        // (e.g., objects in the distance which are always handled to be visible)
1481        // especially annoying is this problem when using the frustum
1482        // fitting on the visible objects for shadow mapping
1483        // but don't see how to solve this issue without using costly calculations
1484       
1485        // we stored the near plane distance => we can use it also here
1486        float distanceToNearPlane = node->GetDistance();
1487        //float distanceToNearPlane = node->GetBox().GetMinDistance(sNearPlane);
1488       
1489        return (distanceToNearPlane < sNear);
1490}
1491
1492
1493void Bvh::CreateRoot()
1494{
1495        // create new root
1496        mRoot = new BvhInterior(NULL);
1497
1498        // the separation is a purely logical one
1499        // the bounding boxes of the child nodes are
1500        // identical to those of the root node
1501
1502        mRoot->mBox = mStaticRoot->mBox;
1503        mRoot->mBox.Include(mDynamicRoot->mBox);
1504
1505        mRoot->mArea = mRoot->mBox.SurfaceArea();
1506
1507        mRoot->mFirst = 0;
1508        mRoot->mLast = (int)mGeometrySize - 1;
1509
1510        //cout<<"f: " << mRoot->mFirst<< " l: " <<mRoot->mLast << endl;
1511        // add static root on left subtree
1512        mRoot->mFront = mStaticRoot;
1513        mStaticRoot->mParent = mRoot;
1514
1515        // add dynamic root on left subtree
1516        mRoot->mBack = mDynamicRoot;
1517        mDynamicRoot->mParent = mRoot;
1518}
1519
1520
1521}
Note: See TracBrowser for help on using the repository browser.