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

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