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

Revision 1314, 25.9 KB checked in by mattausch, 18 years ago (diff)

started osp mesh construction for obj files. Introduced new primitive faceintersectable

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