/*

-----------------------------------------------------------------------------

This source file is part of OGRE

(Object-oriented Graphics Rendering Engine)

For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2014 Torus Knot Software Ltd

Permission is hereby granted, free of charge, to any person obtaining a copy

of this software and associated documentation files (the "Software"), to deal

in the Software without restriction, including without limitation the rights

to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

copies of the Software, and to permit persons to whom the Software is

furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in

all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

THE SOFTWARE.

-----------------------------------------------------------------------------

*/

#ifndef __Ogre_TerrainQuadTreeNode_H__

#define __Ogre_TerrainQuadTreeNode_H__

#include "OgreTerrainPrerequisites.h"

#include "OgreCommon.h"

#include "OgreMovableObject.h"

#include "OgreRenderable.h"

namespace Ogre

{

    /** \addtogroup Optional

    *  @{

    */

    /** \addtogroup Terrain

    *  Some details on the terrain component

    *  @{

    */

    /** A node in a quad tree used to store a patch of terrain.

        <b>Algorithm overview:</b>

    @par

        Our goal is to perform traditional chunked LOD with geomorphing. But, 

        instead of just dividing the terrain into tiles, we will divide them into

        a hierarchy of tiles, a quadtree, where any level of the quadtree can 

        be a rendered tile (to the exclusion of its children). The idea is to 

        collect together children into a larger batch with their siblings as LOD 

        decreases, to improve performance.

    @par

        The minBatchSize and maxBatchSize parameters on Terrain a key to 

        defining this behaviour. Both values are expressed in vertices down one axis.

        maxBatchSize determines the number of tiles on one side of the terrain,

        which is numTiles = (terrainSize-1) / (maxBatchSize-1). This in turn determines the depth

        of the quad tree, which is sqrt(numTiles). The minBatchSize determines

        the 'floor' of how low the number of vertices can go in a tile before it

        has to be grouped together with its siblings to drop any lower. We also do not group 

        a tile with its siblings unless all of them are at this minimum batch size, 

        rather than trying to group them when they all end up on the same 'middle' LOD;

        this is for several reasons; firstly, tiles hitting the same 'middle' LOD is

        less likely and more transient if they have different levels of 'roughness',

        and secondly since we're sharing a vertex / index pool between all tiles, 

        only grouping at the min level means that the number of combinations of 

        buffer sizes for any one tile is greatly simplified, making it easier to 

        pool data. To be more specific, any tile / quadtree node can only have

        log2(maxBatchSize-1) - log2(minBatchSize-1) + 1 LOD levels (and if you set them 

        to the same value, LOD can only change by going up/down the quadtree).

        The numbers of vertices / indices in each of these levels is constant for

        the same (relative) LOD index no matter where you are in the tree, therefore

        buffers can potentially be reused more easily.

    */

    class _OgreTerrainExport TerrainQuadTreeNode : private Renderable, private MovableObject

    {

    public:

        /** Constructor.

        @param terrain The ultimate parent terrain

        @param parent Optional parent node (in which case xoff, yoff are 0 and size must be entire terrain)

        @param xoff, yoff Offsets from the start of the terrain data in 2D

        @param size The size of the node in vertices at the highest LOD

        @param lod The base LOD level

        @param depth The depth that this node is at in the tree (or convenience)

        */

        TerrainQuadTreeNode(Terrain* terrain, TerrainQuadTreeNode* parent, 

            uint16 xoff, uint16 yoff, uint16 size, uint16 lod, uint16 depth);

        virtual ~TerrainQuadTreeNode();

        /// Get the horizontal offset into the main terrain data of this node

        uint16 getXOffset() const { return mOffsetX; }

        /// Get the vertical offset into the main terrain data of this node

        uint16 getYOffset() const { return mOffsetY; }

        /// Is this a leaf node (no children)

        bool isLeaf() const;

        /// Get the base LOD level this node starts at (the highest LOD it handles)

        uint16 getBaseLod() const { return mBaseLod; }

        /// Get the number of LOD levels this node can represent itself (only > 1 for leaf nodes)

        uint16 getLodCount() const;

        /// Get child node

        TerrainQuadTreeNode* getChild(unsigned short child) const;

        /// Get parent node

        TerrainQuadTreeNode* getParent() const;

        /// Get ultimate parent terrain

        Terrain* getTerrain() const;

        /// Prepare node and children (perform CPU tasks, may be background thread)

        void prepare();

        /// Prepare node from a stream

        void prepare(StreamSerialiser& stream);

        /// Load node and children (perform GPU tasks, will be render thread)

        void load();

        /// Load node and children in a depth range (perform GPU tasks, will be render thread)

        void load(uint16 depthStart, uint16 depthEnd);

        void loadSelf();

        /// Unload node and children (perform GPU tasks, will be render thread)

        void unload();

        /// Unload node and children in a depth range (perform GPU tasks, will be render thread)

        void unload(uint16 depthStart, uint16 depthEnd);

        /// Unprepare node and children (perform CPU tasks, may be background thread)

        void unprepare();

        /// Save node to a stream

        void save(StreamSerialiser& stream);

        struct _OgreTerrainExport LodLevel : public TerrainAlloc

        {

            /// Number of vertices rendered down one side (not including skirts)

            uint16 batchSize;

            /// Index data on the gpu

            IndexData* gpuIndexData;

            /// Maximum delta height between this and the next lower lod

            Real maxHeightDelta;

            /// Temp calc area for max height delta

            Real calcMaxHeightDelta;

            /// The most recently calculated transition distance

            Real lastTransitionDist;

            /// The cFactor value used to calculate transitionDist

            Real lastCFactor;

            LodLevel() : batchSize(0), gpuIndexData(0), maxHeightDelta(0), calcMaxHeightDelta(0),

                lastTransitionDist(0), lastCFactor(0) {}

        };

        typedef std::vector<LodLevel*> LodLevelList;

        /** Get the LodLevel information for a given lod.

        @param lod The lod level index relative to this classes own list; if you

            want to use a global lod level, subtract getBaseLod() first. Higher

            LOD levels are lower detail.

        */

        const LodLevel* getLodLevel(uint16 lod);

        /** Notify the node (and children) that deltas are going to be calculated for a given range.

            Based on this call, we can know whether or not to reset the max height.

        */

        void preDeltaCalculation(const Rect& rect);

        /** Notify the node (and children) of a height delta value. */

        void notifyDelta(uint16 x, uint16 y, uint16 lod, Real delta);

        /** Notify the node (and children) that deltas have finished being calculated.

        */

        void postDeltaCalculation(const Rect& rect);

        /** Promote the delta values calculated to the runtime ones (this must

            be called in the main thread). 

        */

        void finaliseDeltaValues(const Rect& rect);

        /** Assign vertex data to the tree, from a depth and at a given resolution.

        @param treeDepthStart The first depth of tree that should use this data, owns the data

        @param treeDepthEnd The end of the depth that should use this data (exclusive)

        @param resolution The resolution of the data to use (compared to full terrain)

        @param sz The size of the data along one edge

        */

        void assignVertexData(uint16 treeDepthStart, uint16 treeDepthEnd, uint16 resolution, uint sz);

        /** Tell a node that it should use an anscestor's vertex data.

        @param owner

        @param treeDepthEnd The end of the depth that should use this data (exclusive)

        @param resolution The resolution of the data to use

        */

        void useAncestorVertexData(TerrainQuadTreeNode* owner, uint16 treeDepthEnd, uint16 resolution);

        /** Tell the node to update its vertex data for a given region. 

        */

        void updateVertexData(bool positions, bool deltas, const Rect& rect, bool cpuData);

        /** Merge a point (relative to terrain node) into the local bounds, 

            and that of children if applicable.

        @param x,y The point on the terrain to which this position corresponds 

            (affects which nodes update their bounds)

        @param pos The position relative to the terrain centre

        */

        void mergeIntoBounds(long x, long y, const Vector3& pos);

        /** Reset the bounds of this node and all its children for the region given.

        @param rect The region for which bounds should be reset, in top-level terrain coords

        */

        void resetBounds(const Rect& rect);

        /** Returns true if the given rectangle overlaps the terrain area that

            this node references.

         @param rect The region in top-level terrain coords

        */

        bool rectIntersectsNode(const Rect& rect);

        /** Returns true if the given rectangle completely contains the terrain area that

        this node references.

        @param rect The region in top-level terrain coords

        */

        bool rectContainsNode(const Rect& rect);

        /** Returns true if the given point is in the terrain area that

         this node references.

         @param x,y The point in top-level terrain coords

         */

        bool pointIntersectsNode(long x, long y);

        /// Get the AABB (local coords) of this node

        const AxisAlignedBox& getBoundingBox(void) const override { return mAABB; }

        /// Get the bounding radius of this node

        Real getBoundingRadius() const override;

        /// Get the local centre of this node, relative to parent terrain centre

        const Vector3& getLocalCentre() const { return mLocalCentre; }

        /// Get the minimum height of the node

        Real getMinHeight() const;

        /// Get the maximum height of the node

        Real getMaxHeight() const;

        /** Calculate appropriate LOD for this node and children

        @param cam The camera to be used (this should already be the LOD camera)

        @param cFactor The cFactor which incorporates the viewport size, max pixel error and lod bias

        @return true if this node or any of its children were selected for rendering

        */

        bool calculateCurrentLod(const Camera* cam, Real cFactor);

        /// Get the current LOD index (only valid after calculateCurrentLod)

        int getCurrentLod() const { return mCurrentLod; }

        /// Returns whether this node is rendering itself at the current LOD level

        bool isRenderedAtCurrentLod() const;

        /// Returns whether this node or its children are being rendered at the current LOD level

        bool isSelfOrChildRenderedAtCurrentLod() const;

        /// Manually set the current LOD, intended for internal use only

        void setCurrentLod(int lod);

        /// Get the transition state between the current LOD and the next lower one (only valid after calculateCurrentLod)

        float getLodTransition() const { return mLodTransition; }

        /// Manually set the current LOD transition state, intended for internal use only

        void setLodTransition(float t);

        /// Buffer binding used for holding positions

        static unsigned short POSITION_BUFFER;

        /// Buffer binding used for holding delta values

        static unsigned short DELTA_BUFFER;

    private:

        Terrain* mTerrain;

        TerrainQuadTreeNode* mParent;

        TerrainQuadTreeNode* mChildren[4];

        LodLevelList mLodLevels;

        uint16 mOffsetX, mOffsetY;

        uint16 mBoundaryX, mBoundaryY;

        /// The number of vertices at the original terrain resolution this node encompasses

        uint16 mSize;

        uint16 mBaseLod;

        uint16 mDepth;

        Vector3 mLocalCentre; /// Relative to terrain centre

        AxisAlignedBox mAABB; /// Relative to mLocalCentre

        Real mBoundingRadius; /// Relative to mLocalCentre

        int mCurrentLod; /// -1 = none (do not render)

        float mLodTransition; /// 0-1 transition to lower LOD

        /// The child with the largest height delta 

        TerrainQuadTreeNode* mChildWithMaxHeightDelta;

        bool mSelfOrChildRendered;

        struct VertexDataRecord : public TerrainAlloc

        {

            VertexData* cpuVertexData;

            VertexData* gpuVertexData;

            /// Resolution of the data compared to the base terrain data (NOT number of vertices!)

            uint16 resolution;

            /// Size of the data along one edge

            uint16 size;

            /// Number of quadtree levels (including this one) this data applies to

            uint16 treeLevels;

            /// Number of rows and columns of skirts

            uint16 numSkirtRowsCols;

            /// The number of rows / cols to skip in between skirts

            uint16 skirtRowColSkip;

            /// Is the GPU vertex data out of date?

            bool gpuVertexDataDirty;

            VertexDataRecord(uint16 res, uint16 sz, uint16 lvls) 

                : cpuVertexData(0), gpuVertexData(0), resolution(res), size(sz),

                treeLevels(lvls), numSkirtRowsCols(0),

                skirtRowColSkip(0), gpuVertexDataDirty(false) {}

        };

        TerrainQuadTreeNode* mNodeWithVertexData;

        VertexDataRecord* mVertexDataRecord;

        /** MovableObject implementation to provide the hook to the scene.

            In one sense, it would be most convenient to have a single MovableObject

            to represent the whole Terrain object, and then internally perform

            some quadtree frustum culling to narrow down which specific tiles are rendered.

            However, the one major flaw with that is that exposing the bounds to 

            the SceneManager at that level prevents it from doing anything smarter

            in terms of culling - for example a portal or occlusion culling SceneManager

            would have no opportunity to process the leaf nodes in those terms, and

            a simple frustum cull may give significantly poorer results. 

        @par

            Therefore, we in fact register a MovableObject at every node, and 

            use the LOD factor to determine which one is currently active. LODs

            must be mutually exclusive and to deal with precision errors, we really

            need to evaluate them all at once, rather than as part of the 

            _notifyCurrentCamera function. Therefore the root Terrain registers

            a SceneManager::Listener to precalculate which nodes will be displayed 

            when it comes to purely a LOD basis.

        */

        SceneNode* mLocalNode;

        // actual implementation of MovableObject methods

        bool isVisible(void) const override;

        const String& getMovableType(void) const override;

        void _updateRenderQueue(RenderQueue* queue) override;

        void visitRenderables(Renderable::Visitor* visitor,  bool debugRenderables = false) override;

        // actual implementations of Renderable methods

        const MaterialPtr& getMaterial(void) const override;

        Technique* getTechnique(void) const override;

        void getRenderOperation(RenderOperation& op) override;

        void getWorldTransforms(Matrix4* xform) const override;

        Real getSquaredViewDepth(const Camera* cam) const override;

        const LightList& getLights(void) const override;

        bool getCastShadows(void) const override;

        /// @deprecated will be private in 14

        bool getCastsShadows(void) const override { return getCastShadows(); }

        const VertexDataRecord* getVertexDataRecord() const;

        void createCpuVertexData();

        /* Update the vertex buffers - the rect in question is relative to the whole terrain, 

            not the local vertex data (which may use a subset)

        */

        void updateVertexBuffer(const HardwareVertexBufferPtr& posbuf, const HardwareVertexBufferPtr& deltabuf, const Rect& rect);

        void destroyCpuVertexData();

        void createGpuVertexData();

        void destroyGpuVertexData();

        void updateGpuVertexData();

        void createGpuIndexData();

        void destroyGpuIndexData();

        void populateIndexData(uint16 batchSize, IndexData* destData);

        void writePosVertex(bool compress, uint16 x, uint16 y, float height, const Vector3& pos, float uvScale, float** ppPos);

        void writeDeltaVertex(bool compress, uint16 x, uint16 y, float delta, float deltaThresh, float** ppDelta);

        uint16 calcSkirtVertexIndex(uint16 mainIndex, bool isCol);

    };

    /** @} */

    /** @} */

}

#endif