NEP Dev Update #10: A programmer trying to art - Part 2

The exciting conclusion!

When we last left our hero, we had a usable render of a normal map for our sprite, the RIG. The trouble was, the Horde engine (the engine I'm making to run Non-Essential Personnel), didn't actually support rendering with normal maps.

Luckily, adding normal maps to a rendering engine is actually pretty easy.

The basic recipe is:

1. bundle the normal data into your material texture format.
2. update fragment shaders to decode normals from the material directly, instead of calculating them indirectly from a bump map.

Part 2 is pretty boring, so I won't say anything about that. There's a little something interesting going on in part 1 though, so I'll say a bit about that.

General normal vectors normally have three pieces of information, namely the x, y, and z components of the vector. Normally this would eat up three color channels in a texture, so that's probably why lots of games/engines just use separate textures for normal maps.

But we can do better!

For sprite rendering, we're actually only interested in surface normals, which are slightly restricted compared to general normals. Surface normals must always point "outside" of the surface, so that rules out half of the possible orientations for each normal. We'll assume the surface is locally flat too. That assumption holds pretty well for triangles. Specifically for sprites, the surface is always pointing towards the camera (say along the +z axis), so that's even more restricted since the surface orientation is fixed. All of these restrictions mean we only have to care about normals with positive z components. Therefore we can "compress" the surface normals for sprites into just two channels by completely ignoring the z component of the normal.

Don't worry though. We can always get the z component back with a tiny bit of math. We just project the x,y components of the normal onto the +z side of the unit sphere, like so:

z = sqrt(1 - x² - y²)

Horde uses 32 bit PNG images for material textures, so that leaves 2 other channels for the other material properties, like shininess, translucency, and reflectivity. As long as we're ok with having 16 unique values (instead of the usual 256) for less-used properties like reflectivity, then we can use bit packing tricks to encode multiple properties to a single color channel. This keeps our material properties down to one texture and keeps sprite loading pretty quick during the game.

But what does it look like?

Last time, our bump mapped sprite came out looking just a little bit awful.

Now that the Horde engine supports rendering with normal maps, we can finally see if all our hard work pays off.

The RIG actually looks like a 3D thing now even though it's actually just a pair of triangles on the GPU. This is the magic of normal maps. =)

There's still a little left to be desired though. The edges on those curved bits look might blocky. Or Aliased. We could do with some anti-aliasing to smooth them out.

Classic techniques for anti-aliasing involve subsampling objects at greater-than-pixel density, and then aggregating back down to pixel resolution. Well, we have a full 3D model of the RIG now, and we don't have to create sprite textures in real-time, so we can subsample all we want. Let's start with a 4x sample, and then scale the normal map and color texture back down to 1x resolution using our favorite free 2D image tool, the GIMP.

Those white outlines happened because when we scaled the normal map, we did something bad. Downscaling images generally involves averaging pixels together. In the case of a normal map, the pixels represent unit vectors, so we're really averaging normal vectors together. Two bad things are happening here.

1. We're averaging neighboring unit vectors together. In general, this breaks the unit-ness of the normal. That's easy to fix in the shader by re-normalizing, so no big deal there.

2. Sometimes neighboring normals shouldn't be averaged at all. This is the bigger problem and the cause of our white outlines. On the RIG's pixels, we have all our lovely normals. Just hanging out. On the pixels not on the RIG though, those pixels still have colors, but who knows what normals those colors encode. There's no geometry at those pixels, so those normals are undefined. We definitely don't want to average undefined normals into our RIG normals just because they happen to be neighbors.

The solution for #2 isn't quite as simple as tweaking the fragment shader. We really need to stop using GIMP to scale our normal maps since it doesn't know how to handle normals correctly. For the Horde engine, I wrote a custom image scaler to handle this special case. It does all the usual stuff an image scaler would do, but I also taught it to use a mask. To scale the normal map correctly, we can encode the RIG vs non-RIG pixels into a mask. Say... the alpha channel. Then we just tell our custom scaler to read the alpha channel and ask, "should I average this pixel?" If the answer is yes, we average that pixel like normal. If no, then we just completely ignore that pixel.

The result is nice-looking anti-aliasing, but without the visual artifacts.

But wait. There's more!

Since we went to all the trouble of making a fully-3D asset workflow, we might as well make good use of it. Having a tool like Blender at our command means we can use all kinds of awesome buttons that someone must have spent lots of time on so we don't have to. =P

Like ambient occlusion.

Wow, it's really is just one button.

Ambient occlusion is basically just making concavities ("in" corners) a little bit darker than the flat bits, but the end result usually looks pretty good even in different lighting conditions. And we don't even have to change the Horde renderer to support AO. We can just bake the AO map right into the color texture without making any changes anywhere else. We can even do anti-aliasing easily by 4x sampling the 3D model and downscaling like we did for the color texture.

The content will flow!

Now that I finally have a workflow for making sprites that look a little better than completely awful, I can start adding more content to the game. Here's a shot of the console that sits next to the RIG.

And just for fun, I added a cheap facimile of a day/night cycle to Horde's sprite tool to better show the dynamic lighting.

Next Time

Next I'll work on adding support to the game for big complicated sprites that you want to stick around after you unload/reload the world. Persistence in inifinite-world games is kind of tricky because you generally don't want to keep the entire world state in memory at once, but you still need quick access to parts of it.

Some voxel games piggy-back their world-object persistence onto the world chunk system. In other words, a world object gets saved with the group of voxels it's sitting on. There are a lot of downsides to that approach though. Like, which chunk should a sprite be assigned to at any given moment? What if the sprite is sitting on multiple chunks? Chunk membership gets really annoying to keep track of too, especially if sprites can freely migrate between chunks.

Since there's no clear map between world objects and chunks, I'm going to use a completely different mechanism to persist our world objects. This is where fancy data structures (if you can call 30-year old data structures fancy) can help out. The magic of R-Trees will let us track millions of world objects, save/read/search them efficiently, and even save them to permanent (ie, slow) storage meda like a hard drive or an SSD.

Sadly, all the good implementations of R-Trees seem to be in C/C++, but the Horde engine is written in Java (you're welcome, Modders). I'll be damned if I'm going to waste time writing my own R-Tree implementation though, so I'll just cobble together what I need from a couple different Java implementations.

It'll work. I think. =)