Byte Wrangler is 1 year old!

I started this programming blog a year ago and its time to look back at what I've accomplished over the last year, and see if I'm on track.

The first thing to note is that there isn't anything available for download. In my second post on this blog I suggested I wanted to have something available for download at the end of 2011. That was my plan throughout the year and it seemed achievable until about August when I re-assessed where I was up to and realised I was well short of where I needed to be.  Rather than lament the slippage of the deadline it's worthwhile looking at what went wrong and learning from the experience.

As far as I can tell I made 3 main mistakes, which I'll discuss in more detail below:

Mistake 1: Underestimating how long it would take to get certain parts of the system working.

This is the big one, and probably caused nearly 6 months of slippage.  Since I decided I would use SlimDX and develop everything from scratch and not use an existing games engine, I started with nothing. I accepted this, but overlooked the fact that meant I had no user interface system to work with at all. That means no buttons, no textboxes, no labels, no scrollbars etc. Even designing a simple settings screen requires many different interface controls, and if you want to implement something more complex like an inventory screen with drag and drop etc, you're talking quite a bit of coding to develop the whole lot.

And just when I thought I'd implemented every control I'd need, I would think of another major one I'd forgotten. As if developing the user input side wassn't enough, I also needed a skinning/texturing system that allowed the controls to size dynamically as required and not have visual artifacts or ugly stretching when resizing.

On the plus side, over the past year I've implemented a windowing system and the following interface controls:

• Window
• Button
• Checkbox
• Context Menu 
• Label
• Image
• Message Box
• Progress Bar
• Scroll Bar
• Text Box
• Tool Tip

There are a few additional controls on the wishlist, but they won't be needed until later and shouldn't take as long as getting this framework up and running.

Mistake 2: Overestimating how much free time I had over the entire year.

This one is hard to judge, as 2011 turned out to be fairly tumultous from a family standpoint, and since I'm developing this game in my spare time, work, family and sleep pretty much come first, and Bulldog lost out more times than I would have liked. Not much can be done about this moving forward as life is unpredictable, but I should adjust my estimates in the future to assume I have less free time.

Mistake 3: Spending too much time researching and developing unnecessary features.

This one was avoidable, and was caused by becoming sick of coding "boring" features and wanting to implement some cool stuff. Like for example, I spent a good 6 weeks developing the signed distance field font system, when I had an ok (albeit ugly) font system already in place. The end result is about 10x better in terms of flexibility and visual look, but that time might have been better spent working on essential features. At the same time though, the distance field stuff was a lot of fun to work on, and was very rewarding at the end of the day.

It's hard to stay focussed on the boring stuff, when there's so much unnecessary fun stuff. But since the fun stuff keeps you motivated, you have to deviate from the schedule sometimes.

Where to from here?

So I guess the question is, how much has actually been done, and what's the current plan / deadline? Since that will be a reasonably large post in itself, I'll leave that to my next post. Stay tuned.

Signed Distance Fields

I was first exposed to Signed Distance Fields through this white paper written by Chris Green from Valve Software. Valve often make technical documentation on their graphics technology available, which is awesome.  In this case, the technique was used in Team Fortress 2, specifically for some of the signs and decals in the game.

Signed Distance Fields are a different way of storing (typically monochrome) bitmap data.  Instead of each pixel in the bitmap representing the intensity at that point, it represents the distance to the nearest non black pixel in the source image. Pixels outside of the shape have positive distance values, while pixels inside the shape have negative distance values, hence the "signed" part of the name.

Figure 1. An example of how a signed distance field looks at the pixel level.

Note that in reality the distance field is made up of floating point data, but for illustrative purposes I've shown them as integers.

To create a signed distance field you apply a distance transform to a source image. Then, to render the original image you do the following:

For each distance value in the field,
    is the value <= 0?
    if yes, draw the pixel
    if no, ignore it.

The thing that makes signed distance fields really useful is what happens if you need to resize the image. The distance values are interpolated by the 3D hardware in the same way as intensity values in a traditional bitmap, but because the edge comes from a test, it remains crisp. This means you can magnify the bitmap many times and not suffer the blurry or chunky edges that traditional bitmaps exhibit due to filtering artifacts.

Creating the Distance Field

There are many different transforms you can use to calculate the distance field.  It turns out that the best approach is to use a high resolution source image and then downsample the result to an acceptable size for your application, as the nature of the distance field preserves a lot of the information.

The brute force method (by which I mean calculating the euclidean distance between a given pixel and every other pixel in the bitmap) will generate a perfect distance field but is particularly slow for large bitmaps as it has O(n^2) complexity. There are faster (albeit less accurate) algorithms out there though the selection of algorithm isn't too important, as it doesn't need to be done at runtime. Valve actually used the brute force solution and ran the processing as a batch job overnight on their servers. I chose a faster approach simply because I was eager to get some results.

Figure 2. An example of what the final distance field looks like in Bulldog.

An application of Distance Fields

Since the source data for Distance Fields is generally monochromatic, their usefulness is limited, however one application that is particularly well suited to distance fields is drawing text.

For example, a TrueType or OpenType font (or "typeface" to use the correct term) is stored in a vector format. This means each of the glyphs (characters in the typeface) are represented as shapes with x,y coordinates for their corners and control points. This is converted into a bitmap or "rasterised" for display on the screen. Depending on the size of the text you want, the x,y coordinates are scaled and the curves that represent the shape of the letter are scaled too. The rasterisation process can be a little slow even on modern hardware, so in games the preferred technique is to pre-rasterise the font at the size you want, store it as a bitmap and then construct the text required by picking individual letters from the bitmap.

This technique is very fast, but has some limitations. You need to create a seperate font bitmap for every size and style combination you want to use in your game since bitmaps don't scale well. Take for example a game that wants to have 2 different typefaces, say a normal looking sans serif typeface like Arial, and maybe a fancier caligraphy typeface for ye olde books and scrolls and the like. You may want to support 3 different sizes for stylistic reasons, such as titles/captions or tooltips. Or perhaps you want to support a wide range of screen resolutions and don't want people to require a microscope to read your UI elements. Already we have 2 * 3 = 6 different bitmaps you need to create and manage in the game. It gets even worse if you want to support italics or bold styles as well.

The signed distance field approach helps alleviate this burden by taking the sizing out of the equation since the distance field can be scaled up and down with less graphical artifacts.

As an added bonus distance field data can be used to anti-alias the edges. This can be achieved by adding an additional term to the distance test to smoothly ramp from lit to unlit for distance values within a certain range. The Valve paper covers a few other effects, such as drop shadows and outlines.

In Bulldog, I implemented signed distance field fonts using a pixel shader, which makes juggling the distance field data considerably easier.

The shader code is surprisingly simple, and for simple anti-aliased text is as follows:

float4 ps( VS_OUTPUT IN) : COLOR
{
    // get the alpha value from the distance field texture
    float rawAlpha = tex2D( TextureSampler, IN.TilingCoords).a;


    clip (rawAlpha - (0.5f-delta));

    return float4(fillColour, smoothstep(0.5f-delta,0.5f+delta,rawAlpha) );
}

delta is a constant which determines how far from the edge of the letter the anti-aliasing extends. The actual shader code I use in bulldog is slightly more complex as it handles borders and reversed characters (such as when selecting text in a textbox), as well as adjusting the anti-aliasing for different font sizes. I'll write up a more detailed post on the new font system I built using signed distance fields at some point. In the mean-time, here's an example of the same font rendered at several different sizes:

Figure 3. An example of the font output at 12, 24 and 64 pixels high.

As a last note, I should mention I've also used signed distance fields in an unusual way in a different part of Bulldog, but that's a post for another time...

Math.Pow(x,2) vs x * x

I've recently commented on posts on gamedev.net where the author posted some code they were concerned about the speed of. In each example I noted they were using the Math.Pow() function to calculate the square of a number.

In each circumstance I recommended they alter their code to multiply the two values together. This was mostly based on the "gut feel" that Math.Pow() should be slower. That's fairly poor practise, and because I loathe giving people a bum steer, I decided I should do a quick benchmark on my CPU.

100 million iterations in a tight loop. (x is a double):

Math.Pow(x,2)	8.540 seconds
x * x	1.152 seconds

Similarly, as an aside, Math.Sqrt(x) is significantly faster than Math.Pow(x,0.5):

Math.Pow(x,0.5)	8.543 seconds
Math.Sqrt(x)	1.737 seconds

The results are pretty clear. Stay away from Math.Pow(x,2) and Math.Pow(x,0.5). I did some further benchmarking on higher integer powers, and Math.Pow() stays the same, while x * x * x ... gets slower as you'd expect. The breakeven point is somewhere around x ^ 20 I think. So it's still better to do the direct multiplication for x ^ 3 and x ^ 4.

I was actually surprised by the performance of Math.Sqrt(x), I thought it would be alot slower than it turned out to be. The important lesson here is to always benchmark.

Quick Update

I haven't posted anything in a while, but progress on Bulldog continues (albeit slowly). My day job has been pretty intense over the last month in terms of workload, so I've not had much time of late to actually code anything significant. I've been focussing on higher level concepts like fleshing out the way character creation will integrate with the initial origin scenario, which at this stage I think is coming together nicely.