The Long View
The Long View
Regions
Programmers drew their programs on the Macintosh screen using the Quickdraw library. Like other graphics libraries at the time, it was vector-oriented, drawing lines, rectangles, arcs and other geometric shapes. Lines were defined by their endpoints, circles by radii and centers, polygons by their vertices. So how can you describe an irregular shape? Irregular shape are used for clipping. When a program draws the contents of a window, it is common for the object being drawn to be larger than the visible area of the window. When the program draws the object, it will try to draw outside its window. Clipping the drawing at the edges of the window was a required part of the Macintosh design, and programmers didn’t have to worry about it. The Macintosh window manager kept track of the visible space in a window, and clipped the drawing to the edges of that shape.
Windows are usually (but not always) rectangular, so you might hope that if you only allowed rectangular windows you would only have to clip drawing to rectangular window shapes. Back in the old days, clipping of vector drawings to rectangular windows was done with a simple algorithm invented by computer graphics legends Ivan Sutherland and Gary Hodgman in 1974, and was described in the classic Newman and Sproull book “Principles of Interactive Computer Graphics”, published in 1979. That method preserved the integrity of polygons when clipped against the edges of a rectangular window. But if windows are allowed to overlap each other on the screen, the visible area of windows that are not frontmost may not be rectangular, because they are overlapped by part of other windows. Early windowing systems, like the ones used on the Xerox Alto systems seen by Apple engineers in the famous 1979 visits, had to draw all the overlying windows whenever they refreshed the content of any partially visible window. The Macintosh had no hardware graphics acceleration (to keep hardware development cost down), so drawing on the screen was done in software on the CPU. Graphics could be a bottleneck, so it was important to optimize drawing as much as possible. When preparing the Quickdraw library, it was critical to minimize redrawing stuff that didn’t need redrawing. In writing Quickdraw, Bill Atkinson needed to put an emphasis on Quick. It was important to have a way to describe an arbitrary shape, and clip drawings to it.
Regions were the solution. The idea was Atkinson’s own, and it was patented by Atkinson and Apple in US patent number 4,622,545, filed in 1982.
Keeping Secrets
These days, Apple is known as a company that has lots of secrets, and can keep them to themselves. It wasn’t always so. In fact, Apple’s original corporate style was completely open. In the Apple II days, Apple shared every detail of the hardware and software design with their customers. This was a successful strategy, because it facilitated a very supportive third party economy that built boards and software for the Apple II. But there was a down side. In the early 1980’s, while the Lisa and Macintosh projects were making progress, a series of companies made blatant copies of the Apple II and openly marketed them as such. Apple eventually resorted to legal action. A successful suit against the original cloner Franklin in 1983 became a turning point in the computer industry generally, but even more so for Apple. This must have had a big effect on thinking at Apple, at least among the leadership; maybe not so much among the engineers.
The Lisa project was secretive, but I’m not sure how to interpret that. There was not a lot of information released on how to write a program for the Lisa, or how to build a board that would work in it. Lisa was not aimed at hobbyists, and it was expected that customers buying the machine would be satisfied the office software suite that came with it. But the Lisa did have a classical expandable architecture, and there were apparently plans to make programming tools available. If it had been more successful, I think we would have seen the release of much more information over time. Also, the Lisa was not designed and built by a bunch of ex-Apple II engineers, but mostly by outsiders who had been brought to Apple from the more serious and commercial world of minicomputers.
The Macintosh team had mostly come from various parts of the Apple II operation. They did not intend to keep secrets about the design of the Macintosh or its software. Even before the Macintosh was finished, the effort began to document the operating system for programmers. Excellent writers like Caroline Rose and Chris Espinosa wrote Inside Macintosh, a complete description of the operation of the operating system. It included details about the layout of a Macintosh program in memory, and all the data structures that were used by the operating system to represent windows, files, and other key objects. Early drafts of the chapters from Inside Macintosh were distributed to developers with the Software Supplements, and later became the famous 3 volume set that was sold by Addison-Wesley.
On this background, the secrecy associated with Regions seemed out of place. Regions were not well documented. Inside Macintosh told you how to make and use regions, but it didn’t explain much about the data structure that represented them.
Making Regions
But What is this Region of Which You Speak?
The implementation of regions was not revealed in the documentation, but there were plenty of ways to find out. One way was just to disassemble the ROMs. That was pretty hard work, and if you didn’t want to do it, you could read a magazine article by somebody who did it. MacTutor was a great source of information for this kind of thing, and they published a couple of good articles, one in the October issue of vol. 3 (1987) and one in the September issue of vol. 4 (1988). I don’t know when it became available, but there is also the patent, filed by Apple and Atkinson. It makes great reading. This year, the original source code for Quickdraw was released, so you can just read the code that does everything. Or, you could just do a dump of data in a region data structure, and try to figure it out.
Most of computer graphics is geometry. The traditional approach is to imagine a continuous geometric plane, independent of the screen’s pixels. Then solve for the intersections between shapes and the boundaries of a clipping rectangle, and calculate new clipped shapes. Then find the coordinates of the pixels nearest to the line end points and draw the clipped lines. Programmers want to do things this way, because the geometry is independent of the pixel density of the screen (or printer). Resolution independence is especially all the rage right now, because the density of pixels on various devices we program for vary so widely. But it was just as popular in the 1970s and 1980s for exactly the same reason. The pen plotters, Tektronix storage tube graphics displays, Evans and Sutherland graphics terminals and a the host of other graphics gadgets in use at the time had resolutions that varied enormously. People chose solutions that didn’t depend too much on display details.
Atkinson took a different tack when writing the Quickdraw library. The Macintosh’s resolution was fixed. It and its printer were designed to work together, and everything was based on a graphics world in which coordinates were specified to the nearest 1/72 of an inch (a printer’s point). On the printer, lines between points could be drawn at a higher resolution but the end points of the line could only be specified at the screen resolution. This simplicity about how graphics would be rendered allowed Quickdraw to do things differently, and much more efficiently.
There was no separate graphics hardware. The screen’s buffer was stored in the Macintosh’s main memory as a block of bits. Set a bit to a 1 and the pixel turned black. Clearing a bit it turned the corresponding pixel white. Note this was the opposite of most bitmapped systems at the time and reflected the black-on-white nature of the Macintosh graphical world. The bits representing the screen were in row-order. That is, the 0th position corresponded to the upper left, and the first set of 512 bits represented the topmost single horizontal line of pixels on the screen. Subsequent rows of pixels represented the rest of the lines, from top to bottom. These were called scanlines, because the electron beam in the crt scanned horizontally, drawing each line on the screen, left to right, and top to bottom. The Macintosh’s screen coordinate system was isomorphic with the process that displayed the screen, one line at a time, 342 lines every 1/60th of a second.
Was this on Purpose?
One thing I always wondered about was the unusual arrangement of calls to start and end a region. You start a region using OpenRgn, which takes no parameters. That call puts Quickdraw in a region-saving state, at least for that GrafPort (usually corresponding to a window). By default, subsequent calls do not draw anything on the screen. That means that somewhere, Quickdraw is saving all the information about the shapes you draw, but you have no pointer to those data. When you are done defining the region, you call CloseRgn, and pass it a handle into which to return the region structure. But you can’t just pass it any old handle. It has to be a pre-allocated region. Why? If it is creating a region somewhere in your program’s heap, why not just attach that spot in memory to an uninitialized handle? Looking at OpenRgn and CloseRgn in the Quickdraw source clarifies that a lot. Drawing while a region is open adds data to a list of reversal points, but not a region handle. That data structure is allocated in the program’s heap, and its handle is saved in rgnBuf, which is a Quickdraw global variable. The fact that Quickdraw is making a region is stored by setting a field in the GrafPort structure, rgnSave, to true (nonzero). When you are done, CloseRgn doesn’t return the handle at rgnBuf to you. It packs the region information into a proper Region, and puts that in the region you pass in. Then it disposes the handle it held at rgnBuf. Here is the weird part. RgnBuf is a Quickdraw Global and not a field in the GrafPort, but rgnSave is. That means that if you start saving a region in one Window, and then switch to drawing in another, the second window doesn’t know that you are saving a region. If you start saving a new region in the second window, it clobbers the contents of rgnBuf, causes a memory leak, and messes up future things that happen in the first window. There’s even a warning in Inside Macintosh saying you should not start a new region while one is in progress. But Inside Macintosh also says that the data are saved in rgnSave, not in rgnBuf, and in the source code, rgnSave is declared to be a long said (in a comment) to be a Handle, not a flag. But the source code uses it otherwise. Was there a change in plan? Maybe there was some indecision about whether region state ought to be stored with a GrafPort or in the Quickdraw Globals, which are in the program’s scope. It seems to me that if both rgnSave and rgnBuf were in the GrafPort, everything would have been ok. But rgnBuf was an undocumented Quickdraw global. Maybe things were changed to make it harder for us to see into the machinery that made regions.
What is so Great about Regions?
What were regions for? There wasn’t all that much call to frame or paint regions. One good use was calculating the overlap or lack of it among arbitrary shapes. UnionRgn and SectRgn, XorRgn, and DiffRgn did this kind of thing. You could also check to see if a point was inside or outside a region using PtInRgn. But the most common use was as a clipping mask. Every time you drew something in a window on the Macintosh, it got clipped against at least 2 regions. That had to go fast if Quickdraw was going to live up to it’s name. Regions were a fast way to do clipping. Way faster than the geometric methods like the Sutherland and Hodgman style geometric method. And, you could clip anything with it. Not just geometrically defined shapes, but also bitmap sprites, glyphs and characters. This was because clipping was done on the Macintosh at the time of raster conversion.
The low level algorithms for approximating lines and geometric shapes on bitmapped system had been worked out in the 1960s, not so much for crt screens, but for plotters. The Calcomp drum plotter was popular then. It had a pen that moved horizontally, and paper was on a drum, so that vertical lines were made by rotating the drum. Both directions had fixed step sizes. To draw a diagonal line, one had to move the pen horizontally by so many steps, and rotate the drum by so many steps. Of course, one could lift or lower the pen, so it was possible to move to some position, put the pen down, and move to a new position. The result would be a line between positions. But one had to program every movement to every position along the line, by sending signals to the stepping motors that moved the pen and the drum. For lots of angles of lines, there is no integral ratio of horizontal to vertical steps so every position along the pen’s route has to be calculated. A general method for specifying the positions of the motors that should be visited along the length of a line were worked out by Jack Bresenham in the early 1960’s and published in the IBM systems journal in 1965 (vol. 4 no 1, p25-30). An elaboration for drawing circles was published in 1977. A great thing about these algorithms was that they went through the bitmap, line by line, and determined what pixels should be drawn and which not, to draw the portion of the shape that ought to be on that line. They were local in operation, as opposed to the more global approach of finding the intersections of one geometric shape with another. Because regions gave a line-by-line map of the region on a bitmap, it was easy to use a scanline in a region to make a mask when doing raster conversion on a line or other shape, and show only the pixels that are in the region on that line.
What Happened to Regions?
Where are regions now? Of course Apple still owns regions and they are still a part of the Carbon library. They work the same as the always did. Of course everything having to do with regions is marked as deprecated. What isn’t? They still work; turn off the warnings and go ahead. But are there regions in Cocoa? If not, how is clipping done there? Is there an NSRegion I can create and use to clip my drawing? Well, no, so far as I can tell. When you update your view using NSView’s drawRect message, you don’t get an update region to draw into, but a rectangle. Maybe rectangles are efficient for windows given the backing store method now using to update the screen. I just update my entire window’s contents into the backing store, and the widowing system can worry about the most efficient way to put that on the screen, given overlap with other things. But what if I want to clip my drawing myself against an arbitrary shape? Cocoa was previously NeXTSTEP, which was not Apple, and Apple had a patent on regions. Could there be regions in there somewhere? I think so. The Cocoa Drawing Guide tells you how to use a bezier path to define your clipping region (their term), and shows examples that could have come right out of Inside Macintosh. Define your shape using bezier paths, and then use NSBezierPath’s addClip message. Because bezier paths can be appended with about any shape, it turns out to be able to do all the same stuff. How does it work? How fast is it? Is there a region down there at the scan conversion level? I don’t know. Apple these days is much better at keeping secrets. Maybe Apple will release the source code for NSBezierPath one of these days. Yeah, right.
-- BG (basalgangster@macGUI.com)
Sunday, August 29, 2010