Midpoint Ellipse Algorithm

I must admit, I use this one as a modified version from what's found on Wikipedia and I haven't really delved too deeply into how it works. All I know is that it calculates 45 degrees from 0 to <45 and then from 45 to <90 and draw the ellipse by repeating each value across the four graphing quadrants.

I intend to dig a bit deeper into this one since I really don't like the way the math is laid out. Even though it's only a single line of floating point calculations, I'll sleep a little better at night if I can convert it to fixed point instead. The DSP I'm using is a slug on floating point at best. Additionally, it makes use of 64-bit integers for "error" adjustments and I'm not pleased with that either. I'm sure it can function on a much lower precision with equal results. So at some point I'll sit and refactor this function more completely to make it useful in all circumstances.

```/// Draws four points relative to the given center point.
///
/// \li centerX + X, centerY + Y
/// \li centerX + X, centerY - Y
/// \li centerX - X, centerY + Y
/// \li centerX - X, centerY - Y
///
/// \param centerX the x coordinate of the center point
/// \param centerY the y coordinate of the center point
/// \param deltaX the difference between the centerX coordinate and each pixel drawn
/// \param deltaY the difference between the centerY coordinate and each pixel drawn
/// \param color the color to draw the pixels with.
inline void plotFourQuadrants(int32_t centerX, int32_t centerY, int32_t deltaX, int32_t deltaY, Color color)
{
setPixel(centerX + deltaX, centerY + deltaY, color);      // Ist      Quadrant
setPixel(centerX - deltaX, centerY + deltaY, color);      // IInd     Quadrant
setPixel(centerX - deltaX, centerY - deltaY, color);      // IIIrd    Quadrant
setPixel(centerX + deltaX, centerY - deltaY, color);      // IVth     Quadrant
}

/// Implements the midpoint ellipse drawing algorithm which is a bresenham
/// style DDF.
///
/// \param centerX the x coordinate of the center of the ellipse
/// \param centerY the y coordinate of the center of the ellipse
/// \param horizontalRadius the horizontal radius of the ellipse
/// \param verticalRadius the vertical radius of the ellipse
/// \param color the color of the ellipse border
void ellipse(int centerX, int centerY, int horizontalRadius, int verticalRadius, Color color)
{

int x = 0;
int y = verticalRadius;
int deltaX = 0;
int deltaY = (doubleHorizontalRadius << 1) * y;

plotFourQuadrants(centerX, centerY, x, y, color);

while(deltaY >= deltaX)
{
x++;
deltaX += (doubleVerticalRadius << 1);

error +=  deltaX + doubleVerticalRadius;

if(error >= 0)
{
y--;
deltaY -= (doubleHorizontalRadius << 1);

error -= deltaY;
}
plotFourQuadrants(centerX, centerY, x, y, color);
}

error = (int64_t)(doubleVerticalRadius * (x + 1 / 2.0) * (x + 1 / 2.0) + doubleHorizontalRadius * (y - 1) * (y - 1) - doubleHorizontalRadius * doubleVerticalRadius);

while (y>=0)
{
y--;
error -= deltaY;

if(error <= 0)
{
x++;
deltaX += (doubleVerticalRadius << 1);
error += deltaX;
}

plotFourQuadrants(centerX, centerY, x, y, color);
}
}
```
page revision: 3, last edited: 05 Oct 2010 06:40