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

Revision 1696, 28.5 KB checked in by mattausch, 18 years ago (diff)

removed memory leaks
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                        mDirty = false;
483                        sVspTree->EvalSubdivisionCandidate(*this, computeSplitplane);
484                }
485
486                bool GlobalTerminationCriteriaMet() const
487                {
488                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
489                }
490
491                bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet)
492                {
493                        VspNode *n = sVspTree->Subdivide(splitQueue, this, terminationCriteriaMet);
494                       
495                        // local or global termination criteria failed
496                        return !n->IsLeaf();           
497                }
498
499                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
500                                                                        const bool onlyUnmailed)
501                {
502                        sVspTree->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
503                }
504
505        VspSubdivisionCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):
506                mSplitPlane(plane), mParentData(tData)
507                {}
508
509                float GetPriority() const
510                {
511                        HierarchyManager *hm = sVspTree->mHierarchyManager;
512                       
513                        if (hm->ConsiderMemory())
514                        {
515                                const float rc = mRenderCostDecrease / (hm->mInitialRenderCost - hm->GetHierarchyStats().mTotalCost + 1.0f);
516                                //const float mc = mMemoryIncr /  / hm->GetHierarchyStats().mMemory;
517                                //const float rc = mPriority / (hm->mInitialRenderCost - hm->GetHierarchyStats().mTotalCost + 1.0f);
518                                const float mc = (float)mPvsEntriesIncr / (float)hm->GetHierarchyStats().mPvsEntries;   
519                               
520                                //cout << "\np: " << mPriority << " i: " << hm->mInitialRenderCost << " t: " << hm->GetHierarchyStats().mTotalCost << endl;
521                                //cout << "vsp rc: " << rc << " mc: " << mc << endl;
522                               
523                                return hm->GetMemoryConst() * rc - (1.0f - hm->GetMemoryConst()) * mc;
524                        }
525                        else
526                        {
527                                return mPriority;
528                        }
529                }
530        };
531
532        /** Struct for traversing line segment.
533        */
534        struct LineTraversalData
535        {
536                VspNode *mNode;
537                Vector3 mExitPoint;
538                float mMaxT;
539   
540                LineTraversalData () {}
541                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
542                mNode(n), mExitPoint(p), mMaxT(maxt) {}
543        };
544
545        /** Default constructor creating an empty tree.
546        */
547        VspTree();
548        /** Default destructor.
549        */
550        ~VspTree();
551
552        /** Returns BSP Tree statistics.
553        */
554        const VspTreeStatistics &GetStatistics() const;
555 
556        /** Returns bounding box of the specified node.
557        */
558        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
559
560        /** Returns list of BSP leaves with pvs smaller than
561                a certain threshold.
562                @param onlyUnmailed if only the unmailed leaves should be considered
563                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
564        */
565        void CollectLeaves(vector<VspLeaf *> &leaves,
566                                           const bool onlyUnmailed = false,
567                                           const int maxPvs = -1) const;
568
569        /** Returns box which bounds the whole tree.
570        */
571        AxisAlignedBox3 GetBoundingBox() const;
572
573        /** Returns root of the view space partitioning tree.
574        */
575        VspNode *GetRoot() const;
576
577        /** Collects the leaf view cells of the tree
578                @param viewCells returns the view cells
579        */
580        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
581
582        /** A ray is cast possible intersecting the tree.
583                @param the ray that is cast.
584                @returns the number of intersections with objects stored in the tree.
585        */
586        int CastRay(Ray &ray);
587
588
589        /** finds neighbouring leaves of this tree node.
590        */
591        int FindNeighbors(VspLeaf *n,
592                                          vector<VspLeaf *> &neighbors,
593                                          const bool onlyUnmailed) const;
594
595        /** Returns random leaf of BSP tree.
596                @param halfspace defines the halfspace from which the leaf is taken.
597        */
598        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
599
600        /** Returns random leaf of BSP tree.
601                @param onlyUnmailed if only unmailed leaves should be returned.
602        */
603        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
604
605        /** Returns epsilon of this tree.
606        */
607        float GetEpsilon() const;
608
609        /** Casts line segment into the tree.
610                @param origin the origin of the line segment
611                @param termination the end point of the line segment
612                @returns view cells intersecting the line segment.
613        */
614    int CastLineSegment(const Vector3 &origin,
615                                                const Vector3 &termination,
616                                                ViewCellContainer &viewcells,
617                                                const bool useMailboxing = true);
618
619               
620        /** Sets pointer to view cells manager.
621        */
622        void SetViewCellsManager(ViewCellsManager *vcm);
623
624        /** Returns view cell the current point is located in.
625                @param point the current view point
626                @param active if currently active view cells should be returned or
627                elementary view cell
628        */
629        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
630
631
632        /** Returns true if this view point is in a valid view space,
633                false otherwise.
634        */
635        bool ViewPointValid(const Vector3 &viewPoint) const;
636
637        /** Returns view cell corresponding to
638                the invalid view space.
639        */
640        VspViewCell *GetOutOfBoundsCell();
641
642        /** Writes tree to output stream
643        */
644        bool Export(OUT_STREAM &stream);
645
646        /** Casts beam, i.e. a 5D frustum of rays, into tree.
647                Tests conservative using the bounding box of the nodes.
648                @returns number of view cells it intersected
649        */
650        int CastBeam(Beam &beam);
651
652        /** Checks if tree validity-flags are right
653                with respect to view cell valitiy.
654                If not, marks subtree as invalid.
655        */
656        void ValidateTree();
657
658        /** Invalid view cells are added to the unbounded space
659        */
660        void CollapseViewCells();
661
662        /** Collects rays stored in the leaves.
663        */
664        void CollectRays(VssRayContainer &rays);
665
666        /** Intersects box with the tree and returns the number of intersected boxes.
667                @returns number of view cells found
668        */
669        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
670                                                                ViewCellContainer &viewCells) const;
671
672        /** Returns view cells of this ray, either taking precomputed cells
673                or by recomputation.
674        */
675        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
676
677        /** Returns view cells tree.
678        */
679        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
680
681        /** Sets the view cells tree.
682        */
683        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
684
685#if WORK_WITH_VIEWCELLS
686        /** Remove the references of the parent view cell from the kd nodes associated with
687                the objects.
688        */
689        void RemoveParentViewCellReferences(ViewCell *parent) const;
690
691        /** Adds references to the view cell to the kd nodes associated with the objects.
692        */
693        void AddViewCellReferences(ViewCell *vc) const;
694#endif
695
696        VspNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
697
698protected:
699
700        // --------------------------------------------------------------
701        // For sorting objects
702        // --------------------------------------------------------------
703        struct SortableEntry
704        {
705                enum EType
706                {
707                        ERayMin,
708                        ERayMax
709                };
710
711                int type;
712                float value;
713                VssRay *ray;
714 
715                SortableEntry() {}
716                SortableEntry(const int t, const float v, VssRay *r):
717                type(t), value(v), ray(r)
718                {
719                }
720               
721                friend inline bool operator<(const SortableEntry &a, const SortableEntry &b)
722                {       // prefer max event
723                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
724                        //      return (a.type == ERayMax);
725
726                        return (a.value < b.value);
727                }
728        };
729
730        /** faster evaluation of split plane cost for kd axis aligned cells.
731        */
732        float EvalLocalSplitCost(const VspTraversalData &data,
733                                                         const AxisAlignedBox3 &box,
734                                                         const int axis,
735                                                         const float &position,
736                                                         float &pFront,
737                                                         float &pBack) const;
738
739        void ComputeBoundingBox(const VssRayContainer &rays,
740                                                        AxisAlignedBox3 *forcedBoundingBox);
741
742        /** Evaluates candidate for splitting.
743        */
744        void EvalSubdivisionCandidate(VspSubdivisionCandidate &splitData,
745                                                                  bool computeSplitPlane = true);
746
747        /** Evaluates render cost decrease of next split.
748        */
749        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
750                                                                 const VspTraversalData &data,
751                                                                 float &normalizedOldRenderCost) const;
752
753        /** Collects view cells in the subtree under root.
754        */
755        void CollectViewCells(VspNode *root,
756                                                  bool onlyValid,
757                                                  ViewCellContainer &viewCells,
758                                                  bool onlyUnmailed = false) const;
759
760        /** Returns view cell corresponding to
761                the invalid view space. If it does not exist, it is created.
762        */
763        VspViewCell *GetOrCreateOutOfBoundsCell();
764
765        /** Collapses the tree with respect to the view cell partition,
766                i.e. leaves having the same view cell are collapsed.
767                @param node the root of the subtree to be collapsed
768                @param collapsed returns the number of collapsed nodes
769                @returns node of type leaf if the node could be collapsed,
770                this node otherwise
771        */
772        VspNode *CollapseTree(VspNode *node, int &collapsed);
773
774        /** Helper function revalidating the view cell leaf list after merge.
775        */
776        void RepairViewCellsLeafLists();
777
778        /** Evaluates tree stats in the BSP tree leafs.
779        */
780        void EvaluateLeafStats(const VspTraversalData &data);
781
782        /** Subdivides node using a best split priority queue.
783            @param tQueue the best split priority queue
784                @param splitCandidate the candidate for the next split
785                @param globalCriteriaMet if the global termination criteria were already met
786                @returns new root of the subtree
787        */
788        VspNode *Subdivide(SplitQueue &tQueue,
789                                           SubdivisionCandidate *splitCandidate,
790                                           const bool globalCriteriaMet);
791
792        /** Adds stats to subdivision log file.
793        */
794        void AddSubdivisionStats(const int viewCells,
795                                                         const float renderCostDecr,
796                                                         const float totalRenderCost,
797                                                         const float avgRenderCost);
798       
799        /** Subdivides leaf.
800                       
801                @param tData data object holding, e.g., a pointer to the leaf
802                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
803                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
804               
805                @param rays the polygons to be filtered
806                @param frontRays returns the polygons in front of the split plane
807       
808                @returns the root of the subdivision
809        */
810        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
811                                                           VspTraversalData &tData,
812                                                           VspTraversalData &frontData,
813                               VspTraversalData &backData);
814
815        /** Selects an axis aligned for the next split.
816                @returns cost for this split
817        */
818        float SelectSplitPlane(const VspTraversalData &tData,
819                                                   AxisAlignedPlane &plane,
820                                                   float &pFront,
821                                                   float &pBack);
822
823        /** Sorts split candidates along the specified axis.
824                The split candidates are generated on possible visibility
825                events (i.e., where ray segments intersect the ray boundaries).
826                The sorted candidates are needed to compute the heuristics.
827
828                @param polys the input for choosing split candidates
829                @param axis the current split axis
830                @param splitCandidates returns sorted list of split candidates
831        */
832        void SortSubdivisionCandidates(const RayInfoContainer &rays,
833                                                         const int axis,
834                                                         float minBand,
835                                                         float maxBand);
836
837        /** Evaluate pvs size as induced by the samples.
838        */
839        int EvalPvsSize(const RayInfoContainer &rays) const;
840
841        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const;
842
843        /** Returns number of effective entries in the pvs.
844        */
845        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;
846        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
847        /** Computes best cost for axis aligned planes.
848        */
849        float EvalLocalCostHeuristics(const VspTraversalData &tData,
850                                                                  const AxisAlignedBox3 &box,
851                                                                  const int axis,
852                                                                  float &position);
853
854
855        //////////////////////////////////////////
856        // Helper function for computing heuristics
857
858        /** Evaluates the contribution to left and right pvs at a visibility event ve.
859                @param ve the visibility event
860                @param pvsLeft updates the left pvs
861                @param rightPvs updates the right pvs
862        */
863        void EvalHeuristics(const SortableEntry &ve, int &pvsLeft, int &pvsRight) const;
864
865        /** Evaluates contribution of min event to pvs
866        */
867        int EvalMinEventContribution(
868                const VssRay &ray, const bool isTermination) const;
869
870        /** Evaluates contribution of max event to pvs
871        */
872        int EvalMaxEventContribution(
873                const VssRay &ray, const bool isTermination) const;
874
875        /** Evaluates contribution of kd leaf when encountering a min event
876        */
877        int EvalMinEventContribution(KdLeaf *leaf) const;
878        /**  Evaluates contribution of kd leaf when encountering a max event
879        */
880        int EvalMaxEventContribution(KdLeaf *leaf) const;
881
882        /** Prepares objects for the heuristics.
883                @returns pvs size as seen by the rays.
884        */
885        int PrepareHeuristics(const RayInfoContainer &rays);
886       
887        /** Prepare a single ray for heuristics.
888        */
889        int PrepareHeuristics(const VssRay &ray, const bool isTermination);
890        /** Prepare a single kd leaf for heuristics.
891        */
892        int PrepareHeuristics(KdLeaf *leaf);
893
894       
895        /////////////////////////////////////////////////////////////////////////////
896
897
898        /** Subdivides the rays into front and back rays according to the split plane.
899               
900                @param plane the split plane
901                @param rays contains the rays to be split. The rays are
902                           distributed into front and back rays.
903                @param frontRays returns rays on the front side of the plane
904                @param backRays returns rays on the back side of the plane
905               
906                @returns the number of splits
907        */
908        int SplitRays(const AxisAlignedPlane &plane,
909                                  RayInfoContainer &rays,
910                              RayInfoContainer &frontRays,
911                                  RayInfoContainer &backRays) const;
912
913        void UpdatePvsEntriesContribution(
914                const VssRay &ray,
915                const bool isTermination,
916                const int cf,
917                float &frontPvs,
918                float &backPvs,
919                float &totalPvs) const;
920
921        /** Classfifies the object with respect to the
922                pvs of the front and back leaf and updates pvs size
923                accordingly.
924
925                @param obj the object to be added
926                @param cf the ray classification regarding the split plane
927                @param frontPvs returns the PVS of the front partition
928                @param backPvs returns the PVS of the back partition
929       
930        */
931        void UpdateContributionsToPvs(
932                const VssRay &ray,
933                const bool isTermination,
934                const int cf,
935                float &frontPvs,
936                float &backPvs,
937                float &totalPvs) const;
938
939        /** Evaluates the contribution for objects.
940        */
941        void UpdateContributionsToPvs(
942                Intersectable *obj,
943                const int cf,
944                float &frontPvs,
945                float &backPvs,
946                float &totalPvs) const;
947
948        /** Evaluates the contribution for bounding volume leaves.
949        */
950        void UpdateContributionsToPvs(
951                BvhLeaf *leaf,
952                const int cf,
953                float &frontPvs,
954                float &backPvs,
955                float &totalPvsm,
956                const bool countEntries = false) const;
957
958        /** Evaluates the contribution for kd leaves.
959        */
960        void UpdateContributionsToPvs(
961                KdLeaf *leaf,
962                const int cf,
963                float &frontPvs,
964                float &backPvs,
965                float &totalPvs) const;
966
967        /** Returns true if tree can be terminated.
968        */
969        bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
970
971        /** Returns true if global tree can be terminated.
972        */
973        bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
974
975        /** Adds ray sample contributions to the PVS.
976                @param sampleContributions the number contributions of the samples
977                @param contributingSampels the number of contributing rays
978               
979        */
980        void AddSamplesToPvs(VspLeaf *leaf,
981                                                 const RayInfoContainer &rays,
982                                                 float &sampleContributions,
983                                                 int &contributingSamples);
984
985        /** Propagates valid flag up the tree.
986        */
987        void PropagateUpValidity(VspNode *node);
988
989        /** Writes the node to disk
990                @note: should be implemented as visitor.
991        */
992        void ExportNode(VspNode *node, OUT_STREAM &stream);
993
994        /** Returns estimated memory usage of tree.
995        */
996        float GetMemUsage() const;
997
998        /** Updates view cell pvs of objects.
999        */
1000        void ProcessViewCellObjects(ViewCell *parent,
1001                                                                ViewCell *front,
1002                                                                ViewCell *back) const;
1003
1004        void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
1005
1006        /** Collect split candidates which are affected by the last split
1007                and must be reevaluated.
1008        */
1009        void CollectDirtyCandidates(VspSubdivisionCandidate *sc,
1010                                                                vector<SubdivisionCandidate *> &dirtyList,
1011                                                                const bool onlyUnmailed);
1012
1013        void CollectDirtyCandidate(const VssRay &ray,
1014                                                           const bool isTermination,
1015                                                           vector<SubdivisionCandidate *> &dirtyList,
1016                                                           const bool onlyUnmailed) const;
1017
1018        /** Rays will be clipped to the bounding box.
1019        */
1020        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
1021
1022        /** Evaluate subdivision statistics.
1023        */
1024        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
1025
1026        SubdivisionCandidate *PrepareConstruction(
1027                const VssRayContainer &sampleRays,
1028                RayInfoContainer &rays);
1029
1030        /** Evaluates pvs contribution of this ray.
1031        */
1032        int EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
1033
1034        /** Evaluates pvs contribution of a kd node.
1035        */
1036        int EvalContributionToPvs(KdLeaf *leaf) const;
1037
1038        /** Creates new root of hierarchy and computes bounding box.
1039                Has to be called before the preparation of the subdivision.
1040        */
1041        void Initialise(const VssRayContainer &rays,
1042                                        AxisAlignedBox3 *forcedBoundingBox);
1043
1044protected:
1045
1046        /// pointer to the hierarchy of view cells
1047        ViewCellsTree *mViewCellsTree;
1048
1049        HierarchyManager *mHierarchyManager;
1050        //OspTree *mOspTree;
1051        //bool mUseKdPvsForHeuristics;
1052       
1053        ViewCellsManager *mViewCellsManager;
1054       
1055        vector<SortableEntry> *mLocalSubdivisionCandidates;
1056
1057        /// Pointer to the root of the tree
1058        VspNode *mRoot;
1059               
1060        VspTreeStatistics mVspStats;
1061       
1062        /// View cell corresponding to the space outside the valid view space
1063        VspViewCell *mOutOfBoundsCell;
1064
1065        /// box around the whole view domain
1066        AxisAlignedBox3 mBoundingBox;
1067
1068
1069        //-- local termination
1070
1071        /// minimal number of rays before subdivision termination
1072        int mTermMinRays;
1073        /// maximal possible depth
1074        int mTermMaxDepth;
1075        /// mininum probability
1076        float mTermMinProbability;
1077        /// mininum PVS
1078        int mTermMinPvs;
1079        /// maximal contribution per ray
1080        float mTermMaxRayContribution;
1081        /// maximal acceptable cost ratio
1082        float mTermMaxCostRatio;
1083        /// tolerance value indicating how often the max cost ratio can be failed
1084        int mTermMissTolerance;
1085
1086
1087        //-- global criteria
1088        float mTermMinGlobalCostRatio;
1089        int mTermGlobalCostMissTolerance;
1090       
1091
1092        /// maximal number of view cells
1093        int mMaxViewCells;
1094        /// maximal tree memory
1095        float mMaxMemory;
1096        /// the tree is out of memory
1097        bool mOutOfMemory;
1098
1099        ////////////
1100        //-- split heuristics based parameters
1101       
1102        bool mUseCostHeuristics;
1103        /// balancing factor for PVS criterium
1104        float mCtDivCi;
1105        /// if only driving axis should be used for split
1106        bool mOnlyDrivingAxis;
1107        /// if random split axis should be used
1108        bool mUseRandomAxis;
1109        /// if vsp bsp tree should simulate octree
1110        bool mCirculatingAxis;
1111        /// minimal relative position where the split axis can be placed
1112        float mMinBand;
1113        /// maximal relative position where the split axis can be placed
1114        float mMaxBand;
1115
1116
1117        /// current time stamp (used for keeping split history)
1118        int mTimeStamp;
1119        // if rays should be stored in leaves
1120        bool mStoreRays;
1121
1122        /// epsilon for geometric comparisons
1123        float mEpsilon;
1124
1125        /// subdivision stats output file
1126        ofstream  mSubdivisionStats;
1127        /// keeps track of cost during subdivision
1128        float mTotalCost;
1129        int mPvsEntries;
1130        /// keeps track of overall pvs size during subdivision
1131        int mTotalPvsSize;
1132        /// number of currenly generated view cells
1133        int mCreatedViewCells;
1134
1135        /// weight between render cost decrease and node render cost
1136        float mRenderCostDecreaseWeight;
1137
1138        int mMaxTests;
1139};
1140
1141
1142}
1143
1144#endif
Note: See TracBrowser for help on using the repository browser.