2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ An additional question: Is there any reason not to generate a mesh / vertex data (Using something like Marching Cubes, or a height map + other methods) and storing the mesh, rather than say the voxel data or height map image? Would it remove enough of the processing required to make it worth while? \$\endgroup\$
    – Jon
    Feb 11, 2013 at 8:10
  • \$\begingroup\$ Can you use something like CUDA to generate it first? \$\endgroup\$ Feb 13, 2013 at 5:44

3 Answers 3

2
+50
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks a bunch :). Also, I actually came across this blog before, but I didn't pay any attention to it since I hadn't considered using marching cubes to only generate the data once and use that. On a related note, in your opinion - do you think that's the best method for generating good looking landscapes? I have really only see Marching Cubes discussed as an option for dynamic terrain. Oh and for the record, I knew that vertex data only needed to be updated on change, not every frame. \$\endgroup\$
    – Jon
    Feb 13, 2013 at 18:06
  • \$\begingroup\$ The methods used in Shamus' Project Octant should produce good terrain for you. Although he moves away from simple cubes / other stuff, mixed into that article should be good information for you. \$\endgroup\$
    – E.T.
    Feb 13, 2013 at 18:24
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 1. Ideally GPU, however since I'm using XNA, which even in HiDef mode only supports DX9 - I'd say I'm stuck with CPU. I've also read through that chapter, and iirc it requires DX10. 2. Not massive, but yes larger. Breaking the terrain into "Chunks" is trivial with an algorithm like simplex noise, however. 3. Mountains, and plains. The noise generation isn't my problem, per se. The caves aspect is, to an extent though. \$\endgroup\$
    – Jon
    Feb 11, 2013 at 17:26
  • \$\begingroup\$ Procedural terrains: I was planning to use Simplex noise, actually - but yeah, I want terrain that looks ... Not life like, but definitely realistic. I.e. Mountains, plains, etc. Surface Extraction: This is my main problem and what I'm looking for solutions to. I'll definitely have to check out the blog post, thanks. Thanks in general for the post, and I've seen Polyvox and it looks great but its C# bindings aren't all that great right now, sadly. \$\endgroup\$
    – Jon
    Feb 11, 2013 at 17:26
0
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ He specifically mentioned that marching cubes isn't a good option. \$\endgroup\$
    – ashes999
    Feb 11, 2013 at 3:24
  • \$\begingroup\$ And I'm telling him why he's wrong. \$\endgroup\$
    – jmegaffin
    Feb 11, 2013 at 4:57
  • \$\begingroup\$ I just wanted to say I appreciate the reply, and I'm not the one who downvoted you. You didn't answer the main question I wanted answer, but you provided some useful information, so thanks. \$\endgroup\$
    – Jon
    Feb 12, 2013 at 8:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .