BSP Trees: The Magic Behind Collision Detection in Quake

An explanation of how Quake, and other games like it, use this revolutionary data structure to stop the player from walking through walls and falling through the ground.
Music Credits:
----
Guiton Sketch by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
----
Pioneers by Audionautix is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Artist: audionautix.com/
----
0:00 Intro
0:33 BSP tree warm-up
3:21 Tracing a line
6:20 Tracing a box
8:05 Outro

[@MattsRamblings]

As I mention in the video, there's a lot more that can be said on this topic! Let me know what you'd like to see in a follow up video, or if there's any other aspects of Quake's tech that you'd like to see explored.

[@NJP-Supremacist]

It would be interesting to see how the buttons players have to push with their bounding box work from this perspective, since they seem to rely on this collision and movement system.

[@trober256]

This sort of visualization but for the PVS compiling step would be most welcome! Fantastic work!

[@MattsRamblings]

@@NJP-Supremacist Each button in the level (and lift, door, platform, etc) actually gets its own (much smaller) BSP tree, and the player's bounding box is traced against the button's tree in the same way as for the full level. That is how the collision aspect works anyway, what happens after a collision is detected is another matter. Perhaps that would be a good video in itself.

[@MattsRamblings]

@@trober256 That's a great idea, I've looked at this a bit before and the PVS algorithm is crazy complicated. If I can find a concise way of explaining it, it would make a neat video.

[@Admer456]

@@NJP-Supremacist Buttons and such, being made out of brushes, can be seen as their own, mini BSP trees, so they indeed rely on this same collision system. Nobody asked me to explain this but I feel it'd be good to know. The Quake engine has some simple "physics" code which handles things like touching, blocking and other physical events. All buttons really do is just gradually change their position between two points, just like doors, elevators and other platforms, and they don't check for any collisions against the level. There is no detection of the player's movement direction either, there's no real pushing going on, it is enough to merely collide once with the button and it'll start moving to its "pressed" position. That being said, they *do* check for collision against moving entities like players & monsters, for the purposes of gibbing if they're in the way, and of course for button activation I described above.

[@voidpunch1324]

Honestly i can hardly wrap my head about BSP Trees but those slick animations really helped me visualize it, great job.

[@TonyToon]

It never ceases to amaze me how well both doom and quake ran on pcs given how much they had to process every tic.

[@halfsourlizard9319]

Approximations, hacks, and offline precomputation (BSPs, LUTs, etc.) ... Cheat when you can; compute when you must.

[@skilz8098]

If you think this is amazing, then you might want to look into how older 8 bit systems such as the NES were able to generate and store their audio tracks. Now that's a feat of engineering with the limited number of channels two pulse waves, one triangle wave, one white noise, and one sample channel. And yet people were able to create well known and memorable themes and scores such as Mario Brothers, Zelda , Final Fantasy, and more... But yet BSP trees back in the day was an excellent source of optimization to pack in and squeeze as much performance that you could get of the systems in that era. Back then they were cautious not only of each and every byte, but also in some cases down to every single bit.

[@halfsourlizard9319]

@@skilz8098 Yep! The vids about building 'Micro Mages' are amazing; really good explanation of minimising storage for tiles/level data. Retro Games Mechanics has some great vids about similar stuff in SMB1 -- and how it relates to the glitch levels.

[@quakespeedrunsexplained]

So cool! Those animations are next-level.

[@MattsRamblings]

Hey, good to see you here, and thank you!

[@AbacusManify]

Great video - as someone who has mapped in Quake for many years, it's surprising how much we take for granted in the BSP system - 'modern' quake maps often produce maps hundreds of times more geometrically complex than what was originally shipped with the game, and the system still holds up (for the most part)! As for another video idea, I'd love to see this series continue with an exploration of some of Quake's other pre-rendered 'tricks' - investigations of how VIS and LIGHT work, especially in the context of BSP, would be really interesting.

[@soylentgreenb]

AFAIK VIS just attaches a potentially vissible set to each BSP leaf node that isn’t solid. If you are anywhere in this node you could potentially see these other leaves; so draw them. How it is computed efficiently I don’t know. RAD computes a sparse matrix of weights; how much diffusely scattered light hitting LUXEL a reaches LUXEL b accounting for surface normal. If the leaf LUXEL a is in does not have LUXEL b’s leaf node in its PVIS that coefficient is zero; otherwise it might be something. When calculated it is trivial to calculate multiple light bounces and let the light diffuse through the level. The starting light is skylight + whatever is given off by emissive textures according to lights.rad. After 1 pass you have direct light. After two passes you have a good balance between direct and indirect lighting that still looks a bit stark and grungy. More passes and it can get a bit too bland and mellow. Due to not having HDR and tone mapping having many light bounces looks off.

[@yiannos3009]

Great video. Spent much of my teens dissecting the black book of graphics programming and Quake's code -- it's great to see some of it distilled here so eloquently. Thank you.

[@ProXicT]

Wow, this must have taken quite some work to put together and you've executed it perfectly. Very well explained and visualized, thanks!

[@MattsRamblings]

Thank you for the kind words and super!

[@Calinou]

Great explanation! The collision hull for ogres is also used for large monsters like Shamblers, which sometimes creates situations where certain monsters that should logically be able to walk below a low ceiling never attempt to do so.

[@Gorialis]

These visualizations brilliantly describe this system. I now have a lot more appreciation for how ingenious Quake really was.

[@satarimar]

one small detail: the sweep test boils down to doing a raycast against a minkowski sum (not difference) - minkowski difference is used to test overlap but that requires absolute transforms for both tested convex objects. in the case of quake, convex brushes are inflated according to the hull AABB extent (plus beveled through brush edges and AABB planes), then CSG is performed and then final collision BSP is computed

[@LordFers]

Hey @satarimar do you know if there is any historical reference to where its known that they used Minkowski? Or what paper they used on Quake 1 and next what change on Q2 and 3. Ty.

[@Admer456]

Absolutely lovely! People I often interact with think of Quake BSP as a visibility thing, or a thing that has leaks, or the thing when cylinders cut up the floor & ceiling into lots of triangles, but there's so, so much more to it.

[@NinjaRunningWild]

Well, its main motivation was rendering, but there’s a lot of techniques in game programming it applies to or is useful for.

[@Admer456]

@@NinjaRunningWild Yeah, pretty much. When I started mapping for CS 1.6 in 2014, I thought of BSP as just brushes, and later I knew it as "the thing with leaks, VIS portals and cutting up surfaces", and around 2017 I realised it's also used for collision. In 2018 I got into programming and as I was exploring Half-Life SDK (and later Quake 3 code), I found out quite a few more use cases for BSP trees: audio occlusion, contents at a given point, NPC pathfinding using a BSP tree (Quake 3's bot AI). There's a quirky little engine behind Thief and System Shock 2, Dark Engine, which seems to use BSP to determine how to play ambient sounds. Each room would have its own ambient sound which would change as you stepped through portal boundaries. Sounds would get quieter and change the direction they're coming from, depending on which portal boundaries they were crossing. Unreal used BSP extensively with its concept of "zones". You'd put an invisible polygon somewhere to make a split, and a point on one of the sides. Depending on where you placed that point, that whole volume would become a zone. And then it's up to you to define what that zone is, whether it's water, or a fog volume or something else. Now that I think of it, this is basically Quake's point contents with extra info. So really, it basically boils down to "can I describe this concept as the property of a volume between some planes?" Sometimes it's the planes that matter, other times the volume itself, and other times the properties, or a combination of all 3. Very fun stuff.

[@nonhunt]

Best explanation of BSP I ever seen! Quake games never cease to amaze me with all the tricks used.

[@porglezomp7235]

It's maybe too niche of a topic, but I'd be very interested in hearing about the numerical stability issues involved in constructing and then using BSPs.

[@MattsRamblings]

One issue with my version of the trace function as presented is that due to floating point error, you may end up inside a solid after the trace. In the best case the player would be freed by a catch-all "unstick player" function, but worst case they get stuck. To avoid this the real function attempts to back the player off a small distance so that they're less than 1/32 units away from the collision plane, which is one of the reasons the real function is much longer. Even this isn't perfect though and you will occasionally get stuck to a moving platform, or incur damage. I'm sure there are other numerical issues to contend with particularly during construction, but I don't know specifics.

[@noodlesfan8536]

constructing the bsp could lead to a division by zero if you miss an if because the parallel planes property other than that i dunno.

[@halfsourlizard9319]

Computing the BSP would be an interesting follow-up ... I'd be keen to see how the computational-complexity vs precision trade-off was managed ... what sort of hacks ended up being used to make it tractable ... and how level design had to be constrained to avoid pathological cases.

[@pieterverhoeven1642]

Geometry vertices have to be calculated from plane intersections, and yes, that implies roundoff errors everywhere, iirc qmap simply uses an absolute epsilon to quantize nearby vertices and it works surprisingly “well enough” - I believe one quake unit is one texel square using default texture scaling. I’m not sure modern qmap implementations do something more clever, since the custom maps of today are a far cry of the original maps, so more room for errors to creep in.

[@ArneChristianRosenfeldt]

I think when you start with geometry defined by bytes ( per axis ) on a 64 bit CPU ( inside N64 for example) you can do all calculations using integers. Inner product. Cross product. Volume. And some more stuff which need the 4th byte ( or was it 5th )?

[@MrChromed]

Fun fact: the entire Halo saga has been using BSP as main structure for ages. From Halo 1 to Infinite, each game has been using something we call "scenario_structure_bsp", which has received some modifications and tweaks over the time but the main conception is still there.

[@purityspiral662]

It's great to see a visual example of what BSP splitting looks like using 3D volumes instead of just 2D areas

[@zyad48]

7:56 Holy shit that's brilliant. I knew the minds over at id Software were smart, wizards even, but seeing that right there just blew me away, that's such an awesome way to dramatically speed up collision detection on the specs of the time. Absolutely wild.

[@DavidStrife7]

That was insane, and I have a newfound appreciation for Carmack. When you read about their story in "Masters of Doom", it's crazy to think they were just kind of winging it on diet coke, pizza, and whatever innovations Carmack came up with that month, or even week! Crazy times. Legends. Thank you for visualising BSP in those intricate animations too. Really helped me grasp a basic understanding.

[@france976]

20 years i ve waited for this video

[@empty5013]

I checked your channel and realised you're the guy who made the technical breakdowns on strafejumping years ago! Those videos were eye opening to me back then, made me way better at q/goldsrc/source movement, and started me thinking about character control in FPS shooters on a more technical level too! So glad to see you're still making great content like that! That video and these games have been a huge inspiration for my own work in game dev, I'm always striving to get movement that feels as good as quake in other engines (I mainly use unity) and I've struggled for years. I think this video is another critical puzzle piece for getting there. Thanks again :)

[@Bunny99s]

Yes, Quake had and still has the best movement. Also the way the network snapshots work is also fascinating. Since all movement has an acceleration / ramp up time, the server will actually backtrack and correct your movement based on the latency it took to get the new input state from the client to the server. You get a feeling for this when you play Q3 with a low timescale

[@coyo_t]

An indepth video on minkowski differences (how theyre calculated, and unrelated to quake, how they work for other shapes) would be neato

[@GlennBroadway]

I once watched John Carmack describe this at a conference (something like GDC). I’ve never seen the video again, but I remember that his explanation was excellent.

[@0xGRIDRUNR]

is there literally any part of quake that isnt a programming marvel? these guys were insane at making every little thing its own masterpiece

[@Mkemcz]

Having separate BSP trees for player-sized and ogre-sized bounding boxes is a very clever idea. Really solves the problem efficiently for the hardware available at the time.

[@JathraDH]

Its amazing how much game programming boils down to the simple dot product ie: backface culling check. You can do SOOO much with it its insane.

[@paulbunyangonewild7596]

So beautiful to see how neat and tidy this system is.

[@birdrun4246]

That bsp animation was incredible.

[@vittorioromeo1]

Excellent video, loved it! Would love to see a follow-up. I'd be really interested in knowing what more modern engines today use instead of BSP trees, and why. Would also love to know if there's a way to get around the limitation of the three Minkowski Difference hulls -- it was a pain while developing Quake VR!

[@user-sl6gn1ss8p]

I think you could have as many as you want, so long as they have fixed sizes. Like, in principle, not on the quake engine, that I wouldn't know how to go about. (as a side note, when compiling maps you can omit hull sizes, so like for CS you might omit hull size 2 which is not used)

[@user-sl6gn1ss8p]

also, I guess you could maybe interpolate between Minkowski Difference hulls? Not sure whether that would make sense in practice

[@porglezomp7235]

(Basing on my answer to one of the comments above) More modern systems tend to directly do individual swept shape-to-shape collisions instead of doing point-vs-hull sweeps, the same way Quake does collisions against dynamic entities. In order to avoid having to do N^2 work checking every shape against every other shape, they use broad-phase structures to only check shapes against ones that are nearby and thus might be colliding. There are multiple of these structures that get used (like octrees, grids, spatial hashing) but a very common one is BVHs: "Bounding Volume Hierarchies". These are also trees, but they're trees defined by collections of shapes that contain other shapes (usually boxes containing boxes as well as the leaf colliders), rather than being a tree defined by planes. You can imagine that every cluster of objects is contained inside a box, and every cluster of those boxes is contained inside a larger box, etc. This is less fine-grained than a BVH, but it has the advantage that you can build a sloppy tree that is still reasonably efficient and it's much easier to dynamically update that tree when things move around. For geometry like a Quake level, nowadays I would probably generate convex colliders out of all of the brushes at map compilation time, and then just use all of those convex hulls as static geometry in a modern collision engine that works as described above.

[@GokkePep]

@@porglezomp7235 Do you mean BSP here instead of BVH: "This is less fine-grained than a BVH"? And since you seem to know what you are talking about, do you know of more resources like this video that explains this in a relatively simple manner?

[@porglezomp7235]

@@GokkePep Thanks, I did mean BSP there. I don't have specific videos in mind, but I can point to some resources and you can find videos on them. For collision, I learned years ago from "N tutorial A" and "N tutorial B" which introduce the Separating Axis Theorem and broad-phase collision. You'll need a flash emulator for the interactive parts on that nowadays. For narrow phase collision, you'll want to look into the "GJK algorithm" (I know there are a number of good videos but I don't remember which ones to recommend). For broad phase collision: The N tutorials introduce a collision grid, searching for "broad phase collision" on youtube finds a number of results, you'll want to find stuff about BVH and about quadtrees.

[@Tenetri]

I grew up playing Quake, these videos are super nostalgic for me. Thanks so much for taking the time on such a interesting topic! Great Video!

[@trober256]

The visualizations here are next level, thank you for the detailed work!

[@MSimp2k6]

I had no idea BSP calculated those extra trees for the minkowski difference. It's a bit of a kludge, but a clever trade-off! I started making Half-Life maps in ~1998 or so and became well-acquainted with many of the quirks of Quake-based engines (r_speeds be damned), so this series is really cool to see. It boggles my mind how many times Carmack & co. would have hit a stumbling block, only to persist, figure out these clever hacks and get moving again. Imagine you had to do this from scratch in the 1990s with no web to lean on, ancient processors, and the only prior art was closed source military software & some academic papers.

[@johanrg70]

That bsp tree animation must have taken forever to create. Great video, thanks.

[@Quizack]

I do not know how to code, but I do appreciate video games. This video was surprisingly easy to understand considering I have no skills or knowledge in this subject. It really amazes me how much is going on behind the scenes in a video game. It’s essentially just using a whole ton of mathematics to give us the illusion of a cohesive 3D world that follows a set of life-like physics, and every developer has their own little tricks to work out ways of implementing ways to make that world interesting, fun, yet still somehow logical. I suppose that this is a realisation that people who understand the subject have made a long time ago, but it’s an entirely new world for me. Really great video mate. I appreciate the work you did on it. Cheers

[@bamtna]

very cool animations

[@magnetbox_]

This is a great explanation, and the visuals illustrating everything are so polished! Thanks for making it!

[@windup-games]

Amazing! I cannot imagine how much work has gone into this, especially the part where you visualize the splitting planes building the bsp tree. Thank you for your great work. Well explained and very accurate. It's amazing how well games in the old days got away with not having a "numerical stable" physics engine, but just simple yet effective tricks to achieve something feeling that great when playing. I would even go further and say that the reason not real physics were used games felt so good. Nowadays people tend to rely to much on physics of game engines and miss the point of good feeling collision/response mechanics.

[@elimgarak3597]

Best material on the topic so far

[@progman8688]

This video is like 'BSP tree for dummies'. Great video!

[@Tienghan2]

Today was harvest day in the corner of peace very great video, Like, wish you always happy and make more good videos. thank you for sharing

[@Visleaf]

Love your explanatory visuals, very cool

[@SomeRandomPiggo]

Incredibly good video! Especially for a channel of your size. BSP is still a very valuable tool, and I'm surprised it's been almost completely phased out from modern engines for meshes

[@longwelsh]

When they released the Quake source code I poured over it for months. Clever bastards they were. Your visualisations are brilliant and really helped solidify what what’s going on. BSP was absolutely genius.

[@flintbrenick]

These videos are so good! I absolutely love the animation of the first level being broken down. Please keep up to awesome work!

[@abbyslab]

Matt, these are some beautiful illustrations, thank you.

[@PalmliX]

One of the best explanations I've seen!

[@SomeDude0881]

How do you have so few views? I’ve immediately subscribed. You’re one of my new favorite KZbinrs. I hope you get the attention you deserve man. Fantastic explanations and breakdowns of complicated topics.

[@AlleBalle54]

you have a nice way of deconstructing complex topics, well done!

[@loleq2137]

Very well-made, informative video 👍👍 The visuals in particular are out of this world!

[@Biel7318]

what about quake3 / doom3 AAS Adanced Awareaness System?

[@richardallbert]

Outstanding work. Thank you

[@hetias]

Carmack you're a genius

[@transientwaveform1475]

This visualization is incredible!

[@F00d5tamp]

DUDE this is the best visualization on how it works. I didn't know until i came across this video! Thanks!

[@empty5013]

this video is incredible, it explains so succinctly and so carefully a really complicated fundamental part of the quake engine brilliantly. thank you so much for making this, I don't know if it'll ever be useful to me as a game dev since the technique is no longer in vogue, but it's an amazing piece of history you've documented here and the technique is just wonderfully elegant and genius at the same time.

[@randall.chamberlain]

Fantastic summary mate. Thanks

[@appidydafoo]

Fascinating. Wish I had learned about this when I was a child. I spent endless hours figuratively beating my head against a brick wall; using buggy software (THRED) to design maps with no comprehension of this underlying architecture - wondering why they took so long to compile (or why the compiler failed, more likely than not) and why the resulting performance was so dismal. The animations are so well done and the video presentation was very educational. Thank you.

[@kanan348]

The visualisation looks magical.

[@LearningMathPhysicsLive]

I did not expect this to be recursive. Great video.

[@mrgunn3r904]

Very informative video , Thanks for making it.

[@pomino255]

thanks for the great videos as always!

[@bschwand]

beautiful visualizations

[@starc0w]

Awesome explanation! Thank you very much!

[@hl2mukkel]

Your visualizations are absolutely amazing, can you shine some light on what programs or programming language (libraries) you use to create them? Love your videos!

[@MattsRamblings]

Thank you. I use Blender for most of the graphics (2D and 3D), driven by Python scripts.

[@kaleygoode1681]

I wondered what is used instead of BSP Trees... ChatGPT says: While BSP (Binary Space Partitioning) trees were once a popular technique for representing and rendering complex 3D environments in video games, their usage has diminished in recent years. Modern game developers have adopted various alternative approaches and technologies for creating virtual environments. Some of these include: 1. Octrees: Octrees are hierarchical data structures that partition 3D space into smaller octants. They are particularly useful for representing dynamic scenes and efficiently managing collision detection, visibility culling, and LOD (Level of Detail) rendering. 2. Spatial Partitioning Grids: Spatial partitioning grids divide the game world into a grid of cells. Each cell contains a list of objects or entities that occupy that cell. This approach enables efficient spatial queries such as collision detection and visibility determination. 3. Portal Culling: Portal culling techniques involve dividing a game world into interconnected rooms or areas and using portals to determine visibility between them. This approach reduces the amount of geometry that needs to be rendered by excluding areas that are not visible from the current viewpoint. 4. 3D Mesh Hierarchies: Modern game engines often use hierarchical structures, such as bounding volume hierarchies (BVH) or spatial subdivision trees, to organize and optimize the rendering of complex 3D meshes. These structures allow for efficient frustum culling, occlusion culling, and LOD management. 5. Signed Distance Fields (SDFs): Signed Distance Fields represent 3D geometry as a voxel grid where each voxel stores the signed distance to the nearest surface. SDFs are useful for a variety of purposes, including efficient ray marching for ray tracing, dynamic object placement, and procedural generation of complex shapes. 6. Procedural Generation: Rather than relying on predefined structures, game developers are increasingly turning to procedural generation techniques to create game worlds dynamically. By using algorithms and rules, developers can generate terrain, buildings, and other objects on the fly, allowing for more varied and expansive environments. It's important to note that the specific techniques and technologies used by game developers can vary based on factors such as the game genre, target platform, and performance requirements. Additionally, hybrid approaches and custom solutions may be employed depending on the unique needs of each game project.

[@user-og6hl6lv7p]

Octrees are GOAT. They are super easy to implement and you can use simple AABB search queries to find nodes. They also work well with ECS-like data structures as you can simply store index positions of whatever object you need to point to.

[@NinjaRunningWild]

It's the key to a LOT more than just collision detection. All the rendering in id games from the SNES Wolf3D on used it.

[@adamrushford]

nice visuals in the beginning dude

[@sekaita]

great video with wonderful visualisations

[@hoovysimulator2518]

It would be interesting to see how collision detection has been implemented in future games, especially GoldSrc and Source games (as they share some code from Quake, though mainly for movement). And how Unreal does it!

[@klasop]

Love your videos! Very educational and super interesting! Thanks you!

[@ruzgar1372]

That bounding box collision method has to be singlehandedly the weirdest solution to a problem I have seen. I wonder if it's done like that in Half Life 1 too because Gold Source engine is a deritave of the Quake engine.

[@figloalds]

Guys at Id software back then truly are gods of programming The "fast inverse square root" hack is also brilliant af

[@pepe6666]

awesome!! i didn't know that bsp trees were used for more than the map geometry. amazing

[@TheRiptideRaptor]

Wow, I just rewatched your movement tricks video yesterday, wondering when you'd release something new

[@stardustmotion]

this animation/teaching is 50 years ahead of university course

[@HomeOnTheEdge]

THIS IS SO BEAUTIFUL

[@ADR69]

Love these niche videos

Great visuals! I instantly subscribed. You could go to any level of detail in your analysis of this or similar topics and I would be here for it.

[@just__khang]

very nice

[@Jorge-vv8cy]

Thank you. I allways wanted to know how this works.

[@kuklama0706]

In Xash3D you can visualize collision model with r_showhull 1 2 3. It was ported over from some Quake port

[@KillPixelGames]

well done

[@thosethatcan]

As said in FL, that's dope! ty

[@thedanebear]

Wow! This is really impressive. What did you do the animations in? They're really remarkable

[@peterSobieraj]

I like makeing games, and this is helpful. Thank You.

[@Crylar44]

Holy fucking hell, I would never guess that player collision box size and Oger collision box size effected the stored data for a level, awesome, and also what the hell xDD

[@demolish_united_nations]

I prefer BVH over BSP or any other spatial subdivision structures which don’t handle primitive-box interaction very well and end up with plenty primitives in the root node or being split into two or more child nodes.

[@forgottenforever1036]

Lovely!

[@neumi569]

This was very interesting indeed. I would also be interested in how others did it, Jedi Knight for example.

[@ZdrytchX]

Were minkowski differences calculated in Quake 1 on the fly or were they precompiled? In tremulous, the humans can crouch and the alien team can evolve into different classes with different bounding box dimensions. The way I understood it was that it was calculated every frame, but not done beforehand, but now that I think about it, it does kind of make sense when you consider the fact that map mesh can take quite a while to load. On the related note, because the bounding box does not rotate, this caused quite an annoyance with acid tubes in the successor project unvanquished, because the acid tubes were no longer cubes, but cuboids and the developers completely forgot that bounding boxes don't rotate even when the structure is placed on walls. It took me some time to convince them of such a simple fault and they later fixed it.

[@MattsRamblings]

Hello, they're precomputed in Quake 1 but subsequent Quakes used a different system that allowed a greater variety of bbox size, which is why Tremulous (based on Q3 IIRC) had more capable collisions.

[@VoidloniXaarii]

You're so amazing!

[@LordFers]

Are you sure about if is the Minkowski difference used in Quake? Why is it that they never mention this in Michael Abrash's black book? I mean... I understand that Bruce Naylor went to id Software in 1994 to explain to Carmack how to take advantage of BSP Tree for Collision Detection (Doom doesn't use that approach), but I don't know if he explained to him that he could use the Minkowski difference (as what we now know as GJK). It would make me very happy to know where you got the idea that they used Minkowski Difference in Quake, or if it was just an approach you came up with for the video. Thank you so much and great video!

[@willtheoct]

things im trying to do in javascript right now: thanks bro

[@skope2055]

awesome

[@zeez7777]

Very nice video as always. I am very interested in your workflow for creating these animations. What software do you use? I think this would make for a cool video series too. Explaining concepts with these high quality animations is just so valuable for many other domains too.

[@MattsRamblings]

Hey, I use Blender for most of the animations (both 2D and 3D), using lots of Python scripts to set up the scenes.

[@zeez7777]

@@MattsRamblings Thanks!

[@adamrushford]

I learned BSP mapping before anything else, return to castle wolfenstein used quake BSP maps, I modded maps in the beginning, now I try to make games, I have most of the skills but the projects are very large

[@nicolamarchesan4597]

Really thanks for this ultra very well done video. I'm almost 40 now, but when I tried to study this stuff in the 2000s it was very difficult. Can't even believe you can find this kind of videos today, showing the unmatchable brilliance of Carmack. I didn't even know there were more thatn one BPS tree, made just for collision detection. When I was writing my own 3D engine back in 2000s, I had the very same problem, solved by expanding the geometry (an idea I had along with a friend of mine), but the final result was not stable. How could Carmack come up with this idea? thanks!

[@ocamlmail]

Thank you in advance.

[@MattsRamblings]

Thank you too

[@Magicalbat]

Do you know why the popularity has declined in recent years? It is just because they are less necessary with faster computers? Are they worse for cache? Something else? (Also, the animations were amazing).

[@elimgarak3597]

I think it is because computers are faster. Today's way of building a level is just treating it like any other model. You build a model of your level in a tool like Blender, export the obj, load it into a modern engine, and then add a collision box around it.

[@charlieking7600]

Algorithmic complexity is awful. It grows as n² function in memory requirements for visibility bitmasks. Each new polygon on brush wall adds new leaf. You can't make detailed environments without awful performance. And it only slows building the level. Handmade sectors are more efficient. It's much cheaper to check only parent sectors with also manually set portals.

[@SianaGearz]

It works well to describe a set of corridors but doesn't generalise well to an open environment. Physics middleware that found their way into games in mid 2000s (Havok, PhysX) didn't come from gamedev background, but from simulation background, and the most efficient geometries supplied in physics engines are primitives and convex hulls, and it just treats everything vaguely equally and broadpass is used to quickly sift through all objects to see which ones need to be checked for collision.

[@elimgarak3597]

@@charlieking7600 while space complexity is n^2 (because each node MUST have two childs), the time complexity of the tree's traversal is linear. There is a reason why Carmack used it, and Doom's BSPs wouldn't have worked so well on a x486 processor in the early 90' if it wasn't a fast technique.

[@charlieking7600]

@@elimgarak3597 of course. I mean it works well only in low scale, trying to explain why it's not used in modern games.

[@PDivision1]

The animation is amazing! How did you make them? I mean splitting the level in chunks.

[@user-sl6gn1ss8p]

not just quake but half-life and all it's mods too

[@thenderyoshi]

Ooooh so THAT'S why visleafs have that name in the Source Engine!