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

Revision 2695, 25.4 KB checked in by mattausch, 16 years ago (diff)

debug version: problematic view points for vienna detected

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