hikari – Designing a Terrain System

The next big addition to hikari is going to be a system for rendering terrain. I’ve done a few weeks of research and wanted to write up my plans before¬†implementing. Then, once it’s complete, I can review what did and did not work.

That’s the idea, anyway.

Source Format:

I decided to use simple heightmap-based terrain. Starting with a regular grid of points, offset each vertically based on a grayscale value stored in an image. This is not the only (or best) choice, but it is the simplest to implement as a programmer with no art team at hand. Other options include marching-cubes voxels, constructive solid geometry, and hand-authored meshes.

However, I’m consciously trying to avoid depending on the specific source of the mesh in the rest of the pipeline. This would allow any of (or even a mix of) these sources to work interchangeably. We’ll see how realistic that expectation is in practice.

Chunking:

Terrain meshes can be quite large, especially in the case of an open-world game where the map may cover tens of kilometers in any direction, while still maintaining detail up close. Working with such a large mesh is unwieldy, so let’s not.

Instead, we cut the terrain up into chunks. For example, if our world map is 4km x 4km, we could cut it up into 1600 separate 100m x 100m chunks. Now we don’t need to keep the entire map in memory, only the chunks that we might need to render in the near future (e.g, chunks around the camera.)

There are additional benefits to chunking the map; for example, the ability to frustum cull the chunks. Chunks provide a convenient granularity for applying level-of-detail optimizations as well.

Materials:

The mesh is only part of our terrain, of course. It needs texture and color from materials: grass, rock, snow, etc. Importantly, we don’t necessarily want to texture every part of the terrain with the same material. One solution would be to assign a single material to each chunk, and have an artist paint a unique texture.

This seems to be a non-starter to me — potentially thousands of textures (of high resolution) would need to be created and stored, not to mention streamed into and out of memory alongside their mesh chunks. In addition, producing a distortion-free UV-mapping for terrain is difficult. Finally, while we don’t want to texture everything the same, there are only a limited set of materials we want to use, and it’d be nice if we could reuse the same textures.

Enter splat maps. The basic idea is straightforward: assign a color to the terrain. The components of that color determine the blend weights of a set of materials. If the red channel weights a rock texture and the green channel weights a grass texture, ‘yellow’ terrain is a blend between rock and grass. This allows us to smoothly blend between 5 different materials.

Wait, 5? How?

A color has four components, red, green, blue, and alpha. However, if we assume the material weights must add to equal 1.0, we can construct a new weight that is (1.0 – (r + g + b + a)). This becomes the weight of our 5th material. (Of course, we need to actually enforce these constraints in art production, but that is a separate issue.)

Furthermore, since chunks of the terrain get rendered in their own draw call, there’s no reason we can’t swap the materials used in each chunk. So while the number of materials in a specific chunk is limited, the total number of materials is unlimited (well, close enough).

The name “splat map” may imply using a texture to assign this color (and, for a heightmap terrain, that’s the easiest way to store it on disk), but I actually want to use vertex colors. This puts heightmaps and authored meshes on the same footing, and keeps decisions about mesh source in the mesh loading where it belongs.

In order to do texturing, we need texture coordinates. The obvious way to do this is assign a UV grid to our heightmap mesh. This will look fine for smooth, subtle terrain features, but the more drastic the slope the more distorted the texturing will be.

Instead, we can use so-called triplanar mapping to generate texture coordinates. Project the world position to each of the XY, YZ, and ZX planes, and use that value as the texture coordinate for three different lookups. Then, blend between them based on the vertex normal.

As an added bonus, there’s no requirement that the various axes in triplanar mapping use the same material. By mixing materials, we can create effects such as smooth grass that fades to patches of dirt on slopes.

Of course, there is a cost to all of this. Triplanar mapping requires doing 3x the material samples. Splat mapping requires doing up to 5x the samples. Together, it’s up to 15x the material samples, and we haven’t even begun to talk about the number of individual textures in each material. Needless to say, rendering terrain in this fashion is going to read a *lot* of texture samples per-pixel.

That said, hikari already uses a depth prepass to avoid wasted shading on opaque geometry, so I suspect that would mitigate the worst of the cost. In addition, it’s easy enough to write another shader for more distant chunks that only uses the 2-3 highest weights out of the splat where that’s likely to be an unnoticeable difference.

Plumbing:

There are a bunch of assumptions that hikari makes regarding meshes and materials that are a bit at odds with what I’ve mentioned above. The renderer is simple enough that I can work around these assumptions for special cases. However, I will need to be on the look out for opportunities to make some of the rendering systems (or, at least, the exposed API) more general.

Some examples: at the moment, meshes are assumed to use a specific common vertex format (position, UV, normal, tangent) — terrain meshes will not (no need for UV and tangent, but we need the splat color.) Meshes are expected to use only one material, and materials do not pack any texture maps together (so, for example, baked AO and roughness are separate maps). Neither of these will play nicely with terrain, but should be simple enough to fix. “Materials” are currently just a bag of textures and a handful of uniform parameters, since at the moment there are only two mesh shaders in the engine. A more generic material model that ties directly into its associated shader would be a useful thing to fix.

So, there’s the plan of attack. We’ll see how well it stacks up. I’ll be documenting the implementation of each part of the system in a series of blog posts, capped off by a final report on what worked and where I got it totally wrong.

Advertisements

Z-Ordering for Isometric Tile Maps

For a 2D, top-down view, the natural ordering of a tile map is a linear array, organized as a 2D matrix. The coordinates of any given tile can be calculated by `y * width + x` (row-major) or `x * height + y` (column-major). Conversely, you can calculate the x and y from the index of a given tile. [1] This is not the only way to represent such a map — for example, if you have an extremely large map it may be worthwhile to ‘swizzle’ the array, storing blocks of tiles sequentially rather than entire rows. [2]

The advantage of the top-down view is that order of rendering is less important. Tiles do not overlap, so the order they are rendered to the screen does not affect the final image. Therefore, rearranging the tile array has no visible effect on rendering. The matrix view of the map is easy to reason about, so this is convenient.

An isometric view, on the other hand, is a different matter.
Continue reading

FTJ2014 Post-mortem Part II – Animation

Unlike rendering, I went into this jam with no clue how to do animation. Fortunately, it turns out to be fairly simple (in part thanks to my per-entity rendering setup.)

First, a brief bit of background, for anyone unfamiliar with rendering:

Each vertex drawn has three properties: position, color, and texture coordinates. The rest of the pixels draw are determined by linear interpolation between connected vertices. Which vertices are connected depends on the primitive type defined when we send the vertex buffer to the GPU. In Majo, everything is rendered as Quads (4 consecutive vertices create a single face.) Finally, by convention, the elements of the position vector are referred to by the familiar (x, y, z), but texture coordinates are labeled (u, v, w).

So, the following code renders a 16×16 square starting at the origin (top-left of screen), textured with a 32×32 block of the current texture, starting at the top-left of the texture image:

void Foo::render(sf::Vertex * quad) const
{
    quad[0].position = sf::Vector2f(0, 0);
    quad[1].position = sf::Vector2f(16, 0);
    quad[2].position = sf::Vector2f(16, 16);
    quad[3].position = sf::Vector2f(0, 16);

    quad[0].texCoords = sf::Vector2f(0, 0);
    quad[1].texCoords = sf::Vector2f(32, 0);
    quad[2].texCoords = sf::Vector2f(32, 32);
    quad[3].texCoords = sf::Vector2f(0, 32);
}

(There’s no requirement for texture size and actual rendered size to be related, but direct multiples prevent squashing and stretching.)

What this means is we can place multiple sprites on a single texture image (a spritesheet), and slice out the portion we want to render. Which means that *animating* these sprites is just a matter of changing which slice of the spritesheet we render.

A single frame of animation, then, is simply a rectangle indicating what part of the spritesheet to render:

struct AnimationFrame
{
    sf::Vector2f uv;  // Offset into the texture.
    sf::Vector2f spriteSize;  // Size of the sprite on the texture.
};

And an animation consists of a list of frames, with some bookkeeping regarding when to switch:

class Animation
{
private:
    /* Container for a list of animation frames. */
    std::vector<const AnimationFrame> m_frames;
    int m_currentFrame;

    int m_ticksPerFrame;
    int m_ticksSinceLastFrame;

public:
    // Constructors / Accessors elided.

    /* Start the animation. */
    void start();
    /* Update call.  Advances the animation. */
    void update();
    /* 
     * Render the texture coords to quad.
     * Does not touch position -- that is to be set by the entity.
     */
    void render(sf::Vertex * quad) const;
};

The render method allows the owning entity to pass a quad to render the appropriate uv coordinates (while still rendering position and color itself.)

We’re not done yet!

The problem is that this class is hefty: a four-frame animation weighs in at 76 bytes, plus overhead incurred by the vector class. Copying this class as a member of every Entity that uses an animation adds up to a lot of memory moving around. (The issue is less the memory usage, and more that allocating, copying, and deallocating that memory is not free.)

The obvious solution is to cache the Animation, and let each entity store a pointer to it. However, we now have a different problem: the timing information and current frame are shared between all entities using a given animation. (Since each entity calls Animation::update, this leads to undesired behavior.)

This leads to the core lesson I learned during this jam: data and state are different things. Separate them.

Our animation frames are data: we load them into memory once, and only read from them. On the other hand, the timing information is *state*, modified on each update. These are two separate concepts, so let’s carve out the stateful bits into their own structure:

struct AnimationState
{
    int frameCount;
    int currentFrame;
    int ticksPerFrame;
    int ticksSinceLast;

    // Methods elided
};

With a bit of trivial setup, each animated Entity now owns an AnimationState, as well as a pointer to an Animation (20 + 4 bytes per Entity on x86). Now we can cache and share Animations all we want, as they are constant data. Animation::render has its signature changed to accept an AnimationState passed in: void render(sf::Vertex * quad, const AnimationState& state) const;

Over 1000 entities, this system saves ~54.6kB of memory. That’s not a lot. However, by enabling caching of Animations, we reduce the amount of initialization code involved, as well as the number of runtime copies/moves neccessary. Decreased memory usage is just a nice bonus.

Next time: design, scope, and some miscellaneous issues encountered over the week.