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

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