June 30, 2007 will

In yr code twiddling yr bits

Added a few functions to gameobjects.util that seemed worth sharing. The first two are two-dimensional versions of range and xrange. When iterating over something 2 dimensional (such as pixels in an image) you typically have an outer loop for the y coordinate, and an inner loop for the x coordinate. The range2d and xrange2d functions combine these two loops in to one and take range iterables as parameters.

def range2d(range_x, range_y):

    """Creates a 2D range."""

    range_x = list(range_x)
    return [ (x, y) for y in range_y for x in range_x ]

def xrange2d(range_x, range_y):

    """Iterates over a 2D range."""

    range_x = list(range_x)
    for y in range_y:
        for x in range_x:
            yield (x, y)

Here's how you might use range2d to iterate over the coordinates in an image.

for x, y in range2d(xrange(width), xrange(height)):
    #Do something with x, y

The xrange2d function returns a generator rather than a list, but works the same.

Next up we have two functions to help with power of two textures; is_power_of_2 returns True if a given value is a power of 2, and next_power_of_2 returns a power of 2 that is greater than or equal to a given value. These may be useful if you are working with OpenGL which requires power of 2 textures. I know newer versions of OpenGL support non-power of 2 textures, but it is a good idea to stick to power of 2 dimensions for compatibility.

def is_power_of_2(n)
    """Returns True if a value is a power of 2."""
    return log(n, 2) % 1.0 == 0.0

def next_power_of_2(n):
    """Returns the next power of 2 that is greater than or equal to n"""
    return int(2 ** ceil(log(n, 2)))

There is actually bit-twiddling magic that could replace both of these functions, but I don't want to make any assumptions about which is faster in Python. The bit-twiddling code to calculate the next power of 2 is particularly suspect. It may generate just a dozen or so instructions in C, but I suspect that the Python overhead would make it slower than doing the float math. I may be wrong, but I lack the motivation to do the tests. The following is C *spit* code to find the next power of 2.

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

If you are going for a job interview in the games industry, memorizing that code may be worthwhile, but you will never need it again!

Ok. Thats your lot. Go play nicely.

Use Markdown for formatting
*Italic* **Bold** `inline code` Links to [Google](http://www.google.com) > This is a quote > ```python import this ```
your comment will be previewed here
gravatar
Paddy3118

For is_power_of_2 and next_power_of_2 you could pre-compute the first 32 (or 64 or ...) powers of two and keep them in a sorted list as well as a set

The is_power function boils down to 'return n in set_of_powers'

The next_power would become
for x in list_of_powers:
if x >= n: return x


- Paddy.

gravatar
Richard Jones

Hehe. See http://pyglet.googlecode.com/svn/trunk/pyglet/image/__init__.py _nearest_pow2 :)

gravatar
Will

So Pyglet uses bit-twiddling... Ok, now I'm sufficiently motivated to do some tests!