3 ms·
Binary Space partitioning (https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning) is an elegant algori
by 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 agoA prettier demo: https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=60 https://turbowarp.org/984959784/fullscreen?stuck&hqpen&fps=6...
- SiempreViernes 9mo agoMan 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 agoWithin 2 seconds I knew exactly where this was and I haven't played in 20 years. Dust is forever.
- CamperBob2 9mo agoThey 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 agoIt 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.
- taneq 9mo agoFor rendering voxel data like in a minecraft world I’d think an octree would be the go-to data structure.
- douira 9mo agoHi, it’s me, the author. In this thesis the focus was on techniques that don’t involve splitting the geometry into pieces, and the objects in Figure 4.2 can’t be partitioned without splitting. In later iterations of the implementation I have added splitting and I’ve detailed this in a talk I gave at Blanketcon 2025 (https://douira.dev/assets/document/presentation-blanketcon25.pdf https://douira.dev/assets/document/presentation-blanketcon25...), but the algorithm still attempts to avoid it as much as possible since it can explode the amount of quads in the worst case.
- djmips 9mo agoBSP was not used in Doom and Quake for rendering translucency.
- taneq 9mo agoOkay. BSP trees were the basis of the Doom WAD format and were used for visible surface determination and depth sorting, though. Seems relevant.