Andreas Raab asks:
>Can you explain what 'the QuickDraw region algorithm' is/does?! Any pointers
>would be very much appreciated.

The primary purpose of a region is as a complex clipping mask that can be
succinctly encoded and readily manipulated with various Boolean operations.

You could check the patent, but this is the basic idea of encoding:

QD regions use a "inversion points" table to encode a region.  Effectively,
the occurance of an inversion point toggles the "pen up"/"pen down" state
of the mask.

The neat thing about the algorithm is that previous inversion points are
kept while scanning down the image from top to bottom - that way, only
_changes_ to a scanline's inversions compared to the previous scanlines are
needed.

For instance, the region:

******
******
**  **
******
******

is encoded:

(some overhead....)
0033 (total byte size of region, including size and bounding box)
0000 0000 0005 0006 (bounding box)
(...now for actual region encoding)
0000 (y index) 0000 0006 7FFF (eol)
0002 0002 0004 7FFF (notice didn't need 0 & 6!)
0003 0002 0004 7FFF (removing those two inversions)
0006 0000 0006 7FFF (last line, turn off all remaining inversions)
7FFF (done indicated by max y coordinate)

...at 17 words of region data plus some overhead.

A rectangular region doesn't require any data beyond the bouding box.  A
hack to compute the inversion points is to XOR an image with itself shifted
one pixel to the right, then XOR the result with itself shifted one pixel
down.  Any remaining pixels are the inversion points.

The more common and unencumbered method for a region is the y-sorted list
of x-sorted non-overlapping rectangles: the above region in Steinhart would
instead encode as:

0000 (y start) 0001 (one span) 0000 0005
0002 0002 0000 0001 0004 0005
0003 0001 0000 0005
0005 0000

...at 16 words of region data.  While this is smaller for this particular
example, in most cases the QD region is more compact.

The nastiest case for both algorithms is the "1-bit checkerboard" which
used to blow the 32K limit the Mac originally had for the region size,
since every pixel ends up being an inversion, or a 1-bit-square rectangle.

-- Duane