source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.h @ 2199

Revision 2199, 19.8 KB checked in by mattausch, 18 years ago (diff)

using mutationsamples for evaluation

Line 
1#ifndef _ViewCell_H__
2#define _ViewCell_H__
3
4#include "Mesh.h"
5#include "Containers.h"
6#include "Ray.h"
7#include "Statistics.h"
8#include "Material.h"
9#include "gzstream.h"
10#include "ObjectPvs.h"
11
12namespace GtpVisibilityPreprocessor {
13
14struct Triangle3;
15
16class BspInterior;
17class BspPvs;
18class BspLeaf;
19class VspLeaf;
20class KdLeaf;
21class ViewCellInterior;
22class MergeCandidate;
23class ViewCellsManager;
24class ViewCellLeaf;
25
26
27//class ObjectPvs;
28
29
30/** Statistics for a view cell partition.
31*/
32
33class ViewCellsStatistics: public StatisticsBase
34{
35public:
36
37        /// number of view cells
38        int viewCells;
39        /// cost of the PVS
40        float pvsCost;
41        /// largest PVS of all view cells
42        float maxPvs;
43        /// smallest PVS of all view cells
44        float minPvs;
45        /// view cells with empty PVS
46        int emptyPvs;
47        /// number of leaves covering the view space
48        int leaves;
49        /// largest number of leaves covered by one view cell
50        int maxLeaves;
51        /// number of invalid view cells
52        int invalid;
53
54    // Constructor
55        ViewCellsStatistics()
56        {
57                Reset();
58        }
59
60        double AvgLeaves() const {return (double)leaves / (double)viewCells;};
61        double AvgPvs() const {return (double)pvsCost / (double)viewCells;};
62
63        void Reset()
64        {
65                viewCells = 0;
66                pvsCost = 0;
67                maxPvs = 0;
68
69                minPvs = 999999;
70                emptyPvs = 0;
71                leaves = 0;
72                maxLeaves = 0;
73                invalid = 0;
74        }
75
76        void Print(std::ostream &app) const;
77
78        friend std::ostream &operator<<(std::ostream &s, const ViewCellsStatistics &stat)
79        {
80                stat.Print(s);
81                return s;
82        }
83};
84
85
86class ViewCellsTreeStats
87{
88public:
89        int mPass;
90   
91        int mNumViewCells;
92               
93        float mRenderCostDecrease;
94
95    float mTotalRenderCost;
96   
97        float mCurrentPvsCost;
98                                                       
99        float mExpectedCost;
100   
101        float mAvgRenderCost;
102       
103        float mDeviation;
104                       
105        float mTotalPvsCost;
106       
107        int mEntriesInPvs;
108   
109        float mMemoryCost;
110       
111        int mPvsSizeDecr;
112 
113        float mVolume;
114
115
116        void Reset()
117        {
118                mPass = 0;
119                mNumViewCells = 0;
120                mRenderCostDecrease = 0;
121                mTotalRenderCost = 0;
122                mCurrentPvsCost = 0;
123                mExpectedCost = 0;
124                mAvgRenderCost = 0;
125                mDeviation = 0;
126                mTotalPvsCost = 0;
127                mEntriesInPvs = 0;
128                mMemoryCost = 0;
129                mPvsSizeDecr = 0;
130                mVolume = 0;
131        }
132
133
134        void Print(std::ostream &app) const;
135
136        friend std::ostream &operator<<(std::ostream &s, const ViewCellsTreeStats &stat)
137        {
138                stat.Print(s);
139                return s;
140        }
141};
142
143
144/**
145        A view cell. View cells are regions in space. The visibility informations,
146        i.e., the primitives seen by the view cell are stored in a PVs.
147        A view cell can be represented in many different ways, e.g.,
148        a mesh representation.
149*/
150class ViewCell: public MeshInstance
151{
152        friend class ViewCellsTree;
153        friend class ViewCellsManager;
154
155public:
156
157        ViewCell();
158
159        /** Constructor taking a mesh representing the shape of the viewcell.
160        */
161        ViewCell(Mesh *mesh);
162
163        /** Default destructor.
164        */
165        virtual ~ViewCell();
166        /** Returns Pvs.
167        */
168        const ObjectPvs &GetPvs() const;
169        /** Returns pvs.
170        */
171        ObjectPvs &GetPvs();
172        /** Completely substitutes the pvs.
173        */
174        void SetPvs(const ObjectPvs &pvs);
175        /** Type of view cell.
176        */
177        int Type() const;
178        /** Adds a passing ray to the passing ray container.
179        */
180        void AddPassingRay(const Ray &ray, const int contributions);
181        /** Returns volume of the view cell.
182        */
183        inline float GetVolume() const
184        {
185                return mVolume;
186        }
187        /** Sets the volume of the view cell.
188        */
189        inline void SetVolume(float volume)
190        {
191                mVolume = volume;
192        }
193        /** Returns area of the view cell.
194        */
195        inline float GetArea() const
196        {
197                return mArea;
198        }
199        /** Sets the area of the view cell.
200        */
201        void SetArea(float area)
202        {
203                mArea = area;
204        }
205        /** if this view cell is the root of a view cell hierarchy
206        */
207        bool IsRoot() const;
208        /** Returns parent view cell.
209        */
210        ViewCellInterior *GetParent() const;
211        /** Sets parent of this view cell.
212        */
213        void SetParent(ViewCellInterior *parent);
214        /** Sets the mesh for this view cell.
215        */
216        void SetMesh(Mesh *mesh);
217        /** Sets this view cell to be a valid view cell according to some criteria.
218        */
219        void SetValid(const bool valid);
220        /** Returns true if this view cell is considered to be valid according to
221                some criteria.
222        */
223        bool GetValid() const;
224
225        /** Returns estimated render cost of this view cell.
226        */
227        float GetRenderCost() const;
228
229        /** set color for visiualizations.
230        */
231        void SetColor(const RgbColor &color);
232
233        /** get color for visualuzations.
234        */
235    RgbColor GetColor() const;
236
237        /** Adds a sample to the pvs.
238                @param sample the sample to be added
239                @param pdf a continuos measure of visibility
240                @param contribution returns the contribution of this sample to the pvs
241        */
242        bool AddPvsSample(Intersectable *sample, const float pdf, float &contribution);
243
244        /** if this is a view cell correspending to a leaf in a hierarchy.
245        */
246        virtual bool IsLeaf() const = 0;
247
248        static bool SmallerPvs(const ViewCell *a, const ViewCell *b)
249        {
250                // HACK: take scalar value because pvs may not have been stored properly
251#if 1
252                return a->mPvsCost < b->mPvsCost;
253#else
254                return a->GetPvs().EvalPvsCost() < b->GetPvs().EvalPvsCost();
255#endif
256        }
257
258        static bool GreaterOrEqualPvs(const ViewCell *a, const ViewCell *b)
259        {
260                return !SmallerPvs(a, b);
261        }
262
263        static bool SmallerRenderCost(const ViewCell *a, const ViewCell *b)
264        {
265                return a->GetRenderCost() < b->GetRenderCost();
266        }
267
268        static bool LargerRenderCost(const ViewCell *a, const ViewCell *b)
269        {
270                return a->GetRenderCost() > b->GetRenderCost();
271        }
272
273        /** Sets merge cost used for merging this view cell from other cells.
274                @hack The function is available for leaves also to have a common interface,
275                but it should be less than zero for leaves.
276        */
277        void SetMergeCost(const float mergeCost);
278
279        /** Returns merge cost needed to merge this leaf from other cells.
280                @hack The function is available for leaves also to have a common interface,
281                but it should be less than zero for leaves.
282        */
283        float GetMergeCost() const;
284
285        void UpdatePvsCost() {
286                mPvsCost = GetPvs().EvalPvsCost();
287        }
288
289        void SetPvsCost(const float c) {
290                mPvsCost = c;
291        }
292
293        float GetPvsCost() const {
294                return mPvsCost;
295        }
296
297        int GetFilteredPvsSize() const
298        {
299                return mFilteredPvsSize;
300        }
301
302        void SetFilteredPvsSize(const int s) {
303                mFilteredPvsSize = s;
304        }
305
306        //virtual int ViewCellType;
307
308protected:
309
310        /// parent view cell in the view cell hierarchy
311        ViewCellInterior *mParent;
312        /// the potentially visible objects
313        ObjectPvs mPvs;
314        /// the volume of this view cell
315        float mVolume;
316        /// the area of this view cell
317        float mArea;
318        /// the cost that were paid for merging this view cells from two others.
319        float mMergeCost;
320        /// if the view cell is valid view space
321        bool mValid;
322        /// color used for consistent visualization
323        RgbColor mColor;
324        /// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
325        float mPvsCost;
326        /** stores number of entries in pvs
327            this variable has the same value as mPvsSize for object pvs,
328                but usually not for kd cell based pvs
329        */
330        int mEntriesInPvs;
331        /** if the pvs size scalar (+ entries into pvs)
332                is up to date and corresponding to the real pvs size
333        */
334        bool mPvsSizeValid;
335
336        /// Filter cost of the pvs
337        int mFilteredPvsSize;
338
339};
340
341
342class ViewCellInterior: public ViewCell
343{
344        friend class ViewCellsManager;
345
346public:
347        ViewCellInterior();
348        ~ViewCellInterior();
349
350        ViewCellInterior(Mesh *mesh);
351
352        /** Sets pointer from parent to child and vice versa.
353        */
354        void SetupChildLink(ViewCell *l);
355        void ReplaceChildLink(ViewCell *prev, ViewCell *cur);
356
357        void RemoveChildLink(ViewCell *l);
358        bool IsLeaf() const;
359
360        void SetCost(const float c) {
361                mCost = c;
362        }
363
364        float GetCost() const {
365                return mCost;
366        }
367
368        ViewCellContainer mChildren;
369
370protected:
371
372        /// Pverall cost resulting from the merge.
373        float mCost;
374};
375
376
377/**
378        Leaf of the view cell.
379*/
380class ViewCellLeaf: public ViewCell
381{
382public:
383        ViewCellLeaf()  {  mActiveViewCell = this; }
384        ViewCellLeaf(Mesh *mesh):
385        ViewCell(mesh) { mActiveViewCell = this; }
386
387        bool IsLeaf() const
388        {
389                return true;
390        }
391
392        /** Returns active view cell, i.e. this view cell or
393                a parent view cell which is set as active view cell.
394        */
395        ViewCell *GetActiveViewCell() const
396        { return mActiveViewCell; }
397
398        /** Sets this view cell to be an active view cell.
399        */
400        void SetActiveViewCell(ViewCell *vc)
401        { mActiveViewCell = vc;}
402       
403        /** points to the currently active view cell. This is the
404                view cell representing the current brach.
405        */
406        ViewCell *mActiveViewCell;
407};
408
409
410/** Leaf of the view cell hierarchy corresponding
411        to a leaf in a spatial hierarchy.
412*/
413template<typename T>
414class HierarchyLeafViewCell: public ViewCellLeaf
415{
416public:
417
418        HierarchyLeafViewCell<T>(): ViewCellLeaf() {  }
419        HierarchyLeafViewCell<T>(Mesh *mesh):
420        ViewCellLeaf(mesh) {  }
421               
422        bool IsLeaf() const
423        {
424                return true;
425        }
426
427        /// Leaves of some hierarchy which contains this view cell.
428        vector<T> mLeaves;
429};
430
431
432typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
433typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
434typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;
435
436
437
438
439class ViewCellsTree
440{
441        friend class ViewCellsManager;
442        friend class ViewCellsParseHandlers;
443
444public:
445
446        ViewCellsTree();
447
448        /** View cells tree constructor taking a view cell mnanager as parameter
449        */
450        ViewCellsTree(ViewCellsManager *vcm);
451        ~ViewCellsTree();
452
453        /** Returns number of leaves this view cell consists of.
454        */
455        int GetNumInitialViewCells(ViewCell *vc) const;
456
457        /** Collects leaves corresponding to a view cell.
458        */
459        void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
460
461        /** Merges view cells according to some cost heuristics.
462        */
463        int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
464       
465        /** Refines view cells using shuffling, i.e., border leaves
466                of two view cells are exchanged if the resulting view cells
467                are tested to be "better" than the old ones.
468                @returns number of refined view cells
469        */
470        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
471       
472        /** Assign colors to the viewcells so that they can be renderered interactively without
473            color flickering. 
474        */
475        void AssignRandomColors();
476
477        /** Updates view cell stats for this particular view cell.
478        */
479        void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);
480
481        /** Get costs resulting from each merge step.
482        */
483        void GetCostFunction(vector<float> &costFunction);
484       
485        /** Returns storage cost resulting from each merge step.
486        */
487        void GetStorageFunction(vector<int> &storageCost);
488
489        /** Returns optimal set of view cells for a given number of view cells.
490        */
491        void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);
492
493        /** Root of view cells tree.
494        */
495        ViewCell *GetRoot() const;
496
497        /** Returns pvs of view cell.
498                @note pvs is returned per reference if tree is not compressed,
499                per copy else.
500        */
501        void GetPvs(ViewCell *vc, ObjectPvs &pvs) const;
502
503        /** Returns pvs size (i.e. the render cost of the stored objects)
504        */
505        float GetPvsCost(ViewCell *vc) const;
506 
507        /** Returns number of entries associated with this view cell.
508
509                This returns the same value as the "GetPvsSize" function for object pvs
510                but most likely different values if we use object space grouping.
511                E.g., using bounding volumes.
512        */
513        int GetPvsEntries(ViewCell *vc) const;
514
515        /** Returns the number of physically stored entries in the view cells sub tree.
516                This can vary based on the current storage method
517        */
518        int CountStoredPvsEntries(ViewCell *root) const;
519
520        /** Returns memory cost of this view cell.
521        */
522        float GetMemoryCost(ViewCell *vc) const;
523
524        /** Sets method of storage for view cells.
525        */
526        void SetViewCellsStorage(int type);
527
528        /** pvs storage methods
529        */
530        enum {PVS_IN_INTERIORS, COMPRESSED, PVS_IN_LEAVES};
531
532        /** If view cells in this tree have compressed pvs.
533        */
534        int ViewCellsStorage() const;
535
536        /** Returns active view cell that is in the path of this view cell.
537        */
538        ViewCell *GetActiveViewCell(ViewCellLeaf *vc) const;
539
540        /** Sets the leaves to be the currently active view cells.
541        */
542    void SetActiveSetToLeaves();
543
544        /** Propagates pvs up the tree to the root and downwards the tree.
545        */
546        void PropagatePvs(ViewCell *vc);
547
548        /** Exports view cells to file.
549        */
550        bool Export(OUT_STREAM &stream, const bool exportPvs = false);
551
552        /** Export statistics of this view cell tree.
553        */
554        void ExportStats(const std::string &mergeStats);
555
556        /** Sets root of hierarchy.
557        */
558        void SetRoot(ViewCell *root);
559
560        /** Assignes unique ids to view cells.
561        */
562        void CreateUniqueViewCellsIds();
563
564        /** Resets pvs of whole tree.
565        */
566        void ResetPvs();
567
568        /** Counts pvs of the view cell taking the kd cells into account.
569        */
570        int CountKdPvs(const ViewCellLeaf *vc) const;
571
572        /** Sets pointer to view cells manager.
573        */
574        void SetViewCellsManager(ViewCellsManager *vcm);
575
576        void Update();
577
578protected:
579
580        /** Reads the environment and sets member variables.
581        */
582        void ReadEnvironment();
583
584
585        //////////////////////////////////////////////////////////////
586        //                    merge related stuff                   //
587        //////////////////////////////////////////////////////////////
588
589
590        /** Computes render cost of the merged pvs.
591        */
592        float ComputeMergedPvsCost(const ObjectPvs &pvs1, const ObjectPvs &pvs2) const;
593
594        /** Returns cost of this leaf according to current heuristics.
595        */
596        float GetCostHeuristics(ViewCell *vc) const;
597
598        /** Returns cost of leaf.
599        */
600        float GetRenderCost(ViewCell *vc) const;
601
602        /** Evaluates the merge cost of this merge candidate pair.
603        */
604        void EvalMergeCost(MergeCandidate &mc) const;
605
606        /** Variance of leaf.
607        */
608        float GetVariance(ViewCell *vc) const;
609
610        /** Standard deviation of leaf.
611        */
612        float GetDeviation(ViewCell *vc) const;
613
614        /** Tries to set this merge candidate to valid.
615                @returns false if both view cells are the same
616        */
617        bool ValidateMergeCandidate(MergeCandidate &mc) const;
618
619        /** Merge view cells of leaves l1 and l2.
620                @returns difference in pvs size
621        */
622        ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, float &pvsDiff);
623
624        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it
625                to view cell 2.
626        */
627        void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;   
628               
629        /** Shuffles the leaves, i.e., tests if exchanging
630                the leaves helps in improving the view cells.
631        */
632        bool ShuffleLeaves(MergeCandidate &mc) const;
633
634        /** Calculates cost for merge of view cell 1 and 2.
635        */
636        float EvalShuffleCost(ViewCell *leaf,
637                                                  ViewCellInterior *vc1,
638                                                  ViewCellInterior *vc2) const;
639
640        /** Exports a snapshot of the merged view cells to disc.
641        */
642        void ExportMergedViewCells(ViewCellContainer &viewCells,
643                                                           const ObjectContainer &objects,
644                                                           const int numNewViewCells);
645
646        /** Merge queue must be reset after some time because expected value
647                may not be valid.
648        */
649        void ResetMergeQueue();
650
651        /** Updates the current cut of view cells.
652                @returns number of newly merged view cells
653        */
654        int UpdateActiveViewCells(ViewCellContainer &viewCells);
655
656        /** Helper function pullling pvs as high up in the tree as possible.
657        */
658        void PullUpVisibility(ViewCellInterior *interior);
659
660        /** Compress pvs of view cell and children.
661        */
662        void CompressViewCellsPvs(ViewCell *root);
663
664        /** Returns memory usage of view cells.
665        */
666        float GetMemUsage() const;
667
668        /**     Exports single view cell.
669                NOTE: should be in exporter!!
670        */
671        void ExportViewCell(ViewCell *viewCell, OUT_STREAM &stream, const bool exportPvs);     
672
673        /** Exports pvs of a view cell.
674        */
675        void ExportPvs(ViewCell *viewCell, OUT_STREAM &stream);
676
677        /** Counts the logical number of entries in the pvs this view cell.
678                The pvs is assumed to be stored using lossless compression.
679        */
680        int GetEntriesInPvsForCompressedStorage(ViewCell *vc) const;
681
682        /** Computes pvs size of this view cell.
683                The pvs is assumed to be stored using lossless compression.
684        */
685        float GetPvsCostForCompressedStorage(ViewCell *vc) const;
686       
687        /** Computes pvs size of this view cell.
688                The pvs is assumed to be stored in the leaves.
689        */
690        float GetPvsCostForLeafStorage(ViewCell *vc) const;
691
692        /** Counts the logical number of entries in the pvs this view cell.
693                The pvs is assumed to be stored using the leaves.
694        */
695        int GetEntriesInPvsForLeafStorage(ViewCell *vc) const;
696
697        /** Update stats for the log.
698        */
699        void UpdateStats(std::ofstream &stats,
700                                         const ViewCellsTreeStats &vcStats);
701
702       
703
704        //////////////////////////////////////
705
706        /// if the view cell tree hold compressed pvs
707        int mViewCellsStorage;
708        /// pointer to the view cells manager
709        ViewCellsManager *mViewCellsManager;
710        /// the root of the view cells hierarchy
711        ViewCell *mRoot;
712
713        /// if merge visualization should be shown
714        bool mExportMergedViewCells;
715        /// intermediate container of merged view cells.
716        ViewCellContainer mMergedViewCells;
717        /// if merged view cells are refined.
718        bool mRefineViewCells;
719        /// weights between variance and render cost increase in the range [0 .. 1].
720        float mRenderCostWeight;
721
722        /// overall cost used to normalize cost ratio
723        float mOverallCost;
724        float mExpectedCost;
725    float mDeviation;
726        float mAvgRenderCost;
727       
728        /// the area is used for pvs heuristics
729        int mUseAreaForPvs;
730        /// number of currently active view cells (=current cut)
731        int mNumActiveViewCells;
732        /// minimal number of view cells
733        int mMergeMinViewCells;
734        /// maximal cost ratio for the merge
735        float mMergeMaxCostRatio;
736
737        typedef std::priority_queue<MergeCandidate> MergeQueue;
738
739        MergeQueue mMergeQueue;
740
741        float mMaxMemory;
742
743        int mMaxMergesPerPass;
744        float mAvgCostMaxDeviation;
745};
746
747
748/**
749        Candidate for leaf merging based on priority.
750*/
751class MergeCandidate
752
753        friend class ViewCellsTree;
754
755public:
756
757        MergeCandidate(ViewCell *l, ViewCell *r);
758
759        /** If this merge pair is still valid.
760        */
761        bool IsValid() const;
762
763       
764        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
765        {
766                return leafb.GetMergeCost() < leafa.GetMergeCost();
767        }
768
769        void SetLeftViewCell(ViewCell *l);
770        void SetRightViewCell(ViewCell *l);
771
772        ViewCell *GetLeftViewCell() const;
773        ViewCell *GetRightViewCell() const;
774
775        /** Returns leaf view cell initially associated with this merge candidate.
776        */
777        ViewCell *GetInitialLeftViewCell() const;
778        /** Returns leaf view cell initially associated with this merge candidate.
779        */
780        ViewCell *GetInitialRightViewCell() const;
781
782        /** Returns the increase of the standard deviation of this merge candidate.
783        */
784        float GetDeviationIncr() const;
785
786        /** Merge cost of this candidate pair.
787        */
788        float GetMergeCost() const;
789
790        /** Render cost of this candidate.
791        */
792        float GetRenderCost() const;
793       
794        static float sRenderCostWeight;
795
796protected:
797
798        /// render cost increase by this merge
799        float mRenderCost;
800        /// increase / decrease of standard deviation
801        float mDeviationIncr;
802
803        ViewCell *mLeftViewCell;
804        ViewCell *mRightViewCell;
805
806        ViewCell *mInitialLeftViewCell;
807        ViewCell *mInitialRightViewCell;
808};
809
810
811class MergeStatistics: public StatisticsBase
812{
813public:
814       
815        int merged;
816        int siblings;
817        int candidates;
818        int nodes;
819
820        int accTreeDist;
821        int maxTreeDist;
822       
823        Real collectTime;
824        Real mergeTime;
825
826        Real overallCost;
827
828        Real expectedRenderCost;
829        Real deviation;
830        Real heuristics;
831
832        // Constructor
833        MergeStatistics()
834        {
835                Reset();
836        }
837       
838        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;};
839
840        void Reset()
841        {
842                nodes = 0;
843                merged = 0;
844                siblings = 0;
845                candidates = 0;
846       
847                accTreeDist = 0;
848                maxTreeDist = 0;
849
850                collectTime = 0;
851                mergeTime = 0;
852                overallCost = 0;
853
854                expectedRenderCost = 0;
855                deviation = 0;
856                heuristics = 0;
857
858        }
859
860        void Print(std::ostream &app) const;
861
862        friend std::ostream &operator<<(std::ostream &s, const MergeStatistics &stat)
863        {
864                stat.Print(s);
865                return s;
866        }
867};
868
869}
870
871#endif
Note: See TracBrowser for help on using the repository browser.