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

Revision 503, 22.1 KB checked in by mattausch, 19 years ago (diff)

added mesh creation function

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