How Quake Failed their way to Success

Patrons can now vote for the next video! Thank you for your support. Patreon: www.patreon.com/simondevyt Courses: simondev.io/

I bought Abrash "Zen of Graphics Programming", and spent an intensive couple of weeks of a summer in the 90's learning graphics programming on the PC from it. Starting from the bare bottom with selecting video modes, going though lines, polys, phong shading, texture shading until I got a small world I could move around in. I only ate like noodles or pasta with ketchup, barely showered, and I was in too much overdrive to be able turn off so my sleep schedule was just half and hour there, half han hour there. I still remember it as being one of the best episodes in my life.

The most important aspect of this solution is that it moves a huge chunk of the visibility calculations from runtime to compile time.  By working out in advance which parts of the space could theoretically be visible from which other parts, they could then, at runtime, cull everything else at very little cost (a lookup, instead of a calculation), and only had to "manually" check a much smaller space.  And by checking the known portals first, they could potentially shrink this set even further, before finally devolving to a more time-consuming, detailed process for rendering the remainder.

Running vis on your maps, while faster than light, still took FOREVER on a 75 mhz machine. A couple years ago I made a quake map for old times sakes, ran a modern nodebuilder with some updated vis and a gl enable light, threw just a simple map together, some big open spaces, some lights of varying strength, some water, y'know, a basic mess around map, and I was disgusted with how absurdly fast the map compiled. I just remember working on a map and clicking the test button on Quark, but not hitting the "skip light" compile option so I could just get into the map for testing, and so I'd just go turn on the TV, pop a bag of popcorn, and watch a show. If it was in the middle of a block, come back and vis had just ended, and it had just started light processing between shows, so you decide whether you want to watch another show and take a break or if you'd just stay at the computer and watch it slowly compile lighting.

I bought The Black Book with my first pay from my first job out of high school. Re-read it so many times trying to figure out these concepts. The one that really stuck with me was the span-based rasteriser that is the next step in the renderer. Thanks for (another) brilliant video.

just realised this is the only channel I have notifications turned on for - that says something

Source engines still do BSP+VIS+RAD, mostly for better backwards compatibility. GoldSrc-BSP (1998) is derived from quake1-bsp. source-BSP (2004) is closer to quake2-bsp.

Your animations help a lot understanding all these concepts, they are so clear. Perfect!

John Carmack is a total genius. The comparison with House is probably apt 😅

That might be the best explanation of BSPs I've ever seen. And the final culling technique was a great example of "it doesn't need to be great, it only has to be 'good enough'". When you're talking about doing 10x extra work, even a scrappy "incomplete" solution gives you huge wins as long as it's not giving false positives, so if it's simple and fast it may remove the need for anything better. And the principle that "anything you can cache you can probably precache" is always a good one to try on for size. Doesn't always apply, but when it does the results are like you're doing magic.

I regret not developing that 3D graphics engine I made in 1996. It ran texture mapped, shaded polygons, and allowed fullscreen graphics at 640x480 at 16fps minimum (with a scene / screen filled with texture mapped triangles). The best part was that this was on a 486 DX4-100, and it did allow rotation in all 3 axes! Those were the days!

That was probably the most intuitive, well-written explanation of what BSP trees are and how they function. The visuals were an awesome addition 💯. Thanks Simon! Appreciate ya.

I worked on Beam trees in university, but did not know that they were called that. I needed to calculate Constructive Solid Geometry defined by surface-equations that were combined in logical composition (AND/OR/NOT). The equations would vary. I would have loved to have polygons instead, but the project manager was stuck on the equations. I started with the camera beam, then sub-dividing it into 4 each time. The beams turned the logical composition into 1 dimension, with some overlapping. So with each beam, I could perform calculations that removed a part of the equations. Until a few were left, and I could perform ray-trace calculations. The same was done for calculating shadows. In a later job I made one that generated polygons from slightly similar structures. And that worked much faster. Now these things are already integrated in Blender and such.

Matt's Ramblings has done an excellent deep dive on everything Quake rendering.

Great video!! but as far as I recall, the engine used in the game Descent, released 1 or 2 years prior, also employed a portal system to determine visibility across different areas. I'm not sure if it was implemented in the same way, but the concept of portals wasn't a 100% innovation of Quake.

Nobody has explained BSPs to me in a way I understand until now

Another great video, Simon! This subject is very close to my heart, as I have been specializing in visibility determination pretty much since I started my gamedev career in 2004, and indeed by learning from games like Quake in my early days of tinkering with stuff. I've worked on most of the Tomb Raider games from Crystal Dynamics since that time (mostly the Tomb Raider series, and Marvel: Avengers was my last game before we got acquired by Playstation Studios), including a couple of Eidos Montreal ones (Deus Ex: HR). Of course, this was all GPU rendering, so we were mostly bothered by quickly being able to cull large chunks of geometry. They wanted a cell and portal system where they would hand-author cells and portals into the world geometry and I singlehandedly implemented most of it (which is pretty wild for a junior if I think back about it). The first iteration was pretty basic, where cells could be concave polytopes and portals convex polygons. You generate a BSP tree mainly for point location so you can assign in-game objects to cells, and then use the portals to cut up the view frustum as you traversed the portals, testing all objects and lights against the cut up frustum. Then we did a pass for each visible shadowcasting light to figure out which objects to render to the light's shadowmap. This firstly got shipped in the PC port of Tomb Raider: Legend as it featured the new per pixel lighting engine, that wasn't in any of the console versions (we're talking original Xbox and PS2 here). During development of Deus Ex: Human Revolution we played around with the ability to have occluders. To implement this, I used the beam tree approach as well, by calculating the entire visible volume using the portals and occluders, for the camera as well as the dynamic shadowcasting lights. The beamtree is essentially a bsp tree for visible space, and to test for visibility you simply push the bounding volume of whatever object you want to test through the tree to see if it hits any visible leafs. This system has been used all the way up to Marvel: Avengers (2020). Of course lots of optimizations and minor features were added throughout the years, but the fundamental idea stayed the same.

Comparing your phone to our old 90s pcs, I wonder if that gives young people the impression that we suffered under our old PCs, But in fact they were mind-blowing for us at the time. I suppose its like comparing a modern cutting edge gaming pc to one from 2045. What we have now will also seem shockingly weak. Its also funny to remember how my friends and I would make multiple trips back and forth carrying our pcs so we could LAN. But now I carry a tiny remote control sized device in my pocket that can play all those games and its orders of magnitude more powerful. It would be amazing to take one back in time and show everyone, Not that you'd have any way of charging it once it ran out of power.

High Quality as always. :D

oh man, im 6 minutes in now, for me (born in late 99) this processing comparison between your phone and that pentium 75 was already worth watching this video