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.
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.
You know reading this caused some forgotten neuron in my brain to fire.
When I was reverse engineering the thing, I seem to remember there being a bit related to color/shading that I couldn't figure out what it did (I could see that it was being used).
The system had a 64 color palette. The software broke that up into 8 sub-palettes to give you for 8 main colors with 8 shades each (0-7 first color, 8-15 second color, etc.)
Polygons could call out colors directly using full palette index. Most polygons "faked" shading, they really just specified different shades of the same color for effect. For example, the dodecahedron / meteors in the space waves aren't real-time shaded, just colored to look that way.
However the hardware could do shading, which cost an expensive dot product. So it was used sparingly. To do shading, the polygon used a 3 bit color "index" to call out one of the 8 sub-pallets. Then you add an offset of 0-7 based on the dot product of the normal vector to apply shading (I used 8 x dot product to get you an offset from 0 to 7.9999).
I recall there being an extra bit there (4 bits instead of 3) but couldn't figure out what that last bit was for (it seemed like a "1/2 bit" to me). It looked like it was being used, but didn't make sense, so I stripped it off, and it didn't seem to affect anything so I forgot about it... till now. If I'm remembering correctly, this might literally be a "1/2 step" to add between shades? That can't be right can it?
Another way I read what you wrote is that it could be considered an "anti-aliasing" bit to do some alpha blending at the edge of a polygon to fake higher resolution? Maybe that's a better way to read it?
My memory is probably not 100% here... Would love to hear more.
I don't think it was for antialiasing (to interpolate between shades at adjacent pixels), it affected the horizontal timing.
I don't recall the actual resolution, but say it was 256 pixels per scan line. If the color for pixel 100 was index 5 and for pixel 101 it was index 3, the straight forward way would be to send the right RGB phase for whatever index color was throughout the interval pixel 100 and then send the right RGB phase for whatever was the right color for pixel 101. The half bit modified the timing to delay the transition from pixel 100 to pixel 101, somewhat doubling the horizontal resolution. It made polygon edges less chunky.
Or another way to conceptualize it: each row had 512 pixels, but memory for only 256 pixels. By default each memory location would be used to fill in the color for pixels X and X+1. But the half bit would modify it to say whether the transition should be shifted out one more pixel. If the transition was from red to blue, the default way would be to generate four pixels out (R, R, B, B), but if the half bit was set, the video generator would output (R, R, R, B).
OK so I did some digging into the schematics.
Posted relevant parts of schematics here [1]
Yeah it totally jibes with what you said above.
The rasterizer outputs what looks to be 10 bits of horizontal position (for the pixel being written I'm assuming). Since screen is only 256 pixels wide, this would imply that there are fractional horizontal bits here. The rasterizer keeps track of fractional bits to compute sloping (jaggies)... so the fractional bit implies the pixel being written fills up more than 1/2 of the next pixel.
Video memory is 7-bits per pixel. 6 bits are for 64 color palette index. The fractional 1/2 pixel bit (after some AND/OR/XORing) is stored as the 7th bit of the pixel. Indicates its a "wide" pixel.
Later, when video memory is being read/scanned to the monitor, the buffer holding the 6-bit color to output is sometimes latched a half clock cycle later. The half clock cycle delay is the 7th bit stored in the video memory, the 1/2 bit.
So yeah.. you're essentially delaying the latching of the next color if the pixel is "wider". It makes sense to think of the additional bit as a width bit.
This is a crazy way of doubling resolution... instead of needing double the screen buffer memory, you add 1 bit to indicate the pixel is wider. The caveat is you really don't have true double resolution, you can't have a single pixel at half resolution. You only get pixels of normal width, or 1.5 pixel width. Still that's amazing!
It should be possible to see this artifacting on a real game. Since the alphanumerics overlay is scanned at normal pixel size, if there is a half pixel in the bitmap, the overlay should sometimes not appear aligned to the background. Paul, you might be able to see this on your machine. If you play around in doodle city, you can move polygons where they're behind the alpha overlay, slight movements might show the half pixel in relation to the overlay.
>> The caveat is you really don't have true double resolution...
And only on the right side of a polygon. If video RAM is cleared to 0-black, there would be no "wide" background pixels, only wide polygon pixels and they're extended to the right only.
I will look at Doodle City and try to move things under the text overlay.
Also, what is that big chip in the linked schematic doing? HPOS6-15? PADD0-PADD10. It has a 5MHz clock (the dot clock) but that FF has a different clock which might be 10MHz?
The big chip (ICY) is the custom rasterizer ASIC. Basically a very primitive GPU, maybe the first? I don't know the internals (I'm told they're floating around) but I know what it does.
Yes that chip has a different clock, as its writing pixels to the frame buffer. The monitor always displays the other buffer not being written to, so the rasterizer does not need to be sync'd to the monitor pixel clock (which has overscan areas etc.), therefore the rasterizer can fill pixels at a different speed. My guess is that they couldn't run the ICY faster than the 5MHz, because I'm sure they wanted to run it as fast as possible!
Essentially the chip takes the display list, which is a bunch of instructions for DOTs / VECTORs / POLYGONs, and draws them to the frame buffer pixel by pixel. Starts at the top of the display list (address zero), goes instruction by instruction filling pixels until list end is reached. Note the START and HALT signals coming from the main 6809 CPU telling the chip there is work to do. When you "HIT A BLACK HOLE" everything is halted and the CPU tries to recover things.
Commands generally look like this (this is a major oversimplification so don't take this as 1:1 with the real hardware)
CMD_TYPE COLOR XLEFT XRIGHT YTOP SLOPELEFT SLOPERIGHT NUMSCANLINES
Where CMD_TYPE is [dot/vector/polygon], COLOR is the palette index, and coordinates are in 16-bit with fixed precision slopes.
The chip fills pixels from left poly edge to right edge, when it reaches the end it adjusts the left/right edges and adds 1 to the scanline, eventually stopping when all scanlines are drawn.
As I said I know the internals are floating around, and I know of at least 1 project attempting to duplicate the ICY on a daughterboard. ICYs are 40 years old and are starting to die and there is no replacement.
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.
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.
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.
20 years after playing around with your emulator, I get to tell you that the "metafile dump to Window's clipboard" feature is just so nifty it still sticks out in my memory today.
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.
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.
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.
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.