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

Revision 1287, 20.3 KB checked in by mattausch, 18 years ago (diff)

implemented bv hierarchy

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(
630                const OspTraversalData &tData,
631                ViewCellContainer &touchedViewCells);
632
633        /** Prepares heuristics for a particular ray.
634        */
635        void PrepareHeuristics(
636                const VssRay &ray,
637                ViewCellContainer &touchedViewCells);
638
639        /** Prepares construction for vsp and osp trees.
640        */
641        void ComputeBoundingBox(const ObjectContainer &objects);
642
643        void CollectDirtyCandidates(OspSubdivisionCandidate *sc,
644                vector<SubdivisionCandidate *> &dirtyList);
645
646        /** Collect view cells which see this kd leaf.
647        */
648        void CollectViewCells(KdLeaf *leaf,
649                ViewCellContainer &viewCells);
650
651        /** Rays will be clipped to the bounding box.
652        */
653        void PreprocessRays(
654                KdLeaf *root,
655                const VssRayContainer &sampleRays,
656                RayInfoContainer &rays);
657
658        /** Reads parameters from environment singleton.
659        */
660        void ReadEnvironment();
661
662        /** Returns true if the specified ray end points is inside the kd leaf.
663                @param isTermination if origin or termination point should be checked
664        */
665        bool EndPointInsideNode(KdLeaf *leaf, VssRay &ray, bool isTermination) const;
666
667        void AddViewCellVolumeContri(
668                ViewCell *vc,
669                float &frontVol,
670                float &backVol,
671                float &frontAndBackVol) const;
672
673        /** Classifies and mail view cell with respect to the heuristics contribution.
674                Set view cell mail box according to it's influence on
675                front (0), back (1) and front / back node (2).
676        */
677        void  MailViewCell(ViewCell *vc, const int cf) const;
678
679        int ClassifyRay(VssRay *ray, KdLeaf *leaf, const AxisAlignedPlane &plane) const;
680
681        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
682
683        void AddSubdivisionStats(const int viewCells,
684                const float renderCostDecr,
685                const float totalRenderCost);
686
687        void EvalViewCellsForHeuristics(const VssRay &ray,
688                float &volLeft,
689                float &volRight);
690
691        float EvalViewCellsVolume(KdLeaf *leaf, const RayInfoContainer &rays) const;
692       
693        int RemoveParentViewCellsPvs(KdLeaf *leaf,
694                                                                          const RayInfoContainer &rays
695                                                                          ) const;
696
697        int UpdateViewCellsPvs(KdLeaf *leaf, const RayInfoContainer &rays) const;
698int CheckViewCellsPvs(KdLeaf *leaf,
699                                                           const RayInfoContainer &rays) const;
700        bool AddViewCellToObjectPvs(
701                Intersectable *obj,
702                ViewCell *vc,
703                float &contribution,
704                bool onlyMailed) const;
705
706        int ClassifyRays(
707                const RayInfoContainer &rays,
708                KdLeaf *leaf,
709                const AxisAlignedPlane &plane,
710                RayInfoContainer &frontRays,
711                RayInfoContainer &backRays) const;
712
713        void CollectTouchedViewCells(
714                const RayInfoContainer &rays,
715                ViewCellContainer &touchedViewCells) const;
716
717        void AddObjectContribution(
718                KdLeaf *leaf,
719                Intersectable * obj,
720                ViewCellContainer &touchedViewCells,
721                float &renderCost);
722
723        void SubtractObjectContribution(
724                KdLeaf *leaf,
725                Intersectable * obj,
726                ViewCellContainer &touchedViewCells,
727                float &renderCost);
728
729        SubdivisionCandidate *PrepareConstruction(
730                const VssRayContainer &sampleRays,
731                const ObjectContainer &objects,
732                RayInfoContainer &rays);
733
734
735protected:
736       
737        /// pointer to the hierarchy of view cells
738        ViewCellsTree *mViewCellsTree;
739
740        VspTree *mVspTree;
741
742        /// The view cells manager
743        ViewCellsManager *mViewCellsManager;
744
745        /// candidates for placing split planes during cost heuristics
746        vector<SortableEntry> *mSubdivisionCandidates;
747
748        /// Pointer to the root of the tree
749        KdNode *mRoot;
750               
751        /// Statistics for the object space partition
752        OspTreeStatistics mOspStats;
753       
754        /// box around the whole view domain
755        AxisAlignedBox3 mBoundingBox;
756
757
758        //-- local termination
759
760        /// maximal possible depth
761        int mTermMaxDepth;
762        /// mininum probability
763        float mTermMinProbability;
764        /// minimal number of objects
765        int mTermMinObjects;
766        /// maximal contribution per ray
767        float mTermMaxRayContribution;
768        /// maximal acceptable cost ratio
769        float mTermMaxCostRatio;
770        /// tolerance value indicating how often the max cost ratio can be failed
771        int mTermMissTolerance;
772
773
774        //-- global criteria
775
776        float mTermMinGlobalCostRatio;
777        int mTermGlobalCostMissTolerance;
778        int mGlobalCostMisses;
779
780        /// maximal number of view cells
781        int mTermMaxLeaves;
782        /// maximal tree memory
783        float mMaxMemory;
784        /// the tree is out of memory
785        bool mOutOfMemory;
786
787
788        //-- split heuristics based parameters
789       
790        bool mUseCostHeuristics;
791        /// balancing factor for PVS criterium
792        float mCtDivCi;
793        /// if only driving axis should be used for split
794        bool mOnlyDrivingAxis;
795       
796        /// current time stamp (used for keeping split history)
797        int mTimeStamp;
798        // if rays should be stored in leaves
799        bool mStoreRays;
800
801        /// epsilon for geometric comparisons
802        float mEpsilon;
803
804        /// subdivision stats output file
805        ofstream  mSubdivisionStats;
806        /// keeps track of cost during subdivision
807        float mTotalCost;
808        /// keeps track of overall pvs size during subdivision
809        int mTotalPvsSize;
810        /// number of currenly generated view cells
811        int mCreatedLeaves;
812
813        /// represents min and max band for sweep
814        float mSplitBorder;
815
816        /// weight between  render cost decrease and node render cost
817        float mRenderCostDecreaseWeight;
818
819        /// stores the kd node intersectables used for pvs
820        KdIntersectableMap mKdIntersectables;
821
822
823private:
824
825        bool mCopyFromKdTree;
826};
827
828
829}
830
831#endif
Note: See TracBrowser for help on using the repository browser.