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

Revision 1010, 16.8 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
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
270        float mVolume;
271        float mArea;
272
273        float mMergeCost;
274
275        bool mValid;
276
277        /// color used for consistent visualization
278        RgbColor mColor;
279
280       
281        /// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
282        int mPvsSize;
283        /// if the pvs size scalar is up to date and corresponding to the real pvs size
284        bool mPvsSizeValid;
285
286};
287
288
289class ViewCellInterior: public ViewCell
290{
291        friend class ViewCellsManager;
292public:
293        ViewCellInterior();
294        ~ViewCellInterior();
295
296        ViewCellInterior(Mesh *mesh);
297       
298
299        /** Sets pointer from parent to child and vice versa.
300        */
301        void SetupChildLink(ViewCell *l);
302        void RemoveChildLink(ViewCell *l);
303        bool IsLeaf() const;
304
305        ViewCellContainer mChildren;
306
307  void SetCost(const float c) {
308        mCost = c;
309  }
310  float GetCost() const {
311        return mCost;
312  }
313 
314protected:
315  /** overall cost resulting from the merge */
316  float mCost;
317};
318
319
320/**
321        Leaf of the view cell.
322*/
323class ViewCellLeaf: public ViewCell
324{
325public:
326        ViewCellLeaf()  {  mActiveViewCell = this; }
327        ViewCellLeaf(Mesh *mesh):
328        ViewCell(mesh) { mActiveViewCell = this; }
329
330        bool IsLeaf() const
331        {
332                return true;
333        }
334
335        /** Returns if this view cell is active.
336        */
337        ViewCell *GetActiveViewCell() const
338        { return mActiveViewCell; }
339
340        /** Sets this view cell to be an active view cell.
341        */
342        void SetActiveViewCell(ViewCell *vc)
343        { mActiveViewCell = vc;}
344
345       
346        /** points to the currently active view cell. This is the
347                view cell representing the current brach.
348        */
349        ViewCell *mActiveViewCell;
350};
351
352/**
353        Leaf of the view cell hierarchy corresponding to a leaf in a spatial hierarchy.
354*/
355template<typename T>
356class HierarchyLeafViewCell: public ViewCellLeaf
357{
358public:
359
360        HierarchyLeafViewCell<T>(): ViewCellLeaf() {  }
361        HierarchyLeafViewCell<T>(Mesh *mesh):
362        ViewCellLeaf(mesh) {  }
363               
364
365        bool IsLeaf() const
366        {
367                return true;
368        }
369
370
371        /// Leaf of some hierarchy which is part of this view cell.
372        T mLeaf;
373};
374
375
376typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
377typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
378typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;
379
380
381
382
383class ViewCellsTree
384{
385        friend class ViewCellsManager;
386
387
388public:
389        /** View cells tree constructor taking a view cell mnanager as parameter
390        */
391        ViewCellsTree(ViewCellsManager *vcm);
392        ~ViewCellsTree();
393
394        /** Returns number of leaves this view cell consists of.
395        */
396        int GetNumInitialViewCells(ViewCell *vc) const;
397
398        /** Collects leaves corresponding to a view cell.
399        */
400        void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
401
402        /** Merges view cells according to some cost heuristics.
403        */
404        int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
405       
406        /** Refines view cells using shuffling, i.e., border leaves
407                of two view cells are exchanged if the resulting view cells
408                are tested to be "better" than the old ones.
409                @returns number of refined view cells
410        */
411        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
412       
413        /** Assign colors to the viewcells so that they can be renderered interactively without
414            color flickering. 
415        */
416        void AssignRandomColors();
417
418        /** Updates view cell stats for this particular view cell.
419        */
420        void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);
421
422
423        /** Get costs resulting from each merge step.
424        */
425        void GetCostFunction(vector<float> &costFunction);
426
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
446        /** Returns actual number of object in this pvs and the children.
447        */
448        int GetNumPvsEntries(ViewCell *vc) const;
449
450        /** Returns memory cost of this view cell.
451        */
452        float GetMemoryCost(ViewCell *vc) const;
453
454        /** Sets method of storage for view cells.
455        */
456        void SetViewCellsStorage(int type);
457
458        /** pvs storage methods
459        */
460        enum {PVS_IN_INTERIORS, COMPRESSED, PVS_IN_LEAVES};
461
462       
463        /** If view cells in this tree have compressed pvs.
464        */
465        int ViewCellsStorage() const;
466
467        /** Returns active view cell that is in the path of this view cell.
468        */
469        ViewCell *GetActiveViewCell(ViewCellLeaf *vc) const;
470
471        /** Sets the leaves to be the currently active view cells.
472        */
473    void SetActiveSetToLeaves();
474
475        /** Propagates pvs up the tree to the root and downwards the tree.
476        */
477        void PropagatePvs(ViewCell *vc);
478
479        /** Exports view cells to file.
480        */
481#if ZIPPED_VIEWCELLS
482        bool Export(ogzstream &stream, const bool exportPvs = false);
483#else
484        bool Export(ofstream &stream, const bool exportPvs = false);
485#endif
486
487        /** Export statistics of this view cell tree.
488        */
489        void ExportStats(const string &mergeStats);
490
491        /** Sets root of hierarchy.
492        */
493        void SetRoot(ViewCell *root);
494
495        //float ComputeVolume(ViewCell *vc);
496
497        /** Assignes unique ids to view cells.
498        */
499        void CreateUniqueViewCellsIds();
500
501        /** Resets pvs of whole tree.
502        */
503        void ResetPvs();
504
505protected:
506
507
508        /////////////////////////////////////////////////////////////////
509        //                    merge related stuff                      //
510        /////////////////////////////////////////////////////////////////
511
512        /** Computes render cost of the merged pvs.
513        */
514        float ComputeMergedPvsCost(const ObjectPvs &pvs1, const ObjectPvs &pvs2) const;
515
516        /** Returns cost of this leaf according to current heuristics.
517        */
518        float GetCostHeuristics(ViewCell *vc) const;
519
520        /** Returns cost of leaf.
521        */
522        float GetRenderCost(ViewCell *vc) const;
523
524        /** Evaluates the merge cost of this merge candidate pair.
525        */
526        void EvalMergeCost(MergeCandidate &mc) const;
527
528        /** Variance of leaf.
529        */
530        float GetVariance(ViewCell *vc) const;
531
532        /** Standard deviation of leaf.
533        */
534        float GetDeviation(ViewCell *vc) const;
535
536        /** Tries to set this merge candidate to valid.
537                @returns false if both view cells are the same
538        */
539        bool ValidateMergeCandidate(MergeCandidate &mc) const;
540
541        /** Merge view cells of leaves l1 and l2.
542                @returns difference in pvs size
543        */
544        ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;
545
546        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it
547                to view cell 2.
548        */
549        void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;   
550               
551        /** Shuffles the leaves, i.e., tests if exchanging
552                the leaves helps in improving the view cells.
553        */
554        bool ShuffleLeaves(MergeCandidate &mc) const;
555
556        /** Calculates cost for merge of view cell 1 and 2.
557        */
558        float EvalShuffleCost(ViewCell *leaf,
559                                                  ViewCellInterior *vc1,
560                                                  ViewCellInterior *vc2) const;
561
562        /** Exports a snapshot of the merged view cells to disc.
563        */
564        void ExportMergedViewCells(ViewCellContainer &viewCells,
565                                                           const ObjectContainer &objects,
566                                                           const int numNewViewCells);
567
568        /** Merge queue must be reset after some time because expected value
569                may not be valid.
570        */
571        void ResetMergeQueue();
572
573        /** Updates the current top level of view cells.
574                @returns number of newly merged view cells
575        */
576        int UpdateActiveViewCells(ViewCellContainer &viewCells);
577
578        /** Helper function pullling pvs as high up in the tree as possible.
579        */
580        void PullUpVisibility(ViewCellInterior *interior);
581
582        /** Compress pvs of view cell and children.
583        */
584        void CompressViewCellsPvs(ViewCell *root);
585
586        /** Returns memory usage of view cells.
587        */
588        float GetMemUsage() const;
589
590        /**     Exports single view cell.
591                NOTE: should be in exporter!!
592        */
593#if ZIPPED_VIEWCELLS
594        void ExportViewCell(ViewCell *viewCell, ogzstream &stream, const bool exportPvs);
595#else
596        void ExportViewCell(ViewCell *viewCell, ofstream &stream, const bool exportPvs);       
597#endif
598
599        /** Exports pvs of a view cell.
600        */
601#if ZIPPED_VIEWCELLS
602        void ExportPvs(ViewCell *viewCell, ogzstream &stream);
603#else
604        void ExportPvs(ViewCell *viewCell, ofstream &stream);
605#endif
606
607
608        /// if the view cell tree hold compressed pvs
609        int mViewCellsStorage;
610
611        ViewCellsManager *mViewCellsManager;
612        ViewCell *mRoot;
613
614        /// if merge visualization should be shown
615        bool mExportMergedViewCells;
616
617       
618        /// intermediate container of merged view cells.
619        ViewCellContainer mMergedViewCells;
620       
621
622        /// if merged view cells are refined.
623        bool mRefineViewCells;
624
625        /// weights between variance and render cost increase (must be between zero and one)
626        float mRenderCostWeight;
627
628        /// overall cost used to normalize cost ratio
629        float mOverallCost;
630        float mExpectedCost;
631    float mDeviation;
632        float mAvgRenderCost;
633        /// the area is used for pvs heuristics
634        int mUseAreaForPvs;
635
636        int mNumActiveViewCells;
637
638        /// minimal number of view cells
639        int mMergeMinViewCells;
640        /// maximal cost ratio for the merge
641        float mMergeMaxCostRatio;
642
643        typedef priority_queue<MergeCandidate> MergeQueue;
644
645        MergeQueue mMergeQueue;
646
647        float mMaxMemory;
648
649        int mMaxMergesPerPass;
650        float mAvgCostMaxDeviation;
651};
652
653
654/**
655        Candidate for leaf merging based on priority.
656*/
657class MergeCandidate
658
659        friend class ViewCellsTree;
660
661public:
662
663        MergeCandidate(ViewCell *l, ViewCell *r);
664
665        /** If this merge pair is still valid.
666        */
667        bool IsValid() const;
668
669       
670        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
671        {
672                return leafb.GetMergeCost() < leafa.GetMergeCost();
673        }
674
675        void SetLeftViewCell(ViewCell *l);
676        void SetRightViewCell(ViewCell *l);
677
678        ViewCell *GetLeftViewCell() const;
679        ViewCell *GetRightViewCell() const;
680
681        /** Returns leaf view cell initially associated with this merge candidate.
682        */
683        ViewCell *GetInitialLeftViewCell() const;
684        ViewCell *GetInitialRightViewCell() const;
685
686        /** Returns the increase of the standard deviation of this merge candidate.
687        */
688        float GetDeviationIncr() const;
689
690        /** Merge cost of this candidate pair.
691        */
692        float GetMergeCost() const;
693
694        /** Render cost of this candidate.
695        */
696        float GetRenderCost() const;
697       
698        static float sRenderCostWeight;
699
700protected:
701
702        /// render cost increase by this merge
703        float mRenderCost;
704        /// increase / decrease of standard deviation
705        float mDeviationIncr;
706
707        ViewCell *mLeftViewCell;
708        ViewCell *mRightViewCell;
709
710        ViewCell *mInitialLeftViewCell;
711        ViewCell *mInitialRightViewCell;
712};
713
714
715class MergeStatistics: public StatisticsBase
716{
717public:
718       
719        int merged;
720        int siblings;
721        int candidates;
722        int nodes;
723
724        int accTreeDist;
725        int maxTreeDist;
726       
727        Real collectTime;
728        Real mergeTime;
729
730        Real overallCost;
731
732        Real expectedRenderCost;
733        Real deviation;
734        Real heuristics;
735
736        // Constructor
737        MergeStatistics()
738        {
739                Reset();
740        }
741       
742        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;};
743
744        void Reset()
745        {
746                nodes = 0;
747                merged = 0;
748                siblings = 0;
749                candidates = 0;
750       
751                accTreeDist = 0;
752                maxTreeDist = 0;
753
754                collectTime = 0;
755                mergeTime = 0;
756                overallCost = 0;
757
758                expectedRenderCost = 0;
759                deviation = 0;
760                heuristics = 0;
761
762        }
763
764        void Print(ostream &app) const;
765
766        friend ostream &operator<<(ostream &s, const MergeStatistics &stat)
767        {
768                stat.Print(s);
769                return s;
770        }
771};
772
773}
774
775#endif
Note: See TracBrowser for help on using the repository browser.