3 ms·

Geometric Algorithms for Translucency Sorting in Minecraft [pdf]

77 points by HeliumHydride 9mo ago

jacobp100 9mo ago
I had a blog post on something similar (but less sophisticated) https://jacobdoescode.com/2025/05/18/precomputing-transparency-order-in-3d https://jacobdoescode.com/2025/05/18/precomputing-transparen...
- Sharlin 9mo ago
  This is… essentially a BSP tree traversal without splitting polys that straddle a partition plane, right?
gatane 9mo ago
This looks interesting! Thanks for sharing it, wonder if anyone else has related content.
- zoenolan 9mo ago
  - Stencil Routed A-buffer [1] - Multi-Fragment Effects on the GPU using the k-Buffer [2] - Production Volume Rendering [3] - Translucent Shadow Maps [4] [1] https://developer.download.nvidia.com/presentations/2007/siggraph/stencil_routed_a-Buffer_sigg07.ppt https://developer.download.nvidia.com/presentations/2007/sig... [2] https://www.sci.utah.edu/~stevec/papers/kbuffer.pdf https://www.sci.utah.edu/~stevec/papers/kbuffer.pdf [3] https://graphics.pixar.com/library/ProductionVolumeRendering/paper.pdf https://graphics.pixar.com/library/ProductionVolumeRendering... [4] https://www.scribd.com/document/657069029/Translucent-Shadow-Maps https://www.scribd.com/document/657069029/Translucent-Shadow...
- user____name 9mo ago
  Emil Persson's GPU BSP traversal demo (2017) https://www.humus.name/index.php?page=3D&ID=92 https://www.humus.name/index.php?page=3D&ID=92
ANighRaisin 9mo ago
Binary Space partitioning (https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning) 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. 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. https://scratch.mit.edu/projects/1203675921 https://scratch.mit.edu/projects/1203675921 is an example of such a project.
- ANighRaisin 9mo ago
  A prettier demo: https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=60 https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=6...
  - SiempreViernes 9mo ago
    Man Dust in 1.6! At first instantly familiar but then things didn't make sense and I realise I was in an alien land.
    - seg_lol 9mo ago
      Within 2 seconds I knew exactly where this was and I haven't played in 20 years. Dust is forever.
- CamperBob2 9mo ago
  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 the go-to example of a sorting problem that is handled with BSP trees.
  - user____name 9mo ago
    It works, it may just degenerate into a worst case scenario, and this particular scenario is pretty common in minecraft. I think this is particular to auto-partitioning BSPs where the splitting planes are aligned with scene geometry.
NotGMan 9mo ago
There was an old AMD/Ati demo where they did per-pixel sorting, basicaly a per pixel linked list of fragments. In general: https://en.wikipedia.org/wiki/Order-independent_transparency https://en.wikipedia.org/wiki/Order-independent_transparency
rendaw 9mo ago
Only slightly related, but since Minecraft seems to have a lot of community graphics programming associated with it I thought I'd ask here... Does anyone know how those Minecraft realistic rendering mods work? I'm guessing today there's a lot of RTX, but e.g. in 2018 there was still fairly impressive global illumination in SEUS Renewed. Minecraft is the definition of a world with dynamic geometry, and I'm not aware of any decent realtime GI algorithms for 3d. The lighting in base Minecraft is a super basic and ugly hack. I've seen Unity's dynamic GI features and those are nowhere near as good either.
- HeliumHydride 9mo ago
  I don't know much about lighting, but looking at the source code of the shaders might give a clue. https://modrinth.com/discover/shaders https://modrinth.com/discover/shaders has a lot of shaders that change the lighting. In other parts of the rendering pipeline, there are some very impressive mods utilizing GPU magic. One of them is Voxy (https://modrinth.com/mod/voxy https://modrinth.com/mod/voxy), one that massively increases render distance with mesh shaders and level-of-detail based rendering.
  - rendaw 9mo ago
    Ah yeah, I was mostly interested in lighting, but that's really interesting too. Voxy's LOD thing... so like, I guess what they do is when you're in an area so that area's high LOD assets are loaded, it computes the lower LOD and saves it, and then as you move around you get a library of more and more lower LODs? And since modifications to geometry only happen when you're nearby the LODs are static? I'd love to see a writeup of that too...
- amlib 9mo ago
  A lot of non raytracing GI solutions uses voxel grids on top of the world geometry, SVOGI is one of the fancy ones used in cry engine games. I imagine since minecraft essentially gives a voxel grid to you for "free" most of minecraft GI solutions also uses a similar technique.
jjoe 9mo ago
Three-pass method analysis of the paper: https://papersplain.com/sample/19d93721d4de21982ca5d81ec63969919f1e8e9cc48ccc33f7630614d6a8e374 https://papersplain.com/sample/19d93721d4de21982ca5d81ec6396...
Lucasoato 9mo ago
If you’re marveled by these articles, I suggest you to read this blog: https://0fps.net/ https://0fps.net/ It inspired me so much back when I was graduating in mathematics, the author is a genius.

77 points by HeliumHydride 9mo ago

I had a blog post on something similar (but less sophisticated) https://jacobdoescode.com/2025/05/18/precomputing-transparency-order-in-3d https://jacobdoescode.com/2025/05/18/precomputing-transparen...

Sharlin 9mo ago
This is… essentially a BSP tree traversal without splitting polys that straddle a partition plane, right?

gatane 9mo ago

This looks interesting! Thanks for sharing it, wonder if anyone else has related content.

zoenolan 9mo ago
- Stencil Routed A-buffer [1] - Multi-Fragment Effects on the GPU using the k-Buffer [2] - Production Volume Rendering [3] - Translucent Shadow Maps [4] [1] https://developer.download.nvidia.com/presentations/2007/siggraph/stencil_routed_a-Buffer_sigg07.ppt https://developer.download.nvidia.com/presentations/2007/sig... [2] https://www.sci.utah.edu/~stevec/papers/kbuffer.pdf https://www.sci.utah.edu/~stevec/papers/kbuffer.pdf [3] https://graphics.pixar.com/library/ProductionVolumeRendering/paper.pdf https://graphics.pixar.com/library/ProductionVolumeRendering... [4] https://www.scribd.com/document/657069029/Translucent-Shadow-Maps https://www.scribd.com/document/657069029/Translucent-Shadow...
user____name 9mo ago
Emil Persson's GPU BSP traversal demo (2017) https://www.humus.name/index.php?page=3D&ID=92 https://www.humus.name/index.php?page=3D&ID=92

ANighRaisin 9mo ago

Binary Space partitioning (https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning) 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. 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. https://scratch.mit.edu/projects/1203675921 https://scratch.mit.edu/projects/1203675921 is an example of such a project.

ANighRaisin 9mo ago
A prettier demo: https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=60 https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=6...
- SiempreViernes 9mo ago
  Man Dust in 1.6! At first instantly familiar but then things didn't make sense and I realise I was in an alien land.
  - seg_lol 9mo ago
    Within 2 seconds I knew exactly where this was and I haven't played in 20 years. Dust is forever.
CamperBob2 9mo ago
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 the go-to example of a sorting problem that is handled with BSP trees.
- user____name 9mo ago
  It works, it may just degenerate into a worst case scenario, and this particular scenario is pretty common in minecraft. I think this is particular to auto-partitioning BSPs where the splitting planes are aligned with scene geometry.

NotGMan 9mo ago

There was an old AMD/Ati demo where they did per-pixel sorting, basicaly a per pixel linked list of fragments. In general: https://en.wikipedia.org/wiki/Order-independent_transparency https://en.wikipedia.org/wiki/Order-independent_transparency

rendaw 9mo ago

Only slightly related, but since Minecraft seems to have a lot of community graphics programming associated with it I thought I'd ask here... Does anyone know how those Minecraft realistic rendering mods work? I'm guessing today there's a lot of RTX, but e.g. in 2018 there was still fairly impressive global illumination in SEUS Renewed. Minecraft is the definition of a world with dynamic geometry, and I'm not aware of any decent realtime GI algorithms for 3d. The lighting in base Minecraft is a super basic and ugly hack. I've seen Unity's dynamic GI features and those are nowhere near as good either.

HeliumHydride 9mo ago
I don't know much about lighting, but looking at the source code of the shaders might give a clue. https://modrinth.com/discover/shaders https://modrinth.com/discover/shaders has a lot of shaders that change the lighting. In other parts of the rendering pipeline, there are some very impressive mods utilizing GPU magic. One of them is Voxy (https://modrinth.com/mod/voxy https://modrinth.com/mod/voxy), one that massively increases render distance with mesh shaders and level-of-detail based rendering.
- rendaw 9mo ago
  Ah yeah, I was mostly interested in lighting, but that's really interesting too. Voxy's LOD thing... so like, I guess what they do is when you're in an area so that area's high LOD assets are loaded, it computes the lower LOD and saves it, and then as you move around you get a library of more and more lower LODs? And since modifications to geometry only happen when you're nearby the LODs are static? I'd love to see a writeup of that too...
amlib 9mo ago
A lot of non raytracing GI solutions uses voxel grids on top of the world geometry, SVOGI is one of the fancy ones used in cry engine games. I imagine since minecraft essentially gives a voxel grid to you for "free" most of minecraft GI solutions also uses a similar technique.

jjoe 9mo ago

Three-pass method analysis of the paper: https://papersplain.com/sample/19d93721d4de21982ca5d81ec63969919f1e8e9cc48ccc33f7630614d6a8e374 https://papersplain.com/sample/19d93721d4de21982ca5d81ec6396...

Lucasoato 9mo ago

If you’re marveled by these articles, I suggest you to read this blog: https://0fps.net/ https://0fps.net/ It inspired me so much back when I was graduating in mathematics, the author is a genius.