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

Revision 703, 13.2 KB checked in by mattausch, 19 years ago (diff)

started implementation of visibility filter

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