Circle drawing

Here's some code to draw circles one pixel at a time. It uses entirely integer math, so the radius is also an integer.

'Midpoint Circle algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local radius:Int
Local p,x,y:Int
Repeat
	Cls
	If MouseDown(1)
		xCenter=MouseX()
		yCenter=MouseY()
	EndIf
	radius=Abs(xCenter-MouseX())
	x=0
	y=radius
	Plot xCenter+x,yCenter+y
	Plot xCenter-x,yCenter+y
	Plot xCenter+x,yCenter-y
	Plot xCenter-x,yCenter-y
	Plot xCenter+y,yCenter+x
	Plot xCenter-y,yCenter+x
	Plot xCenter+y,yCenter-x
	Plot xCenter-y,yCenter-x
	p=1-radius
	While x<y
		If p<0
			x:+1
		Else
			x:+1
			y:-1
		EndIf
		If p<0
			p=p+(x Shl 1)+1
		Else
			p=p+((x-y) Shl 1)+1
		EndIf
		Plot xCenter+x,yCenter+y
		Plot xCenter-x,yCenter+y
		Plot xCenter+x,yCenter-y
		Plot xCenter-x,yCenter-y
		Plot xCenter+y,yCenter+x
		Plot xCenter-y,yCenter+x
		Plot xCenter+y,yCenter-x
		Plot xCenter-y,yCenter-x
	Wend
	Flip
Until KeyHit(KEY_ESCAPE)
End

And here is the routine to draw an ellipse. It's a bit more complicated as you can see. Again it uses only integer math/variables. However, there are two lines that require a floating point calculation and a rounding operation. The ellipse itself, as with the circle, does not use any trigonometry. Currently this routine does not support rotation, but if you are plotting the pixels with Max2D or direct OpenGl/DirectX, maybe you can draw vertices/pixels whose position are influenced by rotation, e.g. rotating the camera or something. As it stands, the routine draws a non-rotated ellipse and if you were to rotate the same coordinates they might not produce an accurate or smooth ellipse when rotated.

'Midpoint ellipse algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local Rx,Ry:Int
Local p,px,py,x,y:Int
Local Rx2,Ry2,twoRx2,twoRy2:Int
Local pFloat:Float
Repeat
	Cls
	If MouseDown(1)
		xCenter=MouseX()
		yCenter=MouseY()
	EndIf
	Rx=Abs(xCenter-MouseX())
	Ry=Abs(yCenter-MouseY())
	DrawText String(Rx)+" x "+String(Ry),20,20
	Rx2=Rx*Rx
	Ry2=Ry*Ry
	twoRx2=Rx2 Shl 1
	twoRy2=Ry2 Shl 1
	'Region 1
	x=0
	y=Ry
	Plot xCenter+x,yCenter+y
	Plot xCenter-x,yCenter+y
	Plot xCenter+x,yCenter-y
	Plot xCenter-x,yCenter-y
	pFloat=(Ry2-(Rx2*Ry))+(0.25*Rx2)
	p=Int(pFloat)
	If pFloat Mod 1.0>=0.5 Then p:+1
	px=0
	py=twoRx2*y
	While px<py
		x:+1
		px:+twoRy2
		If p>=0
			y:-1
			py:-twoRx2
		EndIf
		If p<0 Then p:+Ry2+px Else p:+Ry2+px-py
		Plot xCenter+x,yCenter+y
		Plot xCenter-x,yCenter+y
		Plot xCenter+x,yCenter-y
		Plot xCenter-x,yCenter-y
	Wend
	'Region 2
	pFloat=(Ry2*(x+0.5)*(x+0.5))+(Rx2*(y-1.0)*(y-1.0))-(Rx2*(Float(Ry2)))
	p=Int(pFloat)
	If pFloat Mod 1.0>=0.5 Then p:+1
	While y>0
		y:-1
		py:-twoRx2
		If p<=0
			x:+1
			px:+twoRy2
		EndIf
		If p>0 Then p:+Rx2-py Else p:+Rx2-py+px
		Plot xCenter+x,yCenter+y
		Plot xCenter-x,yCenter+y
		Plot xCenter+x,yCenter-y
		Plot xCenter-x,yCenter-y
	Wend
	Flip
Until KeyHit(KEY_ESCAPE)
End

UPDATED:

Here is the (now updated) circle routine, with a modification to fill the circle, making sure to draw each row only once. In this example it draws a filled circle and also draws a hollow one on top. You can comment out either the DrawRects or the Plots, and you'll see each circle by itself. Because it's drawing both parts simulateneously some pixels appear to go missing.

'Midpoint Circle algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local radius:Int
Local p,x,y,prevy:Int
Repeat
	Cls
	If MouseDown(1)
		xCenter=MouseX()
		yCenter=MouseY()
	EndIf
	radius=Abs(xCenter-MouseX())
	x=0
	y=radius
	SetColor $FF,$88,$00
	DrawRect xCenter-y,yCenter+x,y Shl 1,1
	SetColor $FF,$FF,$FF
	Plot xCenter+x,yCenter+y
	Plot xCenter-x,yCenter+y
	Plot xCenter+x,yCenter-y
	Plot xCenter-x,yCenter-y
	Plot xCenter+y,yCenter+x
	Plot xCenter-y,yCenter+x
	Plot xCenter+y,yCenter-x
	Plot xCenter-y,yCenter-x
	p=1-radius
	While x<y-1
		prevy=y
		If p<0
			x:+1
		Else
			x:+1
			y:-1
		EndIf
		If p<0
			p=p+(x Shl 1)+1
		Else
			p=p+((x-y) Shl 1)+1
		EndIf
		If y<prevy And x<y
			SetColor $FF,$88,$00
			DrawRect xCenter-x,yCenter+y,x Shl 1,1
			DrawRect xCenter-x,yCenter-y,x Shl 1,1
			SetColor $FF,$FF,$FF
			Plot xCenter+x,yCenter+y
			Plot xCenter-x,yCenter+y
			Plot xCenter+x,yCenter-y
			Plot xCenter-x,yCenter-y
		EndIf
		SetColor $FF,$88,$00
		DrawRect xCenter-y,yCenter+x,y Shl 1,1
		DrawRect xCenter-y,yCenter-x,y Shl 1,1
		SetColor $FF,$FF,$FF
		Plot xCenter+y,yCenter+x
		Plot xCenter-y,yCenter+x
		Plot xCenter+y,yCenter-x
		Plot xCenter-y,yCenter-x
	Wend
	Flip
Until KeyHit(KEY_ESCAPE)
End

UPDATED:

Here is the ellipse routine which now draws a filled ellipse (at the same time as a hollow one), making sure to only draw each row once. Again you can either take out the Plots or the DrawRects to see either the filled or unfilled ellipse by itself. Since they are drawn simultaneously, some pixels appear to go missing. Removing the Plots or the DrawRects lets the full filled or unfilled ellipse be drawn in entirity without trashing the other one.

'Midpoint ellipse algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local Rx,Ry:Int
Local p,px,py,x,y,prevy:Int
Local Rx2,Ry2,twoRx2,twoRy2:Int
Local pFloat:Float
Repeat
	Cls
	If MouseDown(1)
		xCenter=MouseX()
		yCenter=MouseY()
	EndIf
	Rx=Abs(xCenter-MouseX())
	Ry=Abs(yCenter-MouseY())
	DrawText String(Rx)+" x "+String(Ry),20,20
	Rx2=Rx*Rx
	Ry2=Ry*Ry
	twoRx2=Rx2 Shl 1
	twoRy2=Ry2 Shl 1
	'Region 1
	x=0
	y=Ry
	SetColor $FF,$88,$00
	DrawRect xCenter-Rx,yCenter,Rx Shl 1,1
	SetColor $FF,$FF,$FF
	Plot xCenter+Rx,yCenter
	Plot xCenter-Rx,yCenter
	Plot xCenter,yCenter-Ry
	Plot xCenter,yCenter+Ry
	pFloat=(Ry2-(Rx2*Ry))+(0.25*Rx2)
	p=Int(pFloat + (Sgn(pFloat)*0.5))
	px=0
	py=twoRx2*y
	While px<py-1
		prevy=y
		x:+1
		px:+twoRy2
		If p>=0
			y:-1
			py:-twoRx2
		EndIf
		If p<0 Then p:+Ry2+px Else p:+Ry2+px-py
		If y<prevy And px<py-1
			SetColor $FF,$88,$00
			DrawRect xCenter-x,yCenter+y,x Shl 1,1
			DrawRect xCenter-x,yCenter-y,x Shl 1,1
			SetColor $FF,$FF,$FF
			Plot xCenter+x,yCenter+y
			Plot xCenter-x,yCenter+y
			Plot xCenter+x,yCenter-y
			Plot xCenter-x,yCenter-y
		EndIf
	Wend
	'Region 2
	pFloat=(Ry2*(x+0.5)*(x+0.5))+(Rx2*(y-1.0)*(y-1.0))-(Rx2*(Float(Ry2)))
	p=Int(pFloat + (Sgn(pFloat)*0.5))
	y:+1
	While y>1
		y:-1
		py:-twoRx2
		If p<=0
			x:+1
			px:+twoRy2
		EndIf
		If p>0 Then p:+Rx2-py Else p:+Rx2-py+px
		SetColor $FF,$88,$00
		DrawRect xCenter-x,yCenter+y,x Shl 1,1
		DrawRect xCenter-x,yCenter-y,x Shl 1,1
		SetColor $FF,$FF,$FF
		Plot xCenter+x,yCenter+y
		Plot xCenter-x,yCenter+y
		Plot xCenter+x,yCenter-y
		Plot xCenter-x,yCenter-y
		Wend
	Flip
Until KeyHit(KEY_ESCAPE)
End

Added all four to the BlitzMax code archives. :-)

Hoorar for Mr Bresenham!

Indeed. What I just realized though is that the filled routines are doing some work that doesn't need to be done. The ellipse and circle are drawn first of all from the top and the bottom towards the middle, then the middle section is filled in. The middle part is correct, but because some of the top and bottom quarters have more than one pixel on a horizontal row, drawing rectangles for every one of those pixels is filling the row more times than is needed. What should better happen is the routine should only draw the first rectangle/row for the first pixel that it gets to on a new line, when the Y coord changes, rather than for every movement. Then it would only draw one row for each which would cut out a bunch of graphics operations and speed it up.

For the circle, those instructions are the last four Plots or the last two DrawRects of each group. For the ellipse, it's anything drawn in `region 1` of the code.

Since I realized that the fill was drawing a lot of the lines more than once, where there are more than one pixel horizontally on a line (if it were hollow), I have made modifications to the above circle and ellipse programs (and re-uploaded) to now do it correctly.

Each row to be fiilled is only drawn once. So this now draws correctly when SetBlend LIGHTBLEND or some other mode is used. As a result it is also faster.