source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h @ 648

Revision 648, 20.8 KB checked in by mattausch, 19 years ago (diff)

removed problems with bsp due to polygons equal to scene box faces. removing
this polyogns in a preprocessing step. also using this for vsp bsp tree, because it
is generally a good thing.

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        /** Collects rays stored in the leaves.
313        */
314        void CollectRays(VssRayContainer &rays);
315
316
317        ViewCellsTree *mViewCellsTree;
318
319
320protected:
321
322        // --------------------------------------------------------------
323        // For sorting objects
324        // --------------------------------------------------------------
325        struct SortableEntry
326        {
327                enum EType
328                {
329                        ERayMin,
330                        ERayMax
331                };
332
333                int type;
334                float value;
335                VssRay *ray;
336 
337                SortableEntry() {}
338                SortableEntry(const int t, const float v, VssRay *r):type(t),
339                                          value(v), ray(r)
340                {
341                }
342               
343                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
344                {
345                        return a.value < b.value;
346                }
347        };
348
349        /** faster evaluation of split plane cost for kd axis aligned cells.
350        */
351        float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
352                                                                   const AxisAlignedBox3 &box,
353                                                                   const int axis,
354                                                                   const float &position,
355                                                                   float &pFront,
356                                                                   float &pBack) const;
357
358        /** Returns view cell corresponding to
359                the invalid view space. If it does not exist, it is created.
360        */
361        BspViewCell *GetOrCreateOutOfBoundsCell();
362
363        /** Collapses the tree with respect to the view cell partition,
364                i.e. leaves having the same view cell are collapsed.
365                @param node the root of the subtree to be collapsed
366                @param collapsed returns the number of collapsed nodes
367                @returns node of type leaf if the node could be collapsed,
368                this node otherwise
369        */
370        BspNode *CollapseTree(BspNode *node, int &collapsed);
371
372        /** Helper function revalidating the view cell leaf list after merge.
373        */
374        void RepairViewCellsLeafLists();
375
376        /** Evaluates tree stats in the BSP tree leafs.
377        */
378        void EvaluateLeafStats(const VspBspTraversalData &data);
379
380        /** Subdivides node with respect to the traversal data.
381            @param tStack current traversal stack
382                @param tData traversal data also holding node to be subdivided
383                @returns new root of the subtree
384        */
385        BspNode *Subdivide(VspBspTraversalQueue &tStack,
386                                           VspBspTraversalData &tData);
387
388        /** Constructs the tree from the given traversal data.
389                @param polys stores set of polygons on which subdivision may be based
390                @param rays storesset of rays on which subdivision may be based
391        */
392        void Construct(const PolygonContainer &polys, RayInfoContainer *rays);
393
394        /** Selects the best possible splitting plane.
395                @param plane returns the split plane
396                @param leaf the leaf to be split
397                @param polys the polygon list on which the split decition is based
398                @param rays ray container on which selection may be based
399                @note the polygons can be reordered in the process
400                @returns true if the cost of the split is under maxCostRatio
401
402        */
403        bool SelectPlane(Plane3 &plane,
404                                         BspLeaf *leaf,
405                                         VspBspTraversalData &data,
406                                         VspBspTraversalData &frontData,
407                                         VspBspTraversalData &backData,
408                                         int &splitAxis);
409       
410        /** Strategies where the effect of the split plane is tested
411            on all input rays.
412
413                @returns the cost of the candidate split plane
414        */
415        float EvalSplitPlaneCost(const Plane3 &candidatePlane,
416                                                         const VspBspTraversalData &data,
417                                                         BspNodeGeometry &geomFront,
418                                                         BspNodeGeometry &geomBack,
419                                                         float &pFront,
420                                                         float &pBack) const;
421
422        /** Subdivide leaf.
423                @param leaf the leaf to be subdivided
424               
425                @param polys the polygons to be split
426                @param frontPolys returns the polygons in front of the split plane
427                @param backPolys returns the polygons in the back of the split plane
428               
429                @param rays the polygons to be filtered
430                @param frontRays returns the polygons in front of the split plane
431                @param backRays returns the polygons in the back of the split plane
432
433                @returns the root of the subdivision
434        */
435
436        BspNode *SubdivideNode(VspBspTraversalData &tData,
437                                                   VspBspTraversalData &frontData,
438                                                   VspBspTraversalData &backData,
439                                                   PolygonContainer &coincident);
440
441        /** Extracts the meshes of the objects and adds them to polygons.
442                Adds object aabb to the aabb of the tree.
443                @param maxPolys the maximal number of objects to be stored as polygons
444                @returns the number of polygons
445        */
446        int AddToPolygonSoup(const ObjectContainer &objects,
447                                                 PolygonContainer &polys,
448                                                 int maxObjects = 0);
449
450        /** Extracts the meshes of the view cells and and adds them to polygons.
451                Adds view cell aabb to the aabb of the tree.
452                @param maxPolys the maximal number of objects to be stored as polygons
453                @returns the number of polygons
454        */
455        int AddToPolygonSoup(const ViewCellContainer &viewCells,
456                                                 PolygonContainer &polys,
457                                                 int maxObjects = 0);
458
459        /** Extract polygons of this mesh and add to polygon container.
460                @param mesh the mesh that drives the polygon construction
461                @param parent the parent intersectable this polygon is constructed from
462                @returns number of polygons
463        */
464        int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);
465
466        /** Selects an axis aligned for the next split.
467                @returns cost for this split
468        */
469        float SelectAxisAlignedPlane(Plane3 &plane,
470                                                                 const VspBspTraversalData &tData,
471                                                                 int &axis,
472                                                                 BspNodeGeometry **frontGeom,
473                                                                 BspNodeGeometry **backGeom,
474                                                                 float &pFront,
475                                                                 float &pBack,
476                                                                 const bool useKdSplit);
477
478        /** Sorts split candidates for surface area heuristics for axis aligned splits.
479                @param polys the input for choosing split candidates
480                @param axis the current split axis
481                @param splitCandidates returns sorted list of split candidates
482        */
483        void SortSplitCandidates(const RayInfoContainer &rays, const int axis);
484
485        /** Computes best cost for axis aligned planes.
486        */
487        float BestCostRatioHeuristics(const RayInfoContainer &rays,
488                                                                  const AxisAlignedBox3 &box,
489                                                                  const int pvsSize,
490                                                                  const int &axis,
491                                                                  float &position);
492
493        /** Selects an axis aligned split plane.
494                @Returns true if split is valied
495        */
496        bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;
497
498        /** Subdivides the rays into front and back rays according to the split plane.
499               
500                @param plane the split plane
501                @param rays contains the rays to be split. The rays are
502                           distributed into front and back rays.
503                @param frontRays returns rays on the front side of the plane
504                @param backRays returns rays on the back side of the plane
505               
506                @returns the number of splits
507        */
508        int SplitRays(const Plane3 &plane,
509                                  RayInfoContainer &rays,
510                              RayInfoContainer &frontRays,
511                                  RayInfoContainer &backRays) const;
512
513
514        /** Extracts the split planes representing the space bounded by node n.
515        */
516        void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;
517
518        /** Adds the object to the pvs of the front and back leaf with a given classification.
519
520                @param obj the object to be added
521                @param cf the ray classification regarding the split plane
522                @param frontPvs returns the PVS of the front partition
523                @param backPvs returns the PVS of the back partition
524       
525        */
526        void AddObjToPvs(Intersectable *obj,
527                                         const int cf,
528                                         int &frontPvs,
529                                         int &backPvs,
530                                         int &totalPvs) const;
531       
532        /** Computes PVS size induced by the rays.
533        */
534        int ComputePvsSize(const RayInfoContainer &rays) const;
535
536        /** Returns true if tree can be terminated.
537        */
538        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
539
540        /** Computes accumulated ray lenght of this rays.
541        */
542        float AccumulatedRayLength(const RayInfoContainer &rays) const;
543
544        /** Splits polygons with respect to the split plane.
545
546                @param plane the split plane
547                @param polys the polygons to be split. the polygons are consumed and
548                           distributed to the containers frontPolys, backPolys, coincident.
549                @param frontPolys returns the polygons in the front of the split plane
550                @param backPolys returns the polygons in the back of the split plane
551                @param coincident returns the polygons coincident to the split plane
552
553                @returns the number of splits   
554        */
555        int SplitPolygons(const Plane3 &plane,
556                                          PolygonContainer &polys,
557                                          PolygonContainer &frontPolys,
558                                          PolygonContainer &backPolys,
559                                          PolygonContainer &coincident) const;
560
561        /** Adds ray sample contributions to the PVS.
562                @param sampleContributions the number contributions of the samples
563                @param contributingSampels the number of contributing rays
564               
565        */
566        void AddToPvs(BspLeaf *leaf,
567                                  const RayInfoContainer &rays,
568                                  float &sampleContributions,
569                                  int &contributingSamples);
570
571
572
573
574
575       
576        /** Take 3 ray endpoints, where two are minimum and one a maximum
577                point or the other way round.
578        */
579        Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;
580
581        /** Take plane normal as plane normal and the midpoint of the ray.
582                PROBLEM: does not resemble any point where visibility is
583                likely to change
584        */
585        Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
586
587        /** Fit the plane between the two lines so that the plane
588                has equal shortest distance to both lines.
589        */
590        Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
591 
592        /** Collects candidates for merging.
593                @param leaves the leaves to be merged
594                @returns number of leaves in queue
595        */
596        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
597
598        /** Collects candidates for the merge in the merge queue.
599                @returns number of leaves in queue
600        */
601        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
602       
603        /** Preprocesses polygons and throws out all polygons which are coincident to
604                the view space box faces (they can be problematic).
605        */
606        void PreprocessPolygons(PolygonContainer &polys);
607       
608        /** Propagates valid flag up the tree.
609        */
610        void PropagateUpValidity(BspNode *node);
611
612        /** Writes the node to disk
613                @note: should be implemented as visitor
614        */
615        void ExportNode(BspNode *node, ofstream &stream);
616
617        /** Returns estimated memory usage of tree.
618        */
619        //float GetMemUsage(const VspBspTraversalQueue &tstack) const;
620        float GetMemUsage() const;
621
622
623
624        /// Pointer to the root of the tree
625        BspNode *mRoot;
626               
627        BspTreeStatistics mBspStats;
628
629        /// Strategies for choosing next split plane.
630        enum {NO_STRATEGY = 0,
631                  RANDOM_POLYGON = 1,
632                  AXIS_ALIGNED = 2,
633                  LEAST_RAY_SPLITS = 256,
634                  BALANCED_RAYS = 512,
635                  PVS = 1024
636                };
637
638        /// box around the whole view domain
639        AxisAlignedBox3 mBox;
640
641        bool mUseCostHeuristics;
642
643        /// minimal number of rays before subdivision termination
644        int mTermMinRays;
645        /// maximal possible depth
646        int mTermMaxDepth;
647        /// mininum probability
648        float mTermMinProbability;
649        /// mininum PVS
650        int mTermMinPvs;
651        /// maximal contribution per ray
652        float mTermMaxRayContribution;
653        /// minimal accumulated ray length
654        float mTermMinAccRayLength;
655
656        //HACK
657        int mTermMinPolygons;
658
659        //-- termination criteria for axis aligned split
660
661        /// minimal number of rays for axis aligned split
662        int mTermMinRaysForAxisAligned;
663        // max ray contribution
664        float mTermMaxRayContriForAxisAligned;
665
666        /// strategy to get the best split plane
667        int mSplitPlaneStrategy;
668        /// number of candidates evaluated for the next split plane
669        int mMaxPolyCandidates;
670        /// number of candidates for split planes evaluated using the rays
671        int mMaxRayCandidates;
672        /// balancing factor for PVS criterium
673        float mCtDivCi;
674
675        //-- axis aligned split criteria
676        float mAxisAlignedCtDivCi;
677        /// spezifies the split border of the axis aligned split
678        float mAxisAlignedSplitBorder;
679
680        /// maximal acceptable cost ratio
681        float mTermMaxCostRatio;
682        /// tolerance value indicating how often the max cost ratio can be failed
683        int mTermMissTolerance;
684
685        //-- factors guiding the split plane heuristics
686        float mLeastRaySplitsFactor;
687        float mBalancedRaysFactor;
688        float mPvsFactor;
689
690        /// if area or volume should be used for PVS heuristics
691        bool mUseAreaForPvs;
692        /// tolerance for polygon split
693        float mEpsilon;
694        /// maximal number of test rays used to evaluate candidate split plane
695        int mMaxTests;
696        /// normalizes different bsp split plane criteria
697        float mCostNormalizer;
698        /// maximal number of view cells
699        int mMaxViewCells;
700       
701        ofstream  mSubdivisionStats;
702
703        // if rays should be stored in leaves
704        bool mStoreRays;
705       
706        /// if only driving axis should be used for split
707        bool mOnlyDrivingAxis;
708
709        ViewCellsManager *mViewCellsManager;
710
711        vector<SortableEntry> *mSplitCandidates;
712
713       
714        float mRenderCostWeight;
715        /// View cell corresponding to the space outside the valid view space
716        BspViewCell *mOutOfBoundsCell;
717
718        /// maximal tree memory
719        float mMaxMemory;
720        /// the tree is out of memory
721        bool mOutOfMemory;
722       
723        float mTotalCost;
724        int mTotalPvsSize;
725
726        //int mSplits;
727
728        ofstream mSubdivsionStats;
729
730        bool mUseRandomAxis;
731
732        bool mUsePolygonSplitIfAvailable;
733
734        int mTimeStamp;
735
736        int mCreatedViewCells;
737
738private:
739
740
741        static const float sLeastRaySplitsTable[5];
742        /** Evaluates split plane classification with respect to the plane's
743                contribution for balanced rays.
744        */
745        static const float sBalancedRaysTable[5];
746
747        /// Generates unique ids for PVS criterium
748        static void GenerateUniqueIdsForPvs();
749
750        //-- unique ids for PVS criterium
751        static int sFrontId;
752        static int sBackId;
753        static int sFrontAndBackId;
754};
755
756
757
758
759#endif
Note: See TracBrowser for help on using the repository browser.