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

Revision 3203, 35.3 KB checked in by mattausch, 16 years ago (diff)

only adapting filter size left ...

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