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

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

resolved coflicts
improved memory constant

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