source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h @ 551

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