For a little while I've wondered how you would go about writing a game with vector graphics trying to get the kind of smooth look you see in flash games and the like, in C++. It's been a little while since I posted here so I thought I would share my progress; I've really just been trying to crack anti-aliased lines but I found the de-facto algorithm, Xiaolin Wu's, wasn't really good enough for my purposes, so I'm going to post what I've come up with to see what people make of it and if anyone wants to suggest improvements that would be very welcome!
Apologies to people who are familiar with all this (skip to the end for code) but to explain where I have gone I kinda need to cover where I've come from. Starting with Bresenham's line algorithm (all this stuff is on Wikipedia) you can get non-anti-aliased lines very quickly. If you want, for instance, to draw a diagonal line it works in the following manner; it draws a flat horizontal (or vertical depending how steep the line you want is) line but for each pixel it draws it increments an error counter which it uses to keep track of how far the line it's drawing has deviated from the ideal one. Each time that error exceeds a threshold value it moves to the next row (or column) of pixels so it ends up drawing a line which follows the ideal one in steps.
Its great but obviously is not anti-aliased. Xiaolin Wu's algorithm is very similar but for each pixel Bresenham's algorithm would draw, it draws two and uses that error term to make each of them semi-transparent to a different degree. If the error term is half way to its threshold it knows the ideal point you want to draw is exactly between two pixels so it fills both of them but at half opacity.
So you end up getting anti-aliased lines from something that's still really quite fast. However, like I said it's not good enough for getting that kind of flash effect as it doesn't smooth motion; most implementations of it don't account for a the fractional part of a line's starting and ending positions. As a result a line drawn from (0, 0) to (50, 50) appears the same as one drawn from (0.5, 0.5) to (50.5, 50.5) so, whilst the individual lines appear smooth, they also jump from pixel to pixel as moved.
The algorithm can be tweaked relatively easily to combat this; using the fractional part of the starting point to calculate and initial value for that error term. However this only smoothes motion in one direction because the algorithm only splits each point you want to draw between two pixels. For example if you use this algorithm to draw a vertical line and slowly shift it upwards it will appear to move smoothly. However shift it to the side and it will still jump from point to point. Vertical and horizontal lines are normally treated as special cases so that particular example can be fixed but the same problem exists for other lines to.
The solution I've come up with is to basically draw four lines. If we are drawing a line that starts at (a, b) I first draw a line, using Xiaolin Wu's algorithm, from ((int)a, (int)b) and use the fractional part to offset the transparency of the whole thing. I then do a similar thing for ((int)(a+1), (int)b), ((int)a, (int)(b+1)) and ((int)(a+1), (int)(b+1)). At least in principle; in practice it's better not to actually draw them separately.
The result is a pretty pleasing line that animates smoothly in any direction. I've not actually compared the time it takes to Xiaolin Wu's algorithm; that's my next task but it involves very little in the way of extra calculations so I expect that the majority of the time difference will come from the extra draw calls.
Below is an example a line produced by this and the code can be found here;
http://mattiasgustavsson.com/asking/code/AntiAliasDrawer.zip
The important function is the public DrawSmoothLine (DrawSimpleSmoothLine uses Xiaolin Wu' algorithm and DrawLine uses Bresenham's) ... It uses Mattias' Pixie engine but it should be easy enough to use with anything else as it only uses the engine for the draw calls and a few STL replacement functions. I'm fine with anyone using it, if they think it's good enough, though accreditation and/or notification would be nice.
