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

Revision 2199, 26.8 KB checked in by mattausch, 17 years ago (diff)

using mutationsamples for evaluation

RevLine 
[1237]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"
[1239]12#include "SubdivisionCandidate.h"
[1237]13#include "AxisAlignedBox3.h"
[1315]14#include "IntersectableWrapper.h"
[1667]15#include "HierarchyManager.h"
[2187]16#include "PerfTimer.h"
[1237]17
18
19namespace GtpVisibilityPreprocessor {
20
21
22class ViewCellLeaf;
23class Plane3;
24class AxisAlignedBox3;
25class Ray;
26class ViewCellsStatistics;
27class ViewCellsManager;
28class MergeCandidate;
29class Beam;
30class ViewCellsTree;
31class Environment;
32class BvhInterior;
33class BvhLeaf;
34class BvhNode;
35class BvhTree;
36class VspTree;
[1370]37class HierarchyManager;
[1237]38
[1297]39
[1237]40/** View space partition statistics.
41*/
42class BvhStatistics: public StatisticsBase
43{
44public:
[1370]45       
46        /// Constructor
[1237]47        BvhStatistics()
48        {
49                Reset();
50        }
51
52        int Nodes() const {return nodes;}
53        int Interior() const { return nodes / 2; }
54        int Leaves() const { return (nodes / 2) + 1; }
55       
56        double AvgDepth() const
57        { return accumDepth / (double)Leaves(); }
58
[1370]59        double AvgObjectRefs() const
60        { return objectRefs / (double)Leaves(); }
61
62        double AvgRayRefs() const
63        { return rayRefs / (double)Leaves(); }
64
[1763]65       
[1237]66        void Reset()
67        {
68                nodes = 0;
69                splits = 0;
70                maxDepth = 0;
[1705]71
[1237]72                minDepth = 99999;
73                accumDepth = 0;
74        maxDepthNodes = 0;
75                minProbabilityNodes = 0;
76                maxCostNodes = 0;
[1370]77                ///////////////////
78                minObjectsNodes = 0;
[1237]79                maxObjectRefs = 0;
[1370]80                minObjectRefs = 999999999;
[1237]81                objectRefs = 0;
[1408]82                emptyNodes = 0;
[1370]83
84                ///////////////////
85                minRaysNodes = 0;
86                maxRayRefs = 0;
87                minRayRefs = 999999999;
88                rayRefs = 0;
89                maxRayContriNodes = 0;
[1449]90                mGlobalCostMisses = 0;
[1237]91        }
92
[1370]93
94public:
95
96        // total number of nodes
97        int nodes;
98        // number of splits
99        int splits;
100        // maximal reached depth
101        int maxDepth;
102        // minimal depth
103        int minDepth;
104        // max depth nodes
105        int maxDepthNodes;
106        // accumulated depth (used to compute average)
107        int accumDepth;
108        // minimum area nodes
109        int minProbabilityNodes;
110        /// nodes termination because of max cost ratio;
111        int maxCostNodes;
[1449]112        // global cost ratio violations
113        int mGlobalCostMisses;
[1370]114
[1449]115        //////////////////
[1370]116        // nodes with minimum objects
117        int minObjectsNodes;
118        // max number of rays per node
119        int maxObjectRefs;
120        // min number of rays per node
121        int minObjectRefs;
122        /// object references
123        int objectRefs;
[1408]124        // leaves with no objects
125        int emptyNodes;
[1370]126
127        //////////////////////////
128        // nodes with minimum rays
129        int minRaysNodes;
130        // max number of rays per node
131        int maxRayRefs;
132        // min number of rays per node
133        int minRayRefs;
134        /// object references
135        int rayRefs;
136        /// nodes with max ray contribution
137        int maxRayContriNodes;
138
[2176]139        void Print(std::ostream &app) const;
[1237]140
[2176]141        friend std::ostream &operator<<(std::ostream &s, const BvhStatistics &stat)
[1237]142        {
143                stat.Print(s);
144                return s;
145        }
146};
147
148
149/**
150    VspNode abstract class serving for interior and leaf node implementation
151*/
[1758]152class BvhNode: public Intersectable
[1237]153{
154public:
155       
156        // types of vsp nodes
157        enum {Interior, Leaf};
158
[1297]159        BvhNode();
[1237]160        BvhNode(const AxisAlignedBox3 &bbox);
161        BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent);
162
163        virtual ~BvhNode(){};
164
165        /** Determines whether this node is a leaf or not
166                @return true if leaf
167        */
168        virtual bool IsLeaf() const = 0;
169
170        /** Determines whether this node is a root
171                @return true if root
172        */
173        virtual bool IsRoot() const;
174
175        /** Returns parent node.
176        */
177        BvhInterior *GetParent();
178
179        /** Sets parent node.
180        */
181        void SetParent(BvhInterior *parent);
182
[1666]183        /** collects all objects under this node.
184        */
[1614]185        virtual void CollectObjects(ObjectContainer &objects) = 0;
[1666]186
[1237]187        /** The bounding box specifies the node extent.
188        */
[1357]189        inline
[1237]190        AxisAlignedBox3 GetBoundingBox() const
191        { return mBoundingBox; }
192
[1666]193        /** Sets bouding box of this node.
194        */
[1357]195        inline
[1237]196        void SetBoundingBox(const AxisAlignedBox3 &boundingBox)
197        { mBoundingBox = boundingBox; }
198
[1679]199        /** Cost of mergin this node.
200        */
201        float GetMergeCost() {return (float)-mTimeStamp; }
[1237]202
[2115]203        virtual int GetRandomEdgePoint(Vector3 &point, Vector3 &normal);
[1666]204
[1763]205        inline int GetTimeStamp() const { return mTimeStamp; }
206        inline void SetTimeStamp(const int timeStamp) { mTimeStamp = timeStamp; };
207
[1237]208
[1786]209        ////////////////////////
[1758]210        //-- inherited functions from Intersectable
211
212        AxisAlignedBox3 GetBox() const { return mBoundingBox; }
213       
214        int CastRay(Ray &ray) { return 0; }
215       
216        bool IsConvex() const { return true; }
217        bool IsWatertight() const { return true; }
218        float IntersectionComplexity() { return 1; }
219 
220        int NumberOfFaces() const { return 6; };
221       
[2115]222        int GetRandomSurfacePoint(GtpVisibilityPreprocessor::Vector3 &point,
[1758]223                                                          GtpVisibilityPreprocessor::Vector3 &normal)
224        {
225                // TODO
226                return 0;
227        }
228
229        int GetRandomVisibleSurfacePoint(GtpVisibilityPreprocessor::Vector3 &point,
230                                                                         GtpVisibilityPreprocessor::Vector3 &normal,
231                                                                         const GtpVisibilityPreprocessor::Vector3 &viewpoint,
232                                                                         const int maxTries)
233        {
234                // TODO
235                return 0;
236        }
237 
238        int Type() const
239        {
240                return Intersectable::BVH_INTERSECTABLE;
241        }
242
[2176]243        std::ostream &Describe(std::ostream &s) { return s; }
[1758]244
[1237]245        ///////////////////////////////////
246
[1786]247        float mRenderCost;
248
[1237]249protected:
250       
251        /// the bounding box of the node
252        AxisAlignedBox3 mBoundingBox;
253        /// parent of this node
254        BvhInterior *mParent;
[1763]255        int mTimeStamp;
[1237]256};
257
258
259/** BSP interior node implementation
260*/
261class BvhInterior: public BvhNode
262{
263public:
264        /** Standard contructor taking a bounding box as argument.
265        */
266        BvhInterior(const AxisAlignedBox3 &bbox);
267        BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent);
268
269        ~BvhInterior();
270        /** @return false since it is an interior node
271        */
272        bool IsLeaf() const;
[1294]273       
[1237]274        BvhNode *GetBack() { return mBack; }
275        BvhNode *GetFront() { return mFront; }
276
277        /** Replace front or back child with new child.
278        */
279        void ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild);
280
281        /** Replace front and back child.
282        */
283        void SetupChildLinks(BvhNode *front, BvhNode *back);
284
[2176]285        friend std::ostream &operator<<(std::ostream &s, const BvhInterior &A)
[1237]286        {
287                return s << A.mBoundingBox;
288        }
[1679]289
290        virtual void CollectObjects(ObjectContainer &objects);
[1684]291
[1237]292protected:
293
294        /// back node
295        BvhNode *mBack;
296        /// front node
297        BvhNode *mFront;
298};
299
300
301/** BSP leaf node implementation.
302*/
303class BvhLeaf: public BvhNode
304{
305public:
306        /** Standard contructor taking a bounding box as argument.
307        */
308        BvhLeaf(const AxisAlignedBox3 &bbox);
[1920]309        BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent);
[1237]310        BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent, const int numObjects);
311
312        ~BvhLeaf();
313
314        /** @return true since it is an interior node
315        */
316        bool IsLeaf() const;
317       
[1297]318        SubdivisionCandidate *GetSubdivisionCandidate()// const
[1237]319        {
320                return mSubdivisionCandidate;
321        }
322
[1297]323        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
324        {
325                mSubdivisionCandidate = candidate;
326        }
[1684]327       
328        virtual void CollectObjects(ObjectContainer &objects);
329
[1707]330        /** Returns level of the hierarchy that is "active" right now.
[1706]331        */
332        BvhNode *GetActiveNode()
333        {
334                return mActiveNode;
335        }
336
[1707]337        /** Returns level of the hierarchy that is "active" right now.
338        */
339        void SetActiveNode(BvhNode *node)
340        {
341                mActiveNode = node;
342        }
343
[1237]344public:
[1785]345  // gl list use to store the geometry on the gl server
346  int mGlList;
347 
348  /// objects
349  ObjectContainer mObjects;
350 
[1920]351 
[1237]352protected:
[1785]353 
354  /// pointer to a split plane candidate splitting this leaf
355  SubdivisionCandidate *mSubdivisionCandidate;
356 
357  /// the active node which will be accounted for in the pvs
358  BvhNode *mActiveNode;
[1237]359};
360
361
362/** View Space Partitioning tree.
363*/
364class BvHierarchy
365{
366        friend class ViewCellsParseHandlers;
[2119]367        friend class ObjectsParseHandlers;
[1237]368        friend class HierarchyManager;
369
[1379]370protected:
[1345]371        struct SortableEntry;
372        typedef vector<SortableEntry> SortableEntryContainer;
373
[1379]374public:
375       
[1237]376        /** Additional data which is passed down the BSP tree during traversal.
377        */
378        class BvhTraversalData
379        { 
380        public:
[1294]381               
[1237]382                BvhTraversalData():
383                mNode(NULL),
384                mDepth(0),
385                mMaxCostMisses(0),
[1370]386                mAxis(0),
[1912]387                mNumRays(0),
388                mCorrectedPvs(0),
389                mPvs(0),
[1913]390                mCorrectedVolume(0),
391                mVolume(0)
[1357]392                {
[1778]393                        for (int i = 0; i < 4; ++ i)
394                                mSortedObjects[i] = NULL;
[1357]395                }
[1237]396               
397                BvhTraversalData(BvhLeaf *node,
398                                                 const int depth,
[1370]399                                                 const float v,
400                                                 const int numRays):
[1237]401                mNode(node),
402                mDepth(depth),
403                mMaxCostMisses(0),
[1370]404                mAxis(0),
[1912]405                mNumRays(numRays),
406                mCorrectedPvs(0),
407                mPvs(0),
[1913]408                mCorrectedVolume(0),
409                mVolume(v)
[1357]410                {
[1778]411                        for (int i = 0; i < 4; ++ i)
412                                mSortedObjects[i] = NULL;
[1357]413                }
[1237]414
[1357]415                /** Deletes contents and sets them to NULL.
416                */
[1237]417                void Clear()
418                {
[1294]419                        DEL_PTR(mNode);
[1778]420                        for (int i = 0; i < 4; ++ i)
421                                DEL_PTR(mSortedObjects[i]);
[1237]422                }
423
[1294]424                /// the current node
425                BvhLeaf *mNode;
426                /// current depth
427                int mDepth;
[1913]428                /// the volume of the node
429                float mVolume;
430                /// the corrected volume
431                float mCorrectedVolume;
[1294]432                /// how often this branch has missed the max-cost ratio
433                int mMaxCostMisses;
434                /// current axis
435                int mAxis;
[1370]436                /// number of rays
437                int mNumRays;
[1912]438                /// parent Pvs;
439                float mPvs;
440                /// parent pvs correction factor
441                float mCorrectedPvs;
442
[1357]443                /// the sorted objects for the three dimensions
[1778]444                ObjectContainer *mSortedObjects[4];             
[1237]445    };
446
[1357]447
448        /** Candidate for a object space split.
[1237]449        */
450        class BvhSubdivisionCandidate: public SubdivisionCandidate
451        { 
452        public:
453
[1294]454        BvhSubdivisionCandidate(const BvhTraversalData &tData): mParentData(tData)
[1237]455                {};
456
[1305]457                ~BvhSubdivisionCandidate()
458                {
459                        mParentData.Clear();
460                }
[1294]461
[1237]462                int Type() const { return OBJECT_SPACE; }
463       
[1667]464                void EvalCandidate(bool computeSplitplane = true)
[1237]465                {
[1705]466            mDirty = false;
[1667]467                        sBvHierarchy->EvalSubdivisionCandidate(*this, computeSplitplane);
[1237]468                }
469
[1633]470                bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet)
[1632]471                {
[1667]472                        BvhNode *n = sBvHierarchy->Subdivide(splitQueue, this, terminationCriteriaMet);
473
[1632]474                        // local or global termination criteria failed
475                        return !n->IsLeaf();           
[1633]476                }
[1632]477
[1633]478                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
479                                                                        const bool onlyUnmailed)
480                {
481                        sBvHierarchy->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
482                }
483
[1237]484                bool GlobalTerminationCriteriaMet() const
485                {
486                        return sBvHierarchy->GlobalTerminationCriteriaMet(mParentData);
487                }
488
[1667]489                BvhSubdivisionCandidate(const ObjectContainer &frontObjects,
490                                                                const ObjectContainer &backObjects,
491                                                                const BvhTraversalData &tData):
[1237]492                mFrontObjects(frontObjects), mBackObjects(backObjects), mParentData(tData)
493                {}
[1294]494
[1667]495                float GetPriority() const
496                {
[2187]497                        //return (float)-mParentData.mDepth;
498                        return mPriority;
[1667]499                }
500
[1912]501                /////////////////////////////7
502
[1305]503                /// pointer to parent tree.
[1294]504                static BvHierarchy *sBvHierarchy;
[1680]505
[1294]506                /// parent data
507                BvhTraversalData mParentData;
[1305]508                /// the objects on the front of the potential split
[1294]509                ObjectContainer mFrontObjects;
[1305]510                /// the objects on the back of the potential split
[1294]511                ObjectContainer mBackObjects;
[1912]512                       
513                float mCorrectedFrontPvs;
514                float mCorrectedBackPvs;
515
[1913]516                float mCorrectedFrontVolume;
517                float mCorrectedBackVolume;
[1237]518        };
519
520        /** Struct for traversing line segment.
521        */
522        struct LineTraversalData
523        {
524                BvhNode *mNode;
525                Vector3 mExitPoint;
526               
527                float mMaxT;
528   
529                LineTraversalData () {}
530                LineTraversalData (BvhNode *n, const Vector3 &p, const float maxt):
531                mNode(n), mExitPoint(p), mMaxT(maxt) {}
532        };
533
534
535        /** Default constructor creating an empty tree.
536        */
537        BvHierarchy();
538
539        /** Default destructor.
540        */
541        ~BvHierarchy();
542
543        /** Returns tree statistics.
544        */
545        const BvhStatistics &GetStatistics() const;
546 
547        /** Returns bounding box of the specified node.
548        */
549        AxisAlignedBox3 GetBoundingBox(BvhNode *node) const;
550
551        /** Reads parameters from environment singleton.
552        */
553        void ReadEnvironment();
554
555        /** Evaluates candidate for splitting.
556        */
[1680]557        void EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitData,
558                                                                  bool computeSplitPlane = true);
[1237]559
[1707]560        /** Returns vector of leaves.
[1237]561        */
[1707]562        void CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const;
[1237]563
[2093]564        /** Returns vector of leaves.
565        */
566        void CollectNodes(BvhNode *root, vector<BvhNode *> &nodes) const;
567
[1237]568        /** Returns bounding box of the whole tree (= bbox of root node)
569        */
570        AxisAlignedBox3 GetBoundingBox()const;
571
572        /** Returns root of the view space partitioning tree.
573        */
574        BvhNode *GetRoot() const;
575
576        /** finds neighbouring leaves of this tree node.
577        */
578        int FindNeighbors(BvhLeaf *n,
579                                          vector<BvhLeaf *> &neighbors,
580                                          const bool onlyUnmailed) const;
581
582        /** Returns random leaf of BSP tree.
583                @param halfspace defines the halfspace from which the leaf is taken.
584        */
585        BvhLeaf *GetRandomLeaf(const Plane3 &halfspace);
586
587        /** Returns random leaf of BSP tree.
588                @param onlyUnmailed if only unmailed leaves should be returned.
589        */
590        BvhLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
591
592        /** Casts line segment into the tree.
593                @param origin the origin of the line segment
594                @param termination the end point of the line segment
595                @returns view cells intersecting the line segment.
596        */
597    int CastLineSegment(const Vector3 &origin,
598                                                const Vector3 &termination,
599                                                ViewCellContainer &viewcells);
600               
601        /** Sets pointer to view cells manager.
602        */
603        void SetViewCellsManager(ViewCellsManager *vcm);
604
[1913]605        float GetViewSpaceVolume() const;
[1237]606        /** Writes tree to output stream
607        */
608        bool Export(OUT_STREAM &stream);
609
[1640]610        /** Collects rays associated with the objects.
[1237]611        */
612        void CollectRays(const ObjectContainer &objects, VssRayContainer &rays) const;
613
614        /** Intersects box with the tree and returns the number of intersected boxes.
615                @returns number of view cells found
616        */
[1640]617        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
618                                                                ViewCellContainer &viewCells) const;
[1237]619
620        /** Returns leaf the point pt lies in, starting from root.
621        */
622        BvhLeaf *GetLeaf(Intersectable *obj, BvhNode *root = NULL) const;
623
[1370]624        /** Sets a pointer to the view cells tree.
625        */
[1237]626        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
[1707]627       
[1370]628        /** See Get
629        */
[1237]630        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
631
[1640]632        /** Returns estimated memory usage of tree.
633        */
634        float GetMemUsage() const;
[1237]635
[1707]636        /** Sets this node to be an active node.
637        */
638        void SetActive(BvhNode *node) const;
[1680]639
[1707]640
[1684]641        ///////////////////////////
642        // hacks in order to provide interleaved heurisitcs
643
[1686]644        BvhNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
[1684]645
646        /////////////////////////////////
647
[1703]648        static float EvalAbsCost(const ObjectContainer &objects);
[1698]649
[1718]650        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
[1707]651
[1786]652        float GetRenderCostIncrementially(BvhNode *node) const;
653
[1844]654        void Compress();
[1843]655        void CreateUniqueObjectIds();
[1786]656
[2187]657        PerfTimer mNodeTimer;
658        PerfTimer mSubdivTimer;
659        PerfTimer mEvalTimer;
660        PerfTimer mSplitTimer;
[2198]661        PerfTimer mPlaneTimer;
[2199]662        PerfTimer mSortTimer;
[2198]663        PerfTimer mCollectTimer;
[2187]664
[1237]665protected:
666
667        /** Returns true if tree can be terminated.
668        */
[1251]669        bool LocalTerminationCriteriaMet(const BvhTraversalData &data) const;
[1237]670
671        /** Returns true if global tree can be terminated.
672        */
[1251]673        bool GlobalTerminationCriteriaMet(const BvhTraversalData &data) const;
[1237]674
[1287]675        /** For sorting the objects during the heuristics
676        */
[1237]677        struct SortableEntry
678        {
[1287]679                Intersectable *mObject;
[1237]680                float mPos;
681
682                SortableEntry() {}
683
[1287]684                SortableEntry(Intersectable *obj, const float pos):
685                mObject(obj), mPos(pos)
[1237]686                {}
687
688                bool operator<(const SortableEntry &b) const
689                {
690                        return mPos < b.mPos;
691                }
692        };
[1345]693
[1287]694        /** Evaluate balanced object partition.
[1237]695        */
[1640]696        float EvalLocalObjectPartition(const BvhTraversalData &tData,
697                                                                   const int axis,
698                                                                   ObjectContainer &objectsFront,
699                                                                   ObjectContainer &objectsBack);
[1237]700
[1640]701        /** Evaluate surface area heuristic for the node.
702        */
703        float EvalSah(const BvhTraversalData &tData,
704                                  const int axis,
705                                  ObjectContainer &objectsFront,
706                                  ObjectContainer &objectsBack);
[1323]707
[1237]708
[1379]709        /** Evaluates render cost of the bv induced by these objects
[1237]710        */
[2198]711        float EvalRenderCost(const ObjectContainer &objects);// const;
[1237]712
713        /** Evaluates tree stats in the BSP tree leafs.
714        */
715        void EvaluateLeafStats(const BvhTraversalData &data);
716
717        /** Subdivides node using a best split priority queue.
718            @param tQueue the best split priority queue
719                @param splitCandidate the candidate for the next split
720                @param globalCriteriaMet if the global termination criteria were already met
721                @returns new root of the subtree
722        */
[1640]723        BvhNode *Subdivide(SplitQueue &tQueue,
724                                           SubdivisionCandidate *splitCandidate,
725                                           const bool globalCriteriaMet);
[1237]726       
727        /** Subdivides leaf.
[1345]728                @param sc the subdivisionCandidate holding all necessary data for subdivision           
[1237]729               
[1345]730                @param frontData returns the traversal data for the front node
731                @param backData returns the traversal data for the back node
[1237]732
[1345]733                @returns the new interior node = the of the subdivision
[1237]734        */
[1640]735        BvhInterior *SubdivideNode(const BvhSubdivisionCandidate &sc,
736                                                           BvhTraversalData &frontData,
737                                                           BvhTraversalData &backData);
[1237]738
739        /** Splits the objects for the next subdivision.
740                @returns cost for this split
741        */
[1640]742        float SelectObjectPartition(const BvhTraversalData &tData,
743                                                                ObjectContainer &frontObjects,
[1676]744                                                                ObjectContainer &backObjects,
745                                                                bool useVisibilityBasedHeuristics);
[1237]746       
747        /** Writes the node to disk
748                @note: should be implemented as visitor.
749        */
750        void ExportNode(BvhNode *node, OUT_STREAM &stream);
751
[1640]752        /** Exports objects associated with this leaf.
753        */
[1286]754        void ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream);
755
[1548]756        /** Associates the objects with their bvh leaves.
[1294]757        */
[1486]758        static void AssociateObjectsWithLeaf(BvhLeaf *leaf);
759
[2198]760       
[1237]761        /////////////////////////////
762        // Helper functions for local cost heuristics
763       
[1357]764        /** Prepare split candidates for cost heuristics using axis aligned splits.
[1237]765                @param node the current node
766                @param axis the current split axis
767        */
[1640]768        void PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
769                                                                                   const int axis);
[1237]770
[1640]771        static void CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
772                                                                                                 SortableEntryContainer **subdivisionCandidates,
773                                                                                                 const bool sort,
774                                                                                                 const int axis);
[1357]775
[1779]776        float EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
777                                           const float renderCostDecr,
778                                           const float oldRenderCost) const;
779
[1357]780        /** Computes object partition with the best cost according to the heurisics.
781                @param tData the traversal data
782                @param axis the split axis
783                @param objectsFront the objects in the front child bv
784                @param objectsBack the objects in the back child bv
785                @param backObjectsStart the iterator marking the position where the back objects begin
786
787                @returns relative cost (relative to parent cost)
[1237]788        */
[1640]789        float EvalLocalCostHeuristics(const BvhTraversalData &tData,
790                                                                  const int axis,
791                                                                  ObjectContainer &objectsFront,
792                                                                  ObjectContainer &objectsBack);
[1237]793
[1287]794        /** Evaluates the contribution to the front and back volume
795                when this object is changing sides in the bvs.
[1237]796
[1287]797                @param object the object
798                @param volLeft updates the left pvs
799                @param volPvs updates the right pvs
[1237]800        */
[1640]801        void EvalHeuristicsContribution(Intersectable *obj,
802                                                                        float &volLeft,
803                                                                        float &volRight);
[1237]804
805        /** Prepares objects for the cost heuristics.
806                @returns sum of volume of associated view cells
807        */
[1287]808        float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
[1237]809       
[1705]810        /** Evaluates cost for a leaf given the surface area heuristics.
811        */
[1779]812        float EvalSahCost(BvhLeaf *leaf) const;
[1633]813
[1237]814        ////////////////////////////////////////////////
815
816
817        /** Prepares construction for vsp and osp trees.
818        */
[1640]819        AxisAlignedBox3 EvalBoundingBox(const ObjectContainer &objects,
820                                                                        const AxisAlignedBox3 *parentBox = NULL) const;
[1237]821
[1370]822        /** Collects list of invalid candidates. Candidates
823                are invalidated by a view space subdivision step
824                that affects this candidate.
825        */
[1640]826        void CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
827                                                                vector<SubdivisionCandidate *> &dirtyList,
828                                                                const bool onlyUnmailed);
[1237]829
[1287]830        /** Collect view cells which see this bvh leaf.
[1237]831        */
[1744]832        int CollectViewCells(const ObjectContainer &objects,
833                                                 ViewCellContainer &viewCells,
834                                                 const bool setCounter,
[2198]835                                                 const bool onlyUnmailedRays);// const;
[1237]836
[1933]837        /** Collects view cells which see an object.
838                @param useMailBoxing if mailing should be used and
839                only unmailed object should pass
840                @param setCounter counter for the sweep algorithm
[1941]841                @param onlyUnmailedRays if only unmailed rays should be considered
[1933]842        */
843        int CollectViewCells(Intersectable *object,
844                                                 ViewCellContainer &viewCells,
845                                                 const bool useMailBoxing,
846                                                 const bool setCounter,
[2198]847                                                 const bool onlyUnmailedRays);// const;
[1933]848
[1576]849        /** Counts the view cells of this object. note: only
850                counts unmailed objects.
851        */
[2198]852        int CountViewCells(Intersectable *obj);// const;
[1576]853
854        /** Counts the view cells seen by this bvh leaf
855        */
[2198]856        int CountViewCells(const ObjectContainer &objects);// const;
[1576]857
[2198]858#if STORE_VIEWCELLS_WITH_BVH
859
860        int AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const;
861
862        void AssociateViewCellsWithObjects(const ObjectContainer &objects) const;
863
864        void ReleaseViewCells(const ObjectContainer &objects);
865
866        int CollectViewCellsFromRays(Intersectable *obj,
867                                                                 ViewCellContainer &viewCells,
868                                                                 const bool useMailBoxing,
869                                                                 const bool setCounter,
870                                                                 const bool onlyUnmailedRays);
871
872        int CountViewCellsFromRays(Intersectable *obj);
873#endif
874
[1576]875        /** Evaluates increase in pvs size.
876        */
[2198]877        int EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate,
878                                                   const float avgRayContri);// const;
[1576]879
[1237]880        /** Rays will be clipped to the bounding box.
881        */
[1640]882        void PreprocessRays(BvhLeaf *root,
883                                                const VssRayContainer &sampleRays,
884                                                RayInfoContainer &rays);
[1237]885
[1287]886        /** Print the subdivision stats in the subdivison log.
887        */
888        void PrintSubdivisionStats(const SubdivisionCandidate &tData);
[1237]889
[1370]890        /** Prints out the stats for this subdivision.
891        */
[1640]892        void AddSubdivisionStats(const int viewCells,
893                                                         const float renderCostDecr,
894                                                         const float totalRenderCost);
[1237]895
[1370]896        /** Stores rays with objects that see the rays.
897        */
898        int AssociateObjectsWithRays(const VssRayContainer &rays) const;
[1237]899
[1370]900        /** Tests if object is in this leaf.
901                @note: assumes that objects are sorted by their id.
902        */
[1237]903        bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;
904
[1370]905        /** Prepares the construction of the bv hierarchy and returns
906                the first subdivision candidate.
907        */
[1779]908        void PrepareConstruction(SplitQueue &tQueue,
909                                                         const VssRayContainer &sampleRays,
910                                                         const ObjectContainer &objects);
[1237]911
[1548]912        /** Resets bv hierarchy. E.g. deletes root and resets stats.
913        */
[1779]914        void Reset(SplitQueue &tQueue,
915                           const VssRayContainer &rays,
916                           const ObjectContainer &objects);
[1548]917
[1370]918        /** Evaluates volume of view cells that see the objects.
919        */
[2198]920        float EvalViewCellsVolume(const ObjectContainer &objects);// const;
[1237]921
[1580]922        /** Assigns or newly creates initial list of sorted objects.
[1370]923        */
[1779]924        void AssignInitialSortedObjectList(BvhTraversalData &tData,
925                                                                           const ObjectContainer &objects);
[1259]926
[1370]927        /** Assigns sorted objects to front and back data.
928        */
[1640]929        void AssignSortedObjects(const BvhSubdivisionCandidate &sc,
930                                                         BvhTraversalData &frontData,
931                                                         BvhTraversalData &backData);
[1548]932       
[1640]933        /** Creates new root of hierarchy and computes bounding box.
934                Has to be called before the preparation of the subdivision.
[1548]935        */
[1640]936        void Initialise(const ObjectContainer &objects);
937
938
[1779]939        ////////////////////
[1774]940        // initial subdivision
941
942        /** Makes an initial parititon of the object space based on
943                some criteria (size, shader)
944        */
[1779]945        void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
[1789]946                                                                 vector<SubdivisionCandidate *> &candidateContainer);
[1774]947
[1784]948        void ApplyInitialSplit(const BvhTraversalData &tData,
949                                                   ObjectContainer &frontObjects,
950                                                   ObjectContainer &backObjects);
[1774]951
[1779]952        bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;
953
[2093]954        /** Sets the bvh node ids.
955        */
956        void SetUniqueNodeIds();
[1779]957
[1237]958protected:
959       
[1345]960        /// pre-sorted subdivision candidtes for all three directions.
961        vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
[1237]962        /// pointer to the hierarchy of view cells
963        ViewCellsTree *mViewCellsTree;
964        /// The view cells manager
965        ViewCellsManager *mViewCellsManager;
966        /// candidates for placing split planes during cost heuristics
967        vector<SortableEntry> *mSubdivisionCandidates;
968        /// Pointer to the root of the tree
969        BvhNode *mRoot;
970        /// Statistics for the object space partition
[1370]971        BvhStatistics mBvhStats;       
[1237]972        /// box around the whole view domain
973        AxisAlignedBox3 mBoundingBox;
[1370]974        /// the hierarchy manager
975        HierarchyManager *mHierarchyManager;
[1237]976
977
[1449]978        ////////////////////
[1357]979        //-- local termination criteria
[1237]980
981        /// maximal possible depth
982        int mTermMaxDepth;
983        /// mininum probability
[1287]984        float mTermMinProbability;
[1237]985        /// minimal number of objects
986        int mTermMinObjects;
987        /// maximal acceptable cost ratio
988        float mTermMaxCostRatio;
989        /// tolerance value indicating how often the max cost ratio can be failed
990        int mTermMissTolerance;
[1370]991        /// minimum number of rays
992        int mTermMinRays;
[1237]993
994
[1449]995        ////////////////////
[1357]996        //-- global termination criteria
[1237]997
[1580]998        /// the minimal accepted global cost ratio
[1237]999        float mTermMinGlobalCostRatio;
[1580]1000        //// number of accepted misses of the global cost ratio
[1237]1001        int mTermGlobalCostMissTolerance;
1002        /// maximal number of view cells
1003        int mTermMaxLeaves;
1004        /// maximal tree memory
1005        float mMaxMemory;
1006        /// the tree is out of memory
1007        bool mOutOfMemory;
1008
1009
[1357]1010        ////////////////////////////////////////
[1237]1011        //-- split heuristics based parameters
1012       
[1643]1013        /// if a heuristics should be used for finding a split plane
1014    bool mUseCostHeuristics;
1015        /// if sah heuristcs should be used for finding a split plane
1016        bool mUseSah;
1017    /// balancing factor for PVS criterium
[1237]1018        float mCtDivCi;
1019        /// if only driving axis should be used for split
1020        bool mOnlyDrivingAxis;
1021        /// current time stamp (used for keeping split history)
1022        int mTimeStamp;
1023        // if rays should be stored in leaves
1024        bool mStoreRays;
[1357]1025        // subdivision stats output file
[2176]1026        std::ofstream  mSubdivisionStats;
[1237]1027        /// keeps track of cost during subdivision
1028        float mTotalCost;
[1662]1029        int mPvsEntries;
[1237]1030        /// keeps track of overall pvs size during subdivision
1031        int mTotalPvsSize;
1032        /// number of currenly generated view cells
1033        int mCreatedLeaves;
1034        /// represents min and max band for sweep
[2124]1035        //float mSplitBorder;
[1237]1036        /// weight between render cost decrease and node render cost
1037        float mRenderCostDecreaseWeight;
[1758]1038
[1580]1039        /// if the objects should be sorted in one global step
1040        bool mUseGlobalSorting;
[1237]1041
[1662]1042        bool mUseBboxAreaForSah;
1043
[1779]1044        //SortableEntryContainer *mSortedObjects[4];
[1676]1045
1046        int mMinRaysForVisibility;
[1727]1047
[1732]1048        /// constant value for driving the heuristics
1049        float mMemoryConst;
1050
[1786]1051        int mMaxTests;
1052
[1779]1053        bool mIsInitialSubdivision;
1054
1055        bool mApplyInitialPartition;
[1786]1056       
1057        int mInitialMinObjects;
1058        float mInitialMaxAreaRatio;
1059        float mInitialMinArea;
[1237]1060};
1061
1062}
1063
1064#endif
Note: See TracBrowser for help on using the repository browser.