[pygame] Efficient circles

[Mike Lawrence <mike.lwrnc@xxxxxxxxx>]

Hi all,

Now that pygame includes the (experimental) gfxdraw module for drawing
shapes, I thought it might interest some to hear about an efficient
circle drawing algorithm I came across:

http://slabode.exofire.net/circle_draw.shtml
(mirror: http://www.mmsguru.com/mirror/circle_cached.html)

The link discusses it in the context of OpenGL, but where the
algorithm is simply about finding out where to put the circle's
vertices, it generalizes rather widely. Below I include a timing
example of using it in pygame with gfxdraw. I know gfxdraw has a
built-in circle drawing function; indeed, as you'll see at the end of
the code, the built-in function is rather faster than either manual
function I create (possibly because it wraps compiled code for
determining the vertices?). However, I thought this example might
still be of use to some, for example those that want to make their own
version of the pie function that draws a filled pie, etc. It's even
possible that whatever compiled code achieves the built-in circle
functions may achieve speed-ups by implementing the more efficient
vertex locating algorithm.

A final note of interest, when polygon() is replaced by aapolygon() in
the manual functions below, the traditional trig approach slows down
quite a bit whereas SiegeLord's approach doesn't seem to slow down
much at all. Not sure why this would be though.

#####START CODE#####

#import requisite libraries
import pygame , math , time
from pygame.locals import *
from pygame.gfxdraw import *

pygame.init()

screen_size = (500,500)
screen = pygame.display.set_mode(screen_size)

screen_rect = screen.get_rect()
screen_x_center = screen_size[0]/2
screen_y_center = screen_size[1]/2

BLACK = (0,0,0)
WHITE = (255,255,255)
screen.fill(BLACK)

radius = 200

#define the standard (slow) circle function
def draw_circle(cx,cy,radius):
	points = []
	for angle in range(361):
		points.append(( \
			cx + math.sin(angle) * radius \
			, cy + math.cos(angle) * radius \
		))
	polygon(screen,points,WHITE)

#time the standard circle function
start=time.time()
for i in range(1000):
	draw_circle( \
		screen_x_center \
		, screen_y_center \
		, radius \
	)
print time.time()-start

#define SiegeLord's (faster) circle function
def draw_circle_fast(cx, cy, radius):
	theta = 2 * math.pi / 361
	tangetial_factor = math.tan(theta)
	radial_factor = math.cos(theta)
	x = radius
	y = 0
	points = []
	for ii in range(361):
		points.append((x + cx, y + cy))
		tx = -y
		ty = x
		x = x + tx * tangetial_factor
		y = y + ty * tangetial_factor
		x = x * radial_factor
		y = y * radial_factor
	polygon(screen,points,WHITE)

#time SiegeLord's function
start=time.time()
for i in range(1000):
	draw_circle_fast( \
		screen_x_center \
		, screen_y_center \
		, radius \
	)
print time.time()-start

#time the built-in function
start=time.time()
for i in range(1000):
	circle( \
		screen \
		, screen_x_center \
		, screen_y_center \
		, radius \
		, WHITE \
	)
print time.time()-start

#####END CODE#####

-- 
Mike Lawrence
Graduate Student
Department of Psychology
Dalhousie University

Looking to arrange a meeting? Check my public calendar:
http://tr.im/mikes_public_calendar

~ Certainty is folly... I think. ~