source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h @ 1233

Revision 1233, 47.6 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _VspOspTree_H__
2#define _VspOspTree_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 "FlexibleHeap.h"
13
14
15namespace GtpVisibilityPreprocessor {
16
17class ViewCellLeaf;
18class Plane3;
19class AxisAlignedBox3;
20class Ray;
21class ViewCellsStatistics;
22class ViewCellsManager;
23class MergeCandidate;
24class Beam;
25class ViewCellsTree;
26class Environment;
27class VspInterior;
28class VspLeaf;
29class VspNode;
30class KdNode;
31class KdInterior;
32class KdLeaf;
33class OspTree;
34class KdIntersectable;
35class KdTree;
36class VspTree;
37class KdTreeStatistics;
38
39
40
41template <typename T> class GtPriority
42{
43public:
44        bool operator() (const T c1, const T c2) const
45        {
46                //return false;
47                return c1->GetPriority() < c2->GetPriority();
48        }
49};
50
51
52/** View space partition statistics.
53*/
54class VspTreeStatistics: public StatisticsBase
55{
56public:
57        // total number of nodes
58        int nodes;
59        // number of splits
60        int splits[3];
61       
62        // totals number of rays
63        int rays;
64        // maximal reached depth
65        int maxDepth;
66        // minimal depth
67        int minDepth;
68       
69        // max depth nodes
70        int maxDepthNodes;
71        // minimum depth nodes
72        int minDepthNodes;
73        // max depth nodes
74        int minPvsNodes;
75        // nodes with minimum PVS
76        int minRaysNodes;
77        // max ray contribution nodes
78        int maxRayContribNodes;
79        // minimum area nodes
80        int minProbabilityNodes;
81        /// nodes termination because of max cost ratio;
82        int maxCostNodes;
83        // max number of rays per node
84        int maxObjectRefs;
85        /// samples contributing to pvs
86        int contributingSamples;
87        /// sample contributions to pvs
88        int sampleContributions;
89        /// largest pvs
90        int maxPvs;
91        /// number of invalid leaves
92        int invalidLeaves;
93        /// accumulated number of rays refs
94        int accumRays;
95        int pvs;
96        // accumulated depth (used to compute average)
97        int accumDepth;
98
99        // Constructor
100        VspTreeStatistics()
101        {
102                Reset();
103        }
104
105        int Nodes() const {return nodes;}
106        int Interior() const { return nodes / 2; }
107        int Leaves() const { return (nodes / 2) + 1; }
108       
109        // TODO: computation wrong
110        double AvgDepth() const { return accumDepth / (double)Leaves();};
111        double AvgRays() const { return accumRays / (double)Leaves();};
112
113        void Reset()
114        {
115                nodes = 0;
116                for (int i = 0; i < 3; ++ i)
117                        splits[i] = 0;
118               
119                maxDepth = 0;
120                minDepth = 99999;
121                accumDepth = 0;
122        pvs = 0;
123                maxDepthNodes = 0;
124                minPvsNodes = 0;
125                minRaysNodes = 0;
126                maxRayContribNodes = 0;
127                minProbabilityNodes = 0;
128                maxCostNodes = 0;
129
130                contributingSamples = 0;
131                sampleContributions = 0;
132
133                maxPvs = 0;
134                invalidLeaves = 0;
135                accumRays = 0;
136                maxObjectRefs = 0;
137        }
138
139        void Print(ostream &app) const;
140
141        friend ostream &operator<<(ostream &s, const VspTreeStatistics &stat)
142        {
143                stat.Print(s);
144                return s;
145        }
146};
147
148
149/** View space partition statistics.
150*/
151class OspTreeStatistics: public StatisticsBase
152{
153public:
154        // total number of nodes
155        int nodes;
156        // number of splits
157        int splits[3];
158       
159        // maximal reached depth
160        int maxDepth;
161        // minimal depth
162        int minDepth;
163       
164        // max depth nodes
165        int maxDepthNodes;
166        // minimum depth nodes
167        int minDepthNodes;
168        // max depth nodes
169        int minPvsNodes;
170        // minimum area nodes
171        int minProbabilityNodes;
172        /// nodes termination because of max cost ratio;
173        int maxCostNodes;
174        // max number of objects per node
175        int maxObjectRefs;
176        int objectRefs;
177        /// samples contributing to pvs
178        int contributingSamples;
179        /// sample contributions to pvs
180        int sampleContributions;
181        /// largest pvs
182        int maxPvs;
183        /// number of invalid leaves
184        int invalidLeaves;
185        /// accumulated number of rays refs
186        int accumRays;
187        /// potentially visible objects from this leaf
188        int pvs;
189
190        // accumulated depth (used to compute average)
191        int accumDepth;
192
193        // Constructor
194        OspTreeStatistics()
195        {
196                Reset();
197        }
198
199        int Nodes() const {return nodes;}
200        int Interior() const { return nodes / 2; }
201        int Leaves() const { return (nodes / 2) + 1; }
202       
203        // TODO: computation wrong
204        double AvgDepth() const { return accumDepth / (double)Leaves();};
205       
206
207        void Reset()
208        {
209                nodes = 0;
210                for (int i = 0; i < 3; ++ i)
211                        splits[i] = 0;
212               
213                maxDepth = 0;
214                minDepth = 99999;
215                accumDepth = 0;
216        pvs = 0;
217                maxDepthNodes = 0;
218                minPvsNodes = 0;
219       
220                minProbabilityNodes = 0;
221                maxCostNodes = 0;
222
223                contributingSamples = 0;
224                sampleContributions = 0;
225
226                maxPvs = 0;
227                invalidLeaves = 0;
228                objectRefs = 0;
229
230                maxObjectRefs = 0;
231        }
232
233
234        void Print(ostream &app) const;
235
236        friend ostream &operator<<(ostream &s, const OspTreeStatistics &stat)
237        {
238                stat.Print(s);
239                return s;
240        }
241};
242
243
244/**
245    VspNode abstract class serving for interior and leaf node implementation
246*/
247class VspNode
248{
249public:
250       
251        // types of vsp nodes
252        enum {Interior, Leaf};
253
254        VspNode();
255        virtual ~VspNode(){};
256        VspNode(VspInterior *parent);
257
258        /** Determines whether this node is a leaf or not
259                @return true if leaf
260        */
261        virtual bool IsLeaf() const = 0;
262
263        virtual int Type() const = 0;
264
265        /** Determines whether this node is a root
266                @return true if root
267        */
268        virtual bool IsRoot() const;
269
270        /** Returns parent node.
271        */
272        VspInterior *GetParent();
273
274        /** Sets parent node.
275        */
276        void SetParent(VspInterior *parent);
277
278        /** Returns true if this node is a sibling of node n.
279        */
280        bool IsSibling(VspNode *n) const;
281
282        /** returns depth of the node.
283        */
284        int GetDepth() const;
285
286        /** returns true if the whole subtree is valid
287        */
288        bool TreeValid() const;
289
290        void SetTreeValid(const bool v);
291
292        //-- mailing options
293
294        void Mail() { mMailbox = sMailId; }
295        static void NewMail() { ++ sMailId; }
296        bool Mailed() const { return mMailbox == sMailId; }
297
298        static int sMailId;
299        int mMailbox;
300
301        int mTimeStamp;
302
303protected:
304
305        /// if this sub tree is a completely valid view space region
306        bool mTreeValid;
307        /// parent of this node
308        VspInterior *mParent;
309};
310
311
312/** BSP interior node implementation
313*/
314class VspInterior: public VspNode
315{
316public:
317        /** Standard contructor taking split plane as argument.
318        */
319        VspInterior(const AxisAlignedPlane &plane);
320
321        ~VspInterior();
322        /** @return false since it is an interior node
323        */
324        bool IsLeaf() const;
325
326        int Type() const;
327
328        VspNode *GetBack();
329        VspNode *GetFront();
330
331        /** Returns split plane.
332        */
333        AxisAlignedPlane GetPlane() const;
334
335        /** Returns position of split plane.
336        */
337        float GetPosition() const;
338
339        /** Returns split axis.
340        */
341        int GetAxis() const;
342
343        /** Replace front or back child with new child.
344        */
345        void ReplaceChildLink(VspNode *oldChild, VspNode *newChild);
346
347        /** Replace front and back child.
348        */
349        void SetupChildLinks(VspNode *front, VspNode *back);
350
351        friend ostream &operator<<(ostream &s, const VspInterior &A)
352        {
353                return s << A.mPlane.mAxis << " " << A.mPlane.mPosition;
354        }
355
356        AxisAlignedBox3 GetBoundingBox() const;
357        void SetBoundingBox(const AxisAlignedBox3 &box);
358
359        /** Computes intersection of this plane with the ray segment.
360        */
361        int ComputeRayIntersection(const RayInfo &rayData, float &t) const
362        {
363                return rayData.ComputeRayIntersection(mPlane.mAxis, mPlane.mPosition, t);
364        }
365
366
367protected:
368
369        AxisAlignedBox3 mBoundingBox;
370
371        /// Splitting plane corresponding to this node
372        AxisAlignedPlane mPlane;
373
374        /// back node
375        VspNode *mBack;
376        /// front node
377        VspNode *mFront;
378};
379
380
381/** BSP leaf node implementation.
382*/
383class VspLeaf: public VspNode
384{
385        friend VspTree;
386
387public:
388        VspLeaf();
389        VspLeaf(ViewCellLeaf *viewCell);
390        VspLeaf(VspInterior *parent);
391        VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell);
392
393        ~VspLeaf();
394
395        /** @return true since it is an interior node
396        */
397        bool IsLeaf() const;
398       
399        int Type() const;
400
401        /** Returns pointer of view cell.
402        */
403        ViewCellLeaf *GetViewCell() const;
404
405        /** Sets pointer to view cell.
406        */
407        void SetViewCell(ViewCellLeaf *viewCell);
408
409        SplitCandidate *GetSplitCandidate() const
410        {
411                return mSplitCandidate;
412        }
413
414public:
415
416        /// Rays piercing this leaf.
417        VssRayContainer mVssRays;
418       
419        /// leaf pvs
420        ObjectPvs *mPvs;
421
422        /// Probability that the view point lies in this leaf
423        float mProbability;
424
425protected:
426
427        /// pointer to a split plane candidate splitting this leaf
428        SplitCandidate *mSplitCandidate;
429
430        /// if NULL this does not correspond to feasible viewcell
431        ViewCellLeaf *mViewCell;
432};
433
434
435#if 0
436typedef std::priority_queue<SplitCandidate *,
437                                                        std::vector<SplitCandidate *>,
438                                                        GtPriority<std::vector<SplitCandidate *>::value_type> > SplitQueue;
439#endif
440
441typedef map<KdNode *, KdIntersectable *> KdIntersectableMap;
442
443typedef FlexibleHeap<SplitCandidate *> SplitQueue;
444
445/** View Space Partitioning tree.
446*/
447class VspTree
448{
449        friend class ViewCellsParseHandlers;
450        friend class HierarchyManager;
451
452public:
453       
454        /** Additional data which is passed down the BSP tree during traversal.
455        */
456        class VspTraversalData
457        { 
458        public:
459                /// the current node
460                VspLeaf *mNode;
461                /// current depth
462                int mDepth;
463                /// rays piercing this node
464                RayInfoContainer *mRays;
465                /// the probability that this node contains view point
466                float mProbability;
467                /// the bounding box of the node
468                AxisAlignedBox3 mBoundingBox;
469                /// pvs size
470                int mPvs;
471                /// how often this branch has missed the max-cost ratio
472                int mMaxCostMisses;
473                // current priority
474                float mPriority;
475
476               
477                /** Returns average ray contribution.
478                */
479                float GetAvgRayContribution() const
480                {
481                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
482                }
483
484
485                VspTraversalData():
486                mNode(NULL),
487                mDepth(0),
488                mRays(NULL),
489                mPvs(0),
490                mProbability(0.0),
491                mMaxCostMisses(0),
492                mPriority(0)
493                {}
494               
495                VspTraversalData(VspLeaf *node,
496                                                 const int depth,
497                                                 RayInfoContainer *rays,
498                                                 const int pvs,
499                                                 const float p,
500                                                 const AxisAlignedBox3 &box):
501                mNode(node),
502                mDepth(depth),
503                mRays(rays),
504                mPvs(pvs),
505                mProbability(p),
506                mBoundingBox(box),
507                mMaxCostMisses(0),
508                mPriority(0)
509                {}
510
511                VspTraversalData(const int depth,
512                                                 RayInfoContainer *rays,
513                                                 const AxisAlignedBox3 &box):
514                mNode(NULL),
515                mDepth(depth),
516                mRays(rays),
517                mPvs(0),
518                mProbability(0),
519                mMaxCostMisses(0),
520                mBoundingBox(box)
521                {}
522
523                /** Returns cost of the traversal data.
524                */
525                float GetCost() const
526                {
527                        //cout << mPriority << endl;
528                        return mPriority;
529                }
530
531                /// deletes contents and sets them to NULL
532                void Clear()
533                {
534                        DEL_PTR(mRays);
535                }
536
537                friend bool operator<(const VspTraversalData &a, const VspTraversalData &b)
538                {
539                        return a.GetCost() < b.GetCost();
540                }
541    };
542
543        /** Candidate for a view space split.
544        */
545        class VspSplitCandidate: public SplitCandidate
546        { 
547        public:
548
549                static VspTree* sVspTree;
550
551                /// parent node traversal data
552                VspTraversalData mParentData;
553               
554                VspSplitCandidate(const VspTraversalData &tData): mParentData(tData)
555                {};
556
557                int Type() const { return VIEW_SPACE; }
558
559                void EvalPriority()
560                {
561                        sVspTree->EvalSplitCandidate(*this);   
562                }
563
564                bool GlobalTerminationCriteriaMet() const
565                {
566                        return sVspTree->GlobalTerminationCriteriaMet(mParentData);
567                }
568
569                VspSplitCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData):
570                SplitCandidate(plane), mParentData(tData)
571                {}
572        };
573
574        /** Struct for traversing line segment.
575        */
576        struct LineTraversalData
577        {
578                VspNode *mNode;
579                Vector3 mExitPoint;
580               
581                float mMaxT;
582   
583                LineTraversalData () {}
584                LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
585                mNode(n), mExitPoint(p), mMaxT(maxt) {}
586        };
587
588        //typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue;
589
590        /** Default constructor creating an empty tree.
591        */
592        VspTree();
593
594        /** Default destructor.
595        */
596        ~VspTree();
597
598        /** Returns BSP Tree statistics.
599        */
600        const VspTreeStatistics &GetStatistics() const;
601 
602        /** Returns bounding box of the specified node.
603        */
604        AxisAlignedBox3 GetBoundingBox(VspNode *node) const;
605
606        /** Returns list of BSP leaves with pvs smaller than
607                a certain threshold.
608                @param onlyUnmailed if only the unmailed leaves should be considered
609                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
610        */
611        void CollectLeaves(vector<VspLeaf *> &leaves,
612                                           const bool onlyUnmailed = false,
613                                           const int maxPvs = -1) const;
614
615        /** Returns box which bounds the whole tree.
616        */
617        AxisAlignedBox3 GetBoundingBox() const;
618
619        /** Returns root of the view space partitioning tree.
620        */
621        VspNode *GetRoot() const;
622
623        /** Collects the leaf view cells of the tree
624                @param viewCells returns the view cells
625        */
626        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
627
628        /** A ray is cast possible intersecting the tree.
629                @param the ray that is cast.
630                @returns the number of intersections with objects stored in the tree.
631        */
632        int CastRay(Ray &ray);
633
634
635        /** finds neighbouring leaves of this tree node.
636        */
637        int FindNeighbors(VspLeaf *n,
638                                          vector<VspLeaf *> &neighbors,
639                                          const bool onlyUnmailed) const;
640
641        /** Returns random leaf of BSP tree.
642                @param halfspace defines the halfspace from which the leaf is taken.
643        */
644        VspLeaf *GetRandomLeaf(const Plane3 &halfspace);
645
646        /** Returns random leaf of BSP tree.
647                @param onlyUnmailed if only unmailed leaves should be returned.
648        */
649        VspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
650
651        /** Returns epsilon of this tree.
652        */
653        float GetEpsilon() const;
654
655        /** Casts line segment into the tree.
656                @param origin the origin of the line segment
657                @param termination the end point of the line segment
658                @returns view cells intersecting the line segment.
659        */
660    int CastLineSegment(const Vector3 &origin,
661                                                const Vector3 &termination,
662                                                ViewCellContainer &viewcells);
663
664               
665        /** Sets pointer to view cells manager.
666        */
667        void SetViewCellsManager(ViewCellsManager *vcm);
668
669        /** Returns view cell the current point is located in.
670                @param point the current view point
671                @param active if currently active view cells should be returned or
672                elementary view cell
673        */
674        ViewCell *GetViewCell(const Vector3 &point, const bool active = false);
675
676
677        /** Returns true if this view point is in a valid view space,
678                false otherwise.
679        */
680        bool ViewPointValid(const Vector3 &viewPoint) const;
681
682        /** Returns view cell corresponding to
683                the invalid view space.
684        */
685        VspViewCell *GetOutOfBoundsCell();
686
687        /** Writes tree to output stream
688        */
689        bool Export(OUT_STREAM &stream);
690
691        /** Casts beam, i.e. a 5D frustum of rays, into tree.
692                Tests conservative using the bounding box of the nodes.
693                @returns number of view cells it intersected
694        */
695        int CastBeam(Beam &beam);
696
697
698        /** Checks if tree validity-flags are right
699                with respect to view cell valitiy.
700                If not, marks subtree as invalid.
701        */
702        void ValidateTree();
703
704        /** Invalid view cells are added to the unbounded space
705        */
706        void CollapseViewCells();
707
708        /** Collects rays stored in the leaves.
709        */
710        void CollectRays(VssRayContainer &rays);
711
712        /** Intersects box with the tree and returns the number of intersected boxes.
713                @returns number of view cells found
714        */
715        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
716                                                                ViewCellContainer &viewCells) const;
717
718        /** Remove the references of the parent view cell from the kd nodes associated with
719                the objects.
720        */
721        void RemoveParentViewCellReferences(ViewCell *parent) const;
722
723        /** Adds references to the view cell to the kd nodes associated with the objects.
724        */
725        void AddViewCellReferences(ViewCell *vc) const;
726
727        /** Returns view cells of this ray, either taking precomputed cells
728                or by recomputation.
729        */
730        void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);
731
732
733        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
734
735        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
736
737
738protected:
739
740        // --------------------------------------------------------------
741        // For sorting objects
742        // --------------------------------------------------------------
743        struct SortableEntry
744        {
745                enum EType
746                {
747                        ERayMin,
748                        ERayMax
749                };
750
751                int type;
752                float value;
753                VssRay *ray;
754 
755                SortableEntry() {}
756                SortableEntry(const int t, const float v, VssRay *r):
757                type(t), value(v), ray(r)
758                {
759                }
760               
761                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
762                {
763                        return a.value < b.value;
764                }
765        };
766
767        /** faster evaluation of split plane cost for kd axis aligned cells.
768        */
769        float EvalLocalSplitCost(const VspTraversalData &data,
770                                                         const AxisAlignedBox3 &box,
771                                                         const int axis,
772                                                         const float &position,
773                                                         float &pFront,
774                                                         float &pBack) const;
775
776        void ComputeBoundingBox(const VssRayContainer &rays,
777                                                        AxisAlignedBox3 *forcedBoundingBox);
778
779        /** Evaluates candidate for splitting.
780        */
781        void EvalSplitCandidate(VspSplitCandidate &splitData);
782
783        /** Evaluates render cost decrease of next split.
784        */
785        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
786                                                                 const VspTraversalData &data,
787                                                                 float &normalizedOldRenderCost) const;
788
789        /** Collects view cells in the subtree under root.
790        */
791        void CollectViewCells(VspNode *root,
792                                                  bool onlyValid,
793                                                  ViewCellContainer &viewCells,
794                                                  bool onlyUnmailed = false) const;
795
796        /** Returns view cell corresponding to
797                the invalid view space. If it does not exist, it is created.
798        */
799        VspViewCell *GetOrCreateOutOfBoundsCell();
800
801        /** Collapses the tree with respect to the view cell partition,
802                i.e. leaves having the same view cell are collapsed.
803                @param node the root of the subtree to be collapsed
804                @param collapsed returns the number of collapsed nodes
805                @returns node of type leaf if the node could be collapsed,
806                this node otherwise
807        */
808        VspNode *CollapseTree(VspNode *node, int &collapsed);
809
810        /** Helper function revalidating the view cell leaf list after merge.
811        */
812        void RepairViewCellsLeafLists();
813
814        /** Evaluates tree stats in the BSP tree leafs.
815        */
816        void EvaluateLeafStats(const VspTraversalData &data);
817
818        /** Subdivides node using a best split priority queue.
819            @param tQueue the best split priority queue
820                @param splitCandidate the candidate for the next split
821                @param globalCriteriaMet if the global termination criteria were already met
822                @returns new root of the subtree
823        */
824        VspNode *Subdivide(SplitQueue &tQueue,
825                                           SplitCandidate *splitCandidate,
826                                           const bool globalCriteriaMet);
827
828        /** Adds stats to subdivision log file.
829        */
830        void AddSubdivisionStats(const int viewCells,
831                                                         const float renderCostDecr,
832                                                         const float totalRenderCost,
833                                                         const float avgRenderCost);
834       
835        /** Subdivides leaf.
836                       
837                @param tData data object holding, e.g., a pointer to the leaf
838                @param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
839                @param backData returns the data (e.g.,  pointer to the leaf) in the back of the split plane
840               
841                @param rays the polygons to be filtered
842                @param frontRays returns the polygons in front of the split plane
843       
844                @returns the root of the subdivision
845        */
846        VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
847                                                           VspTraversalData &tData,
848                                                           VspTraversalData &frontData,
849                               VspTraversalData &backData);
850
851        /** Selects an axis aligned for the next split.
852                @returns cost for this split
853        */
854        float SelectSplitPlane(const VspTraversalData &tData,
855                                                   AxisAlignedPlane &plane,
856                                                   float &pFront,
857                                                   float &pBack);
858
859        /** Sorts split candidates along the specified axis.
860                The split candidates are generated on possible visibility
861                events (i.e., where ray segments intersect the ray boundaries).
862                The sorted candidates are needed to compute the heuristics.
863
864                @param polys the input for choosing split candidates
865                @param axis the current split axis
866                @param splitCandidates returns sorted list of split candidates
867        */
868        void SortSplitCandidates(const RayInfoContainer &rays,
869                                                         const int axis,
870                                                         float minBand,
871                                                         float maxBand);
872
873        /** Evaluate pvs size associated with the rays.
874        */
875        int EvalPvsSize(const RayInfoContainer &rays) const;
876
877        /** Computes pvs increase with respect to the previous pvs for heuristics.
878        */
879        int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);
880
881        /** Returns absolute pvs contribution of this object.
882        */
883        int GetPvsContribution(Intersectable *object) const;
884
885        /** Computes best cost for axis aligned planes.
886        */
887        float EvalLocalCostHeuristics(const VspTraversalData &tData,
888                                                                  const AxisAlignedBox3 &box,
889                                                                  const int axis,
890                                                                  float &position);
891
892        /** Evaluates the influence on the pvs of the visibility event ve.
893                @param ve the visibility event
894                @param pvsLeft updates the left pvs
895                @param rightPvs updates the right pvs
896        */
897        void EvalPvsIncr(const SortableEntry &ve,
898                                          int &pvsLeft,
899                                          int &pvsRight) const;
900
901        void RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const;
902        void AddContriToPvs(KdLeaf *leaf, int &pvs) const;
903
904        /** Prepares objects for the heuristics.
905                @returns pvs size of the ray container
906        */
907        int PrepareHeuristics(const RayInfoContainer &rays);
908
909        int PrepareHeuristics(KdLeaf *leaf);
910
911        /** Subdivides the rays into front and back rays according to the split plane.
912               
913                @param plane the split plane
914                @param rays contains the rays to be split. The rays are
915                           distributed into front and back rays.
916                @param frontRays returns rays on the front side of the plane
917                @param backRays returns rays on the back side of the plane
918               
919                @returns the number of splits
920        */
921        int SplitRays(const AxisAlignedPlane &plane,
922                                  RayInfoContainer &rays,
923                              RayInfoContainer &frontRays,
924                                  RayInfoContainer &backRays) const;
925
926        /** Classfifies the object with respect to the
927                pvs of the front and back leaf and updates pvs size
928                accordingly.
929
930                @param obj the object to be added
931                @param cf the ray classification regarding the split plane
932                @param frontPvs returns the PVS of the front partition
933                @param backPvs returns the PVS of the back partition
934       
935        */
936        void UpdateObjPvsContri(Intersectable *obj,
937                                         const int cf,
938                                         float &frontPvs,
939                                         float &backPvs,
940                                         float &totalPvs) const;
941       
942        /** See UpdateObjPvsContri.
943        */
944        void UpdateKdLeafPvsContri(KdLeaf *leaf,
945                const int cf,
946                float &frontPvs,
947                float &backPvs,
948                float &totalPvs) const;
949
950        /** Collects pvs from rays.
951        */
952        void CollectPvs(const RayInfoContainer &rays,
953                                        ObjectContainer &objects) const;
954
955        /** Returns true if tree can be terminated.
956        */
957        /*inline*/ bool LocalTerminationCriteriaMet(const VspTraversalData &data) const;
958
959        /** Returns true if global tree can be terminated.
960        */
961        /*inline*/ bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;
962
963        /** Adds ray sample contributions to the PVS.
964                @param sampleContributions the number contributions of the samples
965                @param contributingSampels the number of contributing rays
966               
967        */
968        void AddSamplesToPvs(VspLeaf *leaf,
969                                                 const RayInfoContainer &rays,
970                                                 float &sampleContributions,
971                                                 int &contributingSamples);
972
973        bool AddKdLeafToPvs(KdLeaf *leaf,
974                                                ViewCell *vc,
975                                                const float pvs,
976                                                float &contribution);
977
978        /** Propagates valid flag up the tree.
979        */
980        void PropagateUpValidity(VspNode *node);
981
982        /** Writes the node to disk
983                @note: should be implemented as visitor.
984        */
985        void ExportNode(VspNode *node, OUT_STREAM &stream);
986
987        /** Returns estimated memory usage of tree.
988        */
989        float GetMemUsage() const;
990
991        /** Updates view cell pvs of objects.
992        */
993        void ProcessViewCellObjects(ViewCell *parent,
994                ViewCell *front,
995                ViewCell *back) const;
996
997        void CreateViewCell(VspTraversalData &tData, const bool updatePvs);
998
999        /** Collect split candidates which are affected by the last split
1000                and must be reevaluated.
1001        */
1002        void CollectDirtyCandidates(VspSplitCandidate *sc, vector<SplitCandidate *> &dirtyList);
1003
1004        /** Rays will be clipped to the bounding box.
1005        */
1006        void PreprocessRays(const VssRayContainer &sampleRays, RayInfoContainer &rays);
1007
1008        /** Evaluate subdivision statistics.
1009        */
1010        void EvalSubdivisionStats(const SplitCandidate &tData);
1011
1012
1013
1014protected:
1015
1016
1017        /// pointer to the hierarchy of view cells
1018        ViewCellsTree *mViewCellsTree;
1019
1020        OspTree *mOspTree;
1021
1022        bool mUseKdPvsForHeuristics;
1023        bool mStoreKdPvs;
1024
1025        ViewCellsManager *mViewCellsManager;
1026       
1027        vector<SortableEntry> *mLocalSplitCandidates;
1028
1029        /// Pointer to the root of the tree
1030        VspNode *mRoot;
1031               
1032        VspTreeStatistics mVspStats;
1033       
1034        /// View cell corresponding to the space outside the valid view space
1035        VspViewCell *mOutOfBoundsCell;
1036
1037        /// box around the whole view domain
1038        AxisAlignedBox3 mBoundingBox;
1039
1040
1041        //-- local termination
1042
1043        /// minimal number of rays before subdivision termination
1044        int mTermMinRays;
1045        /// maximal possible depth
1046        int mTermMaxDepth;
1047        /// mininum probability
1048        float mTermMinProbability;
1049        /// mininum PVS
1050        int mTermMinPvs;
1051        /// maximal contribution per ray
1052        float mTermMaxRayContribution;
1053        /// maximal acceptable cost ratio
1054        float mTermMaxCostRatio;
1055        /// tolerance value indicating how often the max cost ratio can be failed
1056        int mTermMissTolerance;
1057
1058
1059        //-- global criteria
1060        float mTermMinGlobalCostRatio;
1061        int mTermGlobalCostMissTolerance;
1062        int mGlobalCostMisses;
1063
1064        /// maximal number of view cells
1065        int mMaxViewCells;
1066        /// maximal tree memory
1067        float mMaxMemory;
1068        /// the tree is out of memory
1069        bool mOutOfMemory;
1070
1071
1072        //-- split heuristics based parameters
1073       
1074        bool mUseCostHeuristics;
1075        /// balancing factor for PVS criterium
1076        float mCtDivCi;
1077        /// if only driving axis should be used for split
1078        bool mOnlyDrivingAxis;
1079        /// if random split axis should be used
1080        bool mUseRandomAxis;
1081        /// if vsp bsp tree should simulate octree
1082        bool mCirculatingAxis;
1083        /// minimal relative position where the split axis can be placed
1084        float mMinBand;
1085        /// maximal relative position where the split axis can be placed
1086        float mMaxBand;
1087
1088
1089        /// current time stamp (used for keeping split history)
1090        int mTimeStamp;
1091        // if rays should be stored in leaves
1092        bool mStoreRays;
1093
1094        /// epsilon for geometric comparisons
1095        float mEpsilon;
1096
1097
1098        /// subdivision stats output file
1099        ofstream  mSubdivisionStats;
1100        /// keeps track of cost during subdivision
1101        float mTotalCost;
1102        /// keeps track of overall pvs size during subdivision
1103        int mTotalPvsSize;
1104        /// number of currenly generated view cells
1105        int mCreatedViewCells;
1106
1107        /// weight between render cost decrease and node render cost
1108        float mRenderCostDecreaseWeight;
1109
1110        int mMaxTests;
1111};
1112
1113
1114/** View Space Partitioning tree.
1115*/
1116class OspTree
1117{
1118        friend class ViewCellsParseHandlers;
1119        friend class HierarchyManager;
1120
1121public:
1122       
1123        /** Additional data which is passed down the BSP tree during traversal.
1124        */
1125        class OspTraversalData
1126        { 
1127        public:
1128                /// the current node
1129                KdLeaf *mNode;
1130                /// current depth
1131                int mDepth;
1132                /// rays piercing this node
1133                RayInfoContainer *mRays;
1134                /// the probability that this node contains view point
1135                float mProbability;
1136                /// the bounding box of the node
1137                AxisAlignedBox3 mBoundingBox;
1138                /// pvs size
1139                float mRenderCost;
1140                /// how often this branch has missed the max-cost ratio
1141                int mMaxCostMisses;
1142                // current axis
1143                int mAxis;
1144                // current priority
1145                float mPriority;
1146
1147
1148                OspTraversalData():
1149                mNode(NULL),
1150                mRays(NULL),
1151                mDepth(0),
1152                mRenderCost(0),
1153                mProbability(0.0),
1154                mMaxCostMisses(0),
1155                mPriority(0),
1156                mAxis(0)
1157                {}
1158               
1159                OspTraversalData(KdLeaf *node,
1160                                                 const int depth,
1161                         RayInfoContainer *rays,
1162                                                 const float rc,
1163                                                 const float p,
1164                                                 const AxisAlignedBox3 &box):
1165                mNode(node),
1166                mDepth(depth),
1167                mRays(rays),
1168                mRenderCost(rc),
1169                mProbability(p),
1170                mBoundingBox(box),
1171                mMaxCostMisses(0),
1172                mPriority(0),
1173                mAxis(0)
1174                {}
1175
1176                OspTraversalData(const int depth,
1177                        RayInfoContainer *rays,
1178                        const AxisAlignedBox3 &box):
1179                mNode(NULL),
1180                mDepth(depth),
1181                mRays(rays),
1182                mRenderCost(0),
1183                mProbability(0),
1184                mMaxCostMisses(0),
1185                mAxis(0),
1186                mBoundingBox(box)
1187                {}
1188
1189                /** Returns cost of the traversal data.
1190                */
1191                float GetCost() const
1192                {
1193                        //cout << mPriority << endl;
1194                        return mPriority;
1195                }
1196
1197                /// deletes contents and sets them to NULL
1198                void Clear()
1199                {
1200                        DEL_PTR(mRays);
1201                }
1202
1203
1204                friend bool operator<(const OspTraversalData &a, const OspTraversalData &b)
1205                {
1206                        return a.GetCost() < b.GetCost();
1207                }
1208    };
1209
1210        /** Candidate for a view space split.
1211        */
1212        class OspSplitCandidate: public SplitCandidate
1213        { 
1214        public:
1215                static OspTree* sOspTree;
1216
1217                /// parent data
1218                OspTraversalData mParentData;
1219               
1220                OspSplitCandidate(const OspTraversalData &tData): mParentData(tData)
1221                {};
1222
1223                int Type() const { return OBJECT_SPACE; }
1224       
1225                void EvalPriority()
1226                {
1227                        sOspTree->EvalSplitCandidate(*this);   
1228                }
1229
1230                bool GlobalTerminationCriteriaMet() const
1231                {
1232                        return sOspTree->GlobalTerminationCriteriaMet(mParentData);
1233                }
1234
1235
1236                OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData):
1237                SplitCandidate(plane), mParentData(tData)
1238                {}
1239        };
1240
1241        /** Struct for traversing line segment.
1242        */
1243        struct LineTraversalData
1244        {
1245                KdNode *mNode;
1246                Vector3 mExitPoint;
1247               
1248                float mMaxT;
1249   
1250                LineTraversalData () {}
1251                LineTraversalData (KdNode *n, const Vector3 &p, const float maxt):
1252                mNode(n), mExitPoint(p), mMaxT(maxt) {}
1253        };
1254
1255        //typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue;
1256
1257        /** Default constructor creating an empty tree.
1258        */
1259        OspTree();
1260
1261        OspTree(const KdTree &kdTree);
1262
1263        /** Default destructor.
1264        */
1265        ~OspTree();
1266
1267        /** Returns tree statistics.
1268        */
1269        const OspTreeStatistics &GetStatistics() const;
1270 
1271        /** Returns bounding box of the specified node.
1272        */
1273        AxisAlignedBox3 GetBoundingBox(KdNode *node) const;
1274
1275        /** Returns list of leaves with pvs smaller than
1276                a certain threshold.
1277                @param onlyUnmailed if only the unmailed leaves should be considered
1278                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
1279        */
1280       
1281        void CollectLeaves(vector<KdLeaf *> &leaves) const;
1282
1283        /** Returns bounding box of the whole tree (= bbox of root node)
1284        */
1285        AxisAlignedBox3 GetBoundingBox()const;
1286
1287        /** Returns root of the view space partitioning tree.
1288        */
1289        KdNode *GetRoot() const;
1290
1291        /** Collects the leaf view cells of the tree
1292                @param viewCells returns the view cells
1293        */
1294        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
1295
1296        /** A ray is cast possible intersecting the tree.
1297                @param the ray that is cast.
1298                @returns the number of intersections with objects stored in the tree.
1299        */
1300        int CastRay(Ray &ray);
1301
1302        /** finds neighbouring leaves of this tree node.
1303        */
1304        int FindNeighbors(KdLeaf *n,
1305                                          vector<VspLeaf *> &neighbors,
1306                                          const bool onlyUnmailed) const;
1307
1308        /** Returns random leaf of BSP tree.
1309                @param halfspace defines the halfspace from which the leaf is taken.
1310        */
1311        KdLeaf *GetRandomLeaf(const Plane3 &halfspace);
1312
1313        /** Returns random leaf of BSP tree.
1314                @param onlyUnmailed if only unmailed leaves should be returned.
1315        */
1316        KdLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
1317
1318        /** Returns epsilon of this tree.
1319        */
1320        float GetEpsilon() const;
1321
1322        /** Casts line segment into the tree.
1323                @param origin the origin of the line segment
1324                @param termination the end point of the line segment
1325                @returns view cells intersecting the line segment.
1326        */
1327    int CastLineSegment(const Vector3 &origin,
1328                                                const Vector3 &termination,
1329                                                ViewCellContainer &viewcells);
1330               
1331        /** Sets pointer to view cells manager.
1332        */
1333        void SetViewCellsManager(ViewCellsManager *vcm);
1334
1335        /** Writes tree to output stream
1336        */
1337        bool Export(OUT_STREAM &stream);
1338
1339        /** Returns or creates a new intersectable for use in a kd based pvs.
1340                The OspTree is responsible for destruction of the intersectable.
1341        */
1342        KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);
1343
1344        /** Collects rays stored in the leaves.
1345        */
1346        void CollectRays(VssRayContainer &rays);
1347
1348        /** Intersects box with the tree and returns the number of intersected boxes.
1349                @returns number of view cells found
1350        */
1351        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
1352                                                                ViewCellContainer &viewCells) const;
1353
1354
1355        /** Returns kd leaf the point pt lies in, starting from root.
1356        */
1357        KdLeaf *GetLeaf(const Vector3 &pt, KdNode *root = NULL) const;
1358
1359
1360        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
1361
1362        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
1363
1364        float EvalRenderCost(const VssRayContainer &myrays);
1365        float EvalLeafCost(const OspTraversalData &tData);
1366
1367        /** Adds this objects to the kd leaf objects.
1368                @warning: Can corrupt the tree
1369        */
1370        void InsertObjects(KdNode *node, const ObjectContainer &objects);
1371
1372protected:
1373
1374        // --------------------------------------------------------------
1375        // For sorting objects
1376        // --------------------------------------------------------------
1377        struct SortableEntry
1378        {
1379                /** There is a 3th "event" for rays which intersect a
1380                        box in the middle. These "events" don't induce a change in
1381                        pvs size, but may induce a change in view cell volume.
1382                */
1383                enum EType
1384                {
1385                        BOX_MIN,
1386                        BOX_MAX,
1387                        BOX_INTERSECT
1388                };
1389
1390                int mType;
1391                //int mPvs;
1392                float mPos;
1393                VssRay *mRay;
1394               
1395                Intersectable *mObject;
1396
1397                SortableEntry() {}
1398
1399                SortableEntry(const int type,
1400                        //const float pvs,
1401                        const float pos,
1402                        Intersectable *obj,
1403                        VssRay *ray):
1404                mType(type),
1405                //mPvs(pvs),
1406                mPos(pos),
1407                mObject(obj),
1408                mRay(ray)
1409                {}
1410
1411                bool operator<(const SortableEntry &b) const
1412                {
1413                        return mPos < b.mPos;
1414                }
1415        };
1416
1417 
1418        /** faster evaluation of split plane cost for kd axis aligned cells.
1419        */
1420        float EvalLocalSplitCost(const OspTraversalData &data,
1421                                                         const AxisAlignedBox3 &box,
1422                                                         const int axis,
1423                                                         const float &position,
1424                                                         float &pFront,
1425                                                         float &pBack) const;
1426
1427        /** Evaluates candidate for splitting.
1428        */
1429        void EvalSplitCandidate(OspSplitCandidate &splitData);
1430
1431        /** Computes priority of the traversal data and stores it in tData.
1432        */
1433        void EvalPriority(OspTraversalData &tData) const;
1434
1435        /** Evaluates render cost decrease of next split.
1436        */
1437        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1438                                                                 const OspTraversalData &data,
1439                                                                 float &normalizedOldRenderCost) const;
1440
1441
1442        /** Collects view cells in the subtree under root.
1443        */
1444        void CollectViewCells(KdNode *root,
1445                                                  bool onlyValid,
1446                                                  ViewCellContainer &viewCells,
1447                                                  bool onlyUnmailed = false) const;
1448
1449        /** Evaluates tree stats in the BSP tree leafs.
1450        */
1451        void EvaluateLeafStats(const OspTraversalData &data);
1452
1453        /** Subdivides node using a best split priority queue.
1454            @param tQueue the best split priority queue
1455                @param splitCandidate the candidate for the next split
1456                @param globalCriteriaMet if the global termination criteria were already met
1457                @returns new root of the subtree
1458        */
1459        KdNode *Subdivide(SplitQueue &tQueue,
1460                                          SplitCandidate *splitCandidate,
1461                                          const bool globalCriteriaMet);
1462       
1463        /** Subdivides leaf.
1464                @param leaf the leaf to be subdivided
1465               
1466                @param polys the polygons to be split
1467                @param frontPolys returns the polygons in front of the split plane
1468                @param backPolys returns the polygons in the back of the split plane
1469               
1470                @param rays the polygons to be filtered
1471                @param frontRays returns the polygons in front of the split plane
1472                @param backRays returns the polygons in the back of the split plane
1473
1474                @returns the root of the subdivision
1475        */
1476        KdInterior *SubdivideNode(
1477                const AxisAlignedPlane &splitPlane,
1478                const OspTraversalData &tData,
1479                OspTraversalData &frontData,
1480                OspTraversalData &backData);
1481
1482        void SplitObjects(KdLeaf *leaf,
1483                                          const AxisAlignedPlane & splitPlane,
1484                                          const ObjectContainer &objects,
1485                                          ObjectContainer &front,
1486                                          ObjectContainer &back);
1487
1488        /** does some post processing on the objects in the new child leaves.
1489        */
1490        void ProcessMultipleRefs(KdLeaf *leaf) const;
1491
1492        /** Selects an axis aligned for the next split.
1493                @returns cost for this split
1494        */
1495        float SelectPlane(const OspTraversalData &tData,
1496                                          AxisAlignedPlane &plane,
1497                                          float &pFront,
1498                                          float &pBack);
1499
1500        /** Sorts split candidates for cost heuristics using axis aligned splits.
1501                @param node the current node
1502                @param axis the current split axis
1503        */
1504        void SortSplitCandidates(const OspTraversalData &data,
1505                                                         const int axis,
1506                                                         float minBand,
1507                                                         float maxBand);
1508
1509        /** Computes best cost for axis aligned planes.
1510        */
1511        float EvalLocalCostHeuristics(const OspTraversalData &tData,
1512                const AxisAlignedBox3 &box,
1513                const int axis,
1514                float &position,
1515                int &objectsFront,
1516                int &objectsBack);
1517
1518        /** Subdivides the rays into front and back rays according to the split plane.
1519               
1520                @param plane the split plane
1521                @param rays contains the rays to be split. The rays are
1522                           distributed into front and back rays.
1523                @param frontRays returns rays on the front side of the plane
1524                @param backRays returns rays on the back side of the plane
1525               
1526                @returns the number of splits
1527        */
1528        int SplitRays(const AxisAlignedPlane &plane,
1529                RayInfoContainer &rays,
1530                RayInfoContainer &frontRays,
1531                RayInfoContainer &backRays) const;
1532
1533        int FilterRays(KdLeaf *leaf, const RayInfoContainer &rays, RayInfoContainer &filteredRays);
1534
1535        /** Adds the object to the pvs of the front and back leaf with a given classification.
1536
1537                @param obj the object to be added
1538                @param cf the ray classification regarding the split plane
1539                @param frontPvs returns the PVS of the front partition
1540                @param backPvs returns the PVS of the back partition
1541       
1542        */
1543        void UpdateObjPvsContri(
1544                Intersectable *obj,
1545                const int cf,
1546                float &frontPvs,
1547                float &backPvs,
1548                float &totalPvs) const;
1549       
1550        /** Returns true if tree can be terminated.
1551        */
1552        /*inline*/ bool LocalTerminationCriteriaMet(const OspTraversalData &data) const;
1553
1554        /** Returns true if global tree can be terminated.
1555        */
1556        /*inline*/ bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
1557
1558        float SelectSplitPlane(const OspTraversalData &tData,
1559                AxisAlignedPlane &plane,
1560                float &pFront,
1561                float &pBack);
1562       
1563        /** Propagates valid flag up the tree.
1564        */
1565        void PropagateUpValidity(KdNode *node);
1566
1567        /** Writes the node to disk
1568                @note: should be implemented as visitor.
1569        */
1570        void ExportNode(KdNode *node, OUT_STREAM &stream);
1571
1572        /** Returns estimated memory usage of tree.
1573        */
1574        float GetMemUsage() const;
1575
1576        /** Evaluate the contributions of view cell volume of the left and the right view cell.
1577        */
1578        void EvalRayContribution(KdLeaf *leaf,
1579                                                                         const VssRay &ray,
1580                                                                         float &renderCost);
1581void EvalViewCellContribution(KdLeaf *leaf,
1582                                                                           ViewCell *viewCell,
1583                                                                           float &renderCost);
1584        /** Evaluates the influence on the pvs of the event.
1585                @param ve the visibility event
1586                @param pvsLeft updates the left pvs
1587                @param rightPvs updates the right pvs
1588        */
1589        void EvalHeuristicsContribution(KdLeaf *leaf,
1590                const SortableEntry &ci,
1591                float &renderCost,
1592                ViewCellContainer &touchedViewCells);
1593
1594        /** Prepares objects for the cost heuristics.
1595                @returns pvs size of the node
1596        */
1597        float PrepareHeuristics(const OspTraversalData &tData, ViewCellContainer &touchedViewCells);
1598
1599        /** Prepares heuristics for a particular ray.
1600        */
1601        void PrepareHeuristics(const VssRay &ray, ViewCellContainer &touchedViewCells);
1602
1603        /** Prepares construction for vsp and osp trees.
1604        */
1605        void ComputeBoundingBox(const ObjectContainer &objects,
1606                                                        AxisAlignedBox3 *forcedBoundingBox);
1607
1608        void CollectDirtyCandidates(OspSplitCandidate *sc,
1609                vector<SplitCandidate *> &dirtyList);
1610
1611        /** Collect view cells which see this kd leaf.
1612        */
1613        void CollectViewCells(KdLeaf *leaf,
1614                ViewCellContainer &viewCells);
1615
1616        /** Rays will be clipped to the bounding box.
1617        */
1618        void PreprocessRays(
1619                KdLeaf *root,
1620                const VssRayContainer &sampleRays,
1621                RayInfoContainer &rays);
1622
1623        /** Reads parameters from environment singleton.
1624        */
1625        void ReadEnvironment();
1626
1627        /** Returns true if the specified ray end points is inside the kd leaf.
1628                @param isTermination if origin or termination point should be checked
1629        */
1630        bool EndPointInsideNode(KdLeaf *leaf, VssRay &ray, bool isTermination) const;
1631
1632        void AddViewCellVolumeContri(
1633                ViewCell *vc,
1634                float &frontVol,
1635                float &backVol,
1636                float &frontAndBackVol) const;
1637
1638        /** Classifies and mail view cell with respect to the heuristics contribution.
1639                Set view cell mail box according to it's influence on
1640                front (0), back (1) and front / back node (2).
1641        */
1642        void  MailViewCell(ViewCell *vc, const int cf) const;
1643
1644        int ClassifyRay(VssRay *ray, KdLeaf *leaf, const AxisAlignedPlane &plane) const;
1645
1646        void EvalSubdivisionStats(const SplitCandidate &tData);
1647
1648        void AddSubdivisionStats(const int viewCells,
1649                const float renderCostDecr,
1650                const float totalRenderCost);
1651
1652        void EvalViewCellsForHeuristics(const VssRay &ray,
1653                float &volLeft,
1654                float &volRight);
1655
1656        float EvalViewCellsVolume(KdLeaf *leaf, const RayInfoContainer &rays) const;
1657       
1658        int RemoveParentViewCellsPvs(KdLeaf *leaf,
1659                                                                          const RayInfoContainer &rays
1660                                                                          ) const;
1661
1662        int UpdateViewCellsPvs(KdLeaf *leaf, const RayInfoContainer &rays) const;
1663int CheckViewCellsPvs(KdLeaf *leaf,
1664                                                           const RayInfoContainer &rays) const;
1665        bool AddViewCellToObjectPvs(
1666                Intersectable *obj,
1667                ViewCell *vc,
1668                float &contribution,
1669                bool onlyMailed) const;
1670
1671        int ClassifyRays(
1672                const RayInfoContainer &rays,
1673                KdLeaf *leaf,
1674                const AxisAlignedPlane &plane,
1675                RayInfoContainer &frontRays,
1676                RayInfoContainer &backRays) const;
1677
1678        void CollectTouchedViewCells(
1679                const RayInfoContainer &rays,
1680                ViewCellContainer &touchedViewCells) const;
1681
1682        void AddObjectContribution(KdLeaf *leaf,
1683                                                  Intersectable * obj,
1684                                                  ViewCellContainer &touchedViewCells,
1685                                                  float &renderCost);
1686        void SubtractObjectContribution(KdLeaf *leaf,
1687                                                  Intersectable * obj,
1688                                                  ViewCellContainer &touchedViewCells,
1689                                                  float &renderCost);
1690protected:
1691
1692       
1693        /// pointer to the hierarchy of view cells
1694        ViewCellsTree *mViewCellsTree;
1695
1696        VspTree *mVspTree;
1697
1698        /// The view cells manager
1699        ViewCellsManager *mViewCellsManager;
1700
1701        /// candidates for placing split planes during cost heuristics
1702        vector<SortableEntry> *mSplitCandidates;
1703
1704        /// Pointer to the root of the tree
1705        KdNode *mRoot;
1706               
1707        /// Statistics for the object space partition
1708        OspTreeStatistics mOspStats;
1709       
1710        /// box around the whole view domain
1711        AxisAlignedBox3 mBoundingBox;
1712
1713
1714        //-- local termination
1715
1716        /// maximal possible depth
1717        int mTermMaxDepth;
1718        /// mininum probability
1719        float mTermMinProbability;
1720        /// minimal number of objects
1721        int mTermMinObjects;
1722        /// maximal contribution per ray
1723        float mTermMaxRayContribution;
1724        /// maximal acceptable cost ratio
1725        float mTermMaxCostRatio;
1726        /// tolerance value indicating how often the max cost ratio can be failed
1727        int mTermMissTolerance;
1728
1729
1730        //-- global criteria
1731
1732        float mTermMinGlobalCostRatio;
1733        int mTermGlobalCostMissTolerance;
1734        int mGlobalCostMisses;
1735
1736        /// maximal number of view cells
1737        int mTermMaxLeaves;
1738        /// maximal tree memory
1739        float mMaxMemory;
1740        /// the tree is out of memory
1741        bool mOutOfMemory;
1742
1743
1744        //-- split heuristics based parameters
1745       
1746        bool mUseCostHeuristics;
1747        /// balancing factor for PVS criterium
1748        float mCtDivCi;
1749        /// if only driving axis should be used for split
1750        bool mOnlyDrivingAxis;
1751       
1752        /// current time stamp (used for keeping split history)
1753        int mTimeStamp;
1754        // if rays should be stored in leaves
1755        bool mStoreRays;
1756
1757        /// epsilon for geometric comparisons
1758        float mEpsilon;
1759
1760        /// subdivision stats output file
1761        ofstream  mSubdivisionStats;
1762        /// keeps track of cost during subdivision
1763        float mTotalCost;
1764        /// keeps track of overall pvs size during subdivision
1765        int mTotalPvsSize;
1766        /// number of currenly generated view cells
1767        int mCreatedLeaves;
1768
1769        /// represents min and max band for sweep
1770        float mSplitBorder;
1771
1772        /// weight between  render cost decrease and node render cost
1773        float mRenderCostDecreaseWeight;
1774
1775        /// stores the kd node intersectables used for pvs
1776        KdIntersectableMap mKdIntersectables;
1777
1778
1779private:
1780
1781        bool mCopyFromKdTree;
1782};
1783
1784
1785/** This class implements a structure holding two different hierarchies,
1786        one for object space partitioning and one for view space partitioning.
1787
1788        The object space and the view space are subdivided using a cost heuristics.
1789        If an object space split or a view space split is chosen is also evaluated
1790        based on the heuristics.
1791       
1792        The view space heuristics is evaluated by weighting and adding the pvss of the back and
1793        front node of each specific split. unlike for the standalone method vspbsp tree,
1794        the pvs of an object would not be the pvs of single object but that of all objects
1795        which are contained in the same leaf of the object subdivision. This could be done
1796        by storing the pointer to the object space partition parent, which would allow access to all children.
1797        Another possibility is to include traced kd-cells in the ray casing process.
1798
1799        Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
1800        the contribution to an object to the pvs is the number of view cells it can be seen from.
1801
1802        @note
1803        There is a potential efficiency problem involved in a sense that once a certain type
1804        of split is chosen for view space / object space, the candidates for the next split of
1805        object space / view space must be reevaluated.
1806       
1807*/
1808class HierarchyManager
1809{
1810public:
1811        /** Constructor taking an object space partition and a view space partition tree.
1812        */
1813        HierarchyManager(VspTree &vspTree, OspTree &ospTree);
1814
1815        /** Constructs the view space and object space subdivision from a given set of rays
1816                and a set of objects.
1817                @param sampleRays the set of sample rays the construction is based on
1818                @param objects the set of objects
1819        */
1820        void Construct(const VssRayContainer &sampleRays,
1821                                   const ObjectContainer &objects,
1822                                   AxisAlignedBox3 *forcedViewSpace);
1823
1824        /** Constructs first view cells, then object space partition.
1825        */
1826        void Construct2(const VssRayContainer &sampleRays,
1827                                        const ObjectContainer &objects,
1828                                        AxisAlignedBox3 *forcedViewSpace);
1829
1830        /** Constructs only vsp tree.
1831        */
1832        void Construct3(const VssRayContainer &sampleRays,
1833                                        const ObjectContainer &objects,
1834                                        AxisAlignedBox3 *forcedViewSpace);
1835
1836public:
1837        VspTree &mVspTree;
1838        OspTree &mOspTree;
1839
1840protected:
1841
1842        bool GlobalTerminationCriteriaMet(SplitCandidate *candidate) const;
1843
1844        void PrepareConstruction(const VssRayContainer &sampleRays,
1845                const ObjectContainer &objects,
1846                AxisAlignedBox3 *forcedViewSpace,
1847                RayInfoContainer &viewSpaceRays,
1848                RayInfoContainer &objectSpaceRays);
1849
1850        void RunConstruction(const bool repair);
1851        bool SubdivideSplitCandidate(SplitCandidate *sc);
1852
1853        bool FinishedConstruction() const;
1854
1855        SplitCandidate *NextSplitCandidate();
1856
1857        void RepairQueue();
1858
1859        void CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList);
1860
1861        VspTree::VspSplitCandidate *PrepareVsp(const VssRayContainer &sampleRays,
1862                                                           AxisAlignedBox3 *forcedViewSpace,
1863                                                           RayInfoContainer &rays);
1864
1865        OspTree::OspSplitCandidate *PrepareOsp(const VssRayContainer &sampleRays,
1866                const ObjectContainer &objects,
1867                AxisAlignedBox3 *forcedObjectSpace,
1868                RayInfoContainer &rays);
1869
1870        void EvalSubdivisionStats(const SplitCandidate &tData);
1871
1872        void AddSubdivisionStats(const int splits,
1873                const float renderCostDecr,
1874                const float totalRenderCost);
1875
1876
1877protected:
1878
1879        AxisAlignedBox3 mBoundingBox;
1880
1881        SplitQueue mTQueue;
1882
1883        SplitCandidate *mCurrentCandidate;
1884
1885        //-- global criteria
1886        float mTermMinGlobalCostRatio;
1887        int mTermGlobalCostMissTolerance;
1888        int mGlobalCostMisses;
1889
1890        /// keeps track of cost during subdivision
1891        float mTotalCost;
1892
1893        ofstream mSubdivisionStats;
1894};
1895
1896}
1897
1898#endif
Note: See TracBrowser for help on using the repository browser.