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

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