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

Revision 1259, 20.4 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
399        /** Add the leaf to the pvs of the view cell.
400        */
401        bool AddLeafToPvs(
402                KdLeaf *leaf,
403                ViewCell *vc,
404                const float pdf,
405                float &contribution);
406
407protected:
408
409        // --------------------------------------------------------------
410        // For sorting objects
411        // --------------------------------------------------------------
412        struct SortableEntry
413        {
414                /** There is a 3th "event" for rays which intersect a
415                        box in the middle. These "events" don't induce a change in
416                        pvs size, but may induce a change in view cell volume.
417                */
418                enum EType
419                {
420                        BOX_MIN,
421                        BOX_MAX,
422                        BOX_INTERSECT
423                };
424
425                int mType;
426                //int mPvs;
427                float mPos;
428                VssRay *mRay;
429               
430                Intersectable *mObject;
431
432                SortableEntry() {}
433
434                SortableEntry(const int type,
435                        //const float pvs,
436                        const float pos,
437                        Intersectable *obj,
438                        VssRay *ray):
439                mType(type),
440                //mPvs(pvs),
441                mPos(pos),
442                mObject(obj),
443                mRay(ray)
444                {}
445
446                bool operator<(const SortableEntry &b) const
447                {
448                        return mPos < b.mPos;
449                }
450        };
451
452 
453        /** faster evaluation of split plane cost for kd axis aligned cells.
454        */
455        float EvalLocalSplitCost(const OspTraversalData &data,
456                                                         const AxisAlignedBox3 &box,
457                                                         const int axis,
458                                                         const float &position,
459                                                         float &pFront,
460                                                         float &pBack) const;
461
462        /** Evaluates candidate for splitting.
463        */
464        void EvalSubdivisionCandidate(OspSubdivisionCandidate &splitData);
465
466        /** Computes priority of the traversal data and stores it in tData.
467        */
468        void EvalPriority(OspTraversalData &tData) const;
469
470        /** Evaluates render cost decrease of next split.
471        */
472        float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
473                                                                 const OspTraversalData &data,
474                                                                 float &normalizedOldRenderCost) const;
475
476
477        /** Collects view cells in the subtree under root.
478        */
479        void CollectViewCells(KdNode *root,
480                                                  bool onlyValid,
481                                                  ViewCellContainer &viewCells,
482                                                  bool onlyUnmailed = false) const;
483
484        /** Evaluates tree stats in the BSP tree leafs.
485        */
486        void EvaluateLeafStats(const OspTraversalData &data);
487
488        /** Subdivides node using a best split priority queue.
489            @param tQueue the best split priority queue
490                @param splitCandidate the candidate for the next split
491                @param globalCriteriaMet if the global termination criteria were already met
492                @returns new root of the subtree
493        */
494        KdNode *Subdivide(SplitQueue &tQueue,
495                                          SubdivisionCandidate *splitCandidate,
496                                          const bool globalCriteriaMet);
497       
498        /** Subdivides leaf.
499                @param leaf the leaf to be subdivided
500               
501                @param polys the polygons to be split
502                @param frontPolys returns the polygons in front of the split plane
503                @param backPolys returns the polygons in the back of the split plane
504               
505                @param rays the polygons to be filtered
506                @param frontRays returns the polygons in front of the split plane
507                @param backRays returns the polygons in the back of the split plane
508
509                @returns the root of the subdivision
510        */
511        KdInterior *SubdivideNode(
512                const AxisAlignedPlane &splitPlane,
513                const OspTraversalData &tData,
514                OspTraversalData &frontData,
515                OspTraversalData &backData);
516
517        void SplitObjects(KdLeaf *leaf,
518                                          const AxisAlignedPlane & splitPlane,
519                                          const ObjectContainer &objects,
520                                          ObjectContainer &front,
521                                          ObjectContainer &back);
522
523        /** does some post processing on the objects in the new child leaves.
524        */
525        void ProcessMultipleRefs(KdLeaf *leaf) const;
526
527        /** Sorts split candidates for cost heuristics using axis aligned splits.
528                @param node the current node
529                @param axis the current split axis
530        */
531        void SortSubdivisionCandidates(const OspTraversalData &data,
532                                                         const int axis,
533                                                         float minBand,
534                                                         float maxBand);
535
536        /** Computes best cost for axis aligned planes.
537        */
538        float EvalLocalCostHeuristics(const OspTraversalData &tData,
539                const AxisAlignedBox3 &box,
540                const int axis,
541                float &position,
542                int &objectsFront,
543                int &objectsBack);
544
545        /** Subdivides the rays into front and back rays according to the split plane.
546               
547                @param plane the split plane
548                @param rays contains the rays to be split. The rays are
549                           distributed into front and back rays.
550                @param frontRays returns rays on the front side of the plane
551                @param backRays returns rays on the back side of the plane
552               
553                @returns the number of splits
554        */
555        int SplitRays(const AxisAlignedPlane &plane,
556                RayInfoContainer &rays,
557                RayInfoContainer &frontRays,
558                RayInfoContainer &backRays) const;
559
560        int FilterRays(KdLeaf *leaf, const RayInfoContainer &rays, RayInfoContainer &filteredRays);
561
562        /** Adds the object to the pvs of the front and back leaf with a given classification.
563
564                @param obj the object to be added
565                @param cf the ray classification regarding the split plane
566                @param frontPvs returns the PVS of the front partition
567                @param backPvs returns the PVS of the back partition
568       
569        */
570        void UpdateObjPvsContri(Intersectable *obj,
571                                         const int cf,
572                                         float &frontPvs,
573                                         float &backPvs,
574                                         float &totalPvs) const;
575       
576        /** Returns true if tree can be terminated.
577        */
578        bool LocalTerminationCriteriaMet(const OspTraversalData &data) const;
579
580        /** Returns true if global tree can be terminated.
581        */
582        bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;
583
584        /** Selects an axis aligned for the next split.
585                @returns cost for this split
586        */
587        float SelectSplitPlane(
588                const OspTraversalData &tData,
589                AxisAlignedPlane &plane);
590       
591        /** Propagates valid flag up the tree.
592        */
593        void PropagateUpValidity(KdNode *node);
594
595        /** Writes the node to disk
596                @note: should be implemented as visitor.
597        */
598        void ExportNode(KdNode *node, OUT_STREAM &stream);
599
600        /** Returns estimated memory usage of tree.
601        */
602        float GetMemUsage() const;
603
604        /** Evaluate the contributions of view cell volume of the left and the right view cell.
605        */
606        void EvalRayContribution(
607                KdLeaf *leaf,
608                const VssRay &ray,
609                float &renderCost);
610       
611        void EvalViewCellContribution(
612                KdLeaf *leaf,
613                ViewCell *viewCell,
614                float &renderCost);
615
616        /** Evaluates the influence on the pvs of the event.
617                @param ve the visibility event
618                @param pvsLeft updates the left pvs
619                @param rightPvs updates the right pvs
620        */
621        void EvalHeuristicsContribution(KdLeaf *leaf,
622                const SortableEntry &ci,
623                float &renderCost,
624                ViewCellContainer &touchedViewCells);
625
626        /** Prepares objects for the cost heuristics.
627                @returns pvs size of the node
628        */
629        float PrepareHeuristics(const OspTraversalData &tData, ViewCellContainer &touchedViewCells);
630
631        /** Prepares heuristics for a particular ray.
632        */
633        void PrepareHeuristics(const VssRay &ray, ViewCellContainer &touchedViewCells);
634
635        /** Prepares construction for vsp and osp trees.
636        */
637        void ComputeBoundingBox(const ObjectContainer &objects,
638                                                        AxisAlignedBox3 *forcedBoundingBox);
639
640        void CollectDirtyCandidates(OspSubdivisionCandidate *sc,
641                vector<SubdivisionCandidate *> &dirtyList);
642
643        /** Collect view cells which see this kd leaf.
644        */
645        void CollectViewCells(KdLeaf *leaf,
646                ViewCellContainer &viewCells);
647
648        /** Rays will be clipped to the bounding box.
649        */
650        void PreprocessRays(
651                KdLeaf *root,
652                const VssRayContainer &sampleRays,
653                RayInfoContainer &rays);
654
655        /** Reads parameters from environment singleton.
656        */
657        void ReadEnvironment();
658
659        /** Returns true if the specified ray end points is inside the kd leaf.
660                @param isTermination if origin or termination point should be checked
661        */
662        bool EndPointInsideNode(KdLeaf *leaf, VssRay &ray, bool isTermination) const;
663
664        void AddViewCellVolumeContri(
665                ViewCell *vc,
666                float &frontVol,
667                float &backVol,
668                float &frontAndBackVol) const;
669
670        /** Classifies and mail view cell with respect to the heuristics contribution.
671                Set view cell mail box according to it's influence on
672                front (0), back (1) and front / back node (2).
673        */
674        void  MailViewCell(ViewCell *vc, const int cf) const;
675
676        int ClassifyRay(VssRay *ray, KdLeaf *leaf, const AxisAlignedPlane &plane) const;
677
678        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
679
680        void AddSubdivisionStats(const int viewCells,
681                const float renderCostDecr,
682                const float totalRenderCost);
683
684        void EvalViewCellsForHeuristics(const VssRay &ray,
685                float &volLeft,
686                float &volRight);
687
688        float EvalViewCellsVolume(KdLeaf *leaf, const RayInfoContainer &rays) const;
689       
690        int RemoveParentViewCellsPvs(KdLeaf *leaf,
691                                                                          const RayInfoContainer &rays
692                                                                          ) const;
693
694        int UpdateViewCellsPvs(KdLeaf *leaf, const RayInfoContainer &rays) const;
695int CheckViewCellsPvs(KdLeaf *leaf,
696                                                           const RayInfoContainer &rays) const;
697        bool AddViewCellToObjectPvs(
698                Intersectable *obj,
699                ViewCell *vc,
700                float &contribution,
701                bool onlyMailed) const;
702
703        int ClassifyRays(
704                const RayInfoContainer &rays,
705                KdLeaf *leaf,
706                const AxisAlignedPlane &plane,
707                RayInfoContainer &frontRays,
708                RayInfoContainer &backRays) const;
709
710        void CollectTouchedViewCells(
711                const RayInfoContainer &rays,
712                ViewCellContainer &touchedViewCells) const;
713
714        void AddObjectContribution(
715                KdLeaf *leaf,
716                Intersectable * obj,
717                ViewCellContainer &touchedViewCells,
718                float &renderCost);
719
720        void SubtractObjectContribution(
721                KdLeaf *leaf,
722                Intersectable * obj,
723                ViewCellContainer &touchedViewCells,
724                float &renderCost);
725
726        SubdivisionCandidate *PrepareConstruction(
727                const VssRayContainer &sampleRays,
728                const ObjectContainer &objects,
729                AxisAlignedBox3 *forcedObjectSpace,
730                RayInfoContainer &rays);
731
732
733protected:
734       
735        /// pointer to the hierarchy of view cells
736        ViewCellsTree *mViewCellsTree;
737
738        VspTree *mVspTree;
739
740        /// The view cells manager
741        ViewCellsManager *mViewCellsManager;
742
743        /// candidates for placing split planes during cost heuristics
744        vector<SortableEntry> *mSubdivisionCandidates;
745
746        /// Pointer to the root of the tree
747        KdNode *mRoot;
748               
749        /// Statistics for the object space partition
750        OspTreeStatistics mOspStats;
751       
752        /// box around the whole view domain
753        AxisAlignedBox3 mBoundingBox;
754
755
756        //-- local termination
757
758        /// maximal possible depth
759        int mTermMaxDepth;
760        /// mininum probability
761        float mTermMinProbability;
762        /// minimal number of objects
763        int mTermMinObjects;
764        /// maximal contribution per ray
765        float mTermMaxRayContribution;
766        /// maximal acceptable cost ratio
767        float mTermMaxCostRatio;
768        /// tolerance value indicating how often the max cost ratio can be failed
769        int mTermMissTolerance;
770
771
772        //-- global criteria
773
774        float mTermMinGlobalCostRatio;
775        int mTermGlobalCostMissTolerance;
776        int mGlobalCostMisses;
777
778        /// maximal number of view cells
779        int mTermMaxLeaves;
780        /// maximal tree memory
781        float mMaxMemory;
782        /// the tree is out of memory
783        bool mOutOfMemory;
784
785
786        //-- split heuristics based parameters
787       
788        bool mUseCostHeuristics;
789        /// balancing factor for PVS criterium
790        float mCtDivCi;
791        /// if only driving axis should be used for split
792        bool mOnlyDrivingAxis;
793       
794        /// current time stamp (used for keeping split history)
795        int mTimeStamp;
796        // if rays should be stored in leaves
797        bool mStoreRays;
798
799        /// epsilon for geometric comparisons
800        float mEpsilon;
801
802        /// subdivision stats output file
803        ofstream  mSubdivisionStats;
804        /// keeps track of cost during subdivision
805        float mTotalCost;
806        /// keeps track of overall pvs size during subdivision
807        int mTotalPvsSize;
808        /// number of currenly generated view cells
809        int mCreatedLeaves;
810
811        /// represents min and max band for sweep
812        float mSplitBorder;
813
814        /// weight between  render cost decrease and node render cost
815        float mRenderCostDecreaseWeight;
816
817        /// stores the kd node intersectables used for pvs
818        KdIntersectableMap mKdIntersectables;
819
820
821private:
822
823        bool mCopyFromKdTree;
824};
825
826
827}
828
829#endif
Note: See TracBrowser for help on using the repository browser.