The use of vector graphics instead of 3d rendering or bitmap video seems reminiscent of the techniques which allowed Another World to achieve the fidelity it did on the consoles of that era: https://www.youtube.com/watch?v=X7GVubkh4TE
Actually not the same team, just the same publisher that capitalized on AW's success. Eric Chahi himself, the one-man-army responsible for Another World, only did Heart of Darkness afterwards.
EDIT: Well, maybe I speak too soon. Chahi and Mechner don't exactly represent the average developer - they both are polymaths and were capable of combining their broad interests in amazing and creative ways.
The imprecise overruns because you'll draw over it is a clever optimization.
It's interesting to compare and contrast these techniques from other excellent sources, like Michael Abrash's Graphics Programming Black Book, Special Edition [1].
Thought my technical knowledge topped out somewhere in the middle of the 'Quickly Drawing Tiles' section, the prose and algorithmic detail is lovely, the rationales and code is welcome, and the visualization is excellent.
Quickly drawing tiles is one of those sections that's really only going to make sense if you've ever done development work on a tile-mapped videogame console, as the mode is quite rare in other applications.
A "tile" is nothing more than an index into a collection of 8x8 graphics squares. If you've played any retro-styled games you've seen the effects of this. They were a great way to deal with memory constraints back in the day, as you reduce 64 pixels worth of on-screen data to a small handful of bytes, describing the index of the tile, and often other attributes like the palette to use, or whether to mirror the tile in a given direction.
Since the Mega Drive can only draw tile-mapped graphics, and has no direct bitmap modes, it makes sense for the rasterization engine in this demo to take full advantage of the hardware. When he talks about drawing an entire 8x8 tile with a one-word write, he means quickly setting the index in this way. Somewhere in memory, he's created 16 solid-color 8x8 tiles, one for each of the palette colors. Then, if any group of 8x8 pixels in a row would be the same color and they're aligned with one of the tiles, he can just point that tile at one of this solid-color indices, and move on. Part of the magic of his algorithm is quickly identifying (in advance) which tiles the megadrive can be quickly drawn with this technique, and which tiles (at polygon edges) need to be drawn more slowly in software.
Basically all 8/16-bit console graphics tricks take advantage of one (or both) of the following two facts:
1. 8-bit and (particularly) 16-bit consoles are built to draw and move 2D tiles crazy fast. If the effect you want can be achieved (or faked) by a series of animated tiles, you can do it. The most obvious example is "segmented" characters (usually bosses, but also the protagonist in Vectorman) that are made up of multiple sprites (tiles) that are animated in such a way as to fake smooth 3D animation
2. The screen is drawn one row at a time. Left to right, top to bottom. Like a typewriter. You get a little bit of processing time after each row, and a little extra time after the last row. You can use this time to tweak things (like, the position of the background, or the position of a sprite) in between rows. This is how you can achieve "line scrolling"
"Simple" line scrolling where you change the background scrolling rate on each horizontal line, for a very smooth effect: https://youtu.be/hIiMz_NUDEw?t=97
I am not sure, but I think many of the abstract effects (not the polygon animations, which use tile rendering) in the Over Drive 2 demo that this article discusses are achieved by extremely precise manipulation of sprite positioning and/or scroll registers as in #2 above.
Hey now, your average IBM PC has a tile-mapped display mode, too: we just usually call it "text", and the tiles "characters". :)
But the text-mode 'font' (i.e. the tileset) was often able to be written to, to achieve fast arbitrary-tile drawing results exactly like those of your average game console.
Thanks for writing this. I didn't really expect that much attention, so I kind of assumed most people reading it are at least somewhat familiar with the graphics hardware of that area. I shouldn't have assumed that :)
You want to go one further... according to this interview[1], Yuji Naka actually wrote a 3D graphics engine for the Master System! :) It was very low resolution, of course, but...
According to another interview that I can't find at the moment, he also wrote a Famicom emulator for the Mega Drive, which might have been the first Famicom/NES emulator ever written.
Not a question. But I just wanted to say that this sort of thing is amazing to me.
I literally:
1. Saw this article headline about a polygon rendering engine on the Mega Drive
2. Thought, oh this is going to be good
3. Made some tea
4. Settled in to enjoy it.
Not only did I love the demo and your article, you cleared up a longstanding mystery to me. I know that Another World (aka Out of This World) and Flashback (intro only) used similar techniques to render "canned" or "pre-baked" polygon animations on the Mega Drive, but I knew literally nothing about how that was possible. Thanks to you, now I have some kind of idea. Were you inspired by those games, to pull off this awesome effect in your demo? (BTW, you achieved a much better frame rate AND did it without borders... totally badass)
Last but not least, thank you for the inspiration. I'm not a graphics programmer but I am a programmer and I have always been inspired by demos ever since the days of Future Crew. Coders like you inspire coders like me to better ourselves and be unafraid of challenges.
I had a couple of games on Mega Drive that did basic 3D, or seemed to. One was F1, where a few objects seemed to be true 3D. See the overbridge at 59s and then the long tunnel at 1:01 here for instance:
https://youtu.be/qofonsN3Nwc?t=57
The long tunnel is made of several short tunnels.
I don't know about the F1 game but I can take a guess on Gunstar Heroes.
I noticed the cubes are always aligned perfectly to the axis. And they have an isomorphic projection so the cube is always the same height (although that shouldn't be strictly necessary) as it's rotating. I also noticed the cubes never seem to get smaller if they are closer to the background.
Because of this you could just have a series of sprites each showing the cube in a different angle of rotation.
Now all you need to do is properly position a bunch of sprite (16 cubes + head) and it looks like a bunch of cubes that are actually drawn in 3-D. It wouldn't surprise me if they have some small table of the X/Y positions of the cubes precomputed so they don't have to do that in real time.
In fact since every cube is always rotated at the same angle you could just have one sprite in the system table and update it every frame.
That's my guess anyway. Clever sprite trickery.
It wouldn't surprise me if F1 uses something closer to what is described in the article (although much less capable).
Your analysis appears correct, as several sources write that Gunstar Heroes uses multi-sprite bosses [1][2].
F1 on the Mega Drive owes its existence to an earlier game for the Atari ST, Vroom [5]. The brainchild behind that game, "Dan McRae", talks in a video interview [3] about how he arrived at that particular version of the game from his earlier revisions on older platforms -- where techniques shown in Lou's Pseudo 3d Page [4] apply, to more advanced techniques [6] similar to the ones presented in this submission.
F1 on the Mega Drive was done by the same dev studio that collaborated with McRae on Vroom, and at least one of the same programmers, but presumably had to do some advanced tilemap trickery specific to the console. Unfortunately, compared to other games in this series, there is very little information on the technical aspects of the Mega Drive version.
I've never had a Mega Drive before working on this, so I wasn't really familiar with a lot of its games.
I took a quick look at F1 just now though. The way it makes use of the nametable and patterns is very similar to what I do. There are precomputed fully solid patterns at a fixed location and the non-solid patterns seem to be bump allocated.
It makes use of both layers though, drawing the street on one and everything else on the other. I think it uses per scanline scrolling to apply correct perspective to the street.
I can't say anything about how it actually renders into the tile map for now. That would require a lot more than looking at the VDP (graphics chip) debugger in an emulator.
Thanks so much for taking the time to check it out. I've had that game for >20 years now so it's nice to learn a little bit more about it. Cool that they were doing something similar 24 years ago.
The Gunstar Heroes boss reminds me of an old demo effect called vectorballs or "bobs" https://youtu.be/Itv3f7o7Zac?t=167 combined with a Doom-style pre-rendered set of rotated sprites.
Were there any alternatives/dead ends you went through to arrive at this technique, or any extensions you wanted to do but didn't find the time? Really amazing work BTW, this might be my favorite demo ever!
There weren't really any dead ends. Mostly because I started with a very simple naive way to draw polygons and improved it incrementally. I didn't implement all those steps, but convinced myself that they would work.
I started with a generic plot-individual-pixels-into-tilemap routine. Going by tile-rows and columns with special casing solid tiles came next. That required "convexity" in x direction but at that point I was only thinking of triangles. Then I noticed that avoiding overdraw and working with a tesselation of the screen is probably faster. A that point I also extended it from triangles to polygons. While fleshing out the details of everything I noticed that I don't have to be exact for right-side edges if I draw the polygons in the right order.
There actually was an extension I did, that was scrapped because it just didn't look good. At some point there was support for dithering. That helps with the low color precision of the Mega Drive (3-bit/channel). It only supported 50% checkerboard dither though, which looked odd when animated. I toyed with some ideas on how to improve upon that and discussed them within our demo group, but in the end the decision was to not use dithering.
For the Mega Drive/Genesis the framerate depends on the region, matching the local video standard. The European Mega Drive uses PAL with 50Hz.
As the biggest part (but not all) of the demoscene is based in Europe, most demos target PAL hardware. The same is true for our demo group. NTSC ports can be very difficult if not impossible as PAL often does have a slight advantage in CPU cycles per frame. This is also the case on the Mega Drive.
Porting the polygon renderer shouldn't be a problem as it renders in an off-screen CPU RAM buffer. In the worst case it would have to skip more frames, having a lower effective framerate.
A lot of the other effects have very critical timing though. I've been told that porting some of them to NTSC is just impossible.
There is a little more CPU time, but the extended vertical blanking interval means there is a huge difference in video memory bandwidth, which is critical for a long DMA transfer from 68000-bus memory to VRAM through the Mega Drive's VDP.
60Hz V-blank DMA: 7524
50Hz V-blank DMA: 17622
That's at 320x224 resolution for both. I don't know how much this affects this one demo in particular, but for other things it can be a little annoying sometimes to be bandwidth-starved.
For this project I don't really have to say much about the rust side of it. There were no surprises. The only thing special I can think of is the excellent cross-compiling support. That came in handy as I had to produce windows binaries for the 3D artists.
Nice article. I got a bit lost at the section explaining the left-to-right technique, and wanted to ask about that here, but now I see there's pseudocode and even illustration of the technique. Great that you've gone through the effort to add those, they are really useful to clarify and take away any misconceptions.
Tech overview: http://fabiensanglard.net/anotherWorld_code_review/