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

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