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

Revision 3265, 36.4 KB checked in by mattausch, 15 years ago (diff)

worked on bvh constructor

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