Methods of procedural terrain generation that can work using DirectX 9 (SM2.0)?

Question

I'm working on a simple game / fun project that I want to be largely procedurally generated. At first I started by using boxels (Similar to Minecraft, but not textured) for the terrain and it came out looking decent but I realized something.

I don't need, or really want, destructible terrain. Sure it'd be a nice little bonus, but no part of my game design calls for it, and using boxels requires a fair amount of data to be sent to the GPU, so I'm looking for alternatives and that's where I'm stuck...

What are some alternatives to boxels that can be used to generate terrain quickly, that looks good (Smooth terrain or otherwise), and can be rendered with XNA (Shader Model 2.0)? At first I thought that marching cubes could work, however apparently since XNA still uses DX9 - most of the work is done on the CPU. Then I looked into dual contouring, but I can't find much data on it and I'm afraid it suffers the same issues.

Right now height maps are looking halfway decent, however I don't want to abandon the idea of overhangs and whatnot completely, so... What else is there? I'd love to keep using voxels since they make procedural generation easy (And fun), but, and correct me if I'm wrong, XNA doesn't handle non-boxel rendering of them very well.

(Even if I'm wrong re: marching cubes, I'd still be interested in seeing worth-while alternatives that can run on low end machines using SM2)

Note: My highlighting of words is to help anyone who, like me, finds this after searching for methods of procedural terrain generation, and wants a quick list of what's available.

Edit: Still looking for an answer regarding different methods.

Answer 1

Firstly, from your question, it sounds like you want to generate the polygons and texture coordinates on the fly, for every frame of your game. This is bad. No, really. There is no algorithm to take volumetric datasets and quickly turn them into surface/area datasets. (Read: Take volumes of data and use it to push flat triangles onto the screen.) Realize that what marching cubes, dual contouring, and other algorithms are doing is reducing volumetric data down to surface/area data, which is an order of magnitude easier to deal with. Hardware is fast, but not that fast. Volumetric data is big, if you've got it detailed enough to make it look good.

Remember that the time required for marching cubes is O(n * m), where n is the number of cubes, and m is the cost of getting the scalar value a corner of a cube. Since you're presumably going to have a large map, you're not going to want to recalculate things which aren't changing. Since your terrain won't be destructible, this means that:

• Your noise function only needs to be called once to get your scalars for marching cubes.
• Your marching cubes function only needs to be used once to get your terrain, with its corresponding image/collision data. (bounding boxes, triangles, texture coordinates, etc)

So, you need to separate the following into discrete steps:

• Noise creation.
• Terrain creation. (i.e. Marching cubes.)
• Terrain culling.
  • i.e. Remove sections of the map which the player would never interact with.
  • e.g. A hollow cave inside a mountain, without an entrance accessible to the player.
• Polygon/texture-coordinate generation.
  • If you're using marching cubes, you'll already have the polygons, but will still need to compute texture coordinates, lighting normals, etc.

After this point, regular optimizations, occlusion-testing, lighting, etcetera are the same as a normal game.

You should read through Shamus Young's programming section on his blog. At minimum, read about his Project Octant, which deals with overhangs/cliffs, and is a simple/fun project, like yours. You could also read through his Terrain Project and Project Frontier, although both of those earlier works use height-maps. His Pixel City project also deals a lot with simplifications, and approximations.

Answer 2

Its not really clear what your deliverable are here so its hard to define a "right" answer for you:

1. Must the solution be developed on the GPU or CPU?
2. Do you need to be able to stream massive terrains?
3. What kind of procedural landscape? Do you want to simulate mountains, rivers, oceans, caves?

All these questions and more need to be answered before any kind of concrete solution can be presented.

However I may be able to help you with some resources...

CPU or GPU based generation?

Most people would quickly tell you that the GPU is by far and away the best tool for procedural generation of terrain and the generation of it into a renderable polygonal surface, and they would be right. However it does add complexity and online resources are slightly less abundant. Secondarily, you sound like you have a requirement for your application to work on older hardware. This will be one more problem you'll have to solve on top of writing the surface generation algorithm on the GPU. All 100% doable. But it adds time and complexity. If you are feeling up to it there is a great article in the GPU Gems 3 website on this very topic.

The CPU is actually perfectly capable of generating a procedural terrain in real-time, and it is extremely well documented. If I were you I'd make my first pass on this project of yours completely CPU-based.

Procedural Terrains

Without knowing a little more about what you actually want to simulate I can't really provide much assistance. By far the most simple thing you could possibly do is just run a Perlin Noise function over your entire voxel terrain.

Surface Extraction

Once you've generated your terrain you need to display it. There are quite a few algorithms available to perform this function however there are a couple that stand out. The single best resource I have found to date on surface extraction has been by sdfdsf at 0FPS. He recently wrote a somewhat lengthy blog post on the lending real-time algorithms one can use to generate a smooth surface from voxel data. He even provides javascript-based examples. (Surface Nets are awesome!)

To close this off I might also point you in the direction of a great C++ based project called PolyVox. Its a great little library that can quickly get you off the ground with voxels.

Answer 3

Marching cubes is a pretty efficient algorithm. It's just a couple of lookups per cube and it works in O(n) time. You can also run it in parallel very easily using a thread pool, so even if it's constrained to the CPU it's pretty fast.