18
\$\begingroup\$

In relation to Heightmap, Voxel and Polygon (geometry) terrains:

  1. What are the main differences between all these three?
  2. Can you form a "smooth" terrain with Voxels, I mean, can you for example get a smooth mountain with Voxels, or Voxels are limited to cubes?
  3. Performance wise, a world 2000x2000 units, what would be faster Heightmap terrain, Voxel terrain or Polygon based, geometry terrain? (Assuming that there is "reasonable" performance gains/optimization done for rendering for every of possibilities)
  4. Are there any more techniques used for terrain creation?
  5. Any good titles representing each of types?

P.S. Polygon based terrain should be fully traingulated, no squareish stuff.

\$\endgroup\$

2 Answers 2

34
\$\begingroup\$

Heightmaps

With a heightmap, you store only the height component for each vertex (usually as 2D texture) and provide position and resolution only once for the whole quad. The landscape geometry is generated each frame using the geometry shader or hardware tessellation. Heightmaps are the fastest way to store landscape data for collision detection.

Pros:

  • Relatively low memory usage: You only need to store one value per vertex and no indices. It's possible to improve this further by using detail maps or a noise filter to increase perceived detail.

  • Relatively fast: The geometry shader for heightmaps is small and runs fast. It's not as fast as geometry terrain though.
    On systems without triangle based 3D acceleration, ray marching heightmaps is the fastest way to render terrain. This was referred to as voxel graphics in older games.

  • Dynamic LOD/terrain: It's possible to change the resolution of the generated mesh based on distance from the camera. This will cause the shifting geometry if the resolution drops too far (around 0:40), but can be used for interesting effects.

  • Easy terrain generation/creation: Heightmaps can easily be created by blending noise functions like fractal Perlin Noise and heightmap editors are fast and easy to use. Both approaches can be combined. They are also easy to work with in an editor.

  • Efficient physics: A horizontal position maps directly to (usually) one to four positions in memory, so geometry lookups for physics are very fast.

Cons:

  • Exactly one height per x/y coordinate: There usually can't be holes in the ground or overhanging cliffs.

  • Less control: You can only control the precise height of each point if the grid size matches the texture coordinates.

  • Artifacts: If the four vertices that define a sub-quad aren't on the same plane, the split between the two vertices will become visible. This usually happens on steep cliffs with edges that don't follow a cardinal direction.

Heightmaps are the most efficient way of rendering terrain by far and are used in many newer games that don't rely on advanced terrain features and have large outdoor areas. Wikipedia has a list of programs that use heightmaps, but I'm not sure if that means they only use them as resources or also for rendering, so here a some games that are likely to use them:

  • Just Cause 2: Regions are loaded in square sectors and there are no holes in the terrain. In the demo, there's a deep hole with stretched triangles along the edges where there normally would be a building. (The area is normally inaccessible, but there are mods to remove some of the demo's limitations...)

  • Sims 2 (maybe): Neighborhood terrain is loaded as heightmap, but there are holes where lots (building sites) are placed. There are typical artifacts if you create cliffs on a lot, though, and it's quite tedious to add a cellar to a house (and hide the cliff under a veranda).

  • Valve's Source engine games: Rectangular brushes (static level geometry) can have heightmapped terrain on their faces. In these games, the usual quirks are often hidden with other brushes or props.

It's impossible to tell for sure without looking at the shaders because every heightmap terrain can be rendered as mesh.

Voxels

Voxel terrain stores terrain data for each point in a 3D grid. This method always uses the most storage per meaningful surface detail, even if you use compression methods like sparse octrees.

(The term "voxel engine" was often used to describe a method of ray marching terrain heightmaps common in older 3D games. This section applies only to terrain stored as voxel data.)

Pros:

  • Continuous 3D data: Voxels are pretty much the only efficient way to store continuous data about hidden terrain features like ore veins.

  • Easy to modify: Uncompressed voxel data can be changed easily.

  • Advanced terrain features: It's possible to create overhangs. Tunnels are seamless.

  • Interesting terrain generation: Minecraft does this by overlaying noise functions and gradients with predefined terrain features (trees, dungeons). (Read Terrain Generation, Part 1 in Notch's blog for more info. There is no part 2 as of 05.8.2011.)

Cons:

  • Slow: To render voxel data, you either have to use a ray tracer or compute a mesh, for example with marching cubes (There will be artifacts). Neighboring voxel aren't independent for mesh generation and the shaders are more complicated and usually produce more complex geometry. Rendering voxel data with high LOD can be very slow.

  • Huge storage requirements: Storing voxel data uses lots of memory. It's often not practicable to load the voxel data into VRAM for this reason, as you'd have to use smaller textures to compensate for it, even on modern hardware.

It's not practical to use voxels for games that don't rely on voxel features like deformable terrain, but it can allow interesting game mechanics in some cases. Voxel engines are more common in older games, but there are also newer examples:

  • Atomontage engine: Voxel rendering.

  • Worms 4: Uses "poxels". According to Wikipedia it's a mix of voxels and polygons.

  • Minecraft: Uses voxel to represent the terrain in RAM, the graphics are polygon graphics. It's mostly software calculated though.

  • Terraria: An example for 2D voxels. I don't know how it renders.

  • Voxels combined with physics: Not a game. but it nicely showcases the destruction potential.

  • Voxatron: A game using voxels for almost all of the graphics, including menus and HUD.

Meshes

Polygon meshes are the most flexible and precise way of storing and rendering terrain. They are often used in games where precise control or advanced terrain features are needed.

Pros:

  • Very fast: You only have to do the usual projection calculation in the vertex shader. A geometry shader isn't needed.

  • Very precise: All coordinates are store individually for each vertex, so it's possible to move them horizontally and increase mesh density in places with finer details.

  • Low memory impact: This also means the mesh will usually need less memory than a heighmap, because vertices can be more sparse in areas with less small features.
    (See Triangulated irregular network on Wikipedia).

  • No artifacts: The mesh is rendered as-is, so there won't be any glitches or strange-looking borders.

  • Advanced terrain features: It's possible to leave holes and create overhangs. Tunnels are seamless.

Cons:

  • Poor dynamic LOD: Only possible with precomputed meshes. This will cause "jumps" when switching without additional data to map old to new vertices.

  • Not easy to modify: Finding vertices that correspond to an area that should be modified is slow.

  • Not very efficient for collision detection: Unlike in heightmaps and voxel data, the memory address for a certain location usually can't be calculated directly. This means physics and game logic that depend on the exact surface geometry will most likely run slower than with the other storage formats.

Polygon terrain is often uses in games that don't have large open areas or can't use heightmap terrain because of its lack of precision and overhangs. I don't have a list, but I'm pretty sure that

  • every 3D Zelda and

  • every 3D Mario game

use this.

Other methods

It's possible to create a terrain entirely in the shader pipeline. If the algorithm runs only in the fragment/pixel shader, the detail can be virtually unlimited while memory impact is almost zero. The obvious downsides are almost no control over the shape and problems when the camera intersects the original rendering surface. It's still useful in space games where players don't interact with the surface of a planet. Parameter animations work best with this kind of terrain.

It should be possible to download the generated terrain geometry from the graphics card to use it for the rest of the game engine, but I don't know how the performance of that is or whether this has been done so far.

Conclusion

There is no method that works well for every scenario, but it's fairly easy to choose one for a certain task:

  • Heightmaps are the best solution if you don't need overhangs or holes in the terrain surface and use physics or dynamic terrain. They are scalable and work well for most games.

  • Meshes have the highest precision and can describe overhangs, holes and tunnels. Use them if you have complex terrain that doesn't change often.

  • Voxels are good for describing very dynamic terrain with many complex features. Avoid rendering them directly as they need large amounts of memory and processing.

  • Other methods may be better than any of the above if you don't have to interact with the terrain or need very detailed graphics. They usually work only for very specific scenarios.

It's possible to combine different methods to get features from more than one, for example by tessellating mesh terrain with a heightmap to increase the detail structure of a cliff.

Dynamic terrain generation is heavily used in procedural space simulation and some have become really advanced in the last years. The forums of these projects should have some resources on the topic.

\$\endgroup\$
10
  • 3
    \$\begingroup\$ Source engine doesn't use heightmaps for its terrain. They use tesselated quads called "Displacements" developer.valvesoftware.com/wiki/Displacement \$\endgroup\$
    – Tetrad
    Aug 5, 2011 at 22:05
  • 1
    \$\begingroup\$ That's a sweet answer there, would give a +3 on this one, if it was possible. Thanks for the detailed information, much appreciated. \$\endgroup\$ Aug 5, 2011 at 22:28
  • \$\begingroup\$ @Tetrad Available resolutions for displacements are powers of two (a common restriction for texture buffers), the only coordinate saved per vertex is the height and terrain heightmaps are rendered as tesselated quads. The wiki also says the rendering cost of displacements is lower than that of regular geometry. I think it's fair to assume that they are the same thing with different names. \$\endgroup\$
    – Tamschi
    Aug 5, 2011 at 22:34
  • 1
    \$\begingroup\$ @NickWiggill The meaning of "voxel" seems to have changed quite a bit in the last 10 years. I'm going with the current Wikipedia definition of voxels as values on a regular 3D grid. The entry on Outcast mentions the difference in meaning. I've added to my answer to clarify this. \$\endgroup\$
    – Tamschi
    Nov 6, 2011 at 19:39
  • 2
    \$\begingroup\$ Side note: The "polygon terrain" is also called "Triangulated Irregular Network" ("TIN" for short) in GIS; and it is usually significantly less memory intensive than a heightmaps of the same effective resolution, since it doesn't bother with recording non-essential data or places where there is no data. The first Gothic game used it (not sure about the others). \$\endgroup\$ Nov 7, 2011 at 8:54
9
\$\begingroup\$

I'd like to point out that none of the terms you mentioned are mutually exclusive with each other - you could even have a voxel based game that used heightmaps and rendered using polygons.

  1. Height-maps are two-dimensional representations of the height of the ground at each specific point. They are often stored as greyscale images, where the brightness represents the height of that point. Voxels are basically a 3D bitmap. There are a variety of techniques used to render a voxel space.

  2. You can create a smooth terrain with voxels, and they aren't limited to cubes. One such way is to use an algorithm like marching cubes, which can convert a voxel representation into a polygon list.

  3. The one with the least triangles would render the fastest :3

  4. Fractal algorithms such as Perlin noise can be used to create landscapes with a lot of
    detail. Parametric surfaces such as nurbs can be used to create smooth terrains with little permanent storage requirements.

  5. Delta Force is an old game that uses voxels. Minecraft may use voxel storage to represent the landscape (unsure). Sacrifice by Shiny is a game that uses heightmaps to good effect. Most games with landscapes use geometry terrains.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ One note, on point 3, while the GPU only cares about polygon count, there's still the geometry generation side of things. Generating geometry for a voxel field is usually a slower process (blocks/marching cubes are both more complex processes) than heightmap terrain (which is a simple process), or polygon based (which is obviously already geometry data). Edit: this also depends on whether you intend the terrain to be deformable. \$\endgroup\$
    – Michael
    Aug 5, 2011 at 5:57
  • \$\begingroup\$ For the 3rd point... Well, heightmap still have to be processed and only then it forms into a geometry, right? Keeping that in mind, a polygon mesh would be a tad faster? Could you point out some of the techniques used to render voxels? \$\endgroup\$ Aug 5, 2011 at 8:16
  • 2
    \$\begingroup\$ You can use a geometry shader to generate the mesh from a heightmap. This way you store only the heightmap and parameters like position and resolution while geometry is generated each frame in the shader pipeline. It's faster than marching cubes and slower than a polygon mesh. The advantage of heighmaps is the low memory consumption: only a bit more than 1/3 of what a mesh would need. The downside is that it's not as flexible (no small details, no overhangs). You can dynamically adjust the detail of the generated mesh, but this causes shifting geometry. \$\endgroup\$
    – Tamschi
    Aug 5, 2011 at 12:53
  • \$\begingroup\$ @Tamschi, if only you'd provide that an answer, exactly what I was looking for. :) \$\endgroup\$ Aug 5, 2011 at 16:58
  • \$\begingroup\$ @Tom I'll see if I can get this formatted and find a few more examples. \$\endgroup\$
    – Tamschi
    Aug 5, 2011 at 17:13

You must log in to answer this question.

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