[dkislyuk]

From Walter Isaacson's _Steve Jobs_:

> One of Bill Atkinson’s amazing feats (which we are so accustomed to nowadays that we rarely marvel at it) was to allow the windows on a screen to overlap so that the “top” one clipped into the ones “below” it. Atkinson made it possible to move these windows around, just like shuffling papers on a desk, with those below becoming visible or hidden as you moved the top ones. Of course, on a computer screen there are no layers of pixels underneath the pixels that you see, so there are no windows actually lurking underneath the ones that appear to be on top. To create the illusion of overlapping windows requires complex coding that involves what are called “regions.” Atkinson pushed himself to make this trick work because he thought he had seen this capability during his visit to Xerox PARC. In fact the folks at PARC had never accomplished it, and they later told him they were amazed that he had done so. “I got a feeling for the empowering aspect of naïveté”, Atkinson said. “Because I didn’t know it couldn’t be done, I was enabled to do it.” He was working so hard that one morning, in a daze, he drove his Corvette into a parked truck and nearly killed himself. Jobs immediately drove to the hospital to see him. “We were pretty worried about you”, he said when Atkinson regained consciousness. Atkinson gave him a pained smile and replied, “Don’t worry, I still remember regions.”

[JKCalhoun]

With overlapping rectangular windows (slightly simpler case than ones with rounded corners) you can expect visible regions of windows that are not foremost to be, for example, perhaps "L" shaped, perhaps "T" shaped (if there are many windows and they overlap left and right edges). Bill's region structure was, as I understand it, more or less a RLE (run-length encoded) representation of the visible rows of a window's bounds. The region for the topmost window (not occluded in any way) would indicate the top row as running from 0 to width-of-window (or right edge of the display if clipped by the display). I believe too there was a shortcut to indicate "oh, and the following rows are identical" so that an un-occluded rectangular window would have a pretty compact region representation.

Windows partly obscured would have rows that may not begin at 0, may not continue to width-of-window. Window regions could even have holes if a skinnier window was on top and within the width of the larger background window.

The cleverness, I think, was then to write fast routines to add, subtract, intersect, and union regions, and rectangles of this structure. Never mind quickly traversing them, clipping to them, etc.

[duskwuff]

The QuickDraw source code refers to the contents of the Region structure as an "unpacked array of sorted inversion points". It's a little short on details, but you can sort of get a sense of how it works by looking at the implementation of PtInRgn(Point, RegionHandle):

https://github.com/historicalsource/supermario/blob/9dd3c4be...

As far as I can tell, it's a bounding box (in typical L/T/R/B format), followed by a sequence of the X/Y coordinates of every "corner" inside the region. It's fairly compact for most region shapes which arise from overlapping rectangular windows, and very fast to perform hit tests on.

[JKCalhoun]

Thanks for digging deeper.

[gblargg]

The key seems to have been recognizing the utility of the region concept and making it fundamental to the QuickDraw API (and the clever representation that made finding the main rectangular portions easy). This insulated QuickDraw from the complexity of windowing system operations. Once you go implementing region operations you probably find that it's fairly efficient to work out the major rectangular regions so you can use normal graphics operations on them, leaving small areas that can just be done inefficiently as a bunch of tiny rectangles. All this work for clipped graphics was applicable to far more than just redrawing obscured window content, so it could justify more engineering time to polishing it. Given how easy they were to use, more things could leverage the optimization (e.g. using them to redraw only the dirty region when a window was uncovered).

[rjsw]

I think the difference between the Apple and Xerox approach may be more complicated than the people at PARC not knowing how to do this. The Alto doesn't have a framebuffer, each window has its own buffer and the microcode walks the windows to work out what to put on each scanline.

[JKCalhoun]

Not doubting that, but what is the substantive difference here? Does the fact that there is a screen buffer on the Mac facilitate clipping that is otherwise not possible on the Alto?

[aaronharder]

More details here: https://www.folklore.org/I_Still_Remember_Regions.html

[lambdaone]

It allows the Mac to use far less RAM to display overlapping windows, and doesn't require any extra hardware. Individual regions are refreshed independently of the rest of the screen, with occlusion, updates, and clipping managed automatically,

[saghm]

Yeah, it seems like the hard part of this problem isn't merely coming up with a solution that technically is correct, but one that also is efficient enough to be actually useful. Throwing specialized or more expensive hardware at something is a valid approach for problems like this, but all else being equal, having a lower hardware requirement is better.

[al_borland]

I was just watching an interview with Andy Hertzfeld earlier today and he said this was the main challenge of the Macintosh project. How to take a $10k system (Lisa) and run it on a $3k system (Macintosh).

He said they drew a lot of inspiration from Woz on the hardware side. Woz was well known for employing lots of little hacks to make things more efficient, and the Macintosh team had to apply the same approach to software.

[atombender]

So when the OS needs to refresh a portion of the screen (e.g. everything behind a top window that was closed), what happens?

My guess is it asks each application that overlapped those areas to redraw only those areas (in case the app is able to be smart about redrawing incrementally), and also clips the following redraw so that any draw operations issued by the app can be "culled". If an app isn't smart and just redraws everything, the clipping can still eliminate a lot of the draw calls.

[rsync]

Displaying graphics (of any kind) without a framebuffer is called "racing the beam" and is technically quite difficult and involves managing the real world speed of the electron beam with the cpu clock speed ... as in, if you tax the cpu too much the beam goes by and you missed it ...

The very characteristic horizontally stretched graphics of the Atari 2600 are due to this - the CPU was actually too slow, in a sense, for the electron beam which means your horizontal graphic elements had a fairly large minimum width - you couldn't change the output fast enough.

I strongly recommend:

https://en.wikipedia.org/wiki/Racing_the_Beam

... which goes into great detail on this topic and is one of my favorite books.

[ehaliewicz2]

It definitely makes it simpler. You can do a per-screen window sort, rather than per-pixel :).

Per-pixel sorting while racing the beam is tricky, game consoles usually did it by limiting the number of objects (sprites) per-line, and fetching+caching them before the line is reached.

[scripturial]

I remember coding games for the C64 with an 8 sprite limit, and having to swap sprites in and out for the top and bottom half of the screen to get more than 8.

[peter303]

Frame buffer memory was still incredibly expensive in 1980. Our labs 512 x 512 x 8bit table lookup color buffer cost $30,000 in 1980. Mac's 512 x 384 x 8bit buffer in 1984 had to fit the Macs $2500 price. The Xerox Alto was earlier than these two devices and would have cost even more if it had a full frame buffer.

[sroussey]

Wasn’t the original Mac at 512 x 342 x 1bit?

[mkl]

Yes: https://512pixels.net/2025/05/original-macintosh-resolution/

There was a discussion here a couple of weeks ago (with a typo in the title): https://news.ycombinator.com/item?id=44110219

[jecel]

The Alto created the image from a display list, like the Atari 800 or the Amiga. So you could have a wider rectangle on most of the screen for pictures and a narrower rectangle at the bottom for displaying status. It was not up to showing overlapping windows. Nearly all applications just set things to one rectangle, having a frame buffer in practice. This was the case for Smalltalk, which is where Bill saw the overlapping windows. One problem is that filling up the whole screen (606x808) used up half of the memory and slowed down user code, so Smalltalk-72 reduced this to 512x684 to get back some memory and performance.

The Smalltalk-76 MVC user interface that the Apple people saw only ever updated the topmost window which, by definition, was not clipped by any other window. If you brought some other window to the front it would only then be updated. But since nothing ran in the background it was easy to get the wrong impression that the partially visible windows were being handled.

Bill's solution had two parts: one was regions, as several other people have explained. It allowed drawing to a background window even while clipping to any overlapping windows that are closer. But the second was PICTs, where applications did not directly draw to their windows but instead created a structure (could be a file) with a list of drawing commands which was then passed to the operating system for the actual drawing. You could do something like "open PICT, fill background with grey pattern, draw white oval, draw black rectangle, close PICT". Now if the window was moved the OS could recalculate all the regions of the new configuration and re-execute all the PICTs to update any newly exposed areas. If the application chose to instead draw its own pixels (a game, for example) then the OS would insert a warning into the app's event queue that it should fix its window contents.

In parallel with Bill's work (perhaps a little before it) we had Rob Pike's Blit terminal (commercially released in 1982) which added windows to Unix machines. It had the equivalent of regions (less compact, however) but used a per window buffer so the terminal would have where to copy newly exposed pixels from.

[mjevans]

Reminds me of a GPU's general workflow. (like the sibling comment, 'isn't that the obvious way this is done'? Different drawing areas being hit by 'firmware' / 'software' renderers?)

[heresie-dabord]

Bill Atkinson, all smiles as he receives applause from the audience for his work on Mac Paint: https://www.youtube.com/watch?v=nhISGtLhPx4

[JKCalhoun]

That's a great video. Everything he does gets applause and he is all (embarrassed?) grins.

[rezmason]

I like how he pronounces "pix-els", learning how we arrived at our current pronunciation is the kind of computer history I can't get enough of

[pducks32]

Would someone mind explaining the technical aspect here? I feel with modern compute and OS paradigms I can’t appreciate this. But even now I know that feeling when you crack it and the thrill of getting the imposible to work.

It’s on all of us to keep the history of this field alive and honor the people who made it all possible. So if anyone would nerd out on this, I’d love to be able to remember him that way.

(I did read this https://www.folklore.org/I_Still_Remember_Regions.html but might be not understanding it fully)

[giovannibajo1]

There were far fewer abstraction layers than today. Today when your desktop application draws something, it gets drawn into a context (a "buffer") which holds the picture of the whole window. Then the window manager / compositor simply paints all the windows on the screen, one on top of the other, in the correct priority (I'm simplifying a lot, but just to get the idea). So when you are programing your application, you don't care about other applications on the screen; you just draw the contents of your window and that's done.

Back at the time, there wouldn't be enough memory to hold a copy of the full contents all possible windows. In fact, there were actually zero abstraction layers: each application was responsible to draw itself directly into the framebuffer (array of pixels), into its correct position. So how to handle overlapping windows? How could each application draw itself on the screen, but only on the pixels not covered by other windows?

QuickDraw (the graphics API written by Atkinson) contained this data structure called "region" which basically represent a "set of pixels", like a mask. And QuickDraw drawing primitives (eg: text) supported clipping to a region. So each application had a region instance representing all visible pixels of the window at any given time; the application would then clip all its drawing to the region, so that only the visibile pixels would get updated.

But how was the region implemented? Obviously it could have not been a mask of pixels (as in, a bitmask) as it would use too much RAM and would be slow to update. In fact, think that the region datastructure had to be quick at doing also operations like intersections, unions, etc. as the operating system had to update the regions for each window as windows got dragged around by the mouse.

So the region was implemented as a bounding box plus a list of visible horizontal spans (I think, I don't know exactly the details). When you represent a list of spans, a common hack is to use simply a list of coordinates that represent the coordinates at which the "state" switches between "inside the span" to "outside the span". This approach makes it for some nice tricks when doing operations like intersections.

Hope this answers the question. I'm fuzzy on many details so there might be several mistakes in this comment (and I apologize in advance) but the overall answer should be good enough to highlight the differences compared to what computers to today.

[II2II]

It's a good description, but I'm going to add a couple of details since details that are obvious to someone who lived through that era may not be obvious to those who came after.

> Obviously it could have not been a mask of pixels

To be more specific about your explanation of too much memory: many early GUIs were 1 bit-per-pixel, so the bitmask would use the same amount of memory as the window contents.

There was another advantage to the complexity of only drawing regions: the OS could tell the application when a region was exposed, so you only had to redraw a region if it was exposed and needed an update or it was just exposed. Unless you were doing something complex and could justify buffering the results, you were probably re-rendering it. (At least that is my recollections from making a Mandelbrot fractal program for a compact Mac, several decades back.)

[gblargg]

And even ignoring memory requirements, an uncompressed bitmap mask would have taken a lot of time to process (especially considering when combining regions where one was not a multiple of 8 pixels shifted with respect to the other. With just the horizontal coordinates of inversions, it takes the same amount of time for a region 8 pixels wide and 800 pixels wide, given the same shape complexity.

[duskwuff]

> But how was the region implemented?

The source code describes it as "an unpacked array of sorted inversion points". If you can read 68k assembly, here's the implementation of PtInRgn:

https://github.com/historicalsource/supermario/blob/9dd3c4be...

[giovannibajo1]

Yeah those are the horizontal spans I was referring to.

It’s a sorted list of X coordinates (left to right). If you group them in couples, they are begin/end intervals of pixels within region (visibles), but it’s actually more useful to manipulate them as a flat array, as I described.

I studied a bit the code and each scanline is prefixed by the Y coordinates, and uses an out of bounds terminator (32767).

[duskwuff]

It's a bit more than that. The list of X coordinates is cumulative - once an X coordinate has been marked as an inversion, it continues to be treated as an inversion on all Y coordinates below that, not just until the next Y coordinate shows up. (This manifests in the code as D3 never being reset within the NOTRECT loop.) This makes it easier to perform operations like taking the union of two disjoint regions - the sets of points are simply sorted and combined.

[giovannibajo1]

Uhm can you better explain that? I don’t get it. D3 doesn’t get reset because it’s guaranteed to be 0 at the beginning of each scanline, and the code needs to go through all “scanline blocks” until it finds the one whose Y contains the one specified as argument. It seems to me that each scanline is still self contained and begins logically at X=0 in the “outside” state?

[jajko]

Pretty awesome story, but also with a bit of dark lining. Of course any owner, and triple that for Jobs, loves over-competent guys who work themselves to the death, here almost literally.

But that's not a recipe for personal happiness for most people, and most of us would not end up contributing revolutionary improvements even if done so. World needs awesome workers, and we also need ie awesome parents or just happy balanced content people (or at least some part of those).

[1123581321]

Pretty much. Most of us have creative itches to scratch that make us a bit miserable if we never get to pursue them, even if given a comfortable life. It’s circumstantial whether we get to pursue them as entrepreneurs or employees. The users or enjoyers of our work benefit either way.

[kevinventullo]

Just to add on, some of us have creative itches that are not directly monetizable, and for which there may be no users or enjoyers of our work at all (if there are, all the better!).

Naturally I don’t expect to do such things for a living.

[1123581321]

Yes, and thankful for these. Good addition.

[richardw]

Survivorship bias. The guys going home at 5 went home at 5 and their companies are not written about. It’s dark but we’ve been competing for a while as life forms and this is “dark-lite” compared to what our previous generations had to do.

Some people are competing, and need to make things happen that can’t be done when you check out at 5. Or more generally: the behaviour that achieves the best outcome for a given time and place, is what succeeds and forms the legends of those companies.

If you choose one path, know your competitors are testing the other paths. You succeed or fail partly based on what your most extreme competitors are willing to do, sometimes with some filters for legality and morality. (I.e. not universally true for all countries or times.)

Edit: I currently go home at 5, but have also been the person who actually won the has-no-life award. It’s a continuum, and is context specific. Both are right and sometimes one is necessary.

[duskwuff]

That's not quite how I read the story. Jobs didn't ask Atkinson if he remembered regions - Atkinson brought it up.

[asveikau]

It's also a joke, and a pretty good one at that. Shows a sense of humor.

[bowsamic]

What is the dark lining? Do you think Atkinson did not feel totally satisfied with his labour?

And I don't think anyone said that that's the only way to be

[bluedino]

> In fact the folks at PARC had never accomplished it, and they later told him they were amazed that he had done so.

Reminds me of the story where some company was making a new VGA card, and it was rumored a rival company had implemented a buffer of some sort in their card. When both cards came out the rival had either not actually implemented it or implemented a far simpler solution

[alanfalcon]

An infamous Starcraft example also contains notes of a similar story where they were so humbled by a competitor's demo (and criticism that their own game was simply "Warcraft in space") that they went back and significantly overhauled their game.

Former Ion Storm employees later revealed that Dominion’s E3 1996 demo was pre-rendered, with actors pretending to play, not live gameplay.

[stevenwoo]

I got a look at an early version of StarCraft source code as a reference for the sound library for Diablo 2 and curiosity made me do a quick analysis of the other stuff - they used a very naive approach to C++ and object inheritance to which first time C++ programmers often fall victim. It might have been their first C++ project so they probably needed to start over again anyways. We had an edict on Diablo 2 to make the C++ look like recognizable C for Dave Brevik's benefit which turned out pretty well I think (it was a year late but we shipped).

[genewitch]

Diablo II is in my top 3 games of all time, i still play it all the time. Thanks for contributing so much fun to my life!

(for ref, diablo III is also in my top 3 :)

[stevenwoo]

I was only one of many programmers at Blizzard North + others at Blizzard and our parent company at the time, but you are welcome from me.

[selimthegrim]

What exactly did they do that was naive?

[mhh__]

Similar tale with propaganda and stats with asterisks missing about the MiG-25 leading to the requirements for the F-15 being very high.

[Grosvenor]

Michael Abrash's black book of graphics programming. They heard about a "buffer", so implemented the only non-stupid thing - a write FIFO. Turns out the competition had done the most stupid thing and built a read buffer.

I teach this lesson to my mentees. Knowing that something is possible gives you significant information. Also, don't brag - It gives away significant information.

Just knowing something is possible makes it much, much easier to achieve.

https://valvedev.info/archives/abrash/abrash.pdf

[bogantech]

> Turns out the competition had done the most stupid thing and built a read buffer

This isn't really stupid though as explained in the pdf

> Paradise had stuck a read FIFO between display memory and the video output stage of the VGA, allowing the video output to read ahead, so that when the CPU wanted to access display memory, pixels could come from the FIFO while the CPU was serviced immediately. That did indeed help performance--but not as much as Tom’s write FIFO.

VRAM accesses are contended, so during the visual display period the VGA circuitry has priority. CPU accesses result in wait states - a FIFO between the VRAM and the VGA means less contention and more cycles for CPU accesses

Why improve read performance though? Games accessing VRAM I presume would be 99% write. Perhaps it was to improve performance in GUIs like Windows?