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

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