Circle drawing

BlitzMax Forums/BlitzMax Programming/Circle drawing

ImaginaryHuman(Posted 2005) [#1]
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



ImaginaryHuman(Posted 2005) [#2]
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



ImaginaryHuman(Posted 2005) [#3]
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



ImaginaryHuman(Posted 2005) [#4]
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



ImaginaryHuman(Posted 2005) [#5]
Added all four to the BlitzMax code archives. :-)


Yan(Posted 2005) [#6]
Hoorar for Mr Bresenham!


ImaginaryHuman(Posted 2005) [#7]
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.


ImaginaryHuman(Posted 2005) [#8]
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.


BLaBZ(Posted 2015) [#9]
I needed to use this to write to a pixmap instead of using Max2d - Here's the equivalent

'Midpoint ellipse algorithm

SuperStrict
Graphics 640,480,0


Local pix:TPixmap = CreatePixmap(400,400,PF_RGBA8888)
ClearPixels(pix)

Repeat
	Cls
	SetColor(255,0,0)
	DrawOvalPixmap(pix,100,100,200,400)
	DrawPixmap(pix,0,0)
	Flip
	WaitKey()
	Cls
	DrawOval(100,100,200,400)
	Flip
	WaitKey()
	
Until KeyHit(KEY_ESCAPE)
End

Function DrawOvalPixmap(Pixmap:TPixmap,x:Int,y:Int,w:Int,h:Int)
	Local Rx:Int = (w / 2.0)
	Local Ry:Int = (h / 2.0)
	
	Local p:Int,px:Int,py:Int,prevy:Int
	Local Rx2:Int,Ry2:Int,twoRx2:Int,twoRy2:Int
	Local xCenter:Int= x + (w/2.0) '320
	Local yCenter:Int= y + (h/2.0)'240
	Local pFloat:Float
	
	Local r:Int,g:Int,b:Int
	GetColor(r,g,b)

	Rx2=Rx*Rx
	Ry2=Ry*Ry
	twoRx2=Rx2 Shl 1
	twoRy2=Ry2 Shl 1
	'Region 1
	x=0
	y=Ry
	DrawRectPixmap Pixmap,xCenter-Rx,yCenter,Rx Shl 1,1,r,g,b
	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
			DrawRectPixmap Pixmap,xCenter-x,yCenter+y,x Shl 1,1,r,g,b
			DrawRectPixmap Pixmap,xCenter-x,yCenter-y,x Shl 1,1,r,g,b
		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
		DrawRectPixmap Pixmap,xCenter-x,yCenter+y,x Shl 1,1,r,g,b
		DrawRectPixmap Pixmap,xCenter-x,yCenter-y,x Shl 1,1,r,g,b
	Wend
End Function

Function DrawRectPixmap(Pixmap:TPixmap,x:Int,y:Int,w:Int,h:Int,r:Int,g:Int,b:Int)
	For Local x1:Int = x Until x+w
		For Local y1:Int = y Until y+h
			If x1 < Pixmap.width And y1 < Pixmap.height
				WritePixel(Pixmap,x1,y1,GenRGB(r,g,b))
			EndIf 
		Next
	Next
End Function

Function GenRgb:Int(red:Int, green:Int, blue:Int, alpha:Int = 255)
	Local RGB:Int = (Alpha Shl 24) | (Red Shl 16) | (Green Shl 8) | Blue
	Return RGB
End Function



Scaremonger(Posted 2015) [#10]
It is a sad thing that BlitzMax does not have native functions for non-filled circles, rectangles and polygons.

I did some timings of the MidpointCircle() function against drawOval() and a couple of functions in my library with the following results:

DrawOval(): FILLED 147 ms
DrawCircle(): NON-FILLED 5178 ms
DrawPolygon(): NON-FILLED 18668 ms
FillPolygon(): FILLED 1452 ms
MidpointCircle(): NON-FILLED 14715 ms

Obviously DrawOval() and FillPolygon() are not an exact test as this is a filled circle rather than an outline, but useful for comparison.

The test uses 5 iteration of circles drawn with a radius of between 5 and 360 and is listed below. It does not display anything on the screen so you need to watch the output tab.




ImaginaryHuman(Posted 2015) [#11]
I placed code in the code archives for bmx to do circles/ellipses filled or unfilled.


Hardcoal(Posted 2015) [#12]
tnx for your contribution I.H

Im gonna make in a blitzmax with mini b3d
a Draw oval or any polygone while actualy will create a mesh
so its gonna be ultra fast..

amen