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

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