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

Revision 2588, 31.2 KB checked in by bittner, 17 years ago (diff)

sceneBox bugfix

Line 
1#ifndef _VspTree_H__
2#define _VspTree_H__
3
4#include <stack>
5
6#include "Mesh.h"
7#include "Containers.h"
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "gzstream.h"
12#include "SubdivisionCandidate.h"
13#include "HierarchyManager.h"
14#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;
356
357public:
358       
359        ///////////
360        //-- Helper structs / classes
361
362        /** Additional data which is passed down the BSP tree during traversal.
363        */
364        struct VspTraversalData
365        { 
366        public:
367               
368                VspTraversalData();
369               
370                VspTraversalData(VspLeaf *node,
371                                                 const int depth,
372                                                 RayInfoContainer *rays,
373                                                 const float pvs,
374                                                 const float p,
375                                                 const AxisAlignedBox3 &box);
376
377       
378                /** Returns cost of the traversal data.
379                */
380                inline float GetCost() const;
381                /** Returns average ray contribution.
382                */
383                inline float GetAvgRayContribution() const;
384                /** Returns average rays per object.
385                */
386                inline float GetAvgRaysPerObject() const;
387                /** deletes contents and sets them to NULL.
388                */
389                void Clear();
390
391
392                //////////////////////
393
394                /// the current node
395                VspLeaf *mNode;
396                /// current depth
397                int mDepth;
398                /// rays piercing this node
399                RayInfoContainer *mRays;
400                /// the probability that this node contains view point
401                float mProbability;
402                /// the bounding box of the node
403                AxisAlignedBox3 mBoundingBox;
404                /// how often this branch has missed the max-cost ratio
405                int mMaxCostMisses;
406                // current priority
407                float mPriority;
408                /// pvs size
409                float mPvs;
410                /// the correction factor for this pvs
411                float mCorrectedPvs;
412                /// pvs size
413                float mRenderCost;
414                /// the correction factor for this pvs
415                float mCorrectedRenderCost;
416
417                friend bool operator<(const VspTraversalData &a, const VspTraversalData &b)
418                {
419                        return a.GetCost() < b.GetCost();
420                }
421    };
422
423        /** Helper struct for data that comes with a split of a node.
424        */
425        struct SplitData
426        {
427                SplitData():
428        mFrontRenderCost(0),
429                mBackRenderCost(0),
430                mTotalRenderCost(0),
431                mFrontObjects(0),
432        mBackObjects(0),
433                mTotalObjects(0),
434                mFrontTriangles(0),
435                mBackTriangles(0),
436                mTotalTriangles(0)
437                {}
438
439                //////////////
440
441                float mFrontRenderCost;
442                float mBackRenderCost;
443                float mTotalRenderCost;
444
445                int mFrontObjects;
446                int mBackObjects;
447                int mTotalObjects;
448
449                int mFrontTriangles;
450                int mBackTriangles;
451                int mTotalTriangles;
452        };
453
454
455        /** Candidate for a view space split.
456        */
457        class VspSubdivisionCandidate: public SubdivisionCandidate
458        { 
459        public:
460
461                VspSubdivisionCandidate(const VspTraversalData &tData): mParentData(tData)
462                {};
463
464                ~VspSubdivisionCandidate()
465                {
466                        mParentData.Clear();
467                }
468
469                int Type() const { return VIEW_SPACE; }
470
471                void EvalCandidate(bool computeSplitplane = true)
472                {
473                        mDirty = false;
474                        sVspTree->EvalSubdivisionCandidate(*this, computeSplitplane);
475                }
476
477                bool GlobalTerminationCriteriaMet() const
478                {
479                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
480                }
481
482                bool Apply(SplitQueue &splitQueue,
483                                   bool terminationCriteriaMet,
484                                   SubdivisionCandidateContainer &dirtyList)
485                {
486                        VspNode *n = sVspTree->Subdivide(splitQueue, this, terminationCriteriaMet);
487                       
488                        // local or global termination criteria failed
489                        const bool success = !n->IsLeaf();     
490
491                        if (success)
492                                CollectDirtyCandidates(dirtyList, true);
493
494                        return success;
495                }
496
497                void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
498                                                                        const bool onlyUnmailed)
499                {
500                        sVspTree->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
501                }
502
503                VspSubdivisionCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):
504                        mSplitPlane(plane), mParentData(tData)
505                {}
506
507                float GetPriority() const {     return mPriority; }
508
509
510                ////////////////////
511
512                static VspTree* sVspTree;
513                /// the current split plane
514                AxisAlignedPlane mSplitPlane;
515                /// parent node traversal data
516                VspTraversalData mParentData;
517       
518                float mCorrectedFrontPvs;
519                float mCorrectedBackPvs;
520
521                float mFrontPvs;
522                float mBackPvs;
523
524                float mFrontTriangles;
525                float mBackTriangles;
526               
527                float mCorrectedFrontRenderCost;
528                float mCorrectedBackRenderCost;
529               
530                float mFrontRenderCost;
531                float mBackRenderCost;
532        };
533
534        /** Struct for traversing line segment.
535        */
536        struct LineTraversalData
537        {
538                VspNode *mNode;
539                Vector3 mExitPoint;
540                float mMaxT;
541   
542                LineTraversalData () {}
543                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
544                mNode(n), mExitPoint(p), mMaxT(maxt) {}
545        };
546
547
548        //////////////////////
549
550
551        /** Default constructor creating an empty tree.
552        */
553        VspTree();
554        /** Constructor just setting the bounds of the tree.
555        */
556        VspTree(const AxisAlignedBox3 &bbox);
557        /** Default destructor.
558        */
559        ~VspTree();
560        /** Returns BSP Tree statistics.
561        */
562        const VspTreeStatistics &GetStatistics() const;
563        /** Returns bounding box of the specified node.
564        */
565        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
566        /** Returns list of BSP leaves with pvs smaller than
567                a certain threshold.
568                @param onlyUnmailed if only the unmailed leaves should be considered
569                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
570        */
571        void CollectLeaves(vector<VspLeaf *> &leaves,
572                                           const bool onlyUnmailed = false,
573                                           const int maxPvs = -1) const;
574        /** Returns box which bounds the whole tree.
575        */
576        AxisAlignedBox3 GetBoundingBox() const;
577        /** Returns root of the view space partitioning tree.
578        */
579        VspNode *GetRoot() const;
580        /** Collects the leaf view cells of the tree
581                @param viewCells returns the view cells
582        */
583        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
584        /** A ray is cast possible intersecting the tree.
585                @param the ray that is cast.
586                @returns the number of intersections with objects stored in the tree.
587        */
588        int CastRay(Ray &ray);
589        /** finds neighbouring leaves of this tree node.
590        */
591        int FindNeighbors(VspLeaf *n,
592                                          vector<VspLeaf *> &neighbors,
593                                          const bool onlyUnmailed) const;
594        /** Returns random leaf of BSP tree.
595                @param halfspace defines the halfspace from which the leaf is taken.
596        */
597        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
598
599        /** Returns random leaf of BSP tree.
600                @param onlyUnmailed if only unmailed leaves should be returned.
601        */
602        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
603        /** Returns epsilon of this tree.
604        */
605        float GetEpsilon() const;
606        /** Casts line segment into the tree.
607                @param origin the origin of the line segment
608                @param termination the end point of the line segment
609                @returns view cells intersecting the line segment.
610        */
611    int CastLineSegment(const Vector3 &origin,
612                                                const Vector3 &termination,
613                                                ViewCellContainer &viewcells,
614                                                const bool useMailboxing = true);
615        /** Sets pointer to view cells manager.
616        */
617        void SetViewCellsManager(ViewCellsManager *vcm);
618        /** Returns view cell the current point is located in.
619                @param point the current view point
620                @param active if currently active view cells should be returned or
621                elementary view cell
622        */
623        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
624        /** Returns true if this view point is in a valid view space,
625                false otherwise.
626        */
627        bool ViewPointValid(const Vector3 &viewPoint) const;
628        /** Returns view cell corresponding to
629                the invalid view space.
630        */
631        VspViewCell *GetOutOfBoundsCell();
632        /** Casts beam, i.e. a 5D frustum of rays, into tree.
633                Tests conservative using the bounding box of the nodes.
634                @returns number of view cells it intersected
635        */
636        int CastBeam(Beam &beam);
637        /** Checks if tree validity-flags are right
638                with respect to view cell valitiy.
639                If not, marks subtree as invalid.
640        */
641        void ValidateTree();
642        /** Collects rays stored in the leaves.
643        */
644        void CollectRays(VssRayContainer &rays);
645        /** Intersects box with the tree and returns the number of intersected boxes.
646                @returns number of view cells found
647        */
648        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
649                                                                ViewCellContainer &viewCells) const;
650        /** Returns view cells of this ray, either taking precomputed cells
651                or by recomputation.
652        */
653        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
654        /** Returns view cells tree.
655        */
656        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
657        /** Sets the view cells tree.
658        */
659        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
660        /** Writes vsp tree to output stream
661        */
662        bool Export(OUT_STREAM &stream);
663        /** Writes vsp tree to binary output stream.
664        */
665        bool ExportBinary(OUT_STREAM &stream);
666        /** Imports tree from binary format.
667        */
668        bool ImportBinary(IN_STREAM &stream);
669
670        void TestOutput(const std::string &filename);
671
672        ////////////
673
674#ifdef USE_PERFTIMER 
675        PerfTimer mSortTimer;
676        PerfTimer mSplitTimer;
677        PerfTimer mNodeTimer;
678        PerfTimer mSubdivTimer;
679        PerfTimer mEvalTimer;
680        PerfTimer mPlaneTimer;
681        PerfTimer mViewCellsTimer;
682#endif
683 
684protected:
685
686        // --------------------------------------------------------------
687        // For sorting objects
688        // --------------------------------------------------------------
689        struct SortableEntry
690        {
691                enum EType
692                {
693                        ERayMin,
694                        ERayMax
695                };
696
697                int type;
698                float value;
699                VssRay *ray;
700 
701                SortableEntry() {}
702                SortableEntry(const int t, const float v, VssRay *r):
703                type(t), value(v), ray(r)
704                {
705                }
706               
707                friend inline bool operator<(const SortableEntry &a, const SortableEntry &b)
708                {       // prefer max event
709                        //if (EpsilonEqual(a.value, b.value, 0.0001f))
710                        //      return (a.type == ERayMax);
711
712                        return (a.value < b.value);
713                }
714        };
715        /** Parse the environment settings.
716        */
717        void ParseEnvironment();
718        /** faster evaluation of split plane cost for kd axis aligned cells.
719        */
720        float EvalLocalSplitCost(const VspTraversalData &data,
721                                                         const AxisAlignedBox3 &box,
722                                                         const int axis,
723                                                         const float &position,
724                                                         float &pFront,
725                                                         float &pBack) const;
726        /** If != NULL, sets the bounding box to the forced  bounding box.
727                Else computes the bounding box of the view space using the
728                hit points gathered from the ray-object intersections.
729        */
730        void ComputeBoundingBox(const VssRayContainer &rays,
731                                                        AxisAlignedBox3 *forcedBoundingBox);
732        /** Evaluates candidate for splitting.
733        */
734        void EvalSubdivisionCandidate(VspSubdivisionCandidate &candidate,
735                                                                  bool computeSplitPlane = true);
736        /** Evaluates render cost decrease of next split.
737        */
738        float EvalRenderCostDecrease(VspSubdivisionCandidate &candidate,
739                                                                 float &normalizedOldRenderCost,
740                                                                 const SplitData &data) const;
741        /** Collects view cells in the subtree under root.
742        */
743        void CollectViewCells(VspNode *root,
744                                                  bool onlyValid,
745                                                  ViewCellContainer &viewCells,
746                                                  bool onlyUnmailed = false) const;
747        /** Returns view cell corresponding to
748                the invalid view space. If it does not exist, it is created.
749        */
750        VspViewCell *GetOrCreateOutOfBoundsCell();
751        /** Collapses the tree with respect to the view cell partition,
752                i.e. leaves having the same view cell are collapsed.
753                @param node the root of the subtree to be collapsed
754                @param collapsed returns the number of collapsed nodes
755                @returns node of type leaf if the node could be collapsed,
756                this node otherwise
757        */
758        VspNode *CollapseTree(VspNode *node, int &collapsed);
759        /** Helper function revalidating the view cell leaf list after merge.
760        */
761        void RepairViewCellsLeafLists();
762        /** Evaluates tree stats in the BSP tree leafs.
763        */
764        void EvaluateLeafStats(const VspTraversalData &data);
765        /** Subdivides node using a best split priority queue.
766            @param tQueue the best split priority queue
767                @param splitCandidate the candidate for the next split
768                @param globalCriteriaMet if the global termination criteria were already met
769                @returns new root of the subtree
770        */
771        VspNode *Subdivide(SplitQueue &tQueue,
772                                           SubdivisionCandidate *splitCandidate,
773                                           const bool globalCriteriaMet);
774        /** Adds stats to subdivision log file.
775        */
776        void AddSubdivisionStats(const int viewCells,
777                                                         const float renderCostDecr,
778                                                         const float totalRenderCost,
779                                                         const float avgRenderCost);
780        /** Subdivides leaf.
781                @param tData data object holding, e.g., a pointer to the leaf
782                @param frontData returns the data (e.g., pointer to the leaf) in front of the split plane
783                @param backData returns the data (e.g., pointer to the leaf) in the back of the split plane
784       
785                @returns the root of the subdivision
786        */
787        VspInterior *SubdivideNode(const VspSubdivisionCandidate &sc,
788                                                           VspTraversalData &frontData,
789                               VspTraversalData &backData);
790
791        /** Selects an axis aligned for the next split.
792                @returns cost for this split
793        */
794        float SelectSplitPlane(const VspTraversalData &tData,
795                                                   AxisAlignedPlane &plane,
796                                                   float &pFront,
797                                                   float &pBack);
798        /** Sorts split candidates along the specified axis.
799                The split candidates are generated on possible visibility
800                events (i.e., where ray segments intersect the ray boundaries).
801                The sorted candidates are needed to compute the heuristics.
802
803                @param polys the input for choosing split candidates
804                @param axis the current split axis
805                @param splitCandidates returns sorted list of split candidates
806        */
807        void SortSubdivisionCandidates(const RayInfoContainer &rays,
808                                                                   const int axis,
809                                                                   float minBand,
810                                                                   float maxBand);
811        /** Evaluate render cost of this pvs.
812        */
813        float EvalPvsCost(const RayInfoContainer &rays) const;
814        /** Helper function for split cost evaluation.
815        */
816        int EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate,
817                                                   const SplitData &sData) const;
818        /** Returns number of effective entries in the pvs.
819        */
820        int EvalPvsEntriesSize(const RayInfoContainer &rays) const;
821
822        int EvalPvsEntriesContribution(const VssRay &ray, const bool isTermination) const;
823        /** Computes best cost for axis aligned planes.
824        */
825        float EvalLocalCostHeuristics(const VspTraversalData &tData,
826                                                                  const AxisAlignedBox3 &box,
827                                                                  const int axis,
828                                                                  float &position,
829                                                                  const RayInfoContainer &usedRays);
830
831
832        ///////////////////////
833        //-- Helper function for computing heuristics
834
835        /** Evaluates the contribution to left and right pvs at a visibility event ve.
836                @param ve the visibility event
837                @param pvsLeft updates the left pvs
838                @param rightPvs updates the right pvs
839        */
840        inline void EvalHeuristics(const SortableEntry &ve, float &pvsLeft, float &pvsRight) const;
841        /** Evaluates contribution of min event to pvs
842        */
843        inline float EvalMinEventContribution(const VssRay &ray, const bool isTermination) const;
844        /** Evaluates contribution of max event to pvs
845        */
846        inline float EvalMaxEventContribution(const VssRay &ray, const bool isTermination) const;
847        /** Evaluates contribution of kd leaf when encountering a min event
848        */
849        inline float EvalMinEventContribution(KdLeaf *leaf) const;
850        /**  Evaluates contribution of kd leaf when encountering a max event
851        */
852        inline float EvalMaxEventContribution(KdLeaf *leaf) const;
853        /** Prepares objects for the heuristics.
854                @returns pvs size as seen by the rays.
855        */
856        float PrepareHeuristics(const RayInfoContainer &rays);
857        /** Prepare a single ray for heuristics.
858        */
859        float PrepareHeuristics(const VssRay &ray, const bool isTermination);
860        /** Prepare a single kd leaf for heuristics.
861        */
862        float PrepareHeuristics(KdLeaf *leaf);
863        /** Evaluates minimal and maximal depth in the tree.
864        */
865        void EvalMinMaxDepth(int &minDepth, int &maxDepth);
866        /** Writes the node to disk
867                @note: should be implemented as visitor.
868        */
869        void ExportNode(VspNode *node, OUT_STREAM &stream);
870       
871
872        ////////////////
873
874        void ExportBinInterior(OUT_STREAM &stream, VspInterior *interior);
875        void ExportBinLeaf(OUT_STREAM &stream, VspLeaf *leaf);
876
877        VspInterior *ImportBinInterior(IN_STREAM  &stream, VspInterior *parent);
878        VspLeaf *ImportBinLeaf(IN_STREAM &stream, VspInterior *parent);
879
880        VspNode *ImportNextNode(IN_STREAM &stream,
881                                                        VspInterior *parent);
882
883
884        //////////////////////////////////////////////////
885
886        /** Subdivides the rays into front and back rays according to the split plane.
887                @param plane the split plane
888                @param rays contains the rays to be split. The rays are
889                           distributed into front and back rays.
890                @param frontRays returns rays on the front side of the plane
891                @param backRays returns rays on the back side of the plane
892               
893                @returns the number of splits
894        */
895        int SplitRays(const AxisAlignedPlane &plane,
896                                  RayInfoContainer &rays,
897                              RayInfoContainer &frontRays,
898                                  RayInfoContainer &backRays) const;
899        /** Add contributions of this ray to fron, back, and overall pvs of the parent.
900        */
901        inline void UpdatePvsEntriesContribution(const VssRay &ray,
902                                                                                         const bool isTermination,
903                                                                                         const int cf,
904                                                                                         float &frontPvs,
905                                                                                         float &backPvs,
906                                                                                         float &totalPvs) const;
907        /** Classfifies the object with respect to the
908                pvs of the front and back leaf and updates pvs size
909                accordingly.
910
911                @param obj the object to be added
912                @param cf the ray classification regarding the split plane
913                @param frontPvs returns the PVS of the front partition
914                @param backPvs returns the PVS of the back partition
915       
916        */
917        inline void UpdateContributionsToPvs(const VssRay &ray,
918                                                                                 const bool isTermination,
919                                                                                 const int cf,
920                                                                                 float &frontPvs,
921                                                                                 float &backPvs,
922                                                                                 float &totalPvs) const;
923        /** Evaluates the contribution for objects.
924        */
925        inline void UpdateContributionsToPvs(Intersectable *obj,
926                                                                                 const int cf,
927                                                                                 float &frontPvs,
928                                                                                 float &backPvs,
929                                                                                 float &totalPvs) const;
930        /** Evaluates the contribution for bounding volume leaves.
931        */
932        inline void UpdateContributionsToPvs(BvhLeaf *leaf,
933                                                                                 const int cf,
934                                                                                 float &frontPvs,
935                                                                                 float &backPvs,
936                                                                                 float &totalPvs,
937                                                                                 const bool countEntries) const;
938        /** Updates contribution to pvs caused by this bvh leaf.
939        */
940        inline void UpdateContributionsToPvs(BvhLeaf *leaf,
941                                                                                 const int cf,
942                                                                                 SplitData &sdata) const;
943        /** Evaluates the contribution for kd leaves.
944        */
945        inline void UpdateContributionsToPvs(KdLeaf *leaf,
946                                                                                 const int cf,
947                                                                                 float &frontPvs,
948                                                                                 float &backPvs,
949                                                                                 float &totalPvs) const;
950        /** Returns true if tree can be terminated.
951        */
952        inline bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
953        /** Returns true if global tree can be terminated.
954        */
955        bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
956        /** Adds ray sample contributions to the PVS.
957                @param sampleContributions the number contributions of the samples
958                @param contributingSampels the number of contributing rays
959               
960        */
961        void AddSamplesToPvs(VspLeaf *leaf,
962                                                 const RayInfoContainer &rays,
963                                                 float &sampleContributions,
964                                                 int &contributingSamples);
965        /** Propagates valid flag up the tree.
966        */
967        void PropagateUpValidity(VspNode *node);
968        /** Returns estimated memory usage of tree.
969        */
970        float GetMemUsage() const;
971        /** Updates view cell pvs of objects.
972        */
973        void ProcessViewCellObjects(ViewCell *parent,
974                                                                ViewCell *front,
975                                                                ViewCell *back) const;
976        /** Creates a new view cell from the traversal data.
977        */
978        void CreateViewCell(VspTraversalData &tData,
979                                                const bool updatePvs,
980                                                const float renderCost,
981                                                const int pvs);
982        /** Collect split candidates which are affected by the last split
983                and must be reevaluated.
984        */
985        void CollectDirtyCandidates(VspSubdivisionCandidate *sc,
986                                                                vector<SubdivisionCandidate *> &dirtyList,
987                                                                const bool onlyUnmailed);
988        /** Adds the split candidate associated with this ray to the dirty list.
989        */
990        void AddCandidateToDirtyList(const VssRay &ray,
991                                                           const bool isTermination,
992                                                           vector<SubdivisionCandidate *> &dirtyList,
993                                                           const bool onlyUnmailed) const;
994        /** Rays will be clipped to the bounding box.
995        */
996        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
997        /** Evaluate subdivision statistics.
998        */
999        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
1000        /** Prepares the construction of the vsp tree.
1001        */
1002        void PrepareConstruction(SplitQueue &tQueue,
1003                                                         const VssRayContainer &sampleRays,
1004                                                         RayInfoContainer &rays);
1005        /** Evaluates pvs contribution of this ray.
1006        */
1007        float EvalContributionToPvs(const VssRay &ray, const bool isTermination) const;
1008        /** Evaluates pvs contribution of a kd node.
1009        */
1010        float EvalContributionToPvs(KdLeaf *leaf) const;
1011        /** Creates new root of hierarchy and computes bounding box.
1012                Has to be called before the preparation of the subdivision.
1013        */
1014        void Initialise(const VssRayContainer &rays,
1015                                        AxisAlignedBox3 *forcedBoundingBox,
1016                                        const ObjectContainer &objects);
1017
1018        int CompressObjects();
1019
1020        int CompressObjects(VspLeaf *leaf);
1021
1022        int TraverseRayPacket(RayPacket &rp, const bool useMailboxing);
1023
1024
1025#ifdef USE_SSE
1026        struct PacketTraversalData
1027        {
1028                PacketTraversalData () {}
1029       
1030                PacketTraversalData (VspNode *n,
1031                                         const __m128 &px, const __m128 &py, const __m128 &pz,
1032                                                         const __m128 &maxt,
1033                                                         const __m128 &mask):
1034                mNode(n),
1035                mExitPointX4(px), mExitPointY4(py), mExitPointZ4(pz),
1036                mMaxT4(maxt),
1037                mMask4(mask)
1038                {}
1039
1040                VspNode *mNode;
1041
1042                union { __m128 mExitPointX4; float mExitPointX[4]; };
1043                union { __m128 mExitPointY4; float mExitPointY[4]; };
1044                union { __m128 mExitPointZ4; float mExitPointZ[4]; };
1045
1046                union { __m128 mMaxT4; float mMaxT[4]; };
1047                union { __m128 mMask4; float mMask[4]; };
1048        };
1049
1050
1051        struct __declspec(align(16)) PacketTraversalStack
1052        {
1053                // for performance
1054                friend class VspTree;
1055
1056        public:
1057                PacketTraversalStack(const int depth):
1058                mStackPtr(0),
1059                //mDepth(depth)
1060                mDepth(1000)
1061                {
1062                        //mData = new PacketTraversalData[mDepth];
1063                }
1064
1065                ~PacketTraversalStack()
1066                {
1067                        //delete [] mData;
1068                }
1069               
1070                //PacketTraversalStack() {}
1071
1072                void Pop() {-- mStackPtr;}
1073                const PacketTraversalData &Top() const { return mData[mStackPtr - 1];}
1074               
1075                void Push(const PacketTraversalData &tData)
1076                {
1077                        // note: faster with direct assignments
1078                        mData[mStackPtr ++] = tData;
1079                        //if (mStackPtr == mDepth) std::cerr << "this can never happen!!" << std::endl;
1080                }
1081
1082                bool Empty() const {return mStackPtr <= 0;}
1083
1084        protected:
1085
1086                // static array to avoid using operator new
1087                //PacketTraversalData *mData;
1088                PacketTraversalData mData[1000];
1089
1090                int mStackPtr;
1091                int mDepth;
1092        };
1093
1094#endif
1095       
1096
1097protected:
1098
1099        /// pointer to the hierarchy of view cells
1100        ViewCellsTree *mViewCellsTree;
1101        /// Pointer to the hierarchy manager which is responsible for both
1102        /// view and object space
1103        HierarchyManager *mHierarchyManager;
1104        /// Pointer to the bv hierarchy
1105        BvHierarchy *mBvHierarchy;
1106        /// Pointer to the view cells manager
1107        ViewCellsManager *mViewCellsManager;
1108        /// Buffer for subdivision candidates used for split heuristics evaluation
1109        vector<SortableEntry> *mLocalSubdivisionCandidates;
1110        /// Pointer to the root of the tree
1111        VspNode *mRoot;
1112        /// The statistics
1113        VspTreeStatistics mVspStats;
1114        /// View cell corresponding to the space outside the valid view space
1115        VspViewCell *mOutOfBoundsCell;
1116        /// box around the whole view domain
1117        AxisAlignedBox3 mBoundingBox;
1118
1119
1120        /////////
1121        //-- local termination
1122
1123        /// minimal number of rays before subdivision termination
1124        int mTermMinRays;
1125        /// maximal possible depth
1126        int mTermMaxDepth;
1127        /// mininum probability
1128        float mTermMinProbability;
1129        /// mininum PVS
1130        int mTermMinPvs;
1131        /// maximal contribution per ray
1132        float mTermMaxRayContribution;
1133        /// maximal acceptable cost ratio
1134        float mTermMaxCostRatio;
1135        /// tolerance value indicating how often the max cost ratio can be failed
1136        int mTermMissTolerance;
1137
1138        ////////////
1139        //-- global criteria
1140
1141        float mTermMinGlobalCostRatio;
1142        int mTermGlobalCostMissTolerance;
1143       
1144
1145        /// maximal number of view cells
1146        int mMaxViewCells;
1147        /// maximal tree memory
1148        float mMaxMemory;
1149        /// the tree is out of memory
1150        bool mOutOfMemory;
1151
1152        ////////////
1153        //-- split heuristics based parameters
1154       
1155        bool mUseCostHeuristics;
1156        /// balancing factor for PVS criterium
1157        float mCtDivCi;
1158        /// if only driving axis should be used for split
1159        bool mOnlyDrivingAxis;
1160        /// if random split axis should be used
1161        bool mUseRandomAxis;
1162        /// if vsp bsp tree should simulate octree
1163        bool mCirculatingAxis;
1164        /// minimal relative position where the split axis can be placed
1165        float mMinBand;
1166        /// maximal relative position where the split axis can be placed
1167        float mMaxBand;
1168
1169
1170        /// current time stamp (used for keeping split history)
1171        int mTimeStamp;
1172        // if rays should be stored in leaves
1173        bool mStoreRays;
1174        /// epsilon for geometric comparisons
1175        float mEpsilon;
1176        /// subdivision stats output file
1177        std::ofstream mSubdivisionStats;
1178        /// keeps track of cost during subdivision
1179        float mTotalCost;
1180        /// keeps track of #pvs entries during subdivison
1181        int mPvsEntries;
1182        /// keeps track of overall pvs size during subdivision
1183        int mTotalPvsSize;
1184        /// number of currenly generated view cells
1185        int mCreatedViewCells;
1186
1187        /// weight between render cost decrease and node render cost
1188        float mRenderCostDecreaseWeight;
1189        /// maximal #of rays used for heuristics evalution
1190        int mMaxTests;
1191        /// constant value for driving the heuristics
1192        float mMemoryConst;
1193};
1194
1195
1196}
1197
1198#endif
Note: See TracBrowser for help on using the repository browser.