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

Revision 1145, 25.6 KB checked in by mattausch, 18 years ago (diff)

vsposp debug version

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