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

Revision 2015, 20.3 KB checked in by bittner, 18 years ago (diff)

pvs efficiency tuning

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