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

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