terrainmesh.h

/*--License:
        Lilith 3D Engine
        Copyright Lee Thomason (Grinning Lizard Software) 2002-2007
        www.grinninglizard.com/lilith

        This program is free software; you can redistribute it and/or
        modify it under the terms of the GNU General Public License
        as published by the Free Software Foundation; either version 2
        of the License, or (at your option) any later version.

        This program is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.

        You should have received a copy of the GNU General Public License
        along with this program; if not, write to the Free Software
        Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

        The full text of the license can be found in license.txt
*/
#ifndef TERRAIN_MESH_INCLUDED
#define TERRAIN_MESH_INCLUDED

#ifdef _MSC_VER
#pragma warning( disable : 4786 )       // Debugger truncating names.
#endif

#include "../grinliz/gldebug.h"
#include "../grinliz/gltypes.h"
#include "../grinliz/glrandom.h"
#include "../grinliz/glgeometry.h"
#include "../grinliz/glpublisher.h"
#include "../grinliz/glbitarray.h"
#include "../grinliz/glcolor.h"
#include "../micropather/micropather.h"
#include "meshgroup.h"
#include "weather.h"
#include "worlddefine.h"
#include "meshnode.h"
#include "shader.h"
#include "SDL.h"

#include <set>
#include <vector>


namespace lilith3d
{

class Texture;
struct PathNode;
struct PathSurfaceInstance;
class StaticResource;
class BuildingMesh;
class LilithObject;
struct L3State;

typedef grinliz::BitArray< VERTEXSIZE, VERTEXSIZE > VertexBitArray;
typedef grinliz::BitArray< MAPSIZE/2, MAPSIZE/2 >   PatchBitArray;
typedef grinliz::BitArray< MAPSIZE, MAPSIZE >           MapBitArray;

class TerrainListener : public grinliz::Listener< TerrainListener >
{
  public:
        virtual void TerrainChange( const grinliz::Rectangle2I& vertexBounds ) = 0;
};


class TerrainMesh : public micropather::Graph
{
  public:
        enum
        {
                // To reverse a direction: (dir+4)%8
                EAST, NORTHEAST, NORTH, NORTHWEST, WEST, SOUTHWEST, SOUTH, SOUTHEAST,
                BIT_E   = 0x01,
                BIT_NE  = 0x02,
                BIT_N   = 0x04,
                BIT_NW  = 0x08,
                BIT_W   = 0x10,
                BIT_SW  = 0x20,
                BIT_S   = 0x40,
                BIT_SE  = 0x80,
                        
                // For a mapsize of 4, LOD=0, 4x4       2^MAX = MAPSIZE
                //                                         LOD=1, 2x2
                //                                         LOD=2, 1x1
                MAX_LOD = MAP_POWER-1,
                MAX_NEIGHBORS = ( MAPSIZE >> MIN_LOD ) * 4,

                PATCHSIZE = MAPSIZE / 2,
                WATER_SIZE = 4,
                // The water vertex size doesn't include the edges.
                WATER_VERTEXSIZE = ( MAPSIZE / WATER_SIZE ) + 1,
                WATER_PATCHSIZE  = ( MAPSIZE / WATER_SIZE ),
                WATER_INDEX_COUNT = (WATER_VERTEXSIZE-1) * (WATER_VERTEXSIZE-1) * 4,
        };
        
        TerrainMesh();
        virtual ~TerrainMesh();

        grinliz::Publisher< TerrainListener > publish;

        virtual void DoCulling();
        void StreamOut();
        void StreamOutWater();
        void StreamOutMap();
        void StreamOutShadowed();

        void LoadHeightMap( const char* filename );

        void RandomHeightMap( U32 seed );

        int IntersectRay(       const grinliz::Vector3F& point, 
                                                const grinliz::Vector3F& dir,
                                                grinliz::Vector3F* intersect,
                                                void** state );

        float CalcHeight( float x, float y, grinliz::Vector3F* at=0, bool* inWater=0 );

        inline static bool VertexInRange( int x, int y ) { return ( x >= 0 && x < (int)VERTEXSIZE && y >= 0 && y < (int)VERTEXSIZE ); }

        void PointToPoly(       float x, float y,               // x, y point [in]
                                                int vind[],                             // array of 3 vertex indices [out]
                                                grinliz::Vector3F vertex[],             // array of 3 vertices that match indices [out]
                                                bool *passable )                // set to true or false indicating whether the terrain is passable [out]
        {
                QuadNode* pNode;
                U32 poly;  

                PointToPoly( x, y, vind, vertex, passable, &pNode, &poly );
        }

        // Internal. Renders a decal. ONLY vertex & texture coordinates written to "state"
        void TerrainMesh::RenderDecal( const grinliz::Rectangle2F& coord, bool suppressVState = false );

        // --- Morphing functionality --- //
        float Height( int x, int y )    {       GLASSERT( grinliz::InRange( x, 0, (int)VERTEXSIZE-1 ) );
                                                                                GLASSERT( grinliz::InRange( y, 0, (int)VERTEXSIZE-1 ) );
                                                                                return tvertex[y*VERTEXSIZE+x].pos.z; }

        void StartHeightChange()                {       heightChange = true;
                                                                                heightChangeInit = false;
                                                                        }
        void SetHeight( int x, int y, float height );
        void SetHeightDelta( int x, int y, float delta )        { SetHeight( x, y, tvertex[y*VERTEXSIZE+x].pos.z + delta ); }
        void SetHeightFiltered( int x, int y, float height );

        void EndHeightChange( bool callListeners=true );

        bool IsHeightChanging() { return heightChange; }

        void LockHeight( const grinliz::Rectangle2I& bounds );
        void UnLockHeight( const grinliz::Rectangle2I& bounds );

        // -- The pather -- //
        std::vector< grinliz::Vector2F >* FindPath( float startX, float startY, float endX, float endY );

        std::vector< grinliz::Vector2F >* FindPath( const LilithObject& start, const LilithObject& end );

        bool Passable( float x, float y )
        {
                int vindex[3];
                grinliz::Vector3F vertex[3];
                bool passable;

                PointToPoly( x, y, vindex, vertex, &passable );
                return passable;
        }

        /*
                Cost to cover a terrain. Cost of 1.0 moves at normal speed, 2.0 half speed, etc.
        */
        float CalcCost( const grinliz::Vector3F& pos, float zSlope );

        bool CanPlaceBuilding( int x, int y, const StaticResource* meshResource, grinliz::Rectangle2I* outVertexBounds );

        BuildingMesh* CreateBuilding( int x, int y, const StaticResource* meshResource );

        // [Internal]
        const MapBitArray& GetMapPatherReserved()       { return mapPatherReserved; }

        // [Internal]
        void PatchInfo( int patchX, int patchY, bool* level, float* z );

        // Removes "map" from the pather. Used by building so they don't get pathed through.
        // Note that the pather is reserved in map (grid) coordinates. Return true if area
        // could be reserved.
        bool ReservePather( const grinliz::Rectangle2I& map );
        void ReleasePather( const grinliz::Rectangle2I& map );

        inline static int VINDX( int x, int y ) 
        { 
                GLASSERT( grinliz::InRange( x, 0, VERTEXSIZE-1 ) );
                GLASSERT( grinliz::InRange( y, 0, VERTEXSIZE-1 ) );
                return y*VERTEXSIZE+x; 
        }       // vertex
        inline static int PINDX( int x, int y ) 
        {
                GLASSERT( grinliz::InRange( x, 0, PATCHSIZE-1 ) );
                GLASSERT( grinliz::InRange( y, 0, PATCHSIZE-1 ) );
                return y*PATCHSIZE+x;
        }
        inline static void INV_PINDX( int index, int* x, int* y )
        {
                *y = index / PATCHSIZE;
                *x = index - (*y) * PATCHSIZE;

                GLASSERT( *x >= 0 && *x < PATCHSIZE );
                GLASSERT( *y >= 0 && *y < PATCHSIZE );
        }
        inline static int WVINDX( int x, int y )
        { 
                GLASSERT( x >= 0 && x < WATER_VERTEXSIZE );
                GLASSERT( y >= 0 && y < WATER_VERTEXSIZE );
                return y*WATER_VERTEXSIZE + x;  
        }       // water

        inline static void INV_VINDX( U32 index, grinliz::Vector2I* vertex )
        {
                vertex->y = index / lilith3d::VERTEXSIZE;
                vertex->x = index - vertex->y * lilith3d::VERTEXSIZE;
        }
        inline void INV_VINDX( U32 index, grinliz::Vector3F* vertex )
        {
                U32 iy = index / lilith3d::VERTEXSIZE;
                vertex->y = float( iy );
                vertex->x = float( index - iy * lilith3d::VERTEXSIZE );
                vertex->z = tvertex[ index ].pos.z;
        }
        inline static void INV_VINDX( U32 index, U32* x, U32* y )
        {
                /*
                *y = index / lilith3d::VERTEXSIZE;
                *x = index - ((*y)<<<MAP_POWER) - *y;
                */
                *y = index / lilith3d::VERTEXSIZE;
                *x = index - (*y) * lilith3d::VERTEXSIZE;

                GLASSERT( *x >= 0 && *x < (U32)lilith3d::VERTEXSIZE );
                GLASSERT( *y >= 0 && *y < (U32)lilith3d::VERTEXSIZE );
        }
        inline static void INV_VINDX( U32 index, float* x, float* y )
        {
                U32 iy = index / lilith3d::VERTEXSIZE;
                *y = float( iy );
                *x = float( index - iy * lilith3d::VERTEXSIZE );
        }
        static bool VertexToMap( const grinliz::Rectangle2I& vertex, grinliz::Rectangle2I* map )
        {
                GLASSERT( vertex.min.x >= 0 && vertex.max.x < VERTEXSIZE );
                GLASSERT( vertex.min.y >= 0 && vertex.max.y < VERTEXSIZE );

                if ( vertex.Width() > 1 && vertex.Height() > 1 ) {
                        *map = vertex;
                        --map->max.x;
                        --map->max.y;
                        return true;
                }
                return false;
        }
        static void MapToVertex( const grinliz::Rectangle2I& map, grinliz::Rectangle2I* vertex )
        {
                GLASSERT( map.min.x >= 0 && map.max.x < MAPSIZE );
                GLASSERT( map.min.y >= 0 && map.max.y < MAPSIZE );

                *vertex = map;
                ++vertex->max.x;
                ++vertex->max.y;
        }
        // A more conservatve converter. 
        // Vertex x=2 -> x=4, would convert to patch 1.
        static void VertexToPatchExcl( const grinliz::Rectangle2I& vertex, grinliz::Rectangle2I* patch )
        {
                patch->min.x = vertex.min.x / 2;
                patch->min.y = vertex.min.y / 2;
                patch->max.x = ( vertex.max.x - 1 ) / 2;
                patch->max.y = ( vertex.max.y - 1 ) / 2;
        }
        // A more inclusive converter.
        // vertex x=2 -> x=4 would convert to patch 0, 1, & 2
        static void VertexToPatchInc( const grinliz::Rectangle2I& vertex, grinliz::Rectangle2I* patch )
        {
                patch->min.x = (vertex.min.x-1) / 2;
                patch->min.y = (vertex.min.y-1) / 2;
                patch->max.x = ( vertex.max.x ) / 2;
                patch->max.y = ( vertex.max.y ) / 2;
                if ( patch->max.x == PATCHSIZE ) patch->max.x = PATCHSIZE-1;
                if ( patch->max.y == PATCHSIZE ) patch->max.y = PATCHSIZE-1;
        }
        static void PatchToVertex( const grinliz::Rectangle2I& patch, grinliz::Rectangle2I* vertex )
        {
                // Patch (0,0)-(0,0) covers vertex (0,0)-(2,2)
                GLASSERT( patch.min.x >= 0 );
                GLASSERT( patch.max.x < PATCHSIZE );
                GLASSERT( patch.min.y >= 0 );
                GLASSERT( patch.max.y < PATCHSIZE );

                vertex->min.x = patch.min.x * 2;
                vertex->min.y = patch.min.y * 2;
                vertex->max.x = patch.max.x * 2 + 2;
                vertex->max.y = patch.max.y * 2 + 2;

                GLASSERT( vertex->min.x >= 0 );
                GLASSERT( vertex->max.x < VERTEXSIZE );
                GLASSERT( vertex->min.y >= 0 );
                GLASSERT( vertex->max.y < VERTEXSIZE );
        }

        void DisplayInfo( float x, float y );

        static void DumpMemUse( FILE* fp );

        // Travel along the path. Returns 'true' if stuck.
        bool MicroTravel(       float speed,                                    // speed on a flat surface
                                                grinliz::Vector3F* pos,                 // in/out: position of the walker
                                                grinliz::Vector3F* dir,                 // in/out: direction of the walker
                                                PathSurfaceInstance** psi,              // in/out: psi (null implies terrain)
                                                const grinliz::Vector2F* path,  // pointer to the path to be followed
                                                int *pathIndex,                                 // current index into the path
                                                int pathSize );                                 // length of the path

        virtual float LeastCostEstimate( void* stateStart, void* stateEnd );
        virtual void  AdjacentCost( void* state, std::vector< micropather::StateCost > *adjacent );
        virtual void  PrintStateInfo( void* state );

        // Gets the cost of all the adjacent states, in edge order. 
        // adjacent is a 4 element array.
        void AdjacentState(  void* state, void* adjacent[] );

        const grinliz::LineLoop& Frustum2D() { return frustum2D; }
        void StateToPlane( void* state, grinliz::Plane *plane );

  private:
        // Initialization (from constructor)
        void InitQuadCache();
        void InitEdges();
        void InitQuadNodes();
        void InitNoise();               // creates 2 noise textures

        /*
        // called by MicroTravel for travel across a single quad or tri
        void* MicroSubTravel(   const grinliz::Vector2F& start, 
                                                        const grinliz::Vector2F& dir,
                                                        void* state,
                                                        bool* reachedEnd );
        */
        
        struct QuadNode;

        void StreamOutLand( Lilith3D* lilith );
        void StreamOutLandFlat( Lilith3D* lilith, bool shadows );
        void StreamOutLandFlatRec( bool shadows );
        void StreamOutLandLOD( Lilith3D* lilith );
        void StreamOutLandLODRec( const grinliz::Color4F* );
        void StreamOutLandPather( Lilith3D* lilith );
        void StreamOutLandPatherRec();
        void StreamOutSkybox( Lilith3D* lilith );
        void StreamOutSkyboxQuads( Lilith3D* lilith, const grinliz::Color3F& color, float alpha, const Texture* const tex[] );
        void StreamOutSkydome( Lilith3D* lilith );
        void StreamOutSkydomeQuads( Lilith3D* lilith, const grinliz::Color3F& color, float alpha, const Texture* tex );
        void StreamOutBottom();

        void RandomHeightMapRec( grinliz::Random* random, grinliz::Rectangle2I rect, float range );

        // In vertex coordinates:
        void  CalcVertexNormals( const grinliz::Rectangle2I vertexBounds );

        void  RayCastToSun( int x, int y, const grinliz::Vector3F& sunlight, float* output );
        const Texture   *water;

        std::vector< grinliz::Vector3F > skydomeVertex;
        std::vector< U32 > skydomeIndex;
        std::vector< grinliz::Vector2F > skydomeTex;

        // There are 16 possible patch configurations, identified 
        // by the bits SENW. Use 16 for the VSIZE to optimize array indexing.
        // The origin is in the lower left.
        enum { QUAD_CACHE_SIZE = 16 };
        struct QuadCache
        {
                #ifdef DEBUG
                QuadCache()     { GLASSERT( sizeof( QuadCache ) == 128 ); }
                #endif

                // INDEX traits
                int                                     index[10];              // 40 bytes:    6->10 indices (first and last the same)
                int                                     nIndex;                 // 4 bytes
                U8                                      dVX[10];                // 10 bytes:    vertex coord for each index
                U8                                      dVY[10];                // 10 bytes

                // TRI traits
                U8                                      possible[8];    // 8 bytes:             maps 8 possible-tris to the 4-8 tri-in-use
                U8                                      size[8];                // 8 bytes:             size of each tri-in-use (1 or 2)
                struct 
                {
                        S8                              dx;
                        S8                              dy;
                } facing[8][3];                                         // 48 bytes:    facing of each edge. +1,0,-1. CCW from center.
        };
        QuadCache m_quadCache[QUAD_CACHE_SIZE];


        // Quad Ordering
        struct QuadNode
        {
                void Init( unsigned _x, unsigned _y )
                { 
                        GLASSERT( _x < 0xffff );
                        GLASSERT( _y < 0xffff );
                        this->x = (U16)_x; 
                        this->y = (U16)_y;
                        hasRender = 0;
                }

                // x and y location of the node in the given direction.
                void CalcCorner( int dir, grinliz::Vector2F* point );
        
                bool Render()   { return hasRender ? true : false; }

                void CreateRender( int _numVertex )
                {       
                        GLASSERT( !hasRender );
                        GLASSERT( _numVertex >=6 && _numVertex <= 10 );
                        numVertex = _numVertex;
                        hasRender = 1;
                }

                void DeleteRender()             
                { 
                        hasRender = 0; 
                }

                U32 PatchX()    { return x / 2; }
                U32 PatchY()    { return y / 2; }

                // Can this path at all?
                bool HasPathing() 
                {
                        GLASSERT( hasRender );
                        if ( passable ) // something is set...
                                return true;
                        return false;
                }

                unsigned NumPoly()      { return numVertex-2; }

                void GetPoly( U32 i, int* vind )
                {
                        GLASSERT( i < NumPoly() );
                        vind[0] = fanIndexBase[0]   + fanOffset;
                        vind[1] = fanIndexBase[i+1] + fanOffset;
                        vind[2] = fanIndexBase[i+2] + fanOffset;
                }

                // Find a poly, by index, that has the 2 vindex's given.
                // Returns < 0 if none found.
                int FindPoly( int tailVIndex, int headVIndex );

        public:
                // Want to fit the following into an intel cache line - 128 bits = 16 bytes = 4 dword

                U16 x;
                U16 y;

                int*    fanIndexBase;                   // locations of the fan corners, for rendering
                int             fanOffset;

                unsigned hasRender              : 1;    // is the render state valid?
                unsigned numVertex              : 4;    // 4-8 vertices
                unsigned flat                   : 1;    // 1: the quad is flat: all passable, little terrain variance
                unsigned passable               : 8;    // bitmap of whether a *polygon* is passable or not. There were
                                                                                // a lot of rules for this, but now it is just based on whether
                                                                                // the polygon is underwater.
                unsigned cacheIndex             : 4;    // index into the quadCache

        };

        const QuadCache& GetQuadCache( QuadNode* node ) {
                const QuadCache& qc = m_quadCache[ node->cacheIndex ];
                GLASSERT( qc.nIndex == (int)node->numVertex );
                return qc;
        }

        bool PolyPassable( QuadNode* node, U32 poly );

        void CalcTri( QuadNode* quadNode, int poly, grinliz::Vector3F output[] );

        void CalcTriCentroid( const grinliz::Vector3F* tri, grinliz::Vector3F* center )
        {
                for( int i=0; i<3; ++i )
                        center->X(i) = ( tri[0].X(i) + tri[1].X(i) + tri[2].X(i) ) / 3.0f;
        }

        void CalcTriCentroid( QuadNode* quadNode, int poly, grinliz::Vector3F* center );

        // From the terrain, the pather needs a building.
        PathSurfaceInstance* FindBuildingForPather( QuadNode* quadNode, U32 poly );
        // From a building, the pather needs terrain.
        QuadNode* FindQuadNodeForPather( PathSurfaceInstance* psi, int index, U32* poly );

        friend struct QuadNode;

        struct QuadNodeInfo
        {
                QuadNode* node;         // null for virtual nodes
                int dir;                        // NORTH, SOUTH, EAST, WEST
                int x, y, size;
                void Set( int _x, int _y, int _size, int _dir ) {
                        this->x = _x;   this->y = _y;   this->size = _size;     this->dir = _dir;
                }
        };


        void PointToPoly(       float x, float y,                       // x, y point [in]
                                                int vind[],                                     // array of 3 vertex indices [out]
                                                grinliz::Vector3F vertex[],     // array of 3 vertices that match indices [out]
                                                bool *passable,                         // set to true or false indicating whether the terrain is passable [out]
                                                QuadNode** node,
                                                U32* poly );

        void PointToPoly(       float x, float y,
                                                QuadNode** node,
                                                U32* poly )
        {
                int vindex[3];
                grinliz::Vector3F vertex[3];
                bool passable;
                PointToPoly( x, y, vindex, vertex, &passable, node, poly );
        }

        enum {
                NUM_QUADNODES = PATCHSIZE*PATCHSIZE
        };

        // These structures are kept to 16 bytes, and are meant to be align for very
        // fast access, and to take advanage of the intel cache. Also, the pather
        // uses memory tricks, so they *must* be 16 byte aligned.
        enum { QUADNODE_MEM_SIZE = NUM_QUADNODES*sizeof(QuadNode)+16 };
        U8                      quadNodeMem[QUADNODE_MEM_SIZE];
        QuadNode        *quadNodeArr;

        VertexBitArray vertexInUse;                     // Set if a vertex is used by the LOD system
        MapBitArray        mapPatherReserved;   // Set if reserved for a building

        int INV_DIR( int dir )  { return ( dir+4 )%8; }

        void InitQuadNodesRec( QuadNode* node, int x, int y, unsigned lod );

        // Divides up the terrain mesh until the polygons are as large as possible,
        // while still beneath the error threshhold. Called when a height change ends.
        void SplitAndMerge(     const grinliz::Rectangle2I& patchBounds, grinliz::Rectangle2I* update );
        
        // Clears out stuff in the quad tree for a change. QuadRender, MeshNodes, etc.
        // Be sure to follow with a call to CalcAllQuadRender and RestoreMeshNodes as appropriate.
        void ClearQuadTree( const grinliz::Rectangle2I& patchBounds );

        QuadNode* GetQuadNode( int x, int y ) 
        {
                if ( x < 0 || y < 0 || x >= MAPSIZE || y >= MAPSIZE )
                        return 0;

                QuadNode* node = &quadNodeArr[ PINDX( x/2, y/2 ) ];
                GLASSERT( grinliz::InRange( x, (int)node->x, (int)node->x+1 ) );
                GLASSERT( grinliz::InRange( y, (int)node->y, (int)node->y+1 ) );
                return node;
        }

        // Get a node's neighbor - very useful for pathing. The 'head' and 'tail' are both 
        // on the *outside* of the quad. They are ordered (positive), so the left side is the 
        // current node, and the right side is the neighbor. This also allows the neighbor 
        // poly to be found.
        QuadNode* GetNeighborNode( QuadNode* origin, int tailVertex, int headVertex, U32* poly );

        // Compute a particular render node. Can get called at odd times,
        // and during EndHeightChange/CalcQuadRenderRec
        void CalcQuadRender( QuadNode* node );

        #ifdef DEBUG
        // Debug check to see if the state of this object is consistent.
        bool ValidateQuadRender( QuadNode* node );
        #endif

        void CalcQuadRender( const grinliz::Rectangle2I& patchBounds );

        // For the x, y, and size, would 2 triangles be over the error thresh hold?
        bool IsErrorOverThresh( int x, int y, int size );

        void* QuadNodeToState( QuadNode* quadNode, U32 poly ) {
                GLASSERT( quadNode != 0 );      // 0,0 underwater
                // depends on the quadnode being 16-byte aligned
                GLASSERT( sizeof( QuadNode ) == 16 );
                GLASSERT( ( ((UPTR)quadNode) & 0xf ) == 0 );
                GLASSERT( poly >= 0 && poly < 16 );
                GLASSERT( quadNode->Render() );         // and have a render established

                void* result =  (void*)( ((UPTR)quadNode) | poly );
                GLASSERT( result != 0 );
                return result;
        }

        void* TerrainPointToState( float x, float y )
        {
                QuadNode* quadNode = 0;
                U32 poly;
                PointToPoly( x, y, &quadNode, &poly );
                return QuadNodeToState( quadNode, poly );
        }

        QuadNode* StateToQuadNode( void* state, U32* poly ) {
                GLASSERT( StateIsQuadNode( state ) );
                *poly = ((U32)((UPTR)state)) & 0xf;
                QuadNode* result = (QuadNode*) ( ((UPTR)state) & (~0xf) );

                GLASSERT( result != 0 );
//              GLASSERT( result->Leaf() );             // should always be a terminal node
                GLASSERT( result->Render() );           // and have a render established
                return result;
        }

        bool StateIsQuadNode( void* state ) {
                if ( state >= quadNodeMem && state < ((U8*)quadNodeMem+QUADNODE_MEM_SIZE) )
                        return true;
                return false;
        }

        QuadNode* StateToQuadNode( void* state ) {
                GLASSERT( StateIsQuadNode( state ) );
                QuadNode* result = (QuadNode*) ( ((UPTR)state) & (~0xf) );
                GLASSERT( result != 0 );
                GLASSERT( result->Render() );           // and have a render established
                return result;
        }

        // filter a path
        void FilterPath( void **states, unsigned size );                
        // firter a path of all QuadNode (called by FilterPath)
        void FilterTerrainPath( void **states, unsigned size );

        void StreamOutLandRec(  Lilith3D* lilith, 
                                                        QuadNode* node, 
                                                        int frustum );  // positive (fully inside) or intersecting

        float OceanIntensity( float eyeX, float eyeY, float vX, float vY )
        {
                float len = grinliz::Clamp( grinliz::Length( eyeX - vX, eyeY - vY ), 0.0f, FAR_PLANE_DISTANCE );
                return 0.5f + 0.5f * ( 1.0f - len / FAR_PLANE_DISTANCE );
        }

        enum {
                NORMAL_DIVISIONS = 31,  // works better odd
                NUM_LAYERS = 4,
        };
        
        grinliz::LineLoop frustum2D;

        // When culling is complete, the start and end [start,end] are computed.
        // The culling bounds are computed mathematically, and stored here.
        struct Range {
                int start;
                int end;

                int Length()                            { return end-start+1; }
                void Init( int s, int e )       { start = s; end = e; }
        };
        // Subtle behavior here: a vertex is a mathematical point, which is or isn't visible.
        //                                           a patch is a square - if any part is visible, all is
        // The vertices are computed, but the patch is usually what is queried for occlusion -
        // or even color computation since colors are interpolated between vertices that may
        // not be visible.
        //
        Range vertexRange[ VERTEXSIZE ];
        Range patchRange[ PATCHSIZE ];
        Range waterPatchRange[ WATER_PATCHSIZE ];

        // At culling, compute the bounds of all the vertices, +1 extra row for color interpolation
        grinliz::Rectangle2I looseVertexBounds;
        grinliz::Rectangle2I looseWaterVertexBounds;

        #ifdef DEBUG
        // For debugging, which quads were rendered.
        grinliz::BitArray< PATCHSIZE, PATCHSIZE > quadsDrawn;
        #endif

        // The un-clipped terrain dimensions
        grinliz::Rectangle3F corners;   

        // Vertex strip used to render
        unsigned int waterStrip[ WATER_VERTEXSIZE*2 ];

        struct TVertex
        {
                grinliz::Vector3F pos;
                grinliz::Vector3F normal;
        };
        TVertex tvertex[ VERTEXSIZE * VERTEXSIZE ];
        
        struct WVertex
        {
                grinliz::Vector3F pos;
                grinliz::Vector2F tex;
        };
        WVertex wvertex[WATER_VERTEXSIZE*2];

        U32 vboTVertex;
        U32 vboWVertex;

        int waterPoly;
        int landPoly;           // actual unique triangles sent
        int landQuad;           // the number of quads (not subdivided) sent
        int overPoly;           // tris sent counting overdraw

        bool heightChange;
        bool heightChangeInit;
        grinliz::Rectangle2I heightChangeBounds;                // vertex bounds
        grinliz::BitArray< VERTEXSIZE, VERTEXSIZE > heightLockArray;
        bool regenHeightArray;
        std::list< grinliz::Rectangle2I > heightLock;
        micropather::MicroPather pather;

        // Used to add randomness to the 3D texturing.
        enum { FUZZ_3D_COUNT = 64 };    // power of 2
        float fuzz3D[ FUZZ_3D_COUNT ];

        //              TERRAIN_MIN-->0.0 maps to 0.0-->SPLIT
        //              0.0-->TERRAIN_MAX maps to SPLIT-->1.0
        float TextureZ( float z, int index ) {
                const float SPLIT = 0.35f;
                const float SPLITM1 = ( 1.0f - SPLIT );
                if ( z > 0.0f )
                        return z / TERRAIN_MAX * SPLITM1 + SPLIT + fuzz3D[index&(FUZZ_3D_COUNT-1)];
                else
                        return ( z - TERRAIN_MIN ) / (-TERRAIN_MIN) * SPLIT;
        }

        // Buffers used by the drawing routine.
        enum { 
                INDEX_BUFFER_SIZE = 1000,
        };
        U32 triIndexBuffer[INDEX_BUFFER_SIZE];

        grinliz::Vector3F _eye;
        Lilith3D* _lilith;
        const Texture* _terrainTex[NUM_LAYERS];
};
};
#endif

---