Very fast ellipse drawing

h4tt3n · Post by **h4tt3n** » Jun 09, 2009 19:41

Here's a little thing I cooked up...

This sub draws an ellipse with considerable less cpu consumption than normal brute-force methods. For drawing an ellipse with - say - 128 vertices an un-optimised algorithm spends 258 calls to sin() or cos(). This algorithm only spends 32 trig calls to do the exact same job!!!

Cheers,
Mike

Code: Select all

''	Very fast ellipse drawing function by Michael "h4tt3n" Nissen
''	version 1.0, june 2009

declare sub ellipse(byval x as single, byval y as single, byval a as single, _
	byval b as single, byval angle as single, byval col as uinteger)

screenres 800, 600, 16

''	red ellipse
ellipse (400, 300, 399, 299, 0, rgb(255, 32, 32))

''	green ellipse
ellipse (400, 300, 350, 100, -0.2, rgb(32, 255, 32))

''	blue ellipse
ellipse (400, 300, 420, 50, 0.6, rgb(32, 32, 255))

''	yellow circle
ellipse (400, 300, 100, 100, 0.0, rgb(255, 255, 32))

sleep

end


sub ellipse(byval x as single, byval y as single, byval a as single, _
	byval b as single, byval angle as single, byval col as uinteger)
	
	''	Very fast ellipse drawing function by Michael "h4tt3n" Nissen 
	''	version 1.0, june 2009
	''
	''	Spends less than one eigths as many trig calls as the brute-force method.
	''
	''	This algorithm requires number-of-vertices / 4 trig calls, whereas the 
	''	normal brute-force method requires 2 + number-of-vertices * 2 trig calls.
	
	''	these constants decide the graphic quality of the ellipse
	const as single	 pi						= 4*atn(1)	''	pi
	const as single	 twopi				= 2*pi			''	two pi (radians in a circle)
	const as integer face_length	= 8					''	approx. face length in pixels
	const as integer max_faces		= 4096			''	maximum number of faces in ellipse
	const as integer min_faces		= 32				''	minimum number of faces in ellipse
	
  ''	approx. ellipse circumference (Hudson's method)
  dim as single h	= (a-b*a-b)/(a+b*a+b)
  dim as single circumference = 0.25*pi*(a+b)*(3*(1+h/4)+1/(1-h/4))
  
  ''	number of faces in ellipse
  dim as integer num_faces = circumference\face_length
  
  ''	clamp number of faces
  if num_faces > max_faces then num_faces = max_faces
  if num_faces < min_faces then num_faces = min_faces
  
  ''	keep number of faces divisible by 4
  num_faces -= num_faces mod 4
	
	''	get sine and cosine to ellipse angle
  dim as single sinangle = sin(angle)
  dim as single cosangle = cos(angle)
  
  ''	theta (the angle from the ellipse center)
  dim as single theta = 0
  
  ''	deltatheta (angular step per iteration)
  dim as single deltatheta = twopi/num_faces
  
  ''	number of iterations 
  ''	(optimised to just 1/4 of the ellipse circumference)
  dim as integer num_iterations = num_faces\4
  
  ''	dim array for holding cosine theta
  dim as single costheta(1 to num_iterations-1)
  
  ''	precalc cosine theta
  for i as integer = 1 to num_iterations-1
  	theta += deltatheta
    costheta(i) = cos(theta)
  next
 	
 	''	dim arrays to hold cartesian (x, y) coordinates
 	dim as single _X(num_faces-1), _Y(num_faces-1)
 	
 	''	iterate
  for i as integer = 1 to num_iterations-1
  	
  	''	predefine handy index numbers
  	dim as integer j = 2*num_iterations - i
  	dim as integer k = 2*num_iterations + i
  	dim as integer l = 4*num_iterations - i
  	
		''	precalc a few values
    dim as single a_costheta_cosangle = a*costheta(i)*cosangle
    dim as single a_costheta_sinangle = a*costheta(i)*sinangle
    
    ''	Check this: we get sine theta from already precalced cosine theta!
  	''	since sin(angle) = cos(0.5*pi - angle). This halves the number of trig calls!
    dim as single b_sintheta_sinangle = b*costheta(num_iterations - i)*sinangle
    dim as single b_sintheta_cosangle = b*costheta(num_iterations - i)*cosangle
    
    ''	convert angles to cartesian (x, y) coordinates
    ''	Here we reuse the same cos and sin theta values four times. 
    ''	This reduces the already halved number of trig calls to one fourth - or one eighths all in all!
    _X(i) = x+a_costheta_cosangle-b_sintheta_sinangle:	_Y(i) = y+a_costheta_sinangle+b_sintheta_cosangle
    _X(j) = x-a_costheta_cosangle-b_sintheta_sinangle:	_Y(j) = y-a_costheta_sinangle+b_sintheta_cosangle
    _X(k) = x-a_costheta_cosangle+b_sintheta_sinangle:	_Y(k) = y-a_costheta_sinangle-b_sintheta_cosangle
    _X(l) = x+a_costheta_cosangle+b_sintheta_sinangle:	_Y(l) = y+a_costheta_sinangle-b_sintheta_cosangle
    
  next
  
  ''	get coordinates of the four "right angles"
  ''	(we don't need to call cos / sin theta since it'll always be 0 or 1)
  ''	This reduces the number of trig calls by two. Not much but it's there.
  _X(0*num_iterations) = x+a*cosangle:	_Y(0*num_iterations) = y+a*sinangle	''	0.0*pi
  _X(1*num_iterations) = x-b*sinangle:	_Y(1*num_iterations) = y+b*cosangle	''	0.5*pi
  _X(2*num_iterations) = x-a*cosangle:	_Y(2*num_iterations) = y-a*sinangle	''	1.0*pi
  _X(3*num_iterations) = x+b*sinangle:	_Y(3*num_iterations) = y-b*cosangle	''	1.5*pi
  
  ''	draw ellipse
  for i as integer = 0 to num_faces-1
  	dim as single j = (i+1) mod num_faces
	  line (_X(i), _Y(i))-(_X(j), _Y(j)), col		''	draw ellipse as closed line loop
	  'draw string (_X(i), _Y(i)), str(i)				''	draw ellipse point numbers
	  'pset (_X(i), _Y(i)), col									''	draw ellipse as set of points
  next
  
end sub

rdc · Post by **rdc** » Jun 09, 2009 19:53

Very nice.

h4tt3n · Post by **h4tt3n** » Mar 10, 2010 15:53

Oh well, here's a version that only spends four trig calls for any ellipse, no matter how many faces it has. It is quite a bit faster than the previous one and uses considerably less memory. In addition, the function is only half as many lines :-)

Cheers,
Mike

Code: Select all

''	Very fast ellipse drawing function by Michael "h4tt3n" Nissen
''	version 4.0 March 2010

''	syntax:
''	DrawEllipse(center x, center y, semimajor axis, semiminor axis, angle in radians, color)

''	sample program
Dim Shared As Double pi = 4*Atn(1)

declare sub DrawEllipse(byval x as single, byval y as single, byval a as single, _
byval b as single, byval angle as single, byval col as uinteger)

screenres 800, 600, 16

drawellipse(400, 300, 300, 100, 0.25*pi, rgb(255, 128, 16))		''	orange ellipse
drawellipse(400, 300, 400, 300, 0.0*pi, rgb(32, 128, 16))			''	big green ellipse
drawellipse(400, 300, 300, 300, 0.0*pi, rgb(255, 255, 255))		''	white circle
drawellipse(400, 300, 450, 50,  0.8*pi, rgb(255, 0, 255))			''	oblong purple ellipse

sleep

end

''	the sub
sub DrawEllipse(byval x as single, byval y as single, byval a as single, _
	byval b as single, byval angle as single, byval col as uinteger)
	
	''	very fast ellipse drawing function by Michael "h4tt3n" Nissen, march 2010
	
	''	these constants decide the graphic quality of the ellipse
	Const As Integer face_length	= 8					''	approx. face length in pixels
	Const As Integer max_faces		= 256				''	maximum number of faces in ellipse
	Const As Integer min_faces		= 16				''	minimum number of faces in ellipse
	
	''	approx. ellipse circumference (Hudson's method)
	Dim As Double h								= ((a-b)*(a-b))/((a+b)*(a+b))
	Dim As Double circumference 	= 0.25*pi*(a+b)*(3*(1+h*0.25)+1/(1-h*0.25))
	
	''	number of faces in ellipse
	Dim As Integer num_faces 			= circumference\face_length
	
	''	clamp number of faces
	If num_faces > max_faces Then num_faces = max_faces
	If num_faces < min_faces Then num_faces = min_faces
	
	''	keep number of faces divisible by 4
	num_faces -= num_faces Mod 4
	
	''
	Dim As Double CosAngle = Cos(Angle)
	Dim As Double SinAngle = Sin(Angle)
	
	''
	Dim As Double s  = Sin(2*pi/num_faces)
	Dim As Double c  = Cos(2*pi/num_faces)
	Dim As Double x1 = 1
	Dim As Double y1 = 0
	Dim As Double X2 = 0
	Dim As Double Y2 = 0
	
	''
	For i As Integer = 1 To num_faces-1
		
		x2 = x1
		y2 = y1
		x1 = c*x2-s*y2
		y1 = s*x2+c*y2
		
		Line(x+a*x2*CosAngle-b*y2*SinAngle,	y+a*x2*SinAngle+b*y2*CosAngle)- _
		(x+a*x1*CosAngle-b*y1*SinAngle,	y+a*x1*SinAngle+b*y1*CosAngle), col
		'PSet (x+a*x1*CosAngle-b*y1*SinAngle,	y+a*x1*SinAngle+b*y1*CosAngle), col
		'Draw String (x+a*x2*CosAngle-b*y2*SinAngle,	y+a*x2*SinAngle+b*y2*CosAngle), str(i)
		
	Next
	
	Line(x+a*x1*CosAngle-b*y1*SinAngle, y+a*x1*SinAngle+b*y1*CosAngle)- _
	(x+a*CosAngle, y+a*SinAngle), col
	'Draw String (x+a*x1*CosAngle-b*y1*SinAngle,	y+a*x1*SinAngle+b*y1*CosAngle), str(num_faces)
	
End Sub

rdc · Post by **rdc** » Mar 10, 2010 19:22

Good stuff. I needed a routine like this.

1000101 · Post by **1000101** » Mar 11, 2010 0:52

*cough*Here's an ellipse function with 0 trig calls and all ALU.

Note: This code is jacked from a larger project of mine hence it's isn't usable directly for fbgfx.

Also Note: Unlike your ellipse function, mine can't draw ellipses at angles.

Code: Select all

	Public _
	Sub				_Ellipse				( ByVal pRows As uInteger Ptr Ptr, ByVal Colour As uInteger, ByVal x0 As Integer, ByVal y0 As Integer, ByVal rx As Integer, ByVal ry As Integer, ByVal Clip_ As Clipper Ptr )
		
		
		Dim As Integer		x		= rx
		Dim As Integer		y		= 0
		Dim As Integer		XChange		= ry * ry * ( 1 - 2 * rx )
		Dim As Integer		YChange		= rx * rx
		Dim As Integer		EllipseError	= 0
		Dim As Integer		TwoASquare	= 2 * rx * rx
		Dim As Integer		TwoBSquare	= 2 * ry * ry
		Dim As Integer		StoppingX	= TwoBSquare * rx
		Dim As Integer		StoppingY	= 0
		
		
		While( StoppingX >= StoppingY )
			
			_setPixel( pRows, Colour, x0 - x, y0 + y, Clip_ )
			_setPixel( pRows, Colour, x0 + x, y0 + y, Clip_ )
			_setPixel( pRows, Colour, x0 - x, y0 - y, Clip_ )
			_setPixel( pRows, Colour, x0 + x, y0 - y, Clip_ )
			
			y		+= 1
			StoppingY	+= TwoASquare
			EllipseError	+= YChange
			YChange		+= TwoASquare
			
			If( ( 2 * EllipseError + XChange ) > 0 )Then
				x		-= 1
				StoppingX	-= TwoBSquare
				EllipseError	+= XChange
				XChange		+= TwoBSquare
			End If
			
		Wend
		
		
		x		= 0
		y		= ry
		XChange		= ry * ry
		YChange		= rx * rx * ( 1 - 2 * ry )
		EllipseError	= 0
		StoppingX	= 0
		StoppingY	= TwoASquare * ry
		
		
		While( StoppingX <= StoppingY )
			
			_setPixel( pRows, Colour, x0 - x, y0 + y, Clip_ )
			_setPixel( pRows, Colour, x0 + x, y0 + y, Clip_ )
			_setPixel( pRows, Colour, x0 - x, y0 - y, Clip_ )
			_setPixel( pRows, Colour, x0 + x, y0 - y, Clip_ )
			
			x		+= 1
			StoppingX	+= TwoBSquare
			EllipseError	+= XChange
			XChange		+= TwoBSquare
			
			If( ( 2 * EllipseError + YChange ) > 0 )Then
				Y		-= 1
				StoppingY	-= TwoASquare
				EllipseError	+= YChange
				YChange		+= TwoASquare
				
			End If
			
		Wend
		
		
	End	Sub

h4tt3n · Post by **h4tt3n** » Mar 11, 2010 5:25

Well, lets have a look at it. For starters, here's the sub made ready for compilation outside your project. I'll try to make this handle angled ellipses, otherwise I'm afraid it won't be of much use to me.

Cheers,
Mike

Code: Select all

''	sample program

''	syntax:
''	DrawEllipse(center x, center y, width, height, color)

Declare sub DrawEllipse(Byval x0 As Integer, Byval y0 As Integer, Byval rx As Integer, Byval ry As Integer, Byval Colour As UInteger)

screenres 800, 600, 16

drawellipse(400, 300, 200, 300, RGB(255, 255, 0))		''	yellow ellipse
drawellipse(400, 300, 400, 300, rgb(255, 0, 255))		''	purple ellipse
drawellipse(400, 300, 400, 200, rgb(0, 255, 0))			''	green ellipse
drawellipse(400, 300, 150, 150, rgb(0, 0, 255))			''	blue ellipse

sleep

end

''	the sub
Sub DrawEllipse(Byval x0 As Integer, Byval y0 As Integer, Byval rx As Integer, Byval ry As Integer, Byval Colour As UInteger)
	
	Dim As Integer	x                = rx
	Dim As Integer	y                = 0
	Dim As Integer	XChange          = ry * ry * ( 1 - 2 * rx )
	Dim As Integer	YChange          = rx * rx
	Dim As Integer	EllipseError     = 0
	Dim As Integer	TwoASquare       = 2 * rx * rx
	Dim As Integer	TwoBSquare       = 2 * ry * ry
	Dim As Integer	StoppingX        = TwoBSquare * rx
	Dim As Integer	StoppingY        = 0
	
	While( StoppingX >= StoppingY )
		
		PSet(x0 - x, y0 + y), Colour
		PSet(x0 + x, y0 + y), Colour
		PSet(x0 - x, y0 - y), Colour
		PSet(x0 + x, y0 - y), Colour
		
		y             += 1
		StoppingY     += TwoASquare
		EllipseError  += YChange
		YChange       += TwoASquare
		
		If( ( 2 * EllipseError + XChange ) > 0 )Then
			
			x             -= 1
			StoppingX     -= TwoBSquare
			EllipseError  += XChange
			XChange       += TwoBSquare
			
		End If
		
	Wend
	
	x             = 0
	y             = ry
	XChange       = ry * ry
	YChange       = rx * rx * ( 1 - 2 * ry )
	EllipseError  = 0
	StoppingX     = 0
	StoppingY     = TwoASquare * ry
	
	While( StoppingX <= StoppingY )
		
		Pset(x0 - x, y0 + y), Colour
		PSet(x0 + x, y0 + y), Colour
		PSet(x0 - x, y0 - y), Colour
		Pset(x0 + x, y0 - y), Colour
		
		x             += 1
		StoppingX     += TwoBSquare
		EllipseError  += XChange
		XChange       += TwoBSquare
		
		If( ( 2 * EllipseError + YChange ) > 0 )Then
			
			Y             -= 1
			StoppingY     -= TwoASquare
			EllipseError  += YChange
			YChange       += TwoASquare
			
		End If
		
	Wend
	
End Sub