source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h @ 584

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