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

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