Hightmaps (as they are called) uses an X,Z array of hights, and a triangle mesh is placed over the top of it. These are VERY common, and used everywhere, even today (usually in rolling landscapes).
This might still work if you were to use somesort of refining hight map. For example. Your basic grid is 256x256 points. Lets say you blow up something, you can then "refine" a section of it to a higher res, kind of like an oct-tree.
This would let you have far better detail on groud removal, and couldyou could keep going till you hit almost pixel levels.
This is probably the 3D equivalent of what I did on the SNES in allocating blocks when things changed. I had a static set, then allocated ones I could draw into as things changed. It was quite complicated back then being all in assembler, and on a slow machine... but these days, it should be easy enough.
Or you could try the same with voxals... the hightmap is better IMHO though....
