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

Revision 651, 12.7 KB checked in by mattausch, 19 years ago (diff)

exporting / loading full merge hierarchy

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                                                 
194        // last mail id -> warning not thread safe!
195        // both mailId and mailbox should be unique for each thread!!!
196        static int sMailId;
197        static int sReservedMailboxes;
198       
199        bool mIsActive;
200
201       
202protected:
203
204        /// the potentially visible objects
205        ObjectPvs mPvs;
206
207        float mVolume;
208        float mArea;
209
210        float mMergeCost;
211
212        bool mValid;
213
214  /** color used for consistent visualization */
215  RgbColor mColor;
216};
217
218
219class ViewCellInterior: public ViewCell
220{
221public:
222        ViewCellInterior();
223        ~ViewCellInterior();
224
225        ViewCellInterior(Mesh *mesh);
226       
227
228        /** Sets pointer from parent to child and vice versa.
229        */
230        void SetupChildLink(ViewCell *l);
231        void RemoveChildLink(ViewCell *l);
232        bool IsLeaf() const;
233
234        ViewCellContainer mChildren;
235
236  void SetCost(const float c) {
237        mCost = c;
238  }
239  float GetCost() const {
240        return mCost;
241  }
242 
243protected:
244  /** overall cost resulting from the merge */
245  float mCost;
246};
247
248/**
249        View cell belonging to a hierarchy.
250*/
251template<typename T>
252class ViewCellLeaf: public ViewCell
253{
254public:
255
256        ViewCellLeaf<T>(): mLeaf(NULL) {}
257        ViewCellLeaf<T>(Mesh *mesh):
258                ViewCell(mesh), mLeaf(NULL) {}
259
260       
261
262        bool IsLeaf() const
263        {
264                return true;
265        }
266
267        /// Leaf of some hierarchy which is part of this view cell.
268        T mLeaf;
269};
270
271
272typedef ViewCellLeaf<BspLeaf *> BspViewCell;
273typedef ViewCellLeaf<KdLeaf *> KdViewCell;
274typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell;
275
276
277
278class ViewCellsTree
279{
280        friend class ViewCellsManager;
281public:
282        ViewCellsTree(ViewCellsManager *vcm);
283        ~ViewCellsTree();
284
285        /** Returns number of leaves this view cell consists of.
286        */
287        int GetSize(ViewCell *vc) const;
288
289        /** Collects leaves corresponding to a view cell.
290        */
291        void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
292
293        /** Merges view cells according to some cost heuristics.
294        */
295        int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
296       
297        /** Refines view cells using shuffling, i.e., border leaves
298                of two view cells are exchanged if the resulting view cells
299                are tested to be "better" than the old ones.
300                @returns number of refined view cells
301        */
302        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
303       
304        /** Assign colors to the viewcells so that they can be renderered interactively without
305          color flickering.
306          */
307        void AssignRandomColors();
308
309        /** Updates view cell stats for this particular view cell
310        */
311        void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);
312       
313
314        /** Get costs resulting from each merge step. */
315        void GetCostFunction(vector<float> &costFunction);
316 
317
318        /** Returns optimal set of view cells for a given number of view cells.
319        */
320        void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);
321
322        /** Root of view cells tree.
323        */
324        ViewCell *GetRoot() const;
325
326        /** Returns pvs of view cell.
327                @note pvs is returned per reference if tree is not compressed,
328                per copy else.
329        */
330        void GetPvs(ViewCell *vc, ObjectPvs &pvs) const;
331
332        /** Returns pvs size of view cell.
333        */
334        int GetPvsSize(ViewCell *vc) const;
335
336        /** Returns actual number of object in this pvs and the children.
337        */
338        int GetNumPvsEntries(ViewCell *vc) const;
339
340        /** Returns memory cost of this view cell.
341        */
342        float GetMemoryCost(ViewCell *vc) const;
343
344        /** Compresses the pvs of the view cells from the root.
345        */
346        void CompressViewCellsPvs();
347
348        /** If view cells in this tree have compressed pvs.
349        */
350        bool IsCompressed() const;
351
352        ViewCell *GetActiveViewCell(ViewCell *vc) const;
353
354        /** Propagates pvs up the tree to the root and downwards the tree.
355        */
356        void PropagatePvs(ViewCell *vc);
357
358        bool Export(ofstream &stream);
359
360        /** Export statistics of this view cell tree.
361        */
362        void ExportStats();
363
364        /** Sets root of hierarchy.
365        */
366        void SetRoot(ViewCell *root);
367
368        //float ComputeVolume(ViewCell *vc);
369
370        /** Assignes unique ids to view cells.
371        */
372        void CreateUniqueViewCellsIds();
373
374
375protected:
376
377
378        //////////////////////////////////////////////////////////////
379        //                 merge options                            //
380        //////////////////////////////////////////////////////////////
381       
382
383        /** Returns cost of this leaf according to current heuristics.
384        */
385        float GetCostHeuristics(ViewCell *vc) const;
386
387        /** Returns cost of leaf.
388        */
389        float GetRenderCost(ViewCell *vc) const;
390
391        /** Evaluates the merge cost of this merge candidate pair.
392        */
393        void EvalMergeCost(MergeCandidate &mc) const;
394
395        /** Variance of leaf.
396        */
397        float GetVariance(ViewCell *vc) const;
398
399        /** Standard deviation of leaf.
400        */
401        float GetDeviation(ViewCell *vc) const;
402
403        /** Tries to set this merge candidate to valid.
404                @returns false if both view cells are the same
405        */
406        bool ValidateMergeCandidate(MergeCandidate &mc) const;
407
408        /** Merge view cells of leaves l1 and l2.
409                @returns difference in pvs size
410        */
411        ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;
412
413        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it
414                to view cell 2.
415        */
416        void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;   
417               
418        /** Shuffles the leaves, i.e., tests if exchanging
419                the leaves helps in improving the view cells.
420        */
421        bool ShuffleLeaves(MergeCandidate &mc) const;
422
423        /** Calculates cost for merge of view cell 1 and 2.
424        */
425        float EvalShuffleCost(ViewCell *leaf,
426                                                  ViewCellInterior *vc1,
427                                                  ViewCellInterior *vc2) const;
428
429        /** Exports a snapshot of the merged view cells to disc.
430        */
431        void ExportMergedViewCells(ViewCellContainer &viewCells,
432                                                           const ObjectContainer &objects,
433                                                           const int numNewViewCells);
434
435        /** merge queue must be reset after some time because expected value
436                may not be valid.
437        */
438        void ResetMergeQueue();
439
440        /** Updates the current top level of view cells.
441                @returns number of newly merged view cells
442        */
443        int UpdateActiveViewCells(ViewCellContainer &viewCells);
444
445        void PullUpVisibility(ViewCellInterior *interior);
446
447        void CompressViewCellsPvs(ViewCell *root);
448
449        /** Returns memory usage of view cells.
450        */
451        float GetMemUsage() const;
452       
453        /**
454                Exports single view cell.
455                NOTE: should be in exporter!!
456        */
457        void ExportViewCell(ViewCell *viewCell, ofstream &stream);
458
459
460
461        /// if the view cell tree hold compressed pvs
462        bool mIsCompressed;
463
464        ViewCellsManager *mViewCellsManager;
465        ViewCell *mRoot;
466
467        /// if merge visualization should be shown
468        bool mExportMergedViewCells;
469
470       
471               
472        ViewCellContainer mMergedViewCells;
473       
474
475        bool mRefineViewCells;
476
477        /// weights between variance and render cost increase (must be between zero and one)
478        float mRenderCostWeight;
479
480        /// overall cost used to normalize cost ratio
481        float mOverallCost;
482        float mExpectedCost;
483    float mDeviation;
484        float mAvgRenderCost;
485
486        int mUseAreaForPvs;
487
488        int mNumActiveViewCells;
489
490        /// minimal number of view cells
491        int mMergeMinViewCells;
492        /// maximal cost ratio for the merge
493        float mMergeMaxCostRatio;
494
495        typedef priority_queue<MergeCandidate> MergeQueue;
496
497        MergeQueue mMergeQueue;
498
499        float mMaxMemory;
500
501};
502
503
504/**
505        Candidate for leaf merging based on priority.
506*/
507class MergeCandidate
508
509        friend class ViewCellsTree;
510
511public:
512
513        MergeCandidate(ViewCell *l, ViewCell *r);
514
515        /** If this merge pair is still valid.
516        */
517        bool IsValid() const;
518
519       
520        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
521        {
522                return leafb.GetMergeCost() < leafa.GetMergeCost();
523        }
524
525        void SetLeftViewCell(ViewCell *l);
526        void SetRightViewCell(ViewCell *l);
527
528        ViewCell *GetLeftViewCell() const;
529        ViewCell *GetRightViewCell() const;
530
531        ViewCell *GetInitialLeftViewCell() const;
532        ViewCell *GetInitialRightViewCell() const;
533
534        /** Returns the increase of the standard deviation of this merge candidate.
535        */
536        float GetDeviationIncr() const;
537
538        /** Merge cost of this candidate pair.
539        */
540        float GetMergeCost() const;
541
542        /** Render cost of this candidate.
543        */
544        float GetRenderCost() const;
545       
546        static float sRenderCostWeight;
547
548protected:
549
550        /// render cost increase by this merge
551        float mRenderCost;
552        /// increase / decrease of standard deviation
553        float mDeviationIncr;
554
555        ViewCell *mLeftViewCell;
556        ViewCell *mRightViewCell;
557
558        ViewCell *mInitialLeftViewCell;
559        ViewCell *mInitialRightViewCell;
560};
561
562
563class MergeStatistics: public StatisticsBase
564{
565public:
566       
567        int merged;
568        int siblings;
569        int candidates;
570        int nodes;
571
572        int accTreeDist;
573        int maxTreeDist;
574       
575        Real collectTime;
576        Real mergeTime;
577
578        Real overallCost;
579
580        Real expectedRenderCost;
581        Real deviation;
582        Real heuristics;
583
584        // Constructor
585        MergeStatistics()
586        {
587                Reset();
588        }
589       
590        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;};
591
592        void Reset()
593        {
594                nodes = 0;
595                merged = 0;
596                siblings = 0;
597                candidates = 0;
598       
599                accTreeDist = 0;
600                maxTreeDist = 0;
601
602                collectTime = 0;
603                mergeTime = 0;
604                overallCost = 0;
605
606                expectedRenderCost = 0;
607                deviation = 0;
608                heuristics = 0;
609
610        }
611
612        void Print(ostream &app) const;
613
614        friend ostream &operator<<(ostream &s, const MergeStatistics &stat)
615        {
616                stat.Print(s);
617                return s;
618        }
619};
620
621#endif
Note: See TracBrowser for help on using the repository browser.