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

Revision 2350, 28.0 KB checked in by mattausch, 18 years ago (diff)

fixed new evaluation method

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
672        void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
673
674        float GetTriangleSizeIncrementially(BvhNode *node) const;
675
676        void Compress();
677        void CreateUniqueObjectIds();
678
679        PerfTimer mNodeTimer;
680        PerfTimer mSubdivTimer;
681        PerfTimer mEvalTimer;
682        PerfTimer mSplitTimer;
683        PerfTimer mPlaneTimer;
684        PerfTimer mSortTimer;
685        PerfTimer mCollectTimer;
686
687protected:
688
689        /** Returns true if tree can be terminated.
690        */
691        bool LocalTerminationCriteriaMet(const BvhTraversalData &data) const;
692
693        /** Returns true if global tree can be terminated.
694        */
695        bool GlobalTerminationCriteriaMet(const BvhTraversalData &data) const;
696
697        /** For sorting the objects during the heuristics
698        */
699        struct SortableEntry
700        {
701                Intersectable *mObject;
702                float mPos;
703
704                SortableEntry() {}
705
706                SortableEntry(Intersectable *obj, const float pos):
707                mObject(obj), mPos(pos)
708                {}
709
710                bool operator<(const SortableEntry &b) const
711                {
712                        return mPos < b.mPos;
713                }
714        };
715
716        /** Evaluate balanced object partition.
717        */
718        float EvalLocalObjectPartition(const BvhTraversalData &tData,
719                                                                   const int axis,
720                                                                   ObjectContainer &objectsFront,
721                                                                   ObjectContainer &objectsBack);
722
723        /** Evaluate surface area heuristic for the node.
724        */
725        float EvalSah(const BvhTraversalData &tData,
726                                  const int axis,
727                                  ObjectContainer &objectsFront,
728                                  ObjectContainer &objectsBack);
729
730        float EvalSahWithTigherBbox(const BvhTraversalData &tData,
731                                                                const int axis,
732                                                                ObjectContainer &objectsFront,
733                                                                ObjectContainer &objectsBack);
734
735        /** Evaluates render cost of the bv induced by these objects
736        */
737        float EvalRenderCost(const ObjectContainer &objects);// const;
738
739        float EvalProbability(const ObjectContainer &objects);
740
741        /** Evaluates tree stats in the BSP tree leafs.
742        */
743        void EvaluateLeafStats(const BvhTraversalData &data);
744
745        /** Subdivides node using a best split priority queue.
746            @param tQueue the best split priority queue
747                @param splitCandidate the candidate for the next split
748                @param globalCriteriaMet if the global termination criteria were already met
749                @returns new root of the subtree
750        */
751        BvhNode *Subdivide(SplitQueue &tQueue,
752                                           SubdivisionCandidate *splitCandidate,
753                                           const bool globalCriteriaMet
754                                           ,vector<SubdivisionCandidate *> &dirtyList
755                                           );
756       
757        /** Subdivides leaf.
758                @param sc the subdivisionCandidate holding all necessary data for subdivision           
759               
760                @param frontData returns the traversal data for the front node
761                @param backData returns the traversal data for the back node
762
763                @returns the new interior node = the of the subdivision
764        */
765        BvhInterior *SubdivideNode(const BvhSubdivisionCandidate &sc,
766                                                           BvhTraversalData &frontData,
767                                                           BvhTraversalData &backData);
768
769        /** Splits the objects for the next subdivision.
770                @returns cost for this split
771        */
772        float SelectObjectPartition(const BvhTraversalData &tData,
773                                                                ObjectContainer &frontObjects,
774                                                                ObjectContainer &backObjects,
775                                                                bool useVisibilityBasedHeuristics);
776       
777        /** Writes the node to disk
778                @note: should be implemented as visitor.
779        */
780        void ExportNode(BvhNode *node, OUT_STREAM &stream);
781
782        /** Exports objects associated with this leaf.
783        */
784        void ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream);
785
786        /** Associates the objects with their bvh leaves.
787        */
788        static void AssociateObjectsWithLeaf(BvhLeaf *leaf);
789
790       
791        /////////////////////////////
792        // Helper functions for local cost heuristics
793       
794        /** Prepare split candidates for cost heuristics using axis aligned splits.
795                @param node the current node
796                @param axis the current split axis
797        */
798        void PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
799                                                                                   const int axis);
800
801        static void CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
802                                                                                                 SortableEntryContainer **subdivisionCandidates,
803                                                                                                 const bool sort,
804                                                                                                 const int axis);
805
806        float EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
807                                           const float renderCostDecr,
808                                           const float oldRenderCost) const;
809
810        /** Computes object partition with the best cost according to the heurisics.
811                @param tData the traversal data
812                @param axis the split axis
813                @param objectsFront the objects in the front child bv
814                @param objectsBack the objects in the back child bv
815                @param backObjectsStart the iterator marking the position where the back objects begin
816
817                @returns relative cost (relative to parent cost)
818        */
819        float EvalLocalCostHeuristics(const BvhTraversalData &tData,
820                                                                  const int axis,
821                                                                  ObjectContainer &objectsFront,
822                                                                  ObjectContainer &objectsBack);
823
824        /** Evaluates the contribution to the front and back volume
825                when this object is changing sides in the bvs.
826
827                @param object the object
828                @param volLeft updates the left pvs
829                @param volPvs updates the right pvs
830        */
831        void EvalHeuristicsContribution(Intersectable *obj,
832                                                                        float &volLeft,
833                                                                        float &volRight);
834
835        /** Prepares objects for the cost heuristics.
836                @returns sum of volume of associated view cells
837        */
838        float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
839       
840        /** Evaluates cost for a leaf given the surface area heuristics.
841        */
842        float EvalSahCost(BvhLeaf *leaf) const;
843
844        ////////////////////////////////////////////////
845
846
847        /** Prepares construction for vsp and osp trees.
848        */
849        AxisAlignedBox3 EvalBoundingBox(const ObjectContainer &objects,
850                                                                        const AxisAlignedBox3 *parentBox = NULL) const;
851
852        /** Collects list of invalid candidates. Candidates
853                are invalidated by a view space subdivision step
854                that affects this candidate.
855        */
856        void CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
857                                                                vector<SubdivisionCandidate *> &dirtyList,
858                                                                const bool onlyUnmailed);
859
860        /** Collect view cells which see this bvh leaf.
861        */
862        int CollectViewCells(const ObjectContainer &objects,
863                                                 ViewCellContainer &viewCells,
864                                                 const bool setCounter,
865                                                 const bool onlyUnmailedRays);// const;
866
867        /** Collects view cells which see an object.
868                @param useMailBoxing if mailing should be used and
869                only unmailed object should pass
870                @param setCounter counter for the sweep algorithm
871                @param onlyUnmailedRays if only unmailed rays should be considered
872        */
873        int CollectViewCells(Intersectable *object,
874                                                 ViewCellContainer &viewCells,
875                                                 const bool useMailBoxing,
876                                                 const bool setCounter,
877                                                 const bool onlyUnmailedRays);// const;
878
879        /** Counts the view cells of this object. note: only
880                counts unmailed objects.
881        */
882        int CountViewCells(Intersectable *obj);// const;
883
884        /** Counts the view cells seen by this bvh leaf
885        */
886        int CountViewCells(const ObjectContainer &objects);// const;
887
888#if STORE_VIEWCELLS_WITH_BVH
889
890        int AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const;
891
892        void AssociateViewCellsWithObjects(const ObjectContainer &objects) const;
893
894        void ReleaseViewCells(const ObjectContainer &objects);
895
896        int CollectViewCellsFromRays(Intersectable *obj,
897                                                                 ViewCellContainer &viewCells,
898                                                                 const bool useMailBoxing,
899                                                                 const bool setCounter,
900                                                                 const bool onlyUnmailedRays);
901
902        int CountViewCellsFromRays(Intersectable *obj);
903#endif
904
905        /** Evaluates increase in pvs size.
906        */
907        int EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate,
908                                                   const float raysPerObjects,
909                                                   const int numParentViewCells,
910                                                   const int numFrontViewCells,
911                                                   const int numBackViewCells);// const;
912
913        /** Rays will be clipped to the bounding box.
914        */
915        void PreprocessRays(BvhLeaf *root,
916                                                const VssRayContainer &sampleRays,
917                                                RayInfoContainer &rays);
918
919        /** Print the subdivision stats in the subdivison log.
920        */
921        void PrintSubdivisionStats(const SubdivisionCandidate &tData);
922
923        /** Prints out the stats for this subdivision.
924        */
925        void AddSubdivisionStats(const int viewCells,
926                                                         const float renderCostDecr,
927                                                         const float totalRenderCost);
928
929        /** Stores rays with objects that see the rays.
930        */
931        int AssociateObjectsWithRays(const VssRayContainer &rays) const;
932
933        /** Tests if object is in this leaf.
934                @note: assumes that objects are sorted by their id.
935        */
936        bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;
937
938        /** Prepares the construction of the bv hierarchy and returns
939                the first subdivision candidate.
940        */
941        void PrepareConstruction(SplitQueue &tQueue,
942                                                         const VssRayContainer &sampleRays,
943                                                         const ObjectContainer &objects);
944
945        /** Resets bv hierarchy. E.g. deletes root and resets stats.
946        */
947        void Reset(SplitQueue &tQueue,
948                           const VssRayContainer &rays,
949                           const ObjectContainer &objects);
950
951        /** Evaluates volume of view cells that see the objects.
952        */
953        float EvalViewCellsVolume(const ObjectContainer &objects);// const;
954
955        /** Assigns or newly creates initial list of sorted objects.
956        */
957        void AssignInitialSortedObjectList(BvhTraversalData &tData,
958                                                                           const ObjectContainer &objects);
959
960        /** Assigns sorted objects to front and back data.
961        */
962        void AssignSortedObjects(const BvhSubdivisionCandidate &sc,
963                                                         BvhTraversalData &frontData,
964                                                         BvhTraversalData &backData);
965       
966        /** Creates new root of hierarchy and computes bounding box.
967                Has to be called before the preparation of the subdivision.
968        */
969        void Initialise(const ObjectContainer &objects);
970
971
972        ////////////////////
973        // initial subdivision
974
975        /** Makes an initial parititon of the object space based on
976                some criteria (size, shader)
977        */
978        void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
979                                                                 vector<SubdivisionCandidate *> &candidateContainer);
980
981        void ApplyInitialSplit(const BvhTraversalData &tData,
982                                                   ObjectContainer &frontObjects,
983                                                   ObjectContainer &backObjects);
984
985        bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;
986
987        /** Sets the bvh node ids.
988        */
989        void SetUniqueNodeIds();
990
991        void UpdateViewCells(const BvhSubdivisionCandidate &sc);
992        void TestEvaluation(const BvhSubdivisionCandidate &sc);
993
994
995protected:
996       
997        /// pre-sorted subdivision candidtes for all three directions.
998        vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
999        /// pointer to the hierarchy of view cells
1000        ViewCellsTree *mViewCellsTree;
1001        /// The view cells manager
1002        ViewCellsManager *mViewCellsManager;
1003        /// candidates for placing split planes during cost heuristics
1004        vector<SortableEntry> *mSubdivisionCandidates;
1005        /// Pointer to the root of the tree
1006        BvhNode *mRoot;
1007        /// Statistics for the object space partition
1008        BvhStatistics mBvhStats;       
1009        /// box around the whole view domain
1010        AxisAlignedBox3 mBoundingBox;
1011        /// the hierarchy manager
1012        HierarchyManager *mHierarchyManager;
1013
1014
1015        ////////////////////
1016        //-- local termination criteria
1017
1018        /// maximal possible depth
1019        int mTermMaxDepth;
1020        /// mininum probability
1021        float mTermMinProbability;
1022        /// minimal number of objects
1023        int mTermMinObjects;
1024        /// maximal acceptable cost ratio
1025        float mTermMaxCostRatio;
1026        /// tolerance value indicating how often the max cost ratio can be failed
1027        int mTermMissTolerance;
1028        /// minimum number of rays
1029        int mTermMinRays;
1030
1031
1032        ////////////////////
1033        //-- global termination criteria
1034
1035        /// the minimal accepted global cost ratio
1036        float mTermMinGlobalCostRatio;
1037        //// number of accepted misses of the global cost ratio
1038        int mTermGlobalCostMissTolerance;
1039        /// maximal number of view cells
1040        int mTermMaxLeaves;
1041        /// maximal tree memory
1042        float mMaxMemory;
1043        /// the tree is out of memory
1044        bool mOutOfMemory;
1045
1046
1047        ////////////////////////////////////////
1048        //-- split heuristics based parameters
1049       
1050        /// if a heuristics should be used for finding a split plane
1051    bool mUseCostHeuristics;
1052        /// if sah heuristcs should be used for finding a split plane
1053        bool mUseSah;
1054    /// balancing factor for PVS criterium
1055        float mCtDivCi;
1056        /// if only driving axis should be used for split
1057        bool mOnlyDrivingAxis;
1058        /// current time stamp (used for keeping split history)
1059        int mTimeStamp;
1060        // if rays should be stored in leaves
1061        bool mStoreRays;
1062        // subdivision stats output file
1063        std::ofstream  mSubdivisionStats;
1064        /// keeps track of cost during subdivision
1065        float mTotalCost;
1066        int mPvsEntries;
1067        /// keeps track of overall pvs size during subdivision
1068        int mTotalPvsSize;
1069        /// number of currenly generated view cells
1070        int mCreatedLeaves;
1071        /// represents min and max band for sweep
1072        //float mSplitBorder;
1073        /// weight between render cost decrease and node render cost
1074        float mRenderCostDecreaseWeight;
1075
1076        /// if the objects should be sorted in one global step
1077        bool mUseGlobalSorting;
1078
1079        bool mUseBboxAreaForSah;
1080
1081        //SortableEntryContainer *mSortedObjects[4];
1082
1083        int mMinRaysForVisibility;
1084
1085        /// constant value for driving the heuristics
1086        float mMemoryConst;
1087
1088        int mMaxTests;
1089
1090        bool mIsInitialSubdivision;
1091
1092        bool mApplyInitialPartition;
1093       
1094        int mInitialMinObjects;
1095        float mInitialMaxAreaRatio;
1096        float mInitialMinArea;
1097};
1098
1099
1100
1101}
1102
1103#endif
Note: See TracBrowser for help on using the repository browser.