info-mac@uw-beaver (01/14/85)
From: Hackerjack <Palevich%hplabs.csnet@csnet-relay.arpa>
An Explanation of QuickDraw's Region's Internal Representation
One of Quickdraw's nicest features is the ability to construct a
region of arbitrary shape, then force graphics to be drawn only inside
that region. This ability is one of the key reasons that the
Macintosh window system is so pretty.
Long time Info-Mac readers might remember that I asked about Regions a
while back. The consensus was that they were some kind of run-length
encoded pixel map, but the exact representation was un-documented.
Using MacPascal and a couple of spare hours, I think I have figured
out the internal format for regions. This information is of use to
people attempting to construct, manipulate, or render QuickDraw-
compatable graphics on other machines. It's also useful to know how
regions are stored because it gives the Macintosh application
programmer some idea as to the storage cost of various region shapes.
As with any hobbiest probing of an undocumented feature of a complex
system, this information may not be completly accurate.
Regions are represented as a byte string. From the QuickDraw manual,
we know that regions are stored as follows:
0,1 : length of region's data, in bytes (at least 10)
2,9 : bounding rectangle of the region (0,0,0,0 means empty region)
10..length-1 : mask-data (empty if region is simply the boundry rectangle.)
If memory usage were not an issue, the region could be represented as
a mask-bitmap, with 1 bits implying that it was OK to write data in
the corresponding pixel, and 0 bits implying that the corresponding
pixel should not be changed. Regions are, in fact, encoded in such a
way that they can be easily decoded into such a mask-bitmap.
The mask-data is a run-length-encoded description of the changes in the
mask-bitmap as it is traversed from top to bottom. The general format is:
<mask-data> ::= {<line-data>}* <marker>
<line-data> ::= <line-number> {<change-run>}* <marker>
<change-run> ::= <start-of-run> <end-of-run + 1>
<marker> ::= $7fff
Marker, line-data, start-of-run, and end-of-run are all 2-byte signed
integers. The line-number data are in ascending order, as are the
start-of-run and end-of-run data. Here is an example:
Let's assume the region looks like this:
x
19 20 21 22 23 24 25 26 27 28 29 30 31 32
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
19| | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
20| |[]|[]| | | | | | | | |[]|[]| |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
y 21| | |[]|[]| | | | | | | |[]|[]| |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
22| | |[]|[]| | | | | | | |[]|[]| |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
23| | |[]|[]| | | | | | | |[]|[]| |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
24| | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
The cells filled with [] are those which are inside the region. This region
is so small that it is unlikely that it would actually be used, but it makes
a good example.
The data representation of this region would be, in decimal words:
48 ; the length of the region, in bytes
20,20,32,24 ; the bounding rectangle
20 ; the first line of changes
20,22 ; the first change (pixel collumn 20-21 turn on)
30,32 ; the second change (pixel collumn 30-31 turn on)
$7fff ; the end-of-line marker
21 ; the second line of changes
20,21 ; the first change (pixel collumn 20 turns off)
22,23 ; the second change (pixel collumn 22 turns on)
$7fff ; the end-of-line marker
24 ; the third line of changes
21,23 ; the first change (pixel collumns 21-22 turn off)
30,32 ; the second change (pixel collumns 30-31 turn off)
$7fff ; end-of-line
$7fff ; end-of-region
Pretty nifty, huh? This data compression scheme is very good for dealing
with the intersection-of-rectangles kinds of shapes that come up so often
in an overlapping-window environment. It's also pretty cheap to decode it
at the lowest level of a bit-blt routine. I would create a scan-line
buffer and xor the runs to determine what the current line's mask is.
Finally, notice that it is possible, with some extra effort, to use this
list in reverse-scan-line order, which might be useful for the occasional
reverse-scan-line-order blt.
Jack Palevich
-------info-mac@uw-beaver (02/01/85)
From: Andy Stadler c/o <Hoffman.es@XEROX.ARPA>
Congratulations to Jack Palevich for decoding the QuickDraw region
structure. This is the same region structure which Atkinson, Jobs, and
Apple had bragged on and on about, and are hoping to patent....
There is one thing I hope I can clarify. Close reading of the QuickDraw
manual reveals that it uses a non-standard row/column numbering system.
Instead of numbering each row and column of bits, the numbers are
assigned to the "infinitely thin" lines between them. So the example
region should have been drawn like this (top portion only):
x
1 2 2 2 2 2 2 2 2 2 2 3 3 3 3
9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
19 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | |
20 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
y | |[]|[]| | | | | | | | |[]|[]| |
21 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | |[]|[]| | | | | | | |[]|[]| |
etc.
Note that this permits a cleaner definition of <change run>:
<change run> ::= <left-border-of-run> <right-border-of-run>
You see, the two numbers are actually coordinates of the
"infinitely-thin" walls of a rectangle which *encloses* the bits of
interest. As far as the Y-coordinates, I suppose you could look at the
numbers as saying, "below this line, make the following changes...."
As far as the compression goes, you are right, and this is great for
rectangles. It fails on complex shapes (imagine encoding a circle!). I
wonder if there are any other encoding forms for other shapes? Anyone
want to try looking?
Andy Stadler
Arpanet: Andy Stadler c/o <Hoffman.es@Xerox.ARPA>info-mac@uw-beaver (02/01/85)
From: Bob Cralle <cralle@lll-crg.ARPA> Why not encode a circle using Minsky's algorithm?k x(n+1) = x(n) - k y(n) y(n+1) = y(n) + k x(n+1) [x(n+1) is intentional, else spiral] k is small const. Negative power of 2 is nice. x(0) = radius (y(0) = 0). This scheme makes best circle (actually it's an ellipse). I found that it also makes nice ellipses if 1st k = ke & 2nd k = k/e, where e is the eccentricity. Pretty compact encoding: center of circle & small const. Regards, Bob p.s. I wrote a couple of short notes on this subject. If interested I will send.