Drawing circles with triangles

As pyglet has no in-built method to return a vertex list of circle, I had to build one myself. This is a critical piece of code that I will use very frequently. I need it to be of very fine performance.

Here's what I've written:

""" Pyglet utilities. Designed to ease drawing of primitives with Pyglet. """

# Dependencies
import pyglet
from math import sin, cos, pi

# Constants
TAU = 2 * pi

def circle(x, y, r, n, c, b):
    """ Adds a vertex list of circle polygon to batch and returns it. """
    rad = TAU / n # getting 360 / n in radians
    index = list(chain.from_iterable( (0, x-1, x)  for x in range(2, n+1) ))
    index.extend( (0, 1, n) ) # end of fan
    p = x, y # adding center of fan
    for i in range(1, n+1):
        d = rad * i
        p += int(r * cos(d)) + x, int(r * sin(d)) + y
    p += x+r, y # adding end of fan
    return b.add_indexed(n+2, pyglet.gl.GL_TRIANGLES, None, index, ('v2i', p), ('c3B', (c+c[-3:])))

This is a test that draws a circle of increasing quality:

import pyglet
from utilities import circle

# Constants
WIN = 900, 900, 'TEST', False, 'tool' # x, y, caption, resizable, style
CENTER = WIN[0] // 2, WIN[1] // 2
RADIUS = 450
SPEED = 0.3 # in seconds

# Color constants
WHITE = (255, 255, 255) # for center
RED = (255, 0, 0)       # for points

# Variables
win = pyglet.window.Window(*WIN)
win.set_location(510, 90)
batch = pyglet.graphics.Batch()
n = 3 # starting with triangle

def on_step(dt):
    """ Logic performed every frame. """
    global batch, n
    batch = pyglet.graphics.Batch()
    circle(CENTER[0], CENTER[1], RADIUS, n, WHITE+RED*n, batch)
    n += 1

@win.event
def on_draw():
    """ Drawing perfomed every frame. """
    win.clear()
    batch.draw()

pyglet.clock.schedule_interval(on_step, SPEED)
pyglet.app.run()

This is a test that adds more and more circles to the batch:

```
import pyglet
from utilities import circle
from random import randrange

# Constants
WIN = 900, 900, 'TEST', False, 'tool', False,

I can suggest a bit of math trickiness here. I highly doubt that would improve the readability of your code, but these reduce the amount of required computations. And one remark, I haven't worked with Python, so, no code. Sorry about that. Only performance suggestions.

Keep your angles constant

The heaviest part you have in your vertex computation is constantly recomputing sine and cosine, as you're creating a circle by "rotating the radius" and its angle is constantly changing by a fixed value.

You can reduce this to computing only a single pair of sine and cosine by relying on the rotation matrix. Once computed, it allows you to rotate an arbitrary point around zero by a constant angle.

You push in the first "radius" yourself, then you rotate it by rad, then by 2*rad (and you're forced to compute its sine and cosine again) and so on. But you don't really need it! Instead, you can take the previous computed radius and rotate it by rad again, using the same sine and cosine. The math looks like:

x_new = x * cos(rad) - y * sin(rad)
y_new = x * sin(rad) + y * cos(rad)

There's only one thing to be cautious of: floating point isn't perfect and absolutely precise. And in extreme cases the error will add up with each iteration and may become noticeable. You can't really counter that in any way but reducing the number of iterations. And yes, you can do that too.

Exploit your axes

You have 2 orthogonal axes. And you're drawing a circle which has a neat property of having all the points within a specific distance from its center. Assuming the circle is centered at (0; 0) for brevity, how many points can you get by performing a single rotation? One? No, actually eight. Here are 3 independent things you can do with a single point to get some others, each doubles the amount of points you get:

• Negate X

• Negate Y

• Swap X and Y

1 2 2 * 2 == 8 # Yeah, okay.

Imagine you're traversing the circle only knowing 1/8th of its points.

• You start from angle 0 (right), you reach pi/4 and...

• You follow your pointset in reverse with coordinates swapped, until you reach pi/2.

• You swap coordinates back, negate X and follow the pointset straight again, you reach 3pi/4.

• You swap coordinates and follow the pointset in reverse again until you reach pi.

• You swap coordinates, negate Y and traverse the lower semicircle the same way as above.

So it makes sense to only compute 1/8th of the circle, points in [0; pi/4]. This takes 8 times less point computations, but you should store the results and reuse them when drawing the circle. This requires some extra memory.

Of course, this does not relieve you of benchmarking the improvement. The above is math, just theory.

StackExchange Code Review Q#90921, answer score: 5