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

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