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

Revision 1686, 28.5 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
695        VspNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);
696
697protected:
698
699        // --------------------------------------------------------------
700        // For sorting objects
701        // --------------------------------------------------------------
702        struct SortableEntry
703        {
704                enum EType
705                {
706                        ERayMin,
707                        ERayMax
708                };
709
710                int type;
711                float value;
712                VssRay *ray;
713 
714                SortableEntry() {}
715                SortableEntry(const int t, const float v, VssRay *r):
716                type(t), value(v), ray(r)
717                {
718                }
719               
720                friend inline bool operator<(const SortableEntry &a, const SortableEntry &b)
721                {       // prefer max event
722                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
723                        //      return (a.type == ERayMax);
724
725                        return (a.value < b.value);
726                }
727        };
728
729        /** faster evaluation of split plane cost for kd axis aligned cells.
730        */
731        float EvalLocalSplitCost(const VspTraversalData &data,
732                                                         const AxisAlignedBox3 &box,
733                                                         const int axis,
734                                                         const float &position,
735                                                         float &pFront,
736                                                         float &pBack) const;
737
738        void ComputeBoundingBox(const VssRayContainer &rays,
739                                                        AxisAlignedBox3 *forcedBoundingBox);
740
741        /** Evaluates candidate for splitting.
742        */
743        void EvalSubdivisionCandidate(VspSubdivisionCandidate &splitData,
744                                                                  bool computeSplitPlane = true);
745
746        /** Evaluates render cost decrease of next split.
747        */
748        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
749                                                                 const VspTraversalData &data,
750                                                                 float &normalizedOldRenderCost) const;
751
752        /** Collects view cells in the subtree under root.
753        */
754        void CollectViewCells(VspNode *root,
755                                                  bool onlyValid,
756                                                  ViewCellContainer &viewCells,
757                                                  bool onlyUnmailed = false) const;
758
759        /** Returns view cell corresponding to
760                the invalid view space. If it does not exist, it is created.
761        */
762        VspViewCell *GetOrCreateOutOfBoundsCell();
763
764        /** Collapses the tree with respect to the view cell partition,
765                i.e. leaves having the same view cell are collapsed.
766                @param node the root of the subtree to be collapsed
767                @param collapsed returns the number of collapsed nodes
768                @returns node of type leaf if the node could be collapsed,
769                this node otherwise
770        */
771        VspNode *CollapseTree(VspNode *node, int &collapsed);
772
773        /** Helper function revalidating the view cell leaf list after merge.
774        */
775        void RepairViewCellsLeafLists();
776
777        /** Evaluates tree stats in the BSP tree leafs.
778        */
779        void EvaluateLeafStats(const VspTraversalData &data);
780
781        /** Subdivides node using a best split priority queue.
782            @param tQueue the best split priority queue
783                @param splitCandidate the candidate for the next split
784                @param globalCriteriaMet if the global termination criteria were already met
785                @returns new root of the subtree
786        */
787        VspNode *Subdivide(SplitQueue &tQueue,
788                                           SubdivisionCandidate *splitCandidate,
789                                           const bool globalCriteriaMet);
790
791        /** Adds stats to subdivision log file.
792        */
793        void AddSubdivisionStats(const int viewCells,
794                                                         const float renderCostDecr,
795                                                         const float totalRenderCost,
796                                                         const float avgRenderCost);
797       
798        /** Subdivides leaf.
799                       
800                @param tData data object holding, e.g., a pointer to the leaf
801                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
802                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
803               
804                @param rays the polygons to be filtered
805                @param frontRays returns the polygons in front of the split plane
806       
807                @returns the root of the subdivision
808        */
809        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
810                                                           VspTraversalData &tData,
811                                                           VspTraversalData &frontData,
812                               VspTraversalData &backData);
813
814        /** Selects an axis aligned for the next split.
815                @returns cost for this split
816        */
817        float SelectSplitPlane(const VspTraversalData &tData,
818                                                   AxisAlignedPlane &plane,
819                                                   float &pFront,
820                                                   float &pBack);
821
822        /** Sorts split candidates along the specified axis.
823                The split candidates are generated on possible visibility
824                events (i.e., where ray segments intersect the ray boundaries).
825                The sorted candidates are needed to compute the heuristics.
826
827                @param polys the input for choosing split candidates
828                @param axis the current split axis
829                @param splitCandidates returns sorted list of split candidates
830        */
831        void SortSubdivisionCandidates(const RayInfoContainer &rays,
832                                                         const int axis,
833                                                         float minBand,
834                                                         float maxBand);
835
836        /** Evaluate pvs size as induced by the samples.
837        */
838        int EvalPvsSize(const RayInfoContainer &rays) const;
839
840        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate) const;
841
842        /** Returns number of effective entries in the pvs.
843        */
844        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;
845        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
846        /** Computes best cost for axis aligned planes.
847        */
848        float EvalLocalCostHeuristics(const VspTraversalData &tData,
849                                                                  const AxisAlignedBox3 &box,
850                                                                  const int axis,
851                                                                  float &position);
852
853
854        //////////////////////////////////////////
855        // Helper function for computing heuristics
856
857        /** Evaluates the contribution to left and right pvs at a visibility event ve.
858                @param ve the visibility event
859                @param pvsLeft updates the left pvs
860                @param rightPvs updates the right pvs
861        */
862        void EvalHeuristics(const SortableEntry &ve, int &pvsLeft, int &pvsRight) const;
863
864        /** Evaluates contribution of min event to pvs
865        */
866        int EvalMinEventContribution(
867                const VssRay &ray, const bool isTermination) const;
868
869        /** Evaluates contribution of max event to pvs
870        */
871        int EvalMaxEventContribution(
872                const VssRay &ray, const bool isTermination) const;
873
874        /** Evaluates contribution of kd leaf when encountering a min event
875        */
876        int EvalMinEventContribution(KdLeaf *leaf) const;
877        /**  Evaluates contribution of kd leaf when encountering a max event
878        */
879        int EvalMaxEventContribution(KdLeaf *leaf) const;
880
881        /** Prepares objects for the heuristics.
882                @returns pvs size as seen by the rays.
883        */
884        int PrepareHeuristics(const RayInfoContainer &rays);
885       
886        /** Prepare a single ray for heuristics.
887        */
888        int PrepareHeuristics(const VssRay &ray, const bool isTermination);
889        /** Prepare a single kd leaf for heuristics.
890        */
891        int PrepareHeuristics(KdLeaf *leaf);
892
893       
894        /////////////////////////////////////////////////////////////////////////////
895
896
897        /** Subdivides the rays into front and back rays according to the split plane.
898               
899                @param plane the split plane
900                @param rays contains the rays to be split. The rays are
901                           distributed into front and back rays.
902                @param frontRays returns rays on the front side of the plane
903                @param backRays returns rays on the back side of the plane
904               
905                @returns the number of splits
906        */
907        int SplitRays(const AxisAlignedPlane &plane,
908                                  RayInfoContainer &rays,
909                              RayInfoContainer &frontRays,
910                                  RayInfoContainer &backRays) const;
911
912        void UpdatePvsEntriesContribution(
913                const VssRay &ray,
914                const bool isTermination,
915                const int cf,
916                float &frontPvs,
917                float &backPvs,
918                float &totalPvs) const;
919
920        /** Classfifies the object with respect to the
921                pvs of the front and back leaf and updates pvs size
922                accordingly.
923
924                @param obj the object to be added
925                @param cf the ray classification regarding the split plane
926                @param frontPvs returns the PVS of the front partition
927                @param backPvs returns the PVS of the back partition
928       
929        */
930        void UpdateContributionsToPvs(
931                const VssRay &ray,
932                const bool isTermination,
933                const int cf,
934                float &frontPvs,
935                float &backPvs,
936                float &totalPvs) const;
937
938        /** Evaluates the contribution for objects.
939        */
940        void UpdateContributionsToPvs(
941                Intersectable *obj,
942                const int cf,
943                float &frontPvs,
944                float &backPvs,
945                float &totalPvs) const;
946
947        /** Evaluates the contribution for bounding volume leaves.
948        */
949        void UpdateContributionsToPvs(
950                BvhLeaf *leaf,
951                const int cf,
952                float &frontPvs,
953                float &backPvs,
954                float &totalPvsm,
955                const bool countEntries = false) const;
956
957        /** Evaluates the contribution for kd leaves.
958        */
959        void UpdateContributionsToPvs(
960                KdLeaf *leaf,
961                const int cf,
962                float &frontPvs,
963                float &backPvs,
964                float &totalPvs) const;
965
966        /** Returns true if tree can be terminated.
967        */
968        bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
969
970        /** Returns true if global tree can be terminated.
971        */
972        bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
973
974        /** Adds ray sample contributions to the PVS.
975                @param sampleContributions the number contributions of the samples
976                @param contributingSampels the number of contributing rays
977               
978        */
979        void AddSamplesToPvs(VspLeaf *leaf,
980                                                 const RayInfoContainer &rays,
981                                                 float &sampleContributions,
982                                                 int &contributingSamples);
983
984        /** Propagates valid flag up the tree.
985        */
986        void PropagateUpValidity(VspNode *node);
987
988        /** Writes the node to disk
989                @note: should be implemented as visitor.
990        */
991        void ExportNode(VspNode *node, OUT_STREAM &stream);
992
993        /** Returns estimated memory usage of tree.
994        */
995        float GetMemUsage() const;
996
997        /** Updates view cell pvs of objects.
998        */
999        void ProcessViewCellObjects(ViewCell *parent,
1000                                                                ViewCell *front,
1001                                                                ViewCell *back) const;
1002
1003        void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
1004
1005        /** Collect split candidates which are affected by the last split
1006                and must be reevaluated.
1007        */
1008        void CollectDirtyCandidates(VspSubdivisionCandidate *sc,
1009                                                                vector<SubdivisionCandidate *> &dirtyList,
1010                                                                const bool onlyUnmailed);
1011
1012        void CollectDirtyCandidate(const VssRay &ray,
1013                                                           const bool isTermination,
1014                                                           vector<SubdivisionCandidate *> &dirtyList,
1015                                                           const bool onlyUnmailed) const;
1016
1017        /** Rays will be clipped to the bounding box.
1018        */
1019        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
1020
1021        /** Evaluate subdivision statistics.
1022        */
1023        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
1024
1025        SubdivisionCandidate *PrepareConstruction(
1026                const VssRayContainer &sampleRays,
1027                RayInfoContainer &rays);
1028
1029        /** Evaluates pvs contribution of this ray.
1030        */
1031        int EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
1032
1033        /** Evaluates pvs contribution of a kd node.
1034        */
1035        int EvalContributionToPvs(KdLeaf *leaf) const;
1036
1037        /** Creates new root of hierarchy and computes bounding box.
1038                Has to be called before the preparation of the subdivision.
1039        */
1040        void Initialise(const VssRayContainer &rays,
1041                                        AxisAlignedBox3 *forcedBoundingBox);
1042
1043protected:
1044
1045        /// pointer to the hierarchy of view cells
1046        ViewCellsTree *mViewCellsTree;
1047
1048        HierarchyManager *mHierarchyManager;
1049        //OspTree *mOspTree;
1050        //bool mUseKdPvsForHeuristics;
1051       
1052        ViewCellsManager *mViewCellsManager;
1053       
1054        vector<SortableEntry> *mLocalSubdivisionCandidates;
1055
1056        /// Pointer to the root of the tree
1057        VspNode *mRoot;
1058               
1059        VspTreeStatistics mVspStats;
1060       
1061        /// View cell corresponding to the space outside the valid view space
1062        VspViewCell *mOutOfBoundsCell;
1063
1064        /// box around the whole view domain
1065        AxisAlignedBox3 mBoundingBox;
1066
1067
1068        //-- local termination
1069
1070        /// minimal number of rays before subdivision termination
1071        int mTermMinRays;
1072        /// maximal possible depth
1073        int mTermMaxDepth;
1074        /// mininum probability
1075        float mTermMinProbability;
1076        /// mininum PVS
1077        int mTermMinPvs;
1078        /// maximal contribution per ray
1079        float mTermMaxRayContribution;
1080        /// maximal acceptable cost ratio
1081        float mTermMaxCostRatio;
1082        /// tolerance value indicating how often the max cost ratio can be failed
1083        int mTermMissTolerance;
1084
1085
1086        //-- global criteria
1087        float mTermMinGlobalCostRatio;
1088        int mTermGlobalCostMissTolerance;
1089       
1090
1091        /// maximal number of view cells
1092        int mMaxViewCells;
1093        /// maximal tree memory
1094        float mMaxMemory;
1095        /// the tree is out of memory
1096        bool mOutOfMemory;
1097
1098        ////////////
1099        //-- split heuristics based parameters
1100       
1101        bool mUseCostHeuristics;
1102        /// balancing factor for PVS criterium
1103        float mCtDivCi;
1104        /// if only driving axis should be used for split
1105        bool mOnlyDrivingAxis;
1106        /// if random split axis should be used
1107        bool mUseRandomAxis;
1108        /// if vsp bsp tree should simulate octree
1109        bool mCirculatingAxis;
1110        /// minimal relative position where the split axis can be placed
1111        float mMinBand;
1112        /// maximal relative position where the split axis can be placed
1113        float mMaxBand;
1114
1115
1116        /// current time stamp (used for keeping split history)
1117        int mTimeStamp;
1118        // if rays should be stored in leaves
1119        bool mStoreRays;
1120
1121        /// epsilon for geometric comparisons
1122        float mEpsilon;
1123
1124        /// subdivision stats output file
1125        ofstream  mSubdivisionStats;
1126        /// keeps track of cost during subdivision
1127        float mTotalCost;
1128        int mPvsEntries;
1129        /// keeps track of overall pvs size during subdivision
1130        int mTotalPvsSize;
1131        /// number of currenly generated view cells
1132        int mCreatedViewCells;
1133
1134        /// weight between render cost decrease and node render cost
1135        float mRenderCostDecreaseWeight;
1136
1137        int mMaxTests;
1138};
1139
1140
1141}
1142
1143#endif
Note: See TracBrowser for help on using the repository browser.