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

Revision 1845, 27.9 KB checked in by mattausch, 18 years ago (diff)

improved object pvs

Line 
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"
12#include "SubdivisionCandidate.h"
13#include "HierarchyManager.h"
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;
34class HierarchyManager;
35class KdIntersectable;
36class KdTree;
37class VspTree;
38class KdTreeStatistics;
39
40
41#define WORK_WITH_VIEWCELLS 0
42
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;
84        /// number of rays refs
85        int rayRefs;
86        /// overall pvs size
87        int pvs;
88        // accumulated depth (used to compute average)
89        int accumDepth;
90        // global cost ratio violations
91        int mGlobalCostMisses;
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();};
105        double AvgRays() const { return rayRefs / (double)Leaves();};
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;
129                rayRefs = 0;
130                maxObjectRefs = 0;
131                mGlobalCostMisses = 0;
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       
151        /// types of vsp nodes
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;
169       
170        /** Returns parent node.
171        */
172        VspInterior *GetParent();
173       
174        /** Sets parent node.
175        */
176        void SetParent(VspInterior *parent);
177
178        /** Returns true if this node is a sibling of node n.
179        */
180        bool IsSibling(VspNode *n) const;
181       
182        /** returns depth of the node.
183        */
184        int GetDepth() const;
185       
186        /** returns true if the whole subtree is valid
187        */
188        bool TreeValid() const;
189
190        void SetTreeValid(const bool v);
191       
192        /** Cost of mergin this node.
193        */
194        float GetMergeCost() {return (float)-mTimeStamp; }
195
196        int mTimeStamp;
197
198        /////////
199        //-- mailing options
200
201        void Mail() { mMailbox = sMailId; }
202        static void NewMail() { ++ sMailId; }
203        bool Mailed() const { return mMailbox == sMailId; }
204
205
206        static int sMailId;
207        int mMailbox;
208
209        //int mPvsEntriesIncr;
210        //float mMemoryIncr;
211        //float mRenderCostDecr;
212
213protected:
214
215        /// if this sub tree is a completely valid view space region
216        bool mTreeValid;
217       
218        /// parent of this node
219        VspInterior *mParent;
220};
221
222
223/** BSP interior node implementation
224*/
225class VspInterior: public VspNode
226{
227public:
228
229        /** Standard contructor taking split plane as argument.
230        */
231        VspInterior(const AxisAlignedPlane &plane);
232
233        ~VspInterior();
234       
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:
281        /// bounding box for this interior node: should we really store this?
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
321        SubdivisionCandidate *GetSubdivisionCandidate()
322        {
323                return mSubdivisionCandidate;
324        }
325
326        void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
327        {
328                mSubdivisionCandidate = candidate;
329        }
330
331
332public:
333
334        /// Rays piercing this leaf.
335        VssRayContainer mVssRays;
336       
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;
344       
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():
374                mNode(NULL),
375                mDepth(0),
376                mRays(NULL),
377                mPvs(0),
378                mProbability(0.0),
379                mMaxCostMisses(0),
380                mPriority(0)
381                {}
382               
383                VspTraversalData(VspLeaf *node,
384                                                 const int depth,
385                                                 RayInfoContainer *rays,
386                                                 const float pvs,
387                                                 const float p,
388                                                 const AxisAlignedBox3 &box):
389                mNode(node),
390                mDepth(depth),
391                mRays(rays),
392                mPvs(pvs),
393                mProbability(p),
394                mBoundingBox(box),
395                mMaxCostMisses(0),
396                mPriority(0)
397                {}
398
399                VspTraversalData(const int depth,
400                                                 RayInfoContainer *rays,
401                                                 const AxisAlignedBox3 &box):
402                mNode(NULL),
403                mDepth(depth),
404                mRays(rays),
405                mPvs(0),
406                mProbability(0),
407                mMaxCostMisses(0),
408                mBoundingBox(box)
409                {}
410
411                /** Returns cost of the traversal data.
412                */
413                float GetCost() const
414                {
415                        return mPriority;
416                }
417
418                /// deletes contents and sets them to NULL
419                void Clear()
420                {
421                        DEL_PTR(mRays);
422
423                        if (mNode)
424                        {
425                                // delete old view cell
426                                delete mNode->GetViewCell();
427                                delete mNode;
428                                mNode = NULL;
429                        }
430                }
431
432                /// the current node
433                VspLeaf *mNode;
434                /// current depth
435                int mDepth;
436                /// rays piercing this node
437                RayInfoContainer *mRays;
438                /// the probability that this node contains view point
439                float mProbability;
440                /// the bounding box of the node
441                AxisAlignedBox3 mBoundingBox;
442                /// pvs size
443                float mPvs;
444                /// how often this branch has missed the max-cost ratio
445                int mMaxCostMisses;
446                // current priority
447                float mPriority;
448
449               
450                friend bool operator<(const VspTraversalData &a, const VspTraversalData &b)
451                {
452                        return a.GetCost() < b.GetCost();
453                }
454    };
455
456        /** Candidate for a view space split.
457        */
458        class VspSubdivisionCandidate: public SubdivisionCandidate
459        { 
460        public:
461
462                static VspTree* sVspTree;
463
464                /// the current split plane
465                AxisAlignedPlane mSplitPlane;
466                /// parent node traversal data
467                VspTraversalData mParentData;
468               
469                VspSubdivisionCandidate(const VspTraversalData &tData): mParentData(tData)
470                {};
471
472                ~VspSubdivisionCandidate()
473                {
474                        mParentData.Clear();
475                }
476
477                int Type() const { return VIEW_SPACE; }
478
479                void EvalCandidate(bool computeSplitplane = true)
480                {
481                        mDirty = false;
482                        sVspTree->EvalSubdivisionCandidate(*this, computeSplitplane);
483                }
484
485                bool GlobalTerminationCriteriaMet() const
486                {
487                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
488                }
489
490                bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet)
491                {
492                        VspNode *n = sVspTree->Subdivide(splitQueue, this, terminationCriteriaMet);
493                       
494                        // local or global termination criteria failed
495                        return !n->IsLeaf();           
496                }
497
498                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
499                                                                        const bool onlyUnmailed)
500                {
501                        sVspTree->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
502                }
503
504        VspSubdivisionCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):
505                mSplitPlane(plane), mParentData(tData)
506                {}
507
508                float GetPriority() const
509                {
510                        return mPriority;
511                }
512        };
513
514        /** Struct for traversing line segment.
515        */
516        struct LineTraversalData
517        {
518                VspNode *mNode;
519                Vector3 mExitPoint;
520                float mMaxT;
521   
522                LineTraversalData () {}
523                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
524                mNode(n), mExitPoint(p), mMaxT(maxt) {}
525        };
526
527        /** Default constructor creating an empty tree.
528        */
529        VspTree();
530        /** Default destructor.
531        */
532        ~VspTree();
533
534        /** Returns BSP Tree statistics.
535        */
536        const VspTreeStatistics &GetStatistics() const;
537 
538        /** Returns bounding box of the specified node.
539        */
540        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
541
542        /** Returns list of BSP leaves with pvs smaller than
543                a certain threshold.
544                @param onlyUnmailed if only the unmailed leaves should be considered
545                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
546        */
547        void CollectLeaves(vector<VspLeaf *> &leaves,
548                                           const bool onlyUnmailed = false,
549                                           const int maxPvs = -1) const;
550
551        /** Returns box which bounds the whole tree.
552        */
553        AxisAlignedBox3 GetBoundingBox() const;
554
555        /** Returns root of the view space partitioning tree.
556        */
557        VspNode *GetRoot() const;
558
559        /** Collects the leaf view cells of the tree
560                @param viewCells returns the view cells
561        */
562        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
563
564        /** A ray is cast possible intersecting the tree.
565                @param the ray that is cast.
566                @returns the number of intersections with objects stored in the tree.
567        */
568        int CastRay(Ray &ray);
569
570
571        /** finds neighbouring leaves of this tree node.
572        */
573        int FindNeighbors(VspLeaf *n,
574                                          vector<VspLeaf *> &neighbors,
575                                          const bool onlyUnmailed) const;
576
577        /** Returns random leaf of BSP tree.
578                @param halfspace defines the halfspace from which the leaf is taken.
579        */
580        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
581
582        /** Returns random leaf of BSP tree.
583                @param onlyUnmailed if only unmailed leaves should be returned.
584        */
585        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
586
587        /** Returns epsilon of this tree.
588        */
589        float GetEpsilon() const;
590
591        /** Casts line segment into the tree.
592                @param origin the origin of the line segment
593                @param termination the end point of the line segment
594                @returns view cells intersecting the line segment.
595        */
596    int CastLineSegment(const Vector3 &origin,
597                                                const Vector3 &termination,
598                                                ViewCellContainer &viewcells,
599                                                const bool useMailboxing = true);
600
601               
602        /** Sets pointer to view cells manager.
603        */
604        void SetViewCellsManager(ViewCellsManager *vcm);
605
606        /** Returns view cell the current point is located in.
607                @param point the current view point
608                @param active if currently active view cells should be returned or
609                elementary view cell
610        */
611        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
612
613
614        /** Returns true if this view point is in a valid view space,
615                false otherwise.
616        */
617        bool ViewPointValid(const Vector3 &viewPoint) const;
618
619        /** Returns view cell corresponding to
620                the invalid view space.
621        */
622        VspViewCell *GetOutOfBoundsCell();
623
624        /** Writes tree to output stream
625        */
626        bool Export(OUT_STREAM &stream);
627
628        /** Casts beam, i.e. a 5D frustum of rays, into tree.
629                Tests conservative using the bounding box of the nodes.
630                @returns number of view cells it intersected
631        */
632        int CastBeam(Beam &beam);
633
634        /** Checks if tree validity-flags are right
635                with respect to view cell valitiy.
636                If not, marks subtree as invalid.
637        */
638        void ValidateTree();
639
640        /** Invalid view cells are added to the unbounded space
641        */
642        void CollapseViewCells();
643
644        /** Collects rays stored in the leaves.
645        */
646        void CollectRays(VssRayContainer &rays);
647
648        /** Intersects box with the tree and returns the number of intersected boxes.
649                @returns number of view cells found
650        */
651        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
652                                                                ViewCellContainer &viewCells) const;
653
654        /** Returns view cells of this ray, either taking precomputed cells
655                or by recomputation.
656        */
657        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
658
659        /** Returns view cells tree.
660        */
661        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
662
663        /** Sets the view cells tree.
664        */
665        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
666
667#if WORK_WITH_VIEWCELLS
668        /** Remove the references of the parent view cell from the kd nodes associated with
669                the objects.
670        */
671        void RemoveParentViewCellReferences(ViewCell *parent) const;
672
673        /** Adds references to the view cell to the kd nodes associated with the objects.
674        */
675        void AddViewCellReferences(ViewCell *vc) const;
676#endif
677
678        VspNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
679
680protected:
681
682        // --------------------------------------------------------------
683        // For sorting objects
684        // --------------------------------------------------------------
685        struct SortableEntry
686        {
687                enum EType
688                {
689                        ERayMin,
690                        ERayMax
691                };
692
693                int type;
694                float value;
695                VssRay *ray;
696 
697                SortableEntry() {}
698                SortableEntry(const int t, const float v, VssRay *r):
699                type(t), value(v), ray(r)
700                {
701                }
702               
703                friend inline bool operator<(const SortableEntry &a, const SortableEntry &b)
704                {       // prefer max event
705                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
706                        //      return (a.type == ERayMax);
707
708                        return (a.value < b.value);
709                }
710        };
711
712        /** faster evaluation of split plane cost for kd axis aligned cells.
713        */
714        float EvalLocalSplitCost(const VspTraversalData &data,
715                                                         const AxisAlignedBox3 &box,
716                                                         const int axis,
717                                                         const float &position,
718                                                         float &pFront,
719                                                         float &pBack) const;
720
721        void ComputeBoundingBox(const VssRayContainer &rays,
722                                                        AxisAlignedBox3 *forcedBoundingBox);
723
724        /** Evaluates candidate for splitting.
725        */
726        void EvalSubdivisionCandidate(VspSubdivisionCandidate &splitData,
727                                                                  bool computeSplitPlane = true);
728
729        /** Evaluates render cost decrease of next split.
730        */
731        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
732                                                                 const VspTraversalData &data,
733                                                                 float &normalizedOldRenderCost) const;
734
735        /** Collects view cells in the subtree under root.
736        */
737        void CollectViewCells(VspNode *root,
738                                                  bool onlyValid,
739                                                  ViewCellContainer &viewCells,
740                                                  bool onlyUnmailed = false) const;
741
742        /** Returns view cell corresponding to
743                the invalid view space. If it does not exist, it is created.
744        */
745        VspViewCell *GetOrCreateOutOfBoundsCell();
746
747        /** Collapses the tree with respect to the view cell partition,
748                i.e. leaves having the same view cell are collapsed.
749                @param node the root of the subtree to be collapsed
750                @param collapsed returns the number of collapsed nodes
751                @returns node of type leaf if the node could be collapsed,
752                this node otherwise
753        */
754        VspNode *CollapseTree(VspNode *node, int &collapsed);
755
756        /** Helper function revalidating the view cell leaf list after merge.
757        */
758        void RepairViewCellsLeafLists();
759
760        /** Evaluates tree stats in the BSP tree leafs.
761        */
762        void EvaluateLeafStats(const VspTraversalData &data);
763
764        /** Subdivides node using a best split priority queue.
765            @param tQueue the best split priority queue
766                @param splitCandidate the candidate for the next split
767                @param globalCriteriaMet if the global termination criteria were already met
768                @returns new root of the subtree
769        */
770        VspNode *Subdivide(SplitQueue &tQueue,
771                                           SubdivisionCandidate *splitCandidate,
772                                           const bool globalCriteriaMet);
773
774        /** Adds stats to subdivision log file.
775        */
776        void AddSubdivisionStats(const int viewCells,
777                                                         const float renderCostDecr,
778                                                         const float totalRenderCost,
779                                                         const float avgRenderCost);
780       
781        /** Subdivides leaf.
782                       
783                @param tData data object holding, e.g., a pointer to the leaf
784                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
785                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
786               
787                @param rays the polygons to be filtered
788                @param frontRays returns the polygons in front of the split plane
789       
790                @returns the root of the subdivision
791        */
792        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
793                                                           VspTraversalData &tData,
794                                                           VspTraversalData &frontData,
795                               VspTraversalData &backData);
796
797        /** Selects an axis aligned for the next split.
798                @returns cost for this split
799        */
800        float SelectSplitPlane(const VspTraversalData &tData,
801                                                   AxisAlignedPlane &plane,
802                                                   float &pFront,
803                                                   float &pBack);
804
805        /** Sorts split candidates along the specified axis.
806                The split candidates are generated on possible visibility
807                events (i.e., where ray segments intersect the ray boundaries).
808                The sorted candidates are needed to compute the heuristics.
809
810                @param polys the input for choosing split candidates
811                @param axis the current split axis
812                @param splitCandidates returns sorted list of split candidates
813        */
814        void SortSubdivisionCandidates(const RayInfoContainer &rays,
815                                                         const int axis,
816                                                         float minBand,
817                                                         float maxBand);
818
819        /** Evaluate render cost of this pvs.
820        */
821        float EvalPvsCost(const RayInfoContainer &rays) const;
822
823        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const;
824
825        /** Returns number of effective entries in the pvs.
826        */
827        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;
828
829        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
830
831        /** Computes best cost for axis aligned planes.
832        */
833        float EvalLocalCostHeuristics(const VspTraversalData &tData,
834                                                                  const AxisAlignedBox3 &box,
835                                                                  const int axis,
836                                                                  float &position,
837                                                                  const RayInfoContainer &usedRays);
838
839
840        //////////////////////////////////////////
841        // Helper function for computing heuristics
842
843        /** Evaluates the contribution to left and right pvs at a visibility event ve.
844                @param ve the visibility event
845                @param pvsLeft updates the left pvs
846                @param rightPvs updates the right pvs
847        */
848        void EvalHeuristics(const SortableEntry &ve, float &pvsLeft, float &pvsRight) const;
849
850        /** Evaluates contribution of min event to pvs
851        */
852        int EvalMinEventContribution(
853                const VssRay &ray, const bool isTermination) const;
854
855        /** Evaluates contribution of max event to pvs
856        */
857        int EvalMaxEventContribution(
858                const VssRay &ray, const bool isTermination) const;
859
860        /** Evaluates contribution of kd leaf when encountering a min event
861        */
862        int EvalMinEventContribution(KdLeaf *leaf) const;
863        /**  Evaluates contribution of kd leaf when encountering a max event
864        */
865        int EvalMaxEventContribution(KdLeaf *leaf) const;
866
867        /** Prepares objects for the heuristics.
868                @returns pvs size as seen by the rays.
869        */
870        float PrepareHeuristics(const RayInfoContainer &rays);
871       
872        /** Prepare a single ray for heuristics.
873        */
874        float PrepareHeuristics(const VssRay &ray, const bool isTermination);
875
876        /** Prepare a single kd leaf for heuristics.
877        */
878        float PrepareHeuristics(KdLeaf *leaf);
879
880       
881        /////////////////////////////////////////////////////////////////////////////
882
883
884        /** Subdivides the rays into front and back rays according to the split plane.
885               
886                @param plane the split plane
887                @param rays contains the rays to be split. The rays are
888                           distributed into front and back rays.
889                @param frontRays returns rays on the front side of the plane
890                @param backRays returns rays on the back side of the plane
891               
892                @returns the number of splits
893        */
894        int SplitRays(const AxisAlignedPlane &plane,
895                                  RayInfoContainer &rays,
896                              RayInfoContainer &frontRays,
897                                  RayInfoContainer &backRays) const;
898
899        void UpdatePvsEntriesContribution(
900                const VssRay &ray,
901                const bool isTermination,
902                const int cf,
903                float &frontPvs,
904                float &backPvs,
905                float &totalPvs) const;
906
907        /** Classfifies the object with respect to the
908                pvs of the front and back leaf and updates pvs size
909                accordingly.
910
911                @param obj the object to be added
912                @param cf the ray classification regarding the split plane
913                @param frontPvs returns the PVS of the front partition
914                @param backPvs returns the PVS of the back partition
915       
916        */
917        void UpdateContributionsToPvs(
918                const VssRay &ray,
919                const bool isTermination,
920                const int cf,
921                float &frontPvs,
922                float &backPvs,
923                float &totalPvs) const;
924
925        /** Evaluates the contribution for objects.
926        */
927        void UpdateContributionsToPvs(
928                Intersectable *obj,
929                const int cf,
930                float &frontPvs,
931                float &backPvs,
932                float &totalPvs) const;
933
934        /** Evaluates the contribution for bounding volume leaves.
935        */
936        void UpdateContributionsToPvs(
937                BvhLeaf *leaf,
938                const int cf,
939                float &frontPvs,
940                float &backPvs,
941                float &totalPvsm,
942                const bool countEntries = false) const;
943
944        /** Evaluates the contribution for kd leaves.
945        */
946        void UpdateContributionsToPvs(
947                KdLeaf *leaf,
948                const int cf,
949                float &frontPvs,
950                float &backPvs,
951                float &totalPvs) const;
952
953        /** Returns true if tree can be terminated.
954        */
955        bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
956
957        /** Returns true if global tree can be terminated.
958        */
959        bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
960
961        /** Adds ray sample contributions to the PVS.
962                @param sampleContributions the number contributions of the samples
963                @param contributingSampels the number of contributing rays
964               
965        */
966        void AddSamplesToPvs(VspLeaf *leaf,
967                                                 const RayInfoContainer &rays,
968                                                 float &sampleContributions,
969                                                 int &contributingSamples);
970
971        /** Propagates valid flag up the tree.
972        */
973        void PropagateUpValidity(VspNode *node);
974
975        /** Writes the node to disk
976                @note: should be implemented as visitor.
977        */
978        void ExportNode(VspNode *node, OUT_STREAM &stream);
979
980        /** Returns estimated memory usage of tree.
981        */
982        float GetMemUsage() const;
983
984        /** Updates view cell pvs of objects.
985        */
986        void ProcessViewCellObjects(ViewCell *parent,
987                                                                ViewCell *front,
988                                                                ViewCell *back) const;
989
990        void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
991
992        /** Collect split candidates which are affected by the last split
993                and must be reevaluated.
994        */
995        void CollectDirtyCandidates(VspSubdivisionCandidate *sc,
996                                                                vector<SubdivisionCandidate *> &dirtyList,
997                                                                const bool onlyUnmailed);
998
999        void CollectDirtyCandidate(const VssRay &ray,
1000                                                           const bool isTermination,
1001                                                           vector<SubdivisionCandidate *> &dirtyList,
1002                                                           const bool onlyUnmailed) const;
1003
1004        /** Rays will be clipped to the bounding box.
1005        */
1006        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
1007
1008        /** Evaluate subdivision statistics.
1009        */
1010        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
1011
1012        void PrepareConstruction(SplitQueue &tQueue,
1013                                                         const VssRayContainer &sampleRays,
1014                                                         RayInfoContainer &rays);
1015
1016        /** Evaluates pvs contribution of this ray.
1017        */
1018        int EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
1019
1020        /** Evaluates pvs contribution of a kd node.
1021        */
1022        int EvalContributionToPvs(KdLeaf *leaf) const;
1023
1024        /** Creates new root of hierarchy and computes bounding box.
1025                Has to be called before the preparation of the subdivision.
1026        */
1027        void Initialise(const VssRayContainer &rays,
1028                                        AxisAlignedBox3 *forcedBoundingBox);
1029
1030        int CompressObjects();
1031
1032        int CompressObjects(VspLeaf *leaf);
1033
1034protected:
1035
1036        /// pointer to the hierarchy of view cells
1037        ViewCellsTree *mViewCellsTree;
1038
1039        HierarchyManager *mHierarchyManager;
1040        //OspTree *mOspTree;
1041        //bool mUseKdPvsForHeuristics;
1042       
1043        ViewCellsManager *mViewCellsManager;
1044       
1045        vector<SortableEntry> *mLocalSubdivisionCandidates;
1046
1047        /// Pointer to the root of the tree
1048        VspNode *mRoot;
1049               
1050        VspTreeStatistics mVspStats;
1051       
1052        /// View cell corresponding to the space outside the valid view space
1053        VspViewCell *mOutOfBoundsCell;
1054
1055        /// box around the whole view domain
1056        AxisAlignedBox3 mBoundingBox;
1057
1058
1059        //-- local termination
1060
1061        /// minimal number of rays before subdivision termination
1062        int mTermMinRays;
1063        /// maximal possible depth
1064        int mTermMaxDepth;
1065        /// mininum probability
1066        float mTermMinProbability;
1067        /// mininum PVS
1068        int mTermMinPvs;
1069        /// maximal contribution per ray
1070        float mTermMaxRayContribution;
1071        /// maximal acceptable cost ratio
1072        float mTermMaxCostRatio;
1073        /// tolerance value indicating how often the max cost ratio can be failed
1074        int mTermMissTolerance;
1075
1076
1077        //-- global criteria
1078        float mTermMinGlobalCostRatio;
1079        int mTermGlobalCostMissTolerance;
1080       
1081
1082        /// maximal number of view cells
1083        int mMaxViewCells;
1084        /// maximal tree memory
1085        float mMaxMemory;
1086        /// the tree is out of memory
1087        bool mOutOfMemory;
1088
1089        ////////////
1090        //-- split heuristics based parameters
1091       
1092        bool mUseCostHeuristics;
1093        /// balancing factor for PVS criterium
1094        float mCtDivCi;
1095        /// if only driving axis should be used for split
1096        bool mOnlyDrivingAxis;
1097        /// if random split axis should be used
1098        bool mUseRandomAxis;
1099        /// if vsp bsp tree should simulate octree
1100        bool mCirculatingAxis;
1101        /// minimal relative position where the split axis can be placed
1102        float mMinBand;
1103        /// maximal relative position where the split axis can be placed
1104        float mMaxBand;
1105
1106
1107        /// current time stamp (used for keeping split history)
1108        int mTimeStamp;
1109        // if rays should be stored in leaves
1110        bool mStoreRays;
1111
1112        /// epsilon for geometric comparisons
1113        float mEpsilon;
1114
1115        /// subdivision stats output file
1116        ofstream  mSubdivisionStats;
1117        /// keeps track of cost during subdivision
1118        float mTotalCost;
1119        int mPvsEntries;
1120        /// keeps track of overall pvs size during subdivision
1121        int mTotalPvsSize;
1122        /// number of currenly generated view cells
1123        int mCreatedViewCells;
1124
1125        /// weight between render cost decrease and node render cost
1126        float mRenderCostDecreaseWeight;
1127
1128        int mMaxTests;
1129
1130        /// constant value for driving the heuristics
1131        float mMemoryConst;
1132};
1133
1134
1135}
1136
1137#endif
Note: See TracBrowser for help on using the repository browser.