Was 1991's Hellcats the first instance of incremental screen updates?

Question

In case you have never seen it, 1991's Hellcats was a seminal release on the Mac. It ran at full 8-bit color and could, on a newish machine, drive three 1024x768 screens at the same time. Nothing on the Mac or PC came remotely close.

I recall when I learned how the magic worked... I got up from the game for a moment and returned with the "screen saver" (ahh, the old days) was running. I flicked the mouse to clear it and unpause the game, and noticed the only part of the screen that updated was the horizon. It was reaching high speeds by carefully designing the screen so only certain portions would change as the aircraft moved, and then updating only those portions.

Now you can imagine, in 1991 this was no trivial task on its own. Graphics cards were generally frame buffers driven by the CPU, actual accelerators were just coming to market. So I was always curious how he managed this trick.

Long after I had an email exchange with the author and he explained it. He set aside two screen buffers in memory, and drew into alternate frames. He then compared the two and sent only the diffs over the bus to the card. Because the CPU was much faster than the bus, this provided greatly improved performance.

He also noted that the idea came to him on the SPARC1. This platform had the general problem of having a fast CPU but with a slowish bus. His first app spun a cube at 60 fps. He ended up doing Hellcats on the Mac because it shared this limitation, whereas PCs of the era generally used 320x240 for color, and the advantage of this technique was washed out.

So, the question..

I suspect that this idea of incremental updating may pre-date Mr. Parker's 1989-ish Sun version. Does anyone know of examples of this being used earlier?

Answer 1

Since my interpretation of the question differs from other answers posted, I think the primary topic is inter-frame video compression. It's about historical precedents for a pipeline that starts with the complete contents of frame n and frame n+1 in some representation, determines the differences between them, and communicates only the differences to a third party. That's as distinct from doing active calculation on only portions of an image because it is innately true that whatever isn't touched will be preserve — such as a video game that redraws only the moving sprites — because there are two complete frames, and their entirety is inspected to calculate a diff without a priori knowledge.

In which case, I'm going to nominate “Transform coding of image difference signals”, M R Schroeder, US Patent 3679821, 1972., which emanated from Bell Labs, as the first public reference I can find to digital image differencing; as per the name it's most heavily invested in transforming the differences for transmission, but "worthwhile bandwidth reduction" is the very second advantage it proposes in its abstract (emphasis added):

Immunity to transmission errors and worthwhile bandwidth reduction are achieved by distributing the difference signal, developed in differentially coding an image signal ... and other economies are achieved, particularly for relatively slowly varying sequences of images.

The filing date for the patent is given as the 30th of April 1970; it lists prior art but is the first thing I can find that is explicit about processing a digital signal rather than being purely analogue — in column 2, near the very bottom of the page and rolling over into column 3:

Moreover, the signals may be in analog form although preferably they are in digital form to simplify subsequent processing. Assuming for this illustrative embodiment that the signals are in digital form they are [pulse-code modulated].

Answer 2

The idea is as old as memory-mapped display hardware is. After all, memory bandwidth was for most of the time the limiting factor. Every character based text screen only updates what needs to be changed and similar each and every game - maybe with an exception of the Atari VCS 'Racing the Beam' :)

Similar double buffering. As soon as a machine supports multiple pages it's the best (or even only) way to generate a flicker free and complete update when game logic runs asynchrone to the screen refresh.

The double buffering of complete renderings and only transferring changed parts into a display buffer only makes sense in an environment where the CPU (and local CPU accessible memory) is way faster than access to screen memory, as each transfer needs at least two local memory access cycles (for comparison) instead of one access as with a simple transfer.

And it has been done on mainframes already in the late 1970s (*1) for text screens. Applications are usually form based, so even accessing/handling different data sets, a good part of the screen stays the same, so many screen handlers offered modes to only transfer the data section by default. Similar terminals offered modes to only return changable data.

For one, rather large application we even increased that by keeping a complete image of the terminal screen in main memory and used a terminal mode that only returned changed field content. Similar, only data that has been changed on the host side since the last input was transferred toward the terminal. In average this reduced an input transmission to less than 100 bytes, while average output was less than 500 bytes instead of more than 3 KiB for a whole 80x25 screen (including format control).

The effect was quite notable - even on 240 kBit inhouse hookups. In addition the terminal also didn't clear the screen when updating, but updated in place, giving an even greater impression of quick response :))

Bottom line: "Im Westen nichts Neues"

---

*1 - Personal experience, I bet others had done that already before.

Answer 3

Basically all graphical user environments (MS Windows [1985], X11 [1984], Atari GEM [1984] send a running application a list of screen regions that need to be re-drawn when one of this application's windows is un-obscured (This list of screen regions is typically attached to some sort of WM_PAINT message).

It is up to the application wether it goes the hard way and only updates the parts of its windows that actually need an update, or wether it decides to go easy and collapses all these regions and redraws all of its window area.

So this standard technique is built in practically all WIMP environments that showed up in the early 1980s.

Outside WIMPS, double buffering has obviously always been a standard technology for games, especially on computers that didn't have hardware sprites (move partial sprite-sized window background to offscreen buffer, display software sprite, move background back from offscreen buffer). Such offscreen buffers could be as large as a screen and be switched to the display via one single register transfer (video circuitry that can display more than one framebuffer, for example Atari ST) or much smaller for computers with a fixed framebuffer address like the ZX Spectrum.

Answer 4

It definitely predates 1989, e.g. Apple II games like Bolo (1982) and Star Maze also used double buffering with incremental updates.

The idea is pretty obvious once you have hardware that can do double buffering, so I wouldn't be surprised if it was used much earlier already.

Answer 5

An interesting example, or possibly variation, of this is the Amiga "ANIM" format used by Deluxe Paint. It only stores changes between frames, rather than whole frames. It first appeared in 1988.

Differences between frames were determined by the application creating the file. In the case of Deluxe paint it was based on user input, rather than examining frame-to-frame differences, so could sometimes produce very large files even though the visible changes were relatively small.