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

Revision 2237, 29.8 KB checked in by mattausch, 18 years ago (diff)

worked on optimization. warning: not tested yet

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