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

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