source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Bvh.h @ 3074

Revision 3074, 19.5 KB checked in by mattausch, 16 years ago (diff)

included vbo support for dynamic objects

Line 
1// This file has been written by Jiri Bittner, October 2006
2
3#ifndef __BVH_H
4#define __BVH_H
5
6#include "common.h"
7#include "Vector3.h"
8#include "AxisAlignedBox3.h"
9
10
11
12namespace CHCDemoEngine
13{
14
15// the number of visibility states
16#define NUM_STATES 2
17
18////////
19//-- Forward declarations
20
21class SceneEntity;
22class Camera;
23class RenderState;
24
25
26/** A node in the bv hierarchy.
27*/
28class BvhNode
29{
30        friend class Bvh;
31        friend class BvhLoader;
32        friend class mygreaterdistance;
33
34public:
35
36        /** visibility related options
37        */
38        struct VisibilityInfo
39        {
40                VisibilityInfo() { Reset(); }           
41                /** Reset the visibility info.
42                */
43                void Reset();
44
45                /// if the node is visible
46                bool mIsVisible;
47                /// frame id until this node is assumed to stay visible
48                int mAssumedVisibleFrameId;
49                /// the frame when this node was last touched during traversal
50                int mLastVisitedFrame;
51                /// #times this node was invisible (only valid if the node actually is invisible)
52                int mTimesInvisible;
53                /// if the node is view frustum culled
54                bool mIsFrustumCulled;
55                /// if the node is newly processed with no prior history available
56                bool mIsNew;
57                /// the frame this node was last queried
58                int mLastQueriedFrame;
59        };
60
61        /** Constructor taking the parent node.
62        */
63        BvhNode(BvhNode *parent);
64        /** Virtual destructor doing nothing.
65        */
66        virtual ~BvhNode();
67        /** Reset the status of this node.
68        */
69        virtual void ResetVisibility();
70        /** Returns true if this node is a leaf.
71        */
72        virtual bool IsLeaf() const = 0;
73        /** Depth of this node in the tree.
74        */
75        inline int GetDepth() const;
76        /** Returns parent of this bvh node, NULL if it is root.
77        */
78        inline BvhNode *GetParent();
79        /** Number of leaves in the subtree induced by this node.
80        */
81        inline int GetNumLeaves() const;
82        /** Returns true if this node is a "virtual" leaf,
83                i.e., the node is handled as a leaf during traversal.
84        */
85        inline bool IsVirtualLeaf() const;
86        /** Returns the stored distance to the near plane.
87        */
88        inline float GetDistance() const;
89
90
91        ////////////////
92        //-- visibility culling related functions
93
94        inline int GetLastVisitedFrame() const;
95
96        inline void SetLastVisitedFrame(int lastVisited);
97        /** If this node is considered visible.
98        */
99        inline bool IsVisible() const;
100        /** Set visibility flag of the node.
101        */
102        inline void SetVisible(bool visible);
103        /** The frame id until this node is assumed visible
104        */
105        inline void SetAssumedVisibleFrameId(int t);
106        /** See set.
107        */
108        inline int GetAssumedVisibleFrameId() const;
109        /** Increases the #times this node was
110                successfully tested invisible.
111        */
112        inline void IncTimesTestedInvisible();
113       
114        inline int GetTimesTestedInvisible() const;
115        inline void SetTimesTestedInvisible(int t);
116       
117        inline int GetTurnedVisibleFrame() const;
118        inline void SetTurnedVisibleFrame(int turnedVisibleFrame);
119
120        inline int GetLastQueriedFrame() const;
121        inline void SetLastQueriedFrame(int lastTested);
122       
123        inline bool IsViewFrustumCulled() const;
124        inline void SetViewFrustumCulled(bool frustumCulled);
125
126        inline bool IsNew() const;
127        inline void SetIsNew(bool isNew);
128
129
130        /** Returns the bounding box of this node.
131        */
132        inline const AxisAlignedBox3 &GetBox() const;
133        /** Return index of this node.
134        */
135        inline int GetId() const;
136        /** See get
137        */
138        inline void SetId(int id);
139       
140
141        //////////
142        //-- rendering
143       
144        /** Returns the frame in which this node was last rendered.
145        */
146        inline int GetLastRenderedFrame() const;
147        /** See get.
148        */
149        inline void SetLastRenderedFrame(int lastRenderedFrame);
150        /** Does this node contain renderable geometry?
151        */
152        inline bool Empty() const;
153        /** Counts #geometry stored in the subtree.
154        */
155        inline int CountPrimitives() const;
156        /** This is an imporantent function once you have one or more
157                view point changes within a frame (e.g., camera view and shadow view for
158                shadow mapping), because each camera needs its own state in
159                order to not break temporal coherency.
160        */
161        inline static void SetCurrentState(int _state) { sCurrentState = _state; }
162
163
164protected:
165
166        /// the depth of this node
167        unsigned char mDepth;
168        /// the split axis
169        char mAxis;
170        /// the parent node
171        BvhNode *mParent;
172
173
174        //////////////
175        //-- members definig the current visibility state (one state per camera)
176
177        /// the currently used state
178        static int sCurrentState;
179
180        /// stores the visibility related info
181        VisibilityInfo mVisibility[NUM_STATES];
182       
183        // members used to speed up view frustum culling
184        /// masks out planes of the frustum that do not have to be tested against
185        int mPlaneMask[NUM_STATES];
186        /// the plane that is usually responsible for culling this node.
187        /** if our educated guess was right, we save up to 5 comparisons.
188        */
189        int mPreferredPlane[NUM_STATES];
190        /// when the node was last rendered
191        int mLastRenderedFrame[NUM_STATES];
192
193        ////////////////////
194
195
196        /// #leaves under this node
197        int mNumLeaves;
198        /// Area of this node
199        float mArea;
200        /// distance to the camera
201        float mDistance;
202        /// the index of this node
203        unsigned int mId;
204        /// the bounding box
205        AxisAlignedBox3 mBox;
206        /// if this node is a virtual leaf
207        bool mIsVirtualLeaf;
208        /** This marks the maximal depth where a virtual leaf can be defined.
209            From this point on it makes no sense to traverse down further, as all
210                nodes below contain the same geometry, so no further refinement of visibility
211                can be archieved. All nodes below this point can merely used to define the
212                tighter bounds.
213        */
214        bool mIsMaxDepthForVirtualLeaf;
215
216
217        ////////////
218        //-- rendering related options
219       
220        // Indices to first and last triangle in the triangle array
221        // assumes the triangle are placed in continuous chunk of memory
222        // however this need not be a global array!
223       
224        /// the index of the first triangle
225        int mFirst;
226        /// the index of the last triangle
227        int mLast;
228
229
230        ////////////////
231        //-- rendering related options
232
233        /// the bounding boxes of the test nodes are queries instead of the actual node
234        int mTestNodesIdx;
235        /// the number of these test nodes
236        int mNumTestNodes;
237        /// used for efficient element array rendering
238        int mIndicesPtr;
239};
240
241
242
243/////////////////
244//-- public inline functions
245
246
247int BvhNode::GetLastVisitedFrame() const
248{
249        return mVisibility[sCurrentState].mLastVisitedFrame;
250}
251
252
253void BvhNode::SetLastVisitedFrame(const int lastVisited)
254{
255        mVisibility[sCurrentState].mLastVisitedFrame = lastVisited;
256}
257
258
259bool BvhNode::IsVisible() const
260{
261        return mVisibility[sCurrentState].mIsVisible;
262}
263
264
265void BvhNode::SetVisible(bool visible)
266{
267        mVisibility[sCurrentState].mIsVisible = visible;
268}
269
270
271void BvhNode::IncTimesTestedInvisible()
272{
273        ++ mVisibility[sCurrentState].mTimesInvisible;
274}
275
276
277int BvhNode::GetTimesTestedInvisible() const
278{
279        return mVisibility[sCurrentState].mTimesInvisible;
280}
281
282
283void BvhNode::SetTimesTestedInvisible(int t)
284{
285        mVisibility[sCurrentState].mTimesInvisible = t;
286}
287
288
289bool BvhNode::IsViewFrustumCulled() const
290{
291        return mVisibility[sCurrentState].mIsFrustumCulled;
292}
293
294
295void BvhNode::SetViewFrustumCulled(bool frustumCulled)
296{
297        mVisibility[sCurrentState].mIsFrustumCulled = frustumCulled;
298}
299
300
301bool BvhNode::IsNew() const
302{
303        return mVisibility[sCurrentState].mIsNew;
304}
305
306
307void BvhNode::SetIsNew(bool isNew)
308{
309        mVisibility[sCurrentState].mIsNew = isNew;
310}
311
312
313void BvhNode::SetAssumedVisibleFrameId(int t)
314{
315        mVisibility[sCurrentState].mAssumedVisibleFrameId = t;
316}
317
318
319int BvhNode::GetAssumedVisibleFrameId() const
320{
321        return mVisibility[sCurrentState].mAssumedVisibleFrameId;
322}
323
324
325int BvhNode::GetLastQueriedFrame() const
326{
327        return mVisibility[sCurrentState].mLastQueriedFrame;
328}
329
330
331void BvhNode::SetLastQueriedFrame(int lastTested)
332{
333        mVisibility[sCurrentState].mLastQueriedFrame = lastTested;
334}
335
336
337int BvhNode::GetLastRenderedFrame() const
338{
339        return mLastRenderedFrame[sCurrentState];
340}
341       
342
343void BvhNode::SetLastRenderedFrame(int lastRenderedFrame)
344{
345        mLastRenderedFrame[sCurrentState] = lastRenderedFrame;
346}
347       
348       
349bool BvhNode::Empty() const
350{
351        return (mFirst == -1);
352}
353
354
355int BvhNode::CountPrimitives() const
356{
357        return mLast - mFirst + 1;
358}
359
360int BvhNode::GetDepth() const
361{
362        return mDepth;
363}
364
365
366BvhNode *BvhNode::GetParent()
367{
368        return mParent;
369}
370
371
372int BvhNode::GetNumLeaves() const
373{
374        return mNumLeaves;
375}
376
377
378bool BvhNode::IsVirtualLeaf() const
379{
380        return mIsVirtualLeaf;
381}
382
383
384float BvhNode::GetDistance() const
385{
386        return mDistance;
387}
388
389       
390const AxisAlignedBox3 &BvhNode::GetBox() const
391{
392        return mBox;
393}
394
395
396int BvhNode::GetId() const
397{
398        return mId;
399}
400
401
402void BvhNode::SetId(int id)
403{
404        mId = id;
405}
406
407
408
409/** Internal node of the bv hierarchy.
410*/
411class BvhInterior: public BvhNode
412{
413        friend class Bvh;
414        friend class BvhLoader;
415
416public:
417
418        BvhInterior(BvhNode *parent): mBack(NULL), mFront(NULL), BvhNode(parent)
419        {}
420        virtual bool IsLeaf() const { return false; }
421        /** Back child.
422        */
423        inline BvhNode *GetBack() { return mBack; }
424        /** Front child.
425        */
426        inline BvhNode *GetFront() { return mFront; }
427        /** Recursivly delete hierarchy.
428        */
429        virtual ~BvhInterior();
430
431
432protected:
433
434        BvhNode *mBack;
435        BvhNode *mFront;
436};
437
438
439class BvhLeaf: public BvhNode
440{
441        friend class Bvh;
442        friend class BvhLoader;
443
444public:
445
446        BvhLeaf(BvhNode *parent): BvhNode(parent)
447        {}
448
449        ~BvhLeaf();
450
451        virtual bool IsLeaf() const { return true; }
452};
453
454
455/**     This class implements the compare operator for the priority queue.
456        a lower distance has a higher value in the queue
457*/
458class GtDistance
459{
460public:
461        bool operator() (BvhNode *v1, BvhNode *v2) const
462    {
463                return (v1->GetDistance() > v2->GetDistance());
464    }
465};
466
467typedef std::priority_queue<BvhNode *, std::vector<BvhNode *>, GtDistance> TraversalQueue;
468
469
470/** Class representing a bounding volume hierarchy.
471*/
472class Bvh
473{
474        friend class BvhLoader;
475
476        /** Bvh properties
477        */
478        struct BvhStats
479        {
480                BvhStats() { Reset(); }
481
482                void Reset()
483                {
484                        mInteriorSA = .0f;
485                        mLeafSA = .0f;
486                        mInteriorVol = .0f;
487                        mLeafVol = .0f;
488                        mTriangleRatio = .0f;
489                        mGeometryRatio = .0f;
490
491                        mTriangles = 0;
492                        mLeaves = 0;
493                }
494
495                ///////////////////
496
497                float mInteriorSA;
498                float mLeafSA;
499                float mInteriorVol;
500                float mLeafVol;
501               
502                float mTriangleRatio;
503                float mGeometryRatio;
504
505                int mTriangles;
506                int mLeaves;
507        };
508
509public:
510
511        /** Destructor.
512        */
513        ~Bvh();
514        /** Returns number of bvh nodes.
515        */
516        inline int GetNumNodes() const;
517        /** Returns number of bvh leaves.
518        */
519        inline int GetNumLeaves() const;
520        /** Returns number of 'virtual' nodes in the hierarchy, i.e.
521                the number of nodes actually used for traversal.
522        */
523        inline int GetNumVirtualNodes() const;
524        /** Returns number of bvh leaves.
525        */
526        inline int GetNumVirtualLeaves() const;
527        /** Returns root node of the bvh.
528        */
529        inline BvhNode *GetRoot();
530
531        inline BvhNode *GetDynamicRoot();
532        /** Returns the bounding box of this bvh.
533        */
534        inline const AxisAlignedBox3 &GetBox() const;
535        /** Returns true if the current bvh node intersects the near plane.
536        */
537        bool IntersectsNearPlane(BvhNode *node) const;
538
539
540        ///////////////
541        //-- functions collecting nodes based on some criteria
542
543        /** Collect all child nodes in a given depth from the specified node.
544        */
545        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
546        void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
547        /** Collect the "physical" leaves of the hierarchy
548        */
549        void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
550        /** Collect only the virtual leaves (can be anywhere in the hierarchy).
551        */
552        void CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves);
553
554
555        //////////////////////
556
557        /** Returns geometry by reference (faster).
558        */
559        SceneEntity **GetGeometry(BvhNode *node, int &size) const;
560
561
562        /////////////
563        //-- Rendering related options
564
565        /** Renders the bounds of this node
566            (the box of the node or the tigher bounds of some subnodes).
567        */
568        void RenderBounds(BvhNode *node, RenderState *state, bool useTightBounds);
569        /** Renders bounding boxes of the collection of nodes.
570                @returns #rendered boxes
571        */
572        int RenderBounds(const BvhNodeContainer &nodes, RenderState *state, bool useTightBounds);
573       
574
575
576        //////////////
577        //-- Traversal related options
578
579        /** Pulls up visible classification.
580        */
581        void MakeParentsVisible(BvhNode *node);
582        /** Does the view frustum culling for this node with respect to the previous culls
583                @returns: 0 if completely outside, 1 if completely inside, -1 if intersecting (partly inside),
584        */
585        int     IsWithinViewFrustum(BvhNode *node);
586        /** Sets frame dependent values
587        */
588        void InitFrame(Camera *camera, RenderState *state);
589        /** Stores the orthogonal distance from the viewpoint to a point on the node.
590                We choose the the nearest bounding box vertex .
591                Note that negative values can appear because culling is done only afterwards
592        */
593        void UpdateDistance(BvhNode *node) const;
594        /** Returns the maximum distance from the near plane to this node.
595        */
596        float CalcMaxDistance(BvhNode *node) const;
597        /** Pulls up the last visited classification in the bvh.
598        */
599        void PullUpLastVisited(BvhNode *node, int frameId) const;
600        /** Resets the node classifications in the tree.
601        */
602        void ResetNodeClassifications();
603        /** Count triangles the node contains.
604        */
605        int CountTriangles(BvhNode *node) const;
606        /** Returns area of the the node.
607        */
608        float GetArea(BvhNode *node) const;
609        /** Compute unique ids for the nodes.
610        */
611        void ComputeIds();
612        /** Assign virtual leaves based on specified number of triangles per leaf.
613                That means that we try to set the leaves at a point where we
614                have less than numTriangles triangles within this leaf and beyond.
615
616                Virtual leaves are nodes that are determined to be the leaves
617                of the hierarchy during render traversal. These nodes are not necessarily
618                the same as the real leaves of the hierarchy and can be anywhere
619                in the hierarchy.
620                Please refer to the article for more info about virtual leaves
621        */
622        void SetVirtualLeaves(int numTriangles);
623       
624
625        ////////////
626        //-- functions influencing the tightness of the bounds that are used for testing
627
628
629        /** Sets maximal depth for taking the bounding boxes to test the
630                visibility of a node.
631                Deeper level means that the bounds adapt more to the geometry but
632                also that more boxes are rendered
633        */
634        void SetMaxDepthForTestingChildren(int maxDepth);
635        /** The ratio of area between node and subnodes where
636                testing the subnodes as proxy is still considered feasable
637        */
638        void SetAreaRatioThresholdForTestingChildren(float ratio);
639
640
641        ////////////////////////////
642
643        /** Returns stats.
644        */
645        const BvhStats &GetBvhStats() const { return mBvhStats; }
646        /** Render wireframe bvh for visualization purpose.
647        */
648        void RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds);
649
650
651protected:
652
653        ////////////////////
654
655        /** protected constructor: do nothing.
656        */
657        Bvh();
658        /** Protected constructor taking scene geometry into account
659                Sets the static and dynamic objects for the hierarchy.
660        */
661        const Bvh(const SceneEntityContainer &staticEntities,
662                      const SceneEntityContainer &dynamicEntities);
663        /** Called by the constructor. Initializes important members.
664        */
665        void Init();
666
667        /////////////
668        /** Traverse hierarchy and compute stats.
669        */
670        void ComputeBvhStats(BvhNode *root, BvhStats &bvhStats);
671        /** Output the bvh statistics.
672        */
673        void PrintBvhStats(const BvhStats &bvhStats) const;
674
675
676        //////////
677        //-- Helper methods for bounding box rendering in immediate and vbo mode.
678       
679        void PrepareVertices();
680        /** Prepare nodes for vbo rendering.
681        */
682        int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
683        /** Render the nodes from the vbo prepared previously.
684        */
685        void RenderBoundsWithDrawArrays(int numNodes, RenderState *state);
686
687        /** Create the indices that each node needs to use vbo rendering.
688        */
689        void CreateIndices();
690        /** Create the list of nodes whose bounding boxes are tested instead of the
691                bounding box of the node itself.
692        */
693        bool CreateNodeRenderList(BvhNode *node);
694        /** Recursivly updates indices so we can
695                render also interior nodes without traversing hierarchy
696        */
697        void UpdateInteriors(BvhNode *node);
698        /** Recomputes the boundaries of the nodes.
699            This function is always called if some boundary options are changed.
700        */
701        void RecomputeBounds();
702        /** Does some postprocessing on the nodes.
703        */
704        void PostProcess();
705        /** Helper method that updates the number of leaves in the subtree under
706                this node.
707        */
708        void UpdateNumLeaves(BvhNode *node) const;
709        /** Frustum tests the ith plane.
710        */
711        inline bool TestPlane(BvhNode *node, int i, bool &bIntersect);
712        /** Renders a bounding box in immediate mode.
713        */
714        void RenderBoundingBoxImmediate(const AxisAlignedBox3 &box);
715
716
717        /////////////////////////////
718        //-- functions used to construct the dynamic part of the hierarchy
719
720        int SortTriangles(BvhLeaf *leaf,
721                              int axis,
722                                          float position);
723
724        int SortTrianglesSpatialMedian(BvhLeaf *leaf,
725                                           int axis);
726
727        BvhNode *SubdivideLeaf(BvhLeaf *leaf,
728                                   int parentAxis);
729        /** Recompute the dynamic branch of the hierarchy.
730        */
731        void CreateDynamicBranch();
732
733        void UpdateDynamicBranch(BvhNode *node);
734
735        inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;
736
737        void ComputeMaxDepthForVirtualLeaves();
738
739        void CreateRoot();
740
741        void UpdateDynamicBounds(RenderState *state);
742
743
744        ////////////////////////
745       
746        /// the bounding box of the bvh
747        AxisAlignedBox3 mBox;
748        /// the root of the hierarchy
749        BvhInterior *mRoot;
750        /// the root of static part of the the hierarchy
751        BvhNode *mStaticRoot;
752        /// the root of dynamic part of the the hierarchy
753        BvhNode *mDynamicRoot;
754        /// pointers to the geometry associated with this node
755        SceneEntity **mGeometry;
756        /// #of entities
757        size_t mGeometrySize;
758        /// #of static entities
759        size_t mStaticGeometrySize;
760        /// #of dynamic entities
761        size_t mDynamicGeometrySize;
762
763
764        ////////////////
765        //-- tigher bounds termination criteria
766
767        /** maximal depth from which children are fetched for
768                testing instead of the current node
769        */
770        int mMaxDepthForTestingChildren;
771        /// threshold for computing tighter bounds
772        float mAreaRatioThreshold;
773       
774       
775        ////////////////
776        //-- statistics
777
778        BvhStats mBvhStats;
779        /// the overall number of nodes
780        int mNumNodes;
781        /// the number of "virtual" (=actually used) nodes
782        int mNumVirtualNodes;
783
784
785        ////////////
786        //-- rendering stuff
787
788        /// these proxy nodes are tested instead of the current node
789        BvhNodeContainer mTestNodes;
790        /// the indices used for vbo index buffering
791        unsigned int *mTestIndices;
792        /// a pointer to the end of the indices array
793        int mCurrentIndicesPtr;
794        /// the vbo id
795        unsigned int mVboId;
796        /// a vertex array used if working with indexed arrays (without vbo)
797        Vector3 *mVertices;
798        /// indices used for draw array rendering
799        unsigned int *mIndices;
800
801
802        ///////////
803        //-- termination criteria for dynamic branch
804
805        int mMaxDepthForDynamicBranch;
806
807        //SceneEntityContainer mDynamicEntities;
808};
809
810
811
812/////////////////
813//-- public inline functions
814
815
816int Bvh::GetNumNodes() const
817{
818        return mNumNodes;
819}
820
821
822int Bvh::GetNumLeaves() const
823{
824        return mNumNodes / 2 + 1;
825}
826
827
828int Bvh::GetNumVirtualNodes() const 
829{
830        return mNumVirtualNodes;
831}
832
833
834int Bvh::GetNumVirtualLeaves() const
835{
836        return mNumVirtualNodes / 2 + 1;
837}
838
839
840BvhNode *Bvh::GetRoot()
841{
842        return mRoot;
843}
844
845
846BvhNode *Bvh::GetDynamicRoot()
847{
848        return mDynamicRoot;
849}
850
851
852const AxisAlignedBox3 &Bvh::GetBox() const
853{
854        return mBox;
855}
856
857
858}
859
860#endif // __BVH_H
Note: See TracBrowser for help on using the repository browser.