Circle and ellipse rasterization algorithm

Question

In my project i need to implement circle and ellipse rasterization (in C++ or in assembly + SIMD if possible). I know about midpoint circle algorithm and Bresenham's circle algorithm. But these algorithms work with integer values (center x, center y and radius). In my case radius and center must be expressed in floating-point format (or at least fixed point). And also radius can be less than 1px. So i need an algorithm that works with floating point values. Can somebody help me?

Answer 1

According to Wikipedia's Bresenham's algorithm, it's thought to draw a circle in the pixels of the screen.

That's the reason why you can base the calculations of your circle in floating point numbers, putting the center in any not-integer place, with any not-integer radius, and your circle will be drawn exactly into integer pixel places.

Answer 2

I'll give you the basic introduction to the midpoint algorithm for a circle, but you can find the complete midpoint algorithm in most computer graphics textbooks. I'll assume the center and radius are non-integral. Start with the implicit equation for a circle centered at (x_c,y_c) with radius R:

So given any point (x,y) in the plane, we can test whether this point is inside, on, or outside the circle. We start by only drawing the portion of the circle in the first octant where x - x_c < y_c - y. In this case we will always step by one pixel in the x direction in each iteration. We will step by either 0 or 1 in the y direction based on the sign of the midpoint m between (x+1,y) and (x+1,y+1):

x = round(xc), y = round(yc - R);  // top of circle, y-axis pts down
m = f(x+1,y + 0.5);      // initial midpoint value
while x - cx < yc - y {  // while in first octant
    plot(x,y)            // draw point at pixel grid point (x,y)
    x = x + 1            // step in x by 1
    if m < 0             // if midpoint inside circle
        y = y + 1        // then increment y too
    m = f(x,y)           // update value at midpoint
}

The main tricks left are

• Generalize to all 8 octants to complete the circle;
• For speed do not evaluate f from scratch on every iteration, instead compute the 2nd order differences of f for each horizontal and diagonal step and update date m incrementally on each iteration.
• Alternatively, if you are on a machine with vector support and/or have access to a hardware dot product then evaluate f directly may be very fast.
• If the input values are integers you can scale m = f(x + 1, y + 0.5) so that it is always an integer (we only care about the sign of f) and do everything with only integer arithematic.
• To generalize to an ellipse whose axes are parallel with the main axes you simply change your implicit equation to that of an ellipse and modify the while-loop condition to examine the gradient of f to know when you have completed an octant.
• If you wish to rasterize an oriented ellipse then the answer is beyond the scope of this response :). You can draw a "quick and dirty" ellipse using the parametric form of an ellipse and adjust the parameter step size continuously so that your step size is always between 0.5 and 1.5.