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

Revision 1707, 19.3 KB checked in by mattausch, 18 years ago (diff)

worked on full render cost evaluation
warning: some change sin render cost evaluation for pvs which could have bugs

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