logoalt Hacker News

ANighRaisinyesterday at 10:08 PM2 repliesview on HN

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 is an example of such a project.


Replies

CamperBob2yesterday at 10:52 PM

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.