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?

  • 2
    Just to be clear: you're asking about incremental updates of the form "calculate the whole display, diff, and submit only the differences"? So e.g. the fact that Space Invaders updates each column of aliens in turn is a completely different thing because there's no comparison step. I guess the 'perform a diff' bit is the focus of the question? (Also: I'd always assumed the Parsoft titles were diffing an s-buffer, not a full-on frame buffer; did the author give any indication as to in-memory representation of the frames?) – Tommy Oct 24 at 17:35
  • Yes, its the diffing part. It would only really help when you hand bandwidth issues downstream of the drawing. – Maury Markowitz Oct 25 at 18:45
up vote 12 down vote accepted

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].

  • I agree with your interpretation of the question, and see also @Raffzahn's description of using the technique on terminals where reading from system memory is significantly faster than writing to the terminal screen through the serial port. – traal Oct 24 at 18:03
  • I wasn't completely sure whether the terminals Raffzahn mentioned would necessarily do an actual diff, or just keep a record of things that have changed. But fair enough, yes, my interpretation of the question may or may not differ as much as I think. To be clear, I wanted to explain why I'm adding an additional answer, not to critique anyone. Definitely read it as a comment about me, not about anybody else. – Tommy Oct 24 at 18:07
  • 4
    That's how curses works. It keeps two buffers, one for what is currently displayed on screen and a second for what what screen should be updated to display. When the terminal is updated, basically does a diff of the two buffers in order to minimize the number of bytes sent to the terminal. That can include deleting and inserting characters or lines if the terminal supports it. – Ross Ridge Oct 24 at 18:26
  • 1
    @RossRidge the earliest reference I could find for curses — and this is via Wikipedia, so apply a large pinch of salt — is Arnold, K. C. R. C. (1977). "Screen Updating and Cursor Movement Optimization: A Library Package". University of California, Berkely. So 1977, five years later than the patent I was otherwise citing. I'll try to trawl for earlier mentions. – Tommy Oct 24 at 18:29
  • Most excellent Tommy, this answers the question precisely and I will use that reference in the future. – Maury Markowitz Oct 25 at 18:48

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.

  • 2
    I concur. I wrote a few "full screen text" programs in the mid 1970s that only sent the differences to the asynch terminal (my critical test case was 300 bps dialup), determined by keeping 24x80 buffers and comparing them. I did not feel like I was inventing anything new. – dave Oct 24 at 22:43
  • 1
    But are these form-filling systems really diffing anything, or simply recording the changes? There's a difference between "user typed in field 10" and "look at entire display to see it was in 10". I guess I'm asking about the precise implementation, how did the block-mode terminals actually work? – Maury Markowitz Oct 25 at 18:47
  • Outch, @MauryMarkowitz, that would be a lengthy issue. Even more so as there are many different variations depending on manufacturer and model, beside the basic block mode ways. Block mode in it's most basic functionality means the host sends out a whole screen with field definitions for what parts are can be changed or not. Editing no happenes locally with the terminal controlling all cursor movement and so on. When done, the result gets send back. At that point it depends on what mode (and terminal) is used. ... and that is not only of interest to you, but requires way more than a comment. – Raffzahn Oct 25 at 19:00
  • Ok but more generally, in your example, were the changes noticed because it kept two complete screen buffers and compared them to see the changes? Or did it record the changes as they were made by writing down the location and then sending the commands needed to produce that? I realize this may be splitting hairs, and the terminology confusion adds to this. However, @dave example does seem to be precisely the same concept as Hellcarts – Maury Markowitz Oct 25 at 19:04
  • Well, @MauryMarkowitz, I'd like to say 'all of the above' :)) A screen is defined as a background with the attributes non non-changeable, non-field. It can contain text, which is only send out the first time. 'Atop' are fields, defined. They again can be user changable or not. When a screen gets sendback to the host, only the field get returned. That's default field mode. Some terminals now offer a changed field mode, where only fieds that got changed by the userwill be send back. To identify them, they area packed in a variable length format where each field is prefixed with an ID. – Raffzahn Oct 25 at 20:12

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.

  • WM_PAINT doesn't require double buffering. An application may either create a memory device context (MemDC), write to that, then copy the contents to the main DC, or the application can bypass the memory DC and write directly to the main DC. – traal Oct 24 at 21:20
  • @traal I didn't say that. A MemDC is double buffering in my book. You can obviously not make use of the offering the GUI makes to you and redraw the whole screen from scratch with every WM_PAINT. – tofro Oct 24 at 21:26
  • 1
    You have to explicitly create a MemDC if you want to double buffer. With or without the MemDC, there's no need to redraw the whole window, just paint the background of the region specified by the WM_PAINT message, then iterate through your controls, check which ones coincide with the region that needs to be repainted (in MFC, use CRect::IntersectRect()), and repaint just those controls. This may or may not be faster than double buffering but for sure it uses less memory. – traal Oct 24 at 21:50
  • Classic MacOS used regions for updated, the clever part was that regions did not have to be rectangular or contiguous so the absolute minimum number of pixels would be redrawn. See Folklore.org for a long article about regions. – Michael Shopsin Oct 25 at 14:35
  • @MichaelShopsin: I wonder whether the PARC system used anything similar to regions? The approach of being able to process intersecting regions so as to produce a single description of the area of the screen that should be affected by drawing operations is a vast simplification compared with having to examine a data structure containing all overlapping windows. – supercat Oct 25 at 15:41

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.

  • Again, it's not the double buffer, and not the incremental updates. It's the use of the double buffer to figure out what the increments are. I don't believe this was used in either of these games, and it's not clear why you would need to as the updates are all in main memory - is that true on the A2? – Maury Markowitz Oct 25 at 18:52
  • There's only a very small step from "only draw things that have changed" to "draw everything, but only send changes over a slow bus". If one of the main ingredients is "compare existing things, and only send changes over some slow channel", then please make that more obvious in your question. In that case, do the text updates on an IBM 3270 count? That would be 1971. Though it's text, and not graphics, and the application won't necessary double buffer both text screens. – dirkt Oct 26 at 7:15

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.

  • I looked into Autodesk's similar FLIC, but wasn't able to figure out when that appeared beyond being after 1989 but before 1993. So ANIM predates it for sure. – Tommy Oct 25 at 13:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.