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

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