8
\$\begingroup\$

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, True, False # vsync off to unlimit fps
RADIUS = 30
CORNERS = 20

# 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()

def on_step(dt):
    """ Logic performed every frame. """
    global counter
    x = randrange(RADIUS, WIN[0] - RADIUS)
    y = randrange(RADIUS, WIN[1] - RADIUS)
    circle(x, y, RADIUS, CORNERS, WHITE+RED*CORNERS, batch)

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

pyglet.clock.schedule(on_step)
pyglet.app.run()

I would be glad if you would help to make my method faster, more readable and better overall.

And by the way, this is another version that uses GL_TRIANGLE_FAN and doesn't work because I don't know how to cut off one circle from another. You can try it out:

def circle2(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
    p = x, y # adding center of fan
    for i in range(n):
        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(n+2, pyglet.gl.GL_TRIANGLE_FAN, None, ('v2i', p), ('c3B', (c)))

but use

# Additional specification of the last gradient
circle(x, y, RADIUS, CORNERS, WHITE+RED*CORNERS+RED, batch)

instead.

Oh, and my math:

math

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Using a rotation matrix is definitely gonna speed up the algorithm (avoiding goniometric functions always pays off) but I doubt you'll see any improvements from exploiting the symmetry because using the rotation matrix (4 multiplications and 2 additions per point) is so fast already. \$\endgroup\$ – Vincent van der Weele May 17 '15 at 7:56
  • \$\begingroup\$ @D-side I tried the rotation matrix. Could not get it work as expected: it draws a perfect octagon only. If I try to increase N the thing I get is spiral spiraling down. I will try exploiting my axes and only allowing Ns divisible by 8. That should both simplify and speed up my code. \$\endgroup\$ – Marius Macijauskas May 17 '15 at 14:37
  • \$\begingroup\$ @Xis88 you could post that "wrong code" on StackOverflow so others might point out the issue. The most frequent issue I have seen with others doing this is doing like this: x = rotate_x(x, y, angle); y = rotate_y(x, y, angle) -- obviously this doesn't work, as x is overwritten and y is computed from the wrong data. This is really the most substantial optimization here. \$\endgroup\$ – D-side May 17 '15 at 14:49
  • \$\begingroup\$ @D-side Okay. But are you sure that this is really the most substantial optimization here? The axes seem so mind-bogglingly efficient for 8*n-gons! Imagine you've got an octagon - you have to calculate only one point and all others are just flipping and swapping! And it's much simpler! \$\endgroup\$ – Marius Macijauskas May 17 '15 at 14:57
  • \$\begingroup\$ @Xis88 huh, that makes sense, it's an 8-times CPU cut and should work fine on smaller circles even when recomputing base points from scratch. The rotation matrix' improvement should be clearer on larger circles, like 160 points. \$\endgroup\$ – D-side May 17 '15 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.