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

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