source: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h @ 1315

Revision 1315, 18.9 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _BvHierarchy_H__
2#define _BvHierarchy_H__
3
4#include <stack>
5
6#include "Mesh.h"
7#include "Containers.h"
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "gzstream.h"
12#include "SubdivisionCandidate.h"
13#include "AxisAlignedBox3.h"
14#include "IntersectableWrapper.h"
15
16
17namespace GtpVisibilityPreprocessor {
18
19
20class ViewCellLeaf;
21class Plane3;
22class AxisAlignedBox3;
23class Ray;
24class ViewCellsStatistics;
25class ViewCellsManager;
26class MergeCandidate;
27class Beam;
28class ViewCellsTree;
29class Environment;
30class BvhInterior;
31class BvhLeaf;
32class BvhNode;
33class BvhIntersectable;
34class BvhTree;
35class VspTree;
36class ViewCellsContainer;
37//class BvhSubdivisionCandidate;
38
39
40/** View space partition statistics.
41*/
42class BvhStatistics: public StatisticsBase
43{
44public:
45        // total number of nodes
46        int nodes;
47        // number of splits
48        int splits;
49        // maximal reached depth
50        int maxDepth;
51        // minimal depth
52        int minDepth;
53        // max depth nodes
54        int maxDepthNodes;
55        // minimum depth nodes
56        int minDepthNodes;
57        // nodes with minimum objects
58        int minObjectsNodes;
59        // minimum area nodes
60        int minProbabilityNodes;
61        /// nodes termination because of max cost ratio;
62        int maxCostNodes;
63        // max number of rays per node
64        int maxObjectRefs;
65        /// number of invalid leaves
66        int invalidLeaves;
67        /// accumulated number of rays refs
68        //int accumRays;
69        // accumulated depth (used to compute average)
70        int accumDepth;
71        /// object references
72        int objectRefs;
73
74        // Constructor
75        BvhStatistics()
76        {
77                Reset();
78        }
79
80        int Nodes() const {return nodes;}
81        int Interior() const { return nodes / 2; }
82        int Leaves() const { return (nodes / 2) + 1; }
83       
84        // TODO: computation wrong
85        double AvgDepth() const
86        { return accumDepth / (double)Leaves(); }
87
88        void Reset()
89        {
90                nodes = 0;
91                splits = 0;
92               
93                maxDepth = 0;
94                minDepth = 99999;
95                accumDepth = 0;
96        maxDepthNodes = 0;
97                minObjectsNodes = 0;
98                minProbabilityNodes = 0;
99                maxCostNodes = 0;
100                invalidLeaves = 0;
101                maxObjectRefs = 0;
102                objectRefs = 0;
103        }
104
105        void Print(ostream &app) const;
106
107        friend ostream &operator<<(ostream &s, const BvhStatistics &stat)
108        {
109                stat.Print(s);
110                return s;
111        }
112};
113
114
115/**
116    VspNode abstract class serving for interior and leaf node implementation
117*/
118class BvhNode
119{
120public:
121       
122        // types of vsp nodes
123        enum {Interior, Leaf};
124
125        BvhNode();
126        BvhNode(const AxisAlignedBox3 &bbox);
127        BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent);
128
129        virtual ~BvhNode(){};
130
131        /** Determines whether this node is a leaf or not
132                @return true if leaf
133        */
134        virtual bool IsLeaf() const = 0;
135
136        /** Determines whether this node is a root
137                @return true if root
138        */
139        virtual bool IsRoot() const;
140
141        /** Returns parent node.
142        */
143        BvhInterior *GetParent();
144
145        /** Sets parent node.
146        */
147        void SetParent(BvhInterior *parent);
148
149        /** The bounding box specifies the node extent.
150        */
151        AxisAlignedBox3 GetBoundingBox() const
152        { return mBoundingBox; }
153
154
155        void SetBoundingBox(const AxisAlignedBox3 &boundingBox)
156        { mBoundingBox = boundingBox; }
157
158
159        /////////////////////////////////////
160        //-- mailing options
161       
162        static void NewMail(const int reserve = 1) {
163                sMailId += sReservedMailboxes;
164                sReservedMailboxes = reserve;
165        }
166       
167        void Mail() { mMailbox = sMailId; }
168        bool Mailed() const { return mMailbox == sMailId; }
169
170        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
171        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
172
173        int IncMail() { return ++ mMailbox - sMailId; }
174
175        static int sMailId;
176        int mMailbox;
177        static int sReservedMailboxes;
178
179        ///////////////////////////////////
180
181protected:
182       
183        /// the bounding box of the node
184        AxisAlignedBox3 mBoundingBox;
185        /// parent of this node
186        BvhInterior *mParent;
187};
188
189
190/** BSP interior node implementation
191*/
192class BvhInterior: public BvhNode
193{
194public:
195        /** Standard contructor taking a bounding box as argument.
196        */
197        BvhInterior(const AxisAlignedBox3 &bbox);
198        BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent);
199
200        ~BvhInterior();
201        /** @return false since it is an interior node
202        */
203        bool IsLeaf() const;
204       
205        BvhNode *GetBack() { return mBack; }
206        BvhNode *GetFront() { return mFront; }
207
208        /** Replace front or back child with new child.
209        */
210        void ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild);
211
212        /** Replace front and back child.
213        */
214        void SetupChildLinks(BvhNode *front, BvhNode *back);
215
216        friend ostream &operator<<(ostream &s, const BvhInterior &A)
217        {
218                return s << A.mBoundingBox;
219        }
220
221protected:
222
223        /// back node
224        BvhNode *mBack;
225        /// front node
226        BvhNode *mFront;
227};
228
229
230/** BSP leaf node implementation.
231*/
232class BvhLeaf: public BvhNode
233{
234public:
235        /** Standard contructor taking a bounding box as argument.
236        */
237        BvhLeaf(const AxisAlignedBox3 &bbox);
238        BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent);
239        BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent, const int numObjects);
240
241        ~BvhLeaf();
242
243        /** @return true since it is an interior node
244        */
245        bool IsLeaf() const;
246       
247        SubdivisionCandidate *GetSubdivisionCandidate()// const
248        {
249                return mSubdivisionCandidate;
250        }
251
252        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
253        {
254                mSubdivisionCandidate = candidate;
255        }
256
257public:
258
259        /// Rays piercing this leaf.
260        VssRayContainer mVssRays;
261        /// objects
262        ObjectContainer mObjects;
263        /// universal counter
264        int mCounter;
265
266protected:
267
268        /// pointer to a split plane candidate splitting this leaf
269        SubdivisionCandidate *mSubdivisionCandidate;
270};
271
272
273typedef map<BvhNode *, BvhIntersectable *> BvhIntersectableMap;
274
275
276/** View Space Partitioning tree.
277*/
278class BvHierarchy
279{
280        friend class ViewCellsParseHandlers;
281        friend class HierarchyManager;
282
283public:
284       
285        /** Additional data which is passed down the BSP tree during traversal.
286        */
287        class BvhTraversalData
288        { 
289        public:
290               
291                BvhTraversalData():
292                mNode(NULL),
293                mDepth(0),
294                mProbability(0.0),
295                mMaxCostMisses(0),
296                mPriority(0),
297                mAxis(0)
298                {}
299               
300                BvhTraversalData(BvhLeaf *node,
301                                                 const int depth,
302                                                 const AxisAlignedBox3 &box,
303                                                 const float v):
304                mNode(node),
305                mDepth(depth),
306                mBoundingBox(box),
307                mProbability(v),
308                mMaxCostMisses(0),
309                mPriority(0),
310                mAxis(0)
311                {}
312
313
314                /** Returns cost of the traversal data.
315                */
316                float GetCost() const
317                {
318                        return mPriority;
319                }
320
321                /// deletes contents and sets them to NULL
322                void Clear()
323                {
324                        DEL_PTR(mNode);
325                }
326
327                /// the current node
328                BvhLeaf *mNode;
329                /// current depth
330                int mDepth;
331                /// the probability that this node is seen
332                float mProbability;
333                /// the bounding box of the node
334                AxisAlignedBox3 mBoundingBox;
335                /// how often this branch has missed the max-cost ratio
336                int mMaxCostMisses;
337                /// current axis
338                int mAxis;
339                /// current priority
340                float mPriority;
341
342
343                friend bool operator<(const BvhTraversalData &a, const BvhTraversalData &b)
344                {
345                        return a.GetCost() < b.GetCost();
346                }
347    };
348
349        /** Candidate for a view space split.
350        */
351        class BvhSubdivisionCandidate: public SubdivisionCandidate
352        { 
353        public:
354
355        BvhSubdivisionCandidate(const BvhTraversalData &tData): mParentData(tData)
356                {};
357
358                ~BvhSubdivisionCandidate()
359                {
360                        mParentData.Clear();
361                }
362
363                int Type() const { return OBJECT_SPACE; }
364       
365                void EvalPriority()
366                {
367                        sBvHierarchy->EvalSubdivisionCandidate(*this); 
368                }
369
370                bool GlobalTerminationCriteriaMet() const
371                {
372                        return sBvHierarchy->GlobalTerminationCriteriaMet(mParentData);
373                }
374
375                BvhSubdivisionCandidate(
376                        const ObjectContainer &frontObjects,
377                        const ObjectContainer &backObjects,
378                        const BvhTraversalData &tData):
379                mFrontObjects(frontObjects), mBackObjects(backObjects), mParentData(tData)
380                {}
381
382                /// pointer to parent tree.
383                static BvHierarchy *sBvHierarchy;
384                /// parent data
385                BvhTraversalData mParentData;
386                /// the objects on the front of the potential split
387                ObjectContainer mFrontObjects;
388                /// the objects on the back of the potential split
389                ObjectContainer mBackObjects;
390        };
391
392        /** Struct for traversing line segment.
393        */
394        struct LineTraversalData
395        {
396                BvhNode *mNode;
397                Vector3 mExitPoint;
398               
399                float mMaxT;
400   
401                LineTraversalData () {}
402                LineTraversalData (BvhNode *n, const Vector3 &p, const float maxt):
403                mNode(n), mExitPoint(p), mMaxT(maxt) {}
404        };
405
406
407        /** Default constructor creating an empty tree.
408        */
409        BvHierarchy();
410
411        /** Default destructor.
412        */
413        ~BvHierarchy();
414
415        /** Returns tree statistics.
416        */
417        const BvhStatistics &GetStatistics() const;
418 
419        /** Returns bounding box of the specified node.
420        */
421        AxisAlignedBox3 GetBoundingBox(BvhNode *node) const;
422
423        /** Reads parameters from environment singleton.
424        */
425        void ReadEnvironment();
426
427        /** Evaluates candidate for splitting.
428        */
429        void EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitData);
430
431        /** Returns list of leaves with pvs smaller than
432                a certain threshold.
433                @param onlyUnmailed if only the unmailed leaves should be considered
434                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
435        */
436        void CollectLeaves(vector<BvhLeaf *> &leaves) const;
437
438        /** Returns bounding box of the whole tree (= bbox of root node)
439        */
440        AxisAlignedBox3 GetBoundingBox()const;
441
442        /** Returns root of the view space partitioning tree.
443        */
444        BvhNode *GetRoot() const;
445
446        /** A ray is cast possible intersecting the tree.
447                @param the ray that is cast.
448                @returns the number of intersections with objects stored in the tree.
449        */
450        //int CastRay(Ray &ray);
451
452        /** finds neighbouring leaves of this tree node.
453        */
454        int FindNeighbors(BvhLeaf *n,
455                                          vector<BvhLeaf *> &neighbors,
456                                          const bool onlyUnmailed) const;
457
458        /** Returns random leaf of BSP tree.
459                @param halfspace defines the halfspace from which the leaf is taken.
460        */
461        BvhLeaf *GetRandomLeaf(const Plane3 &halfspace);
462
463        /** Returns random leaf of BSP tree.
464                @param onlyUnmailed if only unmailed leaves should be returned.
465        */
466        BvhLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
467
468        /** Casts line segment into the tree.
469                @param origin the origin of the line segment
470                @param termination the end point of the line segment
471                @returns view cells intersecting the line segment.
472        */
473    int CastLineSegment(const Vector3 &origin,
474                                                const Vector3 &termination,
475                                                ViewCellContainer &viewcells);
476               
477        /** Sets pointer to view cells manager.
478        */
479        void SetViewCellsManager(ViewCellsManager *vcm);
480
481        /** Writes tree to output stream
482        */
483        bool Export(OUT_STREAM &stream);
484
485        /** Returns or creates a new intersectable for use in a kd based pvs.
486                The OspTree is responsible for destruction of the intersectable.
487        */
488        BvhIntersectable *GetOrCreateBvhIntersectable(BvhNode *node);
489
490        /** Collects rays.
491        */
492        void CollectRays(const ObjectContainer &objects, VssRayContainer &rays) const;
493
494        /** Intersects box with the tree and returns the number of intersected boxes.
495                @returns number of view cells found
496        */
497        int ComputeBoxIntersections(
498                const AxisAlignedBox3 &box,
499                ViewCellContainer &viewCells) const;
500
501
502        /** Returns leaf the point pt lies in, starting from root.
503        */
504        BvhLeaf *GetLeaf(Intersectable *obj, BvhNode *root = NULL) const;
505
506        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
507       
508        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
509
510        /** Add the bvh leaf to the pvs of the view cell.
511        */
512        bool AddLeafToPvs(
513                BvhLeaf *leaf,
514                ViewCell *vc,
515                const float pdf,
516                float &contribution);
517
518protected:
519
520        /** Returns true if tree can be terminated.
521        */
522        bool LocalTerminationCriteriaMet(const BvhTraversalData &data) const;
523
524        /** Returns true if global tree can be terminated.
525        */
526        bool GlobalTerminationCriteriaMet(const BvhTraversalData &data) const;
527
528        /** For sorting the objects during the heuristics
529        */
530        struct SortableEntry
531        {
532                Intersectable *mObject;
533                float mPos;
534
535                SortableEntry() {}
536
537                SortableEntry(Intersectable *obj, const float pos):
538                mObject(obj), mPos(pos)
539                {}
540
541                bool operator<(const SortableEntry &b) const
542                {
543                        return mPos < b.mPos;
544                }
545        };
546 
547        /** Evaluate balanced object partition.
548        */
549        float EvalLocalObjectPartition(
550                const BvhTraversalData &tData,
551                const int axis,
552                ObjectContainer &objectsFront,
553                ObjectContainer &objectsBack);
554
555        /** Computes priority of the traversal data and stores it in tData.
556        */
557        void EvalPriority(BvhTraversalData &tData) const;
558
559        /** Evaluates render cost of next split.
560        */
561        float EvalRenderCost(
562                const BvhTraversalData &tData,
563                const ObjectContainer &objectsLeft,
564                const ObjectContainer &objectsRight) const;
565
566        /** Evaluates tree stats in the BSP tree leafs.
567        */
568        void EvaluateLeafStats(const BvhTraversalData &data);
569
570        /** Subdivides node using a best split priority queue.
571            @param tQueue the best split priority queue
572                @param splitCandidate the candidate for the next split
573                @param globalCriteriaMet if the global termination criteria were already met
574                @returns new root of the subtree
575        */
576        BvhNode *Subdivide(
577                SplitQueue &tQueue,
578                SubdivisionCandidate *splitCandidate,
579                const bool globalCriteriaMet);
580       
581        /** Subdivides leaf.
582                @param leaf the leaf to be subdivided
583               
584                @param polys the polygons to be split
585                @param frontPolys returns the polygons in front of the split plane
586                @param backPolys returns the polygons in the back of the split plane
587               
588                @param rays the polygons to be filtered
589                @param frontRays returns the polygons in front of the split plane
590                @param backRays returns the polygons in the back of the split plane
591
592                @returns the root of the subdivision
593        */
594        BvhInterior *SubdivideNode(
595                const ObjectContainer &frontObjects,
596                const ObjectContainer &backObjects,
597                const BvhTraversalData &tData,
598                BvhTraversalData &frontData,
599                BvhTraversalData &backData);
600
601        /** Splits the objects for the next subdivision.
602                @returns cost for this split
603        */
604        float SelectObjectPartition(
605                const BvhTraversalData &tData,
606                ObjectContainer &frontObjects,
607                ObjectContainer &backObjects);
608       
609        /** Writes the node to disk
610                @note: should be implemented as visitor.
611        */
612        void ExportNode(BvhNode *node, OUT_STREAM &stream);
613
614        void ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream);
615
616        /** Returns estimated memory usage of tree.
617        */
618        float GetMemUsage() const;
619
620        /** Creates new root of hierarchy.
621        */
622        void CreateRoot(const ObjectContainer &objects);
623
624        /////////////////////////////
625        // Helper functions for local cost heuristics
626
627       
628        /** Sorts split candidates for cost heuristics using axis aligned splits.
629                @param node the current node
630                @param axis the current split axis
631        */
632        void SortSubdivisionCandidates(
633                const BvhTraversalData &data,
634                const int axis);
635
636        /** Computes best cost for axis aligned planes.
637        */
638        float EvalLocalCostHeuristics(
639                const BvhTraversalData &tData,
640                const int axis,
641                ObjectContainer &objectsFront,
642                ObjectContainer &objectsFBack);
643
644        /** Evaluates the contribution to the front and back volume
645                when this object is changing sides in the bvs.
646
647                @param object the object
648                @param volLeft updates the left pvs
649                @param volPvs updates the right pvs
650        */
651        void EvalHeuristicsContribution(
652                Intersectable *obj,
653                float &volLeft,
654                float &volRight);
655
656        /** Prepares objects for the cost heuristics.
657                @returns sum of volume of associated view cells
658        */
659        float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
660       
661
662        ////////////////////////////////////////////////
663
664
665        /** Prepares construction for vsp and osp trees.
666        */
667        AxisAlignedBox3 ComputeBoundingBox(
668                const ObjectContainer &objects,
669                const AxisAlignedBox3 *parentBox = NULL);
670
671        void CollectDirtyCandidates(
672                BvhSubdivisionCandidate *sc,
673                vector<SubdivisionCandidate *> &dirtyList);
674
675        /** Collect view cells which see this bvh leaf.
676        */
677        void CollectViewCells(
678                const ObjectContainer &objects,
679                ViewCellContainer &viewCells,
680                const bool setCounter = false) const;
681
682        /** Collects view cells which see an object.
683        */
684        void CollectViewCells(
685                Intersectable *object,
686                ViewCellContainer &viewCells,
687                const bool useMailBoxing,
688                const bool setCounter = false) const;
689
690        /** Rays will be clipped to the bounding box.
691        */
692        void PreprocessRays(
693                BvhLeaf *root,
694                const VssRayContainer &sampleRays,
695                RayInfoContainer &rays);
696
697        /** Print the subdivision stats in the subdivison log.
698        */
699        void PrintSubdivisionStats(const SubdivisionCandidate &tData);
700
701        void AddSubdivisionStats(
702                const int viewCells,
703                const float renderCostDecr,
704                const float totalRenderCost);
705
706        void AssociateObjectsWithRays(const VssRayContainer &rays);
707
708        bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;
709
710        SubdivisionCandidate *PrepareConstruction(
711                const VssRayContainer &sampleRays,
712                const ObjectContainer &objects
713                );
714
715        float EvalViewCellsVolume(const ObjectContainer &objects) const;
716
717
718protected:
719       
720        /// pointer to the hierarchy of view cells
721        ViewCellsTree *mViewCellsTree;
722
723        VspTree *mVspTree;
724
725        /// The view cells manager
726        ViewCellsManager *mViewCellsManager;
727
728        /// candidates for placing split planes during cost heuristics
729        vector<SortableEntry> *mSubdivisionCandidates;
730
731        /// Pointer to the root of the tree
732        BvhNode *mRoot;
733               
734        /// Statistics for the object space partition
735        BvhStatistics mBvhStats;
736       
737        /// box around the whole view domain
738        AxisAlignedBox3 mBoundingBox;
739
740
741        //-- local termination
742
743        /// maximal possible depth
744        int mTermMaxDepth;
745        /// mininum probability
746        float mTermMinProbability;
747        /// minimal number of objects
748        int mTermMinObjects;
749        /// maximal contribution per ray
750        float mTermMaxRayContribution;
751        /// maximal acceptable cost ratio
752        float mTermMaxCostRatio;
753        /// tolerance value indicating how often the max cost ratio can be failed
754        int mTermMissTolerance;
755
756
757        //-- global criteria
758
759        float mTermMinGlobalCostRatio;
760        int mTermGlobalCostMissTolerance;
761        int mGlobalCostMisses;
762
763        /// maximal number of view cells
764        int mTermMaxLeaves;
765        /// maximal tree memory
766        float mMaxMemory;
767        /// the tree is out of memory
768        bool mOutOfMemory;
769
770
771        //-- split heuristics based parameters
772       
773        bool mUseCostHeuristics;
774        /// balancing factor for PVS criterium
775        float mCtDivCi;
776        /// if only driving axis should be used for split
777        bool mOnlyDrivingAxis;
778       
779        /// current time stamp (used for keeping split history)
780        int mTimeStamp;
781        // if rays should be stored in leaves
782        bool mStoreRays;
783
784        /// epsilon for geometric comparisons
785        float mEpsilon;
786
787        /// subdivision stats output file
788        ofstream  mSubdivisionStats;
789        /// keeps track of cost during subdivision
790        float mTotalCost;
791        /// keeps track of overall pvs size during subdivision
792        int mTotalPvsSize;
793        /// number of currenly generated view cells
794        int mCreatedLeaves;
795
796        /// represents min and max band for sweep
797        float mSplitBorder;
798
799        /// weight between render cost decrease and node render cost
800        float mRenderCostDecreaseWeight;
801
802        /// stores the kd node intersectables used for pvs
803        BvhIntersectableMap mBvhIntersectables;
804
805};
806
807}
808
809#endif
Note: See TracBrowser for help on using the repository browser.