There are a million approaches to terrain, but I highly recommend sticking with a regular grid. Some algos use a TIN or triangle irregular network but real time mesh deformation becomes a chore with those.

The simplest grid I can come up with is. Some of this is Direct3D but most of it is non API specific.

**CTerrain.h**

Code:

#define TERRAINVERTEX_FVF D3DFVF_XYZ | D3DFVF_TEX1
struct TerrainVertex
{
float x,y,z;
float TexU,TexV;
static const DWORD FVF;
TerrainVertex(float fx,float fy,float fz,float fu,float fv):
x(fx),y(fy),z(fz),TexU(fu),TexV(fv) { }
TerrainVertex():x(0.0f),y(0.0f),z(0.0f),TexU(0.0f),TexV(0.0f) { }
};
class CTerrain
{
protected:
TerrainVertex *m_pVerts;
//For quad tree
CBoundingBox *m_pBoundingVolume;
....
....
};

Code:

#include "TerrainVertex.h"
#include "CTerrain.h"
void CTerrain::Create(int iWidth,int iDepth,int iCellSize,float fTexWrap)
{
//Compute verts per row and col
m_iNumVertsPerCol=iDepth;
m_iNumVertsPerRow=iWidth;
//Compute cells per row and col
m_iNumCellsPerCol=m_iNumVertsPerCol-1;
m_iNumCellsPerRow=m_iNumVertsPerRow-1;
//Compute total verts and number of triangles
m_iNumVerts=m_iNumVertsPerCol*m_iNumVertsPerRow;
m_iNumTris=m_iNumCellsPerCol*m_iNumCellsPerRow*2;
//For index buffer if needed - not used in this sample
m_iNumIndices=m_iNumTris*3;
//Allocate vertex buffer
m_pVerts=new TerrainVertex[m_iNumVerts];
if (!m_pVerts)
{
//Bail gracefully here since we could not allocate enough memory for vertex buffer
...
...
return;
}
//Compute starting world locations for grid
int iStartX=-(iWidth>>1)*iCellSize;
int iStartZ=(iDepth>>1)*iCellSize;
int iEndX=-iStartX;
int iEndZ=-iStartZ;
//Texture coordinate information
float u=0.0f,v=0.0f;
float fUInc=fTexWrap/(float)iWidth;
float fVInc=fTexWrap/(float)iDepth;
//Vertex height
float fHeight=0.0f;
//Row and col counters and index into array of verts
int iRow=0,iCol=0;
int iIndex=0;
for (int z=iStartZ;z<iEndZ;z-=iCellSize)
{
for (int x=iStartX;x<iEndX;x+=iCellSize)
{
float fHeight=(float)m_pHeightMap->GetHeight(row,col);
m_pVerts[iIndex]=TerrainVertex((float)x,fHeight,(float)z,(float)iRow*fUInc,(float)iCol*fVInc);
iIndex++;
iCol++;
}
iCol=0;
iRow++;
}
}

If I coded everything correctly there it will give you a simple regular grid of vertices. I coded this from memory while sitting here so I'm not guaranteeing it will work as is. After this you could create an index buffer and index into this vertex buffer to form each triangle. Or you can brute force it and do this while rendering.

Note that since we get the value from a heightmap if you alter the heightmap and the corresponding vertex in the vertex buffer, you can deform the terrain. This can also be used to make a water plane applying a simple or complex water wave equation to produces waves across the grid. This gets into the area of displacement mapping and so I won't go into it.

An ideal system would use the above algo to create a quadtree of the entire terrain world. Then at runtime you compute which areas are inside the frustum and draw those. The algo I presented can be changed to produce sections of regular grids all lined up next to each other.

A simple quad tree structure would be:

Code:

enum TERRAIN_NODE_TYPE
{
LEAF_NODE,
BRANCH_NODE
};
struct TerrainNode
{
TERRAIN_NODE_TYPE iNodeType;
CTerrain *pUpperLeft;
CTerrain *pUpperRight;
CTerrain *pLowerLeft;
CTerrain *pLowerRight;
};

This should get you headed on the right track. Lots more info can be found at www.vterrain.org.

This screenshot was produced with the above algo, with some added 'stuff'.