How to upgrade a heighfield terrain

An interesting idea. Yeah, the constraint of matching the number of vertices along top and bottom of cliff seems awkward - were you thinking of creating the cliff mesh in a modelling package with the correct number of boundary vertices and then inserting it directly into the heightfield with some other tool (like a tool that you''ll write specifically for this purpose) ? I suppose you could always add functionality to the heightfield tool to allow it to weld/crack-fix the boundary of cliff mesh to the boundary of the hole in heightfield, but that depends on your situation I guess.

Assuming a chunked quad-tree heightfield LOD scheme you could clip the cliff mesh to the quadtree and throw the clipped parts in with the heightfield chunks belonging to the quadtree nodes (since vertex/index buffers don''t distinguish between heightfields and polygon soups) but then using vertical skirts to hide the cracks (like Thatcher Ulrich does) wouldn''t work anymore so some other crack-fixing scheme would be needed. Also to get LOD in the vertical direction you''d need an octree(instead of quadtree) but probably wouldn''t need it unless cliffs are really high.
Actually Jonathan Blow has a 5-part article in game developer magazine (starting march03) called "Unified Rendering LOD" - part of which describes a crack-fixing scheme that works for polygon soups which would work well here. So you don''t worry about patches initially and just cut a slice through your terrain heightfield to open a hole (maybe the slice has to pass through the regular grid points) and then insert your cliff or overhang mesh - so now you''ve got a mixture of heightfield and polygon soup. Then you generate your vertical quadtree clip planes and assign geometry to quad-tree nodes/patches. The clip planes are aligned with the heightfield grid (because of quadtree) and hence don''t generate extra triangles for the regular heightfield data (only for the arbitrary cliff meshes). Then you apply simplification to the quadtree nodes in pre-process and use Jon Blow''s crack-fixing scheme. This would synchronise/unify the LOD of heightfield and cliff meshes. This might also get around the limited tile-based cliff variations since your cliff is carved up automatically by the quad-tree clip planes.


I''ve been thinking about this same general problem lately and here''s what I''ve been thinking of if you have any comments/ideas/suggestions...

I''m currently considering catmul-clark subdivision surfaces which are an extension of b-spline patches to arbitrary topology. So you start off with a regular square grid of control points which can only move vertically - this is nothing more than a smooth regular heightfield - and this is used over the majority of the terrain. To get overhangs, cliffs, arches and tunnels, in localised areas of the terrain, you take a set of square patches and replace them with another set of square patches which agree on the boundary. An example of this is taking a single square patch of the regular heightfield and extruding it so that it becomes a cube poking out of the heightfield. Each cube gives you four new control points which you allow to move in *any* direction (not just vertically like the regular heightfield control points) so that you can generate interesting features. For instance you could keep extruding off the cube (hence creating more cubes) giving you a linear sequence of cubes which you could bend and then reattach final cube back onto regular heightfield, at another square patch of heightfield, to get an arch (or a tunnel if you extrude into terrain instead of out of terrain). So this is just your arbitrary topology control mesh - the final surface mesh is generated by applying the subdivision rules to the control mesh up to the desired level of tessellation (for catmul-clark subdivision surfaces, one level of subdivision divides each square patch into four smaller square patches). The subdivision rules ensure that the final surface is smooth everywhere, but since smooth is boring you could add surface roughness with something like fractal displacements along the surface normals.

You could extend this hierarchically so that you can make coarse, as well as detailed, changes (eg from a cliff along a valley down to a small overhang)...
The hierarchical idea of topology changes is described in part 2 of http://cm.bell-labs.com/who/wim/papers/hybrid/ (the rest of paper is not relevant).
The hierarchical editing of subdivision mesh is described at http://graphics.stanford.edu/~dzorin/multires/meshed/.

Cons:
- the surface is smooth so generating sharp features requires either incorporating special crease subdivision rules or displacement maps.
- doesn''t incorporate irregular meshes (eg, an overhang you created in a polygon modelling package), so you have to rely on subdivision surface edits directly on the terrain.
- need to include subdivision surface editing ability in terrain tool.
- probably overkill if the overhangs,cliffs,arches,etc are small and cover a small part of the terrain.
- need to extend terrain texturing to arbitray topology because seamless, tileable, terrain textures only work for regular meshes (eg heightfield grid) and breakdown at extraordinary vertices.

Pros:
- natural extension of smooth surface heightfield to arbitrary topology.
- LOD can follow surface subdivision.
- avoids some problems inserting irregular mesh into hole in heightfield terrain since edits are done directly on the terrain.
- final arbitrary topology surface is made up of square patches so texturing might be easier if can use patch parameterisation somehow and if using texture splatting then texturing might appear more continuous.

I think the cons outway the pros. I think your way is better - just need some way to make the geometry and the texturing seamless and continuous.

quote:

---

Original post by Soiled

---

Thanks, very ineteresing.
But I can''t see how that will be handled with geomipmapping. And it is difficult to edit, I think.
Excuse me for crossposting, but see that if you are interested in further discussion:
http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00009411&forum=3dtheory&id=-1

I think geomipmapping would work with catmull-clark subdivision surface since it''s quad-based. Though editing might not be so easy.

Regarding "Unified Rendering LOD" the deltas required for geomorphing require tracking the vertices as they get simplified from one LOD level to the next coarser one. For geomipmapping this is easy but for irregular meshes that get inserted into heightfield (such as cliffs, overhangs) quadric-error-metric simplification is used in which case http://www.gamasutra.com/features/20000908/lee_02.htm can be used.