source: obsolete/trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h @ 612

Revision 612, 20.5 KB checked in by mattausch, 19 years ago (diff)

really last checkin before svn change

Line 
1#ifndef _VspBspTree_H__
2#define _VspBspTree_H__
3
4#include "Mesh.h"
5#include "Containers.h"
6#include "Polygon3.h"
7#include <stack>
8#include "Statistics.h"
9#include "VssRay.h"
10#include "RayInfo.h"
11#include "ViewCellBsp.h"
12
13class ViewCell;
14//class BspViewCell;
15class Plane3;
16class VspBspTree; 
17class BspInterior;
18class BspNode;
19class AxisAlignedBox3;
20class Ray;
21class ViewCellsStatistics;
22class ViewCellsManager;
23class MergeCandidate;
24class Beam;
25class ViewCellsTree;
26
27
28struct BspRay;
29
30#define OCTREE_HACK 0
31/**
32        This is a view space partitioning specialised BSPtree. 
33        There are no polygon splits, but we split the sample rays.
34        The candidates for the next split plane are evaluated only
35        by checking the sampled visibility information.
36        The polygons are employed merely as candidates for the next split planes.
37*/
38class VspBspTree
39{
40        friend class ViewCellsParseHandlers;
41        friend class VspBspViewCellsManager;
42public:
43       
44        /** Additional data which is passed down the BSP tree during traversal.
45        */
46        struct VspBspTraversalData
47        { 
48                /// the current node
49                BspNode *mNode;
50                /// polygonal data for splitting
51                PolygonContainer *mPolygons;
52                /// current depth
53                int mDepth;
54                /// rays piercing this node
55                RayInfoContainer *mRays;
56                /// the probability that this node contains view point
57                float mProbability;
58                /// geometry of node as induced by planes
59                BspNodeGeometry *mGeometry;
60                /// pvs size
61                int mPvs;
62                /// how often this branch has missed the max-cost ratio
63                int mMaxCostMisses;
64                /// if this node is a kd-node (i.e., boundaries are axis aligned
65                bool mIsKdNode;
66#if OCTREE_HACK // OCTREE HACK
67                int mAxis;
68#endif
69                /// bounding box of current view space.
70                ///AxisAlignedBox3 mBbox;
71               
72                /** Returns average ray contribution.
73                */
74                float GetAvgRayContribution() const
75                {
76                        return (float)mPvs / ((float)mRays->size() + Limits::Small);
77                }
78
79
80                VspBspTraversalData():
81                mNode(NULL),
82                mPolygons(NULL),
83                mDepth(0),
84                mRays(NULL),
85                mPvs(0),
86                mProbability(0.0),
87                mGeometry(NULL),
88                mMaxCostMisses(0),
89                mIsKdNode(false)
90                {}
91               
92                VspBspTraversalData(BspNode *node,
93                                                        PolygonContainer *polys,
94                                                        const int depth,
95                                                        RayInfoContainer *rays,
96                                                        const int pvs,
97                                                        const float p,
98                                                        BspNodeGeometry *geom):
99                mNode(node),
100                mPolygons(polys),
101                mDepth(depth),
102                mRays(rays),
103                mPvs(pvs),
104                mProbability(p),
105                mGeometry(geom),
106                mMaxCostMisses(0),
107                mIsKdNode(false)
108                {}
109
110                VspBspTraversalData(PolygonContainer *polys,
111                                                        const int depth,
112                                                        RayInfoContainer *rays,
113                                                        BspNodeGeometry *geom):
114                mNode(NULL),
115                mPolygons(polys),
116                mDepth(depth),
117                mRays(rays),
118                mPvs(0),
119                mProbability(0),
120                mGeometry(geom),
121                mMaxCostMisses(0),
122                mIsKdNode(false)
123                {}
124
125                /** Returns cost of the traversal data.
126                */
127                float GetCost() const
128                {
129#if 1
130                        return mPvs * mProbability;
131#endif
132#if 0
133                        return (float) (-mDepth); // for regular grid
134#endif
135#if 0
136                        return (float)(mPvs * (int)mRays->size());
137#endif
138#if 0
139                        return (float)mPvs;
140#endif
141#if 0
142                        return mProbabiliy * (float)mRays->size();
143#endif
144                }
145
146                // deletes contents and sets them to NULL
147                void Clear()
148                {
149                        DEL_PTR(mPolygons);
150                        DEL_PTR(mRays);
151                        DEL_PTR(mGeometry);
152                }
153
154                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
155                {
156                        return a.GetCost() < b.GetCost();
157                }
158    };
159       
160        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
161        //typedef std::stack<VspBspTraversalData> VspBspTraversalQueue;
162
163        /** Default constructor creating an empty tree.
164        */
165        VspBspTree();
166
167        /** Default destructor.
168        */
169        ~VspBspTree();
170
171        /** Returns BSP Tree statistics.
172        */
173        const BspTreeStatistics &GetStatistics() const;
174 
175
176        /** Constructs the tree from a given set of rays.
177                @param sampleRays the set of sample rays the construction is based on
178                @param viewCells if not NULL, new view cells are
179                created in the leafs and stored in the container
180        */
181        void Construct(const VssRayContainer &sampleRays,
182                                   AxisAlignedBox3 *forcedBoundingBox);
183
184        /** Returns list of BSP leaves with pvs smaller than
185                a certain threshold.
186                @param onlyUnmailed if only the unmailed leaves should be considered
187                @param maxPvs the maximal pvs (-1 means unlimited)
188        */
189        void CollectLeaves(vector<BspLeaf *> &leaves,
190                                           const bool onlyUnmailed = false,
191                                           const int maxPvs = -1) const;
192
193        /** Returns box which bounds the whole tree.
194        */
195        AxisAlignedBox3 GetBoundingBox()const;
196
197        /** Returns root of BSP tree.
198        */
199        BspNode *GetRoot() const;
200
201        /** Collects the leaf view cells of the tree
202                @param viewCells returns the view cells
203        */
204        void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;
205
206        /** A ray is cast possible intersecting the tree.
207                @param the ray that is cast.
208                @returns the number of intersections with objects stored in the tree.
209        */
210        int CastRay(Ray &ray);
211
212        /// bsp tree construction types
213        enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};
214
215        /** finds neighbouring leaves of this tree node.
216        */
217        int FindNeighbors(BspNode *n,
218                                          vector<BspLeaf *> &neighbors,
219                                          const bool onlyUnmailed) const;
220
221        /** Constructs geometry associated with the half space intersections
222                leading to this node.
223        */
224        void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
225       
226        /** Construct geometry of view cell.
227        */
228        void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;
229
230        /** Returns random leaf of BSP tree.
231                @param halfspace defines the halfspace from which the leaf is taken.
232        */
233        BspLeaf *GetRandomLeaf(const Plane3 &halfspace);
234
235        /** Returns random leaf of BSP tree.
236                @param onlyUnmailed if only unmailed leaves should be returned.
237        */
238        BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
239
240        /** Returns epsilon of this tree.
241        */
242        float GetEpsilon() const;
243
244        /** Casts line segment into the tree.
245                @param origin the origin of the line segment
246                @param termination the end point of the line segment
247                @returns view cells intersecting the line segment.
248        */
249    int CastLineSegment(const Vector3 &origin,
250                                                const Vector3 &termination,
251                                                ViewCellContainer &viewcells);
252
253               
254        /** Sets pointer to view cells manager.
255        */
256        void SetViewCellsManager(ViewCellsManager *vcm);
257
258        /** Returns distance from node 1 to node 2.
259        */
260        int TreeDistance(BspNode *n1, BspNode *n2) const;
261
262        /** Collapses the tree with respect to the view cell partition.
263                @returns number of collapsed nodes
264        */
265        int CollapseTree();
266
267        /** Returns view cell the current point is located in.
268        */
269        ViewCell *GetViewCell(const Vector3 &point);
270
271
272        /** Returns true if this view point is in a valid view space,
273                false otherwise.
274        */
275        bool ViewPointValid(const Vector3 &viewPoint) const;
276
277        /** Returns view cell corresponding to
278                the invalid view space.
279        */
280        BspViewCell *GetOutOfBoundsCell();
281
282        /** Writes tree to output stream
283        */
284        bool Export(ofstream &stream);
285
286        /** Casts beam, i.e. a 5D frustum of rays, into tree.
287                Tests conservative using the bounding box of the nodes.
288                @returns number of view cells it intersected
289        */
290        int CastBeam(Beam &beam);
291
292        void CollectViewCells(BspNode *root,
293                                                  bool onlyValid,
294                                                  ViewCellContainer &viewCells,
295                                                  bool onlyUnmailed = false) const;
296
297       
298        int FindApproximateNeighbors(BspNode *n,
299                                                             vector<BspLeaf *> &neighbors,
300                                                                 const bool onlyUnmailed) const;
301
302        /** Checks if tree validity-flags are right
303                with respect to view cell valitiy.
304                If not, marks subtree as invalid.
305        */
306        void ValidateTree();
307
308        /** Invalid view cells are added to the unbounded space
309        */
310        void CollapseViewCells();
311
312        ViewCellsTree *mViewCellsTree;
313protected:
314
315        // --------------------------------------------------------------
316        // For sorting objects
317        // --------------------------------------------------------------
318        struct SortableEntry
319        {
320                enum EType
321                {
322                        ERayMin,
323                        ERayMax
324                };
325
326                int type;
327                float value;
328                VssRay *ray;
329 
330                SortableEntry() {}
331                SortableEntry(const int t, const float v, VssRay *r):type(t),
332                                          value(v), ray(r)
333                {
334                }
335               
336                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
337                {
338                        return a.value < b.value;
339                }
340        };
341
342        /** faster evaluation of split plane cost for kd axis aligned cells.
343        */
344        float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
345                                                                   const AxisAlignedBox3 &box,
346                                                                   const int axis,
347                                                                   const float &position,
348                                                                   float &pFront,
349                                                                   float &pBack) const;
350
351        /** Returns view cell corresponding to
352                the invalid view space. If it does not exist, it is created.
353        */
354        BspViewCell *GetOrCreateOutOfBoundsCell();
355
356        /** Collapses the tree with respect to the view cell partition,
357                i.e. leaves having the same view cell are collapsed.
358                @param node the root of the subtree to be collapsed
359                @param collapsed returns the number of collapsed nodes
360                @returns node of type leaf if the node could be collapsed,
361                this node otherwise
362        */
363        BspNode *CollapseTree(BspNode *node, int &collapsed);
364
365        /** Helper function revalidating the view cell leaf list after merge.
366        */
367        void RepairViewCellsLeafLists();
368
369        /** Evaluates tree stats in the BSP tree leafs.
370        */
371        void EvaluateLeafStats(const VspBspTraversalData &data);
372
373        /** Subdivides node with respect to the traversal data.
374            @param tStack current traversal stack
375                @param tData traversal data also holding node to be subdivided
376                @returns new root of the subtree
377        */
378        BspNode *Subdivide(VspBspTraversalQueue &tStack,
379                                           VspBspTraversalData &tData);
380
381        /** Constructs the tree from the given traversal data.
382                @param polys stores set of polygons on which subdivision may be based
383                @param rays storesset of rays on which subdivision may be based
384        */
385        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
386
387        /** Selects the best possible splitting plane.
388                @param plane returns the split plane
389                @param leaf the leaf to be split
390                @param polys the polygon list on which the split decition is based
391                @param rays ray container on which selection may be based
392                @note the polygons can be reordered in the process
393                @returns true if the cost of the split is under maxCostRatio
394
395        */
396        bool SelectPlane(Plane3 &plane,
397                                         BspLeaf *leaf,
398                                         VspBspTraversalData &data,
399                                         VspBspTraversalData &frontData,
400                                         VspBspTraversalData &backData,
401                                         int &splitAxis);
402       
403        /** Strategies where the effect of the split plane is tested
404            on all input rays.
405
406                @returns the cost of the candidate split plane
407        */
408        float EvalSplitPlaneCost(const Plane3 &candidatePlane,
409                                                         const VspBspTraversalData &data,
410                                                         BspNodeGeometry &geomFront,
411                                                         BspNodeGeometry &geomBack,
412                                                         float &pFront,
413                                                         float &pBack) const;
414
415        /** Subdivide leaf.
416                @param leaf the leaf to be subdivided
417               
418                @param polys the polygons to be split
419                @param frontPolys returns the polygons in front of the split plane
420                @param backPolys returns the polygons in the back of the split plane
421               
422                @param rays the polygons to be filtered
423                @param frontRays returns the polygons in front of the split plane
424                @param backRays returns the polygons in the back of the split plane
425
426                @returns the root of the subdivision
427        */
428
429        BspNode *SubdivideNode(VspBspTraversalData &tData,
430                                                   VspBspTraversalData &frontData,
431                                                   VspBspTraversalData &backData,
432                                                   PolygonContainer &coincident);
433
434        /** Extracts the meshes of the objects and adds them to polygons.
435                Adds object aabb to the aabb of the tree.
436                @param maxPolys the maximal number of objects to be stored as polygons
437                @returns the number of polygons
438        */
439        int AddToPolygonSoup(const ObjectContainer &objects,
440                                                 PolygonContainer &polys,
441                                                 int maxObjects = 0);
442
443        /** Extracts the meshes of the view cells and and adds them to polygons.
444                Adds view cell aabb to the aabb of the tree.
445                @param maxPolys the maximal number of objects to be stored as polygons
446                @returns the number of polygons
447        */
448        int AddToPolygonSoup(const ViewCellContainer &viewCells,
449                                                 PolygonContainer &polys,
450                                                 int maxObjects = 0);
451
452        /** Extract polygons of this mesh and add to polygon container.
453                @param mesh the mesh that drives the polygon construction
454                @param parent the parent intersectable this polygon is constructed from
455                @returns number of polygons
456        */
457        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
458
459        /** Selects an axis aligned for the next split.
460                @returns cost for this split
461        */
462        float SelectAxisAlignedPlane(Plane3 &plane,
463                                                                 const VspBspTraversalData &tData,
464                                                                 int &axis,
465                                                                 BspNodeGeometry **frontGeom,
466                                                                 BspNodeGeometry **backGeom,
467                                                                 float &pFront,
468                                                                 float &pBack,
469                                                                 const bool useKdSplit);
470
471        /** Sorts split candidates for surface area heuristics for axis aligned splits.
472                @param polys the input for choosing split candidates
473                @param axis the current split axis
474                @param splitCandidates returns sorted list of split candidates
475        */
476        void SortSplitCandidates(const RayInfoContainer &rays, const int axis);
477
478        /** Computes best cost for axis aligned planes.
479        */
480        float BestCostRatioHeuristics(const RayInfoContainer &rays,
481                                                                  const AxisAlignedBox3 &box,
482                                                                  const int pvsSize,
483                                                                  const int &axis,
484                                                                  float &position);
485
486        /** Selects an axis aligned split plane.
487                @Returns true if split is valied
488        */
489        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
490
491        /** Subdivides the rays into front and back rays according to the split plane.
492               
493                @param plane the split plane
494                @param rays contains the rays to be split. The rays are
495                           distributed into front and back rays.
496                @param frontRays returns rays on the front side of the plane
497                @param backRays returns rays on the back side of the plane
498               
499                @returns the number of splits
500        */
501        int SplitRays(const Plane3 &plane,
502                                  RayInfoContainer &rays,
503                              RayInfoContainer &frontRays,
504                                  RayInfoContainer &backRays);
505
506
507        /** Extracts the split planes representing the space bounded by node n.
508        */
509        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
510
511        /** Adds the object to the pvs of the front and back leaf with a given classification.
512
513                @param obj the object to be added
514                @param cf the ray classification regarding the split plane
515                @param frontPvs returns the PVS of the front partition
516                @param backPvs returns the PVS of the back partition
517       
518        */
519        void AddObjToPvs(Intersectable *obj,
520                                         const int cf,
521                                         int &frontPvs,
522                                         int &backPvs,
523                                         int &totalPvs) const;
524       
525        /** Computes PVS size induced by the rays.
526        */
527        int ComputePvsSize(const RayInfoContainer &rays) const;
528
529        /** Returns true if tree can be terminated.
530        */
531        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
532
533        /** Computes accumulated ray lenght of this rays.
534        */
535        float AccumulatedRayLength(const RayInfoContainer &rays) const;
536
537        /** Splits polygons with respect to the split plane.
538
539                @param plane the split plane
540                @param polys the polygons to be split. the polygons are consumed and
541                           distributed to the containers frontPolys, backPolys, coincident.
542                @param frontPolys returns the polygons in the front of the split plane
543                @param backPolys returns the polygons in the back of the split plane
544                @param coincident returns the polygons coincident to the split plane
545
546                @returns the number of splits   
547        */
548        int SplitPolygons(const Plane3 &plane,
549                                          PolygonContainer &polys,
550                                          PolygonContainer &frontPolys,
551                                          PolygonContainer &backPolys,
552                                          PolygonContainer &coincident) const;
553
554        /** Adds ray sample contributions to the PVS.
555                @param sampleContributions the number contributions of the samples
556                @param contributingSampels the number of contributing rays
557               
558        */
559        void AddToPvs(BspLeaf *leaf,
560                                  const RayInfoContainer &rays,
561                                  float &sampleContributions,
562                                  int &contributingSamples);
563
564
565
566
567
568       
569        /** Take 3 ray endpoints, where two are minimum and one a maximum
570                point or the other way round.
571        */
572        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
573
574        /** Take plane normal as plane normal and the midpoint of the ray.
575                PROBLEM: does not resemble any point where visibility is
576                likely to change
577        */
578        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
579
580        /** Fit the plane between the two lines so that the plane
581                has equal shortest distance to both lines.
582        */
583        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
584 
585        /** Collects candidates for merging.
586                @param leaves the leaves to be merged
587                @returns number of leaves in queue
588        */
589        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
590
591        /** Collects candidates for the merge in the merge queue.
592                @returns number of leaves in queue
593        */
594        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
595       
596       
597       
598        /** Propagates valid flag up the tree.
599        */
600        void PropagateUpValidity(BspNode *node);
601
602        /** Writes the node to disk
603                @note: should be implemented as visitor
604        */
605        void ExportNode(BspNode *node, ofstream &stream);
606
607        /** Returns estimated memory usage of tree.
608        */
609        //float GetMemUsage(const VspBspTraversalQueue &tstack) const;
610        float GetMemUsage() const;
611
612
613
614        /// Pointer to the root of the tree
615        BspNode *mRoot;
616               
617        BspTreeStatistics mBspStats;
618
619        /// Strategies for choosing next split plane.
620        enum {NO_STRATEGY = 0,
621                  RANDOM_POLYGON = 1,
622                  AXIS_ALIGNED = 2,
623                  LEAST_RAY_SPLITS = 256,
624                  BALANCED_RAYS = 512,
625                  PVS = 1024
626                };
627
628        /// box around the whole view domain
629        AxisAlignedBox3 mBox;
630
631        bool mUseCostHeuristics;
632
633        /// minimal number of rays before subdivision termination
634        int mTermMinRays;
635        /// maximal possible depth
636        int mTermMaxDepth;
637        /// mininum probability
638        float mTermMinProbability;
639        /// mininum PVS
640        int mTermMinPvs;
641        /// maximal contribution per ray
642        float mTermMaxRayContribution;
643        /// minimal accumulated ray length
644        float mTermMinAccRayLength;
645
646        //HACK
647        int mTermMinPolygons;
648
649        //-- termination criteria for axis aligned split
650
651        /// minimal number of rays for axis aligned split
652        int mTermMinRaysForAxisAligned;
653        // max ray contribution
654        float mTermMaxRayContriForAxisAligned;
655
656        /// strategy to get the best split plane
657        int mSplitPlaneStrategy;
658        /// number of candidates evaluated for the next split plane
659        int mMaxPolyCandidates;
660        /// number of candidates for split planes evaluated using the rays
661        int mMaxRayCandidates;
662        /// balancing factor for PVS criterium
663        float mCtDivCi;
664
665        //-- axis aligned split criteria
666        float mAxisAlignedCtDivCi;
667        /// spezifies the split border of the axis aligned split
668        float mAxisAlignedSplitBorder;
669
670        /// maximal acceptable cost ratio
671        float mTermMaxCostRatio;
672        /// tolerance value indicating how often the max cost ratio can be failed
673        int mTermMissTolerance;
674
675        //-- factors guiding the split plane heuristics
676        float mLeastRaySplitsFactor;
677        float mBalancedRaysFactor;
678        float mPvsFactor;
679
680        /// if area or volume should be used for PVS heuristics
681        bool mUseAreaForPvs;
682        /// tolerance for polygon split
683        float mEpsilon;
684        /// maximal number of test rays used to evaluate candidate split plane
685        int mMaxTests;
686        /// normalizes different bsp split plane criteria
687        float mCostNormalizer;
688        /// maximal number of view cells
689        int mMaxViewCells;
690       
691        ofstream  mSubdivisionStats;
692
693        // if rays should be stored in leaves
694        bool mStoreRays;
695       
696        /// if only driving axis should be used for split
697        bool mOnlyDrivingAxis;
698
699        ViewCellsManager *mViewCellsManager;
700
701        vector<SortableEntry> *mSplitCandidates;
702
703       
704        float mRenderCostWeight;
705        /// View cell corresponding to the space outside the valid view space
706        BspViewCell *mOutOfBoundsCell;
707
708        /// maximal tree memory
709        float mMaxMemory;
710        /// the tree is out of memory
711        bool mOutOfMemory;
712       
713        float mTotalCost;
714        int mTotalPvsSize;
715
716        //int mSplits;
717
718        ofstream mSubdivsionStats;
719
720        bool mUseRandomAxis;
721
722        bool mUsePolygonSplitIfAvailable;
723
724        int mTimeStamp;
725
726        int mCreatedViewCells;
727
728private:
729
730
731        static const float sLeastRaySplitsTable[5];
732        /** Evaluates split plane classification with respect to the plane's
733                contribution for balanced rays.
734        */
735        static const float sBalancedRaysTable[5];
736
737        /// Generates unique ids for PVS criterium
738        static void GenerateUniqueIdsForPvs();
739
740        //-- unique ids for PVS criterium
741        static int sFrontId;
742        static int sBackId;
743        static int sFrontAndBackId;
744};
745
746
747
748
749#endif
Note: See TracBrowser for help on using the repository browser.