source: GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.h @ 1251

Revision 1251, 20.3 KB checked in by mattausch, 18 years ago (diff)
Line 
1#ifndef _OspTree_H__
2#define _OspTree_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
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;
38class SubdivisionCandidate;
39
40
41/** View space partition statistics.
42*/
43class OspTreeStatistics: public StatisticsBase
44{
45public:
46        // total number of nodes
47        int nodes;
48        // number of splits
49        int splits[3];
50       
51        // maximal reached depth
52        int maxDepth;
53        // minimal depth
54        int minDepth;
55       
56        // max depth nodes
57        int maxDepthNodes;
58        // minimum depth nodes
59        int minDepthNodes;
60        // max depth nodes
61        int minPvsNodes;
62        // minimum area nodes
63        int minProbabilityNodes;
64        /// nodes termination because of max cost ratio;
65        int maxCostNodes;
66        // max number of objects per node
67        int maxObjectRefs;
68        int objectRefs;
69        /// samples contributing to pvs
70        int contributingSamples;
71        /// sample contributions to pvs
72        int sampleContributions;
73        /// largest pvs
74        int maxPvs;
75        /// number of invalid leaves
76        int invalidLeaves;
77        /// accumulated number of rays refs
78        int accumRays;
79        /// potentially visible objects from this leaf
80        int pvs;
81
82        // accumulated depth (used to compute average)
83        int accumDepth;
84
85        // Constructor
86        OspTreeStatistics()
87        {
88                Reset();
89        }
90
91        int Nodes() const {return nodes;}
92        int Interior() const { return nodes / 2; }
93        int Leaves() const { return (nodes / 2) + 1; }
94       
95        // TODO: computation wrong
96        double AvgDepth() const { return accumDepth / (double)Leaves();};
97       
98
99        void Reset()
100        {
101                nodes = 0;
102                for (int i = 0; i < 3; ++ i)
103                        splits[i] = 0;
104               
105                maxDepth = 0;
106                minDepth = 99999;
107                accumDepth = 0;
108        pvs = 0;
109                maxDepthNodes = 0;
110                minPvsNodes = 0;
111       
112                minProbabilityNodes = 0;
113                maxCostNodes = 0;
114
115                contributingSamples = 0;
116                sampleContributions = 0;
117
118                maxPvs = 0;
119                invalidLeaves = 0;
120                objectRefs = 0;
121
122                maxObjectRefs = 0;
123        }
124
125
126        void Print(ostream &app) const;
127
128        friend ostream &operator<<(ostream &s, const OspTreeStatistics &stat)
129        {
130                stat.Print(s);
131                return s;
132        }
133};
134
135
136typedef map<KdNode *, KdIntersectable *> KdIntersectableMap;
137
138
139/** View Space Partitioning tree.
140*/
141class OspTree
142{
143        friend class ViewCellsParseHandlers;
144        friend class HierarchyManager;
145
146public:
147       
148        /** Additional data which is passed down the BSP tree during traversal.
149        */
150        class OspTraversalData
151        { 
152        public:
153                /// the current node
154                KdLeaf *mNode;
155                /// current depth
156                int mDepth;
157                /// rays piercing this node
158                RayInfoContainer *mRays;
159                /// the probability that this node contains view point
160                float mProbability;
161                /// the bounding box of the node
162                AxisAlignedBox3 mBoundingBox;
163                /// pvs size
164                float mRenderCost;
165                /// how often this branch has missed the max-cost ratio
166                int mMaxCostMisses;
167                // current axis
168                int mAxis;
169                // current priority
170                float mPriority;
171
172
173                OspTraversalData():
174                mNode(NULL),
175                mRays(NULL),
176                mDepth(0),
177                mRenderCost(0),
178                mProbability(0.0),
179                mMaxCostMisses(0),
180                mPriority(0),
181                mAxis(0)
182                {}
183               
184                OspTraversalData(KdLeaf *node,
185                                                 const int depth,
186                         RayInfoContainer *rays,
187                                                 const float rc,
188                                                 const float p,
189                                                 const AxisAlignedBox3 &box):
190                mNode(node),
191                mDepth(depth),
192                mRays(rays),
193                mRenderCost(rc),
194                mProbability(p),
195                mBoundingBox(box),
196                mMaxCostMisses(0),
197                mPriority(0),
198                mAxis(0)
199                {}
200
201                OspTraversalData(const int depth,
202                        RayInfoContainer *rays,
203                        const AxisAlignedBox3 &box):
204                mNode(NULL),
205                mDepth(depth),
206                mRays(rays),
207                mRenderCost(0),
208                mProbability(0),
209                mMaxCostMisses(0),
210                mAxis(0),
211                mBoundingBox(box)
212                {}
213
214                /** Returns cost of the traversal data.
215                */
216                float GetCost() const
217                {
218                        //cout << mPriority << endl;
219                        return mPriority;
220                }
221
222                /// deletes contents and sets them to NULL
223                void Clear()
224                {
225                        DEL_PTR(mRays);
226                }
227
228
229                friend bool operator<(const OspTraversalData &a, const OspTraversalData &b)
230                {
231                        return a.GetCost() < b.GetCost();
232                }
233    };
234
235        /** Candidate for a view space split.
236        */
237        class OspSubdivisionCandidate: public SubdivisionCandidate
238        { 
239        public:
240                static OspTree* sOspTree;
241
242                /// the current split plane
243                AxisAlignedPlane mSplitPlane;
244                /// parent data
245                OspTraversalData mParentData;
246               
247                OspSubdivisionCandidate(const OspTraversalData &tData): mParentData(tData)
248                {};
249
250                int Type() const { return OBJECT_SPACE; }
251       
252                void EvalPriority()
253                {
254                        sOspTree->EvalSubdivisionCandidate(*this);     
255                }
256
257                bool GlobalTerminationCriteriaMet() const
258                {
259                        return sOspTree->GlobalTerminationCriteriaMet(mParentData);
260                }
261
262
263                OspSubdivisionCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData):
264                mSplitPlane(plane), mParentData(tData)
265                {}
266        };
267
268        /** Struct for traversing line segment.
269        */
270        struct LineTraversalData
271        {
272                KdNode *mNode;
273                Vector3 mExitPoint;
274               
275                float mMaxT;
276   
277                LineTraversalData () {}
278                LineTraversalData (KdNode *n, const Vector3 &p, const float maxt):
279                mNode(n), mExitPoint(p), mMaxT(maxt) {}
280        };
281
282        /** Default constructor creating an empty tree.
283        */
284        OspTree();
285
286        /** Copies tree from a kd tree.
287        */
288        OspTree(const KdTree &kdTree);
289
290        /** Default destructor.
291        */
292        ~OspTree();
293
294        /** Returns tree statistics.
295        */
296        const OspTreeStatistics &GetStatistics() const;
297 
298        /** Returns bounding box of the specified node.
299        */
300        AxisAlignedBox3 GetBoundingBox(KdNode *node) const;
301
302        /** Returns list of leaves with pvs smaller than
303                a certain threshold.
304                @param onlyUnmailed if only the unmailed leaves should be considered
305                @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
306        */
307       
308        void CollectLeaves(vector<KdLeaf *> &leaves) const;
309
310        /** Returns bounding box of the whole tree (= bbox of root node)
311        */
312        AxisAlignedBox3 GetBoundingBox()const;
313
314        /** Returns root of the view space partitioning tree.
315        */
316        KdNode *GetRoot() const;
317
318        /** Collects the leaf view cells of the tree
319                @param viewCells returns the view cells
320        */
321        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
322
323        /** A ray is cast possible intersecting the tree.
324                @param the ray that is cast.
325                @returns the number of intersections with objects stored in the tree.
326        */
327        int CastRay(Ray &ray);
328
329        /** finds neighbouring leaves of this tree node.
330        */
331        int FindNeighbors(KdLeaf *n,
332                                          vector<VspLeaf *> &neighbors,
333                                          const bool onlyUnmailed) const;
334
335        /** Returns random leaf of BSP tree.
336                @param halfspace defines the halfspace from which the leaf is taken.
337        */
338        KdLeaf *GetRandomLeaf(const Plane3 &halfspace);
339
340        /** Returns random leaf of BSP tree.
341                @param onlyUnmailed if only unmailed leaves should be returned.
342        */
343        KdLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
344
345        /** Returns epsilon of this tree.
346        */
347        float GetEpsilon() const;
348
349        /** Casts line segment into the tree.
350                @param origin the origin of the line segment
351                @param termination the end point of the line segment
352                @returns view cells intersecting the line segment.
353        */
354    int CastLineSegment(const Vector3 &origin,
355                                                const Vector3 &termination,
356                                                ViewCellContainer &viewcells);
357               
358        /** Sets pointer to view cells manager.
359        */
360        void SetViewCellsManager(ViewCellsManager *vcm);
361
362        /** Writes tree to output stream
363        */
364        bool Export(OUT_STREAM &stream);
365
366        /** Returns or creates a new intersectable for use in a kd based pvs.
367                The OspTree is responsible for destruction of the intersectable.
368        */
369        KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);
370
371        /** Collects rays stored in the leaves.
372        */
373        void CollectRays(VssRayContainer &rays);
374
375        /** Intersects box with the tree and returns the number of intersected boxes.
376                @returns number of view cells found
377        */
378        int ComputeBoxIntersections(const AxisAlignedBox3 &box,
379                                                                ViewCellContainer &viewCells) const;
380
381
382        /** Returns kd leaf the point pt lies in, starting from root.
383        */
384        KdLeaf *GetLeaf(const Vector3 &pt, KdNode *root = NULL) const;
385
386
387        ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
388
389        void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }
390
391        float EvalRenderCost(const VssRayContainer &myrays);
392        float EvalLeafCost(const OspTraversalData &tData);
393
394        /** Adds this objects to the kd leaf objects.
395                @warning: Can corrupt the tree
396        */
397        void InsertObjects(KdNode *node, const ObjectContainer &objects);
398
399protected:
400
401        // --------------------------------------------------------------
402        // For sorting objects
403        // --------------------------------------------------------------
404        struct SortableEntry
405        {
406                /** There is a 3th "event" for rays which intersect a
407                        box in the middle. These "events" don't induce a change in
408                        pvs size, but may induce a change in view cell volume.
409                */
410                enum EType
411                {
412                        BOX_MIN,
413                        BOX_MAX,
414                        BOX_INTERSECT
415                };
416
417                int mType;
418                //int mPvs;
419                float mPos;
420                VssRay *mRay;
421               
422                Intersectable *mObject;
423
424                SortableEntry() {}
425
426                SortableEntry(const int type,
427                        //const float pvs,
428                        const float pos,
429                        Intersectable *obj,
430                        VssRay *ray):
431                mType(type),
432                //mPvs(pvs),
433                mPos(pos),
434                mObject(obj),
435                mRay(ray)
436                {}
437
438                bool operator<(const SortableEntry &b) const
439                {
440                        return mPos < b.mPos;
441                }
442        };
443
444 
445        /** faster evaluation of split plane cost for kd axis aligned cells.
446        */
447        float EvalLocalSplitCost(const OspTraversalData &data,
448                                                         const AxisAlignedBox3 &box,
449                                                         const int axis,
450                                                         const float &position,
451                                                         float &pFront,
452                                                         float &pBack) const;
453
454        /** Evaluates candidate for splitting.
455        */
456        void EvalSubdivisionCandidate(OspSubdivisionCandidate &splitData);
457
458        /** Computes priority of the traversal data and stores it in tData.
459        */
460        void EvalPriority(OspTraversalData &tData) const;
461
462        /** Evaluates render cost decrease of next split.
463        */
464        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
465                                                                 const OspTraversalData &data,
466                                                                 float &normalizedOldRenderCost) const;
467
468
469        /** Collects view cells in the subtree under root.
470        */
471        void CollectViewCells(KdNode *root,
472                                                  bool onlyValid,
473                                                  ViewCellContainer &viewCells,
474                                                  bool onlyUnmailed = false) const;
475
476        /** Evaluates tree stats in the BSP tree leafs.
477        */
478        void EvaluateLeafStats(const OspTraversalData &data);
479
480        /** Subdivides node using a best split priority queue.
481            @param tQueue the best split priority queue
482                @param splitCandidate the candidate for the next split
483                @param globalCriteriaMet if the global termination criteria were already met
484                @returns new root of the subtree
485        */
486        KdNode *Subdivide(SplitQueue &tQueue,
487                                          SubdivisionCandidate *splitCandidate,
488                                          const bool globalCriteriaMet);
489       
490        /** Subdivides leaf.
491                @param leaf the leaf to be subdivided
492               
493                @param polys the polygons to be split
494                @param frontPolys returns the polygons in front of the split plane
495                @param backPolys returns the polygons in the back of the split plane
496               
497                @param rays the polygons to be filtered
498                @param frontRays returns the polygons in front of the split plane
499                @param backRays returns the polygons in the back of the split plane
500
501                @returns the root of the subdivision
502        */
503        KdInterior *SubdivideNode(
504                const AxisAlignedPlane &splitPlane,
505                const OspTraversalData &tData,
506                OspTraversalData &frontData,
507                OspTraversalData &backData);
508
509        void SplitObjects(KdLeaf *leaf,
510                                          const AxisAlignedPlane & splitPlane,
511                                          const ObjectContainer &objects,
512                                          ObjectContainer &front,
513                                          ObjectContainer &back);
514
515        /** does some post processing on the objects in the new child leaves.
516        */
517        void ProcessMultipleRefs(KdLeaf *leaf) const;
518
519        /** Sorts split candidates for cost heuristics using axis aligned splits.
520                @param node the current node
521                @param axis the current split axis
522        */
523        void SortSubdivisionCandidates(const OspTraversalData &data,
524                                                         const int axis,
525                                                         float minBand,
526                                                         float maxBand);
527
528        /** Computes best cost for axis aligned planes.
529        */
530        float EvalLocalCostHeuristics(const OspTraversalData &tData,
531                const AxisAlignedBox3 &box,
532                const int axis,
533                float &position,
534                int &objectsFront,
535                int &objectsBack);
536
537        /** Subdivides the rays into front and back rays according to the split plane.
538               
539                @param plane the split plane
540                @param rays contains the rays to be split. The rays are
541                           distributed into front and back rays.
542                @param frontRays returns rays on the front side of the plane
543                @param backRays returns rays on the back side of the plane
544               
545                @returns the number of splits
546        */
547        int SplitRays(const AxisAlignedPlane &plane,
548                RayInfoContainer &rays,
549                RayInfoContainer &frontRays,
550                RayInfoContainer &backRays) const;
551
552        int FilterRays(KdLeaf *leaf, const RayInfoContainer &rays, RayInfoContainer &filteredRays);
553
554        /** Adds the object to the pvs of the front and back leaf with a given classification.
555
556                @param obj the object to be added
557                @param cf the ray classification regarding the split plane
558                @param frontPvs returns the PVS of the front partition
559                @param backPvs returns the PVS of the back partition
560       
561        */
562        void UpdateObjPvsContri(Intersectable *obj,
563                                         const int cf,
564                                         float &frontPvs,
565                                         float &backPvs,
566                                         float &totalPvs) const;
567       
568        /** Returns true if tree can be terminated.
569        */
570        bool LocalTerminationCriteriaMet(const OspTraversalData &data) const;
571
572        /** Returns true if global tree can be terminated.
573        */
574        bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
575
576        /** Selects an axis aligned for the next split.
577                @returns cost for this split
578        */
579        float SelectSplitPlane(
580                const OspTraversalData &tData,
581                AxisAlignedPlane &plane);
582       
583        /** Propagates valid flag up the tree.
584        */
585        void PropagateUpValidity(KdNode *node);
586
587        /** Writes the node to disk
588                @note: should be implemented as visitor.
589        */
590        void ExportNode(KdNode *node, OUT_STREAM &stream);
591
592        /** Returns estimated memory usage of tree.
593        */
594        float GetMemUsage() const;
595
596        /** Evaluate the contributions of view cell volume of the left and the right view cell.
597        */
598        void EvalRayContribution(KdLeaf *leaf,
599                                                                         const VssRay &ray,
600                                                                         float &renderCost);
601void EvalViewCellContribution(KdLeaf *leaf,
602                                                                           ViewCell *viewCell,
603                                                                           float &renderCost);
604        /** Evaluates the influence on the pvs of the event.
605                @param ve the visibility event
606                @param pvsLeft updates the left pvs
607                @param rightPvs updates the right pvs
608        */
609        void EvalHeuristicsContribution(KdLeaf *leaf,
610                const SortableEntry &ci,
611                float &renderCost,
612                ViewCellContainer &touchedViewCells);
613
614        /** Prepares objects for the cost heuristics.
615                @returns pvs size of the node
616        */
617        float PrepareHeuristics(const OspTraversalData &tData, ViewCellContainer &touchedViewCells);
618
619        /** Prepares heuristics for a particular ray.
620        */
621        void PrepareHeuristics(const VssRay &ray, ViewCellContainer &touchedViewCells);
622
623        /** Prepares construction for vsp and osp trees.
624        */
625        void ComputeBoundingBox(const ObjectContainer &objects,
626                                                        AxisAlignedBox3 *forcedBoundingBox);
627
628        void CollectDirtyCandidates(OspSubdivisionCandidate *sc,
629                vector<SubdivisionCandidate *> &dirtyList);
630
631        /** Collect view cells which see this kd leaf.
632        */
633        void CollectViewCells(KdLeaf *leaf,
634                ViewCellContainer &viewCells);
635
636        /** Rays will be clipped to the bounding box.
637        */
638        void PreprocessRays(
639                KdLeaf *root,
640                const VssRayContainer &sampleRays,
641                RayInfoContainer &rays);
642
643        /** Reads parameters from environment singleton.
644        */
645        void ReadEnvironment();
646
647        /** Returns true if the specified ray end points is inside the kd leaf.
648                @param isTermination if origin or termination point should be checked
649        */
650        bool EndPointInsideNode(KdLeaf *leaf, VssRay &ray, bool isTermination) const;
651
652        void AddViewCellVolumeContri(
653                ViewCell *vc,
654                float &frontVol,
655                float &backVol,
656                float &frontAndBackVol) const;
657
658        /** Classifies and mail view cell with respect to the heuristics contribution.
659                Set view cell mail box according to it's influence on
660                front (0), back (1) and front / back node (2).
661        */
662        void  MailViewCell(ViewCell *vc, const int cf) const;
663
664        int ClassifyRay(VssRay *ray, KdLeaf *leaf, const AxisAlignedPlane &plane) const;
665
666        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
667
668        void AddSubdivisionStats(const int viewCells,
669                const float renderCostDecr,
670                const float totalRenderCost);
671
672        void EvalViewCellsForHeuristics(const VssRay &ray,
673                float &volLeft,
674                float &volRight);
675
676        float EvalViewCellsVolume(KdLeaf *leaf, const RayInfoContainer &rays) const;
677       
678        int RemoveParentViewCellsPvs(KdLeaf *leaf,
679                                                                          const RayInfoContainer &rays
680                                                                          ) const;
681
682        int UpdateViewCellsPvs(KdLeaf *leaf, const RayInfoContainer &rays) const;
683int CheckViewCellsPvs(KdLeaf *leaf,
684                                                           const RayInfoContainer &rays) const;
685        bool AddViewCellToObjectPvs(
686                Intersectable *obj,
687                ViewCell *vc,
688                float &contribution,
689                bool onlyMailed) const;
690
691        int ClassifyRays(
692                const RayInfoContainer &rays,
693                KdLeaf *leaf,
694                const AxisAlignedPlane &plane,
695                RayInfoContainer &frontRays,
696                RayInfoContainer &backRays) const;
697
698        void CollectTouchedViewCells(
699                const RayInfoContainer &rays,
700                ViewCellContainer &touchedViewCells) const;
701
702        void AddObjectContribution(
703                KdLeaf *leaf,
704                Intersectable * obj,
705                ViewCellContainer &touchedViewCells,
706                float &renderCost);
707
708        void SubtractObjectContribution(
709                KdLeaf *leaf,
710                Intersectable * obj,
711                ViewCellContainer &touchedViewCells,
712                float &renderCost);
713
714        SubdivisionCandidate *PrepareConstruction(
715                const VssRayContainer &sampleRays,
716                const ObjectContainer &objects,
717                AxisAlignedBox3 *forcedObjectSpace,
718                RayInfoContainer &rays);
719
720protected:
721
722       
723        /// pointer to the hierarchy of view cells
724        ViewCellsTree *mViewCellsTree;
725
726        VspTree *mVspTree;
727
728        /// The view cells manager
729        ViewCellsManager *mViewCellsManager;
730
731        /// candidates for placing split planes during cost heuristics
732        vector<SortableEntry> *mSubdivisionCandidates;
733
734        /// Pointer to the root of the tree
735        KdNode *mRoot;
736               
737        /// Statistics for the object space partition
738        OspTreeStatistics mOspStats;
739       
740        /// box around the whole view domain
741        AxisAlignedBox3 mBoundingBox;
742
743
744        //-- local termination
745
746        /// maximal possible depth
747        int mTermMaxDepth;
748        /// mininum probability
749        float mTermMinProbability;
750        /// minimal number of objects
751        int mTermMinObjects;
752        /// maximal contribution per ray
753        float mTermMaxRayContribution;
754        /// maximal acceptable cost ratio
755        float mTermMaxCostRatio;
756        /// tolerance value indicating how often the max cost ratio can be failed
757        int mTermMissTolerance;
758
759
760        //-- global criteria
761
762        float mTermMinGlobalCostRatio;
763        int mTermGlobalCostMissTolerance;
764        int mGlobalCostMisses;
765
766        /// maximal number of view cells
767        int mTermMaxLeaves;
768        /// maximal tree memory
769        float mMaxMemory;
770        /// the tree is out of memory
771        bool mOutOfMemory;
772
773
774        //-- split heuristics based parameters
775       
776        bool mUseCostHeuristics;
777        /// balancing factor for PVS criterium
778        float mCtDivCi;
779        /// if only driving axis should be used for split
780        bool mOnlyDrivingAxis;
781       
782        /// current time stamp (used for keeping split history)
783        int mTimeStamp;
784        // if rays should be stored in leaves
785        bool mStoreRays;
786
787        /// epsilon for geometric comparisons
788        float mEpsilon;
789
790        /// subdivision stats output file
791        ofstream  mSubdivisionStats;
792        /// keeps track of cost during subdivision
793        float mTotalCost;
794        /// keeps track of overall pvs size during subdivision
795        int mTotalPvsSize;
796        /// number of currenly generated view cells
797        int mCreatedLeaves;
798
799        /// represents min and max band for sweep
800        float mSplitBorder;
801
802        /// weight between  render cost decrease and node render cost
803        float mRenderCostDecreaseWeight;
804
805        /// stores the kd node intersectables used for pvs
806        KdIntersectableMap mKdIntersectables;
807
808
809private:
810
811        bool mCopyFromKdTree;
812};
813
814
815}
816
817#endif
Note: See TracBrowser for help on using the repository browser.