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

Revision 587, 20.3 KB checked in by mattausch, 19 years ago (diff)

updated vspkdtree for regular sudbivision

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