3 ms·

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 visib

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.

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.