Intelligently simplifying a terrain mesh?

[Freakrules]

Following Problem: I have a terrain mesh made of a subdivided plane with an applied heightmap. Now I want to decimate it to something more game-suitable (not 100k polys as now), possibly without losing detail. Is there any approach to do this? I use Blender, Max, Maya and Zbrush

This picture from Overgrowths simplification-algorithm illustrates exactly what I want to do to my mesh:
[thumb]http://cdn.wolfire.com/blog/terrain_simp11.jpg[/thumb]

Thanks in advance for all suggestions!

[Deunan]

if it's in quads, decimation along edges might work pretty well. if tris or ngons you're probably out of luck I guess.