April 17, 2023

TIL (Today I learned)

Ray-casting, Ray-tracing, and Binary Space Partitions

In the process of creating a Doom Wad, I've been thinking about customizing some enemy AI behavior that would require teleporting a monster to a run-time determined location. In order to avoid teleporting the monster to out of the play-space or into another object or wall, I had considered whether ray tracing would be a necessary and sufficient solution.

Instead, I nerd-sniped myself and started reading about ray casting and ray tracing. I found this article on lodev.org to be a fairly comprehensive write up on the process. A big question I was trying to answer was "how is an intersection between a ray and wall detected?" and it is basically checking the value of an obstruction world map: a matrix of zeros and ones where 'one' indicates an obstruction. For each value in the matrix between the ray an obstruction, the world map matrix is check to see if the value is zero or one. If it is one, then the casted ray can be stopped (depending on the needed application).

When I realized that the process is depends on the world map obstruction matrix, it finally clicked what "Binary Space Partitions" ("BSP") are and what they are used for. So instead of traversing a matrix to represent a world, a BSP algorithm creates a data structure for the ray casting algorithm to traverse. I'd heard about BSP in the early years of Doom map wad modding. So not only do I have a better understanding of ray casting, but now I see how it relates to a concept I head years ago: BSP.

Somewhere in my brain, two neurons, probably created years apart, finally found each other.

What really strikes me about the process is that it can all happen 30 times per second for at least the number of pixels that need to be rendered in a computer monitor's viewport of the 3D scene - usually close to the monitor's screen resolution. Computer's have been faster than what I thought possible, for longer than what I thought possible. And yet I hear so much about how expensive cloud hosting, server time, etc are.