How much of a genius-level move was using binary space partitioning in Doom?

[Linguica]

https://arstechnica.com/gaming/2019/12/how-much-of-a-genius-level-move-was-using-binary-space-partitioning-in-doom/

 

Quote

That story about Carmack applying cutting-edge academic research to video games has always impressed me. It is my explanation for why Carmack has become such a legendary figure. He deserves to be known as the archetypal genius video game programmer for all sorts of reasons, but this episode with the academic papers and the binary space partitioning is the justification I think of first.

 

Obviously, the story is impressive because “binary space partitioning” sounds like it would be a difficult thing to just read about and implement yourself. I’ve long assumed that what Carmack did was a clever intellectual leap, but because I’ve never understood what binary space partitioning is or how novel a technique it was when Carmack decided to use it, I’ve never known for sure. On a spectrum from Homer Simpson to Albert Einstein, how much of a genius-level move was it really for Carmack to add binary space partitioning to Doom?

 

I’ve also wondered where binary space partitioning first came from and how the idea found its way to Carmack. So this post is about John Carmack and Doom, but it is also about the history of a data structure: the binary space partitioning tree (or BSP tree). It turns out that the BSP tree, rather interestingly, and like so many things in computer science, has its origins in research conducted for the military.

 

That’s right: E1M1, the first level of Doom, was brought to you by the US Air Force.

 

[Gez]

30 minutes ago, Linguica said:

That’s right: E1M1, the first level of Doom, was brought to you by the US Air Force.

This is the kind of dumb nonsensical shortcuts that journalists think makes their articles catchier but that mostly signals they don't know what they're talking about.

 

What's the relationship between E1M1 and the BSP structure? Is E1M1 the only level that requires a BSP to work?

[Xaser]

They missed a huge opportunity: that line would've been way zingier if they'd included the name of the map.

 

Quote

That's right: E1M1, Hangar, was brought to you by the US Air Force.

 

[Gez]

Pictured: the US Air Force after attempting to break the sound barrier

[ETTiNGRiNDER]

Kind of reminds me of similar questioning I've seen regarding just how "out of thin air" the Commander Keen scrolling trick really was.  I don't recall all the specifics but the argument had something to do with:

- similar techniques already being used for other systems outside the PC ecosystem

- the fact that the EGA hardware was designed in a way that allowed it suggesting it was an intended use from the get-go that just wasn't taken advantage of

[andrewj]

It was interesting that Carmack first used BSP trees in a Wolfenstein port.  Getting the algorithm working in that context is a lot easier than Doom, as all the walls in Wolf3D are axis aligned and on a fixed grid, so you never have to split walls or do any complicated math.

 

[Doomkid]

12 hours ago, Gez said:

This is the kind of dumb nonsensical shortcuts that journalists think makes their articles catchier but that mostly signals they don't know what they're talking about.

 

11 hours ago, Xaser said:

They missed a huge opportunity: that line would've been way zingier if they'd included the name of the map.

Not only do they say baseless nonsense for Da Zing, but they aren’t even good at Zing in the first place. Brilliant. Truly an editorial marvel.

 

Complaints aside, that’s a pretty interesting write up. I think it’s safe to say Carmack is Pretty Darn Smart and that the entire concept of trying to put him on a ‘relative intelligence map’ is Pretty Darn Silly, but still, I’m glad the article acknowledges how great a solution BSP was even if the entire concept wasn’t his own from-scratch creation. It sometimes takes a genius to combine multiple parts in a certain way to reach a certain end - sort of like how a genius guitar player is still a genius despite the fact that they didn’t invent the guitar.

 

Good article even despite the dumb “Air Force made E1M1” comment. Gotta wonder why they said E1M1 rather than just saying ‘Doom’, but oh well. Although the article was heavy on the technical jargon it was still very interesting even for a layman reader (me), which is impressive in its own right!

Edited December 30, 2019 by Doomkid

[Nembras]

3 hours ago, Doomkid said:

 

...Gotta wonder why they said E1M1 rather than just saying ‘Doom’...

 

Probably to show that they know the Doom jargon. Because you need to be an advanced doomer to know the ExMx nomenclature, right?

[Soundblock]

"[...]there are usually fewer enemies visible then there is level geometry in a level, speed isn’t as much of an issue here[...]"

 

This begs the questions (or maybe not):

- before, or after you split the geometry?

- how many "level geometries" are visible on average in the original Doom levels?

- what's the thing:"level geometry" ratio on average?

- how has the event of slaughter maps changed this ratio?

- at which point does this ratio, when skewed in favor of things, cause Doom to run slow on contemporary hardware? (I seem to remember the engine just stops drawing them if there are too many)

 

;)

 

Seems to me the author is comparing apples to oranges here? He corrects hyperbole done by Kushner (who's seemingly trying to describe the first practical application of gaming BSPs, albeit dramatically), but maybe adds some underplay himself.

 

At any rate, I found the notes about the "implicit z-buffer" being more effective runtime in a not-true-3D-engine the most interesting & one of the things I marvelled the most about when I first played Doom was certainly how the engine didn't remove dead enemy entities (sprites) from the levels after they were defeated - something that's since "returned to normal" in the Doom series & gaming world at large. How else you gonna have a true Archvile?

[jval]

12 hours ago, andrewj said:

It was interesting that Carmack first used BSP trees in a Wolfenstein port.  Getting the algorithm working in that context is a lot easier than Doom, as all the walls in Wolf3D are axis aligned and on a fixed grid, so you never have to split walls or do any complicated math.

 

 

That's a "Thing about Doom Wolf I just found out"

I thought Worf was a raycast engine.

 

[andrewj]

7 hours ago, jval said:

 

That's a "Thing about Doom Wolf I just found out"

I thought Worf was a raycast engine.

 

The original was a raycaster.

 

But for some console port (PSX I think) it was too slow and he needed a faster way, so he used a BSP algorithm.

Edited December 30, 2019 by andrewj

[Gez]

It was the SNES port of Wolf 3D. The SNES port was also famous for replacing blood with sweat, dogs with rats, and "anonimizing" the Nazi Germany symbols. Hitler lost his moustache and become "the staatmeister".

 

I'm not aware of a PSX port of Wolf 3D, AFAIK Wolf didn't jump to the PlayStation until the PS3, at which point it could just be a direct port of the PC version without needing to sacrifice anything.

 

There were ports to the 3DO, the Jaguar, the GBA, the Acorn, and even the Apple IIGS.

[NiGHTMARE]

On 12/30/2019 at 4:32 PM, jval said:

 

That's a "Thing about Doom Wolf I just found out"

I thought Worf was a raycast engine.

 

 

Worf is a Klingon engine, obviously.

[ketmar]

actually, Carmack didn't realised that unmodified BSP could be used for collision detection too until Q2 or Q3 (don't remember it from the top of my head). Q1 was using a special "secondary" BSP tree for coldet, with inflated leaves. but then Carmack realised that it is possible to add beveling planes to use one BSP both for rendering, and for AABB CCD. the trick is to add axial planes to each leaf, so you can inflate it in runtime by modifying plane distance (think of Minkowski sum here).

[andrewj]

5 hours ago, ketmar said:

actually, Carmack didn't realised that unmodified BSP could be used for collision detection too until Q2 or Q3 (don't remember it from the top of my head).

Yeah, it was Q2, the CM_BoxTrace() code.

 

The Q1 collision hull is interesting in that player collisions are done by considering the movement of a zero-size point through space -- the world is inflated to account for the size of the player.  (There are a few other hulls, e.g. one for large monsters, and IIRC the rendering BSP is used for truely zero-size points i.e. hitscans).

 

At first I thought that Q1 system was brilliant, fairly easy to visualize what is going on.  But after implementing my own code to generate the hulls, I was less enamored with it since it was producing hulls where the player would get stuck while sliding along a particular wall -- something to do with the order the walls appeared in the BSP tree.  The method used in Q2 and Q3 seems to work more robustly in my experience.

Edited January 7, 2020 by andrewj

[printz]

Yeah, cool and all, but BSP is a major hindrance if we want to move ahead and have moving platforms.

[Linguica]

If I ever start experimenting with Doom source ports again one thing I want to look into is extending the BSP to do more interesting things. I've looked at research papers about recalculating parts of BSP trees in real time etc and some of the stuff could surely be applied to a Doom port. I think there would be some very interesting gains to be made in collapsing the BSP tree and blockmap into a single structure and one paper at least suggests you can even get sub-linear BSP search times if you set up the data right.

[ketmar]

5 hours ago, andrewj said:

The method used in Q2 and Q3 seems to work more robustly in my experience.

it's basically the same method, except that Q1 didn't had beveling axial planes, afair, and used less robust inflation. i believe that Q2 algo was born exactly when Carmack realized that simply adding axial planes at the corners is enough to produce correct Minkowski sum of any leaf and AABB. this is also the reason for keeping AABBs in the engine -- any other primitive will require more complex leaf beveling, and will not work as good (yet Bioware engineers used the same beveling trick in MDK2 for ellipsoids).

 

27 minutes ago, Linguica said:

I've looked at research papers about recalculating parts of BSP trees in real time etc

yeah, it is absolutely possible to perform real-time CSG on Doom map. the problem is that Doom maps aren't 3d, so you basically can only cut rectangular holes, or add rectangular regions. which can be done with instalifts. making something like Red Faction is much harder, because you have to create slopes, maybe 3d floors, and you know how messy are those things.

 

fun fact: Unreal1 is dynamically "slicing" all moving object with main mesh BSP. it needs to do so to maintain correct rendering order (which is required for visibility culling too).

 

p.s.: how can i insert another quote when editing? sorry, @printz

Quote

Yeah, cool and all, but BSP is a major hindrance if we want to move ahead and have moving platforms.

basically, no. what is bad is that we don't have a real 3D BSP, as in Quake, for example. and 3d meshes. you can use U1 method with complex polyobjects -- after slicing they'll become a normal map part, and you will be able to use normal position checker and calculate wall openings. it is slightly messy, but not really a huge problem (and i believe that most advanced ports are doing something like that already). Doom coldet code is much worser problem, i am still experimenting with replacing it by box tracing (i have working PoC of `TraceBox()` API on map BSP), but the worst thing is that it is not 3d. it seems to be absolutely impossible to combine XY and Z movements (it was semi-working in my PoC, and it was a freakin' mess i would never put into the engine).

Edited January 7, 2020 by ketmar

[Gez]

3 hours ago, ketmar said:

basically, no. what is bad is that we don't have a real 3D BSP, as in Quake, for example. and 3d meshes. you can use U1 method with complex polyobjects -- after slicing they'll become a normal map part, and you will be able to use normal position checker and calculate wall openings. it is slightly messy, but not really a huge problem (and i believe that most advanced ports are doing something like that already).

Yeah:

Quote

Since the original Raven polyobject system left much to be desired with its restrictions of one polyobject per subsector, no intersections with static geometry, strictly convex objects only, and difficulties wherever polyobjects were crossed by node lines, source port authors eventually sought more robust solutions to the problem.

The Eternity Engine was the first port to attempt to re-implement polyobjects. James Haley (Quasar) created a dynamic seg rendering system (dubbed "dynasegs" for short), which split the polyobjects through the static world BSP tree in order to generate fragments contained within each subsector contacted by the polyobject. This eliminated the need for a polyobject-aware node builder. It also lifted the one-object-per-subsector rule by performing a front-to-back z-sorting algorithm on fragments within each subsector. Polyobjects could also now move arbitrarily between subsectors, rather than being constrained within the single area in which they were spawned.

Limitations of this initial system were still evident, however. The ZDoom source port initially adapted the same approach developed for Eternity, but then went one step further by replacing the restrictive z-sort with generation of "MiniBSP" trees within each subsector, dynamically recomputed via the internal node builder whenever a fragment was added or removed from the subsector during dynaseg generation. These BSPs provide a complete ordering of the dynamic segs so that they draw in the correct sequence regardless of the camera view point. By including the static segs of the subsector into the BSP as well, this removed the remaining limitations: polyobjects could now be concave, intersect with static geometry, and intersect with each other.

ZDaemon and Eternity eventually both followed suit with independent implementations of MiniBSP construction.

https://doomwiki.org/wiki/Polyobject

[ketmar]

yeah, i read that article too. but i didn't checked the code, so i don't know any details. also, this is what i am going to implement in k8vavoom too (and will prolly use that to allow sliding -- and maybe swinging -- doors without explicit polyobject creation). this is what people are using polyobject for most of the time, i believe, so introducing special cases for those things will worth the efforts.

[Graf Zahl]

If you try to do these doors in-place where they are supposed to show up you'll enter Build engine territory where sector shapes are no longer static - that would create an entirely different level of complication. Polyobjects have the advantage of not affecting the target sector's shape.

I think with the polyobject approach movable sectors are possible - the biggest roadblock here is that Doom's actors are square and not cylindrical which would cause massive problems if these moving sectors change orientation, so without further changes it could only be used to move things in a straight line or emulate the rotating light effect in DN3D's first map.

 

 

[ketmar]

2 hours ago, Graf Zahl said:

If you try to do these doors in-place where they are supposed to show up you'll enter Build engine territory where sector shapes are no longer static

that's why i will limit it to only two door types (even to one, prolly -- i'm not sure about swinging doors yet). and will limit door shape to a one-sector rectangle too. more complex things will require polyobjects, but simple doors will be much easier to create. yep, a hack, but i think that it is a worthy hack.

 

still, it is not set in stone yet. i will try various approaches, and if i'll find something acceptable -- i will make it "official" (in the hope that you will implement it in GZDoom later ;-).

Edited January 7, 2020 by ketmar

[andrewj]

10 hours ago, ketmar said:

Doom coldet code is much worser problem, i am still experimenting with replacing it by box tracing (i have working PoC of `TraceBox()` API on map BSP), but the worst thing is that it is not 3d. it seems to be absolutely impossible to combine XY and Z movements (it was semi-working in my PoC, and it was a freakin' mess i would never put into the engine).

You can convert DOOM's 2D BSP to a 3D BSP just by the addition of floor and ceiling planes in each subsector (and at least one partition plane, more for 3D floors).  As usual, the devil is in the details.....

[ketmar]

2 hours ago, andrewj said:

You can convert DOOM's 2D BSP to a 3D BSP just by the addition of floor and ceiling planes in each subsector

it's not that easy, tho. ;-) Doom BSP leaves are void, not solid, and it... distorts math a little. also, Doom "on the floor" means "object z is equal to floor", and this leads to numeric instability (or more weird math hacks).

 

but i tried that approach, including creating convex solids for floors and ceilings. still a mess. ;-)