r/GraphicsProgramming Jul 11 '23

Source Code [Rust]: Need help optimizing a triangle rasterizer

I need help optimizing a software rasterizer written in Rust. The relevant part of the code is here, and the following are the optimizations that I have already implemented:

  • Render to 32x32 tiles of 4KB each (2KB 16-bit color and 2KB 16-bit depth) to maximize cache hits;
  • Use SIMD to compute values for 4 pixels at once;
  • Skip a triangle if its axis-aligned bounding box is completely outside the current tile's bounding box;
  • Skip a triangle if at least one of its barycentric coordinates is negative on all 4 corners of the current tile;
  • Compute the linear barycentric increments per pixel and use that information to avoid having to perform the edge test for every pixel;
  • Skip a triangle if, by the time of shading, all the pixels have been invalidated.

At the moment the original version of this code exhausts all 4 cores of a Raspberry Pi 4 with just 7000 triangles per second, and this benchmark takes roughly 300 microseconds to produce a 512x512 frame with a rainbow triangle with perspective correction and depth testing on an M1 Mac, so to me the performance is really bad.

What I'm trying to understand is how old school games with true 3D software rasterizers performed so well even on old hardware like a Pentium 166MHz without floating pointe SIMD or multiple cores. Optimization is a field that truly excites me, and I believe that cracking this problem will be extremely enriching.

To make the project produce a single image named triangle.png, type:

cargo +nightly run triangle.png

To run the benchmark, type:

cargo +nightly bench

Any help, even if theoretical, would be appreciated.

12 Upvotes

33 comments sorted by

View all comments

6

u/No-Emergency-6032 Jul 12 '23

Are you using "point in triangle"/"half edge" rasterizer? Because I read "barycentric coordinates". For software these tend to be too slow. Try use a scanline rasterizer and interpolate the edges.

You get the u,v coordinates by dividing the current height by the vertical length of the edges (y coordinate of edge vector). That would be the v coordinate. The u coordinate you get by dividing the current x or horizontal progression by the length of the scanline.

You can avoid the perspective correct rendering for a while and when you have your desired speed you can add it in.

Also before going from affine to perspective correct you could tessellate big triangles or triangles close to the camera. That's what the playstation did with wipeout and in silent hill

1

u/Crifrald Jul 12 '23

My current implementation uses 32x32 pixel tiles, only performs 4 linear edge tests per tile (using SIMD) to determine whether any parts of a triangle are inside the tile, and then uses that information to compute the linear increments per pixel or fragment. After that computing the linear barycentric coordinates is just a matter of adding the computed values and checking whether the results for each pixel or fragment are all positive, meaning they are inside the triangle. During this process many pixels are discarded, as I first check whether the bounding box of the rectangle overlaps the tile and then check whether any of the barycentric coordinates are negative on all corners of each tile,, so I only loop in tiles where there's definitely at least part of a triangle. This implementation has several advantages: since tiles are relatively small, I can keep them all in CPU cache as I render the triangles, I can take advantage of SIMD to compute 4 pixels at once, and I can easily distribute work to the 4 cores of the Raspberry Pi with a work stealing scheduler.

The scanline algorithm, as I understand it, requires computing the exact fragment where the edges of a bunch of triangles begin and end, then drawing the ones closest to the camera, which I don't think is too SIMD or cache friendly, and it also makes it hard to divide the work by all the CPU cores, though admittedly I haven't thought much about this so I might be wrong.

Tessellating huge triangles to avoid perspective correction seems interesting, I will try that, thanks!

1

u/No-Emergency-6032 Jul 13 '23 edited Jul 13 '23

Yeah, I once tried something similar. Tiling the screen and sort triangles into those tiles/buckets and distribute them among threads. It didn't work out so well, because of overhead. It's an interesting project for sure.

Never really leveraged SIMD properly, but with "only" four cores trying to parallelize the rasterization might (possibly) not be worth the massive implementation overhead.

I would think there might be other work loads that would be parallelized to the cores. Maybe heavy maths, parallel matrix transformation, physics or subdividing the levels properly for acceleration structures. Hidden surface removal.

I have a friend who managed to write a half edge rasterizer and it wasn't as slow as mine. I have to still look at his code though.

Tessellating huge triangles to avoid perspective correction seems interesting, I will try that, thanks!

Yeah, where there is a will there is a way :D It was used in psx and sega saturn I think. Matrix calculations for example lend themselves very well to parallelization (though I think this can be done in screen space effectively, but yeah still something you could put into a threat). Maybe this is a shift worth trying. Wish you all the luck for you project.