Will Perone

Drawing an Ellipse

The 2 main methods of drawing an ellipse are Bresenham's method and the Midpoint method.
void EllipseBresenham(int xc, int yc, int r1, int r2, int color)
{
	int x= 0, y= r2, 
		a2= r1*r1, b2= r2*r2, 
		S, T;

	S = a2*(1-2*r2) + 2*b2;
	T = b2 - 2*a2*(2*r2-1);
	drawpixel(xc-x, yc-y, color);
	drawpixel(xc+x, yc+y, color);
	drawpixel(xc-x, yc+y, color);
	drawpixel(xc+x, yc-y, color);	
	do {
		if (S < 0)
		{
			S += 2*b2*(2*x + 3);
			T += 4*b2*(x + 1);
			x++;
		} else 
		if (T < 0)
		{
			S += 2*b2*(2*x + 3) - 4*a2*(y - 1);
			T += 4*b2*(x + 1) - 2*a2*(2*y - 3);
			x++;
			y--;
		} else {
			S -= 4*a2*(y - 1);
			T -= 2*a2*(2*y - 3);
			y--;
		}
		drawpixel(xc-x, yc-y, color);
		drawpixel(xc+x, yc+y, color);
		drawpixel(xc-x, yc+y, color);
		drawpixel(xc+x, yc-y, color);
	} while (y > 0);
}

This implementation of the midpoint ellipse algorithm isn't optimized; it still uses floating point numbers.
void EllipseMidpoint(int xc, int yc, int r1, int r2, int color)
{
	double d2;
	int    x= 0, y= r2;
	double dl= r2*r2 - r1*r1*r2 + r1*r1/4.0f;


	if (!r1 || !r2) return;

	r1*=r1;
	r2*=r2;

	drawpixel(xc-x, yc-y, color);
	drawpixel(xc+x, yc+y, color);
	drawpixel(xc-x, yc+y, color);
	drawpixel(xc+x, yc-y, color);

	while (r1*(y-0.5) > r2*(x+1)) // do region 1
	{
		if (dl < 0) dl+=r2*(2.0f*x+3);       // east
		else {
			dl+=r2*(2.0f*x+3) + r1*(2-2.0f*y); //southeast
			y--;
		}
		x++;

		drawpixel(xc-x, yc-y, color);
		drawpixel(xc+x, yc+y, color);
		drawpixel(xc-x, yc+y, color);
		drawpixel(xc+x, yc-y, color);
	}

	d2= r2*(x+0.5f)*(x+0.5f) + r1*(y-1.0f)*(y-1.0f) - r1*r2;
	while (y > 0) // do region 2
	{
		if (d2 < 0)
		{
			d2+=r2*(2.0f*x+2) + r1*(3-2.0f*y); // southeast
			x++;
		} else
			d2+= r1*(3-2.0f*y);	// south
		y--;

		drawpixel(xc-x, yc-y, color);
		drawpixel(xc+x, yc+y, color);
		drawpixel(xc-x, yc+y, color);
		drawpixel(xc+x, yc-y, color);
	}	
}
1 Comment
ElEctric_EyE 2014/09/12 Contact Me0 0
Thanks for posting this code. Looks very simple. Simple enough to convert to Verilog. I need this algorithm for a 3D vector line drawing algorithm. I wasted so much time with circles (i.e. sine/cosine), I should've been focusing on ellipse all the time. Thanks!

<- for private contact