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 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.
@@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.
@Tungsten_Walls 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.
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.
@@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.
@skilz8098 Don’t forget about the Atari, which had no graphics capabilities to speak of and less than a kilobyte of memory- you’d display graphics by timing to the exact cpu cycle (1 cycle = 3 pixels) when to set the next color
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.
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.
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.
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
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.
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.
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 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.
Looking back at early 3D games, it baffles me that Quake has no out-of-bounds exploit unlike its contemporaries. Probably a sign of how solid the programming of it was.
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.
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.
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.
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 :)
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
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.
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.
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.
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.
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 )?
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.
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.
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!
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)
(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.
@@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?
@@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.
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.
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.
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
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.
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.
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.
How do you have so few views? I’ve immediately subscribed. You’re one of my new favorite RUclipsrs. I hope you get the attention you deserve man. Fantastic explanations and breakdowns of complicated topics.
I’ve always wondered since reading about bsps in the doom era how the dynamic elements of quake (doors, elevators, moving blocks, etc) fit into the game engine of quake.
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
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.
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.
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!
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
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.
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.
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
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.
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.
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.
omg the quake builder looks exactly like source....... boom. ive never really looked at the editor for this game but i did know that source was, more or less, based on it. but wow. identical
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!
![How Quake's software renderer ELIMINATES overdraw [⚠️ flashing images]](http://i.ytimg.com/vi/zdXsHWHxeBY/mqdefault.jpg)
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.
This sort of visualization but for the PVS compiling step would be most welcome! Fantastic work!
@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.
@@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.
@Tungsten_Walls 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.
If their use has declined, like you said at the end of the video, then I'm curious - what's been succeeding them?
Honestly i can hardly wrap my head about BSP Trees but those slick animations really helped me visualize it, great job.
It never ceases to amaze me how well both doom and quake ran on pcs given how much they had to process every tic.
Approximations, hacks, and offline precomputation (BSPs, LUTs, etc.) ... Cheat when you can; compute when you must.
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.
@@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.
@skilz8098 Don’t forget about the Atari, which had no graphics capabilities to speak of and less than a kilobyte of memory- you’d display graphics by timing to the exact cpu cycle (1 cycle = 3 pixels) when to set the next color
So cool! Those animations are next-level.
Hey, good to see you here, and thank you!
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.
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.
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.
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
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.
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.
These visualizations brilliantly describe this system. I now have a lot more appreciation for how ingenious Quake really was.
It's great to see a visual example of what BSP splitting looks like using 3D volumes instead of just 2D areas
Best explanation of BSP I ever seen! Quake games never cease to amaze me with all the tricks used.
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.
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.
Well, its main motivation was rendering, but there’s a lot of techniques in game programming it applies to or is useful for.
@@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.
Wow, this must have taken quite some work to put together and you've executed it perfectly. Very well explained and visualized, thanks!
Thank you for the kind words and super!
Looking back at early 3D games, it baffles me that Quake has no out-of-bounds exploit unlike its contemporaries. Probably a sign of how solid the programming of it was.
Production value for this video is insane. Great job.
So beautiful to see how neat and tidy this system is.
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.
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.
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.
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 :)
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
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!
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.
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.
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.
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.
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.
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 )?
The visualizations here are next level, thank you for the detailed work!
I love seeing these old game dissected, particularly quake because it's the first fps I played.
Best material on the topic so far
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.
An indepth video on minkowski differences (how theyre calculated, and unrelated to quake, how they work for other shapes) would be neato
very cool animations
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.
This is a great explanation, and the visuals illustrating everything are so polished! Thanks for making it!
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!
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)
also, I guess you could maybe interpolate between Minkowski Difference hulls? Not sure whether that would make sense in practice
(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.
@@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?
@@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.
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.
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.
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
is there literally any part of quake that isnt a programming marvel? these guys were insane at making every little thing its own masterpiece
DUDE this is the best visualization on how it works. I didn't know until i came across this video! Thanks!
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.
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.
That bsp animation was incredible.
20 years i ve waited for this video
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.
One of the best explanations I've seen!
The visualisation looks magical.
That bsp tree animation must have taken forever to create. Great video, thanks.
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
How do you have so few views? I’ve immediately subscribed. You’re one of my new favorite RUclipsrs. I hope you get the attention you deserve man. Fantastic explanations and breakdowns of complicated topics.
Matt, these are some beautiful illustrations, thank you.
I’ve always wondered since reading about bsps in the doom era how the dynamic elements of quake (doors, elevators, moving blocks, etc) fit into the game engine of quake.
Love your explanatory visuals, very cool
Very well-made, informative video 👍👍 The visuals in particular are out of this world!
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
This video is like 'BSP tree for dummies'. Great video!
I did not expect this to be recursive. Great video.
Outstanding work. Thank you
you have a nice way of deconstructing complex topics, well done!
This visualization is incredible!
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.
These videos are so good! I absolutely love the animation of the first level being broken down. Please keep up to awesome work!
awesome!! i didn't know that bsp trees were used for more than the map geometry. amazing
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.
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.
Wow, I just rewatched your movement tricks video yesterday, wondering when you'd release something new
Very informative video , Thanks for making it.
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!
Thank you. I use Blender for most of the graphics (2D and 3D), driven by Python scripts.
THIS IS SO BEAUTIFUL
thanks for the great videos as always!
Thank you. I allways wanted to know how this works.
beautiful visualizations
Fantastic summary mate. Thanks
In Xash3D you can visualize collision model with r_showhull 1 2 3. It was ported over from some Quake port
Awesome explanation! Thank you very much!
great video with wonderful visualisations
very nice
nice visuals in the beginning dude
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.
Carmack you're a genius
Guys at Id software back then truly are gods of programming
The "fast inverse square root" hack is also brilliant af
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
Love your videos! Very educational and super interesting! Thanks you!
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.
well done
what about quake3 / doom3 AAS Adanced Awareaness System?
Awesome video, thank you for it.
This was very interesting indeed. I would also be interested in how others did it, Jedi Knight for example.
Love these niche videos
I like makeing games, and this is helpful.
Thank You.
Thank you in advance.
Thank you too
As said in FL, that's dope! ty
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.
Ah BSP, bane of my existence when trying to model a Halo map without leaks.
awesome
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
things im trying to do in javascript right now:
thanks bro
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.
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.
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.
Hey, I use Blender for most of the animations (both 2D and 3D), using lots of Python scripts to set up the scenes.
@@MattsRamblings Thanks!
Lovely!
omg the quake builder looks exactly like source....... boom.
ive never really looked at the editor for this game but i did know that source was, more or less, based on it. but wow. identical
this animation/teaching is 50 years ahead of university course
Ooooh so THAT'S why visleafs have that name in the Source Engine!
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!