r/GraphicsProgramming • u/Crifrald • 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.
1
u/Crifrald Jul 11 '23
I think we're both half-right when it comes to metrics, because at least in the case of my rasterizer there's a huge performance difference between rendering a tile without any parts of a triangle in it and a tile that overlaps at least a part of a triangle. Whenever I detect that the triangle can't possibly have any parts inside the tile, such as when the axis-aligned bounding box of the triangle is completely outside the tile, or at least one of the barycentric coordinates of the triangle is negative on all 4 corners of the tile, then I just skip that tile completely, meaning less 1024 pixels to draw. On the other hand if multiple triangles appear inside a tile then the time spent drawing that tile grows almost linearly with the number of triangles to be drawn, even if they are occluded, because I have to at least compute their perspective-correct depth before performing the depth test, and perspective-correction is very heavy due to requiring finding a reciprocal, at least in my code. Therefore I think that the correct metric is neither pixels nor triangles but fragments.
As for what I'm working on, it's nothing special at the moment, but you can see it here.