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

Revision 860, 20.4 KB checked in by mattausch, 19 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        inline VspKdNode *GetBack() const;
280        /** Returns front child.
281        */
282        inline 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,
595                                                                  const Vector3 &p,
596                                                                  const float maxt):
597                mNode(n), mExitPoint(p), mMaxT(maxt) {}
598        };
599
600public:
601
602        VspKdTree();
603        virtual ~VspKdTree();
604
605        virtual void Construct(const VssRayContainer &rays,
606                                                   AxisAlignedBox3 *forcedBoundingBox = NULL);
607
608        /** Returns bounding box of the specified node.
609        */
610        AxisAlignedBox3 GetBBox(VspKdNode *node) const;
611
612        const VspKdStatistics &GetStatistics() const;
613
614        /** Get the root of the tree.
615        */
616        VspKdNode *GetRoot() const;
617
618        /** Returns average PVS size in tree.
619        */
620        float GetAvgPvsSize();
621
622        /** Returns memory usage in MB.
623        */
624        float GetMemUsage() const;
625        //?
626        float GetRayMemUsage() const;
627
628        /** Collects leaves of this tree.
629        */
630        void CollectLeaves(vector<VspKdLeaf *> &leaves) const;
631
632        /** Merges view cells created with this tree according to
633                some (global) cost heuristics.
634        */
635        int MergeViewCells(const VssRayContainer &rays);
636
637        /** Finds neighbours of this node.
638                @param n the input node
639                @param neighbours the neighbors of the input node
640                @param onlyUnmailed if only unmailed neighbors are collected
641        */
642        int FindNeighbors(VspKdLeaf *n,
643                                          vector<VspKdLeaf *> &neighbors,
644                                          bool onlyUnmailed);
645
646       
647        /** Sets pointer to view cells manager.
648        */
649        void SetViewCellsManager(ViewCellsManager *vcm);
650
651        /** A ray is cast possible intersecting the tree.
652                @param the ray that is cast.
653                @returns the number of intersections with objects stored in the tree.
654        */
655        int CastLineSegment(const Vector3 &origin,
656                                                const Vector3 &termination,
657                                                vector<ViewCell *> &viewcells);
658
659        /** Collects view cells generated by this tree.
660        */
661        void CollectViewCells(ViewCellContainer &viewCells) const;
662       
663        /** Refines view cells using shuffling, i.e., border leaves
664                of two view cells are exchanged if the resulting view cells
665                are tested to be "better" than the old ones.
666                @returns number of refined view cells
667        */
668        int RefineViewCells(const VssRayContainer &rays);
669
670        /** Collects candidates for the merge in the merge queue.
671        */
672        void CollectMergeCandidates();
673
674        /** Collapses the tree with respect to the view cell partition.
675                @returns number of collapsed nodes
676        */
677        int CollapseTree();
678
679protected:
680
681        /** Collapses the tree with respect to the view cell partition,
682                i.e. leaves having the same view cell are collapsed.
683                @param node the root of the subtree to be collapsed
684                @param collapsed returns the number of collapsed nodes
685                @returns node of type leaf if the node could be collapsed,
686                this node otherwise
687        */
688        VspKdNode *CollapseTree(VspKdNode *node, int &collapsed);
689
690        // incremental construction
691        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);
692
693        virtual void AddRays(VssRayContainer &add);
694
695        VspKdNode *Locate(const Vector3 &v);
696       
697        VspKdNode *SubdivideNode(VspKdLeaf *leaf,
698                                                                 const AxisAlignedBox3 &box,
699                                                                 AxisAlignedBox3 &backBox,
700                                                                 AxisAlignedBox3 &frontBox);
701       
702        VspKdNode *Subdivide(const TraversalData &tdata);
703       
704        int SelectPlane(VspKdLeaf *leaf,
705                                        const AxisAlignedBox3 &box,
706                                        float &position,
707                                        int &raysBack,
708                                        int &raysFront,
709                                        int &pvsBack,
710                                        int &pvsFront);
711
712        void SortSplitCandidates(VspKdLeaf *node,
713                                                         const int axis);       
714 
715        float BestCostRatioHeuristic(VspKdLeaf *node,
716                                                                 const AxisAlignedBox3 &box,
717                                                                 int &axis,
718                                                                 float &position,
719                                                                 int &raysBack,
720                                                                 int &raysFront,
721                                                                 int &pvsBack,
722                                                                 int &pvsFront);
723
724        float BestCostRatioRegular(VspKdLeaf *node,
725                                                           const AxisAlignedBox3 &box,
726                                                           int &axis,
727                                                           float &position,
728                                                           int &raysBack,
729                                                           int &raysFront,
730                                                           int &pvsBack,
731                                                           int &pvsFront);
732       
733        float EvalCostRatio(VspKdLeaf *node,
734                                                const AxisAlignedBox3 &box,
735                                                const int axis,
736                                                const float position,
737                                                int &raysBack,
738                                                int &raysFront,
739                                                int &pvsBack,
740                                                int &pvsFront);
741
742
743        VspKdNode * SubdivideLeaf(VspKdLeaf *leaf,
744                                                                  const float SAThreshold);
745
746        void RemoveRay(VssRay *ray,
747                                   vector<VspKdLeaf *> *affectedLeaves,
748                                   const bool removeAllScheduledRays);
749
750        void AddRay(VssRay *ray);
751       
752        void TraverseInternalNode(RayTraversalData &data,
753                                                         stack<RayTraversalData> &tstack);
754
755        void EvaluateLeafStats(const TraversalData &data);
756
757
758        int     GetRootPvsSize() const;
759       
760        int     GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const;
761
762        void GetRayContributionStatistics(float &minRayContribution,
763                                                                          float &maxRayContribution,
764                                                                          float &avgRayContribution);
765
766        int GenerateRays(const float ratioPerLeaf,
767                                         SimpleRayContainer &rays);
768
769        /** Collapses this subtree and releases the memory.
770                @returns number of collapsed rays.
771        */
772        int CollapseSubtree(VspKdNode *sroot, const int time);
773       
774        int ReleaseMemory(const int time);
775
776        bool TerminationCriteriaMet(const VspKdLeaf *leaf,
777                                                                const AxisAlignedBox3 &box) const;
778
779        /** Computes PVS size of this node given a global ray set.
780                @returns PVS size of the intersection of this node bounding box with the rays.
781        */
782        int ComputePvsSize(VspKdNode *node,
783                                           const RayInfoContainer &globalRays) const;
784
785
786        /** Generates view cell for this leaf taking the ray contributions.
787        */
788        void GenerateViewCell(VspKdLeaf *leaf);
789
790        /** Merges view cells of the two leaves.
791        */
792        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
793       
794        /** Helper function revalidating the view cell leaf list after merge.
795        */
796        void RepairViewCellsLeafLists();
797
798        /** Shuffles the leaves, i.e., tests if exchanging
799                the view cells the leaves belong to helps in improving the view cells.
800        */
801        bool ShuffleLeaves(VspKdLeaf *leaf1, VspKdLeaf *leaf2) const;
802
803        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it
804                to view cell 2.
805        */
806        void ShuffleLeaf(VspKdLeaf *leaf,
807                                         VspKdViewCell *vc1,
808                                         VspKdViewCell *vc2) const;
809protected:
810       
811
812        /////////////////////////////
813        // The core pointer
814        VspKdNode *mRoot;
815 
816        /////////////////////////////
817        // Basic properties
818
819        // total number of nodes of the tree
820        int mNumNodes;
821       
822        // axis aligned bounding box of the scene
823        AxisAlignedBox3 mBox;
824
825        // epsilon used for the construction
826        float mEpsilon;
827
828        // ratio between traversal and intersection costs
829        float mCtDivCi;
830       
831        // type of the splitting to use for the tree construction
832        enum {ESplitRegular, ESplitHeuristic};
833        int splitType;
834       
835        // maximum alovable memory in MB
836        float mMaxTotalMemory;
837
838        // maximum alovable memory for static kd tree in MB
839        float mMaxStaticMemory;
840
841        // this is used during the construction depending
842        // on the type of the tree and queries...
843        float mMaxMemory;
844
845        // minimal acess time for collapse
846        int mAccessTimeThreshold;
847
848        // minimal depth at which to perform collapse
849        int mMinCollapseDepth;
850       
851        // reusable array of split candidates
852        vector<SortableEntry> *mSplitCandidates;
853       
854        ViewCellsManager *mViewCellsManager;
855
856        priority_queue<VspKdMergeCandidate> mMergeQueue;
857
858
859        /////////////////////////////
860        // Construction parameters
861
862        /// max depth of the tree
863        int mTermMaxDepth;
864        /// minimal ratio of the volume of the cell and the query volume
865        float mTermMinSize;
866        /// minimal pvs per node to still get subdivided
867        int mTermMinPvs;
868        /// minimal ray number per node to still get subdivided
869        int mTermMinRays;
870        /// maximal acceptable cost ratio to continue subdivision
871        float mTermMaxCostRatio;
872        /// maximal contribution per ray to subdivide the node
873        float mTermMaxRayContribution;
874        /// tolerance value indicating how often the max cost ratio can be failed
875        int mTermMissTolerance;
876
877        /// maximal numbers of view cells
878        int mMaxViewCells;
879
880        /// maximal cost ratio of a merge
881        float mMergeMaxCostRatio;
882       
883        /// minimal number of view cells
884        int mMergeMinViewCells;
885
886        /// if only the "driving axis", i.e., the axis with the biggest extent
887        /// should be used for subdivision
888        bool mOnlyDrivingAxis;
889
890        /////////////////////////////
891        VspKdStatistics mStat; 
892};
893
894}
895
896#endif // __VSP_KDTREE_H__
897
Note: See TracBrowser for help on using the repository browser.