5 Comments

Terrain engine

In this post I’ll talk about how I render terrain in the game prototype I’ve been working on.

Representation

The terrain is represented by a height map. At compile time normals are also calculated for each vertex (which corresponds to a pixel on the height map). This is done by finding the face normal of each triangle and “adding it” to the of the vertex. The value for each vertex is then normalized. The result is that associated with each vertex we have the average of the face normals of the (up to 6) triangles of which that vertex is part.

Seen from the side, it might look something like this:

Normal calculation

At runtime this is processed into a grid of triangles with texture coordinates that increase across the world. Due to my desire to have a generally overhead view, I don’t need any kind of LOD algorithm for efficiently drawing distant terrain. Currently the engine manages pieces of the world in 32×32 chunks (thus 32 x 32 x 2 triangles, and 33 x 33 vertices).

The basic result might be something like this:

Basic terrain

and shown in wire-frame mode:

Basic terrain wire-frame

The XNA/DirectX vertex structure for this is pretty simple:

    struct VertexTerrain : IVertexType
    {
        public Vector3 Position;
        public Vector2 TexCoord;
        public Vector3 Normal;
    }

Texturing

The previous section showed basic texture mapping and normal mapping with a directional light source. The problem is that we want a variety of terrain. We could have a small number of different textures and have the pixel shader blend between them based on some terrain tile index. This limits us though – we need to have a separate texture slot for each terrain type (I think there are a maximum of 16, and we need 2 each – texture and normal map). More importantly this increases the texture fetch cost. 16 texture fetches in a pixel shader is slow.

A texture atlas is the obvious way to address this issue. We could use a terrain tile index to know which section of the atlas from which to sample. Unfortunately, texture atlases come with problems of their own.

The first issue is that our terrain textures need to wrap. With a texture atlas there will be “bleeding” from adjacent sub-textures when we sample from near the edge. With DirectX 10/11 (or native access to the XBox 360) we could use texture arrays to solve this issue instead of texture atlases. However, with XNA (DirectX 9) we are out of luck.

This is commonly solved by include wrapping “gutters” around each sub-texture. For instance, if we were to include a 2 pixel gutter, a single line of our texture might look like:

IJABCDEFGHIJAB

We need to adjust our texture coordinates to sample from a slightly smaller region, but we no longer need to worry about a sample bleeding from adjacent sub-textures.

This isn’t the only issue though. A slightly less obvious problem is explained by the article Large-Scale Terrain Rendering for Outdoor Games in GPU Pro2 and arises from the fact that we need to implement texture wrapping manually in the shader. We rely on mipmapping for rendering efficiency and artifact-reduction when the texture rendered is less than full-size on screen. The problem lies in how the GPU determines which miplevel(s) from which to sample. It does so by using the first derivatives of the screen-space texture coordinates in any given 2 x 2 pixel block. Adjacent pixels which sample from spots that are more spaced apart in the texture will sample from smaller miplevels.

The standard situation:

Sampling adjacent pixels

And the problem when one of the sample points has wrapped:

Sampling adjacent pixels

The sample points will be far apart, and the GPU has no idea that we’ve implemented a texture atlas. It will thus sample from a much lower miplevel than it should since it thinks the texture is being viewed from far away. An example of the type of artifact you would see is:

Texture wrapping artifact

The author of the above-mentioned article proposes three possible solutions. The solution I have currently chosen to go with is manual calculation of the miplevel in the shader. This looks like the following:

float GetMipLevel(float2 iUV, float2 iTextureSize)
{
	float2 dx = ddx(iUV * iTextureSize.x);
	float2 dy = ddy(iUV * iTextureSize.y);
	float d = max(dot(dx, dx), dot(dy,dy));
	return 0.5 * log2(d);
}

This is the slowest option proposed due to the additional calculations and the tex2DLod instructions that are required (instead of tex2D).

The fastest is simply to limit the number of miplevels in the actual texture. This results in artifacts which may or may not be acceptable (for my purposes I think this would be fine). Unfortunately this is not an option for me since in XNA there is no way to limit the number of miplevels in a texture. Either only one miplevel is generated, or all of them are generated. I haven’t yet tested the third option, which is to encode the miplevel in a separate texture which is the same size as the atlas. I have my doubts that this would be faster than manual miplevel calculation due to the additional texture fetch (but you never know until you try).

The texture atlas

As an optimization, my texture atlas is only 1 sub-texture tall. Unfortunately the maximum single texture dimension allowed in the XNA HiDef profile is 4096. I currently use 512 x 512 sub-textures, which limits me to 8 terrain types. I want at least 16, so I will either have to forgo that optimization or drop my texture sizes down to 256×256 (I really doubt this is detailed enough though).

Sample texture atlas with 5 sub-textures:

Texture Atlas

There is an additional problem with the construction of the texture atlas. We need at least a 1 pixel gutter (where the repeating of the opposite side of the texture is used) at all miplevels to prevent bleeding into adjacent sub-textures. Extrapolating up from the smallest miplevel, what this ends up meaning is that at the maximum size (512 x 512) I need a full 256 pixels of gutter (128 on each side of a 256 x 256 texture). That means I’ve lost half my resolution! Or that I need to double my memory requirements.

To address this, I declare a maximum number of “accurate” miplevels. For instance, I currently use a value of 5. This means that I will have accurate images at sizes 512, 256, 128, 64 and 32 (remember, since I currently manually calculate the miplevel in the shader, I can limit it). So at size 32 I need a one pixel gutter. This means we’ll actually have a 30 x 32 texture with 1 pixel gutters on each side. Extrapolating back up to 512, we have a 480 x 512 texure with 16 pixel gutters on each side. Whew, I can still use most of my resolution!

This of course requires some extra complexity in both the atlas generation (which runs at compile time) and in the shader. In the shader it looks something like this:

struct TextureAtlasInfo
{
	float TileCount;		// How many tiles in the atlas (e.g. 5)
	float TilePixelSize; 		// Pixel width of each tile (typically 512)
	float GutterPercent;		// Percent of each tile that is the gutter (on one side)
	float MinLOD;			// Only use miplevels from 0 (max) to this level (min)
};
TileTexCoords GetTextureCoordinates_Gutter(TextureAtlasInfo atlasInfo, float MIP, float2 texCoords, float tileIndexA, float tileIndexB)
{
	TileTexCoords tileTexCoords;
	float tilePercentWidth = 1 / atlasInfo.TileCount;
	float atlasTileWidth = (1.0f - 2 * atlasInfo.GutterPercent) * tilePercentWidth; // The width of this tile in the atlas.
	float gutterSize = atlasInfo.GutterPercent * tilePercentWidth;

	float2 texCoord = texCoords;
	texCoord.x %= 1;
	texCoord.x *= atlasTileWidth;

	tileTexCoords.UVA = texCoord;
	tileTexCoords.UVA.x += tilePercentWidth * (tileIndexA + gutterSize);
	tileTexCoords.UVB = texCoord;
	tileTexCoords.UVB.x += tilePercentWidth * (tileIndexB + gutterSize);

	return tileTexCoords;
}

And now it’s time for a picture:

Multiple textures

I use another texture to store the tile indices. This only takes up one component, so I can use the other 3 to express an RGB value for a tint. This can help provide additional variety and break up repeating patterns a bit more.

Multi texture and tint

Tile indices

And now a word about tile indices. The technique used in Large-Scale Terrain Rendering for Outdoor Games relies on tile index interpolation. Though this isn’t clearly explained in the article, it means that there is a distinct ordering with regards to what tiles can appear next to each other. If you have tile index 0 next to tile index 4, you won’t just get a blend between those two terrain types. You’ll get a transition from 0 to 1 to 2 to 3 to 4. A picture better explains it. A red arrow points to where there is a transition through all terrain types from one grid unit in the world to the next.

Tile index blending

Tile index blending

This is an unusual kind of limitation, but in practice this hasn’t proven much of an issue. It will likely become more so once I expand the number of terrain types, but it could be argued that terrain types tend to be adjacent to a small set of other terrain types (so there is a natural progression).

I tried various ways to implement direct blending from “non-adjacent” tile indices in the pixel shader, but I don’t think it’s possible given any interpolated values between vertices. Each vertex would instead need to contain tile index information about all adjacent vertices, which isn’t realistic if we want to keep vertex size down and shader code as simple as possible. If you can think of a possible solution let me know!

Steep terrain

The default texture coordinates we use work great on flat or gently sloping terrain. Once the terrain gets steep though, we see that things look stretched:

Stretched texture coordinates

We could try at compile time to generate more “spread out” texture coordinates on hillsides, but this is difficult or impossible to do without creating seams somewhere else.

In addition, besides looking amateurish, grass doesn’t generally grow on vertical terrain.

So one solution that addresses both of these is using triplanar texturing. Associated with each vertex we will have 3 different sets of texture coordinates. One for use on each of 3 planes. Our vertex structure now looks like this:

struct VertexTerrain : IVertexType
{
    public Vector3 Position;
    public Vector2 TexCoordY;
    public Vector2 TexCoordX;
    public Vector2 TexCoordZ;
    public Vector3 Normal;
}

To avoid jarring transitions, we blend between textures sampled with these different coordinates depending on the normal of the vertex. For vertical terrain we use a different texture atlas that consists of cliff terrain.

The extra calculations and texture samples of course add a large additional cost to the shader. But the result is worth it:

Different textures for vertical terrain

This also makes it easy to paint flat and steep terrain separately, which is convenient. To avoid tripling the number of texture samples in the shader, it might be possible to predetermine which triangles are steep terrain vs flat terrain. Since most triangles will be one or the other, we could then have a separate draw call that targets just flat terrain for instance, thus saving texture fetches in the shader. I have not tried this yet. Or perhaps dynamic branching in the shader can help offset the cost.

Additional optimizations

One problem which becomes noticeable on some hillsides is the presence of a grid-like “noise”. It is easy to see when the lighting is just right:

Ugly grid pattern

This results from the way the terrain is triangulated and how the normals are interpolated from vertex to vertex. One way to get rid of this undesirable pattern is just to increase the resolution of the height map (or perhaps increase the number of vertices we generate from the height map). This comes at a performance and/or memory cost though.

There is a better solution. Given two quads with the same vertices, interpolated values for these vertices come out quite differently depending how you triangulate them:

It turns out we’ll get much better-looking terrain if we instead triangulate the quad so that the split is between the two vertices with the least height difference between them. The original triangulation and the alternate triangulation are shown below:

Original triangulation

And the resulting terrain with simply choosing this different triangulation:

Much better!

About these ads

5 comments on “Terrain engine

  1. [...] post will go over more details about the construction of the texture atlas mentioned in this post, for which I am using an XNA content pipeline extension. There are some subtleties that bear [...]

  2. [...] use projected textures for my terrain (as seen here), and a talk during Pax Dev made me realize that it should be fairly straightforward to use it for [...]

  3. Hey nice article …..I have a similar representation for terrain …..what u can use for tile indicies is a RGBA4444 with red and blue channels storing 2 seperate indicies and blue and alpha channel for the blend weight …..but u would need a seperate texture for the tint – which u can I guess use a very good dxt1 -low frequency data

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

- Woolfe -

Developer's blog for IceFall Games

Ferrara Fabio

Game & Application Developer, 3D Animator, Composer.

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...

BadCorporateLogo

Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a young game developer.

Jonas Kyratzes

Writer, game designer, filmmaker.

Indie Gamer Chick

Indie Game Reviews Without Mercy

The Witness

Developer's blog for IceFall Games

Developer's blog for IceFall Games

Developer's blog for IceFall Games

game producer blog

Developer's blog for IceFall Games

A Random Walk Through Geek-Space

Brain dumps and other ramblings

The ryg blog

When I grow up I'll be an inventor.

Developer's blog for IceFall Games

T-machine.org

Developer's blog for IceFall Games

Ocean Quigley's Projects:

Developer's blog for IceFall Games

Wolfire Games Blog

Developer's blog for IceFall Games

The Witness

Developer's blog for IceFall Games

Follow

Get every new post delivered to your Inbox.

Join 283 other followers

%d bloggers like this: