Drawing fast lines in pygame

Question

I'm trying to draw fast lines using pygame that aren't rendered directly to the screen. I've got a Python list as large as the number of pixels for the desired resolution, and store integer values corresponding to the number of times that pixel was hit by the line algorithm. Using this, a 2D heat map is built up, so rather than drawing a flat pixel value, pixel values are incremented based on the number of times a line runs through it, and "hot" pixels get brighter colours.

The reason for doing it this way is that we don't know in advance how many of these lines are going to get drawn, and what the maximum number of times any given pixel is going to be hit. Since we'd like to scale the output so that each rendering has the correct maximum and minimum RGB values, we can't just draw to the screen.

Is there a better way to draw these lines than a relatively naive Bresenham's algorithm? Here's the critical part of the drawLine function:

  # before the loop, to save repeated multiplications
  xm = []
  for i in range(resolution[0]):
    xm.append(i * resolution[0])

  # inside of drawLine, index into the f list, of size resolution[0] * resolution[1]
  for x in range(x0, x1 + 1):
    if steep:
      idx = y + xm[x]
      f[idx] += 1
    else:
      idx = x + xm[y]
      f[idx] += 1

The end result is scaled and drawn to the screen based on the maximum value inside of f. For example, if the maximum value is 1000, then you can assume the RGB value of each of the pixels is (f[i] * 255) / 1000.

The profile information says that runtime is dominated by the index lookups into f. I've used previous questions here to prove that these basic lists are faster than numpy arrays or arrays in Python, but for drawing lines like this, it still seems like there's room to improve.

What's a good and fast method for drawing an unknown number of lines to the screen, knowing that you'll be scaling the output in the end to render to the screen? Is there a good way to get rid of the index overhead?

Answer 1

Try Cython or something similar. (If you do, I would be interested in knowing if/how much that helped)

Cython is a programming language to simplify writing C and C++ extension modules for the CPython Python runtime. Strictly speaking, Cython syntax is a superset of Python syntax additionally supporting: Direct calling of C functions, or C++ functions/methods, from Cython code. Strong typing of Cython variables, classes, and class attributes as C types. Cython compiles to C or C++ code rather than Python, and the result is used as a Python Extension Module or as a stand-alone application embedding the CPython runtime. (http://en.wikipedia.org/wiki/Cython)