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

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