source: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h @ 485

Revision 485, 18.2 KB checked in by mattausch, 19 years ago (diff)

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

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 MergeCandidate
46
47public:
48
49        MergeCandidate(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 MergeCandidate &leafa, const MergeCandidate &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, ELeaf};
206
207        /** Constructs new interior node from the parent node.
208        */
209        inline VspKdNode(VspKdInterior *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        */
229        virtual int GetAccessTime(); // NOTE: don't really know how it is used!
230
231        /** Returns parent node.
232        */
233        VspKdInterior *GetParent() const;
234
235        /** Sets parent node.
236        */
237        void SetParent(VspKdInterior *p);
238
239protected:
240        /////////////////////////////////
241        // The actual data goes here
242 
243        /// link to the parent
244        VspKdInterior *mParent;
245
246        enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z};
247 
248        /// splitting axis
249        char mAxis;
250       
251        /// depth
252        unsigned char mDepth;
253};
254
255// --------------------------------------------------------------
256// KD-tree node - interior node
257// --------------------------------------------------------------
258class VspKdInterior: public VspKdNode
259{
260public:
261        friend class VspKdTree;
262
263        /** Constructs new interior node from parent node.
264        */
265        VspKdInterior(VspKdInterior *p);
266                       
267        virtual int GetAccessTime();
268       
269        virtual int Type() const;
270 
271        virtual ~VspKdInterior();
272   
273        virtual void Print(ostream &s) const;
274
275        /** Returns back child.
276        */
277        inline VspKdNode *GetBack() const;
278        /** Returns front child.
279        */
280        inline VspKdNode *GetFront() const;
281
282protected:
283
284        /** Sets pointers to back child and front child.
285        */
286        void SetupChildLinks(VspKdNode *b, VspKdNode *f);
287        /** Replaces the pointer to oldChild with a pointer to newChild.
288        */
289        void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild);
290        /** Computes intersection of the ray with the node boundaries.
291        */
292        int ComputeRayIntersection(const RayInfo &rayData, float &t);
293
294        // plane in local modelling coordinates
295        float mPosition;
296
297        // pointers to children
298        VspKdNode *mBack;
299        VspKdNode *mFront;
300
301        // the bbox of the node
302        AxisAlignedBox3 mBox;
303
304        // data for caching
305        long mAccesses;
306        long mLastAccessTime;
307};
308
309
310// --------------------------------------------------------------
311// KD-tree node - leaf node
312// --------------------------------------------------------------
313class VspKdLeaf: public VspKdNode
314{
315public:
316
317        friend class VspKdTree;
318
319        /** Constructs leaf from parent node.
320                @param p the parent node
321                @param nRays preallocates memory to store this number of rays
322                @parma maxMisses how many times the max cost ratio was missed on the path to the leaf
323        */
324        VspKdLeaf(VspKdInterior *p,     const int nRays, const int maxCostMisses = 0);
325       
326        virtual ~VspKdLeaf();
327
328        virtual int Type() const; 
329
330        virtual void Print(ostream &s) const;
331 
332        /** Adds a ray to the leaf ray container.
333        */
334        void AddRay(const RayInfo &data);
335        /** Returns size of the leaf PVS as induced by the rays
336                @note returns precomputed PVS size, which may not be valid
337                anymore. Run UpdatePvsSize to get a valid PVS.
338        */
339        int GetPvsSize() const;
340
341        /** If PVS is not valid, this function recomputes the leaf
342                PVS as induced by the rays.
343        */
344        void UpdatePvsSize();
345
346        /** Returns stored rays.
347        */
348        RayInfoContainer &GetRays();
349
350        /** Returns rays into this ray container.
351        */
352        void GetRays(VssRayContainer &rays);
353        /** Returns average contribution of a ray to the PVS
354        */
355        inline float GetAvgRayContribution() const;
356        /** Returns square of average contribution of a ray.
357        */
358        inline float GetSqrRayContribution() const;
359
360        /** Extracts PVS from ray set.
361        */
362        void ExtractPvs(ObjectContainer &objects) const;
363
364        //-- mailing options
365        void Mail();
366
367        bool Mailed() const;
368 
369        /** Returns true if mail equals the leaf mail box.
370        */
371        bool Mailed(const int mail) const;
372
373        void SetViewCell(VspKdViewCell *viewCell);
374
375        /** Returns mail box of this leaf.
376        */
377        int GetMailbox() const;
378
379        /** Returns view cell associated with this leaf.
380        */
381        VspKdViewCell *GetViewCell();
382
383        /** Returns number of times the max cost ratio was missed until
384                this leaf.
385        */
386        int GetMaxCostMisses();
387
388
389        ////////////////////////////////////////////
390       
391        static void NewMail();
392
393        static int sMailId;
394
395       
396protected:
397
398        /** Manually sets PVS size.
399                @param s the PVS size
400        */
401        void SetPvsSize(const int s);
402
403        int mMailbox;
404 
405        /// rays intersecting this leaf.
406        RayInfoContainer mRays;
407        /// true if mPvsSize is valid => PVS does not have to be updated
408        bool mValidPvs;
409        /// the view cell associated with this leaf
410        VspKdViewCell *mViewCell;
411        /// number of times the max cost ratio was missed on the way to the leaf.
412        int mMaxCostMisses;
413
414private:
415        /// stores PVS size so we have to evaluate PVS size only once
416        int mPvsSize;
417};
418
419
420
421// ---------------------------------------------------------------
422// Main LSDS search class
423// ---------------------------------------------------------------
424class VspKdTree
425{
426        // --------------------------------------------------------------
427        // For sorting rays
428        // -------------------------------------------------------------
429        struct SortableEntry
430        {
431                enum EType
432                {
433                        ERayMin,
434                        ERayMax
435                };
436
437                int type;
438                float value;
439                VssRay *ray;
440 
441                SortableEntry() {}
442                SortableEntry(const int t, const float v, VssRay *r): type(t),
443                                          value(v), ray(r)
444                {
445                }
446               
447                friend bool operator<(const SortableEntry &a, const SortableEntry &b)
448                {
449                        return a.value < b.value;
450                }
451        };
452
453        struct TraversalData
454        { 
455                VspKdNode *mNode;
456                AxisAlignedBox3 mBox;
457                int mDepth;
458                //float mPriority;
459       
460                TraversalData() {}
461
462                TraversalData(VspKdNode *n, const float p):
463                mNode(n)//, mPriority(p)
464                {}
465
466                TraversalData(VspKdNode *n,     const AxisAlignedBox3 &b, const int d):
467                mNode(n), mBox(b), mDepth(d) {}
468   
469                // comparator for the priority queue
470                /*struct less_priority : public binary_function<const TraversalData, const TraversalData, bool>
471                {
472                        bool operator()(const TraversalData a, const TraversalData b) {                 
473                        return a.mPriority < b.mPriority;               }       };*/
474
475                //    ~TraversalData() {}
476                //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
477   
478        friend bool operator<(const TraversalData &a, const TraversalData &b)
479                {
480                        // return a.node->queries.size() < b.node->queries.size();
481                        VspKdLeaf *leafa = (VspKdLeaf *) a.mNode;
482                        VspKdLeaf *leafb = (VspKdLeaf *) b.mNode;
483#if 0
484                        return
485                                leafa->rays.size() * a.mBox.GetVolume()
486                                <
487                                leafb->rays.size() * b.mBox.GetVolume();
488#endif
489#if 1
490                        return
491                                leafa->GetPvsSize() * a.mBox.GetVolume()
492                                <
493                                leafb->GetPvsSize() * b.mBox.GetVolume();
494#endif
495#if 0
496                        return
497                                leafa->GetPvsSize()
498                                <
499                                leafb->GetPvsSize();
500#endif
501#if 0
502                        return
503                                leafa->GetPvsSize() / (float)(leafa->rays.size() + Limits::Small())
504                                >
505                                leafb->GetPvsSize() / (float)(leafb->rays.size() + Limits::Small());
506#endif
507#if 0
508                        return
509                                leafa->GetPvsSize() * (float)leafa->rays.size()
510                                <
511                                leafb->GetPvsSize() * (float)leafb->rays.size();
512#endif
513                }
514        };
515 
516        /** Simplified data for ray traversal only.
517        */
518        struct RayTraversalData
519        {
520                RayInfo mRayData;
521                VspKdNode *mNode;
522
523                RayTraversalData() {}
524         
525                RayTraversalData(VspKdNode *n, const RayInfo &data):
526                mRayData(data), mNode(n) {}
527        };
528       
529        struct LineTraversalData
530        {
531                VspKdNode *mNode;
532                Vector3 mExitPoint;
533               
534                float mMaxT;
535   
536                LineTraversalData () {}
537                LineTraversalData (VspKdNode *n,
538                                                                  const Vector3 &p,
539                                                                  const float maxt):
540                mNode(n), mExitPoint(p), mMaxT(maxt) {}
541        };
542
543public:
544
545        VspKdTree();
546        virtual ~VspKdTree();
547
548        virtual void Construct(const VssRayContainer &rays,
549                                                   AxisAlignedBox3 *forcedBoundingBox = NULL);
550
551        /** Returns bounding box of the specified node.
552        */
553        AxisAlignedBox3 GetBBox(VspKdNode *node) const;
554
555        const VspKdStatistics &GetStatistics() const;
556
557        /** Get the root of the tree.
558        */
559        VspKdNode *GetRoot() const;
560
561        /** Returns average PVS size in tree.
562        */
563        float GetAvgPvsSize();
564
565        /** Returns memory usage in MB.
566        */
567        float GetMemUsage() const;
568        //?
569        float GetRayMemUsage() const;
570
571        /** Collects leaves of this tree.
572        */
573        void CollectLeaves(vector<VspKdLeaf *> &leaves) const;
574
575        /** Merges view cells created with this tree according to
576                some (global) cost heuristics.
577        */
578        int MergeViewCells(const VssRayContainer &rays);
579
580        /** Finds neighbours of this node.
581                @param n the input node
582                @param neighbours the neighbors of the input node
583                @param onlyUnmailed if only unmailed neighbors are collected
584        */
585        int FindNeighbors(VspKdLeaf *n,
586                                          vector<VspKdLeaf *> &neighbors,
587                                          bool onlyUnmailed);
588
589       
590        /** Sets pointer to view cells manager.
591        */
592        void SetViewCellsManager(ViewCellsManager *vcm);
593
594        /** A ray is cast possible intersecting the tree.
595                @param the ray that is cast.
596                @returns the number of intersections with objects stored in the tree.
597        */
598        int CastLineSegment(const Vector3 &origin,
599                                                const Vector3 &termination,
600                                                vector<ViewCell *> &viewcells);
601
602        /** Collects view cells generated by this tree.
603        */
604        void CollectViewCells(ViewCellContainer &viewCells) const;
605        /** Refines view cells in a post processing step.
606        */
607        void RefineViewCells();
608
609        /** Collects candidates for the merge in the merge queue.
610        */
611        void CollectMergeCandidates();
612
613        /** Collapses the tree with respect to the view cell partition.
614                @returns node of type leaf if the node could be collapsed, this node otherwise
615        */
616        VspKdNode *CollapseTree(VspKdNode *node);
617
618protected:
619
620        // incremental construction
621        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);
622
623        virtual void AddRays(VssRayContainer &add);
624
625        VspKdNode *Locate(const Vector3 &v);
626       
627        VspKdNode *SubdivideNode(VspKdLeaf *leaf,
628                                                                 const AxisAlignedBox3 &box,
629                                                                 AxisAlignedBox3 &backBox,
630                                                                 AxisAlignedBox3 &frontBox);
631       
632        VspKdNode *Subdivide(const TraversalData &tdata);
633       
634        int SelectPlane(VspKdLeaf *leaf,
635                                        const AxisAlignedBox3 &box,
636                                        float &position,
637                                        int &raysBack,
638                                        int &raysFront,
639                                        int &pvsBack,
640                                        int &pvsFront);
641
642        void SortSplitCandidates(VspKdLeaf *node,
643                                                         const int axis);       
644 
645        float BestCostRatioHeuristic(VspKdLeaf *node,
646                                                                 const AxisAlignedBox3 &box,
647                                                                 int &axis,
648                                                                 float &position,
649                                                                 int &raysBack,
650                                                                 int &raysFront,
651                                                                 int &pvsBack,
652                                                                 int &pvsFront);
653
654        float BestCostRatioRegular(VspKdLeaf *node,
655                                                           const AxisAlignedBox3 &box,
656                                                           int &axis,
657                                                           float &position,
658                                                           int &raysBack,
659                                                           int &raysFront,
660                                                           int &pvsBack,
661                                                           int &pvsFront);
662       
663        float EvalCostRatio(VspKdLeaf *node,
664                                                const AxisAlignedBox3 &box,
665                                                const int axis,
666                                                const float position,
667                                                int &raysBack,
668                                                int &raysFront,
669                                                int &pvsBack,
670                                                int &pvsFront);
671
672
673        VspKdNode * SubdivideLeaf(VspKdLeaf *leaf,
674                                                                  const float SAThreshold);
675
676        void RemoveRay(VssRay *ray,
677                                   vector<VspKdLeaf *> *affectedLeaves,
678                                   const bool removeAllScheduledRays);
679
680        void AddRay(VssRay *ray);
681       
682        void TraverseInternalNode(RayTraversalData &data,
683                                                         stack<RayTraversalData> &tstack);
684
685        void EvaluateLeafStats(const TraversalData &data);
686
687
688        int     GetRootPvsSize() const;
689       
690        int     GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const;
691
692        void GetRayContributionStatistics(float &minRayContribution,
693                                                                          float &maxRayContribution,
694                                                                          float &avgRayContribution);
695
696        int GenerateRays(const float ratioPerLeaf,
697                                         SimpleRayContainer &rays);
698
699        /** Collapses this subtree and releases the memory.
700                @returns number of collapsed rays.
701        */
702        int CollapseSubtree(VspKdNode *sroot, const int time);
703       
704        int ReleaseMemory(const int time);
705
706        bool TerminationCriteriaMet(const VspKdLeaf *leaf,
707                                                                const AxisAlignedBox3 &box) const;
708
709        /** Computes PVS size of this node given a global ray set.
710                @returns PVS size of the intersection of this node bounding box with the rays.
711        */
712        int ComputePvsSize(VspKdNode *node,
713                                           const RayInfoContainer &globalRays) const;
714
715
716        /** Generates view cell for this leaf taking the ray contributions.
717        */
718        void GenerateViewCell(VspKdLeaf *leaf);
719
720        /** Merges view cells of the two leaves.
721        */
722        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
723       
724        /** Helper function revalidating the view cell leaf list after merge.
725        */
726        void RepairVcLeafLists();
727
728protected:
729       
730
731        /////////////////////////////
732        // The core pointer
733        VspKdNode *mRoot;
734 
735        /////////////////////////////
736        // Basic properties
737
738        // total number of nodes of the tree
739        int mNumNodes;
740       
741        // axis aligned bounding box of the scene
742        AxisAlignedBox3 mBox;
743
744        // epsilon used for the construction
745        float mEpsilon;
746
747        // ratio between traversal and intersection costs
748        float mCtDivCi;
749       
750        // type of the splitting to use for the tree construction
751        enum {ESplitRegular, ESplitHeuristic};
752        int splitType;
753       
754        // maximum alovable memory in MB
755        float mMaxTotalMemory;
756
757        // maximum alovable memory for static kd tree in MB
758        float mMaxStaticMemory;
759
760        // this is used during the construction depending
761        // on the type of the tree and queries...
762        float mMaxMemory;
763
764        // minimal acess time for collapse
765        int mAccessTimeThreshold;
766
767        // minimal depth at which to perform collapse
768        int mMinCollapseDepth;
769       
770        // reusable array of split candidates
771        vector<SortableEntry> *mSplitCandidates;
772       
773        ViewCellsManager *mViewCellsManager;
774
775        priority_queue<MergeCandidate> mMergeQueue;
776
777
778        /////////////////////////////
779        // Construction parameters
780
781        /// max depth of the tree
782        int mTermMaxDepth;
783        /// minimal ratio of the volume of the cell and the query volume
784        float mTermMinSize;
785        /// minimal pvs per node to still get subdivided
786        int mTermMinPvs;
787        /// minimal ray number per node to still get subdivided
788        int mTermMinRays;
789        /// maximal acceptable cost ratio to continue subdivision
790        float mTermMaxCostRatio;
791        /// maximal contribution per ray to subdivide the node
792        float mTermMaxRayContribution;
793        /// tolerance value indicating how often the max cost ratio can be failed
794        int mTermMissTolerance;
795
796        /// maximal numbers of view cells
797        int mMaxViewCells;
798
799        /// maximal cost ratio of a merge
800        float mMergeMaxCostRatio;
801       
802        /// minimal number of view cells
803        int mMergeMinViewCells;
804
805        /// if only the "driving axis", i.e., the axis with the biggest extent
806        /// should be used for subdivision
807        bool mOnlyDrivingAxis;
808
809        /////////////////////////////
810        VspKdStatistics mStat; 
811};
812
813
814#endif // __VSP_KDTREE_H__
815
Note: See TracBrowser for help on using the repository browser.