As a longstanding user of SDL2_gfx I have become aware of some omissions and inconsistencies in the library. For example whilst you can draw a ‘thick’ straight line there are no functions for drawing thick circles or ellipses, and whilst you can draw an antialiased outline circle, there are no functions for drawing an antialiased filled circle.
So I have attempted to address this issue by writing my own extensions to the library. I have added the following functions to my copy:
thickEllipseColor() / thickEllipseRGBA(): Draw a 'thick' outline ellipse
thickArcColor() / thickArcRGBA(): Draw a 'thick' circular arc
thickCircleColor() / thickCircleRGBA(): Draw a 'thick' outline circle.
aaFilledEllipseColor() / aaFilledEllipseRGBA(): Draw an antialiased filled elllipse.
aaFilledPolygonColor() / aaFilledPolygonRGBA(): Draw an antialiased filled polygon.
aaFilledPieColor() / aaFilledPieRGBA(): Draw an antialiased filled sector or segment.
aaArcColor() / aaArcRGBA(): Draw an antialiased elliptical arc.
aaBezierColor() / aaBezierRGBA(): Draw an antialiased Bézier curve.
aaFilledPolyBezierColor() / aaFilledPolyBezierRGBA(): Draw an antialiased shape bounded by a cubic polyBézier.
Unlike the antialiased drawing functions in the original library, which surprisingly take only integer coordinates, my antialiased routines all take floating point parameters for coordinates and line thickness etc.
The code for these extensions can be found here, starting from line 4402. I have tried to do a reasonable amount of testing but if you find a bug please let me know.
Here’s an an example of a graphic created using these routines:
Hi
nice pic!
But your code uses sqrt in the loop, this is not recommended (slow).
The best circle algo (like the one used in sdl_gfx) uses essentially only additions in the loop.
I use COS and SIN in loops too, quite deliberately! The days when such functions were very slow are, thankfully, past: with floating-point units being standard in modern CPUs they are not particularly slow. In any case you will find that the execution time is typically dominated by the calls to SDL_RenderDrawLine() and SDL_RenderDrawPoint() (especially with antialiasing), so there’s little benefit in trying to avoid transcendental functions.
I did some profiling, but have not compared different algorithms.
One thing to consider is that antialiased plotting has sub-pixel resolution (which is why it is strange that the aa routines in the original SDL2_gfx take integer coordinates) so using a ‘fast’ (but approximate) circle algorithm like Bresenham’s risks introducing positional errors. By using sqrt(), sin() and cos() I can guarantee sub-pixel accuracy.
I just made a small “fake” test, where I replace drawing a circle by one of the 3 cases:
a loop of 1000 iterations, each one computing one sine
same but computing one addition instead
filling an array with 1000 points (x,y) and calling SDL_RenderDrawPoints
then, for each test, I repeat 30 times (as if I was drawing 30 circles), and SDL_RenderPresent, and repeat everything 1000 times (to have a measurable time)
Here are the results:
Starting test : sinus
Time per “circle” = 0.000031
Starting test : addition
Time per “circle” = 0.000006
Starting test : points
Time per “circle” = 0.000017
My conclusion (but maybe this test is not decisive) is that the time for computing sinus is not negligible compared to the time to render points. (and, computing a sinus is roughly 5x slower than an addition)
On the other hand, you are probably right about sub-pixel resolution. It’s very recent that SDL allows you to put things at float position, so I didn’t think much about this. Concerning anti-aliased plotting with integer coordinates, there is a very nice version of
Bresenham’s that does this.
I wonder if Bresenham’s algo can be adapted to non-integer center and radius. It would be interesting to investigate.
The only places I use sin() and cos() are in calculating the line segments that are used to approximate the curve of an arc, so the number of times they are called is much less than the number of pixels plotted (also the overhead of my aaFilledPolygon() routine is significant here)
The original SDL2_gfx code also uses sin() and cos(), in exactly the same way, in its arcRGBA() function, so I am not doing anything different! In fact I would expect the percentage effect on execution time to be much greater in the orignal code than in my extensions.
True, but SDL2_gfx could always have supported sub-pixel positioning of antialiased graphics; it does not require those recent additions to SDL (and nor do my extensions). Indeed antialiased graphics are used just as much to achieve sub-pixel positioning as they are to remove ‘jaggies’ (for example when drawing horizontal or vertical lines), so providing so-called ‘aa’ routines that take integer coordinates indicates a fundamental misunderstanding, in my opinion.
@rtrussell:
The only places I use sin() and cos() are in calculating the line segments that are used to approximate the curve of an arc, so the number of times they are called is much less than the number of pixels plotted
I know, this is why I mentioned only sqrt in my first post. But if I benchmark sqrt, it’s almost the same as sinus (30e^-6 vs 32e^-6)
Starting test : sinus
Mean Time per 'circle' = 0.000032
Starting test : sqrt
Mean Time per 'circle' = 0.000030
Starting test : addition
Mean Time per 'circle' = 0.000006
Starting test : points
Mean Time per 'circle' = 0.000017
I don’t want to defend SDL2_glx author, but I think it makes some sense. Since at that time SDL was only working with integer coordinates, it makes sense to have a routine to draw a circle/ellipse with integer coordinates (so that, for instance, it fits well in a rectangle, or for rounded corners of a rectangle). Once this is accepted, it also makes sense to improve the routine to make the drawing ‘nicer’ by smoothing pixels.
Rather than simply criticise, perhaps you can suggest how I might change my code so as to make it faster, but still calculate the coordinates to an accuracy of 0.1 pixels or better with a circle diameter of hundreds of pixels.
I’m not saying that it is useless, but since antialiased graphics are fundamentally not limited to integer coordinates it is a pity to artificially impose them. My main experience of antialiased graphics is with the GDI+ subsystem of Windows (dating from 2001); it supports float coordinates for all its primitives.
Sorry for the criticism tone of my posts. In fact I am really interested in these algorithms. I know they are not obvious to write, and I would really like to know if one has to avoid using transcendental functions (as I always thought) or not, as you suggested. Of course the answer would come only by real testing, and this takes some time.
But maybe I have to understand what you mean by accuracy of 0.1 pixels. The (non-aa) Bressenham algorithm is exact in the sense that it will give you the hardware pixels that are closest to the true circle (and by reading quickly the code, I think that SDL_gfx uses this). The aa-version is also “exact” in the sense that it calculates the exact deviation from the ideal circle and computes the alpha component from this.
My impression is that you could improve your code by dealing with squares and never take the square root (which is, in essence, what the Bressenham algo does). I fully agree that using cosines and sines outside of the main loop is perfectly fine.
I think there are two issues to consider here. Firstly, in SDL2_gfx there is no direct access to the ‘bitmap’ or ‘surface’ (as an array of bytes for example); one must instead call SDL_RenderDrawLine() or SDL_RenderDrawPoint(). This significantly changes the balance between the time taken to calculate where and what to plot, and the time taken actually plotting. That’s not to say that the calculation time is irrelevant, but it is less important than when plotting consists of simply writing to memory, and it may mean that eliminating transcendental functions is of less value.
Secondly, when doing antialiased plotting both the calculation and the plotting are likely to be much slower than for regular non-antialiased plotting. The calculation is slower because it must determine not just which pixels to plot but what alpha values those pixels must have, and the plotting is slower because pixels with different alpha values must be plotted individually, raher than as a line. So again the overhead of the transcendental functions may be less significant.
It’s an arbitrary value, just to make the point that one needs to calculate the coordinates with sub-pixel accuracy. It’s hard to calculate precisely what positional resolution antialiased plotting actually achieves - it depends on factors like the bit-depth and the linearity/gamma - but for 8-bit pixels (with 256 levels) it’s probably somewhere between 0.01 pixels and 0.1 pixels.
Which implies an accuracy of ±0.5 pixels, but that’s not good enough for anti-aliased plotting. One could perform the Bresenham algorithm on a supersampled grid of (say) 10 times the number of lines vertically and 10 times the number of pixels horizontally; that would improve the accuracy but would require ten iterations (rather than 1) per line. To achieve better than 0.1 pixels, which it’s probable the antialiased plotting can manage, it would mean supersampling by an even larger factor. The speed advantage then becomes less clear-cut.
I don’t understand this. If you know the exact distance from the physical pixel to the ideal circle, then you can adjust the alpha channel (say, 8bits). This is much better than 0.5 pixels (which would be if you had only 3 values of alpha: opaque, transparent and half transparent).
Yes, but I thought the standard Bresenham algorithm only returned an integer value (in pixels) for the coordinates of the “ideal circle”, which obviously would mean that the ‘distance’ from the nearest physical pixel is always the same. Is there something I’m missing?
right, in the Bressenham algo (at least the one I know) at each step you propagate an ‘error’ e, which is a signed float, and this e is the horizontal distance from the integer ‘result’ of the algorithm to the ideal circle.
EDIT: this description is not entirely correct, see the following posts below
I’m not familiar with that algorithm. The one I know works only with integers, as circleBres()here and copied below. Obviously if there’s a version of the algorithm that gives exact (rather than approximate) values for the circle’s coordinates it would be suitable. It would need to work for (axis-aligned) ellipses as well as circles though.
// Function for circle-generation
// using Bresenham's algorithm
void circleBres( int xc, int yc, int r)
{
int x = 0, y = r;
int d = 3 - 2 * r;
drawCircle(xc, yc, x, y);
while (y >= x)
{
// for each pixel we will
// draw all eight pixels
x++;
// check for decision parameter
// and correspondingly
// update d, x, y
if (d > 0)
{
y--;
d = d + 4 * (x - y) + 10;
}
else
d = d + 4 * x + 6;
drawCircle(xc, yc, x, y);
delay(50);
}
}
Circle algorithm without anti-aliasing.
(first octant only)
initialise: e=0, x=r, y=0
while y <= x:
plot(x,y)
e1 = e + (2 * y + 1)
e2 = e + (2 * (y - x + 1))
y = y+1
if abs (e1) < abs (e2)
then e = e1
else:
x = x-1
e = e2
The idea is simple and nice: starting from a point (x,y) in the first octant, when we increase y by 1, there are only two candidates for the closest point to the ideal circle: either (x,y+1) or (x-1,y+1).
For each one we compute the error (=norm²(x,y) - r²), this gives e1 and e2. Then we choose the best one (=least error), and continue.
Now, in order to make an anti-aliased version, we can use the error e to change the alpha channel
What is the formula for deriving the alpha from ‘e’: are you sure it does not involve a square root? If it does, you have not achieved any simplification! Note that ‘e’ is always an integer in the code you listed.
When plotting an antialiased filled circle (or ellipse) the required alpha value is the proportion, by area, of the pixel that is ‘inside’ the circle (or ellipse). If the pixel is entirely inside the circle the alpha is 1.0; if it is entirely outside the circle the alpha is 0.0 (i.e. the pixel is not plotted).
The non-trivial case is when the pixel and circle intersect. To calculate accurately the proportion of the pixel inside the circle is in fact quite difficult (for example see this Stack Overflow question). In practice it is necessary to use an approximation to achieve an acceptable performance.
I am not convinced that it is possible to derive the alpha from ‘e’ in a simple way, but if you can come up with a formula that does so which is faster to calculate than my existing code I will happily make the substitution.
that’s right, in this algorithm e is not the distance (as I wrongly stated in my previous post), but a difference of squared distances, and indeed it’s an integer, which is even better (there will be no numerical accumulation of errors). Note that it is the exact difference between the squared distance from pixel to the origin and the radius².
Of course, I don’t want to take square roots, as it will ruin the purpose of optimization. But it is not needed. You can just take alpha1=e2/(e1+e2) (for the left pixel) and alpha2=(e1/(e1+e2)) = 1 - alpha1 for the right pixel. [in the case of a filled circle, only the right pixel is needed]
