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

Revision 2176, 25.4 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h

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