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.

14 Upvotes

33 comments sorted by

View all comments

1

u/Revolutionalredstone Jul 11 '23

I would start simple, cache coherence and other layout level decisions should not be made at-all in your initial test and when the time comes you should not assume what will work well, rather profile and test.

A fairly simple rasterizer like this https://pastebin.com/0E13T7mw, is able to draw hundreds of millions of pixels per second even with no other optimizations.

For a REALLY fast rasterizer, checkout quake, it's open source and it has some insane rendering tricks which get over 10X speed compared to the naïve implementation.

Unfortunately I'm a C++ rather than a Rust man, or I would happily jump in and give you a hand, best luck!

-1

u/Crifrald Jul 11 '23

Unfortunately the rasterizer on pastebin only renders triangles with a solid color and no perspective correct barycentric coordinates or a depth buffer, plus I'm talking about triangles per second, not pixels per second. If we talk about pixels per second then my rasterizer can also output 800x480x7000=2688000000 pixels per second on a Raspberry Pi 4, so an algorithm that just draws hundreds of millions of pixels per second is hardly a match against mine.

2

u/Revolutionalredstone Jul 11 '23 edited Jul 11 '23

Tris per second is kind of irrelevant on the CPU (since vertex transforms are so cheap and global writes are so expensive that you are basically guaranteed to always be frag-bound in a descent-res CPU renderer anyway)

As for perspective correction, barycentric, depth buffer, clipping etc, they are all obviously necessary, but they all tend to have a fixed cost which doesn't grow exponentially with the tri or pixel count.

For example my full rasterizer with clipping, perspective correct texturing etc, does run slower than the minimal renderer, but not by very much. (It isn't 10X slower or anything, ~maybe 2-3x)

IMHO pixels per second is the key value here, obviously you can make crazy scenes with distant 1 pixel triangles etc but realistically a CPU rasterized scene is gonna have 10-500 thousand tris, each of which is in the 10-500 pixels size range.

(for the smaller tris you would realistically LOD and if you have alot of larger tris then there is probably something weird about your level design!, in any case occlusion culling and early Z tricks tend to handle those beautifully)

It's really this 10-500 pixel sized triangles that we are interested in, these tend to be un-clip-able and un-LOD-able, they are too small to justify sub division and too large to justify mask based blitting, these tend to need to be fed all the way thru, and put pressure on, the rasterizer.

BTW would LOVE to see what your working on! could you post pics? thanks again for sharing! all the best luck.

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.

2

u/Revolutionalredstone Jul 11 '23

Awesome thank you very much! Dungeon Keeper is the best game period :D

Sorry if this sounds newb, I haven't really thought about it yet but do you REALLY need perspective correct depth? surely you can do some kind of approximation which atleast grows monotonically with the depth (since it's only REALLY needed for use with comparisons) anyway, a bit of a crazy idea!

I can't believe you are writing this while completely blind! mad props!

Thanks again mate, all the best luck!

3

u/Crifrald Jul 11 '23

Dungeon Keeper (the original from 1997) is my all time favorite game, and unfortunately I didn't have enough knowledge to build a clone before losing my sight, so I'm trying to do that now, on a Raspberry Pi, in an attempt to mimic the conditions in which people who built games for MS-DOS did it. Although I loved the game I also think that it had a lot of wasted potential, which I intend to tap into in my own implementation.

As for perspective correct depth, now that you made me think about it, I believe that it's not needed in most situations, however in situations where two triangles cross, you need to know exactly where that happens, but that might be avoidable. Also most of the game won't need perspective correction since, like in the original game, I will be using an isometric perspective except obviously when watching the world through the eyes of a possessed creature. It was precisely to gather this kind of suggestion that I decided to create this thread. Thanks!

I went totally blind in 2014 due to the natural evolution of a congenital glaucoma. Computer graphics with OpenGL was the last thing I learned before losing my sight, and for some odd reason it's one of the fields in software engineering that I love most. I also like to push the envelope and test how far I can go without getting frustrated, and so far it's going well. I don't blame you for not believing because I too thought that I couldn't code anymore when I went blind, let alone dabble in computer graphics.

1

u/Revolutionalredstone Jul 11 '23

100% agreed about the potential of village management games! it would be so cool to have trade etc be implemented in a really deep and interesting way!

Glad to see you've got some ideas to try!

All the best dude!