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

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