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

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