<< . .

. 14
( : 45)

. . >>

110 Chapter 13: Drawing, Filling, and Erasing

EXERCISE 13.3 doubly ¬lled
Devise an un¬ll command that will produce the pixel values strange path
turning number

when it is used just after the ¬ll and un¬ll commands already given.
A “simple” region is one whose boundary does not intersect itself; more
complicated e¬ects occur when the boundary lines cross. For example,
¬ll (0, 1) - - (9, 1) - - (9, 4) - - (4, 4) - -
(4, 0) - - (6, 0) - - (6, 3) - - (8, 3) - - (8, 2) - - (0, 2) - - cycle
produces the pixel pattern

Notice that some pixels receive the value 2, because they™re “doubly ¬lled.”
There™s also a “hole” where the pixel values remain zero, even though they are
surrounded by ¬lled pixels; the pixels in that hole are not considered to be in
the region, but the doubly ¬lled pixels are considered to be in the region twice.
Show that the ¬rst 9 — 9 cross pattern on the previous page can be generated
by a single ¬ll command. (The nine pixel values in the center should be 2, as if
two separate regions had been ¬lled, even though you are doing only one ¬ll.)
What do you think is the result of ˜¬ll (0, 0) - - (1, 0) - - (1, 1) - - (0, 1) - - (0, 0) - -
(1, 0) - - (1, 1) - - (0, 1) - - cycle™ ?
A ¬ll command can produce even stranger e¬ects when its boundary
lines cross in only one place. If you say, for example,
¬ll (0, 2) - - (4, 2) - - (4, 4) - - (2, 4) - - (2, 0) - - (0, 0) - - cycle
will produce the 4 — 4 pattern

where ˜ ™ stands for the value ’1. Furthermore the machine will report that
you have a “strange path” whose “turning number” is zero! What does this
mean? Basically, it means that your path loops around on itself something like a
¬gure 8; this causes a breakdown in ™s usual rules for distinguishing
the “inside” and “outside” of a curve.
Chapter 13: Drawing, Filling, and Erasing 111

Every cyclic path has a turning number that can be understood as follows. digitized
Imagine that you are driving a car along the path and that you have a digital
compass that tells in what direction you™re heading. For example, if the path is
(0, 0) - - (2, 0) - - (2, 2) - - (0, 2) - - cycle
you begin driving in direction 0—¦ , then you make four left turns. After the ¬rst turn,
your compass heading is 90—¦ ; after the second, it is 180—¦ ; and after the third it is
270—¦ . (The compass direction increases when you turn left and decreases when you
turn right; therefore it now reads 270—¦ , not ’90—¦ .) At the end of this cycle the compass
will read 360—¦ , and if you go around again the reading will be 720—¦ . Similarly, if you
had traversed the path
(0, 0) - - (0, 2) - - (2, 2) - - (2, 0) - - cycle
(which is essentially the same, but in the opposite direction), your compass heading
would have started at 90—¦ and ended at ’270—¦ ; in this case each circuit would have
decreased the reading by 360—¦ . It is clear that a drive around any cyclic path will change
the compass heading by some multiple of 360—¦ , since you end in the same direction you
started. The turning number of a path is de¬ned to be t if the compass heading changes
by exactly t times 360—¦ when the path is traversed. Thus, the two example cycles we
have just discussed have turning numbers of +1 and ’1, respectively; and the “strange
path” on the previous page that produced both positive and negative pixel values does
indeed have a turning number of 0.
Here™s how actually implements a ¬ll command, assuming that
the cyclic path being ¬lled has a positive turning number: The path is ¬rst
“digitized,” if necessary, so that it lies entirely on the edges of pixels; in other words,
it is distorted slightly so that it is con¬ned to the lines between pixels on graph paper.
(Our examples so far in this chapter have not needed any such adjustments.) Then
each individual pixel value is increased by j and decreased by k if an in¬nite horizontal
line to the left of that pixel intersects the digitized path j times when the path is
traveling downward and k times when it is traveling upward. For example, let™s look
more closely at the non-simple path on the previous page that enclosed a hole:
a¦b b¦b b b¦
a a a
a¦b c¦d¦
a a a
¦e e¦f f ¦g
e e gg
a a a bh hh
Pixel d has j = 2 descending edges and k = 1 ascending edges to its left, so its net
value increases by j ’ k = 1; pixels g are similar. Pixels c have j = k = 1, so they lie in
a “hole” that is un¬lled; pixels f have j = 2 and k = 0, so they are doubly ¬lled. This
rule works because, intuitively, the inside of a region lies at the left of a path whose
turning number is positive.
True or false: When the turning number of a cyclic path is positive, a ¬ll
command increases each individual pixel value by l ’ m, if an in¬nite horizontal line to
the right of that pixel intersects the digitized path l times when the path is traveling
upward and m times when it is traveling downward. (For example, pixels e have l = 2
and m = 1; pixels c have l = m = 1.)
112 Chapter 13: Drawing, Filling, and Erasing

When the turning number is negative, a similar rule applies, except that the turningcheck
pixel values are decreased by j and increased by k; in this case the inside of
the region lies at the right of the path. ¬lldraw

But when the turning number is zero, the inside of the region lies sometimes at
the left, sometimes at the right. uses the rule for positive turning
number and reports that the path is “strange.” You can avoid this error message by
setting ˜turningcheck := 0™; in this case the rule for positive turning number is always
used for ¬lling, even when the turning number is negative.
Plain ™s draw command is di¬erent from ¬ll in two impor-
tant ways. First, it uses the currently-picked-up pen, thereby “thickening” the
path. Second, it does not require that the path be cyclic. There is also a third
di¬erence, which needs to be mentioned although it is not quite as important:
A draw command may increase the value of certain pixels by more than 1, even
if the shape being drawn is fairly simple. For example, the pixel pattern

was produced by two draw commands. The left-hand shape came from
pickup penrazor scaled 10; % a pen of width 10 and height 0
draw (6, 1){up } . . (13.5, 25) . . {down }(21, 1);
it™s not di¬cult to imagine why some of the top pixels get the value 2 here
because an actual razor-thin pen would cover those pixels twice as it follows the
given path. But the right-hand shape, which came from
pickup pencircle scaled 16; draw (41, 9) . . (51, 17) . . (61, 9)
is harder to explain; there seems to be no rhyme or reason to the pattern of 2™s
in that case. ™s method for drawing curves with thick pens is too
complicated to explain here, so we shall just regard it as a curious process that
occasionally shoots out extra spurts of ink in the interior of the shape that it™s
¬lling. Sometimes a pixel value even gets as high as 3 or more; but if we ignore
such anomalies and simply consider the set of pixels that receive a positive value,
we ¬nd that a reasonable shape has been drawn.
The left-parenthesis example in Chapter 12 illustrates the ¬lldraw com-
mand, which is like ¬ll in that it requires a cyclic path, and like draw in that it
Chapter 13: Drawing, Filling, and Erasing 113

uses the current pen. Pixel values are increased inside the region that you would drawdot
obtain by drawing the speci¬ed path with the current pen and then ¬lling in the un¬lldraw
interior. Some of the pixel values in this region may increase by 2 or more. The undrawdot
turning number of the path should be nonzero. culling
Besides ¬ll, draw, and ¬lldraw, you can also say ˜drawdot™, as il- erase
lustrated at the beginning of Chapter 5. In this case you should specify only cube
a single point; the currently-picked-up pen will be used to increase pixel values impossible cube
by 1 around that point. Chapter 24 explains that this gives slightly better results
than if you were to draw a one-point path.
There™s also an undraw command, analogous to un¬ll; it decreases pixel
values by the same amount that draw would increase them. Furthermore”
as you might expect”un¬lldraw and undrawdot are the respective opposites of
¬lldraw and drawdot.
If you try to use un¬ll and/or undraw in connection with ¬ll and/or draw,
you™ll soon discover that something else is necessary. Plain has
a cullit command that replaces all negative pixel values by 0 and all positive pixel
values by 1. This “culling” operation makes it possible to erase unwanted sections of
a picture in spite of the vagaries of draw and undraw, and in spite of the fact that
overlapping regions may be doubly ¬lled.
The command ˜erase ¬ll c™ is an abbreviation for ˜cullit; un¬ll c; cullit™;
this zeros out the pixel values inside the cyclic path c, and sets other pixel
values to 1 if they were positive before erasing took place. (It works because the initial
cullit makes all the values 0 or 1, then the un¬ll changes the values inside c to 0 or
negative. The ¬nal cullit gets rid of the negative values, so that they won™t detract
from future ¬lling and drawing.) You can also use ˜draw™, ˜¬lldraw™, or ˜drawdot™
with ˜erase™; for example, ˜erase draw p™ is an abbreviation for ˜cullit; undraw p;
cullit™, which uses the currently-picked-up pen as if it were an eraser applied to path p.
The cube at the right of this paragraph illustrates
one of the e¬ects that is easily obtained by erasing.
First the eight points are de¬ned, and the “back” square (Figure 13a will be in-
serted here; too bad you
is drawn; then two lines of the “front” square are erased, can™t see it now.)

using a somewhat thicker pen; ¬nally the remaining lines
are drawn with the ordinary pen:
s# := 5pt #; de¬ne pixels(s); % side of the square
z1 = (0, 0); z2 = (s, 0); z3 = (0, s); z4 = (s, s);
for k = 1 upto 4: zk+4 = zk + ( 2 s, 1 s); endfor
3 3
pickup pencircle scaled .4pt ; draw z5 - - z6 - - z8 - - z7 - - cycle;
pickup pencircle scaled 1.6pt ; erase draw z2 - - z4 - - z3 ;
pickup pencircle scaled .4pt ; draw z1 - - z2 - - z4 - - z3 - - cycle;
for k = 1 upto 4: draw zk - - zk+4 ; endfor.
At its true size the resulting cube looks like this: ˜ ™.
Modify the draw-and-erase construction in the preceding paragraph so that
you get the impossible cube ˜ ™ instead.
114 Chapter 13: Drawing, Filling, and Erasing

EXERCISE 13.8 rotated
Write a program to produce the symbol ˜ ™. [Hints: The char-
acter is 10 pt wide, 7 pt high, and 2 pt deep. The starlike path can be de¬ned by ¬ve star
points connected by “tense” lines as follows: macro
pair center ; center = (.5w, 2pt ); point
numeric radius ; radius = 5pt ; S
360 M¨bius
for k = 0 upto 4: zk = center + (radius , 0) rotated(90 + k); endfor
def :: = . . tension 5 . . enddef ; currentpicture
path star ; star = z0 :: z2 :: z4 :: z1 :: z3 :: cycle;

You probably want to work with subpaths of star instead of drawing the whole path
at once, in order to give the illusion that the curves cross over and under each other.]

What does the command ˜¬ll star ™ do, if star is the path de¬ned above?

Devise a macro called ˜overdraw™ such that the command
˜overdraw c™ will erase the inside of region c and will then draw the
boundary of c with the currently-picked-up pen, assuming that c is a
cyclic path that doesn™t intersect itself. (Your macro could be used,
for example, in the program (Figure 13aa
will be inserted
here; too bad
path S; S = ((0, 1) . . (2, 0) . . (4, 2) . . you can™t see it
(2, 5.5) . . (0, 8) . . (2, 10) . . (3.5, 9)) scaled 9pt ;
for k = 0 upto 35: overdraw fullcircle scaled 3mm
shifted point k/35 — length S of S; endfor

to create the curious S shown here.)

The M¨bius Watchband Corporation has a logo that looks like this:

(Figure 13bb will be inserted here; too bad you can™t see it now.)

Explain how to produce it (or something very similar) with .

Chapter 7 points out that variables can be of type ˜picture™, and Chapter 8
mentions that expressions can be of type ˜picture™, but we still haven™t seen
any examples of picture variables or picture expressions. Plain keeps the
currently-worked-on picture in a picture variable called currentpicture , and you can
copy it by equating it to a picture variable of your own. For example, if you say
˜picture v[ ]™ at the beginning of your program, you can write equations like

v1 = currentpicture ;

this makes v1 equal to the picture that has been drawn so far; i.e., it gives v1 the same
array of pixel values that currentpicture now has.
Chapter 13: Drawing, Filling, and Erasing 115

Pictures can be added or subtracted; for example, v1 +v2 stands for the picture sum of pictures
negative of a picture
whose pixel values are the sums of the pixel values of v1 and v2 . The “reverse-
inverse video
video dangerous bend” sign that heads this paragraph was made by substituting the reverse-video
following code for the ˜endchar™ in the program at the end of Chapter 12: dangerous bend
black/white reversal
picture dbend ; dbend = currentpicture ; clearit
endchar; % end of the normal dangerous bend sign beginchar
beginchar(0, 25u#, h height # + border #, 0); mode setup
picture primary
¬ll (0, ’11pt ) - - (w, ’11pt ) - - (w, h) - - (0, h) - - cycle; nullpicture
currentpicture := currentpicture ’ dbend ; (
endchar; % end of the reversed dangerous bend sign
picture secondary
picture tertiary
The pixel values in dbend are all zero or more; thus the pixels with a positive value, picture expression
after dbend has been subtracted from a ¬lled rectangle, will be those that are inside totalweight
the rectangle but zero in dbend .

We will see in Chapter 15 that pictures can also be shifted, re¬‚ected, and
rotated by multiples of 90—¦ . For example, the statement ˜currentpicture :=
currentpicture shifted 3right ™ shifts the entire current picture three pixels to the right.

There™s a “constant” picture called nullpicture, whose pixel values are all
zero; plain de¬nes ˜clearit™ to be an abbreviation for the as-
signment ˜currentpicture :=nullpicture™. The current picture is cleared automatically
by every beginchar and mode setup command, so you usually don™t have to say
˜clearit™ in your own programs.

Here™s the formal syntax for picture expressions. Although has
comparatively few built-in operations that deal with entire pictures, the op-
erations that do exist have the same syntax as the similar operations we have seen
applied to numbers and pairs.

picture primary ’’ picture variable
| nullpicture
| ( picture expression )
| plus or minus picture primary
picture secondary ’’ picture primary
| picture secondary transformer
picture tertiary ’’ picture secondary
| picture tertiary plus or minus picture secondary
picture expression ’’ picture tertiary

The “total weight” of a picture is the sum of all its pixel values, divided by
65536; you can compute this numeric quantity by saying

totalweight picture primary .

divides by 65536 in order to avoid over¬‚ow in case of huge pictures. If the
totalweight function returns a number whose absolute value is less than .5, as it almost
always is, you can safely divide that number by epsilon to obtain the integer sum of
all pixel values (since epsilon = 1/65536).
116 Chapter 13: Drawing, Filling, and Erasing

Let™s turn to the computer again and try to evaluate some simple picture ex- hide
pressions interactively, using the general routine expr.mf of Chapter 8. When
says ˜gimme™, you can type resolution

hide(fill unitsquare) currentpicture
and the machine will respond as follows:
>> Edge structure at line 5:
row 0: 0+ 1- |
What does this mean? Well, ˜hide™ is plain ™s sneaky way to insert a
command or sequence of commands into the middle of an expression; such commands
are executed before the rest of the expression is looked at. In this case the command
˜¬ll unitsquare ™ sets one pixel value of the current picture to 1, because unitsquare is
plain ™s abbreviation for the path (0, 0) - - (1, 0) - - (1, 1) - - (0, 1) - - cycle.
The value of currentpicture is displayed as ˜row 0: 0+ 1-™, because this means “in
row 0, the pixel value increases at x = 0 and decreases at x = 1.”
represents pictures internally by remembering only the vertical
edges where pixel values change. For example, the picture just displayed
has just two edges, both in row 0, i.e., both in the row between y coordinates 0 and 1.
(Row k contains vertical edges whose x coordinates are integers and whose y coordinates
run between k and k+1.) The fact that edges are represented, rather than entire arrays
of pixels, makes it possible for to operate e¬ciently at high resolutions,
because the number of edges in a picture is essentially proportional to the resolution
while the total number of pixels is proportional to the resolution squared. A ten-fold
increase in resolution therefore calls for only a ten-fold (rather than a hundred-fold)
increase in memory space and execution time.
Continuing our computer experiments, let™s declare a picture variable and ¬ll
a few more pixels:
hide(picture V; fill unitsquare scaled 2; V=currentpicture) V
The resulting picture has pixel values and its edges are shown thus:

>> Edge structure at line 5:
row 1: 0+ 2- |
row 0: 0+ 2- 0+ 1- |
If we now type ˜-V™, the result is similar but with the signs changed:
>> Edge structure at line 5:
row 1: 0- 2+ |
row 0: 0- 2+ 0- 1+ |
(You should be doing the experiments as you read this.) A more interesting picture
transformation occurs if we ask for ˜V rotated-90™; the picture 2 1 appears below the
baseline, hence the following edges are shown:
>> Edge structure at line 5:
row -1: | 0++ 1- 2-
row -2: | 0+ 2-
Chapter 13: Drawing, Filling, and Erasing 117

Here ˜++™ denotes an edge where the weight increases by 2. The edges appear after ++
vertical lines ˜|™ in this case, while they appeared before vertical lines in the previous
vertical line
examples; this means that has sorted the edges by their x coordinates. rotated
Each ¬ll or draw instruction contributes new edges to a picture, and unsorted edges shifted
edge structure
accumulate until needs to look at them in left-to-right order. (Type

<< . .

. 14
( : 45)

. . >>