source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h @ 2571

#ifndef _ViewCellsManager_H__
#define _ViewCellsManager_H__

#include "Ray.h"
#include "SimpleRay.h"
#include "VssRay.h"
#include "Containers.h"
#include "ViewCell.h"

#define TEST_PACKETS 0

namespace GtpVisibilityPreprocessor {

class ViewCell;
class Intersectable;
class RenderSimulator;
class Renderer;
class Mesh;
struct Triangle3;
class SimulationStatistics;
class BspTree;
class KdTree;
class VspOspTree;
class VspBspTree;
class KdNode;
class KdLeaf;
class AxisAlignedBox3;
class BspLeaf;
class ViewCellsStatistics;
class Exporter;
class Beam;
class Preprocessor;
class ViewCellsTree;
class MergeCandidate;
class BoundingBoxConverter;
class VspTree;
class OspTree;
class VspNode;
class HierarchyManager;
class BvHierarchy;
class ViewCellsTree;
class ViewCell;
class MixtureDistribution;
struct AxisAlignedPlane;
struct BspRay;
class BspTree;



struct PvsFilterStatistics 
{
        PvsFilterStatistics(): 
        mAvgFilterRadius(0.0f), mLocalFilterCount(0), mGlobalFilterCount(0) {}
        
        float mAvgFilterRadius;
        int mLocalFilterCount;
        int mGlobalFilterCount;
};

/** Probably Visible Set 
*/
class PrVs 
{
public:
        /// root of view cells tree
        ViewCell *mViewCell;
        // input parameter is the render budget for the PrVs
        float mRenderBudget;
};


class LocalMergeNode
{
public:
        virtual ~LocalMergeNode() {};
        virtual bool IsLeaf() const = 0;
};

typedef pair<ViewCell *, SimpleRayContainer> ViewCellPoints;

struct VizBuffer
{
        VizBuffer(): mIndex(0), mMaxSize(10000)
        {
        }

        int GetSize() const {return (int)mVizRays.size();}

        void AddRay(VssRay *ray)
        {
                if (mVizRays.size() < mMaxSize)
                        mVizRays.push_back(ray);
                else
                        mVizRays[mIndex] = ray;
                
                mIndex = (mIndex + 1) % mMaxSize;
        }

        VssRayContainer &GetRays() { return mVizRays;}

        VssRay *GetRay(int i) { return mVizRays[i % 100];}

protected:

        const int mMaxSize;
        int mIndex;
        VssRayContainer mVizRays;
};


/**     Manages different higher order operations on the view cells.
*/
class ViewCellsManager
{
public:

        struct PerViewCellStat 
        {
                float pvsSize;
                float relPvsIncrease;
        };

        struct SamplesStatistics 
        {
                int mRays;
                int mViewCells;
                int mContributingRays;
                int mPvsContributions;
                void Reset() 
                {
                        mRays = 0;
                        mViewCells = 0;
                        mContributingRays = 0;
                        mPvsContributions = 0;
                };
        };

        struct PvsStatistics 
        {
                float minPvs;
                float maxPvs;
                float avgPvs;
                float renderCost;
                float avgPvsEntries;

                float avgFilteredPvs;
                float avgFilteredPvsEntries;

                float avgFilterContribution;
                float avgFilterRadius;
                float avgFilterRatio;
                float avgRelPvsIncrease;
                float devRelPvsIncrease;
                int viewcells;

                float mem;
                float renderCostRatio;
        };
  
        /// view cell container types
        enum {BSP, KD, VSP_KD, VSP_BSP, VSP_OSP};
  
        /// render cost evaluation type
        enum {PER_OBJECT, PER_TRIANGLE};

        friend class X3dViewCellsParseHandlers;

        /** Default constructor.
        */
        ViewCellsManager(ViewCellsTree *viewCellsTree);
        /** Destructor.
        */
        virtual ~ViewCellsManager();
        /** Constructs view cells container taking a preprocessor
                @returns the output rays (if not null)
        */ 
        int Construct(Preprocessor *preprocessor, VssRayContainer *outRays = NULL);

        /** Constructs view cell container with a given number of samples.
        */
        virtual int ConstructSubdivision(const ObjectContainer &objects,
                                                                         const VssRayContainer &rays) = 0;

        /** Computes sample contributions of the rays to the view cells PVS.
        
                @param rays bundle of rays used to find intersections with view cells and 
                adding the contribution
                @param addRays true if rays should be added to the PVSs of the viewcells they
                intersect 
                @param storeViewCells true if view cells should be stored in the ray
        */
        virtual float ComputeSampleContributions(const VssRayContainer &rays,
                                                     const bool addContributions,
                                                                                         const bool storeViewCells,
                                                                                         const bool useHitObject = false);

        /** Computes sample contribution of a simgle ray to the view cells PVS.
                @param ray finds intersections with view cells and holds the contribution
                @param addSample if sample should be added to the pvs
                  
                @returns number of sample contributions
        */
        virtual float ComputeSampleContribution(VssRay &ray, 
                                                                                        const bool addContributions,
                                                                                        const bool storeViewCells,
                                                                                        const bool useHitObject = false);
        /** Compute sample contribution only for current view cell.
        */
        virtual float ComputeSampleContribution(VssRay &ray, 
                                                                                        const bool addContributions,
                                                                                        ViewCell *currentViewCell,
                                                                                        const bool useHitObject = false);
        /** Prints out statistics of the view cells.
        */
        virtual void PrintStatistics(std::ostream &s) const;
        /** Post processes view cells givemŽa number of rays.
        */
        virtual int PostProcess(const ObjectContainer &objects, 
                                                        const VssRayContainer &rays) = 0;
        /** Show visualization of the view cells.
        */
        virtual void Visualize(const ObjectContainer &objects,
                                                   const VssRayContainer &sampleRays) = 0;
        /** collect objects intersecting a given spatial box.
        */
        virtual void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
        /** type of the view cell container.
        */
        virtual int GetType() const = 0;
        /** Load the input viewcells. The input viewcells should be given as a collection
                of meshes. Each mesh is assume to form a bounded polyhedron 
                defining the interior of the viewcell. The view cells manager
                is responsible for building a hierarchy over these view cells.
                
                @param filename file to load
                @return true on success
        */
        virtual bool LoadViewCellsGeometry(const string filename, const bool extrudeBaseTriangle);
        /** Merges two view cells.
                @note the piercing rays of the front and back will be ordered   
                @returns new view cell based on the merging.
        */
        ViewCellInterior *MergeViewCells(ViewCell *front, ViewCell *back) const;
        /** Merges a container of view cells.
                @returns new view cell based on the merging.
        */
        ViewCellInterior *MergeViewCells(ViewCellContainer &children) const;
        /** Generates view cell of the type specified by this manager
        */
        virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;
        /** Constructs view cell from base triangle. 
                The view cell is extruded along the normal vector.
                @param the base triangle
                @param the height of the newly created view cell
        */
        ViewCell *ExtrudeViewCell(const Triangle3 &baseTri, const float height) const;
        /** Returns the intersectable that was hit by the ray.
        */
        virtual Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) const;
        /** Sets maximal number of samples used for the 
                construction of the view cells.
        */
        void SetVisualizationSamples(const int visSamples);
        /** Sets maximal number of samples used for the construction of the view cells.
        */
        void SetConstructionSamples(const int constructionSamples);
        /** Sets maximal number of samples used for the visualization of the view cells.
        */
        void SetInitialSamples(const int initialSamples);
        /** Sets maximal number of samples used for the post processing of the view cells.
        */
        void SetPostProcessSamples(const int postProcessingSamples);
        /** See set.
        */
        int GetVisualizationSamples() const;
        /** See set.
        */
        int GetConstructionSamples() const;
        /** See set.
        */
        int GetPostProcessSamples() const;
        /** Returns true if view cells are already constructed.
        */
        virtual bool ViewCellsConstructed() const = 0;
        /** cast line segment to get a list of unique viewcells which are intersected
                by this line segment 
        */
        virtual int CastLineSegment(const Vector3 &origin,
                                                            const Vector3 &termination,
                                                            ViewCellContainer &viewcells) = 0;
        /** Tests if this line segment intersects a particular view cell.
        */
        virtual bool LineSegmentIntersects(const Vector3 &origin,
                                                                           const Vector3 &termination,
                                                                           ViewCell *viewCell) = 0;
        /** Returns a stats about the global pvs.
        */
        virtual void GetPvsStatistics(PvsStatistics &stat);
        /** Returns the probably visible set of the view space filtered pvs.
        */
        virtual void GetPrVS(const Vector3 &viewPoint, PrVs &prvs, const float filterWidth);
        /** Get a viewcell containing the specified view point.
                @param active if the active or elementary view cell should be returned.
        */
        virtual ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const = 0;
        /** Returns the view cell with the given index (different from the id).
        */
        ViewCell *GetViewCell(const int idx) const {return mViewCells[idx];}
        /** Prints the statistics over the view cell pvss.
        */
        virtual void PrintPvsStatistics(std::ostream &s);
        /** Updates pvs of the view cell hierarchy if necessary.
        */
        void UpdatePvs();
        /** Returns probability that view point lies in one view cell.
        */
        virtual float GetProbability(ViewCell *viewCell) = 0;
        /** Returns render cost of a single view cell given the render cost of an object.
        */
        float GetRendercost(ViewCell *viewCell) const;
        /** Returns reference to container of loaded / generated view cells.
        */
        ViewCellContainer &GetViewCells();
        /** Helper function used to split ray sets uniformly 
                into one that is currently used and the other that 
                is saved for later processing.
                @param sourceRays the input ray set
                @param maxSize the maximal number of rays that will be used
                @param usedRays returns the used ray set
                @param savedRays if not null, returns the saved ray set
        */
        void GetRaySets(const VssRayContainer &sourceRays,
                                        const int maxSize,
                                        VssRayContainer &usedRays, 
                                        VssRayContainer *savedRays = NULL) const;
        /** Returns accumulated area of all view cells.
        */
        float GetAccVcArea();
        /** Returns area of one view cell.
        */
        virtual float GetArea(ViewCell *viewCell) const;
        /** Returns volume of view cell.
        */
        virtual float GetVolume(ViewCell *viewCell) const;
        /** Sets the current renderer mainly for view cells statistics.
        */
        void SetRenderer(Renderer *renderer);
        /** Computes a (random) view point in the valid view space.
                @returns true if valid view point was found
        */
        virtual bool GetViewPoint(Vector3 &viewPoint) const;
        /** Returns the current view point given a vector for activating the halton sequence.
        */
        virtual bool GetViewPoint(Vector3 &viewPoint, const Vector3 &params) const;
        /** Returns true if this view point is in the valid view space.
        */
        virtual bool ViewPointValid(const Vector3 &viewPoint) const;
        /** Sets a view space boundary.
        */
        void SetViewSpaceBox(const AxisAlignedBox3 &box);
        /** Returns the boundaries of the view space.
        */
        AxisAlignedBox3 GetViewSpaceBox() const;
        /** Creates mesh for this view cell.
        */
        virtual void CreateMesh(ViewCell *vc) = NULL;
        /** Writes view cells to disc.
        */
        virtual bool ExportViewCells(const string filename, 
                                                                 const bool exportPvs, 
                                                                 const ObjectContainer &objects);
        /** Casts beam to collect view cells.
        */
        virtual int CastBeam(Beam &beam);
        /** Checks if view cell is considered as valid.
        */
        virtual bool CheckValidity(ViewCell *vc, 
                                                           int minPvsSize, 
                                                           int maxPvsSize) const;
        /** Resort pvss after a pass of the algorithm.
        */
        void  SortViewCellPvs();
        /** Map the ray intersection objects from triangles to high level objects.
        */
        void DeterminePvsObjects(VssRayContainer &rays,
                                                         const bool useHitObjects = false);
        /** Sets validity of view cell
        */
        virtual void SetValidity(ViewCell *vc, 
                                                         int minPvsSize, 
                                                         int maxPvsSize) const;
        /** sets validy of all viewcells 
        */
        virtual void SetValidity(int minPvsSize, int maxPvsSize) const;
        /** Set valid viewcells in the range of pvs. sorts the viewcells
                according to the pvs and then pickups those in the ranges 
        */
        void SetValidityPercentage(const float minValid, const float maxValid);
        /** Returns number of valid view cells.
        */
    int CountValidViewcells() const;
        /** Returns maximal allowed pvs size.
        */
        int GetMaxPvsSize() const;
        /** Returns maximal allowed pvs size.
        */
        int GetMinPvsSize() const;
        /** Returns maximal ratio. i.e., currentPVs / maxPvs,
                where pvs is still considered valid.
        */
        float GetMaxPvsRatio() const;
        /** Exports view cell geometry.
        */
        virtual void ExportViewCellGeometry(Exporter *exporter,
                                                                                ViewCell *vc,
                                                                                const AxisAlignedBox3 *box,
                                                                                const AxisAlignedPlane *clipPlane = NULL
                                                                                ) const = 0;
        /** Brings the view cells into their final state, computes meshes and volume.
        */
        virtual void FinalizeViewCells(const bool createMesh);
        /** Evaluates statistics values on view cells.
        */
        void EvaluateRenderStatistics(float &totalRenderCost,
                                                                  float &expectedRenderCost,
                                                                  float &deviation,
                                                                  float &variance,
                                                                  float &totalPvs,
                                                                  float &avgRenderCost);
        /** Returns hierarchy of the view cells.
        */
        ViewCellsTree *GetViewCellsTree();
        /** Collect candidates for the view cell merge.
        */
        virtual void CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                vector<MergeCandidate> &candidates);
        /** Collects n view cells and stores it as the active view cells.
        */
        void CollectViewCells(const int n);
        /** Sets current view cells set to active, 
                i.e., the sampling is done in this view cell set.
        */
        void SetViewCellsActive();
        /** Evaluates render cost statistics of current view cell hierarchy.
        */
        virtual void EvalViewCellPartition();
        /** Sets maximal size of a view cell filter.
        */
        void SetMaxFilterSize(const int size);
        /** Returns maximal filter size.
        */
        int GetMaxFilterSize() const;
        /** Deletes interior nodes from the tree which have negative 
                merge cost set (local merge).
        */  
        void DeleteLocalMergeTree(ViewCell *vc) const;
        /** Evaluautes histogram for a given number of view cells.
        */
        void EvalViewCellHistogram(const string filename, const int nViewCells);
        /** Evaluautes histogram for a given number of view cells.
        */
        void EvalViewCellHistogramForPvsSize(const string filename, 
                                                                                 const int nViewCells);
        /** Evaluautes histogram for a given vector of view cells.
        */
        void EvalViewCellHistogramForPvsSize(const string filename, 
                                                                                 ViewCellContainer &viewCells);
        float ComputeRenderCost(const int tri, const int obj); //const
        /** Sets pvs size of a view cell as a scalar. Used when storing pvs only in the leaves
                of the hierarchy.
        */
        void UpdateScalarPvsSize(ViewCell *vc, 
                                                         const float pvsCost, 
                                                         const int entriesInPvs) const;
        /** Sets render cost of a view cell as a scalar.
        */
        void UpdateScalarPvsCost(ViewCell *vc, const float pvsCost) const;

        /** Returns bounding box of a view cell.
        */
        AxisAlignedBox3 GetViewCellBox(ViewCell *vc);
        /** Exports bounding boxes of objects to file.
        */
        bool ExportBoundingBoxes(const string filename, 
                                                         const ObjectContainer &objects) const;
        /** Load the bounding boxes into the container.
        */
        bool LoadBoundingBoxes(const string filename, 
                                                  IndexedBoundingBoxContainer &boxes) const;
        /** Returns true if pvs should be exported together with the view cells.
        */
        bool GetExportPvs() const;
        /** Efficiently merges the view cells in the container.
        */
        void MergeViewCellsRecursivly(ObjectPvs &pvs, 
                                                                  const ViewCellContainer &viewCells) const;
        /** Compresses the view cells.
        */
        virtual void CompressViewCells();
        /** Returns view cell with the given id.
        */
        ViewCell *GetViewCellById(const int id);
        /** Returns number of view cells.
        */
        int GetNumViewCells() const;

        bool GenerateRandomViewCells(ViewCellContainer &viewCells, 
                                                                 const int numViewCells);

        bool GenerateRandomViewCells(vector<ViewCellPoints *> &viewCells,
                                                                 const int nViewCells,
                                                                 const int nViewPoints);


        bool GenerateViewPoints(ViewCell *viewCell, 
                                                        const int numViewPoints,
                                                        SimpleRayContainer &viewPoints);

        bool ImportRandomViewCells(const string &filename, 
                                                           vector<ViewCellPoints *> &viewCells);

        bool ImportRandomViewCells(const string &filename);

        bool ExportRandomViewCells(const string &filename,
                                                           const vector<ViewCellPoints *> &viewCells);

        bool ExportRandomViewCells(const string &filename);

        bool GenerateViewPoint(ViewCell *viewCell, SimpleRay &ray);

        bool IsValidViewSpace(ViewCell *vc);


        //////////////
        // static members
        
        /** Loads view cells from file. The view cells manager is created with 
                respect to the loaded view cells.

                @param filename the filename of the view cells
                @param objects the scene objects
                @param finalizeViewCells if the view cells should be post processed, i.e.,
                           a mesh is created representing the geometry
                @param bconverter a conversion routine working with the similarities of bounding
                           boxes: if there is a certain similarity of overlap between 
                           bounding boxes, two tested candidate objects are considered 
                           to be the same objects
                @returns the view cells manager if loading was successful, false otherwise
        */
        static ViewCellsManager *LoadViewCells(const string &filename, 
                                                                                   ObjectContainer &pvsObjects,
                                                                                   ObjectContainer &preprocessorObjects,
                                                                                   bool finalizeViewCells = false,
                                                                                   BoundingBoxConverter *bconverter = NULL);

        /** Convenience function assuming that there are no preprocessor objects.
        */
        static ViewCellsManager *LoadViewCells(const string &filename, 
                                                                                   ObjectContainer &pvsObjects,
                                                                                   bool finalizeViewCells = false,
                                                                                   BoundingBoxConverter *bconverter = NULL);


        ///////////////////////
        //-- visiblity filter options

        // TODO: write own visibiltiy filter class
        void ApplyFilter(KdTree *kdTree,
                                         const float viewSpaceFilterSize,
                                         const float spatialFilterSize);

        // new adaptive version of the filter
        PvsFilterStatistics ApplyFilter2(ViewCell *viewCell,
                                                                         const bool useViewSpaceFilter,
                                                                         const float filterSize,
                                                                         ObjectPvs &pvs,
                                                                         vector<AxisAlignedBox3> *filteredBoxes = NULL);

        void ApplySpatialFilter(KdTree *kdTree,
                                                        const float spatialFilterSize,
                                                        ObjectPvs &pvs);

         void ApplyFilter(ViewCell *viewCell,
                                          KdTree *kdTree,
                                          const float viewSpaceFilterSize,
                                          const float spatialFilterSize,
                                          ObjectPvs &pvs);

        float GetFilterWidth();

        float GetAbsFilterWidth();
        /** Returns the bounding box of filter width.
        */
        AxisAlignedBox3 GetFilterBBox(const Vector3 &viewPoint, 
                                                                  const float width) const;



        //////////////////////////////////////////////////////////////////


        /** If true, the kd nodes are stored instead of the object pvs.
        */
        void SetStoreKdPvs(const bool storeKdPvs);

        /** Returns true if the kd nodes are stored instead of the object pvs.
        **/
        bool GetStoreKdPVs() const;

        /** Exports single view cells for visualization.
                @param objects the scene objects
                @param limit the maximal number of output view cells
                @param sortViewCells if the view cells should be sorted by pvs size
                @param exportPvs if the pvs should also be exported
                @param exportRays if sample rays should be exported as well
                @param maxRays maximum number of rays to export
                @param prefix the prefix for the output file
                @param visRays additional rays
        */
        virtual void ExportSingleViewCells(const ObjectContainer &objects,
                                                                           const int maxViewCells,
                                                                           const bool sortViewCells,
                                                                           const bool exportPvs,
                                                                           const bool exportRays,
                                                                           const int maxRays,
                                                                           const string &prefix,
                                                                           VssRayContainer *visRays = NULL) = NULL;


        void ResetPvs();

        Preprocessor *GetPreprocessor() const 
        {
                return mPreprocessor;
        }

        void SetPreprocessor(Preprocessor *p) 
        {
                mPreprocessor = p;
        }

        vector<ViewCellPoints *> *GetViewCellPoints()
        {
                return &mViewCellPoints;
        }

        void UpdatePvsForEvaluation();


        VizBuffer mVizBuffer;


protected:

        void ComputeViewCellContribution(ViewCell *viewCell,
                                                                         VssRay &ray, 
                                                                         Intersectable *obj,
                                                                         const Vector3 &pt,
                                                                         const bool addRays);

        void MergeViewCellsRecursivly(ObjectPvs &pvs, 
                                                                  const ViewCellContainer &viewCells, 
                                                                  const int leftIdx, 
                                                                  const int rightIdx) const;
        /** Intersects box with the tree and returns the number of intersected boxes.
                @returns number of view cells found
        */
        virtual int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                                ViewCellContainer &viewCells) const;
        /** Tests the visibility filter functionality.
        */
        virtual void TestFilter(const ObjectContainer &objects) {};
        /** If the view cells tree was already constructed or not.
        */
        bool ViewCellsTreeConstructed() const;
        /** Requests preprocessor to cast samplesPerPass samples of a specific type.
        */
        int CastPassSamples(const int samplesPerPass, 
                                                const vector<int> &strategies,
                                                VssRayContainer &vssRays) const;
        /** cast samples for the purpose of evaluating the view cells solution
        */
        int CastEvaluationSamples(const int samplesPerPass, 
                                                          VssRayContainer &passSamples);// const;
        /** Parse the options from the environment file.
        */
        void ParseEnvironment();
        /** Creates unique view cell ids.
        */
        void CreateUniqueViewCellIds();
        /** Finalizes, i.e., creates mesh, volume, area etc. for the view cell.
        */
        virtual void Finalize(ViewCell *viewCell, const bool createMesh);
        /** Recollects view cells and resets statistics.
        */
        void ResetViewCells();
        /** Sets this view cell to active.
        */
        void SetViewCellActive(ViewCell *vc) const;
        /** Collects the view cells in the view cell container.
        */
        virtual void CollectViewCells() = 0;
        /** Evaluates view cells statistics and stores it in mViewCellsStatistics.
        */
        void EvaluateViewCellsStats();
        

        void UpdateStatsForViewCell(ViewCell *viewCell, Intersectable *obj);


        ///////////////////////
        //-- helper functions for view cell visualization

        /** Exports the view cell partition.
        */
        void ExportViewCellsForViz(Exporter *exporter, 
                                                           const AxisAlignedBox3 *box,
                                                           const bool colorCode,
                                                           const AxisAlignedPlane *clipPlane) const;
        /** Sets exporter color.
        */
        virtual void ExportColor(Exporter *exporter, 
                                                         ViewCell *vc, 
                                                         const int colorCode) const;
        /** Creates meshes from the view cells.
        */
        void CreateViewCellMeshes();
        /** Creates clip plane for visualization.
        */
        void CreateClipPlane();

        AxisAlignedPlane *GetClipPlane();

        void ExportMergedViewCells(const ObjectContainer &objects);


        ///////////////////////

        /** Returns volume of the view space.
        */
        virtual float GetViewSpaceVolume();
        /** Prepares the view cells for sampling after loading them from disc.
        */
        virtual void PrepareLoadedViewCells() {};
        /** Constructs local view cell merge hierarchy.
        */
        ViewCell *ConstructLocalMergeTree(ViewCell *currentViewCell, 
                                          const ViewCellContainer &viewCells);
        /** Constructs local view cell merge hierarchy based solely on similarity with the
                current viewcell
        */
        ViewCell *ConstructLocalMergeTree2(ViewCell *currentViewCell, 
                                                                           const ViewCellContainer &viewCells);
        /** Updates pvs of all view cells for statistical evaluation after some more sampling
        */
        void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);
        /** Export statistics of the view cells tree.
        */
        virtual void ExportStats(const string &mergeStats);
        /** Loads view cells in binary mode.
        */
        static ViewCellsManager *LoadViewCellsBinary(const string &filename, 
                                                                                                 ObjectContainer &pvsObjects,
                                                                                                 bool finalizeViewCells,
                                                 BoundingBoxConverter *bconverter);
        /** This helper function loads the bounding boxes for a binary solution.
        */
        static void LoadIndexedBoundingBoxesBinary(IN_STREAM &stream, 
                                                       IndexedBoundingBoxContainer &iboxes);



        ///////////
        //-- members

        ofstream mStats;
        Preprocessor *mPreprocessor;
        /// if bounding boxes should be exported together with the view cells
        bool mExportBboxesForPvs;
        /// the clip plane for visualization
        AxisAlignedPlane mClipPlaneForViz;
        /// if the visualization is using the clip plane
        bool mUseClipPlaneForViz;
        /// Renders the view cells.
        Renderer *mRenderer;
        /// Loaded view cells
        ViewCellContainer mViewCells;
        /// the view cell hierarchy (i.e., the logical description of view cells)
        ViewCellsTree *mViewCellsTree;
        
        std::vector<int> mStrategies;

        /** if the values in the view cell leaves and the interiors are up to date
                this is meant for lazy storing of the pvs, where only a scalar indicating
                pvs size is stored in interiors and not the pvs itself.
        */
        bool mViewCellPvsIsUpdated;

        /// maximum number of samples for the view cell construction
        int mConstructionSamples;
        int mSamplesPerPass;
        int mInitialSamples;
        int mPostProcessSamples;
        int mVisualizationSamples;

        int mEvaluationSamples;

        float mTotalAreaValid;
        float mTotalArea;

        int mMaxPvsSize;
        int mMinPvsSize;
        float mMaxPvsRatio;

        int mSamplingType;
        int mEvaluationSamplingType;
        int mNumActiveViewCells;
        bool mCompressViewCells;

        vector<ViewCellPoints *> mViewCellPoints;

        /// holds the current view cell statistics
        ViewCellsStatistics mCurrentViewCellsStats;

        /// the scene bounding box
        AxisAlignedBox3 mViewSpaceBox;
        
        /// if view cells should be exported
        bool mExportViewCells;
        // if only valid view cells should be considered for processing
        bool mOnlyValidViewCells;
        /// if rays should be used to collect merge candidates
        bool mUseRaysForMerge;
        /// if there should be an additional merge step after the subdivision
        bool mMergeViewCells;
        /// the width of the box filter
        float mFilterWidth;
        /// Maximal size of the filter in terms of contributing view cells
        int mMaxFilterSize;
        /// only for debugging: stores some rays used during view cell construction
        VssRayContainer storedRays;
        /// if kd node based pvs is used for preprocessing
        bool mUseKdPvs;
        /// types of distributions used for sampling
        MixtureDistribution *mMixtureDistribution;



        //////////////////
        //-- visualization options
        
        /// color code for view cells visualization
        bool mShowVisualization;
        int mColorCode;
        bool mExportGeometry;
        bool mExportRays;
        bool mViewCellsFinished;
        bool mEvaluateViewCells;

        /// if pvs should be exported with view cells
        bool mExportPvs;

        /// if view cells geometry should be used from other sources
        bool mUsePredefinedViewCells;
        /// the weight for one triangle in the heuristics
        float mTriangleWeight;
        /// the weight for one object (= one entity issued with one draw call) in the heuristics
        float mObjectWeight;

        vector<PerViewCellStat> mPerViewCellStat;
        SamplesStatistics mSamplesStat;
};


/** Manages different higher order operations on the view cells.
*/
class BspViewCellsManager: public ViewCellsManager
{

public:
        /** Constructor taking the bsp tree and the number of samples
                used to construct the bsp tree.
        */
        BspViewCellsManager(ViewCellsTree *viewCellsTree, BspTree *tree);

        ~BspViewCellsManager();

        int ConstructSubdivision(const ObjectContainer &objects, 
                                  const VssRayContainer &rays);

        int PostProcess(const ObjectContainer &objects, 
                                        const VssRayContainer &rays);

        void Visualize(const ObjectContainer &objects,
                                   const VssRayContainer &sampleRays);

        int GetType() const;
        
        ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;

        bool ViewCellsConstructed() const;

        //void PrintStatistics(ostream &s) const;

        int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);
        
        /** Returns the probability that the view point lies
                in this view cells.
        */
        float GetProbability(ViewCell *viewCell);

        /** Get a viewcell containing the specified point.
        */
        ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const;

        /** Creates mesh for this view cell.
        */
        void CreateMesh(ViewCell *vc);

        void ExportViewCellGeometry(Exporter *exporter,
                                                                ViewCell *vc,
                                                                const AxisAlignedBox3 *box,
                                                                const AxisAlignedPlane *clipPlane = NULL
                                                                ) const;
        
        void CollectMergeCandidates(const VssRayContainer &rays, 
                                                                vector<MergeCandidate> &candidates);

        void Finalize(ViewCell *viewCell, const bool createMesh);

        bool ExportViewCells(const string filename, 
                                                 const bool exportPvs, 
                                                 const ObjectContainer &objects);

        /** Constructs merge hierarchy which corresponds to the spatial hierarchy.
        */
        ViewCell *ConstructSpatialMergeTree(BspNode *root);

        void ExportSingleViewCells(const ObjectContainer &objects,
                                                           const int maxViewCells,
                                                           const bool sortViewCells,
                                                           const bool exportPvs,
                                                           const bool exportRays,
                                                           const int maxRays,
                                                           const string &prefix,
                                                           VssRayContainer *visRays = NULL);

        bool LineSegmentIntersects(const Vector3 &origin,
                                                           const Vector3 &termination,
                                                           ViewCell *viewCell);

protected:

        void CollectViewCells();
        
        /// the BSP tree.
        BspTree *mBspTree;
        vector<BspRay *> mBspRays;

private:

        /** Constructs a spatial merge tree only 2 levels deep.
        */
        ViewCell *ConstructDummyMergeTree(BspNode *root);
        /** Exports visualization of the BSP splits.
        */
        void ExportSplits(const ObjectContainer &objects);
        /** test if subdivision is valid in terms of volume / area.
        */
        void TestSubdivision();
};


/**
        Manages different higher order operations on the KD type view cells.
*/
class KdViewCellsManager: public ViewCellsManager
{

public:

        KdViewCellsManager(ViewCellsTree *viewCellsTree, KdTree *tree);

        int ConstructSubdivision(const ObjectContainer &objects, 
                                                         const VssRayContainer &rays);

        int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);

        int PostProcess(const ObjectContainer &objects, 
                                        const VssRayContainer &rays);

        void Visualize(const ObjectContainer &objects,
                                   const VssRayContainer &sampleRays);

        int GetType() const;

        bool ViewCellsConstructed() const;

        ViewCell *GenerateViewCell(Mesh *mesh) const;

        /** Prints out statistics of this approach.
        */
        //  virtual void PrintStatistics(ostream &s) const;
        ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const 
        { return NULL; }

        float GetProbability(ViewCell *viewCell);
        
        void CreateMesh(ViewCell *vc);

        void ExportViewCellGeometry(Exporter *exporter,
                                                                ViewCell *vc,
                                                                const AxisAlignedBox3 *box,
                                                                const AxisAlignedPlane *clipPlane = NULL) const;


        void CollectMergeCandidates(const VssRayContainer &rays, 
                                                                vector<MergeCandidate> &candidates);

        void ExportSingleViewCells(const ObjectContainer &objects,
                                                           const int maxViewCells,
                                                           const bool sortViewCells,
                                                           const bool exportPvs,
                                                           const bool exportRays,
                                                           const int maxRays,
                                                           const string &prefix,
                                                           VssRayContainer *visRays = NULL);

        bool LineSegmentIntersects(const Vector3 &origin,
                                                           const Vector3 &termination,
                                                           ViewCell *viewCell);

protected:

        /** Collects view cells from a hierarchy.
        */
        void CollectViewCells();

        KdNode *GetNodeForPvs(KdLeaf *leaf);

        ////////////////////////////////////////

        /// the BSP tree.
        KdTree *mKdTree;

        /// depth of the KD tree nodes with represent the view cells
        int mKdPvsDepth;


};


/** Manages different higher order operations on the view cells.
*/
class VspBspViewCellsManager: public ViewCellsManager
{

public:

        VspBspViewCellsManager(ViewCellsTree *viewCellsTree, VspBspTree *tree);
        ~VspBspViewCellsManager();

        int ConstructSubdivision(const ObjectContainer &objects, 
                                                         const VssRayContainer &rays);

        int PostProcess(const ObjectContainer &objects, 
                                        const VssRayContainer &rays);

        void Visualize(const ObjectContainer &objects,
                                   const VssRayContainer &sampleRays);

        int GetType() const;
        
        ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;

        bool ViewCellsConstructed() const;
        
        int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);

        float GetProbability(ViewCell *viewCell);
        
        ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const;

        bool GetViewPoint(Vector3 &viewPoint) const;

        bool ViewPointValid(const Vector3 &viewPoint) const;

        void CreateMesh(ViewCell *vc);

        bool ExportViewCells(const string filename, 
                                                 const bool exportPvs, 
                                                 const ObjectContainer &objects);

        int CastBeam(Beam &beam);
        
        void ExportViewCellGeometry(Exporter *exporter,
                                                                ViewCell *vc,
                                                                const AxisAlignedBox3 *box,
                                                                const AxisAlignedPlane *clipPlane = NULL) const;


        void Finalize(ViewCell *viewCell, const bool createMesh);

        void CollectMergeCandidates(const VssRayContainer &rays, 
                                                                vector<MergeCandidate> &candidates);

        void ExportSingleViewCells(const ObjectContainer &objects,
                                                           const int maxViewCells,
                                                           const bool sortViewCells,
                                                           const bool exportPvs,
                                                           const bool exportRays,               
                                                           const int maxRays,
                                                           const string &prefix,
                                                           VssRayContainer *visRays = NULL);

        
        bool LineSegmentIntersects(const Vector3 &origin,
                                                           const Vector3 &termination,
                                                           ViewCell *viewCell);

protected:

        int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                ViewCellContainer &viewCells) const;
        
        /** Merges view cells according to some criteria
        */
        void MergeViewCells(const VssRayContainer &rays, 
                                                const ObjectContainer &objects);
        
        void RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);

        void CollectViewCells();

        /** Returns maximal depth difference of view cell 
                leaves in tree.
        */
        int GetMaxTreeDiff(ViewCell *vc) const;

        /** Prepare view cells for use after loading them from disc.
        */
        void PrepareLoadedViewCells();

        /** Constructs merge hierarchy which corresponds to the spatial hierarchy.
        */
        ViewCell *ConstructSpatialMergeTree(BspNode *root);

        /// HACK for testing visibility filter functionality
        void TestFilter(const ObjectContainer &objects);

        /** Visualization of the pvs difference to exact visubility using 
                from point queries.
        */
        void VisualizeWithFromPointQueries();

        /** Evaluate from point queries for the current scene.
        */
        void EvalFromPointQueries();

        /** Exports visualization of the BSP splits.
        */
        void ExportSplits(const ObjectContainer &objects, 
                                          const VssRayContainer &rays);


        /////////////////////////

        /// the view space partition BSP tree.
        VspBspTree *mVspBspTree;


private:

        /** test if subdivision is valid in terms of volume / area.
        */
        void TestSubdivision();
};



/**     Manages different higher order operations on the view cells.
*/
class VspOspViewCellsManager: public ViewCellsManager
{
        friend class ViewCellsParseHandlers;
        friend class ViewCellsManager;

public:

        /** This version takes a view cells tree and a hierarchy
                as input.
        */
        VspOspViewCellsManager(ViewCellsTree *vcTree, 
                                                   const string &hierarchyType);
        
        ~VspOspViewCellsManager();

        int ConstructSubdivision(const ObjectContainer &objects,
                                                         const VssRayContainer &rays);

        int PostProcess(const ObjectContainer &objects, 
                                        const VssRayContainer &rays);

        void Visualize(const ObjectContainer &objects, 
                                   const VssRayContainer &sampleRays);

        int GetType() const;
        
        ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;

        virtual Intersectable *GetIntersectable(const VssRay &ray, 
                                                                                        const bool isTermination) const;

        bool ViewCellsConstructed() const;

        int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells);

        bool LineSegmentIntersects(const Vector3 &origin, 
                                                           const Vector3 &termination, 
                                                           ViewCell *viewCell);

        float GetProbability(ViewCell *viewCell);
        
        ViewCell *GetViewCell(const Vector3 &point, 
                                                  const bool active = false) const;

        bool GetViewPoint(Vector3 &viewPoint) const;

        bool ViewPointValid(const Vector3 &viewPoint) const;

        void CreateMesh(ViewCell *vc);

        bool ExportViewCells(const string filename, 
                                                 const bool exportPvs, 
                                                 const ObjectContainer &objects);

        int CastBeam(Beam &beam);

        void Finalize(ViewCell *viewCell, const bool createMesh);

        void ExportSingleViewCells(const ObjectContainer &objects,
                                                           const int maxViewCells,
                                                           const bool sortViewCells,
                                                           const bool exportPvs,
                                                           const bool exportRays,
                                                           const int maxRays,
                                                           const string &prefix,
                                                           VssRayContainer *visRays = NULL);
        /** See parent class.
        */
        virtual void FinalizeViewCells(const bool createMesh);

        bool ExportViewCellsBinary(const string filename, 
                                                           const bool exportPvs, 
                                                           const ObjectContainer &objects);

#if TEST_PACKETS

        float ComputeSampleContributions(const VssRayContainer &rays,
                                             const bool addContributions,
                                                                         const bool storeViewCells,
                                                                         const bool useHitObjects = false);
#endif


protected:

        /** View cells manager taking a view cells tree and a hierarchy as input.
        */
        VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm);
        
        virtual void EvalViewCellPartition();
        /** Exports view cell geometry.
        */
        void ExportViewCellGeometry(Exporter *exporter,
                                                                ViewCell *vc,
                                                                const AxisAlignedBox3 *box,
                                                                const AxisAlignedPlane *clipPlane = NULL) const;

        int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                ViewCellContainer &viewCells) const;
        
        void CollectViewCells();

        virtual void CompressViewCells();
        /** Prepare view cells for use after loading them from disc.
        */
        void PrepareLoadedViewCells();
        /** Constructs merge hierarchy which corresponds to the spatial hierarchy.
        */
        ViewCell *ConstructSpatialMergeTree(VspNode *root);
        /** Exports visualization of the PVS.
        */
        void ExportPvs(const ObjectContainer &objects, const VssRayContainer &rays);
        /** Returns a hierarchy manager of the given name.
        */
        static HierarchyManager *CreateHierarchyManager(const string &name);
        /** collect objects intersecting a given spatial box 
        */
        virtual void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
        /** Update the cost of pvss for hierarchy objects.
        */
        float UpdateObjectCosts();


        ////////////////

        /** Fast view cell loader in binary mode.
        */
        friend ViewCellsManager *ViewCellsManager::
                LoadViewCellsBinary(const std::string &filename, 
                                    ObjectContainer &pvsObjects,
                                                        bool finalizeViewCells,
                                                        BoundingBoxConverter *bconverter);


        /** Print statistics about the view cells compression.
        */
        static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries);


        ////////////////////

        /// if we the objects are compressed after evaluation 
        /// this makes only sense for testing purpose
        bool mCompressObjects;
        /// hierarchy manager managing view space / object subdivision.
        HierarchyManager *mHierarchyManager;
};


}

#endif