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

Revision 881, 15.0 KB checked in by mattausch, 19 years ago (diff)

changing concept of active view cells

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