How Quake Failed their way to Success

Breakthroughs aren't created in a vacuum. Let's dig into Quake's technical failures and missteps, in order to better understand their ultimate success.

Follow me on:

In this video, we explore some of the history behind Quake's ground-breaking rendering technology. The developers explored a myriad of options, which ended up being dead-ends or non-starters, but laid the framework for what would eventually be their breakthrough.

Reference:

Links:

[simondev]

Patrons can now vote for the next video! Thank you for your support.

[joebonar]

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.

[AndersCandell]

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.

[khrob]

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.

[SebastianWeinberg]

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.

[matthewtymaja]

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!

[OudinAlex]

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

[oisyn-]

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.

[georgemathieson]

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

[Ylyrra]

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.

[ollllj]

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.

[zyxzevn]

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.

[mickduprez]

I've always had just a basic grasp of BSP trees but the deep intuition just wasn't there....until now! I think this proves (to me at least) that I'm a visual learner and I'll be watching this one at least a few more times :)
All of your vid's and your courses are very well done, the visuals with explanations and practical examples in layman's/more simple terms are awesome, a great help.
I'm mainly a CAD dev and I've already used the info from the spatial hash grid video in one project to great effect, I think BSP's will also help now I understand them better.
Thank you!

[SianaGearz]

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

[FlareGunDebate]

I've been studying navmeshes, polygonal decomp, kd-trees, and bsp-trees lately. I hit the deep end of graph theory and just backed up recently. This video was relaxing.

[damienlmoore]

Well put together production (using JS?) and nice explanation as always. Thanks!

[kerrykreiter]

This was a great way to pay tribute to the games that started a whole genre. Your explanations of concepts difficult to me were super insightful. But, your graphics were phenomenal! Thank you so much for the research and passion that went into the making of this video!

[Skeffles]

Great explanation of BSPs! I used to make Source maps so I had a rough idea of how some of this worked but your visualisations helped fill in the blanks.

[Roxor]

That subdividing ray-casting approach was used in a number of demoscene productions that did real-time ray-tracing (Heaven7 by Exceed, from 2000 being a good one). I once found a little interactive program that could let you limit it to just the horizontal and vertical edges of the subdivisions, so you could get an idea of what it was actually doing, too.

[TrunkMonkey]

Carmack originally saw Ultima Underworld Stygian Abyss at a trade show which inspired him to create Wolfenstein. Stygian Abyss uses an octree to render on a 386.