Binary Space partitioning (<a href="https://en.wikipedia.org/wiki/Binary_space_partitioning" rel="nofollow">https://en.wikipedia.org/wiki/Binary_space_partitioning</a>) is an elegant algorithm that solves this issue. This has fallen out of popularity due to the invention of the depth buffer and the power of modern GPUs, but it was used in DOOM and Quake.<p>This technique, due to the unique limitation of the children's drag-and-drop coding platform, Scratch, has made it proliferate in the 3D community. <a href="https://scratch.mit.edu/projects/1203675921" rel="nofollow">https://scratch.mit.edu/projects/1203675921</a> is an example of such a project.
A prettier demo: <a href="https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=60" rel="nofollow">https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=6...</a>
They seem to point out some examples in section 4 that can't be handled with space partioning. I'll confess I don't follow the reasoning. Figure 4.2 is <i>the</i> go-to example of a sorting problem that is handled with BSP trees.
I had a blog post on something similar (but less sophisticated)<p><a href="https://jacobdoescode.com/2025/05/18/precomputing-transparency-order-in-3d" rel="nofollow">https://jacobdoescode.com/2025/05/18/precomputing-transparen...</a>
This looks interesting! Thanks for sharing it, wonder if anyone else has related content.
There was an old AMD/Ati demo where they did per-pixel sorting, basicaly a per pixel linked list of fragments.<p>In general:
<a href="https://en.wikipedia.org/wiki/Order-independent_transparency" rel="nofollow">https://en.wikipedia.org/wiki/Order-independent_transparency</a>