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

Revision 1676, 27.8 KB checked in by mattausch, 18 years ago (diff)

worked on pvs heuristics

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