Well you always have voxel based terrains (look into Marching Cube and Marching Tetrahedron methods). This allows you to put data on the range of only a single byte into each voxel then the algorithm will reconstruct itself. Going from data to mesh is very, very easy once you understand the algorithm. Going from mesh to voxels is a bit more difficult but possible. To do overhangs you need octrees or some other 3d data type ... you just do.
Also if you are doing stuff in patches you need to make an algorithm for patching your terrains together if you want to operate on them independently.
So something like
class Patch
{
//If Z is equal to 1 or 0 you evaluate it like a piece of a quadtree
//else evaluate it as a octree
private:
int dimX, dimY, dimZ;
float scale; //Scale of each unit of the dataset so we can map
//to real world coordinates.
int sizeXY; //getting Z slice is dimZ*sizeXY;
byte* values; //Assuming you use marching cube algorithm
public:
//Getters / Setters
};
//Convient thing about marching cube is it guarantees
//alignment of your patches if aligned patches have same resolution!
//Warning: Your terrain will follow the same
//general flow but it probably won't be the exact same.
class MarchingCubeConverter
{
//Map of byte value to vertex coords. You can get this
//From white-papers
public:
//Converts a given mesh specified by some coordinates to a voxel
//format with a given resolution and scale.
static void BuildPatch(Mesh* mesh,vec3 limits,dim3 resolution);
//Converts voxel data to a 3d mesh
static void BuildMesh(Patch* patch,Mesh* mesh);
};
Other option is if you don't want to do marching cube is to create your own quadtree structure that can be an octree if the data needs the 3rd dimension. Look at the patch class above and just when moving across the structure test for the Z dim to decide what you do with it. If you don't do marching cube though you would be saving overhands and stuff into a single unit of your quadtree. You only need that 3rd dimension if you plan on splitting the mesh along that 3rd dimension.
Psuedo-code for patching your terrain assuming you only care about 2 dimensional break-up. Should be straightforward to implement to the third dimensions.
void PatchTerrainMesh(QuadTreeNode<Patch>* node,Mesh* mesh,
int VertexPatchLimit)
{
//Test if the x-y dimensions are within your xy extents
//return the number of vertices that are within that limit.
int Vertices = FindContainedVertices(mesh,(*node)->extents);
if(Vertices > VertexPatchLimit)
{
node->subdivide(); //We now have 4 patches with appropriately divided extents
PatchTerrainMesh((*node)[0],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[1],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[2],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[3],mesh,VertexPatchLimit);
}
else
{
ExtractPatchFromMesh(node,mesh);
}
}
void ExtractPatchFromMesh(QuadTreeNode<Patch>* node,Mesh* mesh)
{
//This is the hard part but i'll give some psuedo code to help.
//Need to actually get the vertices you need
vector<int> containingVertices = BuildContainingIndexList(mesh,node->extents);
Line boundaries[4];
ConvertExtentsToBoundaryLines(&boundaries,node->extents);
for(int i = 0;i < containingVertices.size();++i)
{
for(int j = 0;j < mesh->indices.size();++j)
{
if(containingVertices[i] == mesh->indices[j])
{
int start = j - j % 3; //Need the start of the triangle
Triangle tri = Triangle(mesh->vertices[start]
,mesh->vertices[start + 1]
,mesh->vertices[start + 2]);
int intersection = TriangleBoundaryIntersection(&tri,boundaries))
switch(intersection + 1)
{
case 0:
//Add tri to list, no collision
break;
case 1:
//need to subdivide the triangle based on
//line [0]
break;
case 2:
//need to subdivide the triangle based on
//line [1]
break;
//etc....
}
}
}
}
}
