Let there be regions

What are regions exactly?

Short answer: The most important part which made Mac user interface possible.

Long answer: The regions, in the form as they are used in the original Mac, were invented by Bill Atkinson as solution to solving the problem of creating effective algorithms for masking drawing commands with arbitrary bitmap shapes, and performing geometric logical operations with them. There is a good article on macGUI, which gives a better backstory and technical explanation about what regions are from the user’s (or programmer’s) point of view:


Region operations simulated on paper, with inversion points indicated with dots (bottom-right region is not related to the other operations on the paper)

Regions in the QuickDraw

One interesting feature of regions is, that when a region is rectangular, it will always have fixed size (10 bytes), and its bounding box can be used as in rectangular clipping. This helps reducing sometimes drawing in complex regions to trivial rectangular blitting operations, which are much faster than ones requiring region masking for each scanline:

A simple rectangular clipping case, which does not require regions

However, the need for actual region operations comes up very quickly, when wanting to do anything that ends up being non-rectangular. For example, the test case we used at this point, was just to get union of two rectangles into region, and fill that with a solid pattern.

Region decompression and re-compression

In memory, regions are stored in sort of compressed format, with each scanline containing horizontal indices of the inversion points on that scanline. However, during operations, they need to be manipulated as points, with horizontal and vertical coordinate. To achieve this, the region is decompressed during the actual operations into a point buffer, where points from both source regions are added as needed by the actual operation. The resulting points from these operations are then sorted, and re-compressed into a new region. At this point, we do the sorting with slow bubble sort, which will be replaced by a more efficient Quicksort later.

Funny thing about InsetRgn is, that it takes a bit more complex way of performing the operation: For insetting, the region is actually getting inset twice, once for both axis, but the horizontal and vertical coordinates are flipped for the second inset, so the horizontal inset is actually ran *twice*.

Drawing the regions

After the complexity of geometric operations on regions, doing the actual drawing with them is pretty straightforward. The region image blitter is pretty similar to the rectangular blitter, but it takes up to three regions as arguments, which get expanded into horizontal scanline buffers during the drawing. Each of these buffers is updated on each vertical coordinate, and together they form a bitmask, which can be simply ANDed together and used to mask the transfer of source bits to the destination.

First attempt, not really working yet

Second attempt, little better but still fishy

After a few missteps, we finally got the region clipping to work nicely: