source: GTP/trunk/Lib/Vis/Preprocessing/src/VspKdTree.h @ 1012

Revision 1012, 20.3 KB checked in by mattausch, 18 years ago (diff)
Line 
1// ================================================================
2// $Id$
3// ****************************************************************
4//
5// Initial coding by
6/**
7   @author Jiri Bittner
8*/
9
10#ifndef __VSPKDTREE_H__
11#define __VSPKDTREE_H__
12
13// Standard headers
14#include <iomanip>
15#include <vector>
16#include <functional>
17#include <stack>
18
19
20// User headers
21#include "VssRay.h"
22#include "AxisAlignedBox3.h"
23
24
25#define USE_KDNODE_VECTORS 1
26#define _RSS_STATISTICS
27#define _RSS_TRAVERSAL_STATISTICS
28
29
30#include "Statistics.h"
31#include "Ray.h"
32
33#include "RayInfo.h"
34#include "Containers.h"
35#include "ViewCell.h"
36
37class VspKdLeaf;
38class ViewCellsManager;
39class ViewCellsStatistics;
40
41namespace GtpVisibilityPreprocessor {
42
43/**
44        Candidate for leaf merging based on priority.
45*/
46class VspKdMergeCandidate
47
48public:
49
50        VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
51
52        /** Computes PVS difference between the leaves.
53        */
54        //int ComputePvsDifference() const;
55
56        /** If this merge pair is still valid.
57        */
58        bool Valid() const;
59
60        /** Sets this merge candidate to be valid.
61        */
62        void SetValid();
63
64        friend bool operator<(const VspKdMergeCandidate &leafa, const VspKdMergeCandidate &leafb)
65        {
66                return leafb.GetMergeCost() < leafa.GetMergeCost();
67        }
68
69        void SetLeaf1(VspKdLeaf *l);
70        void SetLeaf2(VspKdLeaf *l);
71
72        VspKdLeaf *GetLeaf1();
73        VspKdLeaf *GetLeaf2();
74
75        /** Merge cost of this candidate pair.
76        */
77        float GetMergeCost() const;
78
79        /** Returns cost of leaf 1.
80        */
81        float GetLeaf1Cost() const;
82        /** Returns cost of leaf 2.
83        */
84        float GetLeaf2Cost() const;
85
86        /// maximal pvs size
87        static int sMaxPvsSize;
88        /// overall cost used to normalize cost ratio
89        static float sOverallCost;
90
91protected:
92       
93        /** Evaluates the merge costs of the leaves.
94        */
95        void EvalMergeCost();
96
97        int mLeaf1Id;
98        int mLeaf2Id;
99
100        float mMergeCost;
101       
102        VspKdLeaf *mLeaf1;
103        VspKdLeaf *mLeaf2;
104};
105
106
107
108/**
109        Static statistics for vsp kd-tree search
110*/
111class VspKdStatistics:  public StatisticsBase
112{
113public: 
114        // total number of nodes
115        int nodes;
116        // number of splits along each of the axes
117        int splits[3];
118        // totals number of rays
119        int rays;
120        // initial size of the pvs
121        int initialPvsSize;
122        // total number of query domains
123        int queryDomains;
124        // total number of ray references
125        int rayRefs;
126
127        // max depth nodes
128        int maxDepthNodes;
129        // max depth nodes
130        int minPvsNodes;
131        // nodes with minimum PVS
132        int minRaysNodes;
133        // max ray contribution nodes
134        int maxRayContribNodes;
135        // max depth nodes
136        int minSizeNodes;
137       
138        // max number of rays per node
139        int maxRayRefs;
140        // maximal PVS size / leaf
141        int maxPvsSize;
142
143        // max cost ratio
144        int maxCostNodes;
145
146        // number of dynamically added ray refs
147        int addedRayRefs;
148        // number of dynamically removed ray refs
149        int removedRayRefs;
150 
151        /// for average pvs
152        int accPvsSize;
153
154        /** Default constructor.
155        */
156        VspKdStatistics() {     Reset(); }
157        int Nodes() const { return nodes; }
158        int Interior() const { return nodes / 2; }
159        int Leaves() const { return (nodes / 2) + 1; }
160
161        void Reset()
162        {
163                nodes = 0;
164
165                for (int i=0; i<3; i++)
166                        splits[i] = 0;
167
168                rays = queryDomains = 0;
169                rayRefs = 0;
170               
171                maxDepthNodes = 0;
172                minPvsNodes = 0;
173                minRaysNodes = 0;
174                maxRayContribNodes = 0;
175                minSizeNodes = 0;
176                maxCostNodes = 0;
177
178                maxRayRefs = 0;
179                addedRayRefs = removedRayRefs = 0;
180               
181                initialPvsSize = 0;
182                maxPvsSize = 0;
183                accPvsSize = 0;
184        }
185
186        void Print(ostream &app) const;
187        friend ostream &operator<<(ostream &s, const VspKdStatistics &stat)
188        {
189            stat.Print(s);
190            return s;
191        } 
192};
193
194
195class VspKdInterior;
196
197
198/** Abstract superclass of Vsp-Kd-Tree nodes.
199*/
200class VspKdNode
201{
202public:
203
204        friend class VspKdTree;
205
206        enum {EInterior, EIntermediate, ELeaf};
207
208        /** Constructs new interior node from the parent node.
209        */
210        inline VspKdNode(VspKdNode *p);
211
212        /** Destroys this node and the subtree.
213        */
214        virtual ~VspKdNode();
215
216        /** Type of the node (Einterior or ELeaf)
217        */
218        virtual int Type() const = 0;
219 
220        /** Returns true if this node is a leaf.
221        */
222        bool IsLeaf() const;
223       
224        /** Prints node stats.
225        */
226        virtual void Print(ostream &s) const = 0;
227
228        /** Returns time needed to access this node.
229                @NOTE: don't really know how it is used!
230        */
231        virtual int GetAccessTime();
232
233        /** Returns parent node.
234        */
235        VspKdNode *GetParent() const;
236
237        /** Sets parent node.
238        */
239        void SetParent(VspKdNode *p);
240
241protected:
242        /////////////////////////////////
243        // The actual data goes here
244 
245        /// link to the parent
246        VspKdNode *mParent;
247
248        enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z};
249 
250        /// splitting axis
251        char mAxis;
252       
253        /// depth
254        unsigned char mDepth;
255};
256
257// --------------------------------------------------------------
258// KD-tree node - interior node
259// --------------------------------------------------------------
260class VspKdInterior: public VspKdNode
261{
262public:
263        friend class VspKdTree;
264
265        /** Constructs new interior node from parent node.
266        */
267        VspKdInterior(VspKdInterior *p);
268                       
269        virtual int GetAccessTime();
270       
271        virtual int Type() const;
272 
273        virtual ~VspKdInterior();
274   
275        virtual void Print(ostream &s) const;
276
277        /** Returns back child.
278        */
279        VspKdNode *GetBack() const;
280        /** Returns front child.
281        */
282        VspKdNode *GetFront() const;
283
284protected:
285
286        /** Sets pointers to back child and front child.
287        */
288        void SetupChildLinks(VspKdNode *b, VspKdNode *f);
289        /** Replaces the pointer to oldChild with a pointer to newChild.
290        */
291        void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild);
292        /** Computes intersection of the ray with the node boundaries.
293        */
294        int ComputeRayIntersection(const RayInfo &rayData, float &t);
295
296        // plane in local modelling coordinates
297        float mPosition;
298
299        // pointers to children
300        VspKdNode *mBack;
301        VspKdNode *mFront;
302
303        // the bbox of the node
304        AxisAlignedBox3 mBox;
305
306        // data for caching
307        long mAccesses;
308        long mLastAccessTime;
309};
310
311
312/**
313        Node type just before leaf holding abitrary split plane
314*/
315class VspKdIntermediate: public VspKdNode
316{
317public:
318        friend class VspKdTree;
319
320        /** Constructs new interior node from parent node.
321        */
322        VspKdIntermediate(VspKdInterior *p);
323                       
324        //virtual int GetAccessTime();
325       
326        virtual int Type() const;
327 
328        virtual ~VspKdIntermediate();
329   
330        virtual void Print(ostream &s) const;
331
332        /** Returns back child.
333        */
334        inline VspKdLeaf *GetBack() const;
335        /** Returns front child.
336        */
337        inline VspKdLeaf *GetFront() const;
338
339protected:
340
341        /** Sets pointers to back child and front child.
342        */
343        void SetupChildLinks(VspKdLeaf *b, VspKdLeaf *f);
344        /** Computes intersection of the ray with the node boundaries.
345        */
346        int ComputeRayIntersection(const RayInfo &rayData, float &t);
347
348        // plane in local modelling coordinates
349        Plane3 mSplitPlane;
350
351        // pointers to children
352        VspKdLeaf *mBack;
353        VspKdLeaf *mFront;
354
355        // the bbox of the node
356        AxisAlignedBox3 mBox;
357
358        // data for caching
359        long mAccesses;
360        long mLastAccessTime;
361};
362
363// --------------------------------------------------------------
364// KD-tree node - leaf node
365// --------------------------------------------------------------
366class VspKdLeaf: public VspKdNode
367{
368public:
369
370        friend class VspKdTree;
371
372        /** Constructs leaf from parent node.
373                @param p the parent node
374                @param nRays preallocates memory to store this number of rays
375                @parma maxMisses how many times the max cost ratio was missed on the path to the leaf
376        */
377        VspKdLeaf(VspKdNode *p, const int nRays, const int maxCostMisses = 0);
378       
379        virtual ~VspKdLeaf();
380
381        virtual int Type() const; 
382
383        virtual void Print(ostream &s) const;
384 
385        /** Adds a ray to the leaf ray container.
386        */
387        void AddRay(const RayInfo &data);
388        /** Returns size of the leaf PVS as induced by the rays
389                @note returns precomputed PVS size, which may not be valid
390                anymore. Run UpdatePvsSize to get a valid PVS.
391        */
392        int GetPvsSize() const;
393
394        /** If PVS is not valid, this function recomputes the leaf
395                PVS as induced by the rays.
396        */
397        void UpdatePvsSize();
398
399        /** Returns stored rays.
400        */
401        RayInfoContainer &GetRays();
402
403        /** Returns rays into this ray container.
404        */
405        void GetRays(VssRayContainer &rays);
406        /** Returns average contribution of a ray to the PVS
407        */
408        inline float GetAvgRayContribution() const;
409        /** Returns square of average contribution of a ray.
410        */
411        inline float GetSqrRayContribution() const;
412
413        /** Extracts PVS from ray set.
414        */
415        void ExtractPvs(ObjectContainer &objects) const;
416
417        //-- mailing options
418        void Mail();
419
420        bool Mailed() const;
421 
422        /** Returns true if mail equals the leaf mail box.
423        */
424        bool Mailed(const int mail) const;
425
426        void SetViewCell(VspKdViewCell *viewCell);
427
428        /** Returns mail box of this leaf.
429        */
430        int GetMailbox() const;
431
432        /** Returns view cell associated with this leaf.
433        */
434        VspKdViewCell *GetViewCell();
435
436        /** Returns number of times the max cost ratio was missed until
437                this leaf.
438        */
439        int GetMaxCostMisses();
440
441        ////////////////////////////////////////////
442       
443        static void NewMail();
444        static int sMailId;
445
446        ObjectPvs *mPvs;
447        float mVolume;
448
449protected:
450
451        /** Manually sets PVS size.
452                @param s the PVS size
453        */
454        void SetPvsSize(const int s);
455
456        int mMailbox;
457 
458        /// rays intersecting this leaf.
459        RayInfoContainer mRays;
460        /// true if mPvsSize is valid => PVS does not have to be updated
461        bool mValidPvs;
462        /// the view cell associated with this leaf
463        VspKdViewCell *mViewCell;
464        /// number of times the max cost ratio was missed on the way to the leaf.
465        int mMaxCostMisses;
466
467//private:
468        /// stores PVS size so we have to evaluate PVS size only once
469        int mPvsSize;
470};
471
472
473// ---------------------------------------------------------------
474// Main LSDS search class
475// ---------------------------------------------------------------
476class VspKdTree
477{
478        // --------------------------------------------------------------
479        // For sorting rays
480        // -------------------------------------------------------------
481        struct SortableEntry
482        {
483                enum EType
484                {
485                        ERayMin,
486                        ERayMax
487                };
488
489                int type;
490                float value;
491                VssRay *ray;
492 
493                SortableEntry() {}
494                SortableEntry(const int t, const float v, VssRay *r): type(t),
495                                          value(v), ray(r)
496                {
497                }
498               
499                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
500                {
501                        return a.value < b.value;
502                }
503        };
504
505        struct TraversalData
506        { 
507                VspKdNode *mNode;
508                AxisAlignedBox3 mBox;
509                //TODO PolygonContainer *mPolys;
510
511                int mDepth;
512                //float mPriority;
513       
514                TraversalData() {}
515
516                TraversalData(VspKdNode *n, const float p):
517                mNode(n)//, mPriority(p)
518                {}
519
520                TraversalData(VspKdNode *n,     const AxisAlignedBox3 &b, const int d):
521                mNode(n), mBox(b), mDepth(d) {}
522   
523                // comparator for the priority queue
524                /*struct less_priority : public binary_function<const TraversalData, const TraversalData, bool>
525                {
526                        bool operator()(const TraversalData a, const TraversalData b) {                 
527                        return a.mPriority < b.mPriority;               }       };*/
528
529                //    ~TraversalData() {}
530                //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
531   
532        friend bool operator<(const TraversalData &a, const TraversalData &b)
533                {
534                        // return a.node->queries.size() < b.node->queries.size();
535                        VspKdLeaf *leafa = dynamic_cast<VspKdLeaf *>(a.mNode);
536                        VspKdLeaf *leafb = dynamic_cast<VspKdLeaf *>(b.mNode);
537#if 0
538                        return
539                                leafa->rays.size() * a.mBox.GetVolume()
540                                <
541                                leafb->rays.size() * b.mBox.GetVolume();
542#endif
543#if 0
544                        return
545                                leafa->GetPvsSize() * a.mBox.GetVolume()
546                                <
547                                leafb->GetPvsSize() * b.mBox.GetVolume();
548#endif
549#if 0
550                        return
551                                leafa->GetPvsSize()
552                                <
553                                leafb->GetPvsSize();
554#endif
555#if 0
556                        return
557                                leafa->GetPvsSize() / (float)(leafa->rays.size() + Limits::Small())
558                                >
559                                leafb->GetPvsSize() / (float)(leafb->rays.size() + Limits::Small());
560#endif
561#if 0
562                        return
563                                leafa->GetPvsSize() * (float)leafa->rays.size()
564                                <
565                                leafb->GetPvsSize() * (float)leafb->rays.size();
566#endif
567#if 1
568                        return a.mDepth > b.mDepth;
569#endif
570                }
571        };
572 
573        /** Simplified data for ray traversal only.
574        */
575        struct RayTraversalData
576        {
577                RayInfo mRayData;
578                VspKdNode *mNode;
579
580                RayTraversalData() {}
581         
582                RayTraversalData(VspKdNode *n, const RayInfo &data):
583                mRayData(data), mNode(n) {}
584        };
585       
586        struct LineTraversalData
587        {
588                VspKdNode *mNode;
589                Vector3 mExitPoint;
590               
591                float mMaxT;
592   
593                LineTraversalData () {}
594                LineTraversalData (VspKdNode *n, const Vector3 &p, const float maxt):
595                mNode(n), mExitPoint(p), mMaxT(maxt) {}
596        };
597
598public:
599
600        VspKdTree();
601        virtual ~VspKdTree();
602
603        virtual void Construct(const VssRayContainer &rays,
604                                                   AxisAlignedBox3 *forcedBoundingBox = NULL);
605
606        /** Returns bounding box of the specified node.
607        */
608        AxisAlignedBox3 GetBBox(VspKdNode *node) const;
609
610        const VspKdStatistics &GetStatistics() const;
611
612        /** Get the root of the tree.
613        */
614        VspKdNode *GetRoot() const;
615
616        /** Returns average PVS size in tree.
617        */
618        float GetAvgPvsSize();
619
620        /** Returns memory usage in MB.
621        */
622        float GetMemUsage() const;
623        //?
624        float GetRayMemUsage() const;
625
626        /** Collects leaves of this tree.
627        */
628        void CollectLeaves(vector<VspKdLeaf *> &leaves) const;
629
630        /** Merges view cells created with this tree according to
631                some (global) cost heuristics.
632        */
633        int MergeViewCells(const VssRayContainer &rays);
634
635        /** Finds neighbours of this node.
636                @param n the input node
637                @param neighbours the neighbors of the input node
638                @param onlyUnmailed if only unmailed neighbors are collected
639        */
640        int FindNeighbors(VspKdLeaf *n,
641                                          vector<VspKdLeaf *> &neighbors,
642                                          bool onlyUnmailed);
643
644       
645        /** Sets pointer to view cells manager.
646        */
647        void SetViewCellsManager(ViewCellsManager *vcm);
648
649        /** A ray is cast possible intersecting the tree.
650                @param the ray that is cast.
651                @returns the number of intersections with objects stored in the tree.
652        */
653        int CastLineSegment(const Vector3 &origin,
654                                                const Vector3 &termination,
655                                                vector<ViewCell *> &viewcells);
656
657        /** Collects view cells generated by this tree.
658        */
659        void CollectViewCells(ViewCellContainer &viewCells) const;
660       
661        /** Refines view cells using shuffling, i.e., border leaves
662                of two view cells are exchanged if the resulting view cells
663                are tested to be "better" than the old ones.
664                @returns number of refined view cells
665        */
666        int RefineViewCells(const VssRayContainer &rays);
667
668        /** Collects candidates for the merge in the merge queue.
669        */
670        void CollectMergeCandidates();
671
672        /** Collapses the tree with respect to the view cell partition.
673                @returns number of collapsed nodes
674        */
675        int CollapseTree();
676
677protected:
678
679        /** Collapses the tree with respect to the view cell partition,
680                i.e. leaves having the same view cell are collapsed.
681                @param node the root of the subtree to be collapsed
682                @param collapsed returns the number of collapsed nodes
683                @returns node of type leaf if the node could be collapsed,
684                this node otherwise
685        */
686        VspKdNode *CollapseTree(VspKdNode *node, int &collapsed);
687
688        // incremental construction
689        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);
690
691        virtual void AddRays(VssRayContainer &add);
692
693        VspKdNode *Locate(const Vector3 &v);
694       
695        VspKdNode *SubdivideNode(VspKdLeaf *leaf,
696                                                                 const AxisAlignedBox3 &box,
697                                                                 AxisAlignedBox3 &backBox,
698                                                                 AxisAlignedBox3 &frontBox);
699       
700        VspKdNode *Subdivide(const TraversalData &tdata);
701       
702        int SelectPlane(VspKdLeaf *leaf,
703                                        const AxisAlignedBox3 &box,
704                                        float &position,
705                                        int &raysBack,
706                                        int &raysFront,
707                                        int &pvsBack,
708                                        int &pvsFront);
709
710        void SortSplitCandidates(VspKdLeaf *node,
711                                                         const int axis);       
712 
713        float BestCostRatioHeuristic(VspKdLeaf *node,
714                                                                 const AxisAlignedBox3 &box,
715                                                                 int &axis,
716                                                                 float &position,
717                                                                 int &raysBack,
718                                                                 int &raysFront,
719                                                                 int &pvsBack,
720                                                                 int &pvsFront);
721
722        float BestCostRatioRegular(VspKdLeaf *node,
723                                                           const AxisAlignedBox3 &box,
724                                                           int &axis,
725                                                           float &position,
726                                                           int &raysBack,
727                                                           int &raysFront,
728                                                           int &pvsBack,
729                                                           int &pvsFront);
730       
731        float EvalCostRatio(VspKdLeaf *node,
732                                                const AxisAlignedBox3 &box,
733                                                const int axis,
734                                                const float position,
735                                                int &raysBack,
736                                                int &raysFront,
737                                                int &pvsBack,
738                                                int &pvsFront);
739
740
741        VspKdNode * SubdivideLeaf(VspKdLeaf *leaf,
742                                                                  const float SAThreshold);
743
744        void RemoveRay(VssRay *ray,
745                                   vector<VspKdLeaf *> *affectedLeaves,
746                                   const bool removeAllScheduledRays);
747
748        void AddRay(VssRay *ray);
749       
750        void TraverseInternalNode(RayTraversalData &data,
751                                                         stack<RayTraversalData> &tstack);
752
753        void EvaluateLeafStats(const TraversalData &data);
754
755
756        int     GetRootPvsSize() const;
757       
758        int     GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const;
759
760        void GetRayContributionStatistics(float &minRayContribution,
761                                                                          float &maxRayContribution,
762                                                                          float &avgRayContribution);
763
764        int GenerateRays(const float ratioPerLeaf,
765                                         SimpleRayContainer &rays);
766
767        /** Collapses this subtree and releases the memory.
768                @returns number of collapsed rays.
769        */
770        int CollapseSubtree(VspKdNode *sroot, const int time);
771       
772        int ReleaseMemory(const int time);
773
774        bool TerminationCriteriaMet(const VspKdLeaf *leaf,
775                                                                const AxisAlignedBox3 &box) const;
776
777        /** Computes PVS size of this node given a global ray set.
778                @returns PVS size of the intersection of this node bounding box with the rays.
779        */
780        int ComputePvsSize(VspKdNode *node,
781                                           const RayInfoContainer &globalRays) const;
782
783
784        /** Generates view cell for this leaf taking the ray contributions.
785        */
786        void GenerateViewCell(VspKdLeaf *leaf);
787
788        /** Merges view cells of the two leaves.
789        */
790        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
791       
792        /** Helper function revalidating the view cell leaf list after merge.
793        */
794        void RepairViewCellsLeafLists();
795
796        /** Shuffles the leaves, i.e., tests if exchanging
797                the view cells the leaves belong to helps in improving the view cells.
798        */
799        bool ShuffleLeaves(VspKdLeaf *leaf1, VspKdLeaf *leaf2) const;
800
801        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it
802                to view cell 2.
803        */
804        void ShuffleLeaf(VspKdLeaf *leaf,
805                                         VspKdViewCell *vc1,
806                                         VspKdViewCell *vc2) const;
807protected:
808       
809
810        /////////////////////////////
811        // The core pointer
812        VspKdNode *mRoot;
813 
814        /////////////////////////////
815        // Basic properties
816
817        // total number of nodes of the tree
818        int mNumNodes;
819       
820        // axis aligned bounding box of the scene
821        AxisAlignedBox3 mBox;
822
823        // epsilon used for the construction
824        float mEpsilon;
825
826        // ratio between traversal and intersection costs
827        float mCtDivCi;
828       
829        // type of the splitting to use for the tree construction
830        enum {ESplitRegular, ESplitHeuristic};
831        int splitType;
832       
833        // maximum alovable memory in MB
834        float mMaxTotalMemory;
835
836        // maximum alovable memory for static kd tree in MB
837        float mMaxStaticMemory;
838
839        // this is used during the construction depending
840        // on the type of the tree and queries...
841        float mMaxMemory;
842
843        // minimal acess time for collapse
844        int mAccessTimeThreshold;
845
846        // minimal depth at which to perform collapse
847        int mMinCollapseDepth;
848       
849        // reusable array of split candidates
850        vector<SortableEntry> *mSplitCandidates;
851       
852        ViewCellsManager *mViewCellsManager;
853
854        priority_queue<VspKdMergeCandidate> mMergeQueue;
855
856
857        /////////////////////////////
858        // Construction parameters
859
860        /// max depth of the tree
861        int mTermMaxDepth;
862        /// minimal ratio of the volume of the cell and the query volume
863        float mTermMinSize;
864        /// minimal pvs per node to still get subdivided
865        int mTermMinPvs;
866        /// minimal ray number per node to still get subdivided
867        int mTermMinRays;
868        /// maximal acceptable cost ratio to continue subdivision
869        float mTermMaxCostRatio;
870        /// maximal contribution per ray to subdivide the node
871        float mTermMaxRayContribution;
872        /// tolerance value indicating how often the max cost ratio can be failed
873        int mTermMissTolerance;
874
875        /// maximal numbers of view cells
876        int mMaxViewCells;
877
878        /// maximal cost ratio of a merge
879        float mMergeMaxCostRatio;
880       
881        /// minimal number of view cells
882        int mMergeMinViewCells;
883
884        /// if only the "driving axis", i.e., the axis with the biggest extent
885        /// should be used for subdivision
886        bool mOnlyDrivingAxis;
887
888        /////////////////////////////
889        VspKdStatistics mStat; 
890};
891
892}
893
894#endif // __VSP_KDTREE_H__
895
Note: See TracBrowser for help on using the repository browser.