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

Revision 1201, 17.9 KB checked in by mattausch, 18 years ago (diff)

added loader for osp trees

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