PICT Rotation
Volume Number: 1
Issue Number: 12
Column Tag: C Workshop
PICT Rotation with Copybits 
By Robert B. Denny, Alisa Systems, Inc., MacTutor Editorial Board
Editors's Note: MacTutor is grateful for Bob's dedication in providing this column
after suffering a very bad broken arm (see x-ray above). We wish Bob a speedy
recovery. If you wish to write to Bob personally, we will gladly forward your cards
and letters to him.
A few years ago, I was studying the Smalltalk-80 language when I came across a
novel image rotation algorithm [see Goldberg & Robson, Smalltalk-80: The Language
and its Implementation (Addison Wesley, 1983), pp408-410]. It typifies the sorts
of things that result from applying mathematics to software design.
The C Workshop is due for some less advanced articles, so here's the first. It
serves two purposes: to illustrate a simple application which uses a runtime library,
and to demonstrate QuickDraw bit-maps and the powerful CopyBits() toolbox service.
We'll do this with an implementation of the image rotation algorithm.
A Simple Application
Most C language systems provide glass teletype simulation, where one or more
windows can act like TTY's via the "standard library" (stdio) calls such as scanf() and
printf(). This makes it possible, in many cases, to build and run C applications which
use text commands and output on the Mac.
If the stdio library permits access to the window record for the TTY window, you
can let the library open the window, then experiment with QuickDraw services on that
window. You don't have to start out with a "full-blown" application which uses event
loops, textEdit, etc. The thing to remember is that the run-time library turns C into a
high-level language which has easy access to the toolbox. In this column we use the
Consulair Mac-C system; most other systems have similar support in their libraries.
Here is the classic "Hello World" program in Mac-C, with added QuickDraw
commands to draw nested boxes in the glass teletype window:
#include "Lib:stdio.h" /* Normally required */
#include "Lib:MacDefs.h" /* Toolbox */
#include "Lib:QuickDraw.h
#include "Lib:Window.h
main()
{
Rect frame;
int j, k;
char buf[8];
printf("Hello world!\n");
for(j = 10; j < 100; j += 10)
{
k = 2 * j;
SetRect (&frame, 240 - k, 110 - j, 240+k, 110 + j);
FrameRect (&frame);
}
gets(buf); /* Wait for then exit */
} /* End of program */
In this application, the Mac-C library opens a glass teletype window for use as
stdout. It's the only window, so it's always the current "port". Thus, QuickDraw
operations will be performed on the contents of that window. You don't need direct
access to the window data. Here's what the screen looks like:
QuickDraw Bit Maps
A window is a special case of a QuickDraw port. Most QuickDraw services operate
on the " current" port as established by a call to SetPort(). In the above application,
the run-time library creates the window, and makes its contents the current port. By
the time main() is called by the library, the window contents are ready for drawing.
A port is described by a data structure called a grafPort. One of the components
of a grafPort is a small data structure called a bitMap. Contrary to common usage, a
bit map is not the memory area which contains the image bits (pixels). Rather, it
describes that area. The image is kept in a bit image.. In C, the definition of a bitMap
is:
struct __BM
{
char *baseAddr; /* -> bit image */
unsigned rowBytes; /* MUST BE EVEN */
Rect bounds; /* Boundary Rectangle */
}
#typedef struct __BM bitMap
The baseAddr field points to the memory address of the bit image. For ports
whose bit images are on the screen, baseAddr always contains the address of the screen
memory ($7A700 on 512K Mac). It is possible to "draw" into a bit image other than
the screen. Simply set up a grafPort with a bitmap pointing to your own bit image
area, make it the current port, and draw away. This is how the printing system
works; the image is drawn into a small bit image a strip at a time, and then
transmitted to the imagewriter. The same commands draw to any bit image.
The rowBytes field describes the geometry of the bit image, in particular, the
number of bytes that make up each row of the bit image. The value must be even; each
row must be made up of an integral number of 16-bit words. This seems to imply that
bit images must always be a multiple of 16 bits wide. This is not the case, as we'll see
now.
The bounds field establishes the actual dimensions of the bit image and the "local
coordinate system for the image. There is no restriction that the upper left corner of a
bit image must be at coordinates (0,0) or that the origin coordinates must be positive.
The dimensions of the bounds rectangle set the "logical" size of the bit image, as
opposed to the "physical" size indicated by rowBytes and the total size of the bit image
array.
It's possible to work with on-screen windows without coming into direct contact
with bitMaps. The image rotation algorithm uses the "blitting" service CopyBits() to
perform manipulations involving bitMaps. The image being rotated is kept in a screen
bit image so you can observe the rotation while it's in progress. Just remember that
the window record contains the grafPort which contains the bitMap, which describes
the "chalkboard" bit image.
Image Rotation Using CopyBits
Ever wonder how MacPaint can rotate images so fast? Rotation of an image by a
multiple of 90 degrees is a useful operation, and its easier than you might think. The
algorithm about to be described uses a clever sequence of bit transfer operations to
rotate a square image whose sides are 2n bits in length, for integral n. It can be
generalized to operations on arbitrary rectangles, as is done in MacPaint. Note how
MacPaint does not rotate about the "center" of an image.
The algorithm consists of a series of permutations on the image. The left and
right halves are swapped, followed by an exchange of the upper-left and lower-right
quadrants of the swapped image. Then the four quadrants themselves are permuted in
the same way, then divided into quadrants and the resulting sixteen cells are permuted,
etc. The process completes when the cell size has reduced to two by two bits.
If you wrote a routine to implement the above method literally, it would take
geometrically increasing time as the bit image size increased. Specifically, for an
image 2n bits on a side, it would take
npermutations = 1 + 4 + 16 + ... + 4n-1
to complete the rotation. This would render the algorithm a laboratory curiosity.
The amazing feature of the actual algorithm is its ability to perform all cell
permutations for a given cell size in parallel ! This means that execution time is
proportional to log2(n), where the image is 2n bits on a side. The penalty is that
storage is required for two additional bit images the same size as the image to be
rotated.
Figure 1 shows what it looks like when the Liberty Bell (Copyright 1984,
T/Maker Graphics, used with permission) is rotated as a 256 x 256 bit image. Each
pixel is mapped to a 2-pixel square on the LaserWriter used to produce MacTutor.
The rotation takes log2(256) =8 steps.
Now lets get down to business. Besides the image itself, the algorithm requires
two bit images the same size as the transform image. One, called mask, contains 1's in
the upper left quadrant of each cell, 0's elsewhere. The other, called temp is used for
scratch storage.
Each major step in a permutation is accomplished via a series of bit-transfer
(blit) operations involving the three bit images. On the Mac, blitting is done via the
powerful CopyBits() service, which can copy a bit image with coordinate translation
and size scaling. The major steps in a permutation are (1) swap left and right cell
halves, (2) exchange lower-right and upper-left quadrants of each cell and (3) refine
the mask in preparation for the next cell subdivision.
Figures 2, 3 and 4 show the bit transfers needed for the major steps of the first
permutation. Each bit transfer is a single CopyBits() operation. The gray areas show
the destination rectangles for each CopyBits(). Keep in mind that the destination is
clipped to the bounds in its bitMap.
Adventures With CopyBits()
The image rotation demo program described below makes heavy use of the
QuickDraw CopyBits() service. Success followed several adventures which I'll
describe. Well, I won't describe the first adventure ... I'm embarassed. The other two
adventures relate to the first blit of the mask refinement phase, where the entire mask
is copied and shrunk into the upper-left 128 by 128 bit quadrant (see Fig. 4).
First, I was relieved to discover that CopyBits() works when the source and
destination are the same bit image, as long as the destination Rect is to the left and
above the source Rect. Specifically, mask refinement step 1 takes a single CopyBits().
That's the good news.
Now for the bad news. I discovered another feature (read that as "bug") in
CopyBits(). Mask refinement starts by copying the entire mask into the upper left
quadrant. The image is reduced to one half its size. Most of the time.
The first permutation uses a mask with a single 128-bit black square in the
upper left quadrant, which should shrink to a 64-bit black square on the first