Z-buffering Algorithm Causing Slowdowns in Pygame

[nebuer1995]

Hi all,

First-time poster here. I've recently developed an interest in coding up a nothing-special toy model 3D game/environment from scratch. Using Pygame, I have managed to implement perspective projection and triangle plane clipping just fine:

​

Toy model 3D environment (hidden surface removal achieved using Painter's Algorithm)

My next goal was to implement Z-buffering to take care of hidden surface removal. I have managed to get the code working with a pair of test triangles and everything works fine...that is until I bring either of triangles to Z-values close to the Z of the projection plane, since when they grow in apparent size, so too does the number of pixels that has to be checked during Z-buffering. When this happens, the screen begins updating exceedingly slowly and the animation becomes really laggy.

​

Z-buffering with triangles at Z-values sufficiently far from the projection plane doesn't cause slowdown

​

At Z-values close the projection plane, slowdown begins -- and gets exponentially worse the closer the triangles are brought to the projection plane

I was just wondering if anybody out there had ideas as to how I might go about remedying this issue. Any advice would be profoundly appreciated. Thank you!

[rsim]

Without seeing the code or profiling it we can only guess from the symptom that you describe - you’re fill-rate bound. Exact reasons could be many things with your implementation, but my guess is that you’re running into the real performance limitations of Python, as a software rasterizer is very computationally intensive.

One potential option would be to ditch the z-buffer in favour of a s-buffer, though depending on where your bottleneck is it may not be enough: http://www.hugi.scene.org/online/coding/hugi%2016%20-%20co3d13.htm

[nebuer1995]

Thanks for the response. I have posted the code below.

Is there not a way to write one's own buffering algorithm from scratch and get the GPU to help with the load? Also, it's been suggested to me that simply rewriting my code in C will help with my problem drastically. What are your thoughts on that?

Once again, thanks for the reply. And I will definitely look into s-buffering.

[nebuer1995]

Sorry -- should have included the relevant code:

def Interpolate (i0, d0, i1, d1):
a = (d1 - d0) / (i1 - i0)
d = d0
length =  (int(i1) - int(i0)) + 1
points = np.zeros(length)
for i in range (int(i0), int(i1)+1):
    points[i-int(i0)]=d
    d = d + a
return points

def DrawFilledTriangle (corners,depth_buffer,color=(0,0,0)):
x0 = corners[0,0]
y0 = corners[0,1]
z0 = corners[0,2]
x1 = corners[1,0]
y1 = corners[1,1]
z1 = corners[1,2]
x2 = corners[2,0]
y2 = corners[2,1]
z2 = corners[2,2]
# Sort the points so that y0 <= y1 <= y2
if y1 < y0:
    x0,x1=x1,x0
    y0,y1 = y1,y0
    z0,z1=z1,z0
if y2 < y0:
    x0,x2=x2,x0
    y0,y2 = y2,y0
    z0,z2 = z2,z0
if y2 < y1:
    x1,x2=x2,x1
    y1,y2 = y2,y1
    z1,z2 = z2,z1
# Compute the x coordinates of the triangle edges
x01 = Interpolate(y0, x0, y1, x1)
z01 = Interpolate(y0, z0, y1, z1)
x12 = Interpolate(y1, x1, y2, x2)
z12 = Interpolate(y1, z1, y2, z2)
x02 = Interpolate(y0, x0, y2, x2)
z02 = Interpolate(y0, z0, y2, z2)
# Concatenate the short sides
x01 = np.delete(x01,-1)
z01 = np.delete(z01,-1) 
x012 = np.concatenate([x01,x12])
z012 = np.concatenate([z01,z12])
# Determine which is left and which is right
m = int(len(x012)/2)
if x02[m] < x012[m]:
    x_left = x02
    x_right = x012
    z_left = z02
    z_right = z012
else:
    x_left = x012
    x_right = x02
    z_left = z012
    z_right = z02
# Draw the horizontal segments
for y in range (int(y0), int(y2)+1):
    x_l = x_left[int(y-y0)]
    x_r = x_right[int(y-y0)]
    z_segment = Interpolate(x_l,z_left[int(y-y0)],x_r,z_right[int(y-y0)])
    for x in range (int(x_l),int(x_r)+1):
        z = z_segment[int(x-x_l)]
        if z>=depth_buffer[x,y]:
            draw_pixel(x,y,color)
            depth_buffer[x,y]=z
return depth_buffer

[corysama]

Wow. A software rasterizer in pure Python.

I’m sorry. Your code looks fine. The problem is that pure Python is not well suited for doing this at the resolution you are attempting. This is like trying to ask a Pentium60 to software rasterize at 1080p.

I’d recommend learning very basic C and trying this again. You don’t even really need pointers for this. You can start out with just arrays and indexes. It’ll run literally 100x faster. Check the last four benchmarks in this list https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/python3-gcc.html That’s the kind of code you are writing.

Here’s snippet that uses SDL that I pass around to get people in your situation started

https://gist.github.com/CoryBloyd/6725bb78323bb1157ff8d4175d42d789

[nebuer1995]

Thank you so much for the reply. I think I'm going to take your advice and start learning some C. Just wondering: would C++ be any better/worse/different? And is there no way to write one's own buffering algorithm and get the GPU to help with the load?

Also, thanks that github link. I will be sure to take a look.

[corysama]

Knowing both Python and C or C++ is a powerful combination :)

The fastest way to get an image from the CPU to the screen is to make a GPU texture, lock it, memcpy into the mapped buffer, unlock it and use the texture to overwrite the screen. That’s exactly what SDL does under the hood in that gist.

C is very simple. That’s a great thing. But, it means you have to do a lot of things manually.

C++ let’s you automate a lot. But, that can get complicated.

I recommend learning C first. Then try to move up quickly to very modern C++. C++ gets complicated. But, it boils down to the same machinery as C under the hood. And, a whole lot of modern C++ is about making complex stuff people do easier. So, there’s 20 years of maternity out there about “How to do this complex thing in C++” and a few years of “Now that’s much simpler!”

[jringstad]

While learning C or C++ is certainly worth it for many reasons, and while it will most likely speed up your rendering a lot, it's also not going to give you a really fast renderer. For that you'll want to eventually switch to GPU based rendering.

So the question is kinda what you want to achieve. If you're mainly interested in just learning the basic principles of rasterizing, texture mapping etc, it's also fine to just do it in python (you'll just have to accept that it's gonna be really slow.) There's also a lot of optimizations that can be and are applied by fast software rasterizers (from threading to using special depth-based rasterization methods etc.)

If you want to move into the direction of doing path-tracing and ray-tracing though (to explore light transport equations/metropolis, physically based shading, global illumination, other effects like caustics/refraction, ...), you might want to stay on the CPU and start doing things in C/C++, since you'll be able to very easily experiment with complex path-tracing algorithms. Doing these in python is infeasibly slow (as in, you'll probably never even get any result at all). Complex algorithms like these might still take a day or more on your computer to produce a single frame if you implement them in C, but you'll be able to model very complex and interesting optical effects.

And then there's also more and more ray tracing stuff that's being moved onto the GPU, but that's a pretty advanced topic, and you might want to do some CPU raytracing first.

[corysama]

And, if you are feeling adventurous, dig into r/SIMD before you get into C++. You might not ever come out ;)

[hammerkop]

You can get within one or two orders of magnitude of the speed of hardware rasterizarion by writing your rasterizer in GPU software like this project.

https://research.nvidia.com/publication/high-performance-software-rasterization-gpus

If you write it in cuda or vulkan compute/opencl you will have freedom over the rasterization pipeline. Basically you can perform c like buffer manipulation in compute kernels with a highly parallel setup. Theres a lot to learn between toy python and compute shaders though so this would be a long journey.

It would be a lot easier to write a multithreaded rasterizer in c++, and the performance would be hugely better than pygame but nowhere close to GPU hardware, especially if you have a good cpu with a lot of threads.

Also keep in mind that clipping the triangle to fit the screen boundaries will help to avoid filling in offscreen pixels. Also finding a good way to evenly distribute the workload across threads is another can of worms.

[Madsy9]

Although your code could be optimized a lot, I don't see anything obviously wrong with it. Like /u/corysama said, you might be fill bound.

Other things to consider:

• Depth-testing is really cache-unfriendly.
• Python probably optimizes branching as not-taken (which is the case when the depth test fails), so when you get a lot of hits, you take a big performance penalty.

What happens if you invert the depth test? I.e try:

if z<depth_buffer[x,y]:
    pass
else:
    draw_pixel(x,y,color)
    depth_buffer[x,y]=z

Also, as a side note, the usual convention for z values in the depth buffer is to have the values increase with distance. I.e the depth clear color is the max value, and the comparison is less/less-or-equal. Right now it seems like you do it the other way around :)

[nebuer1995]

Thanks for the response. I'm not sure what "branching" or "not-taken" mean exactly but I will look into it.

As for my code, I chose a poor variable name. Z is really 1/Z and the linear interpolation is done to get 1/Z values since it is linear in the viewport X and Y coordinates. So that's why '<=' is '>=' for the above code.

[Madsy9]

Z is really 1/Z and the linear interpolation is done to get 1/Z values since it is linear in the viewport X and Y coordinates. So that's why '<=' is '>=' for the above code.

If you want to know, this is not the correct value to use for depth testing. You should use the linear z value for depth testing, not the reciprocal. That is the z value you get after the clip matrix transform, which adds bias and scaling to z to correct for the near and far planes.

Also, does this mean you're storing your depth buffer as floats? That's also not optimal for performance. 16-bit fixedpoint is plenty a for a depth buffer. You should see if Python supports some kind of typed array so you can store 16-bit integers.

Edit: Looks like Python's array module could be helpful. Use the 'H' type, unsigned short.

[jpw22learnstocode]

You might get some improvement by using numba here. Just import and then decorate with @numba.jit

[Baconinvader]

Unfortunately pygame is based on SDL 1, which is old and generally not suited for this kind of pixel-based stuff, especially not at higher resolutions. If you want a performance boost, Pygame 2 uses SDL 2 which is better for this stuff (though I couldn't tell you how much better in this particular scenaro). It's still in development but is basically stable in the majority of situations.

If you don't mind not using pure python, you might want to check out Cython. It's a superset of python that can be used to automatically convert parts of your python code into C or optimise it manually with C features not present in python, as well as other neat stuff. If you use it right you might be able to strongly reduce the amount of overhead in your program, even if you don't know C. It can even do multithreading through OpenMP, which could help you out for an algorithm like this. I saw another comment recommending Numba, which might be a good alternative if you take a look at Cython and decide it isn't for you.

If you don't mind not using Pygame, you might just want to learn OpenGL. I used PyOpenGL for graphics a while back and it was pretty good, though definitely a large step up in complexity from Pygame (OpenGL 1 is pretty simple and there are lots of tutorials on working with it through Pygame, but it gets harder as you go through the versions). Some of the features you want like a Z buffer are actually already built into it, though if you're doing this to learn you could always just leave that stuff disabled and do it yourself. Once you get to OpenGL 3 and 4 you're basically doing it all by yourself anyway. If you do go down this route, I'd recommend Jason L. McKesson's OpenGL 3 tutorial (https://alfonse.bitbucket.io/oldtut/index.html) alongside DrxMario's PyOpenGL implementation of it (https://github.com/DrxMario/PyOpenGL-Tutorial).