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

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