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

Revision 3042, 23.6 KB checked in by mattausch, 16 years ago (diff)

added technique

Line 
1#include "Bvh.h"
2#include "Camera.h"
3#include "Plane3.h"
4#include "glInterface.h"
5#include "Triangle3.h"
6#include "SceneEntity.h"
7#include "Geometry.h"
8#include "RenderState.h"
9#include "Material.h"
10#include "gzstream.h"
11
12#include <queue>
13#include <stack>
14#include <fstream>
15#include <iostream>
16#include <iomanip>
17
18
19#ifdef _CRT_SET
20        #define _CRTDBG_MAP_ALLOC
21        #include <stdlib.h>
22        #include <crtdbg.h>
23
24        // redefine new operator
25        #define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
26        #define new DEBUG_NEW
27#endif
28
29
30namespace CHCDemoEngine
31{
32
33#define INVALID_TEST ((unsigned int)-1)
34
35using namespace std;
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 sNumIndicesPerBox = 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 Frustum sFrustum;
79
80/// these values are valid for all nodes
81static int sClipPlaneAABBVertexIndices[12];
82
83
84#define ALIGN_INDICES
85
86BvhNode::BvhNode(BvhNode *parent):
87mParent(parent),
88mAxis(-1),
89mDepth(0),
90mFirst(-1),
91mLast(-1),
92mNumTestNodes(1),
93mTestNodesIdx(-1),
94mIndicesPtr(-1),
95mId(0),
96mIsMaxDepthForVirtualLeaf(false),
97mIsVirtualLeaf(false)
98{
99        for (int i = 0; i < NUM_STATES; ++ i)
100        {
101                mPlaneMask[i] = 0;
102                mPreferredPlane[i]= 0;
103                mLastRenderedFrame[i] = -1;
104        }
105}
106
107
108BvhNode::~BvhNode()
109{
110}
111
112
113void BvhNode::ResetVisibility()
114{
115        for (int i = 0; i < NUM_STATES; ++ i)
116        {
117                mVisibility[i].Reset();
118                mLastRenderedFrame[i] = -1;
119                mPlaneMask[i] = 0;
120                mPreferredPlane[i]= 0;
121        }
122}
123
124
125void BvhNode::VisibilityInfo::Reset()
126{
127        mIsVisible = false;
128        mAssumedVisibleFrameId = 0;
129        mLastVisitedFrame = -1;
130        mTimesInvisible = 0;
131        mIsFrustumCulled = false;
132        mIsNew = true;
133        mLastQueriedFrame = -1;
134}
135
136
137BvhInterior::~BvhInterior()
138{
139        DEL_PTR(mBack);
140        DEL_PTR(mFront);
141}
142
143
144BvhLeaf::~BvhLeaf()
145{
146}
147
148
149/***********************************************************/
150/*                class Bvh implementation                 */
151/***********************************************************/
152
153
154Bvh::Bvh()
155{
156        Init();
157}
158
159
160Bvh::Bvh(const SceneEntityContainer &entities)
161{
162        Init();
163
164        mGeometrySize = entities.size();
165        mGeometry = new SceneEntity*[mGeometrySize];
166
167        SceneEntityContainer::const_iterator it, it_end = entities.end();
168
169        int i = 0;
170        for (it = entities.begin(); it != it_end; ++ it, ++ i)
171        {
172                mGeometry[i] = (*it);
173        }
174}
175
176
177Bvh::~Bvh()
178{
179        if (mVertices) delete [] mVertices;
180        if (mIndices) delete [] mIndices;
181        if (mTestIndices) delete [] mTestIndices;
182        if (mGeometry) delete [] mGeometry;
183
184        if (mRoot) delete mRoot;
185
186        // delete vbo
187        glDeleteBuffersARB(1, &mVboId);
188}
189
190
191void Bvh::Init()
192{
193        mRoot = NULL;
194        mVertices = NULL;
195        mIndices = NULL;
196        mTestIndices = NULL;
197        mCurrentIndicesPtr = 0;
198        mNumNodes = 0;
199       
200        mMaxDepthForTestingChildren = 3;
201        //mMaxDepthForTestingChildren = 4;
202        mAreaRatioThreshold = 2.0f;
203        //mAreaRatioThreshold = 1.4f;
204
205        mVboId = -1;
206}
207
208
209void Bvh::PullUpLastVisited(BvhNode *node, const int frameId) const
210{               
211        BvhNode *parent = node->GetParent();
212
213        while (parent && (parent->GetLastVisitedFrame() != frameId))
214        {
215                parent->SetLastVisitedFrame(frameId);
216                parent = parent->GetParent();
217        }
218}
219
220
221void Bvh::MakeParentsVisible(BvhNode *node)
222{
223        BvhNode *parent = node->GetParent();
224
225        while (parent && (!parent->IsVisible()))
226        {
227                parent->SetVisible(true);
228                parent = parent->GetParent();
229        }
230}
231
232
233void Bvh::CollectLeaves(BvhNode *node, BvhLeafContainer &leaves)
234{
235        stack<BvhNode *> tStack;
236        tStack.push(node);
237
238        while (!tStack.empty())
239        {
240                BvhNode *node = tStack.top();
241
242                tStack.pop();
243
244                if (!node->IsLeaf())
245                {
246                        BvhInterior *interior = static_cast<BvhInterior *>(node);
247
248                        tStack.push(interior->mFront);
249                        tStack.push(interior->mBack);
250                }
251                else
252                {
253                        leaves.push_back(static_cast<BvhLeaf *>(node));
254                }
255        }
256}
257
258
259void Bvh::CollectNodes(BvhNode *node, BvhNodeContainer &nodes)
260{
261        stack<BvhNode *> tStack;
262
263        tStack.push(node);
264
265        while (!tStack.empty())
266        {
267                BvhNode *node = tStack.top();
268                tStack.pop();
269
270                nodes.push_back(node);
271
272                if (!node->IsLeaf())
273                {
274                        BvhInterior *interior = static_cast<BvhInterior *>(node);
275
276                        tStack.push(interior->mFront);
277                        tStack.push(interior->mBack);
278                }
279        }
280}
281
282
283typedef pair<BvhNode *, int> tPair;
284
285void Bvh::CollectNodes(BvhNode *root, BvhNodeContainer &nodes, int depth)
286{
287        stack<tPair> tStack;
288        tStack.push(tPair(root, 0));
289
290        while (!tStack.empty())
291        {
292                BvhNode *node = tStack.top().first;
293                const int d = tStack.top().second;
294
295                tStack.pop();
296
297                // found depth => take this node
298                if ((d == depth) || (node->IsLeaf()))
299                {
300                        nodes.push_back(node);
301                }
302                else
303                {
304                        BvhInterior *interior = static_cast<BvhInterior *>(node);
305
306                        tStack.push(tPair(interior->mFront, d + 1));
307                        tStack.push(tPair(interior->mBack, d + 1));
308                }
309        }
310}
311
312
313SceneEntity **Bvh::GetGeometry(BvhNode *node, int &geometrySize) const
314{
315        geometrySize = node->CountPrimitives();
316        return mGeometry + node->mFirst;
317}
318
319
320bool Bvh::TestPlane(BvhNode *node, int i, bool &bIntersect)
321{
322        // do the test only if necessary
323        if (!(node->mPlaneMask[BvhNode::sCurrentState] & (1 << i)))
324                return true;
325                       
326        ////////
327        //-- test the n-vertex
328               
329        if ((node->mBox.GetDistance(sClipPlaneAABBVertexIndices[i * 2 + 0], sFrustum.mClipPlanes[i]) > 0.0f))
330        {
331                // outside
332                node->mPreferredPlane[BvhNode::sCurrentState] = i;
333                return false;
334        }
335
336        ////////////
337        //-- test the p-vertex
338
339        if (node->mBox.GetDistance(sClipPlaneAABBVertexIndices[i * 2 + 1], sFrustum.mClipPlanes[i]) <= 0.0f)
340        {
341                // completely inside: children don't need to check against this plane no more
342                node->mPlaneMask[BvhNode::sCurrentState] ^= 1 << i;
343        }
344        else
345        {
346                bIntersect = true;
347        }
348       
349        return true;
350}
351
352
353int     Bvh::IsWithinViewFrustum(BvhNode *node)
354{
355        bool bIntersect = false;
356
357        if (node->GetParent())
358                node->mPlaneMask[BvhNode::sCurrentState] = node->GetParent()->mPlaneMask[BvhNode::sCurrentState];
359
360        ////////
361        //-- apply frustum culling for the planes [mPreferredPlane - 5]
362
363        for (int i = node->mPreferredPlane[BvhNode::sCurrentState]; i < 6; ++ i)
364                if (!TestPlane(node, i, bIntersect)) return 0;
365       
366
367        //////////
368        //-- do the view frustum culling for the planes [0 - m_iPreferredPlane)
369
370        for (int i = 0; i < node->mPreferredPlane[BvhNode::sCurrentState]; ++ i)
371                if (!TestPlane(node, i, bIntersect)) return 0;
372       
373        return bIntersect ? -1 : 1;
374}
375
376
377static void CalcNPVertexIndices(const Frustum &frustum, int *indices)
378{
379        for (int i = 0; i < 6; ++ i)
380        {
381                // n-vertex
382                indices[i * 2 + 0] = AxisAlignedBox3::GetIndexNearestVertex(frustum.mClipPlanes[i].mNormal);
383                // p-vertex
384                indices[i * 2 + 1] = AxisAlignedBox3::GetIndexFarthestVertex(frustum.mClipPlanes[i].mNormal);   
385        }
386}
387
388
389void Bvh::InitFrame(Camera *cam)
390{
391        // = 0011 1111 which means that at the beginning, all six planes have to frustum culled
392        mRoot->mPlaneMask[BvhNode::sCurrentState] = 0x3f;
393
394        cam->CalcFrustum(sFrustum);
395        CalcNPVertexIndices(sFrustum, sClipPlaneAABBVertexIndices);
396
397        // store near plane
398        sNearPlane = Plane3(cam->GetDirection(), cam->GetPosition());
399}
400
401
402void Bvh::UpdateDistance(BvhNode *node) const
403{
404        //node->mDistance = node->GetBox()GetMinDistance(sNearPlane);
405        node->mDistance = sNearPlane.Distance(node->GetBox().Center());
406}
407
408
409float Bvh::CalcMaxDistance(BvhNode *node) const
410{
411        return node->GetBox().GetMaxDistance(sNearPlane);
412
413        float maxDist = .0f;
414
415        int geometrySize;
416        SceneEntity **entities = GetGeometry(node, geometrySize);
417
418        for (int i = 0; i < geometrySize; ++ i)
419        {
420                SceneEntity *ent = entities[i];
421                float dist = ent->GetTransformedBoundingBox().GetMaxDistance(sNearPlane);
422
423                if (dist > maxDist) maxDist = dist;
424        }
425
426        return maxDist;
427}
428
429
430void Bvh::RenderBounds(BvhNode *node, RenderState *state, bool useTightBounds)
431{
432        // if not using tight bounds, rendering boxes in immediate mode
433        // is preferable to vertex arrays (less setup time)
434        if (!useTightBounds)
435        {
436                RenderBoundingBoxImmediate(node->GetBox());
437        }
438        else
439        {
440                // hack: use dummy wrapper in order to use function
441                static BvhNodeContainer dummy(1);
442                dummy[0] = node;
443                RenderBounds(dummy, state, useTightBounds);
444        }
445}
446
447
448int Bvh::RenderBounds(const BvhNodeContainer &nodes,
449                                          RenderState *state,
450                                          bool useTightBounds)
451{
452        // if not using tight bounds, rendering boxes in immediate mode
453        // is preferable to vertex arrays (less setup time)
454
455        int renderedBoxes;
456
457        if (!useTightBounds)
458        {
459                BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
460                       
461                for (nit = nodes.begin(); nit != nit_end; ++ nit)
462                {
463                        RenderBoundingBoxImmediate((*nit)->GetBox());
464                }
465
466                renderedBoxes = (int)nodes.size();
467        }
468        else
469        {
470                renderedBoxes = PrepareBoundsWithDrawArrays(nodes);
471                RenderBoundsWithDrawArrays(renderedBoxes, state);
472        }
473
474        return renderedBoxes;
475}
476
477
478int Bvh::PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes)
479{
480        //////
481        //-- for the first time we come here ...
482
483        if (!mIndices)
484        {       // create list of indices
485                CreateIndices();
486        }
487
488        if (mVboId == -1)
489        {       
490                // prepare the vbo
491                PrepareVertices();
492        }
493
494        ///////////////
495
496        int numNodes = 0;
497
498        BvhNodeContainer::const_iterator nit, nit_end = nodes.end();
499
500        for (nit = nodes.begin(); nit != nit_end; ++ nit)
501        {
502                BvhNode *node = *nit;
503
504        const int numIndices = node->mNumTestNodes * sNumIndicesPerBox;
505               
506                // copy indices
507                memcpy(mIndices + numNodes * sNumIndicesPerBox,
508                           mTestIndices + node->mIndicesPtr,
509                           numIndices * sizeof(unsigned int));
510
511                numNodes += node->mNumTestNodes;
512        }
513
514        return numNodes;
515}
516
517
518void Bvh::RenderBoundsWithDrawArrays(int numNodes, RenderState *state)
519{
520        //////
521        //-- Rendering the vbo
522
523        if (state->GetCurrentVboId() != mVboId)
524        {
525                glBindBufferARB(GL_ARRAY_BUFFER_ARB, mVboId);
526                // set the vertex pointer to the vertex buffer
527                glVertexPointer(3, GL_FLOAT, 0, (char *)NULL); 
528
529                state->SetCurrentVboId(mVboId);
530        }
531
532        // we do use the last or the first index (they are generate and only used to connect strips)
533        int numElements = numNodes * sNumIndicesPerBox - 1;
534        // don't render first degenerate index
535        glDrawElements(GL_TRIANGLE_STRIP, numElements, GL_UNSIGNED_INT, mIndices + 1);
536}
537
538
539void Bvh::CreateIndices()
540{
541        // collect bvh nodes
542        BvhNodeContainer nodes;
543        CollectNodes(mRoot, nodes);
544
545        cout << "creating new indices" << endl;
546
547        int numMaxIndices = 0;
548
549        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
550
551        for (lit = nodes.begin(); lit != lit_end; ++ lit)
552        {
553                int offset = (*lit)->mNumTestNodes * sNumIndicesPerBox;
554#ifdef ALIGN_INDICES
555                // align with 32
556                offset = (offset / 32) * 32 + 32;
557#endif
558                numMaxIndices += offset;
559        }
560
561
562        cout << "creating global indices buffer" << endl;
563
564        if (mIndices) delete [] mIndices;
565        if (mTestIndices) delete [] mTestIndices;
566
567        // global buffer: create it once so we don't have
568        // to allocate memory from the chunks of the node
569        mIndices = new unsigned int[numMaxIndices];
570
571        // create new index buffer for the individual nodes
572        mTestIndices = new unsigned int[numMaxIndices];
573       
574        mCurrentIndicesPtr = 0;
575
576        for (lit = nodes.begin(); lit != lit_end; ++ lit)
577        {
578                BvhNode *node = *lit;
579               
580                // resize array
581                node->mIndicesPtr = mCurrentIndicesPtr;
582
583                int numIndices = 0;
584
585                // the bounding box of the test nodes are rendered instead of the root node
586                // => store their indices
587                for (int i = 0; i < node->mNumTestNodes; ++ i, numIndices += sNumIndicesPerBox)
588                {
589                        BvhNode *testNode = mTestNodes[node->mTestNodesIdx + i];
590
591                        // add indices to root node
592                        for (int j = 0; j < sNumIndicesPerBox; ++ j)
593                        {
594                                mTestIndices[mCurrentIndicesPtr + numIndices + j] = sIndices[j] + testNode->GetId() * 8;
595                        }
596                }
597
598                // align with 32
599#ifdef ALIGN_INDICES
600                const int offset = (numIndices / 32) * 32 + 32;
601#else
602                const int offset = numIndices;
603#endif
604                mCurrentIndicesPtr += offset;
605        }
606}
607
608
609void Bvh::ComputeIds()
610{
611        // collect all nodes
612        BvhNodeContainer nodes;
613        CollectNodes(mRoot, nodes);
614
615        // assign ids to all nodes of the "regular" hierarchy
616        int i = 0;
617        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
618
619        for (lit = nodes.begin(); lit != lit_end; ++ lit, ++ i)
620        {
621                (*lit)->SetId(i);
622        }
623}
624
625
626void Bvh::PrepareVertices()
627{
628        // collect all nodes
629        BvhNodeContainer nodes;
630
631        nodes.reserve(GetNumNodes());
632        CollectNodes(mRoot, nodes);
633
634        const unsigned int bufferSize = 8 * (int)nodes.size();
635        mVertices = new Vector3[bufferSize];
636       
637        int i = 0;
638       
639        // store bounding box vertices
640        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
641
642        for (lit = nodes.begin(); lit != lit_end; ++ lit, i += 8)
643        {
644                BvhNode *node = *lit;
645
646                for (int j = 0; j < 8; ++ j)
647                        ((Vector3 *)mVertices)[node->GetId() * 8 + j] = node->GetBox().GetVertex(j);
648        }
649
650        glGenBuffersARB(1, &mVboId);
651        glBindBufferARB(GL_ARRAY_BUFFER_ARB, mVboId);
652        glVertexPointer(3, GL_FLOAT, 0, (char *)NULL);
653       
654        glBufferDataARB(GL_ARRAY_BUFFER_ARB,
655                            bufferSize * sizeof(Vector3),
656                            mVertices,
657                                        GL_STATIC_DRAW_ARB);
658
659        glBindBufferARB(GL_ARRAY_BUFFER_ARB, 0);
660
661        // data handled by graphics driver from now on
662        DEL_PTR(mVertices);
663
664        cout << "***** created vbos for tighter bounds *********" << endl;
665}
666
667
668void Bvh::SetMaxDepthForTestingChildren(int maxDepth)
669{
670        if (maxDepth != mMaxDepthForTestingChildren)
671        {
672                mMaxDepthForTestingChildren = maxDepth;
673                RecomputeBounds();
674        }
675}
676
677
678void Bvh::SetAreaRatioThresholdForTestingChildren(float ratio)
679{
680        if (ratio != mAreaRatioThreshold)
681        {
682                mAreaRatioThreshold = ratio;
683                RecomputeBounds();
684        }
685}
686
687
688void Bvh::RecomputeBounds()
689{
690        // collect all nodes
691        BvhNodeContainer nodes;
692        CollectNodes(mRoot, nodes);
693
694        cout << "recomputing bounds, children will be tested in depth " << mMaxDepthForTestingChildren << endl;
695
696        int success = 0;
697        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
698
699        for (lit = nodes.begin(); lit != lit_end; ++ lit)
700        {
701                BvhNode *node = *lit;
702
703                // recreate list of nodes that will be queried as a proxy
704                if (CreateNodeRenderList(node))
705                        ++ success;
706        }
707
708        float p = 100.0f * (float)success / nodes.size();
709        cout << "created tighter bounds for " << p << " percent of the nodes" << endl;
710
711        // recreate indices used for indirect mode rendering
712        if (mIndices) CreateIndices();
713}
714
715       
716bool Bvh::CreateNodeRenderList(BvhNode *node)
717{
718        BvhNodeContainer children;
719
720        // collect nodes that will be tested instead of the leaf node
721        // in order to get a tighter bounding box test
722        CollectNodes(node, children, mMaxDepthForTestingChildren);
723       
724
725        // using the tighter bounds is not feasable in case
726        // that the tighter bounds represent nearly the same projected area
727        // as the old bounding box. Find this out using either volume or area
728        // heuristics
729
730        float vol = 0;
731        float area = 0;
732
733        BvhNodeContainer::const_iterator cit;
734
735        for (cit = children.begin(); cit != children.end(); ++ cit)
736                area += (*cit)->GetBox().SurfaceArea();
737
738        const float areaRatio = area / node->GetBox().SurfaceArea();
739       
740        bool success;
741
742        if (areaRatio < mAreaRatioThreshold)
743                success = true;
744        else
745        {
746                // hack: only store node itself
747                children.clear();
748                children.push_back(node);
749
750                success = false;
751        }
752
753        // the new test nodes are added at the end of the vector
754        node->mTestNodesIdx = (int)mTestNodes.size();
755
756        // use the found nodes as nodes during the occlusion tests
757        for (cit = children.begin(); cit != children.end(); ++ cit)
758        {
759                BvhNode *child = *cit;
760                mTestNodes.push_back(child);
761        }
762
763        node->mNumTestNodes = (int)children.size();
764
765        return success;
766}
767
768
769void Bvh::ResetNodeClassifications()
770{
771        BvhNodeContainer nodes;
772
773        nodes.reserve(GetNumNodes());
774        CollectNodes(mRoot, nodes);
775
776        BvhNodeContainer::const_iterator lit, lit_end = nodes.end();
777
778        for (lit = nodes.begin(); lit != lit_end; ++ lit)
779        {
780                (*lit)->ResetVisibility();
781        }
782}
783
784
785void Bvh::ComputeBvhStats()
786{
787        std::stack<BvhNode *> nodeStack;
788        nodeStack.push(mRoot);
789
790        int numVirtualLeaves = 0;
791
792        while (!nodeStack.empty())
793        {
794                BvhNode *node = nodeStack.top();
795                nodeStack.pop();
796
797                if (node->IsVirtualLeaf())
798                {
799                        ++ numVirtualLeaves;
800
801                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
802
803                        mBvhStats.mTriangles += CountTriangles(leaf);
804                        mBvhStats.mLeafSA += leaf->mBox.SurfaceArea();
805                        mBvhStats.mLeafVol += leaf->mBox.GetVolume();
806                }
807                else
808                {
809                        mBvhStats.mInteriorSA += node->mBox.SurfaceArea();
810                        mBvhStats.mInteriorVol += node->mBox.GetVolume();
811
812                        BvhInterior *interior = static_cast<BvhInterior *>(node);
813                       
814                        nodeStack.push(interior->mBack);
815                        nodeStack.push(interior->mFront);
816                }
817        }
818
819        mBvhStats.mGeometryRatio = mGeometrySize / (float)numVirtualLeaves;
820        mBvhStats.mTriangleRatio = mBvhStats.mTriangles / (float)numVirtualLeaves;
821}
822
823
824void Bvh::PrintBvhStats() const
825{
826        cout << "\n******** bvh stats: ***********" << endl;
827        cout << "interiorNodesSA = " << mBvhStats.mInteriorSA / mRoot->mBox.SurfaceArea() << endl;
828        cout << "leafNodesSA = " << mBvhStats.mLeafSA / mRoot->mBox.SurfaceArea() << endl;
829        cout << "interiorNodesVolume = " << mBvhStats.mInteriorVol / mRoot->mBox.GetVolume() << endl;
830        cout << "leafNodesVolume = " << mBvhStats.mLeafVol / mRoot->mBox.GetVolume() << endl;
831
832        cout << "geometry per leaf: " <<  mBvhStats.mGeometryRatio << endl;
833        cout << "triangles per leaf: " <<  mBvhStats.mTriangleRatio << endl;
834        cout << "**************" << endl << endl;
835}
836
837
838int Bvh::CountTriangles(BvhNode *node) const
839{
840        int numTriangles = 0;
841
842        for (int i = node->mFirst; i <= node->mLast; ++ i)
843        {
844                numTriangles += mGeometry[i]->CountNumTriangles(0);
845        }
846
847        return numTriangles;
848}
849
850
851float Bvh::GetArea(BvhNode *node) const
852{
853        return node->mArea;
854}
855
856
857void Bvh::UpdateNumLeaves(BvhNode *node) const
858{
859        if (node->IsLeaf())
860        {
861                node->mNumLeaves = 1;
862        }
863        else
864        {
865                BvhNode *f = static_cast<BvhInterior *>(node)->GetFront();
866                BvhNode *b = static_cast<BvhInterior *>(node)->GetBack();
867
868                UpdateNumLeaves(f);
869                UpdateNumLeaves(b);
870
871                node->mNumLeaves = f->mNumLeaves + b->mNumLeaves;
872        }
873}
874
875
876void Bvh::CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves)
877{
878        stack<BvhNode *> tStack;
879        tStack.push(node);
880
881        while (!tStack.empty())
882        {
883                BvhNode *node = tStack.top();
884                tStack.pop();
885
886                if (node->mIsVirtualLeaf)
887                {
888                        leaves.push_back(node);
889                }
890                else if (!node->IsLeaf())
891                {
892                        BvhInterior *interior = static_cast<BvhInterior *>(node);
893
894                        tStack.push(interior->mFront);
895                        tStack.push(interior->mBack);
896                }
897        }
898}
899
900
901void Bvh::SetVirtualLeaves(int numTriangles)
902{
903        // first invalidate old leaves
904        BvhNodeContainer leaves;
905
906        CollectVirtualLeaves(mRoot, leaves);
907
908        BvhNodeContainer::const_iterator bit, bit_end = leaves.end();
909
910        for (bit = leaves.begin(); bit != bit_end; ++ bit)
911        {
912                (*bit)->mIsVirtualLeaf = false;
913        }
914
915        mNumVirtualNodes = 0;
916
917        // assign new virtual leaves based on specified number of triangles per leaf
918        std::stack<BvhNode *> nodeStack;
919        nodeStack.push(mRoot);
920
921        while (!nodeStack.empty())
922        {
923                BvhNode *node = nodeStack.top();
924                nodeStack.pop();
925
926                ++ mNumVirtualNodes;
927
928                if (node->IsLeaf())
929                {
930                        BvhLeaf *leaf = static_cast<BvhLeaf *>(node);
931                        leaf->mIsVirtualLeaf = true;
932                }
933                else
934                {
935                        BvhInterior *interior = static_cast<BvhInterior *>(node);
936
937                        BvhNode *f = interior->mFront;
938                        BvhNode *b = interior->mBack;
939
940                        if (node->mIsMaxDepthForVirtualLeaf || (CountTriangles(node) <= numTriangles))
941                        {
942                                 node->mIsVirtualLeaf = true;
943                        }
944                        else
945                        {
946                                nodeStack.push(interior->mBack);
947                                nodeStack.push(interior->mFront);
948                        }
949                }
950        }
951
952        ResetNodeClassifications();
953}
954
955
956void Bvh::PostProcess()
957{
958        std::stack<BvhNode *> nodeStack;
959        nodeStack.push(mRoot);
960
961        while (!nodeStack.empty())
962        {
963                BvhNode *node = nodeStack.top();
964                nodeStack.pop();
965
966                if (node->IsLeaf())
967                {
968                        node->mIsMaxDepthForVirtualLeaf = true;
969                }
970                else
971                {
972                        BvhInterior *interior = static_cast<BvhInterior *>(node);
973
974                        BvhNode *f = interior->mFront;
975                        BvhNode *b = interior->mBack;
976
977                        // point reached where we cannot subdivide further on object level
978                        if ((f->mFirst == b->mFirst) && (f->mLast == b->mLast))
979                        {
980                                node->mIsMaxDepthForVirtualLeaf = true;
981                        }
982                        else
983                        {
984                                nodeStack.push(f);
985                                nodeStack.push(b);
986                        }
987                }
988        }
989}
990
991
992void Bvh::RenderBoundingBoxImmediate(const AxisAlignedBox3 &box)
993{
994        const Vector3 l = box.Min();
995        const Vector3 u = box.Max();
996
997        glBegin(GL_TRIANGLE_STRIP);
998        {
999                ///////////
1000                //-- render AABB as triangle strips
1001
1002                glVertex3f(l.x, l.y, u.z);
1003                glVertex3f(u.x, l.y, u.z);
1004                glVertex3f(l.x, u.y, u.z);
1005                glVertex3f(u.x, u.y, u.z);
1006                glVertex3f(l.x, u.y, l.z);
1007                glVertex3f(u.x, u.y, l.z);
1008                glVertex3f(l.x, l.y, l.z);
1009                glVertex3f(u.x, l.y, l.z);
1010
1011                glPrimitiveRestartNV();
1012
1013                //-- render second half of AABB
1014                glVertex3f(l.x, u.y, u.z);
1015                glVertex3f(l.x, u.y, l.z);
1016                glVertex3f(l.x, l.y, u.z);
1017                glVertex3f(l.x, l.y, l.z);
1018                glVertex3f(u.x, l.y, u.z);
1019                glVertex3f(u.x, l.y, l.z);
1020                glVertex3f(u.x, u.y, u.z);
1021                glVertex3f(u.x, u.y, l.z);
1022        }
1023        glEnd();
1024}
1025
1026
1027
1028
1029static void RenderBoxForViz(const AxisAlignedBox3 &box)
1030{
1031        glBegin(GL_LINE_LOOP);
1032        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1033        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1034        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1035        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1036        glEnd();
1037
1038        glBegin(GL_LINE_LOOP);
1039        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1040        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1041        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1042        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1043        glEnd();
1044
1045        glBegin(GL_LINE_LOOP);
1046        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1047        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1048        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1049        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1050        glEnd();
1051
1052        glBegin(GL_LINE_LOOP);
1053        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1054        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1055        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1056        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1057        glEnd();
1058
1059        glBegin(GL_LINE_LOOP);
1060        glVertex3d(box.Min().x, box.Min().y, box.Min().z);
1061        glVertex3d(box.Max().x, box.Min().y, box.Min().z);
1062        glVertex3d(box.Max().x, box.Min().y, box.Max().z);
1063        glVertex3d(box.Min().x, box.Min().y, box.Max().z);
1064        glEnd();
1065
1066        glBegin(GL_LINE_LOOP);
1067        glVertex3d(box.Min().x, box.Max().y, box.Min().z);
1068        glVertex3d(box.Max().x, box.Max().y, box.Min().z);
1069        glVertex3d(box.Max().x, box.Max().y, box.Max().z);
1070        glVertex3d(box.Min().x, box.Max().y, box.Max().z);
1071
1072        glEnd();
1073}
1074
1075
1076void Bvh::RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds)
1077{
1078        glDisable(GL_TEXTURE_2D);
1079        glDisable(GL_LIGHTING);
1080        glColor3f(1, 1, 1);
1081
1082        // hack: for deferred shading we have to define a material
1083        static Technique boxMat;
1084        boxMat.SetEmmisive(RgbaColor(1.0f, 1.0f, 1.0f, 1.0f));
1085
1086        boxMat.Render(state);
1087
1088        if (!useTightBounds)
1089        {
1090                RenderBoxForViz(node->GetBox());
1091        }
1092        else
1093        {
1094                for (int i = 0; i < node->mNumTestNodes; ++ i)
1095                {
1096                        RenderBoxForViz(mTestNodes[node->mTestNodesIdx + i]->GetBox());
1097                }
1098        }
1099
1100        glEnable(GL_LIGHTING);
1101        glEnable(GL_TEXTURE_2D);
1102}
1103
1104
1105
1106}
Note: See TracBrowser for help on using the repository browser.