Escher Sketch Pad.(computer graphics program)Edward H. Carlson.

The computer is a splendid toy for the mind. Play is nature's classroom, teaching adult and child alike about the possible and the impossible in this amazing universe we skate through. I hope you will join me over the next months in playing with the computer and the ideas that it can model for us.

This month we sketch some intriguing doodles. In later columns I will model the population explosion of castaways on a desert isle, help you invent planets in alternate solar systems, analyze the concepts that underlie management games--M.U.L.E. and Hammurabi, for example--relating them to economics, and help you build many other computer toys. Please write to me at Creative Computing if you have ideas you would like to contribute.

Escher and the Arabs

Among the many fascinating drawings of Maurits Cornelis Escher are some that tile all space with interlocking figures--angels and devils, birds and fish, horsemen, lizards, and various grotesque monsters. The figures not only fill plane space, leaving no gaps and by repetition extend to infinity, but often are related to one another by certain rotation and reflection symmetries.

Islamic artists (forbidden to represent life forms in their art) created many such tilings with purely geometric forms of intricate design. Escher in his travels studied the Arabic decorations of the Alhambra palace in Granada, Spain (the palace in which Isabella and Ferdinand met with Columbus and approved his plan to sail west to the Indies).

Grab pencil and paper and try to sketch a simple Escher-like drawing--maybe a side view of a cat standing with all four feet showing and legs intertwining with those of another cat, upside down and facing the other way. You find yourself struggling to interlock the figures properly. Now load the program in Listing 1 and draw on the screen. Automatically the figures related by symmetry to the one you are drawing appear on the screen so you can detect any gaps and overlaps immediately. Unless you are somewhat artistic and very patient, you may not produce a satisfactory Escher-like interlocking drawing at all.

OK then, dream you are the architect for a Moorish sultan's harem, and design intricate tile patterns of high symmetry. In either case, borrow or buy a book of Escher's work and analyze the drawings in light of what the computer program shows you about symmetry in the tiling task.

Staring at the Harem Floor

The theory of tiling (tesselation) needs only a few concepts.

An outline, called the unit cell, must fill the plane when you lay copies of it side by side--no gaps, no overlaps, and all cells oriented the same way. That is, you slide one cell (without letting it twist) by its own length to get a neighboring cell. Such a sliding is called a translation.

"But" you say, "how about the common bathroom tile of octagons and squares--two dissimilar shapes that together tile the plane?" All such composite outlines as well as irregular outlines like Escher's "horseman" (Figure 1) can be included by adding inner structure to the basic outlines: parallelogram, rectangle, square, and hexagon.

The cells rarely show up in the final drawing explicitly. To detect a cell you must reconstruct it by marking repeated elements with a dot and then joining the dots by lines. For example, dot the tip of the front hoof of every white horse in the Horsemen drawing. The infinite set of dots you get is called the lattice. Now connect four adjacent dots and you will see the rectangular unit cell. The cell for a given drawing is unique in size and shape, but not in location. If you choose to dot the chin of each black warrior you would get the same set of rectangular cells, but displaced from the "hoof" cells.

Added to the lattice of cells are three kinds of symmetry elements: rotations, reflections, and glides. The requirement that no overlaps or gaps be present in the tiling of the plane can be satisfied in exactly 17 combinations of cell shape and symmetry elements. These are called the 17 plane space groups, and each is named with a special symbol (see lines 2316 through 2348 of Listing 1). In these symbols, p stands for primitive cell (having lattice points at the corners of the cells only) and c for centered, having also a lattice point in the center of each cell. The numbers stand for n-fold rotation axes, m for mirror planes, and g for glide planes.

N-fold axes of rotation are important in many of Escher's drawings. Only values of n=2,3,4,6 are allowed by mathematical consistency with the tiling idea. (N = 1 means no rotations at all.) By a "two-fold axis" we mean this: Taking an axis perpendicular to the paper, you rotate the drawing by one half a turn. The whole plane of figures will rotate into coincidence with itself.

A two-fold axis does not impose any conditions on the cell shape, but a four-fold axis can be present only when the cell is a square, and then only at the corners or center of the square. Likewise, a three-fold or six-fold axis requires the cell be hexagonal in shape.

Look for reflection planes in Escher's drawings. Holding a pocket mirror perpendicular to the page and moving it around, you may find a spot where the reflection in the mirror exactly matches the part of the drawing you see if you remove the mirror. If so, draw a line along the base of the mirror and you have marked a reflection plane. Planes tiled with oblique cells (non-rectangular parallelograms) cannot have reflection planes.

You can also detect the presence of reflection planes by just eyeballing the drawing. A symmetric figure, such as the front view of a soldier standing at attention, has a reflection plane (line, really) as the midline from head to toe. Non-symmetric figures that occur in pairs related like the right and left hand of a glove have a reflection plane half way between them if the line joining equivalent points (tip of each thumb) is perpendicular to the reflection plane. (If not, you have a glide plane.)

Glide planes are a combination of reflection and translation that have no counterpart in everyday life. The horsemen drawing of Escher shows the presence of a glide plane in this way: Each horseman is a mirror image in form (related as right glove to left glove) of one facing the other way (of opposite color) but is not correctly placed to be a mirror image. In fact, each horseman is a mirror image "glided" by a half cell height from the mirror position.

Escher colored his tile prints so the viewer could distinguish each figure from its neighbors. Ignore the colors when saying that one figure reflects, rotates, translates, or glides into another.

More about cell shapes: Symmetry does not restrict the proportions of rectangular or oblique cells, nor the angle in oblique cells. In fact, a rectangular or oblique cell could "accidentally" be square in shape. Each cell contains an integer number of complete figures. (A figure often extends outside the boundaries of the cell. If so, there must be an equivalent part extending into the cell from one corresponding figure in another cell.)

The Dancing Dots

The program is written in Basic on an IBM PC. I have been careful to keep the program as free as possible from special features of the IBM, and hope you can adapt it easily to your computer. Apple and Commodore machines, and Atari and Radio Shack machines using Microsoft Basic, can accept this program with only a few lines changed. I have kept the program simple. It uses the medium resolution black and white screen, and the I, J, K, and L keys to move the cursor for drawing. You may want to use color, low or high resolution, arrow cursor keys, or other special features of your own machine.

Lines 400 to 599 of the program are its geometrical heart and can be moved unchanged to any computer. Each of the 17 space groups is generated by a few lines of code giving the x and y coordinates of all equivalent points in a given cell.

In lines 350 to 399, the dots are written on the screen for four complete cells. One cell has its upper left lattice point in the center of the drawing, and from this point you move the dot that draws the figure. For other computers, you may need to change the PSET command to a PLOT or use a LOCATE or similar manner of putting a dot or character on a specified part of the screen.

Lines 200 to 299 let the program user move the dots around on the screen, and erase dots. These lines can in principle be moved to any other computer, but some changes may have to be made, such as changing the INKEY$ construction of the IBM to a GET or INPUT.

For low symmetry cases, the program is moderately fast. You can input about five points per second. But when you are drawing high symmetry diagrams in which the computer must compute the location of up to 48 points for each point you input, and place them on the screen, the pace slows to about one point per second.

Enjoy the program. May all your figures interlock, on the screen and as you skate through life.