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

Revision 2887, 22.3 KB checked in by mattausch, 16 years ago (diff)

made changes to view transformation but still not working

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