> So Carmack ... started reading research papers.<p>This in itself is a superpower, especially in computer science where history is considered a waste of time.<p>This is commonly even true in actual research computer science, where you'd think papers were crucial. Nowadays with the flood of "PR" preprints particularly in machine learning, it would be impossible to keep up and so nobody tries -- most of those papers write-once-read-never.<p>When I moved out of computing into biochemistry and medicine, and now into climate, I found people take papers seriously, which is a pleasure.
For Crash Bandicoot (1996), Naughty Dog sidestepped the entire VSD performance problem. Since the camera is on rails and only moves forward and back, they pre-calculated the visibility for every position and stored it in the game's data. That meant no visibility calculation needed in real time at all, and they could do it per-pixel. As a result of that and some other brilliant tricks, they were able achieve probably the best graphics on Playstation.
IIRC, both the Jedi engine (1995, <i>Dark Forces</i>) [1] and the Build engine (1995, <i>Duke Nukem 3D</i>) [2] which were of the same era used "sectors" rather than BSP trees for resolving visibility. Basically, it would traverse a graph as rays exited one sector and entered a neighboring sector. The approach is very much akin to walks through tet meshes in modern science apps.<p>In ray tracing, there are three commonly used spatial acceleration structures these days: grids, binary space partitions, and bounding volume hierarchies. Any one of those might have worked for Doom.<p>Though this post mentions marching through grids (as in Wolfenstein 3D) as not working for the arbitrarily positioned and angled walls, the usual way of using grids for ray tracing is to have each grid cell hold a list of the primitives that overlap it (many-to-many). Then you march the ray through the grid and test the ray against the list of primitives for each cell. You'd often use "mailboxing" (i.e., tiny LRU) to prevent retesting the same primitives over and over, since adjacent grid cells would often share primitives.<p>So basically extending the Wolfenstein 3D grid approach to Doom would have mean voxelizing the map to get lists of candidate walls for each cell, but testing the rays against the walls themselves (rather than say, the voxels themselves like in Minecraft).<p>I'm not sure what the tradeoffs for memory or performance on the 386s of the time would have been, however. But I think it's clear that while BSPs were a clever solution, they weren't the only possible choice.<p>[1] <a href="https://en.wikipedia.org/wiki/Jedi_(game_engine)" rel="nofollow">https://en.wikipedia.org/wiki/Jedi_(game_engine)</a><p>[2] <a href="https://en.wikipedia.org/wiki/Build_(game_engine)" rel="nofollow">https://en.wikipedia.org/wiki/Build_(game_engine)</a>
From my memory: In the 90, if you had anything to do with computer graphics[1] you knew about binary space partitioning trees.<p>Off the top of my head I remember two different articles from local German computer magazines (that are still in my basement) discussing and implementing them.<p>But so were many, many other ideas and approaches.<p>Not taking away from Carmack's genius, in my opinion it was not in inventing a horse and neither in finding one, but in betting on the right one.<p>[1] If you were a programmer in the 90s - any kind of programmer - you most certainly had.
> <i>In the early ’90s, when id Software first began publishing games, the games had to be programmed to run efficiently on computers not designed to run them, computers meant for word processing, spreadsheet applications, and little else.</i><p>That isn't really true. Games were there pretty much for all of the PC era. I was using a computer at the time Doom came out, and there were a bajillion (obviously less graphically sophisticated) games in common circulation, and gaming was a significant and widely accepted part of home computer sales.
I implemented a BSP based renderer too in around 1998- 2000.<p>Probably from that same paper.<p>It was/is such a cool fun little algorithm to implement.<p>We were building virtual reality worlds 24 years ago and people are still not using it.
Related:<p><i>The genius of binary space partitioning in Doom (2019)</i> - <a href="https://news.ycombinator.com/item?id=33692947">https://news.ycombinator.com/item?id=33692947</a> - Nov 2022 (159 comments)<p><i>Using Binary Space Partitioning in Doom</i> - <a href="https://news.ycombinator.com/item?id=21906051">https://news.ycombinator.com/item?id=21906051</a> - Dec 2019 (8 comments)<p><i>How Much of a Genius-Level Move Was Using Binary Space Partitioning in Doom?</i> - <a href="https://news.ycombinator.com/item?id=21467817">https://news.ycombinator.com/item?id=21467817</a> - Nov 2019 (6 comments)
Tangentially related: a sort of whimsical ASCII art Doom using ray casting:<p><a href="https://github.com/TurkeyMcMac/ts3d">https://github.com/TurkeyMcMac/ts3d</a><p>Full disclosure: TurkeyMcMac was my son. He wasn't much of a gamer, but he was a pretty good programmer. He wrote this in high school.
My preferred structure is the octtree over the BSP. or I guess for Doom it could have been a quad-tree. No surface splitting, and delete/re-insert for moving objects is possible. But I can claim to have known that until several years after Doom came along.
Reading the development history of the graphics engine of DOOM and especially QUAKE, it's a demonstration of John Carmack's perseverance.<p>He would try a lot of algorithms until he hits something genius enough to solve the problem. I have a feeling this is the situation when you dig in something so hard that solution eventually comes to you.
Carmack:<p>- develops Wolf 3D<p>- develops Doom, realizes there is more optimal algorithm for Wolf 3D, implements it for SNES port<p>- develops Quake, realizes there is optimal algorithm for Doom allowing for zero overdraw. Sadly never implemented or documented further than a footnote in Abrash book, maybe portals like in Duke 3D?