5 ms·

BSP (binary space partitioning) was a well known algorithm, not something Carmack picked out of obscurity. It is well covered in every edition of Foley and van

BSP (binary space partitioning) was a well known algorithm, not something Carmack picked out of obscurity. It is well covered in every edition of Foley and van Dam's bible "Computer Graphics". The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. That isn't to deny that Carmack was brilliant. But him using BSP isn't some masterstroke of genius in itself.

phkahler 4y ago
I, Robot used a lot of great tricks, but I'm gonna have to consult John Manfrida on the use of actual BSP trees. They did use normal vectors to determine visibility and may have done simple back to front within objects using that, but the playfield is a grid and mostly rendered back to front.
- lordfrito 4y ago
  FYI I'm the author of the original I Robot emulator from 1998. This is the one that interprets the mathbox, which means I only know what the mathbox does at the highest 'API' level (can't 100% speak to what the mathbox microcode actually does) Paul is essentially correct. It's mostly back to front, with some assumptions. I can confirm quite a number of tricks were used, not entirely sure they qualify as a full BSP (although it does involve precompiled mesh optimizations) but then again I'm no BSP expert (just an I Robot expert). The rasterizer draws a list of polygons (full polys, not just triangles) which must be fully computed before sending to the rasterizer. This "display list" is drawn in order. There is no Z buffer, so everything draws on top of what was already there. So it's important that the display list have the polygons somewhat sorted. Also the polygons are drawn as is, which means rotation/projection is done before being written to the display list. The camera was fixed (can't yaw) as to simplify math. This means you are always looking straight ahead in Z axis, which allows for all sorts of optimizations. It also makes it trivial to sort objects back to front, simply by checking z coordinate. Next, the hardware only supports 16 moveable "3D mesh" objects that can be drawn per frame. With an object count this low it's trivial to sort back to front without consuming many CPU cycles. 6809 index instructions make this part a breeze. The game playfield is "built on the fly", essentially mirroring a 16x16 (16x24? 16x32?) playfield tile array in RAM (each byte encodes tile height), and building each cube face polygon on the fly. Because of the fixed camera, no real sorting or culling is necessary when creating the display list at the highest level. You simply draw from back of the screen (furthest playfield row) to front (closest row). This process never has to change, it's a linear traversal of playfield array memory, and it always works as long as the camera doesn't yaw. Just draw each row on top of the last one. Guaranteed to not cause problems. To draw a row (16 tiles, 15 visible) all of the front/top/side polygons are computed and written to the display list. Again, because Z axis is fixed it makes creating the polygon coordinates trivial (you always see front of cube, no culling needed). Once that's done you draw any 3D meshes that are in the row (objects sitting on the playfield cells). Then you move to the next row, and the next, and then you're done. So at this high level, no real culling is done... things essentially get drawn in order of depth, which always works as long as you don't yaw the camera. Now... where things get interesting is the 3D mesh objects themselves are stored in a sort of "pre-computed" way to optimize surface removal (not sure if this was done by hand, or by an automated/compile process). It's not so much a tree structure, as it's actually done through specialized instructions. I suppose the jumping/branching is the equivalent of tree traversal. Basically the meshes are held in ROM, and are really just specialized subroutines, written as a series of simple instructions for the Mathbox. To keep this writeup simple, treat the Mathbox as being able to execute two instructions: 1) write a polygon to the display list 2) "relative jump to instruction" if normal vector dot product points towards/away from camera A 3D mesh object might be coded in ROM like this Mathbox3DMeshObject: if normal vector dot product < 0, jump to X ; pointing away from camera write poly 1 to display list ; forward facing polygons write poly 2 to display list ... Jump to Y X: write poly 10 to display list ; back facing polygons write poly 11 to display list ... Y: if normal vector dot product < 0, jump to Z ; sideway facing? write poly 20 to display list write poly 21 to display list ... Z: write poly 99 to display list ; always drawn ... END A mesh object could code any number of jumps, to cover side facing objects, corner cases, etc. Note I'm glossing over the fact that the mathbox would also multiply the coordinates by the current rotation matrix, project to X/Y, perform shading, etc. before emitting to the display list. As code it's not a real tree structure, although executing the code behaves a lot like traversing a tree. I guess this is sort of a BSP? Can anyone chime in here? It was pretty clever how it worked out. The mathbox executes the instructions, and creates draw instructions in order. Polygons get skipped by virtue of the fact you're periodically checking normal vectors, and skipping around to different instructions as needed. Edited: clarity, typos
  - phkahler 4y ago
    Sounds like the mesh objects are nearly equivalent to small BSP trees. Thanks John!
    - lordfrito 4y ago
      It definitely does work like a BSP tree. The issue to me is that a tree is a data structure, but the meshes in I, Robot are encoded as literal subroutines of machine instructions. There is no tree to traverse, the Mathbox simply executes the instructions as it encounters them. These aren't even "interpreted" (fake) instructions for a software VM (like Sweet16). They're literal instructions for the custom Mathbox microcode. The Mathbox executes the instructions, and outputs polygons to the display list as told. It's a lot like a compiler optimization that unrolls a loop inline... Can you even call it a loop once it's unrolled? In this case, it's as if a BSP was created, then turned into literal instructions for a custom machine. Many times the polygons were duplicated in the code (in-lining polys works faster than branching back). It blurs the line between code and data. I'm really blown away by the sophistication of the I, Robot Mathbox... The microcode was exceedingly complex, much more than just some fast matrix math (like Battlezone etc). It executed instructions to compute dot products, which would potentially result in X/Y/Z points being multiplied by a rotation matrix, projected, and written as polygons to the display list, for later rasterization by a different processor altogether. Anyhow it's fun to revisit this stuff :)
      - chowells 4y ago
        Sure, that's still a BSP tree. It's just represented as code instead of data. The duality of data and code is a long-established optimization path for static information.
      - JohnBooty 4y ago
        These aren't even "interpreted" (fake) instructions for a software VM (like Sweet16). They're literal instructions for the custom Mathbox microcode. The Mathbox executes the instructions, and outputs polygons to the display list as told. Wow, that's amazing, I love that. Thank you so much for explaining this.
- tasty_freeze 4y ago
  To be fair, I didn't ever look at the code. I took the word of Dave Sherman, the guy who designed the hardware for it (though the "math box" was lifted from another game, probably Battlezone). Here is one more interesting thing about the display that Dave told me. DRAM was expensive, and at the time the I, Robot game was much more expensive than most of the arcade machines they put out. To save on DRAM, they used fake double horizontal resolution. This is a memory from a conversation 30 years ago, but there is 3b per pixel to specify color, and one bit to indicate if the edge should be pushed out half a pixel. That is, when rasterizing the polygons, they saved one fractional X bit in the pixel. In the interior of polygons it had no effect, but when generating video, if pixel at offset (x+0) and pixel at offset (x+1) had a different color index, the fraction bit from pixel (x+0) was used in the video timing generator to place where the color transition would happen, doubling the apparent horizontal resolution. When more than one edge crossed a pixel the information isn't that useful, but such pixels are a tiny fraction of all edge pixels, so overall it was a big win.
  - phkahler 4y ago
    I had read about that fractional pixel online, and the bit does seen to exist in the vram (3 bits color, 3 bits intensity, one other bit). I don't think it ever got implemented all the way through. If it works as described, it should cause the right edges of polygons to appear with higher resolution than the left edges, particularly on black (blank) background. I've got an I, Robot in my living room and have looked for this visual difference and can not see it. Doodle City even provides the opportunity to move and rotate objects, so even with direct control of object and orientation I can't see it. Apparently there were other things that never got finished with the game too.
    - lordfrito 4y ago
      See my reply above... there is a 1/2 pixel being kept track of... looks like it indicates the pixel is "wide" and takes up at least half of the neighboring pixel to the right. This seems to delay the latching of the color to the monitor guns by a half pixel cycle. I agree that if it's there, its hard to see (I found some actual arcade footage online). I wonder if that's due to issues with the lower res monitors? Would be interesting to ground the 1/2 pixel signal pin and see if that has a noticeable effect on the screen visuals.
HelloNurse 4y ago
Using a BSP tree to render front to back rather than back to front is also quite obvious: it's the same visit in the opposite order.
bitexploder 4y ago
Carmack even discusses this on the Lex Fridman podcast. Carmack basically had high school level math around that era and was a voracious reader of every scrap of game programming lore he could find. And outside of it. He is a very intellectually honest guy and it is refreshing to hear him talk about how he worked in those days. I came up similar to Carmack and he is my programming hero, so, I have a lot of admiration for how he managed to do things.
- gibolt 4y ago
  Long video (5hrs+), but well worth a watch/listen. Can increase playback speed to save time https://youtu.be/I845O57ZSy4 https://youtu.be/I845O57ZSy4
  - beebeepka 4y ago
    I spent several game nights shooting guys in TF2 while listening to this interview. It is long. The channel has a few good interviews with biology guys as well
    - bitexploder 4y ago
      It was easily one of my favorite podcasts of the last few years and Lex usually drives me a little crazy.
pavon 4y ago
Yeah, when I was inexperienced what impressed me about Carmack was all the "cutting edge" techniques and tricks he used to push hardware to its limits. As I've became more experienced what impresses me is how iD was able to crank out so much software so quickly, have time to research these more advanced methods, quickly triage which were promising and which were not, and get them working and well optimized in production software. I can read research and incorporate it into my code, but it takes me a while, and I usually have multiple dead-ends where it isn't until after I've tried using a technique with real data that I realize it has weaknesses the researchers didn't point out and which can't easily be fixed. I can crank out quick code, but it isn't going to be advanced or optimized. I struggle finding the right balance of how to trade between these three things, and yet Carmack and iD were able to squeeze in all three at once.
- kudokatz 4y ago
  > As I've became more experienced what impresses me is how iD was able to crank out so much software so quickly > usually have multiple dead-ends where it isn't until after I've tried using a technique with real data that I realize it has weaknesses the researchers didn't point out and which can't easily be fixed If you listen to John Romero himself telling the story of id and the fast iteration, it was "due to having, basically, 10 years of intense game development experience prior": https://youtu.be/E2MIpi8pIvY?t=543 https://youtu.be/E2MIpi8pIvY?t=543 ("it's also due to the first principle we had - no prototypes") A theme I tend to see is that a lot of folks with super output appear to others like icebergs - a LOT of effort that nobody can see, and a tiny peak at which everyone marvels.
- ww520 4y ago
  Carmack work long hours everyday, really long hours.
toolslive 4y ago
Yes, If you were reading DrDobbs at the time, you would know that they actually tried every algorithm in the computer graphics bible (and they reported about it in that magazine). Some algorithms were in fact better than BSP, but were a bit instable performance wise (better avg performance, but worse worst case)
- Teslazar 4y ago
  I think you're referring to Michael Abrash's Ramblings in Realtime articles which were written about Quake. When I was a teen I used to carry these around with me and read them over and over while I was implementing my own engine. Copies are available here: https://www.bluesnews.com/abrash/ https://www.bluesnews.com/abrash/
  - winrid 4y ago
    A lot of this is covered in his Graphics Programming Black Book too.
  - toolslive 4y ago
    You're right: Quake. not Doom. There are 2 problems getting old: the first one is the memory that goes, ... the second one I forgot.
- johnvanommen 4y ago
  I was thinking the same thing. The author references the Michael Abrash book, and said it was from "the late 90s." But IIRC, Abrash was writing about BSP in Doctor Dobbs Journal in the early 90s. IE: Abrash inspired Carmack, not the other way around. In 1992 I was really keen on learning to make arcade style games on the PC, and I studied those Abrash articles like crazy.
  - bluedino 4y ago
    And then Carmack actually hired Abrash to help him make Quake's graphics fly
throw_m239339 4y ago
> The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. wow 1983 https://www.youtube.com/watch?v=EHkwdvfXHJc https://www.youtube.com/watch?v=EHkwdvfXHJc

phkahler 4y ago

I, Robot used a lot of great tricks, but I'm gonna have to consult John Manfrida on the use of actual BSP trees. They did use normal vectors to determine visibility and may have done simple back to front within objects using that, but the playfield is a grid and mostly rendered back to front.

lordfrito 4y ago
FYI I'm the author of the original I Robot emulator from 1998. This is the one that interprets the mathbox, which means I only know what the mathbox does at the highest 'API' level (can't 100% speak to what the mathbox microcode actually does) Paul is essentially correct. It's mostly back to front, with some assumptions. I can confirm quite a number of tricks were used, not entirely sure they qualify as a full BSP (although it does involve precompiled mesh optimizations) but then again I'm no BSP expert (just an I Robot expert). The rasterizer draws a list of polygons (full polys, not just triangles) which must be fully computed before sending to the rasterizer. This "display list" is drawn in order. There is no Z buffer, so everything draws on top of what was already there. So it's important that the display list have the polygons somewhat sorted. Also the polygons are drawn as is, which means rotation/projection is done before being written to the display list. The camera was fixed (can't yaw) as to simplify math. This means you are always looking straight ahead in Z axis, which allows for all sorts of optimizations. It also makes it trivial to sort objects back to front, simply by checking z coordinate. Next, the hardware only supports 16 moveable "3D mesh" objects that can be drawn per frame. With an object count this low it's trivial to sort back to front without consuming many CPU cycles. 6809 index instructions make this part a breeze. The game playfield is "built on the fly", essentially mirroring a 16x16 (16x24? 16x32?) playfield tile array in RAM (each byte encodes tile height), and building each cube face polygon on the fly. Because of the fixed camera, no real sorting or culling is necessary when creating the display list at the highest level. You simply draw from back of the screen (furthest playfield row) to front (closest row). This process never has to change, it's a linear traversal of playfield array memory, and it always works as long as the camera doesn't yaw. Just draw each row on top of the last one. Guaranteed to not cause problems. To draw a row (16 tiles, 15 visible) all of the front/top/side polygons are computed and written to the display list. Again, because Z axis is fixed it makes creating the polygon coordinates trivial (you always see front of cube, no culling needed). Once that's done you draw any 3D meshes that are in the row (objects sitting on the playfield cells). Then you move to the next row, and the next, and then you're done. So at this high level, no real culling is done... things essentially get drawn in order of depth, which always works as long as you don't yaw the camera. Now... where things get interesting is the 3D mesh objects themselves are stored in a sort of "pre-computed" way to optimize surface removal (not sure if this was done by hand, or by an automated/compile process). It's not so much a tree structure, as it's actually done through specialized instructions. I suppose the jumping/branching is the equivalent of tree traversal. Basically the meshes are held in ROM, and are really just specialized subroutines, written as a series of simple instructions for the Mathbox. To keep this writeup simple, treat the Mathbox as being able to execute two instructions: 1) write a polygon to the display list 2) "relative jump to instruction" if normal vector dot product points towards/away from camera A 3D mesh object might be coded in ROM like this Mathbox3DMeshObject: if normal vector dot product < 0, jump to X ; pointing away from camera write poly 1 to display list ; forward facing polygons write poly 2 to display list ... Jump to Y X: write poly 10 to display list ; back facing polygons write poly 11 to display list ... Y: if normal vector dot product < 0, jump to Z ; sideway facing? write poly 20 to display list write poly 21 to display list ... Z: write poly 99 to display list ; always drawn ... END A mesh object could code any number of jumps, to cover side facing objects, corner cases, etc. Note I'm glossing over the fact that the mathbox would also multiply the coordinates by the current rotation matrix, project to X/Y, perform shading, etc. before emitting to the display list. As code it's not a real tree structure, although executing the code behaves a lot like traversing a tree. I guess this is sort of a BSP? Can anyone chime in here? It was pretty clever how it worked out. The mathbox executes the instructions, and creates draw instructions in order. Polygons get skipped by virtue of the fact you're periodically checking normal vectors, and skipping around to different instructions as needed. Edited: clarity, typos
- phkahler 4y ago
  Sounds like the mesh objects are nearly equivalent to small BSP trees. Thanks John!
  - lordfrito 4y ago
    It definitely does work like a BSP tree. The issue to me is that a tree is a data structure, but the meshes in I, Robot are encoded as literal subroutines of machine instructions. There is no tree to traverse, the Mathbox simply executes the instructions as it encounters them. These aren't even "interpreted" (fake) instructions for a software VM (like Sweet16). They're literal instructions for the custom Mathbox microcode. The Mathbox executes the instructions, and outputs polygons to the display list as told. It's a lot like a compiler optimization that unrolls a loop inline... Can you even call it a loop once it's unrolled? In this case, it's as if a BSP was created, then turned into literal instructions for a custom machine. Many times the polygons were duplicated in the code (in-lining polys works faster than branching back). It blurs the line between code and data. I'm really blown away by the sophistication of the I, Robot Mathbox... The microcode was exceedingly complex, much more than just some fast matrix math (like Battlezone etc). It executed instructions to compute dot products, which would potentially result in X/Y/Z points being multiplied by a rotation matrix, projected, and written as polygons to the display list, for later rasterization by a different processor altogether. Anyhow it's fun to revisit this stuff :)
    - chowells 4y ago
      Sure, that's still a BSP tree. It's just represented as code instead of data. The duality of data and code is a long-established optimization path for static information.
    - JohnBooty 4y ago
      These aren't even "interpreted" (fake) instructions for a software VM (like Sweet16). They're literal instructions for the custom Mathbox microcode. The Mathbox executes the instructions, and outputs polygons to the display list as told. Wow, that's amazing, I love that. Thank you so much for explaining this.
tasty_freeze 4y ago
To be fair, I didn't ever look at the code. I took the word of Dave Sherman, the guy who designed the hardware for it (though the "math box" was lifted from another game, probably Battlezone). Here is one more interesting thing about the display that Dave told me. DRAM was expensive, and at the time the I, Robot game was much more expensive than most of the arcade machines they put out. To save on DRAM, they used fake double horizontal resolution. This is a memory from a conversation 30 years ago, but there is 3b per pixel to specify color, and one bit to indicate if the edge should be pushed out half a pixel. That is, when rasterizing the polygons, they saved one fractional X bit in the pixel. In the interior of polygons it had no effect, but when generating video, if pixel at offset (x+0) and pixel at offset (x+1) had a different color index, the fraction bit from pixel (x+0) was used in the video timing generator to place where the color transition would happen, doubling the apparent horizontal resolution. When more than one edge crossed a pixel the information isn't that useful, but such pixels are a tiny fraction of all edge pixels, so overall it was a big win.
- phkahler 4y ago
  I had read about that fractional pixel online, and the bit does seen to exist in the vram (3 bits color, 3 bits intensity, one other bit). I don't think it ever got implemented all the way through. If it works as described, it should cause the right edges of polygons to appear with higher resolution than the left edges, particularly on black (blank) background. I've got an I, Robot in my living room and have looked for this visual difference and can not see it. Doodle City even provides the opportunity to move and rotate objects, so even with direct control of object and orientation I can't see it. Apparently there were other things that never got finished with the game too.
  - lordfrito 4y ago
    See my reply above... there is a 1/2 pixel being kept track of... looks like it indicates the pixel is "wide" and takes up at least half of the neighboring pixel to the right. This seems to delay the latching of the color to the monitor guns by a half pixel cycle. I agree that if it's there, its hard to see (I found some actual arcade footage online). I wonder if that's due to issues with the lower res monitors? Would be interesting to ground the 1/2 pixel signal pin and see if that has a noticeable effect on the screen visuals.

HelloNurse 4y ago

Using a BSP tree to render front to back rather than back to front is also quite obvious: it's the same visit in the opposite order.

bitexploder 4y ago

Carmack even discusses this on the Lex Fridman podcast. Carmack basically had high school level math around that era and was a voracious reader of every scrap of game programming lore he could find. And outside of it. He is a very intellectually honest guy and it is refreshing to hear him talk about how he worked in those days. I came up similar to Carmack and he is my programming hero, so, I have a lot of admiration for how he managed to do things.

gibolt 4y ago
Long video (5hrs+), but well worth a watch/listen. Can increase playback speed to save time https://youtu.be/I845O57ZSy4 https://youtu.be/I845O57ZSy4
- beebeepka 4y ago
  I spent several game nights shooting guys in TF2 while listening to this interview. It is long. The channel has a few good interviews with biology guys as well
  - bitexploder 4y ago
    It was easily one of my favorite podcasts of the last few years and Lex usually drives me a little crazy.

pavon 4y ago

Yeah, when I was inexperienced what impressed me about Carmack was all the "cutting edge" techniques and tricks he used to push hardware to its limits. As I've became more experienced what impresses me is how iD was able to crank out so much software so quickly, have time to research these more advanced methods, quickly triage which were promising and which were not, and get them working and well optimized in production software. I can read research and incorporate it into my code, but it takes me a while, and I usually have multiple dead-ends where it isn't until after I've tried using a technique with real data that I realize it has weaknesses the researchers didn't point out and which can't easily be fixed. I can crank out quick code, but it isn't going to be advanced or optimized. I struggle finding the right balance of how to trade between these three things, and yet Carmack and iD were able to squeeze in all three at once.

kudokatz 4y ago
> As I've became more experienced what impresses me is how iD was able to crank out so much software so quickly > usually have multiple dead-ends where it isn't until after I've tried using a technique with real data that I realize it has weaknesses the researchers didn't point out and which can't easily be fixed If you listen to John Romero himself telling the story of id and the fast iteration, it was "due to having, basically, 10 years of intense game development experience prior": https://youtu.be/E2MIpi8pIvY?t=543 https://youtu.be/E2MIpi8pIvY?t=543 ("it's also due to the first principle we had - no prototypes") A theme I tend to see is that a lot of folks with super output appear to others like icebergs - a LOT of effort that nobody can see, and a tiny peak at which everyone marvels.
ww520 4y ago
Carmack work long hours everyday, really long hours.

toolslive 4y ago

Yes, If you were reading DrDobbs at the time, you would know that they actually tried every algorithm in the computer graphics bible (and they reported about it in that magazine). Some algorithms were in fact better than BSP, but were a bit instable performance wise (better avg performance, but worse worst case)

Teslazar 4y ago
I think you're referring to Michael Abrash's Ramblings in Realtime articles which were written about Quake. When I was a teen I used to carry these around with me and read them over and over while I was implementing my own engine. Copies are available here: https://www.bluesnews.com/abrash/ https://www.bluesnews.com/abrash/
- winrid 4y ago
  A lot of this is covered in his Graphics Programming Black Book too.
- toolslive 4y ago
  You're right: Quake. not Doom. There are 2 problems getting old: the first one is the memory that goes, ... the second one I forgot.
johnvanommen 4y ago
I was thinking the same thing. The author references the Michael Abrash book, and said it was from "the late 90s." But IIRC, Abrash was writing about BSP in Doctor Dobbs Journal in the early 90s. IE: Abrash inspired Carmack, not the other way around. In 1992 I was really keen on learning to make arcade style games on the PC, and I studied those Abrash articles like crazy.
- bluedino 4y ago
  And then Carmack actually hired Abrash to help him make Quake's graphics fly

throw_m239339 4y ago

> The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. wow 1983 https://www.youtube.com/watch?v=EHkwdvfXHJc https://www.youtube.com/watch?v=EHkwdvfXHJc