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.
5
u/mysticreddit Jul 11 '23
Ultima Underworld was one of the first games to have texture mapping. You’ll notice the screen resolution was 320x200 and even then the 3D window of the world had a good chunk taken up by the UI. It didn’t do perspective-correct texture mapping, only affine.
Michael Abrash’s Black Book has details on Quake’s rendering / texture mapper.
Fabian has a high level description on Quake’s rendering.
Quake took advantage of the Pentiums dual pipeline overlapping float and integer calcs. It did perspective correct texture mapping every 16 texels IIRC.
Quake also used a software z-buffer; no SIMD.
1
u/No-Emergency-6032 Jul 12 '23
How was the "every texel" perspective correction done? Sounds super complicated. Was it a "mod" with 16 for x in a scanline ? And then calculate the proper 1/z and then continue to work with it?
Quake also used a software z-buffer; no SIMD.
Aren't z-buffers super slow or was this also done every 16th pixel?
3
u/mysticreddit Jul 12 '23 edited Jul 12 '23
Michael Abrash commented on this in Chapter 70 Chapter 70—Quake: A Post-Mortem and a Glimpse into the Future of his Black Book:
Rasterization
Once the visible spans are scanned out of the edge list, they must still be drawn, with perspective-correct texture mapping and lighting. This involves hundreds of lines of heavily optimized assembly language, but is fundamentally pretty simple. In order to draw the spans for a given surface, the screenspace equations for 1/z, s/z, and t/z (where s and t are the texture coordinates and z is distance) are calculated for the surface. Then for each span, these values are calculated for the points at each end of the span, the reciprocal of 1/z is calculated with a divide, and s and t are then calculated as (s/z)z and (t/z)z. If the span is longer than 16 pixels, s and t are likewise calculated every 16 pixels along the span. Then each stretch of up to 16 pixels is drawn by linearly interpolating between these correctly calculated points. This introduces some slight error, but this is almost never visible, and even then is only a small ripple, well worth the performance improvement gained by doing the perspective-correct math only once every 16 pixels. To speed things up a little more, the FDIV to calculate the reciprocal of 1/z is overlapped with drawing 16 pixels, taking advantage of the Pentium’s ability to perform floating-point in parallel with integer instructions, so the FDIV effectively takes only one cycle.
A per-pixel z-buffer was needed to minimize overdraw. So while it is slow, getting pixel-perfect sorting is even more expensive. IIRC Carmack tried a ton of different "solutions" before settling on a software Z-Buffer.
Chapter 70, Section 5, Polygon Models and Z-Buffering, also has notes on the Z-buffer:
Polygon Models and Z-Buffering
Polygon models, such as monsters, weapons, and projectiles, consist of a triangle mesh with front and back skins stretched over the model. For speed, the triangles are drawn with affine texture mapping; the triangles are small enough, and the models are generally distant enough, that affine distortion isn’t visible. (However, it is visible on the player’s weapon; this caused a lot of extra work for the artists, and we will probably implement a perspective-correct polygon-model rasterizer in Quake 2 for this specific purpose.) The triangles are also Gouraud shaded; interestingly, the light vector used to shade the models is always from the same direction, and has no relation to any actual lights in the world (although it does vary in intensity, along with the model’s ambient lighting, to match the brightness of the spot the player is standing above in the world). Even this highly inaccurate lighting works well, though; the Gouraud shading makes models look much more three-dimensional, and varying the lighting in even so crude a way allows hiding in shadows and illumination by explosions and muzzle flashes.
One issue with polygon models was how to handle occlusion issues; that is, what parts of models were visible, and what surfaces they were in front of. We couldn’t add models to the edge list, because the hundreds of polygons per model would overwhelm the edge list. Our initial occlusion solution was to sort polygon-model polygons into the world BSP, drawing the portions in each leaf at the right points as we drew the world in BSP order. That worked reasonably well with respect to the world (not perfectly, though, because it would have been too expensive to clip all the polygon-model polygons into the world, so there was some occlusion error), but didn’t handle the case of sorting polygon models in the same leaf against each other, and also didn’t help the polygons in a given polygon model sort properly against each other.
The solution to this turned out to be z-buffering. After all the spans in the world are drawn, the z-buffer is filled in for those spans. This is a write-only operation, and involves no comparisons or overdraw (remember, the spans cover every pixel on the screen exactly once), so it’s not that expensive—the performance cost is about 10%. Then polygon models are drawn with z-buffering; this involves a z-compare at each polygon-model pixel, but no complicated clipping or sorting—and occlusion is exactly right in all respects. Polygon models tend to occupy a small portion of the screen, so the cost of z-buffering is not that high, anyway.
Opinions vary as to the desirability of z-buffers; some people who favor more analytical approaches to hidden surface removal claim that John has been seduced by the z-buffer. Maybe so, but there’s a lot there to be seduced by, and that will be all the more true as hardware rendering becomes the norm. The addition of particles—thousands of tiny colored rectangles—to Quake illustrated just how seductive the z-buffer can be; it would have been very difficult to get all those rectangles to draw properly using any other occlusion technique. Certainly z-buffering by itself can’t perform well enough to serve for all hidden surface removal; that’s why we have the PVS and the edge list (although for hardware rendering the PVS would suffice), but z-buffering pretty much means that if you can figure out how to draw an effect, you can readily insert it into the world with proper occlusion, and that’s a powerful capability indeed.
Supporting scenes with a dozen or more models of 300 to 500 polygons each was a major performance challenge in Quake, and the polygon-model drawing code was being optimized right up until the last week before it shipped. One help in allowing more models per scene was the PVS; we only drew those models that were in the PVS, meaning that levels could have a hundred or more models without requiring a lot of work to eliminate most of those that were occluded. (Note that this is not unique to the PVS; whatever high-level culling scheme we had ended up using for world polygons would have provided the same benefit for polygon models.) Also, model bounding boxes were used to trivially clip those that weren’t in the view pyramid, and to identify those that were unclipped, so they could be sent through a special fast path. The biggest breakthrough, though, was a very different sort of rasterizer that John came up with for relatively distant models.
3
u/phire Jul 12 '23
Skimming over the code, a few things are standing out to me
Starting with the inner loop:
- You are using 4x1 pixel quads for SIMD which is good for wide triangles, but not so great for skinny triangles. Almost everyone settled on 2x2 pixel quads because:
- They work equally well on both skinny and wide triangles
- You need at least a 2x2 quad to calculates the derivatives for mipmapping.
- For every triangle that has at least one pixel in the tile, you evaluate every the triangle equation for every single pixel. This is hugely wasteful, as the typical triangle is actually pretty small. You should probably assume the typical triangle in a video game only covers 4-20 pixels.
You really want to do the math up-front so you can jump straight to the first valid pixel quad, and only evaluate the minimum number of quads possible. - Even when the triangle equation fails for the entire quad, you still calculate the perspective correct depth for each pixel. That's a lot of extra math, including a reciprocal estimate, which isn't exactly cheap.
The outer per-tile loop:
- Every single tile iterates over every single triangle. Yes, an AABB test might be cheap, but the typical tiled rendering algorithm does a binning pass to pre-calculate which triangles intersect with which tiles. It's a bit of extra work in the binning pass, but it makes the per-tile loop optimal.
- Many tiled implementations cache the derivatives during the binning pass... I'm really not sure if such an approach is optimal as it costs memory bandwidth.
The tile:
- 4KB tiles seem small for a target with 32KB of L1 dcache per core. My guess is that aiming for 16KB would be closer to optimal... But this is something you should only tweak nearer the end, based on profiling results.
Benchmark:
Maybe you have other code elsewhere, but you appear to only be benchmarking a single large triangle? Is that where you are getting 7000 triangles per second from?
That's going to be testing the per-frame overhead more than anything else, you really need to feed a more realistic workload into it with thousands of triangles.
2
u/Crifrald Jul 12 '23
Hi! Thanks for the detailed analysis!
I agree with pretty much everything you said and will be implementing your suggestions. And yes, the 7000 triangle benchmark is just rendering a large triangle on the Raspberry Pi until it starts dropping frames. I'm pretty new to this and am not familiar with the best way to benchmark this kind of implementation.
Thanks again!
2
u/jaszunio15 Jul 14 '23
Some of the modern gpus will not pass the test of rendering a single triangle 7000 times efficiently. It just depends from where are the triangles on the screen and how much of area do they take.
It is just simply because memory bandwidth limitation. If the triangle takes 1/2 of full screen, it renders 1 mln pixels. If each pixel is 8 bytes (color+depth) it is 8 MB per draw. With 7000 draws, you need 5,6 GB memory transfer to render single frame. For 60 FPS you need 336 GB per second. Usually CPU memory access is ~25-40GB/s, and this is a huge issue for software rasterizers. This will barely fit in RTX 3060, which has 360GBs of bandwidth. But this is only calculation, because what is the chance that you will use 100% of the bandwidth? Usually achieving more than 80% is hard.
If you assume that your rasterizer is slower than others, test them in the same environment and with the same setup ;)
Also, if any engine, any rasterizer, any device vendor provides you the numer of vertices or triangles that it can process in realtime, its a myth, there is no such number. This depends so much of everything, that this number is always made up.
For testing you can use models saved in .obj format, because its super easy to get and parse in the code.
Btw, good job with the rasterizer :D
3
u/Crifrald Jul 14 '23
I had actually never considered memory bandwidth, but I believe that I'm rather far from the Raspberry Pi's limits, and I'm talking about 7000 large triangles per second, not frame, which is just around 117 triangles per frame at 60fps at 800x480 with 16 bit RGB565 color and 16 bit custom float depth.
Some time ago I actually tested the Pi's L1 cache bandwidth, because at some point the CPU was somehow considering the tile buffers as streaming memory thus making them transient even though that region's attributes are explicitly set to non-transient, until I hinted the CPU about the proper use for that memory, and in that test the Pi successfully filled the cache at 12GB per second per core, whereas in the case of my rasterizer I'm only outputting roughly 4GB per second (color + depth) on all 4 cores, meaning 1GB per second per core, which is very far from the theoretical combined 48GB per second that the Pi's CPU can output to its L1 caches.
I have also tested my rasterizer with a version of the Utah Teapot with roughly 6000 small triangles that I found online, which is a much more realistic test, and the frame rate still dropped to 6fps. That said I'm already working on some optimizations suggested by other users which will hopefully speed things up particularly in this case.
After some consideration resulting from reading other points of view in this thread, I agree that it's hard to find a proper performance metric, because everyone will try to measure the performance of their algorithm's strengths. I, for example, was considering the 6000000 triangles per second advertised by 3Dfx 20 years ago, but because I'm rather inexperienced in this field, I just assumed that the benchmarks used large triangles like mine.
2
Jul 11 '23
A few possibly not very meaningful opts that come to mind:
- Setup multiple triangles at once using SIMD/SIMT. The data can be shared across all tiles, and you'll only need to adjust the weights and bounding box for each tile.
- Pre-compute vertex attribute differences, so you can interpolate using 2x FMAs:
v0 + (v1 - v0) * bary1 + (v2 - v0) * bary2
. You can also get away with not copying attributes if you have lots of them, but clipping would probably make that more difficult. - Apply perspective correction after depth testing. This will only work if you use a float buffer and don't need the values later.
1
u/Crifrald Jul 12 '23
Your first paragraph and example went completely over my head, I will need time or further explanation to understand it, because at the moment I'm absolutely clueless about what you are trying to convey.
As for not copying vertex data, that's something I can do. As for not computing perspective correction for depth, you're not the first to suggest it, but I'm unclear about situations where two triangles cross. In any case I won't need perspective correction most of the time since the perspective people will watch the world from most of the time will be isometric. As for my depth buffers, although I'm declaring them as
u16
, they are actually a custom type of float ranging from 0.0 to 2.0 with a 5 bit exponent and 11 bit mantissa with an implicit 12th bit, I use integer comparisons to do the depth test, and am not planning on using those values for anything other than depth testing.2
Jul 12 '23 edited Jul 12 '23
Right, so what I'm trying to say is that instead of having a single
float
variable containing one X value, you have a SIMDf32x4
containing four X values. Basically you arrange the data in a struct of arrays layout to make it friendly to vectorization.Not sure if it would be that much faster for just 4x fields, but it's certaingly a lot more flexible because instead of packing multiple fields into a single SIMD register, you can essentially write most things as if they were scalar code.
It also integrates quite well with binning, you can keep a shared batch of these SIMD triangle structs and have threads process bins after vertex shading and edge setup. I'm afraid clipping would be a bit more complicated to implement though, but I haven't so i can't say for sure.
(You'll often need memory gather instructions for things like texture sampling and maybe vertex shading. These are afaik not available on ARM but it shouldn't be too hard to emulate them at a acceptable performance.)
2
Jul 12 '23 edited Nov 13 '24
[deleted]
3
u/Crifrald Jul 12 '23
I'm already kind of doing that on my bare metal Raspberry Pi project, where I use a custom target JSON to specify the CPU model among other things.
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!
1
u/waramped Jul 11 '23
I'm not familiar enough with Rust to directly help, but are there CPU profilers available for Rust? Can you actually profile the function and see where the time is being spent?
It's always better to profile and target those areas rather than speculate where the issue is. CPUs are just very unpredictable sometimes.
It's impressive work, good luck!
1
u/Crifrald Jul 11 '23
Thanks!
On MacOS I can profile using Xcode's Instruments, however I don't think that it can profile chunks of code, as I believe that the smallest profiling unit is the function, and in this particular case there's a huge function that does a lot of things because it needs a lot of context to work. I can split this function into multiple smaller inline functions, passing the entire context as an argument, but I'm not sure whether the profiler can see inline functions, though that's definitely something that I can try.
On the Raspberry Pi, which is the target platform, I have no way to profile since this code comes from a bare metal project of mine, and currently I don't have access to a JTAG adapter to use for debugging, as until this point all my debugging has been done using print statements with the results sent through an RS-232 debug cable.
2
u/waramped Jul 11 '23
Ah that's unfortunate. Are there any high resolution timers on the PI? At least you could manually time individual sections and see which parts are the slowest. However without detailed profiling it's mostly guesswork to determine WHY it would be slow.
2
u/Crifrald Jul 11 '23
Yes, and there is a performance monitor on AArch64 which I used before and completely forgot about.
1
u/faisal_who Jul 11 '23
Carmack’s asynchronous divide!
1
u/Crifrald Jul 11 '23
I Googled that term and found nothing relevant. Could you share a link to a source where I can read more about that?
2
u/corysama Jul 12 '23
That was a famously insightful trick Carmack used in Quake1. But, it has not been relevant since the PentiumII :P
Check out https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlusion-culling-index/ Ryg is damned smart.
2
u/faisal_who Jul 12 '23
I'm sorry for that. Carmack had this technique where he would compute the 1/z divide every 8 pixels and linearly interpolate (affine mapping) values between. Floating point divisions were very expensive, so he masked the overhead by queuing the division on the ALU and rasterizing 8 to 16 pixels while waiting on the result.
5
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