14 ms·

The genius of binary space partitioning in Doom (2019)

359 points by lispybanana 4y ago

phkahler 4y ago
I was studying computer graphics at the time. The book we used was "Computer Graphics Principles and Practice" I don't recall which edition. BSP trees are covered in the book, and like the article says, had been written about more than a decade prior. What Carmack had was the ability to read research papers and translate them into working code. I can do that too, but it does seem to be a less common skill in the software world.
- bluedino 4y ago
  > What Carmack had was the ability to read research papers And he had to read actual papers, too. I could see him making copies at the library. No Google or StackOverflow back then.
  - jasonwatkinspdx 4y ago
    Not quite when Doom came out, but within a few years you could find a surprising amount about graphics on grad students' homepages. I remember learning about PVS, Portal based rendering, and a number of similar things from the original paper author's homepage.
- bitwize 4y ago
  Not just working code -- code that worked well in a real-time video game on 386/486 class hardware. That's the genius bit as far as Doom's code is concerned. Edit: clarify
  - coliveira 4y ago
    When Carmack did his work, the computers he had were 386/486 class. So the distinction you're making doesn't make sense. Working code is code that works in the computer you have at the time you're writing the software.
    - royjacobs 4y ago
      There is a distinction between 'working code' and 'working code that runs at interactive frame rates in a severely memory-constrained environment'.
    - bombcar 4y ago
      Doom was technically developed on NeXT workstations, but it had to perform well enough on a 386 (even if in a reduced window).
  - johnvanommen 4y ago
    That was the thing that was so revolutionary about Abrash: he figured out how to create graphics that rivaled arcade hardware on the IBM PC. Most importantly: without a GPU. At the time, all of the really "flashy" arcade games used GPUs that cost around $1500 in today's dollars. Abrash pulled off this stunt with no GPU. I'd argue that the entire reason the Xbox is called "Xbox" is because of "Mode X", invented by Abrash.
    - bitwize 4y ago
      The Xbox is called Xbox because Microsoft wanted to build a console around Windows APIs, internally calling it a "DirectX box". And DirectX has nothing to do with ModeX; it's a family of APIs: DirectDraw, Direct3D, DirectSound, etc.
- JohnBooty 4y ago
  What Carmack had was the ability to read research papers and translate them into working code. I can do that too, but it does seem to be a less common skill in the software world. Well, that's the argument for Carmack being merely very very very good and not a "genius." Here's the argument for him: There were a lot of exceptionally talented people working in the games industry, and for four+ generations of PC hardware (the Keen, Wolf3D, Doom, and Quake eras) Carmack's engines were years ahead of everybody else's and had an absolutely massive impact on the industry. Of course, the term "genius" is nebulous and it can mean whatever we want it to mean. However, describing him as merely a guy who implemented other peoples' algorithms may be true in a literal sense but really misses the big picture IMO.
tasty_freeze 4y ago
BSP (binary space partitioning) was a well known algorithm, not something Carmack picked out of obscurity. It is well covered in every edition of Foley and van Dam's bible "Computer Graphics". The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. That isn't to deny that Carmack was brilliant. But him using BSP isn't some masterstroke of genius in itself.
- phkahler 4y ago
  I, Robot used a lot of great tricks, but I'm gonna have to consult John Manfrida on the use of actual BSP trees. They did use normal vectors to determine visibility and may have done simple back to front within objects using that, but the playfield is a grid and mostly rendered back to front.
  - lordfrito 4y ago
    FYI I'm the author of the original I Robot emulator from 1998. This is the one that interprets the mathbox, which means I only know what the mathbox does at the highest 'API' level (can't 100% speak to what the mathbox microcode actually does) Paul is essentially correct. It's mostly back to front, with some assumptions. I can confirm quite a number of tricks were used, not entirely sure they qualify as a full BSP (although it does involve precompiled mesh optimizations) but then again I'm no BSP expert (just an I Robot expert). The rasterizer draws a list of polygons (full polys, not just triangles) which must be fully computed before sending to the rasterizer. This "display list" is drawn in order. There is no Z buffer, so everything draws on top of what was already there. So it's important that the display list have the polygons somewhat sorted. Also the polygons are drawn as is, which means rotation/projection is done before being written to the display list. The camera was fixed (can't yaw) as to simplify math. This means you are always looking straight ahead in Z axis, which allows for all sorts of optimizations. It also makes it trivial to sort objects back to front, simply by checking z coordinate. Next, the hardware only supports 16 moveable "3D mesh" objects that can be drawn per frame. With an object count this low it's trivial to sort back to front without consuming many CPU cycles. 6809 index instructions make this part a breeze. The game playfield is "built on the fly", essentially mirroring a 16x16 (16x24? 16x32?) playfield tile array in RAM (each byte encodes tile height), and building each cube face polygon on the fly. Because of the fixed camera, no real sorting or culling is necessary when creating the display list at the highest level. You simply draw from back of the screen (furthest playfield row) to front (closest row). This process never has to change, it's a linear traversal of playfield array memory, and it always works as long as the camera doesn't yaw. Just draw each row on top of the last one. Guaranteed to not cause problems. To draw a row (16 tiles, 15 visible) all of the front/top/side polygons are computed and written to the display list. Again, because Z axis is fixed it makes creating the polygon coordinates trivial (you always see front of cube, no culling needed). Once that's done you draw any 3D meshes that are in the row (objects sitting on the playfield cells). Then you move to the next row, and the next, and then you're done. So at this high level, no real culling is done... things essentially get drawn in order of depth, which always works as long as you don't yaw the camera. Now... where things get interesting is the 3D mesh objects themselves are stored in a sort of "pre-computed" way to optimize surface removal (not sure if this was done by hand, or by an automated/compile process). It's not so much a tree structure, as it's actually done through specialized instructions. I suppose the jumping/branching is the equivalent of tree traversal. Basically the meshes are held in ROM, and are really just specialized subroutines, written as a series of simple instructions for the Mathbox. To keep this writeup simple, treat the Mathbox as being able to execute two instructions: 1) write a polygon to the display list 2) "relative jump to instruction" if normal vector dot product points towards/away from camera A 3D mesh object might be coded in ROM like this Mathbox3DMeshObject: if normal vector dot product < 0, jump to X ; pointing away from camera write poly 1 to display list ; forward facing polygons write poly 2 to display list ... Jump to Y X: write poly 10 to display list ; back facing polygons write poly 11 to display list ... Y: if normal vector dot product < 0, jump to Z ; sideway facing? write poly 20 to display list write poly 21 to display list ... Z: write poly 99 to display list ; always drawn ... END A mesh object could code any number of jumps, to cover side facing objects, corner cases, etc. Note I'm glossing over the fact that the mathbox would also multiply the coordinates by the current rotation matrix, project to X/Y, perform shading, etc. before emitting to the display list. As code it's not a real tree structure, although executing the code behaves a lot like traversing a tree. I guess this is sort of a BSP? Can anyone chime in here? It was pretty clever how it worked out. The mathbox executes the instructions, and creates draw instructions in order. Polygons get skipped by virtue of the fact you're periodically checking normal vectors, and skipping around to different instructions as needed. Edited: clarity, typos
isolli 4y ago
I'm reminded of the render algorithm in Comanche, the 1992 video game [0]. I find it remarkably ingenious, and it certainly felt incredible at the time. [0] https://github.com/s-macke/VoxelSpace https://github.com/s-macke/VoxelSpace
- speed_spread 4y ago
  I've played countless hours with the A-10 simulator which I believe used the same "voxel" technique.
  - atan2 4y ago
    Really? I am not aware of such game. Do you remember the A-10 flight sim you played that used voxelspace?
    - speed_spread 4y ago
      Apologies; I've looked it up and the one I found that most it wasn't voxel based. "Silent Thunder: A-10 Tank Killer II" was a first gen 3D accelerated game, nothing to do with Comanche, which I also remember playing with delight. Memory fades, next thing I'll be conflating Descent with those games...
sedeki 4y ago
What is a good learning path (books, videos, ???) to take in order to understand modern graphics programming? At the level of Vulkan or Metal, say. I have had a bird's eye exposure to shader-based OpenGL but don't feel I have a good intuitive understanding of how the GPU operates.
- coldpie 4y ago
  Start with Foley & van Dam to lay the groundwork & terms of art, then grab whatever API tutorial you like and get started. You'll find plenty of further resources once you're more familiar with the field and start discovering your interests. Graphics programming is a seriously deep discipline and will take years of study to start doing real work in. But it's a super cool field with plenty of work on both the research & practical implementation sides.
- newsclues 4y ago
  Graphics Programming Black Book by Michael Abrash 1997
  - bombcar 4y ago
    I recommend this even though it's now 20+ years old, it's accessible enough that you can get a foothold. Alternatively, get the Black Books for Wolfenstein and Doom, and read them first.
- i_like_apis 4y ago
  Include: Ericson, Real-Time Collision Detection https://www.goodreads.com/book/show/620505.Real_Time_Collision_Detection https://www.goodreads.com/book/show/620505.Real_Time_Collisi...
- dceddia 4y ago
  This tutorial is well regarded for learning the ins and outs of modern OpenGL including how the GPU pipeline works, which I think translates pretty well to Vulkan or Metal (at least the concepts anyway) https://learnopengl.com/ https://learnopengl.com/
ddeville 4y ago
Carmack himself describes it well in the recent interview with Lex Fridman https://youtu.be/I845O57ZSy4?t=8961 https://youtu.be/I845O57ZSy4?t=8961
0xAFFFF 4y ago
I you guys are interested in how Doom was implemented, I cannot recommend enough Fabien Sanglard's book, Game Engine Black Book: Doom. https://fabiensanglard.net/gebbdoom/ https://fabiensanglard.net/gebbdoom/
- teaearlgraycold 4y ago
  Also the first one on Wolfenstein
random314 4y ago
Yet another Carmack worship story. He is a great engineer, but let's not overhype this. It started with the legendary square root function. Which lost its legendary status once it turned out Carmack wasn't the author. Now it is about standard BSP technique from Computer graphics text books from that era. There is also hype about Carmack solving AGI by 2030, when he is yet to publish a single widely cited AI paper. EDIT: I am guilty of reading the first couple of paragraphs and assuming this was Carmack worship. My bad! Leaving the original comment, mostly as is.
- smoldesu 4y ago
  FWIW, the inverse square root function wasn't popularized by Carmack. Most people shared it because they were amused by the confused comments surrounding it, and how it demonstrated an extremely vertical slice of optimization. Treating anyone like a rockstar is a bad idea, but Carmacks and Wozniaks deserve the praise more than the Zuckerbergs and Jobs' out there.
- royjacobs 4y ago
  Let's not underhype it, either: It seems you are underestimating the impact that Doom had on PC gaming when it came out. Using BSP trees to perform zero overdraw rendering definitely was not something that had been done before on consumer level hardware and it can definitely be argued that applying them this way for Doom was a stroke of genius.
  - coliveira 4y ago
    You're setting the bar for "genius" too low, which unfortunately is commonplace in computer programming. If you take something that already exists and apply it to your code I don't call it genius. Hi quality programming, yes, but genius no.
    - royjacobs 4y ago
      I didn't realise I was not allowed to set my own bars, though :)
    - 4y ago
sebstefan 4y ago
> The really neat thing about a BSP tree, which Fuchs, Kedem, and Naylor stress several times, is that it only has to be constructed once. This is somewhat surprising, but the same BSP tree can be used to render a scene no matter where the camera viewpoint is. The BSP tree remains valid as long as the polygons in the scene don’t move. This is why the BSP tree is so useful for real-time rendering—all the hard work that goes into constructing the tree can be done beforehand rather than during rendering. I can't visualize why it's true
- bombcar 4y ago
  https://developer.valvesoftware.com/wiki/BSP https://developer.valvesoftware.com/wiki/BSP may help - the key is you have divided it into convex spaces.
- deleted 4y ago
  [deleted]
- whatshisface 4y ago
  Here's my explanation of BSP trees, written as much for my own benefit as anybody else's (maybe it will help you): To start off with, we have a basic geometric fact: if you have a surface that divides space into separate regions (this can be a closed surface like a sphere, or an infinite surface like a plane), a line of sight can't cross between the two partitions of space without passing through the surface. If the surface is convex, a line of sight can only cross it once. (That's one definition of convexity.) Now, suppose that you have a lot of objects, and none of them are on both sides of the boundary. You can ensure that condition by splitting any object that crosses the boundary in two. No matter where the line of sight begins, and no matter what direction it moves in, the boundary then offers a definite, albeit partial ordering of events: objects on the same side of the boundary may intersect, then the line will intersect the boundary, then the objects on the other side may intersect. If you find an intersection with an opaque object on the same side of the boundary, you never need to check any objects on the other side, because the order of events above. That is a big benefit when about half of the objects in front of you are on your side of the boundary: if you are right in front of the boundary, or if there's nothing on the other side of it, it doesn't help a lot. Checking all of the objects on one side of the boundary is the same kind of problem as checking all the objects, and that means you can speed those up too by having sub-boundaries for the sub-problems. That gives you the recursion and makes it a tree. If the reasoning based on boundaries continues until there is only one object in a sub-problem, you don't need to sort lists based on distance - meaning that the whole ordering problem can be solved just with partition trees. Choosing a good tree is a difficult problem because, unlike the fact that the ordering problem can always be solved, the amount that an individual boundary division helps depends on where you and the objects are in relation to it. Planes are generally used instead of other things like spheres because splitting a polygon along the edge of a sphere doesn't result in another polygon, while splitting it along a plane does.
yojo 4y ago
For people not reading the whole thing (reasonable, it is long): the author comes to the conclusion that it was not so “genius” after all, given the prior art, and that he read it in a computer graphics book. He still gives Carmack props for doing his homework and getting a working implementation built in a novel game engine.
dmbaggett 4y ago
Amazingly brilliant work, especially given the CPU capabilities at the time. Carmack's use of BSP trees inspired my own work on the Crash Bandicoot renderer. I was also really intrigued by Seth Teller's Ph.D. thesis on Precomputed Visibility Sets though I knew that would never run on home console hardware. None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. But at the time (mid 90s) it was arguably the key problem 3D game developers needed to solve. (The other was camera control; for Crash Andy Gavin did that.) A key insight is that sorting polygons correctly is inherently O(N^2), not O(N lg N) as most would initially assume. This is because polygon overlap is not a transitive property (A in front of B and B in front of C does NOT imply A in front of C, due to cyclic overlap.) This means you can't use O(N lg N) sorting, which in turn means sorting 1000 polygons requires a million comparisons -- infeasible for hardware at the time. This is why many games from that era (3DO, PS1, etc) suffer from polygons that flicker back and forth, in front of and behind each other: most games used bucket sorting, which is O(N) but only approximate, and not stable frame to frame. The handful of games that did something more clever to enable correct polygon sorting (Doom, Crash and I'm sure a few others) looked much better as a result. Finally, just to screw with other developers, I generated a giant file of random data to fill up the Crash 1 CD and labeled it "bsptree.dat". I feel a bit guilty about that given that everyone has to download it when installing the game from the internet, even though it is completely useless to the game.
- jetbalsa 4y ago
  Great comment! That poor poor bsptree.dat will forever live on. I wonder if anyone really sat down and tried to bash their head against bsptree.dat
- chrisseaton 4y ago
  > None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. You can’t mean that all the polygons in a game world are now sent to the GPU, entirely relying on viewport culling and Z buffer to remove the ones out of view? I’m not an expert but I’m sure that’s not true - doesn’t Source and latest iD Tech use BSP right now for example?
NayamAmarshe 4y ago
Doom is truly an amazing showcase of engineering achievements and going the extra mile for optimizations. Games these days just depend on raw hardware and optimization takes a back seat. Games like Plague Tale Requiem, while look fantastic, are equally bad at the engineering part. How is an RTX 3080 the minimum recommended spec for 1080@60fps, is beyond me. Sadly, people these days do not care about software optimization and those who do are bombarded with comments like "Get better hardware".
- HellDunkel 4y ago
  The truely great games do. I am sure the developers of BOTW were very serious about optimization and you can actually feel that playing the game (on switch). It’s a masterpiece just like doom.
  - hbn 4y ago
    BotW performs well enough, but there's some areas where things get REALLY choppy. It seems like areas with tall grass are the worst for it, most notably Korok forest in front of the Deku tree where you get the Master sword and talk to Hestu.
    - HellDunkel 4y ago
      Yes, i know that area. Seems as if the designers insisted on that volume light. :) Its not a combat area so its fine.
- mhh__ 4y ago
  That depends. GTA V ran pretty well on the 360 which was pretty awful hardware even a decade ago.
  - NayamAmarshe 4y ago
    Yeah, there are a few companies who focus on optimization a lot. Rockstar's games are usually well optimized. Also Sony's recent offerings as well. Maybe even throw FPS games in the mix, Call Of Duty, Battlefield all look amazing and do not require super high-end hardware.
samlittlewood 4y ago
Quite a few games (eg: Starfox) in the 90's would use BSP in a slightly different way - purely within each object. The tree would be generated offline (mechanically or by hand), and would often be some sort of branching bytecode (test this, draw that etc.) It was very useful to be able to use one plane test to discard a whole bunch of geometry, eg: a surface plus its detail, or everything visible through a window. This still left the problem of sorting between objects - mostly a depth sort was just fine. Special cases like weapons on hardpoints, or vehicles in hangars could be handled by having some sort of 'call submodel' for spaces within the parent model. Beyond that, just dial up the hostile firepower until players stop complaining about rendering artefacts.
pkilgore 4y ago
Also discussed / covered in https://news.ycombinator.com/item?id=21906051 https://news.ycombinator.com/item?id=21906051
j7ake 4y ago
Brilliant synthesis of the problem and why it was difficult. My feeling is that Carmack is really good at speeding up important parts of video game performance to achieve qualitatively different gaming experience. Sometimes I wonder if Carmack was born 30 years later, when computing resources make such advances less needed, he would still be as successful? Perhaps he would go on to improve performance of other problems eg virtual reality and deep learning…..
- emiliobumachar 4y ago
  AFAIK he did successfully improve performance in VR as part of his work in this space. He's still working currently, mostly on AGI research. https://en.wikipedia.org/wiki/John_Carmack https://en.wikipedia.org/wiki/John_Carmack Of course being famous does open doors, but there's no reason to doubt he'd break into VR in the counterfactual. He did break into game development in reality after all.
- emiliobumachar 4y ago
  "computing resources make such advances less needed" That's arguable. Someone has to improve the graphics engines at Unity and Unreal, with enormous reach. There's a big potential market in porting what only runs in dedicated VR headsets and expensive gaming computers and consoles to cheaper phone-in-a-helmet VR headsets and notebook computers. Then to cheap phones and netbooks.
diskzero 4y ago
I implimented a BSP renderer in my somewhat unremarkable CDROM game Dark Fiber [1] in 1995 or so. I also remember seeing the algorithm in Foley and Van Dam, but it wasn't until a conversation with John at some conference/tradeshow that I went for doing the engine using BSP. It was a lot of fun figuring out how to optimize the algorithm and I also spent a lot of time using Mathematica figuring out the equations. Well, that was at least my excuse for buying a fairly expensive piece of software as a small gaming startup. https://archive.org/details/DarkFiberWindowsMac https://archive.org/details/DarkFiberWindowsMac
bigmattystyles 4y ago
I thought this was going to be about all the small hallways in Doom where you have to close one door before opening another - this was done so that the engine would never have to render more space than 1 room at a time. I don't know if that's true, just something I've often heard repeated.
- tboughen 4y ago
  I played Doom, Doom 2 and Final Doom all the way through about 20 years ago - I can’t recall a single instance of this kind of level design. Doors stayed open once opened. Maybe it was done with corners/sight lines instead? To be honest I remember some vast areas rendered, especially when accessing secrets.
  - jonny_eh 4y ago
    Doors definitely auto-closed behind you.
jamestimmins 4y ago
One thing confuses me about this: does it require a separate tree per-axis?
- gary_0 4y ago
  It doesn't split by axis, it splits by planes that can be oriented however. Planes split a space into 2 half-spaces, hence the "binary" part. Only the older Wolfenstein-style rendering cared about the axis.
  - jamestimmins 4y ago
    That makes sense if I think about everything existing on a single axis (objects in front of each other on the z-axis). But if you then turn 90 degrees, then suddenly a bunch of those z-axis items are side by side, and order is based on the x-axis of my original perspective. So I don't understand how a binary structure accounts for that perspective shift. Edit: For clarification, my understanding is that there's a single tree built per-level in advance. If I'm mistaken and it's re-building the tree 30 times per second, the lack of axis concerns makes sense, but the article seemed to indicate that that's computationally prohibitive.
    - gary_0 4y ago
      The tree is built once. The tree can be traversed from any point in the world because each node stores which plane it used to split, and it is easy to compute which side of the plane you are viewing. Have you tried reading https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning ? It shows how a BSP is built and traversed for rendering.
      - jamestimmins 4y ago
        Interesting. Thanks for sharing. I think i need to dig into that article to try to understand this better.
_whiteCaps_ 4y ago
Wow, this brings back memories... I took a 3D computer graphics course in university in the early 2000s, and the final project was to make a game. IIRC we could use as many open source libraries + assets as we wanted, but we had to write the renderer. Our professor was a big Buffy the Vampire Slayer fan, so we made a Buffy game. My team thought we'd have some easy points for that. When we presented our plan, he says "I know you know I'm a Buffy fan, so this better be good"... Ooops. Time to get to work. We used the Quake map format, which is BSP, and our renderer worked pretty well. We used Quake 2 character models, which worked pretty well on its own. I think it was because someone had made some vampire models for it. When we integrated the two, the performance was terrible. Like a slideshow. After a brief panic, we realized that the Z axis was inverted between the two modules we'd written, and the guy that put them together was inverting the model every frame. After inverting it once when the model was loaded, they worked pretty well together. We added a simple hitbox (a rectangular prism at the maximum points of the model), and had a fun little game after that!
kazinator 4y ago
It seems that a challenge in BSP is going to be artifacts, when a surface, particularly a textured one, is chopped into pieces by several planes. If this is not done very carefully, the cuts might show, due to edge artifacts caused by the separate scan conversion of the fragments. Certain shading tricks like Phong may be difficult to apply in such a way that the result looks as if the original undivided polygon had been rendered.
HellDunkel 4y ago
The beauty of the BSP tree is that it used recursion. When first approached this is a challenge to wrap your head around- very similar to the quicksort algorithm. Great read. These days octtrees more or less replaced BSP trees i guess. They are easier to handle and work better with more polygons.
choeger 4y ago
What I don't understand is, how the tree can be used even after movement? How do you know which polygon is behind the other if camera position and angle are freely chosen?
- cityofdelusion 4y ago
  When the tree is traversed, you make a decision on which subtree to render depending on the camera viewpoint. This is covered in the article right before all the pictures of the trees.
Waterluvian 4y ago
I think the “sit and read research papers” part is often omitted, to our own peril, from the romanticized image of the genius computer hacker of that era.
georgeburdell 4y ago
I’m surprised by the claim Doom was the first game to use BSP. I remember in the late 90s casually browsing the internet and coming across a demo of BSP and incorporated it into my own amateurish game projects
amelius 4y ago
Nice, but it only works for static environments which is a bit unsatisfactory.
Newtonip 4y ago
I highly recommend the "Masters of Doom" book mentioned in the article. It gives a lot of insight in what motivated and inspired the people of iD as well as provides some technical details of how they accomplished things. It's a very easy read.
- hbn 4y ago
  I just finished it last night. It's certainly a fun read but I felt a little underwhelmed in the technical aspect of things. I don't think the author is a programmer so I can't really blame him. I recall the book describing DirectX as a programming language at one point.
voidfunc 4y ago
My first introduction to bsp was qeradiant while making q3a and later sof2 maps. There used to be a bsp compilation stage that I recall. At the time I had no idea what it meant.
deleted 4y ago
[deleted]
anonymousDan 4y ago
Bizarre how Carmack is idolized as being some sort of genius for reading a few research papers and applying an existing technique. What about the academic who actually invented the technique!
yrgulation 4y ago
> but this episode with the academic papers and the binary space partitioning is the justification I think of first. Subtly amusing considering carmack is not on favour of academia. But everything he uses is made possible by it.
rurban 4y ago
BSP's were first used in Quake, not Doom. Doom was not 3D, just 2.5D. Full BSP's as used in common VR's applications those times were not needed then. The Doom precomputed z-buffer hack is described in this article, but I wouldn't call it genius. The Quake BSP was much better, but neither genius as a lot of people used it before to their advantage. It was a common technique, just not in games. Even we used it in our VR application years before Quake.
- HelloNurse 4y ago
  Doom has 2D BSP trees, it's the same technique in any number of dimensions.

359 points by lispybanana 4y ago

I was studying computer graphics at the time. The book we used was "Computer Graphics Principles and Practice" I don't recall which edition. BSP trees are covered in the book, and like the article says, had been written about more than a decade prior. What Carmack had was the ability to read research papers and translate them into working code. I can do that too, but it does seem to be a less common skill in the software world.

bluedino 4y ago
> What Carmack had was the ability to read research papers And he had to read actual papers, too. I could see him making copies at the library. No Google or StackOverflow back then.
- jasonwatkinspdx 4y ago
  Not quite when Doom came out, but within a few years you could find a surprising amount about graphics on grad students' homepages. I remember learning about PVS, Portal based rendering, and a number of similar things from the original paper author's homepage.
bitwize 4y ago
Not just working code -- code that worked well in a real-time video game on 386/486 class hardware. That's the genius bit as far as Doom's code is concerned. Edit: clarify
- coliveira 4y ago
  When Carmack did his work, the computers he had were 386/486 class. So the distinction you're making doesn't make sense. Working code is code that works in the computer you have at the time you're writing the software.
  - royjacobs 4y ago
    There is a distinction between 'working code' and 'working code that runs at interactive frame rates in a severely memory-constrained environment'.
  - bombcar 4y ago
    Doom was technically developed on NeXT workstations, but it had to perform well enough on a 386 (even if in a reduced window).
- johnvanommen 4y ago
  That was the thing that was so revolutionary about Abrash: he figured out how to create graphics that rivaled arcade hardware on the IBM PC. Most importantly: without a GPU. At the time, all of the really "flashy" arcade games used GPUs that cost around $1500 in today's dollars. Abrash pulled off this stunt with no GPU. I'd argue that the entire reason the Xbox is called "Xbox" is because of "Mode X", invented by Abrash.
  - bitwize 4y ago
    The Xbox is called Xbox because Microsoft wanted to build a console around Windows APIs, internally calling it a "DirectX box". And DirectX has nothing to do with ModeX; it's a family of APIs: DirectDraw, Direct3D, DirectSound, etc.
JohnBooty 4y ago
What Carmack had was the ability to read research papers and translate them into working code. I can do that too, but it does seem to be a less common skill in the software world. Well, that's the argument for Carmack being merely very very very good and not a "genius." Here's the argument for him: There were a lot of exceptionally talented people working in the games industry, and for four+ generations of PC hardware (the Keen, Wolf3D, Doom, and Quake eras) Carmack's engines were years ahead of everybody else's and had an absolutely massive impact on the industry. Of course, the term "genius" is nebulous and it can mean whatever we want it to mean. However, describing him as merely a guy who implemented other peoples' algorithms may be true in a literal sense but really misses the big picture IMO.

tasty_freeze 4y ago

BSP (binary space partitioning) was a well known algorithm, not something Carmack picked out of obscurity. It is well covered in every edition of Foley and van Dam's bible "Computer Graphics". The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. That isn't to deny that Carmack was brilliant. But him using BSP isn't some masterstroke of genius in itself.

phkahler 4y ago
I, Robot used a lot of great tricks, but I'm gonna have to consult John Manfrida on the use of actual BSP trees. They did use normal vectors to determine visibility and may have done simple back to front within objects using that, but the playfield is a grid and mostly rendered back to front.
- lordfrito 4y ago
  FYI I'm the author of the original I Robot emulator from 1998. This is the one that interprets the mathbox, which means I only know what the mathbox does at the highest 'API' level (can't 100% speak to what the mathbox microcode actually does) Paul is essentially correct. It's mostly back to front, with some assumptions. I can confirm quite a number of tricks were used, not entirely sure they qualify as a full BSP (although it does involve precompiled mesh optimizations) but then again I'm no BSP expert (just an I Robot expert). The rasterizer draws a list of polygons (full polys, not just triangles) which must be fully computed before sending to the rasterizer. This "display list" is drawn in order. There is no Z buffer, so everything draws on top of what was already there. So it's important that the display list have the polygons somewhat sorted. Also the polygons are drawn as is, which means rotation/projection is done before being written to the display list. The camera was fixed (can't yaw) as to simplify math. This means you are always looking straight ahead in Z axis, which allows for all sorts of optimizations. It also makes it trivial to sort objects back to front, simply by checking z coordinate. Next, the hardware only supports 16 moveable "3D mesh" objects that can be drawn per frame. With an object count this low it's trivial to sort back to front without consuming many CPU cycles. 6809 index instructions make this part a breeze. The game playfield is "built on the fly", essentially mirroring a 16x16 (16x24? 16x32?) playfield tile array in RAM (each byte encodes tile height), and building each cube face polygon on the fly. Because of the fixed camera, no real sorting or culling is necessary when creating the display list at the highest level. You simply draw from back of the screen (furthest playfield row) to front (closest row). This process never has to change, it's a linear traversal of playfield array memory, and it always works as long as the camera doesn't yaw. Just draw each row on top of the last one. Guaranteed to not cause problems. To draw a row (16 tiles, 15 visible) all of the front/top/side polygons are computed and written to the display list. Again, because Z axis is fixed it makes creating the polygon coordinates trivial (you always see front of cube, no culling needed). Once that's done you draw any 3D meshes that are in the row (objects sitting on the playfield cells). Then you move to the next row, and the next, and then you're done. So at this high level, no real culling is done... things essentially get drawn in order of depth, which always works as long as you don't yaw the camera. Now... where things get interesting is the 3D mesh objects themselves are stored in a sort of "pre-computed" way to optimize surface removal (not sure if this was done by hand, or by an automated/compile process). It's not so much a tree structure, as it's actually done through specialized instructions. I suppose the jumping/branching is the equivalent of tree traversal. Basically the meshes are held in ROM, and are really just specialized subroutines, written as a series of simple instructions for the Mathbox. To keep this writeup simple, treat the Mathbox as being able to execute two instructions: 1) write a polygon to the display list 2) "relative jump to instruction" if normal vector dot product points towards/away from camera A 3D mesh object might be coded in ROM like this Mathbox3DMeshObject: if normal vector dot product < 0, jump to X ; pointing away from camera write poly 1 to display list ; forward facing polygons write poly 2 to display list ... Jump to Y X: write poly 10 to display list ; back facing polygons write poly 11 to display list ... Y: if normal vector dot product < 0, jump to Z ; sideway facing? write poly 20 to display list write poly 21 to display list ... Z: write poly 99 to display list ; always drawn ... END A mesh object could code any number of jumps, to cover side facing objects, corner cases, etc. Note I'm glossing over the fact that the mathbox would also multiply the coordinates by the current rotation matrix, project to X/Y, perform shading, etc. before emitting to the display list. As code it's not a real tree structure, although executing the code behaves a lot like traversing a tree. I guess this is sort of a BSP? Can anyone chime in here? It was pretty clever how it worked out. The mathbox executes the instructions, and creates draw instructions in order. Polygons get skipped by virtue of the fact you're periodically checking normal vectors, and skipping around to different instructions as needed. Edited: clarity, typos

isolli 4y ago

I'm reminded of the render algorithm in Comanche, the 1992 video game [0]. I find it remarkably ingenious, and it certainly felt incredible at the time. [0] https://github.com/s-macke/VoxelSpace https://github.com/s-macke/VoxelSpace

speed_spread 4y ago
I've played countless hours with the A-10 simulator which I believe used the same "voxel" technique.
- atan2 4y ago
  Really? I am not aware of such game. Do you remember the A-10 flight sim you played that used voxelspace?
  - speed_spread 4y ago
    Apologies; I've looked it up and the one I found that most it wasn't voxel based. "Silent Thunder: A-10 Tank Killer II" was a first gen 3D accelerated game, nothing to do with Comanche, which I also remember playing with delight. Memory fades, next thing I'll be conflating Descent with those games...

sedeki 4y ago

What is a good learning path (books, videos, ???) to take in order to understand modern graphics programming? At the level of Vulkan or Metal, say. I have had a bird's eye exposure to shader-based OpenGL but don't feel I have a good intuitive understanding of how the GPU operates.

coldpie 4y ago
Start with Foley & van Dam to lay the groundwork & terms of art, then grab whatever API tutorial you like and get started. You'll find plenty of further resources once you're more familiar with the field and start discovering your interests. Graphics programming is a seriously deep discipline and will take years of study to start doing real work in. But it's a super cool field with plenty of work on both the research & practical implementation sides.
newsclues 4y ago
Graphics Programming Black Book by Michael Abrash 1997
- bombcar 4y ago
  I recommend this even though it's now 20+ years old, it's accessible enough that you can get a foothold. Alternatively, get the Black Books for Wolfenstein and Doom, and read them first.
i_like_apis 4y ago
Include: Ericson, Real-Time Collision Detection https://www.goodreads.com/book/show/620505.Real_Time_Collision_Detection https://www.goodreads.com/book/show/620505.Real_Time_Collisi...
dceddia 4y ago
This tutorial is well regarded for learning the ins and outs of modern OpenGL including how the GPU pipeline works, which I think translates pretty well to Vulkan or Metal (at least the concepts anyway) https://learnopengl.com/ https://learnopengl.com/

ddeville 4y ago

Carmack himself describes it well in the recent interview with Lex Fridman https://youtu.be/I845O57ZSy4?t=8961 https://youtu.be/I845O57ZSy4?t=8961

0xAFFFF 4y ago

I you guys are interested in how Doom was implemented, I cannot recommend enough Fabien Sanglard's book, Game Engine Black Book: Doom. https://fabiensanglard.net/gebbdoom/ https://fabiensanglard.net/gebbdoom/

teaearlgraycold 4y ago
Also the first one on Wolfenstein

random314 4y ago

Yet another Carmack worship story. He is a great engineer, but let's not overhype this. It started with the legendary square root function. Which lost its legendary status once it turned out Carmack wasn't the author. Now it is about standard BSP technique from Computer graphics text books from that era. There is also hype about Carmack solving AGI by 2030, when he is yet to publish a single widely cited AI paper. EDIT: I am guilty of reading the first couple of paragraphs and assuming this was Carmack worship. My bad! Leaving the original comment, mostly as is.

smoldesu 4y ago
FWIW, the inverse square root function wasn't popularized by Carmack. Most people shared it because they were amused by the confused comments surrounding it, and how it demonstrated an extremely vertical slice of optimization. Treating anyone like a rockstar is a bad idea, but Carmacks and Wozniaks deserve the praise more than the Zuckerbergs and Jobs' out there.
royjacobs 4y ago
Let's not underhype it, either: It seems you are underestimating the impact that Doom had on PC gaming when it came out. Using BSP trees to perform zero overdraw rendering definitely was not something that had been done before on consumer level hardware and it can definitely be argued that applying them this way for Doom was a stroke of genius.
- coliveira 4y ago
  You're setting the bar for "genius" too low, which unfortunately is commonplace in computer programming. If you take something that already exists and apply it to your code I don't call it genius. Hi quality programming, yes, but genius no.
  - royjacobs 4y ago
    I didn't realise I was not allowed to set my own bars, though :)
  - 4y ago

sebstefan 4y ago

> The really neat thing about a BSP tree, which Fuchs, Kedem, and Naylor stress several times, is that it only has to be constructed once. This is somewhat surprising, but the same BSP tree can be used to render a scene no matter where the camera viewpoint is. The BSP tree remains valid as long as the polygons in the scene don’t move. This is why the BSP tree is so useful for real-time rendering—all the hard work that goes into constructing the tree can be done beforehand rather than during rendering. I can't visualize why it's true

bombcar 4y ago
https://developer.valvesoftware.com/wiki/BSP https://developer.valvesoftware.com/wiki/BSP may help - the key is you have divided it into convex spaces.
deleted 4y ago
[deleted]
whatshisface 4y ago
Here's my explanation of BSP trees, written as much for my own benefit as anybody else's (maybe it will help you): To start off with, we have a basic geometric fact: if you have a surface that divides space into separate regions (this can be a closed surface like a sphere, or an infinite surface like a plane), a line of sight can't cross between the two partitions of space without passing through the surface. If the surface is convex, a line of sight can only cross it once. (That's one definition of convexity.) Now, suppose that you have a lot of objects, and none of them are on both sides of the boundary. You can ensure that condition by splitting any object that crosses the boundary in two. No matter where the line of sight begins, and no matter what direction it moves in, the boundary then offers a definite, albeit partial ordering of events: objects on the same side of the boundary may intersect, then the line will intersect the boundary, then the objects on the other side may intersect. If you find an intersection with an opaque object on the same side of the boundary, you never need to check any objects on the other side, because the order of events above. That is a big benefit when about half of the objects in front of you are on your side of the boundary: if you are right in front of the boundary, or if there's nothing on the other side of it, it doesn't help a lot. Checking all of the objects on one side of the boundary is the same kind of problem as checking all the objects, and that means you can speed those up too by having sub-boundaries for the sub-problems. That gives you the recursion and makes it a tree. If the reasoning based on boundaries continues until there is only one object in a sub-problem, you don't need to sort lists based on distance - meaning that the whole ordering problem can be solved just with partition trees. Choosing a good tree is a difficult problem because, unlike the fact that the ordering problem can always be solved, the amount that an individual boundary division helps depends on where you and the objects are in relation to it. Planes are generally used instead of other things like spheres because splitting a polygon along the edge of a sphere doesn't result in another polygon, while splitting it along a plane does.

yojo 4y ago

For people not reading the whole thing (reasonable, it is long): the author comes to the conclusion that it was not so “genius” after all, given the prior art, and that he read it in a computer graphics book. He still gives Carmack props for doing his homework and getting a working implementation built in a novel game engine.

dmbaggett 4y ago

Amazingly brilliant work, especially given the CPU capabilities at the time. Carmack's use of BSP trees inspired my own work on the Crash Bandicoot renderer. I was also really intrigued by Seth Teller's Ph.D. thesis on Precomputed Visibility Sets though I knew that would never run on home console hardware. None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. But at the time (mid 90s) it was arguably the key problem 3D game developers needed to solve. (The other was camera control; for Crash Andy Gavin did that.) A key insight is that sorting polygons correctly is inherently O(N^2), not O(N lg N) as most would initially assume. This is because polygon overlap is not a transitive property (A in front of B and B in front of C does NOT imply A in front of C, due to cyclic overlap.) This means you can't use O(N lg N) sorting, which in turn means sorting 1000 polygons requires a million comparisons -- infeasible for hardware at the time. This is why many games from that era (3DO, PS1, etc) suffer from polygons that flicker back and forth, in front of and behind each other: most games used bucket sorting, which is O(N) but only approximate, and not stable frame to frame. The handful of games that did something more clever to enable correct polygon sorting (Doom, Crash and I'm sure a few others) looked much better as a result. Finally, just to screw with other developers, I generated a giant file of random data to fill up the Crash 1 CD and labeled it "bsptree.dat". I feel a bit guilty about that given that everyone has to download it when installing the game from the internet, even though it is completely useless to the game.

jetbalsa 4y ago
Great comment! That poor poor bsptree.dat will forever live on. I wonder if anyone really sat down and tried to bash their head against bsptree.dat
chrisseaton 4y ago
> None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. You can’t mean that all the polygons in a game world are now sent to the GPU, entirely relying on viewport culling and Z buffer to remove the ones out of view? I’m not an expert but I’m sure that’s not true - doesn’t Source and latest iD Tech use BSP right now for example?

NayamAmarshe 4y ago

Doom is truly an amazing showcase of engineering achievements and going the extra mile for optimizations. Games these days just depend on raw hardware and optimization takes a back seat. Games like Plague Tale Requiem, while look fantastic, are equally bad at the engineering part. How is an RTX 3080 the minimum recommended spec for 1080@60fps, is beyond me. Sadly, people these days do not care about software optimization and those who do are bombarded with comments like "Get better hardware".

HellDunkel 4y ago
The truely great games do. I am sure the developers of BOTW were very serious about optimization and you can actually feel that playing the game (on switch). It’s a masterpiece just like doom.
- hbn 4y ago
  BotW performs well enough, but there's some areas where things get REALLY choppy. It seems like areas with tall grass are the worst for it, most notably Korok forest in front of the Deku tree where you get the Master sword and talk to Hestu.
  - HellDunkel 4y ago
    Yes, i know that area. Seems as if the designers insisted on that volume light. :) Its not a combat area so its fine.
mhh__ 4y ago
That depends. GTA V ran pretty well on the 360 which was pretty awful hardware even a decade ago.
- NayamAmarshe 4y ago
  Yeah, there are a few companies who focus on optimization a lot. Rockstar's games are usually well optimized. Also Sony's recent offerings as well. Maybe even throw FPS games in the mix, Call Of Duty, Battlefield all look amazing and do not require super high-end hardware.

samlittlewood 4y ago

Quite a few games (eg: Starfox) in the 90's would use BSP in a slightly different way - purely within each object. The tree would be generated offline (mechanically or by hand), and would often be some sort of branching bytecode (test this, draw that etc.) It was very useful to be able to use one plane test to discard a whole bunch of geometry, eg: a surface plus its detail, or everything visible through a window. This still left the problem of sorting between objects - mostly a depth sort was just fine. Special cases like weapons on hardpoints, or vehicles in hangars could be handled by having some sort of 'call submodel' for spaces within the parent model. Beyond that, just dial up the hostile firepower until players stop complaining about rendering artefacts.

pkilgore 4y ago

Also discussed / covered in https://news.ycombinator.com/item?id=21906051 https://news.ycombinator.com/item?id=21906051

j7ake 4y ago

Brilliant synthesis of the problem and why it was difficult. My feeling is that Carmack is really good at speeding up important parts of video game performance to achieve qualitatively different gaming experience. Sometimes I wonder if Carmack was born 30 years later, when computing resources make such advances less needed, he would still be as successful? Perhaps he would go on to improve performance of other problems eg virtual reality and deep learning…..

emiliobumachar 4y ago
AFAIK he did successfully improve performance in VR as part of his work in this space. He's still working currently, mostly on AGI research. https://en.wikipedia.org/wiki/John_Carmack https://en.wikipedia.org/wiki/John_Carmack Of course being famous does open doors, but there's no reason to doubt he'd break into VR in the counterfactual. He did break into game development in reality after all.
emiliobumachar 4y ago
"computing resources make such advances less needed" That's arguable. Someone has to improve the graphics engines at Unity and Unreal, with enormous reach. There's a big potential market in porting what only runs in dedicated VR headsets and expensive gaming computers and consoles to cheaper phone-in-a-helmet VR headsets and notebook computers. Then to cheap phones and netbooks.

diskzero 4y ago

I implimented a BSP renderer in my somewhat unremarkable CDROM game Dark Fiber [1] in 1995 or so. I also remember seeing the algorithm in Foley and Van Dam, but it wasn't until a conversation with John at some conference/tradeshow that I went for doing the engine using BSP. It was a lot of fun figuring out how to optimize the algorithm and I also spent a lot of time using Mathematica figuring out the equations. Well, that was at least my excuse for buying a fairly expensive piece of software as a small gaming startup. https://archive.org/details/DarkFiberWindowsMac https://archive.org/details/DarkFiberWindowsMac

bigmattystyles 4y ago

I thought this was going to be about all the small hallways in Doom where you have to close one door before opening another - this was done so that the engine would never have to render more space than 1 room at a time. I don't know if that's true, just something I've often heard repeated.

tboughen 4y ago
I played Doom, Doom 2 and Final Doom all the way through about 20 years ago - I can’t recall a single instance of this kind of level design. Doors stayed open once opened. Maybe it was done with corners/sight lines instead? To be honest I remember some vast areas rendered, especially when accessing secrets.
- jonny_eh 4y ago
  Doors definitely auto-closed behind you.

jamestimmins 4y ago

One thing confuses me about this: does it require a separate tree per-axis?

gary_0 4y ago
It doesn't split by axis, it splits by planes that can be oriented however. Planes split a space into 2 half-spaces, hence the "binary" part. Only the older Wolfenstein-style rendering cared about the axis.
- jamestimmins 4y ago
  That makes sense if I think about everything existing on a single axis (objects in front of each other on the z-axis). But if you then turn 90 degrees, then suddenly a bunch of those z-axis items are side by side, and order is based on the x-axis of my original perspective. So I don't understand how a binary structure accounts for that perspective shift. Edit: For clarification, my understanding is that there's a single tree built per-level in advance. If I'm mistaken and it's re-building the tree 30 times per second, the lack of axis concerns makes sense, but the article seemed to indicate that that's computationally prohibitive.
  - gary_0 4y ago
    The tree is built once. The tree can be traversed from any point in the world because each node stores which plane it used to split, and it is easy to compute which side of the plane you are viewing. Have you tried reading https://en.wikipedia.org/wiki/Binary_space_partitioning https://en.wikipedia.org/wiki/Binary_space_partitioning ? It shows how a BSP is built and traversed for rendering.
    - jamestimmins 4y ago
      Interesting. Thanks for sharing. I think i need to dig into that article to try to understand this better.

_whiteCaps_ 4y ago

Wow, this brings back memories... I took a 3D computer graphics course in university in the early 2000s, and the final project was to make a game. IIRC we could use as many open source libraries + assets as we wanted, but we had to write the renderer. Our professor was a big Buffy the Vampire Slayer fan, so we made a Buffy game. My team thought we'd have some easy points for that. When we presented our plan, he says "I know you know I'm a Buffy fan, so this better be good"... Ooops. Time to get to work. We used the Quake map format, which is BSP, and our renderer worked pretty well. We used Quake 2 character models, which worked pretty well on its own. I think it was because someone had made some vampire models for it. When we integrated the two, the performance was terrible. Like a slideshow. After a brief panic, we realized that the Z axis was inverted between the two modules we'd written, and the guy that put them together was inverting the model every frame. After inverting it once when the model was loaded, they worked pretty well together. We added a simple hitbox (a rectangular prism at the maximum points of the model), and had a fun little game after that!

kazinator 4y ago

It seems that a challenge in BSP is going to be artifacts, when a surface, particularly a textured one, is chopped into pieces by several planes. If this is not done very carefully, the cuts might show, due to edge artifacts caused by the separate scan conversion of the fragments. Certain shading tricks like Phong may be difficult to apply in such a way that the result looks as if the original undivided polygon had been rendered.

HellDunkel 4y ago

The beauty of the BSP tree is that it used recursion. When first approached this is a challenge to wrap your head around- very similar to the quicksort algorithm. Great read. These days octtrees more or less replaced BSP trees i guess. They are easier to handle and work better with more polygons.

choeger 4y ago

What I don't understand is, how the tree can be used even after movement? How do you know which polygon is behind the other if camera position and angle are freely chosen?

cityofdelusion 4y ago
When the tree is traversed, you make a decision on which subtree to render depending on the camera viewpoint. This is covered in the article right before all the pictures of the trees.

Waterluvian 4y ago

I think the “sit and read research papers” part is often omitted, to our own peril, from the romanticized image of the genius computer hacker of that era.

georgeburdell 4y ago

I’m surprised by the claim Doom was the first game to use BSP. I remember in the late 90s casually browsing the internet and coming across a demo of BSP and incorporated it into my own amateurish game projects

amelius 4y ago

Nice, but it only works for static environments which is a bit unsatisfactory.

Newtonip 4y ago

I highly recommend the "Masters of Doom" book mentioned in the article. It gives a lot of insight in what motivated and inspired the people of iD as well as provides some technical details of how they accomplished things. It's a very easy read.

hbn 4y ago
I just finished it last night. It's certainly a fun read but I felt a little underwhelmed in the technical aspect of things. I don't think the author is a programmer so I can't really blame him. I recall the book describing DirectX as a programming language at one point.

voidfunc 4y ago

My first introduction to bsp was qeradiant while making q3a and later sof2 maps. There used to be a bsp compilation stage that I recall. At the time I had no idea what it meant.

deleted 4y ago

[deleted]

anonymousDan 4y ago

Bizarre how Carmack is idolized as being some sort of genius for reading a few research papers and applying an existing technique. What about the academic who actually invented the technique!

yrgulation 4y ago

> but this episode with the academic papers and the binary space partitioning is the justification I think of first. Subtly amusing considering carmack is not on favour of academia. But everything he uses is made possible by it.

rurban 4y ago

BSP's were first used in Quake, not Doom. Doom was not 3D, just 2.5D. Full BSP's as used in common VR's applications those times were not needed then. The Doom precomputed z-buffer hack is described in this article, but I wouldn't call it genius. The Quake BSP was much better, but neither genius as a lot of people used it before to their advantage. It was a common technique, just not in games. Even we used it in our VR application years before Quake.

HelloNurse 4y ago
Doom has 2D BSP trees, it's the same technique in any number of dimensions.