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

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