A different kind of sprite system

Question

Early consoles and home computers that were optimized for games, often provided sprites. From the viewpoint of a game developer, these were good to have, though one always wanted bigger sprites, to the extent that one sometimes placed two or more together, or at least on the Commodore 64, flipped the 'double width' bit despite this doing bad things to resolution. (In this discussion, I will always be talking about size in terms of width, since you can usually reuse sprites on subsequent scan lines, so height tends not to be an issue.)

I asked in Limiting factor on sprite sizes what the limiting resource is, and there were some good explanations about how memory bandwidth and the size of on-chip memory to store sprite data are both issues. Supported by this pseudocode description of the NES sprite system https://wiki.nesdev.com/w/index.php/PPU_sprite_evaluation which seems to be describing a process of reading data from all eight sprites into quickly accessible memory to be ready to deal with the worst-case scenario where all eight might partially overlay each other. Looking at that, it's certainly understandable how it taxes chip resources, making it impractical to provide more than eight small sprites.

I've been thinking about how one might get around that limit, and it seems to me you could do it by thinking in terms of supplying, not sprites directly, but transitions. That is:

• At any given time, the video chip is rendering from a background or from some sprite.
• At a transition, the video chip switches to some (maybe different) sprite, or to the background.
• At each scan line, the video chip is given a list of transitions, their X coordinates and pointers to the data to be rendered.
• The list of transitions must have been sorted by the CPU.
• There is a minimum distance between transitions. (Maybe a couple of words? Enough that the video chip only has to deal with one transition at a time, basically.)
• There may be a maximum number of transitions per scan line.

This would require more active involvement from the CPU; in a sense it would be partway between the 'racing the beam' techniques on the Atari 2600, and the fully seamless (but resource-limited) sprite systems on the likes of the Atari 800, Commodore 64 and NES. But it would eliminate the limit on sprite sizes; in my opinion, that would be a worthwhile tradeoff.

So my question is:

Did any historical computer or console ever implement a sprite system like the one I have outlined?

(And if not, why not?)

Answer 1

Expanding on my comment above:

For a while I pursued efficient drawing of filled polygon graphics on 8-bit systems through differencing. My intention was that I would exit the 3d calculations with what amounts to a span buffer: for each line an ordered list of only the x positions at which a change of colour occurs, and the colour that is changed to. The advantage of that is that it's fairly trivial to do an O(n) comparison between the new list for a line and the last one that was drawn there and draw only the differences. So you're in effect only repainting the boundary changes. Since polygons tend to be large, that's a lot less drawing.

Demos do that sort of thing all the time but are specialised to particular scenes, e.g. a single non-overlapping shape (because it's convex with hidden face removal, or originally 2d), or a scene that is entirely or overwhelmingly precomputed. I didn't want to produce a demo.

So what I wanted was essentially identical to what you're proposing: just an ordered list of transitions.

Option one is to fill the thing from back to front. Naively assuming that my intermediate working set is the same as my final output set, to add a new span x1 to x2 I need to figure out where x1 should go in the existing list and insert it, and then I need to walk the list until x2 keeping track of colours and removing transitions, then insert one at x2 back to whatever I discovered the active colour to be there. I do that for every span, I'm done. It's a logarithmic search, then naively a linear one.

Smarter is to store left colour and right colour at each transition. Then that's two logarithmic searches, one over a smaller data set than the other, plus arbitrary removals and usually two insertions (unless you fall exactly on an existing transition, that is).

In practice, the amount of time you spend shuffling bytes back and forth in the list kills any advantage you might have hoped to get as soon as you have any number of polygons more than the amount you could just straight draw.

So I tried switching to drawing front to back. Therefore you may insert only that portion of a new span that would cover an area that is currently the background colour. That prima facie reduces inserts but makes walking the list obligatory. So you're back to logarithmic plus a linear walk. And, actually, it actually often increases inserts because you're often splitting the new span you're inserting. Though if you keep a proper tally you can spot when a line is already full and reject all further spans immediately, so looking directly at a wall suddenly becomes the optimal case rather than the worst.

Using a linked list rather than a linear makes the issues worse, not better, because it makes all searches linear rather than logarithmic.

So I abandoned the idea of creating the list in its output form and switched to front to back tree-based insertion, which is serialised only at the end. Each node is a complete span, and sticking with front-to-back means never splitting what's already in the tree, only splitting or discarding what's being inserted. An issue then is storage if you want any sort of speedy traversal. I was targetting a 256-pixel display window so I went with five bytes per node — start x, end x, link to left subtree, link to right subtree, colour, and allocated each output line its own 128-byte half-page aligned section of memory. So that's 24kb, ouch! And no more than 25 polygons on each line, though that's less troubling.

The inserts are then 'cheap' and the final serialisation is a simple stack-based in-order walk but that still very quickly became far and away the dominant processing cost.

You can resolve the fixed-24kb issue by using seven-byte records but then you're talking about walking 16-bit pointers which is more hassle for a Z80 and not really practical at all for a game on a 6502.

You can also resolve it by producing polygon spans on demand and having only a single-line buffer. That introduces a further potential optimisation: sort your span-producing objects from left to right and produce the sorted list 'directly'. The issue is that you've lost your front-to-back ordering. So actually what happens is that at each object edge you know which n objects are currently outputting pixels, you pick the frontmost, then proceed to the next transition point. Where you possibly make much the same decision, but after adding or subtracting from the active list.

That actually ended up being the most optimal thing, and was demonstrably smarter than brute forcing, but look at the steps I've had to perform:

• prepare a list of all objects that contribute to the scene up front;
• ideally, sort them by starting y position;
• step down the display one line at a time, keeping a note of which objects are active on that line without breaking the ordering;
• for that line, look at my indirect list of active objects and check that it is still properly sorted by x. If it isn't, adjust it;
• step through the transition points (i.e. start or end of object) of that that from left to right, at each making a decision about the new frontmost and writing a transition if it has changed.

My case is actually slightly simpler than sprites: my objects were horizontally convex. Each had only one start and end per line. For sprites you're going to need to have an RLE version of their boundaries.

I pursued it because it was interesting, but it was a major rabbit hole, the in-RAM requirements for doing anything in a feasible amount of time are large by the standards of the day, and it still cost quite a lot.

If you presented that to contemporaneous developers as an alternative for sprite output to the C64, NES, ColecoVision, etc school of just giving a list of sprites and accepting that they're limited to, often, 16x16 and four or eight per line, I don't think your platform would get much support. It's a lot of work, it burns a huge amount of your CPU advantage, and it's just too peculiar. Maybe you'd have found an audience for a brief while if you'd been able to leap in with that as the next development straight from the 2600, getting an audience of beam racers directly on board, but even then somebody like Coleco would have appeared and said 'we just made it simple and, look, we can port things reasonably well very quickly'.

So I like the idea, but it's actually much more complicated than it sounds, and I think that would have dissuaded development.

I'll also note that for sprite graphics you've also probably substantially increased the necessary memory bandwidth because you need to write a transition each time a sprite switches from transparent to opaque. So you need a decent precision on where the display processor should start fetching from. So you're probably talking a worst case of 16 bits per pixel for anything regular and with decent precision. If you don't bucket the transitions then it's at least 24 bits per transition as you need to be explicit about location. Something like the C64 has bandwidth for only 40 byte fetches in a line (bad lines aside) so that's 13 whole transitions. Even with just rectangles, each has a transition in and a transition out. So that's 6 whole objects. You've done worse than with the 8 hardware sprites that machine actually has.

(bonus chatter: yes, preparing the scene as above would in principle allow it to be commuted to something like a Copper or ANTIC list rather than actual pixels; no, I'm insufficiently familiar with those machines to know whether that's actually helpful; I was just looking for the platform-neutral partial redraw possibilities)

---

EDIT: having typed all that out, I realise there's something of a real example: PowerVR versus 3DFX. The former offered in theory much higher geometry rates through a process called tile-based deferred rendering, which required the programmer to track and bucket all geometry in a scene before submission. Whereas with the 3DFX one just see one polygon at a time. It's not exactly the same because the 3DFX was also generally considered to be better at filling polygons: the PowerVR lacked bilinear interpolation. So it was one type of looking better versus another type of looking better. The one that didn't really require any programming effort won.

Answer 2

Most sprite systems allow for sprites to overlap, generally with either the first or last sprite having priority over the others. If software allocates sprite resources in the required order of priority, this will avoid the need to have hardware manage priority in any other way. While a display system that requires sprites to be listed in left-to-right order might be able to display more sprites than one which allows them to be listed in any order, such a design would make it necessary to add some other means of controlling sprite priority. It would also require a lot of extra work by the main CPU.

A more interesting approach is used in the Atari 7800's MARIA chip. While that particular chip suffers from some design missteps, the overall approach is a good one. It has a specially-designed RAM with enough data to store a scan line and the ability to copy its contents to a shift register. On each scan line, the MARIA reads a list of sprite commands from memory and, after reading each command, reads the memory for one line of that sprite's data and copies it into the scan line buffer starting at the appropriate X position. This approach can accommodate either a large number of narrow sprites or a smaller number of wide sprites, without needing any per-sprite hardware.

Answer 3

I asked in Limiting factor on sprite sizes what the limiting resource is, and there were some good explanations about how memory bandwidth and the size of on-chip memory to store sprite data are both issues.

And these issues stay the same. In fact, your concept suffers even more from limited bandwidth. Storing character data (like on the C64) in a buffer just mitigates that issue - and even with a buffer the time isn't sufficient to read line data and resulting pixel data, thus the CPU gets cut of every 8th line (to fill the buffer).

One scan line is ~64µs with a visible length of ~52µs. A System using 1980s RAM chips - at least the kind that did make sense in home computers, hat a cycle time of ~350-450 ns, that means maximum access rate is two per microsecond. In a 6502 System that translates to one access for the CPU and one for Video. Or, if we clamp out the CPU we get two per microsecond.

So in a system where we let the CPU operate in parallel, this allows 52 bytes to be read per scan line, or a maximum resolution of 416 b&w pixels. Or less. The amount of data read can not be more or less as timing is set by the memory clock. So even if we somehow are able to load a transition list for each line, a transition can only happen at byte borders. So either the resolution is reduced to 52 pixel horizontally, or Spritescan only be positioned on multiples of 8. Not exactly allowing a smooth horizontal movement. Further sprite width can only be sized in multiples of 8.

Using the whole memory bandwidth for video would also just double the data rate, but not solve the basic issue - and result in either a separate video memory and slow access (see TI's TMS9918) or some ZX81 alike slow mode.

To make this work on a pixel level, you need way faster memory. Roughly 8 times faster, which would be like 60 ns RAM if the CPU should run in parallel (could be an 8 MHz 6502 now), or 120ns if the CPU gets stoped/fenced out. Both are note really a solution for that time frame.

I'd say the shortfall of the idea is, that you might have been thinking in pixel, where access is in bytes - and access time is quite limited.

No matter at what end you start to look at the idea, it all comes down to access rate - Just think, each entry in your transition table must be like 4 bytes at least (2 bytes X position and 2 bytes for sprite data start address). That's the same time as accessing data for 32 continuous pixels. Which of course, now can't be displayed, as the table entry is to be loaded. Having a long blank areas in front and after each sprite doesn't sound cool, does it?

And no, there is no time to load it before each line - after all, there are only 12µs or 12 byte loading times. That's barely enough to load the first transition data.

And so on.

---

Grandpa story: I did design a somewhat similar video system. The focus wasn't about sprites, but merging display buffers of arbitrary size in real time ... well, thinking of it, it sounds exactly the same :))

I solved it with real wide memory (32 Bit) and special fast RAM for the transition tables and a microprogram engine doing the data selection and blending (well, plus some bitbliting). In the end the project got scraped, as the hardware got way too expensive without really solving the problem.

---

Such a system will very soon use more memory bandwidth for management data and data manipulation than the whole picture data needs for display - which in turn is the the lower time limit it would take to compose it into a buffer (as it's the Memory bandwidth). And that's also the the solution to the problem - and why modern systems no longer use sprites - it's more versatile to have two buffers, one where the next picture is composed and one where the last composed one gets displayed from.