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

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