source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.h @ 1913

Revision 1913, 28.4 KB checked in by mattausch, 18 years ago (diff)
RevLine 
[1237]1#ifndef _VspTree_H__
2#define _VspTree_H__
3
4#include <stack>
5
6#include "Mesh.h"
7#include "Containers.h"
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "gzstream.h"
[1239]12#include "SubdivisionCandidate.h"
[1667]13#include "HierarchyManager.h"
[1237]14
15
16namespace GtpVisibilityPreprocessor {
17
18class ViewCellLeaf;
19class Plane3;
20class AxisAlignedBox3;
21class Ray;
22class ViewCellsStatistics;
23class ViewCellsManager;
24class MergeCandidate;
25class Beam;
26class ViewCellsTree;
27class Environment;
28class VspInterior;
29class VspLeaf;
30class VspNode;
31class KdNode;
32class KdInterior;
33class KdLeaf;
[1259]34class HierarchyManager;
[1237]35class KdIntersectable;
36class KdTree;
37class VspTree;
38class KdTreeStatistics;
39
[1576]40
[1764]41#define WORK_WITH_VIEWCELLS 0
42
[1237]43/** View space partition statistics.
44*/
45class VspTreeStatistics: public StatisticsBase
46{
47public:
48        // total number of nodes
49        int nodes;
50        // number of splits
51        int splits[3];
52       
53        // totals number of rays
54        int rays;
55        // maximal reached depth
56        int maxDepth;
57        // minimal depth
58        int minDepth;
59       
60        // max depth nodes
61        int maxDepthNodes;
62        // minimum depth nodes
63        int minDepthNodes;
64        // max depth nodes
65        int minPvsNodes;
66        // nodes with minimum PVS
67        int minRaysNodes;
68        // max ray contribution nodes
69        int maxRayContribNodes;
70        // minimum area nodes
71        int minProbabilityNodes;
72        /// nodes termination because of max cost ratio;
73        int maxCostNodes;
74        // max number of rays per node
75        int maxObjectRefs;
76        /// samples contributing to pvs
77        int contributingSamples;
78        /// sample contributions to pvs
79        int sampleContributions;
80        /// largest pvs
81        int maxPvs;
82        /// number of invalid leaves
83        int invalidLeaves;
[1640]84        /// number of rays refs
85        int rayRefs;
[1449]86        /// overall pvs size
[1237]87        int pvs;
88        // accumulated depth (used to compute average)
89        int accumDepth;
[1449]90        // global cost ratio violations
91        int mGlobalCostMisses;
[1237]92
93        // Constructor
94        VspTreeStatistics()
95        {
96                Reset();
97        }
98
99        int Nodes() const {return nodes;}
100        int Interior() const { return nodes / 2; }
101        int Leaves() const { return (nodes / 2) + 1; }
102       
103        // TODO: computation wrong
104        double AvgDepth() const { return accumDepth / (double)Leaves();};
[1640]105        double AvgRays() const { return rayRefs / (double)Leaves();};
[1237]106
107        void Reset()
108        {
109                nodes = 0;
110                for (int i = 0; i < 3; ++ i)
111                        splits[i] = 0;
112               
113                maxDepth = 0;
114                minDepth = 99999;
115                accumDepth = 0;
116        pvs = 0;
117                maxDepthNodes = 0;
118                minPvsNodes = 0;
119                minRaysNodes = 0;
120                maxRayContribNodes = 0;
121                minProbabilityNodes = 0;
122                maxCostNodes = 0;
123
124                contributingSamples = 0;
125                sampleContributions = 0;
126
127                maxPvs = 0;
128                invalidLeaves = 0;
[1640]129                rayRefs = 0;
[1237]130                maxObjectRefs = 0;
[1449]131                mGlobalCostMisses = 0;
[1237]132        }
133
134        void Print(ostream &app) const;
135
136        friend ostream &operator<<(ostream &s, const VspTreeStatistics &stat)
137        {
138                stat.Print(s);
139                return s;
140        }
141};
142
143
144/**
145    VspNode abstract class serving for interior and leaf node implementation
146*/
147class VspNode
148{
149public:
150       
[1679]151        /// types of vsp nodes
[1237]152        enum {Interior, Leaf};
153
154        VspNode();
155        virtual ~VspNode(){};
156        VspNode(VspInterior *parent);
157
158        /** Determines whether this node is a leaf or not
159                @return true if leaf
160        */
161        virtual bool IsLeaf() const = 0;
162
163        virtual int Type() const = 0;
164
165        /** Determines whether this node is a root
166                @return true if root
167        */
168        virtual bool IsRoot() const;
[1679]169       
[1237]170        /** Returns parent node.
171        */
172        VspInterior *GetParent();
[1679]173       
[1237]174        /** Sets parent node.
175        */
176        void SetParent(VspInterior *parent);
[1679]177
[1237]178        /** Returns true if this node is a sibling of node n.
179        */
180        bool IsSibling(VspNode *n) const;
[1679]181       
[1237]182        /** returns depth of the node.
183        */
184        int GetDepth() const;
[1679]185       
[1237]186        /** returns true if the whole subtree is valid
187        */
188        bool TreeValid() const;
189
190        void SetTreeValid(const bool v);
[1679]191       
192        /** Cost of mergin this node.
193        */
194        float GetMergeCost() {return (float)-mTimeStamp; }
[1237]195
[1732]196        int mTimeStamp;
197
[1679]198        /////////
[1237]199        //-- mailing options
200
201        void Mail() { mMailbox = sMailId; }
202        static void NewMail() { ++ sMailId; }
203        bool Mailed() const { return mMailbox == sMailId; }
204
[1292]205
[1237]206        static int sMailId;
207        int mMailbox;
208
[1732]209        //int mPvsEntriesIncr;
210        //float mMemoryIncr;
211        //float mRenderCostDecr;
[1237]212
213protected:
214
215        /// if this sub tree is a completely valid view space region
216        bool mTreeValid;
[1679]217       
[1237]218        /// parent of this node
219        VspInterior *mParent;
220};
221
222
223/** BSP interior node implementation
224*/
225class VspInterior: public VspNode
226{
227public:
[1679]228
[1237]229        /** Standard contructor taking split plane as argument.
230        */
231        VspInterior(const AxisAlignedPlane &plane);
232
233        ~VspInterior();
[1679]234       
[1237]235        /** @return false since it is an interior node
236        */
237        bool IsLeaf() const;
238
239        int Type() const;
240
241        VspNode *GetBack();
242        VspNode *GetFront();
243
244        /** Returns split plane.
245        */
246        AxisAlignedPlane GetPlane() const;
247
248        /** Returns position of split plane.
249        */
250        float GetPosition() const;
251
252        /** Returns split axis.
253        */
254        int GetAxis() const;
255
256        /** Replace front or back child with new child.
257        */
258        void ReplaceChildLink(VspNode *oldChild, VspNode *newChild);
259
260        /** Replace front and back child.
261        */
262        void SetupChildLinks(VspNode *front, VspNode *back);
263
264        friend ostream &operator<<(ostream &s, const VspInterior &A)
265        {
266                return s << A.mPlane.mAxis << " " << A.mPlane.mPosition;
267        }
268
269        AxisAlignedBox3 GetBoundingBox() const;
270        void SetBoundingBox(const AxisAlignedBox3 &box);
271
272        /** Computes intersection of this plane with the ray segment.
273        */
274        int ComputeRayIntersection(const RayInfo &rayData, float &t) const
275        {
276                return rayData.ComputeRayIntersection(mPlane.mAxis, mPlane.mPosition, t);
277        }
278
279
280protected:
[1357]281        /// bounding box for this interior node: should we really store this?
[1237]282        AxisAlignedBox3 mBoundingBox;
283
284        /// Splitting plane corresponding to this node
285        AxisAlignedPlane mPlane;
286
287        /// back node
288        VspNode *mBack;
289        /// front node
290        VspNode *mFront;
291};
292
293
294/** BSP leaf node implementation.
295*/
296class VspLeaf: public VspNode
297{
298        friend VspTree;
299
300public:
301        VspLeaf();
302        VspLeaf(ViewCellLeaf *viewCell);
303        VspLeaf(VspInterior *parent);
304        VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell);
305
306        ~VspLeaf();
307
308        /** @return true since it is an interior node
309        */
310        bool IsLeaf() const;
311       
312        int Type() const;
313
314        /** Returns pointer of view cell.
315        */
316        ViewCellLeaf *GetViewCell() const;
317        /** Sets pointer to view cell.
318        */
319        void SetViewCell(ViewCellLeaf *viewCell);
320
[1297]321        SubdivisionCandidate *GetSubdivisionCandidate()
[1237]322        {
323                return mSubdivisionCandidate;
324        }
325
[1297]326        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
327        {
328                mSubdivisionCandidate = candidate;
329        }
330
331
[1237]332public:
333
334        /// Rays piercing this leaf.
335        VssRayContainer mVssRays;
[1679]336       
[1237]337        /// Probability that the view point lies in this leaf
338        float mProbability;
339
340protected:
341
342        /// pointer to a split plane candidate splitting this leaf
343        SubdivisionCandidate *mSubdivisionCandidate;
[1679]344       
[1237]345        /// if NULL this does not correspond to feasible viewcell
346        ViewCellLeaf *mViewCell;
347};
348
349
350/** View Space Partitioning tree.
351*/
352class VspTree
353{
354        friend class ViewCellsParseHandlers;
355        friend class HierarchyManager;
356
357public:
358       
359        /** Additional data which is passed down the BSP tree during traversal.
360        */
361        class VspTraversalData
362        { 
363        public:
364               
365                /** Returns average ray contribution.
366                */
367                float GetAvgRayContribution() const
368                {
369                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
370                }
371
372
373                VspTraversalData():
[1912]374                        mNode(NULL),
375                        mDepth(0),
376                        mRays(NULL),
377                        mPvs(0),
378                        mProbability(0.0),
379                        mMaxCostMisses(0),
380                        mPriority(0),
381                        mCorrectedPvs(0)
[1237]382                {}
383               
384                VspTraversalData(VspLeaf *node,
385                                                 const int depth,
386                                                 RayInfoContainer *rays,
[1765]387                                                 const float pvs,
[1237]388                                                 const float p,
389                                                 const AxisAlignedBox3 &box):
[1912]390                        mNode(node),
391                        mDepth(depth),
392                        mRays(rays),
393                        mProbability(p),
394                        mBoundingBox(box),
395                        mMaxCostMisses(0),
396                        mPriority(0),
397                        mCorrectedPvs(0),
398                        mPvs(pvs),
399                        mRenderCost(0),
400                        mCorrectedRenderCost(0)
[1237]401                {}
402
403                VspTraversalData(const int depth,
404                                                 RayInfoContainer *rays,
405                                                 const AxisAlignedBox3 &box):
[1912]406                        mNode(NULL),
407                        mDepth(depth),
408                        mRays(rays),
409                        mProbability(0),
410                        mMaxCostMisses(0),
411                        mBoundingBox(box),
412                        mCorrectedPvs(0),
413                        mPvs(0) ,
414                        mRenderCost(0),
415                        mCorrectedRenderCost(0)
[1237]416                {}
417
418                /** Returns cost of the traversal data.
419                */
420                float GetCost() const
421                {
422                        return mPriority;
423                }
424
425                /// deletes contents and sets them to NULL
426                void Clear()
427                {
428                        DEL_PTR(mRays);
[1297]429
430                        if (mNode)
431                        {
432                                // delete old view cell
433                                delete mNode->GetViewCell();
[1912]434
[1297]435                                delete mNode;
436                                mNode = NULL;
437                        }
[1237]438                }
439
[1294]440                /// the current node
441                VspLeaf *mNode;
442                /// current depth
443                int mDepth;
444                /// rays piercing this node
445                RayInfoContainer *mRays;
446                /// the probability that this node contains view point
447                float mProbability;
448                /// the bounding box of the node
449                AxisAlignedBox3 mBoundingBox;
450                /// how often this branch has missed the max-cost ratio
451                int mMaxCostMisses;
452                // current priority
453                float mPriority;
[1912]454                /// pvs size
455                float mPvs;
456                /// the correction factor for this pvs
457                float mCorrectedPvs;
458                /// pvs size
459                float mRenderCost;
460                /// the correction factor for this pvs
461                float mCorrectedRenderCost;
[1294]462
[1237]463                friend bool operator<(const VspTraversalData &a, const VspTraversalData &b)
464                {
465                        return a.GetCost() < b.GetCost();
466                }
467    };
468
469        /** Candidate for a view space split.
470        */
471        class VspSubdivisionCandidate: public SubdivisionCandidate
472        { 
473        public:
474
475                VspSubdivisionCandidate(const VspTraversalData &tData): mParentData(tData)
476                {};
477
[1305]478                ~VspSubdivisionCandidate()
479                {
480                        mParentData.Clear();
481                }
[1294]482
[1237]483                int Type() const { return VIEW_SPACE; }
484
[1667]485                void EvalCandidate(bool computeSplitplane = true)
[1237]486                {
[1695]487                        mDirty = false;
[1667]488                        sVspTree->EvalSubdivisionCandidate(*this, computeSplitplane);
[1237]489                }
490
491                bool GlobalTerminationCriteriaMet() const
492                {
493                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
494                }
495
[1633]496                bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet)
497                {
498                        VspNode *n = sVspTree->Subdivide(splitQueue, this, terminationCriteriaMet);
499                       
500                        // local or global termination criteria failed
501                        return !n->IsLeaf();           
502                }
503
504                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
505                                                                        const bool onlyUnmailed)
506                {
507                        sVspTree->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
508                }
509
[1912]510                VspSubdivisionCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):
511                        mSplitPlane(plane), mParentData(tData)
[1237]512                {}
[1667]513
514                float GetPriority() const
515                {
[1705]516                        return mPriority;
[1667]517                }
[1912]518
519                ////////////////////
520
521                static VspTree* sVspTree;
522
523                /// the current split plane
524                AxisAlignedPlane mSplitPlane;
525                /// parent node traversal data
526                VspTraversalData mParentData;
527       
528                float mCorrectedFrontPvs;
529                float mCorrectedBackPvs;
530
531                float mCorrectedFrontRenderCost;
532                float mCorrectedBackRenderCost;
[1913]533                float mCorrectedFrontVolume;
534                float mCorrectedBackVolume;
[1237]535        };
536
537        /** Struct for traversing line segment.
538        */
539        struct LineTraversalData
540        {
541                VspNode *mNode;
542                Vector3 mExitPoint;
543                float mMaxT;
544   
545                LineTraversalData () {}
546                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
547                mNode(n), mExitPoint(p), mMaxT(maxt) {}
548        };
549
550        /** Default constructor creating an empty tree.
551        */
552        VspTree();
553        /** Default destructor.
554        */
555        ~VspTree();
556
557        /** Returns BSP Tree statistics.
558        */
559        const VspTreeStatistics &GetStatistics() const;
560 
561        /** Returns bounding box of the specified node.
562        */
563        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
564
565        /** Returns list of BSP leaves with pvs smaller than
566                a certain threshold.
567                @param onlyUnmailed if only the unmailed leaves should be considered
568                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
569        */
570        void CollectLeaves(vector<VspLeaf *> &leaves,
571                                           const bool onlyUnmailed = false,
572                                           const int maxPvs = -1) const;
573
574        /** Returns box which bounds the whole tree.
575        */
576        AxisAlignedBox3 GetBoundingBox() const;
577
578        /** Returns root of the view space partitioning tree.
579        */
580        VspNode *GetRoot() const;
581
582        /** Collects the leaf view cells of the tree
583                @param viewCells returns the view cells
584        */
585        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
586
587        /** A ray is cast possible intersecting the tree.
588                @param the ray that is cast.
589                @returns the number of intersections with objects stored in the tree.
590        */
591        int CastRay(Ray &ray);
592
593
594        /** finds neighbouring leaves of this tree node.
595        */
596        int FindNeighbors(VspLeaf *n,
597                                          vector<VspLeaf *> &neighbors,
598                                          const bool onlyUnmailed) const;
599
600        /** Returns random leaf of BSP tree.
601                @param halfspace defines the halfspace from which the leaf is taken.
602        */
603        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
604
605        /** Returns random leaf of BSP tree.
606                @param onlyUnmailed if only unmailed leaves should be returned.
607        */
608        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
609
610        /** Returns epsilon of this tree.
611        */
612        float GetEpsilon() const;
613
614        /** Casts line segment into the tree.
615                @param origin the origin of the line segment
616                @param termination the end point of the line segment
617                @returns view cells intersecting the line segment.
618        */
619    int CastLineSegment(const Vector3 &origin,
620                                                const Vector3 &termination,
[1291]621                                                ViewCellContainer &viewcells,
622                                                const bool useMailboxing = true);
[1237]623
624               
625        /** Sets pointer to view cells manager.
626        */
627        void SetViewCellsManager(ViewCellsManager *vcm);
628
629        /** Returns view cell the current point is located in.
630                @param point the current view point
631                @param active if currently active view cells should be returned or
632                elementary view cell
633        */
634        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
635
636
637        /** Returns true if this view point is in a valid view space,
638                false otherwise.
639        */
640        bool ViewPointValid(const Vector3 &viewPoint) const;
641
642        /** Returns view cell corresponding to
643                the invalid view space.
644        */
645        VspViewCell *GetOutOfBoundsCell();
646
647        /** Writes tree to output stream
648        */
649        bool Export(OUT_STREAM &stream);
650
651        /** Casts beam, i.e. a 5D frustum of rays, into tree.
652                Tests conservative using the bounding box of the nodes.
653                @returns number of view cells it intersected
654        */
655        int CastBeam(Beam &beam);
656
657        /** Checks if tree validity-flags are right
658                with respect to view cell valitiy.
659                If not, marks subtree as invalid.
660        */
661        void ValidateTree();
662
663        /** Invalid view cells are added to the unbounded space
664        */
665        void CollapseViewCells();
666
667        /** Collects rays stored in the leaves.
668        */
669        void CollectRays(VssRayContainer &rays);
670
671        /** Intersects box with the tree and returns the number of intersected boxes.
672                @returns number of view cells found
673        */
674        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
675                                                                ViewCellContainer &viewCells) const;
676
677        /** Returns view cells of this ray, either taking precomputed cells
678                or by recomputation.
679        */
680        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
681
[1291]682        /** Returns view cells tree.
683        */
[1237]684        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
685
[1291]686        /** Sets the view cells tree.
687        */
[1237]688        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
689
[1570]690#if WORK_WITH_VIEWCELLS
691        /** Remove the references of the parent view cell from the kd nodes associated with
692                the objects.
693        */
694        void RemoveParentViewCellReferences(ViewCell *parent) const;
[1237]695
[1570]696        /** Adds references to the view cell to the kd nodes associated with the objects.
697        */
698        void AddViewCellReferences(ViewCell *vc) const;
699#endif
700
[1686]701        VspNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
[1684]702
[1237]703protected:
704
705        // --------------------------------------------------------------
706        // For sorting objects
707        // --------------------------------------------------------------
708        struct SortableEntry
709        {
710                enum EType
711                {
712                        ERayMin,
713                        ERayMax
714                };
715
716                int type;
717                float value;
718                VssRay *ray;
719 
720                SortableEntry() {}
721                SortableEntry(const int t, const float v, VssRay *r):
722                type(t), value(v), ray(r)
723                {
724                }
725               
[1314]726                friend inline bool operator<(const SortableEntry &a, const SortableEntry &b)
727                {       // prefer max event
728                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
729                        //      return (a.type == ERayMax);
730
731                        return (a.value < b.value);
[1237]732                }
733        };
734
735        /** faster evaluation of split plane cost for kd axis aligned cells.
736        */
737        float EvalLocalSplitCost(const VspTraversalData &data,
738                                                         const AxisAlignedBox3 &box,
739                                                         const int axis,
740                                                         const float &position,
741                                                         float &pFront,
742                                                         float &pBack) const;
743
744        void ComputeBoundingBox(const VssRayContainer &rays,
745                                                        AxisAlignedBox3 *forcedBoundingBox);
746
747        /** Evaluates candidate for splitting.
748        */
[1667]749        void EvalSubdivisionCandidate(VspSubdivisionCandidate &splitData,
750                                                                  bool computeSplitPlane = true);
[1237]751
752        /** Evaluates render cost decrease of next split.
753        */
[1912]754        float EvalRenderCostDecrease(VspSubdivisionCandidate &splitData,
[1237]755                                                                 float &normalizedOldRenderCost) const;
756
757        /** Collects view cells in the subtree under root.
758        */
759        void CollectViewCells(VspNode *root,
760                                                  bool onlyValid,
761                                                  ViewCellContainer &viewCells,
762                                                  bool onlyUnmailed = false) const;
763
764        /** Returns view cell corresponding to
765                the invalid view space. If it does not exist, it is created.
766        */
767        VspViewCell *GetOrCreateOutOfBoundsCell();
768
769        /** Collapses the tree with respect to the view cell partition,
770                i.e. leaves having the same view cell are collapsed.
771                @param node the root of the subtree to be collapsed
772                @param collapsed returns the number of collapsed nodes
773                @returns node of type leaf if the node could be collapsed,
774                this node otherwise
775        */
776        VspNode *CollapseTree(VspNode *node, int &collapsed);
777
778        /** Helper function revalidating the view cell leaf list after merge.
779        */
780        void RepairViewCellsLeafLists();
781
782        /** Evaluates tree stats in the BSP tree leafs.
783        */
784        void EvaluateLeafStats(const VspTraversalData &data);
785
786        /** Subdivides node using a best split priority queue.
787            @param tQueue the best split priority queue
788                @param splitCandidate the candidate for the next split
789                @param globalCriteriaMet if the global termination criteria were already met
790                @returns new root of the subtree
791        */
792        VspNode *Subdivide(SplitQueue &tQueue,
793                                           SubdivisionCandidate *splitCandidate,
794                                           const bool globalCriteriaMet);
795
796        /** Adds stats to subdivision log file.
797        */
798        void AddSubdivisionStats(const int viewCells,
799                                                         const float renderCostDecr,
800                                                         const float totalRenderCost,
801                                                         const float avgRenderCost);
802       
803        /** Subdivides leaf.
804                       
805                @param tData data object holding, e.g., a pointer to the leaf
806                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
807                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
808               
809                @param rays the polygons to be filtered
810                @param frontRays returns the polygons in front of the split plane
811       
812                @returns the root of the subdivision
813        */
[1912]814        VspInterior *SubdivideNode(const VspSubdivisionCandidate &sc,
[1237]815                                                           VspTraversalData &frontData,
816                               VspTraversalData &backData);
817
818        /** Selects an axis aligned for the next split.
819                @returns cost for this split
820        */
821        float SelectSplitPlane(const VspTraversalData &tData,
822                                                   AxisAlignedPlane &plane,
823                                                   float &pFront,
824                                                   float &pBack);
825
826        /** Sorts split candidates along the specified axis.
827                The split candidates are generated on possible visibility
828                events (i.e., where ray segments intersect the ray boundaries).
829                The sorted candidates are needed to compute the heuristics.
830
831                @param polys the input for choosing split candidates
832                @param axis the current split axis
833                @param splitCandidates returns sorted list of split candidates
834        */
835        void SortSubdivisionCandidates(const RayInfoContainer &rays,
[1912]836                                                                   const int axis,
837                                                                   float minBand,
838                                                                   float maxBand);
[1237]839
[1765]840        /** Evaluate render cost of this pvs.
[1237]841        */
[1765]842        float EvalPvsCost(const RayInfoContainer &rays) const;
[1237]843
[1576]844        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const;
845
846        /** Returns number of effective entries in the pvs.
847        */
848        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;
[1765]849
[1576]850        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
[1765]851
[1237]852        /** Computes best cost for axis aligned planes.
853        */
854        float EvalLocalCostHeuristics(const VspTraversalData &tData,
855                                                                  const AxisAlignedBox3 &box,
856                                                                  const int axis,
[1765]857                                                                  float &position,
858                                                                  const RayInfoContainer &usedRays);
[1237]859
[1291]860
861        //////////////////////////////////////////
862        // Helper function for computing heuristics
863
[1259]864        /** Evaluates the contribution to left and right pvs at a visibility event ve.
[1237]865                @param ve the visibility event
866                @param pvsLeft updates the left pvs
867                @param rightPvs updates the right pvs
868        */
[1765]869        void EvalHeuristics(const SortableEntry &ve, float &pvsLeft, float &pvsRight) const;
[1237]870
[1291]871        /** Evaluates contribution of min event to pvs
[1259]872        */
873        int EvalMinEventContribution(
874                const VssRay &ray, const bool isTermination) const;
[1237]875
[1291]876        /** Evaluates contribution of max event to pvs
877        */
[1259]878        int EvalMaxEventContribution(
879                const VssRay &ray, const bool isTermination) const;
880
[1291]881        /** Evaluates contribution of kd leaf when encountering a min event
882        */
[1259]883        int EvalMinEventContribution(KdLeaf *leaf) const;
[1291]884        /**  Evaluates contribution of kd leaf when encountering a max event
885        */
[1259]886        int EvalMaxEventContribution(KdLeaf *leaf) const;
887
[1237]888        /** Prepares objects for the heuristics.
[1291]889                @returns pvs size as seen by the rays.
[1237]890        */
[1765]891        float PrepareHeuristics(const RayInfoContainer &rays);
[1291]892       
893        /** Prepare a single ray for heuristics.
894        */
[1765]895        float PrepareHeuristics(const VssRay &ray, const bool isTermination);
896
[1291]897        /** Prepare a single kd leaf for heuristics.
898        */
[1765]899        float PrepareHeuristics(KdLeaf *leaf);
[1237]900
[1673]901       
[1291]902        /////////////////////////////////////////////////////////////////////////////
903
904
[1237]905        /** Subdivides the rays into front and back rays according to the split plane.
906               
907                @param plane the split plane
908                @param rays contains the rays to be split. The rays are
909                           distributed into front and back rays.
910                @param frontRays returns rays on the front side of the plane
911                @param backRays returns rays on the back side of the plane
912               
913                @returns the number of splits
914        */
915        int SplitRays(const AxisAlignedPlane &plane,
916                                  RayInfoContainer &rays,
917                              RayInfoContainer &frontRays,
918                                  RayInfoContainer &backRays) const;
919
[1576]920        void UpdatePvsEntriesContribution(
921                const VssRay &ray,
922                const bool isTermination,
923                const int cf,
924                float &frontPvs,
925                float &backPvs,
926                float &totalPvs) const;
927
[1237]928        /** Classfifies the object with respect to the
929                pvs of the front and back leaf and updates pvs size
930                accordingly.
931
932                @param obj the object to be added
933                @param cf the ray classification regarding the split plane
934                @param frontPvs returns the PVS of the front partition
935                @param backPvs returns the PVS of the back partition
936       
937        */
[1291]938        void UpdateContributionsToPvs(
939                const VssRay &ray,
940                const bool isTermination,
941                const int cf,
942                float &frontPvs,
943                float &backPvs,
944                float &totalPvs) const;
945
946        /** Evaluates the contribution for objects.
947        */
948        void UpdateContributionsToPvs(
[1289]949                Intersectable *obj,
950                const int cf,
951                float &frontPvs,
952                float &backPvs,
953                float &totalPvs) const;
954
[1291]955        /** Evaluates the contribution for bounding volume leaves.
956        */
957        void UpdateContributionsToPvs(
[1289]958                BvhLeaf *leaf,
959                const int cf,
960                float &frontPvs,
961                float &backPvs,
[1576]962                float &totalPvsm,
963                const bool countEntries = false) const;
[1289]964
[1291]965        /** Evaluates the contribution for kd leaves.
[1237]966        */
[1291]967        void UpdateContributionsToPvs(
968                KdLeaf *leaf,
[1237]969                const int cf,
970                float &frontPvs,
971                float &backPvs,
972                float &totalPvs) const;
973
974        /** Returns true if tree can be terminated.
975        */
[1251]976        bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
[1237]977
978        /** Returns true if global tree can be terminated.
979        */
[1251]980        bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
[1237]981
982        /** Adds ray sample contributions to the PVS.
983                @param sampleContributions the number contributions of the samples
984                @param contributingSampels the number of contributing rays
985               
986        */
987        void AddSamplesToPvs(VspLeaf *leaf,
988                                                 const RayInfoContainer &rays,
989                                                 float &sampleContributions,
990                                                 int &contributingSamples);
991
992        /** Propagates valid flag up the tree.
993        */
994        void PropagateUpValidity(VspNode *node);
995
996        /** Writes the node to disk
997                @note: should be implemented as visitor.
998        */
999        void ExportNode(VspNode *node, OUT_STREAM &stream);
1000
1001        /** Returns estimated memory usage of tree.
1002        */
1003        float GetMemUsage() const;
1004
1005        /** Updates view cell pvs of objects.
1006        */
1007        void ProcessViewCellObjects(ViewCell *parent,
[1633]1008                                                                ViewCell *front,
1009                                                                ViewCell *back) const;
[1237]1010
1011        void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
1012
1013        /** Collect split candidates which are affected by the last split
1014                and must be reevaluated.
1015        */
[1633]1016        void CollectDirtyCandidates(VspSubdivisionCandidate *sc,
1017                                                                vector<SubdivisionCandidate *> &dirtyList,
1018                                                                const bool onlyUnmailed);
[1237]1019
[1633]1020        void CollectDirtyCandidate(const VssRay &ray,
1021                                                           const bool isTermination,
1022                                                           vector<SubdivisionCandidate *> &dirtyList,
1023                                                           const bool onlyUnmailed) const;
[1294]1024
[1237]1025        /** Rays will be clipped to the bounding box.
1026        */
1027        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
1028
1029        /** Evaluate subdivision statistics.
1030        */
1031        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
1032
[1779]1033        void PrepareConstruction(SplitQueue &tQueue,
1034                                                         const VssRayContainer &sampleRays,
1035                                                         RayInfoContainer &rays);
[1237]1036
[1291]1037        /** Evaluates pvs contribution of this ray.
[1259]1038        */
[1291]1039        int EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
[1259]1040
[1291]1041        /** Evaluates pvs contribution of a kd node.
1042        */
1043        int EvalContributionToPvs(KdLeaf *leaf) const;
1044
[1640]1045        /** Creates new root of hierarchy and computes bounding box.
1046                Has to be called before the preparation of the subdivision.
1047        */
1048        void Initialise(const VssRayContainer &rays,
1049                                        AxisAlignedBox3 *forcedBoundingBox);
[1291]1050
[1845]1051        int CompressObjects();
[1844]1052
[1845]1053        int CompressObjects(VspLeaf *leaf);
[1844]1054
[1237]1055protected:
1056
1057        /// pointer to the hierarchy of view cells
1058        ViewCellsTree *mViewCellsTree;
1059
[1259]1060        HierarchyManager *mHierarchyManager;
1061        //OspTree *mOspTree;
1062        //bool mUseKdPvsForHeuristics;
1063       
[1237]1064        ViewCellsManager *mViewCellsManager;
1065       
1066        vector<SortableEntry> *mLocalSubdivisionCandidates;
1067
1068        /// Pointer to the root of the tree
1069        VspNode *mRoot;
1070               
1071        VspTreeStatistics mVspStats;
1072       
1073        /// View cell corresponding to the space outside the valid view space
1074        VspViewCell *mOutOfBoundsCell;
1075
1076        /// box around the whole view domain
1077        AxisAlignedBox3 mBoundingBox;
1078
1079
1080        //-- local termination
1081
1082        /// minimal number of rays before subdivision termination
1083        int mTermMinRays;
1084        /// maximal possible depth
1085        int mTermMaxDepth;
1086        /// mininum probability
1087        float mTermMinProbability;
1088        /// mininum PVS
1089        int mTermMinPvs;
1090        /// maximal contribution per ray
1091        float mTermMaxRayContribution;
1092        /// maximal acceptable cost ratio
1093        float mTermMaxCostRatio;
1094        /// tolerance value indicating how often the max cost ratio can be failed
1095        int mTermMissTolerance;
1096
1097
1098        //-- global criteria
1099        float mTermMinGlobalCostRatio;
1100        int mTermGlobalCostMissTolerance;
[1449]1101       
[1237]1102
1103        /// maximal number of view cells
1104        int mMaxViewCells;
1105        /// maximal tree memory
1106        float mMaxMemory;
1107        /// the tree is out of memory
1108        bool mOutOfMemory;
1109
[1673]1110        ////////////
[1237]1111        //-- split heuristics based parameters
1112       
1113        bool mUseCostHeuristics;
1114        /// balancing factor for PVS criterium
1115        float mCtDivCi;
1116        /// if only driving axis should be used for split
1117        bool mOnlyDrivingAxis;
1118        /// if random split axis should be used
1119        bool mUseRandomAxis;
1120        /// if vsp bsp tree should simulate octree
1121        bool mCirculatingAxis;
1122        /// minimal relative position where the split axis can be placed
1123        float mMinBand;
1124        /// maximal relative position where the split axis can be placed
1125        float mMaxBand;
1126
1127
1128        /// current time stamp (used for keeping split history)
1129        int mTimeStamp;
1130        // if rays should be stored in leaves
1131        bool mStoreRays;
1132
1133        /// epsilon for geometric comparisons
1134        float mEpsilon;
1135
1136        /// subdivision stats output file
1137        ofstream  mSubdivisionStats;
1138        /// keeps track of cost during subdivision
1139        float mTotalCost;
[1662]1140        int mPvsEntries;
[1237]1141        /// keeps track of overall pvs size during subdivision
1142        int mTotalPvsSize;
1143        /// number of currenly generated view cells
1144        int mCreatedViewCells;
1145
1146        /// weight between render cost decrease and node render cost
1147        float mRenderCostDecreaseWeight;
1148
1149        int mMaxTests;
[1732]1150
1151        /// constant value for driving the heuristics
1152        float mMemoryConst;
[1237]1153};
1154
1155
1156}
1157
1158#endif
Note: See TracBrowser for help on using the repository browser.