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

Revision 2255, 28.7 KB checked in by mattausch, 18 years ago (diff)

improved scenemanager config

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#include "HierarchyManager.h"
16#include "Timer/PerfTimer.h"
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;
37class HierarchyManager;
38
39
40/** View space partition statistics.
41*/
42class BvhStatistics: public StatisticsBase
43{
44public:
45       
46        /// Constructor
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
59        double AvgObjectRefs() const
60        { return objectRefs / (double)Leaves(); }
61
62        double AvgRayRefs() const
63        { return rayRefs / (double)Leaves(); }
64
65       
66        void Reset()
67        {
68                nodes = 0;
69                splits = 0;
70                maxDepth = 0;
71
72                minDepth = 99999;
73                accumDepth = 0;
74        maxDepthNodes = 0;
75                minProbabilityNodes = 0;
76                maxCostNodes = 0;
77                ///////////////////
78                minObjectsNodes = 0;
79                maxObjectRefs = 0;
80                minObjectRefs = 999999999;
81                objectRefs = 0;
82                emptyNodes = 0;
83
84                ///////////////////
85                minRaysNodes = 0;
86                maxRayRefs = 0;
87                minRayRefs = 999999999;
88                rayRefs = 0;
89                maxRayContriNodes = 0;
90                mGlobalCostMisses = 0;
91        }
92
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;
112        // global cost ratio violations
113        int mGlobalCostMisses;
114
115        //////////////////
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;
124        // leaves with no objects
125        int emptyNodes;
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
139        void Print(std::ostream &app) const;
140
141        friend std::ostream &operator<<(std::ostream &s, const BvhStatistics &stat)
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*/
152class BvhNode: public Intersectable
153{
154public:
155       
156        // types of vsp nodes
157        enum {Interior, Leaf};
158
159        BvhNode();
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
183        /** collects all objects under this node.
184        */
185        virtual void CollectObjects(ObjectContainer &objects) = 0;
186
187        /** The bounding box specifies the node extent.
188        */
189        inline
190        AxisAlignedBox3 GetBoundingBox() const
191        { return mBoundingBox; }
192
193        /** Sets bouding box of this node.
194        */
195        inline
196        void SetBoundingBox(const AxisAlignedBox3 &boundingBox)
197        { mBoundingBox = boundingBox; }
198
199        /** Cost of mergin this node.
200        */
201        float GetMergeCost() {return (float)-mTimeStamp; }
202
203        virtual int GetRandomEdgePoint(Vector3 &point, Vector3 &normal);
204
205        inline int GetTimeStamp() const { return mTimeStamp; }
206        inline void SetTimeStamp(const int timeStamp) { mTimeStamp = timeStamp; };
207
208
209        ////////////////////////
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       
222        int GetRandomSurfacePoint(GtpVisibilityPreprocessor::Vector3 &point,
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
243        std::ostream &Describe(std::ostream &s) { return s; }
244
245        ///////////////////////////////////
246
247        float mRenderCost;
248
249protected:
250       
251        /// the bounding box of the node
252        AxisAlignedBox3 mBoundingBox;
253        /// parent of this node
254        BvhInterior *mParent;
255        int mTimeStamp;
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;
273       
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
285        friend std::ostream &operator<<(std::ostream &s, const BvhInterior &A)
286        {
287                return s << A.mBoundingBox;
288        }
289
290        virtual void CollectObjects(ObjectContainer &objects);
291
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);
309        BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent);
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       
318        SubdivisionCandidate *GetSubdivisionCandidate()// const
319        {
320                return mSubdivisionCandidate;
321        }
322
323        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
324        {
325                mSubdivisionCandidate = candidate;
326        }
327       
328        virtual void CollectObjects(ObjectContainer &objects);
329
330        /** Returns level of the hierarchy that is "active" right now.
331        */
332        BvhNode *GetActiveNode()
333        {
334                return mActiveNode;
335        }
336
337        /** Returns level of the hierarchy that is "active" right now.
338        */
339        void SetActiveNode(BvhNode *node)
340        {
341                mActiveNode = node;
342        }
343
344public:
345  // gl list use to store the geometry on the gl server
346  int mGlList;
347 
348  /// objects
349  ObjectContainer mObjects;
350 
351 
352protected:
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;
359};
360
361
362/** View Space Partitioning tree.
363*/
364class BvHierarchy
365{
366        friend class ViewCellsParseHandlers;
367        friend class ObjectsParseHandlers;
368        friend class HierarchyManager;
369
370protected:
371        struct SortableEntry;
372        typedef vector<SortableEntry> SortableEntryContainer;
373
374public:
375       
376        /** Additional data which is passed down the BSP tree during traversal.
377        */
378        class BvhTraversalData
379        { 
380        public:
381               
382                BvhTraversalData():
383                mNode(NULL),
384                mDepth(0),
385                mMaxCostMisses(0),
386                mAxis(0),
387                mNumRays(0),
388                mCorrectedPvs(0),
389                mPvs(0),
390                mCorrectedVolume(0),
391                mVolume(0)
392                {
393                        for (int i = 0; i < 4; ++ i)
394                                mSortedObjects[i] = NULL;
395                }
396               
397                BvhTraversalData(BvhLeaf *node,
398                                                 const int depth,
399                                                 const float v,
400                                                 const int numRays):
401                mNode(node),
402                mDepth(depth),
403                mMaxCostMisses(0),
404                mAxis(0),
405                mNumRays(numRays),
406                mCorrectedPvs(0),
407                mPvs(0),
408                mCorrectedVolume(0),
409                mVolume(v),
410                mSampledObjects(NULL)
411                {
412                        for (int i = 0; i < 4; ++ i)
413                                mSortedObjects[i] = NULL;
414                }
415
416                /** Deletes contents and sets them to NULL.
417                */
418                void Clear()
419                {
420                        DEL_PTR(mNode);
421                        for (int i = 0; i < 4; ++ i)
422                                DEL_PTR(mSortedObjects[i]);
423
424                        DEL_PTR(mSampledObjects);
425                }
426
427                /// the current node
428                BvhLeaf *mNode;
429                /// current depth
430                int mDepth;
431                /// the volume of the node
432                float mVolume;
433                /// the corrected volume
434                float mCorrectedVolume;
435                /// how often this branch has missed the max-cost ratio
436                int mMaxCostMisses;
437                /// current axis
438                int mAxis;
439                /// number of rays
440                int mNumRays;
441                /// parent Pvs;
442                float mPvs;
443                /// parent pvs correction factor
444                float mCorrectedPvs;
445
446                /** the sorted objects for the three dimensions + one for the original
447                        order + one for the objects which have been sampled at least once
448                */
449                ObjectContainer *mSortedObjects[4];             
450                ObjectContainer *mSampledObjects;       
451    };
452
453
454        /** Candidate for a object space split.
455        */
456        class BvhSubdivisionCandidate: public SubdivisionCandidate
457        { 
458        public:
459
460        BvhSubdivisionCandidate(const BvhTraversalData &tData): mParentData(tData)
461                {};
462
463                ~BvhSubdivisionCandidate()
464                {
465                        mParentData.Clear();
466                }
467
468                int Type() const { return OBJECT_SPACE; }
469       
470                void EvalCandidate(bool computeSplitplane = true)
471                {
472            mDirty = false;
473                        sBvHierarchy->EvalSubdivisionCandidate(*this, computeSplitplane, true);
474                }
475
476                bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet, SubdivisionCandidateContainer &dirtyList)
477                {
478                        BvhNode *n = sBvHierarchy->Subdivide(splitQueue, this, terminationCriteriaMet, dirtyList);
479
480                        // local or global termination criteria failed
481                        return !n->IsLeaf();           
482                }
483
484                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
485                                                                        const bool onlyUnmailed)
486                {
487                        sBvHierarchy->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
488                }
489
490                bool GlobalTerminationCriteriaMet() const
491                {
492                        return sBvHierarchy->GlobalTerminationCriteriaMet(mParentData);
493                }
494
495                BvhSubdivisionCandidate(const ObjectContainer &frontObjects,
496                                                                const ObjectContainer &backObjects,
497                                                                const BvhTraversalData &tData):
498                mFrontObjects(frontObjects), mBackObjects(backObjects), mParentData(tData)
499                {}
500
501                float GetPriority() const
502                {
503                        //return (float)-mParentData.mDepth;
504                        return mPriority;
505                }
506
507                /////////////////////////////7
508
509                /// pointer to parent tree.
510                static BvHierarchy *sBvHierarchy;
511
512                /// parent data
513                BvhTraversalData mParentData;
514                /// the objects on the front of the potential split
515                ObjectContainer mFrontObjects;
516                /// the objects on the back of the potential split
517                ObjectContainer mBackObjects;
518                       
519                /// the sampled objects on the front of the potential split
520                ObjectContainer mSampledFrontObjects;
521                /// the sampled objects on the back of the potential split
522                ObjectContainer mSampledBackObjects;
523
524                float mCorrectedFrontPvs;
525                float mCorrectedBackPvs;
526
527                float mCorrectedFrontVolume;
528                float mCorrectedBackVolume;
529
530                //int mNumFrontRays;
531                //int mNumBackRays;
532               
533                int mNumFrontViewCells;
534                int mNumBackViewCells;
535
536                float mVolumeFrontViewCells;
537                float mVolumeBackViewCells;
538        };
539
540        /** Struct for traversing line segment.
541        */
542        struct LineTraversalData
543        {
544                BvhNode *mNode;
545                Vector3 mExitPoint;
546               
547                float mMaxT;
548   
549                LineTraversalData () {}
550                LineTraversalData (BvhNode *n, const Vector3 &p, const float maxt):
551                mNode(n), mExitPoint(p), mMaxT(maxt) {}
552        };
553
554
555        /** Default constructor creating an empty tree.
556        */
557        BvHierarchy();
558
559        /** Default destructor.
560        */
561        ~BvHierarchy();
562
563        /** Returns tree statistics.
564        */
565        const BvhStatistics &GetStatistics() const;
566 
567        /** Returns bounding box of the specified node.
568        */
569        AxisAlignedBox3 GetBoundingBox(BvhNode *node) const;
570
571        /** Reads parameters from environment singleton.
572        */
573        void ReadEnvironment();
574
575        /** Evaluates candidate for splitting.
576        */
577        void EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitData,
578                                                                  const bool computeSplitPlane,
579                                                                  const bool preprocessViewCells);
580
581        /** Returns vector of leaves.
582        */
583        void CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const;
584
585        /** Returns vector of leaves.
586        */
587        void CollectNodes(BvhNode *root, vector<BvhNode *> &nodes) const;
588
589        /** Returns bounding box of the whole tree (= bbox of root node)
590        */
591        AxisAlignedBox3 GetBoundingBox()const;
592
593        /** Returns root of the view space partitioning tree.
594        */
595        BvhNode *GetRoot() const;
596
597        /** finds neighbouring leaves of this tree node.
598        */
599        int FindNeighbors(BvhLeaf *n,
600                                          vector<BvhLeaf *> &neighbors,
601                                          const bool onlyUnmailed) const;
602
603        /** Returns random leaf of BSP tree.
604                @param halfspace defines the halfspace from which the leaf is taken.
605        */
606        BvhLeaf *GetRandomLeaf(const Plane3 &halfspace);
607
608        /** Returns random leaf of BSP tree.
609                @param onlyUnmailed if only unmailed leaves should be returned.
610        */
611        BvhLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
612
613        /** Casts line segment into the tree.
614                @param origin the origin of the line segment
615                @param termination the end point of the line segment
616                @returns view cells intersecting the line segment.
617        */
618    int CastLineSegment(const Vector3 &origin,
619                                                const Vector3 &termination,
620                                                ViewCellContainer &viewcells);
621               
622        /** Sets pointer to view cells manager.
623        */
624        void SetViewCellsManager(ViewCellsManager *vcm);
625
626        float GetViewSpaceVolume() const;
627        /** Writes tree to output stream
628        */
629        bool Export(OUT_STREAM &stream);
630
631        /** Collects rays associated with the objects.
632        */
633        void CollectRays(const ObjectContainer &objects, VssRayContainer &rays) const;
634
635        /** Intersects box with the tree and returns the number of intersected boxes.
636                @returns number of view cells found
637        */
638        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
639                                                                ViewCellContainer &viewCells) const;
640
641        /** Returns leaf the point pt lies in, starting from root.
642        */
643        inline BvhLeaf *GetLeaf(Intersectable *object, BvhNode *root = NULL) const
644        {
645                // hack: we use the simpler but faster version
646                //if (!object) return NULL;
647
648                return object->mBvhLeaf;
649        }
650
651        /** Sets a pointer to the view cells tree.
652        */
653        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
654       
655        /** See Get
656        */
657        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
658
659        /** Returns estimated memory usage of tree.
660        */
661        float GetMemUsage() const;
662
663        /** Sets this node to be an active node.
664        */
665        void SetActive(BvhNode *node) const;
666
667
668        void StoreSampledObjects(ObjectContainer &sampledObjects, const ObjectContainer &objects);
669
670        ///////////////////////////
671        // hacks in order to provide interleaved heurisitcs
672
673        BvhNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
674
675        /////////////////////////////////
676
677        static inline float EvalAbsCost(const ObjectContainer &objects);
678
679        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
680
681        float GetRenderCostIncrementially(BvhNode *node) const;
682
683        void Compress();
684        void CreateUniqueObjectIds();
685
686        PerfTimer mNodeTimer;
687        PerfTimer mSubdivTimer;
688        PerfTimer mEvalTimer;
689        PerfTimer mSplitTimer;
690        PerfTimer mPlaneTimer;
691        PerfTimer mSortTimer;
692        PerfTimer mCollectTimer;
693
694protected:
695
696        /** Returns true if tree can be terminated.
697        */
698        bool LocalTerminationCriteriaMet(const BvhTraversalData &data) const;
699
700        /** Returns true if global tree can be terminated.
701        */
702        bool GlobalTerminationCriteriaMet(const BvhTraversalData &data) const;
703
704        /** For sorting the objects during the heuristics
705        */
706        struct SortableEntry
707        {
708                Intersectable *mObject;
709                float mPos;
710
711                SortableEntry() {}
712
713                SortableEntry(Intersectable *obj, const float pos):
714                mObject(obj), mPos(pos)
715                {}
716
717                bool operator<(const SortableEntry &b) const
718                {
719                        return mPos < b.mPos;
720                }
721        };
722
723        /** Evaluate balanced object partition.
724        */
725        float EvalLocalObjectPartition(const BvhTraversalData &tData,
726                                                                   const int axis,
727                                                                   ObjectContainer &objectsFront,
728                                                                   ObjectContainer &objectsBack);
729
730        /** Evaluate surface area heuristic for the node.
731        */
732        float EvalSah(const BvhTraversalData &tData,
733                                  const int axis,
734                                  ObjectContainer &objectsFront,
735                                  ObjectContainer &objectsBack);
736
737        float EvalSahWithTigherBbox(const BvhTraversalData &tData,
738                                                                const int axis,
739                                                                ObjectContainer &objectsFront,
740                                                                ObjectContainer &objectsBack);
741
742        /** Evaluates render cost of the bv induced by these objects
743        */
744        float EvalRenderCost(const ObjectContainer &objects);// const;
745
746        float EvalProbability(const ObjectContainer &objects);
747
748        /** Evaluates tree stats in the BSP tree leafs.
749        */
750        void EvaluateLeafStats(const BvhTraversalData &data);
751
752        /** Subdivides node using a best split priority queue.
753            @param tQueue the best split priority queue
754                @param splitCandidate the candidate for the next split
755                @param globalCriteriaMet if the global termination criteria were already met
756                @returns new root of the subtree
757        */
758        BvhNode *Subdivide(SplitQueue &tQueue,
759                                           SubdivisionCandidate *splitCandidate,
760                                           const bool globalCriteriaMet
761                                           ,vector<SubdivisionCandidate *> &dirtyList
762                                           );
763       
764        /** Subdivides leaf.
765                @param sc the subdivisionCandidate holding all necessary data for subdivision           
766               
767                @param frontData returns the traversal data for the front node
768                @param backData returns the traversal data for the back node
769
770                @returns the new interior node = the of the subdivision
771        */
772        BvhInterior *SubdivideNode(const BvhSubdivisionCandidate &sc,
773                                                           BvhTraversalData &frontData,
774                                                           BvhTraversalData &backData);
775
776        /** Splits the objects for the next subdivision.
777                @returns cost for this split
778        */
779        float SelectObjectPartition(const BvhTraversalData &tData,
780                                                                ObjectContainer &frontObjects,
781                                                                ObjectContainer &backObjects,
782                                                                bool useVisibilityBasedHeuristics);
783       
784        /** Writes the node to disk
785                @note: should be implemented as visitor.
786        */
787        void ExportNode(BvhNode *node, OUT_STREAM &stream);
788
789        /** Exports objects associated with this leaf.
790        */
791        void ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream);
792
793        /** Associates the objects with their bvh leaves.
794        */
795        static void AssociateObjectsWithLeaf(BvhLeaf *leaf);
796
797       
798        /////////////////////////////
799        // Helper functions for local cost heuristics
800       
801        /** Prepare split candidates for cost heuristics using axis aligned splits.
802                @param node the current node
803                @param axis the current split axis
804        */
805        void PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
806                                                                                   const int axis);
807
808        static void CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
809                                                                                                 SortableEntryContainer **subdivisionCandidates,
810                                                                                                 const bool sort,
811                                                                                                 const int axis);
812
813        float EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
814                                           const float renderCostDecr,
815                                           const float oldRenderCost) const;
816
817        /** Computes object partition with the best cost according to the heurisics.
818                @param tData the traversal data
819                @param axis the split axis
820                @param objectsFront the objects in the front child bv
821                @param objectsBack the objects in the back child bv
822                @param backObjectsStart the iterator marking the position where the back objects begin
823
824                @returns relative cost (relative to parent cost)
825        */
826        float EvalLocalCostHeuristics(const BvhTraversalData &tData,
827                                                                  const int axis,
828                                                                  ObjectContainer &objectsFront,
829                                                                  ObjectContainer &objectsBack);
830
831        /** Evaluates the contribution to the front and back volume
832                when this object is changing sides in the bvs.
833
834                @param object the object
835                @param volLeft updates the left pvs
836                @param volPvs updates the right pvs
837        */
838        void EvalHeuristicsContribution(Intersectable *obj,
839                                                                        float &volLeft,
840                                                                        float &volRight);
841
842        /** Prepares objects for the cost heuristics.
843                @returns sum of volume of associated view cells
844        */
845        float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
846       
847        /** Evaluates cost for a leaf given the surface area heuristics.
848        */
849        float EvalSahCost(BvhLeaf *leaf) const;
850
851        ////////////////////////////////////////////////
852
853
854        /** Prepares construction for vsp and osp trees.
855        */
856        AxisAlignedBox3 EvalBoundingBox(const ObjectContainer &objects,
857                                                                        const AxisAlignedBox3 *parentBox = NULL) const;
858
859        /** Collects list of invalid candidates. Candidates
860                are invalidated by a view space subdivision step
861                that affects this candidate.
862        */
863        void CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
864                                                                vector<SubdivisionCandidate *> &dirtyList,
865                                                                const bool onlyUnmailed);
866
867        /** Collect view cells which see this bvh leaf.
868        */
869        int CollectViewCells(const ObjectContainer &objects,
870                                                 ViewCellContainer &viewCells,
871                                                 const bool setCounter,
872                                                 const bool onlyUnmailedRays);// const;
873
874        /** Collects view cells which see an object.
875                @param useMailBoxing if mailing should be used and
876                only unmailed object should pass
877                @param setCounter counter for the sweep algorithm
878                @param onlyUnmailedRays if only unmailed rays should be considered
879        */
880        int CollectViewCells(Intersectable *object,
881                                                 ViewCellContainer &viewCells,
882                                                 const bool useMailBoxing,
883                                                 const bool setCounter,
884                                                 const bool onlyUnmailedRays);// const;
885
886        /** Counts the view cells of this object. note: only
887                counts unmailed objects.
888        */
889        int CountViewCells(Intersectable *obj);// const;
890
891        /** Counts the view cells seen by this bvh leaf
892        */
893        int CountViewCells(const ObjectContainer &objects);// const;
894
895#if STORE_VIEWCELLS_WITH_BVH
896
897        int AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const;
898
899        void AssociateViewCellsWithObjects(const ObjectContainer &objects) const;
900
901        void ReleaseViewCells(const ObjectContainer &objects);
902
903        int CollectViewCellsFromRays(Intersectable *obj,
904                                                                 ViewCellContainer &viewCells,
905                                                                 const bool useMailBoxing,
906                                                                 const bool setCounter,
907                                                                 const bool onlyUnmailedRays);
908
909        int CountViewCellsFromRays(Intersectable *obj);
910#endif
911
912        /** Evaluates increase in pvs size.
913        */
914        int EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate,
915                                                   const float raysPerObjects,
916                                                   const int numParentViewCells,
917                                                   const int numFrontViewCells,
918                                                   const int numBackViewCells);// const;
919
920        /** Rays will be clipped to the bounding box.
921        */
922        void PreprocessRays(BvhLeaf *root,
923                                                const VssRayContainer &sampleRays,
924                                                RayInfoContainer &rays);
925
926        /** Print the subdivision stats in the subdivison log.
927        */
928        void PrintSubdivisionStats(const SubdivisionCandidate &tData);
929
930        /** Prints out the stats for this subdivision.
931        */
932        void AddSubdivisionStats(const int viewCells,
933                                                         const float renderCostDecr,
934                                                         const float totalRenderCost);
935
936        /** Stores rays with objects that see the rays.
937        */
938        int AssociateObjectsWithRays(const VssRayContainer &rays) const;
939
940        /** Tests if object is in this leaf.
941                @note: assumes that objects are sorted by their id.
942        */
943        bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;
944
945        /** Prepares the construction of the bv hierarchy and returns
946                the first subdivision candidate.
947        */
948        void PrepareConstruction(SplitQueue &tQueue,
949                                                         const VssRayContainer &sampleRays,
950                                                         const ObjectContainer &objects);
951
952        /** Resets bv hierarchy. E.g. deletes root and resets stats.
953        */
954        void Reset(SplitQueue &tQueue,
955                           const VssRayContainer &rays,
956                           const ObjectContainer &objects);
957
958        /** Evaluates volume of view cells that see the objects.
959        */
960        float EvalViewCellsVolume(const ObjectContainer &objects);// const;
961
962        /** Assigns or newly creates initial list of sorted objects.
963        */
964        void AssignInitialSortedObjectList(BvhTraversalData &tData,
965                                                                           const ObjectContainer &objects);
966
967        /** Assigns sorted objects to front and back data.
968        */
969        void AssignSortedObjects(const BvhSubdivisionCandidate &sc,
970                                                         BvhTraversalData &frontData,
971                                                         BvhTraversalData &backData);
972       
973        /** Creates new root of hierarchy and computes bounding box.
974                Has to be called before the preparation of the subdivision.
975        */
976        void Initialise(const ObjectContainer &objects);
977
978
979        ////////////////////
980        // initial subdivision
981
982        /** Makes an initial parititon of the object space based on
983                some criteria (size, shader)
984        */
985        void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
986                                                                 vector<SubdivisionCandidate *> &candidateContainer);
987
988        void ApplyInitialSplit(const BvhTraversalData &tData,
989                                                   ObjectContainer &frontObjects,
990                                                   ObjectContainer &backObjects);
991
992        bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;
993
994        /** Sets the bvh node ids.
995        */
996        void SetUniqueNodeIds();
997
998protected:
999       
1000        /// pre-sorted subdivision candidtes for all three directions.
1001        vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
1002        /// pointer to the hierarchy of view cells
1003        ViewCellsTree *mViewCellsTree;
1004        /// The view cells manager
1005        ViewCellsManager *mViewCellsManager;
1006        /// candidates for placing split planes during cost heuristics
1007        vector<SortableEntry> *mSubdivisionCandidates;
1008        /// Pointer to the root of the tree
1009        BvhNode *mRoot;
1010        /// Statistics for the object space partition
1011        BvhStatistics mBvhStats;       
1012        /// box around the whole view domain
1013        AxisAlignedBox3 mBoundingBox;
1014        /// the hierarchy manager
1015        HierarchyManager *mHierarchyManager;
1016
1017
1018        ////////////////////
1019        //-- local termination criteria
1020
1021        /// maximal possible depth
1022        int mTermMaxDepth;
1023        /// mininum probability
1024        float mTermMinProbability;
1025        /// minimal number of objects
1026        int mTermMinObjects;
1027        /// maximal acceptable cost ratio
1028        float mTermMaxCostRatio;
1029        /// tolerance value indicating how often the max cost ratio can be failed
1030        int mTermMissTolerance;
1031        /// minimum number of rays
1032        int mTermMinRays;
1033
1034
1035        ////////////////////
1036        //-- global termination criteria
1037
1038        /// the minimal accepted global cost ratio
1039        float mTermMinGlobalCostRatio;
1040        //// number of accepted misses of the global cost ratio
1041        int mTermGlobalCostMissTolerance;
1042        /// maximal number of view cells
1043        int mTermMaxLeaves;
1044        /// maximal tree memory
1045        float mMaxMemory;
1046        /// the tree is out of memory
1047        bool mOutOfMemory;
1048
1049
1050        ////////////////////////////////////////
1051        //-- split heuristics based parameters
1052       
1053        /// if a heuristics should be used for finding a split plane
1054    bool mUseCostHeuristics;
1055        /// if sah heuristcs should be used for finding a split plane
1056        bool mUseSah;
1057    /// balancing factor for PVS criterium
1058        float mCtDivCi;
1059        /// if only driving axis should be used for split
1060        bool mOnlyDrivingAxis;
1061        /// current time stamp (used for keeping split history)
1062        int mTimeStamp;
1063        // if rays should be stored in leaves
1064        bool mStoreRays;
1065        // subdivision stats output file
1066        std::ofstream  mSubdivisionStats;
1067        /// keeps track of cost during subdivision
1068        float mTotalCost;
1069        int mPvsEntries;
1070        /// keeps track of overall pvs size during subdivision
1071        int mTotalPvsSize;
1072        /// number of currenly generated view cells
1073        int mCreatedLeaves;
1074        /// represents min and max band for sweep
1075        //float mSplitBorder;
1076        /// weight between render cost decrease and node render cost
1077        float mRenderCostDecreaseWeight;
1078
1079        /// if the objects should be sorted in one global step
1080        bool mUseGlobalSorting;
1081
1082        bool mUseBboxAreaForSah;
1083
1084        //SortableEntryContainer *mSortedObjects[4];
1085
1086        int mMinRaysForVisibility;
1087
1088        /// constant value for driving the heuristics
1089        float mMemoryConst;
1090
1091        int mMaxTests;
1092
1093        bool mIsInitialSubdivision;
1094
1095        bool mApplyInitialPartition;
1096       
1097        int mInitialMinObjects;
1098        float mInitialMaxAreaRatio;
1099        float mInitialMinArea;
1100};
1101
1102
1103float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)
1104{
1105        float result;
1106
1107#if USE_BETTER_RENDERCOST_EST
1108       
1109        const float switchcost = 1.0f;
1110
1111        float o = 0;
1112
1113        ObjectContainer::const_iterator oit, oit_end = objects.end();
1114
1115        for (oit = objects.begin(); oit != oit_end; ++ oit)
1116        {
1117                o += ViewCellsManager::GetRendercost(*oit);
1118        }
1119
1120        float n = (float)objects.size() * switchcost;
1121       
1122#else
1123       
1124        result = (float)objects.size();
1125
1126#endif
1127
1128#if BOUND_RENDERCOST
1129       
1130        if (result > MIN_RENDERCOST)
1131                return result;
1132        else
1133        {
1134                //std::cout << "b";
1135                return MIN_RENDERCOST;
1136        }
1137#endif
1138
1139        return result;
1140}
1141
1142}
1143
1144#endif
Note: See TracBrowser for help on using the repository browser.