need to compute the exact coordinates for some reason, we can always work them

out from the general formula, getting z2 + .4(z6 ’ z2 ) = (100, 100) + .4 (200, 0) ’

(100, 100) = (100, 100) + .4(100, ’100) = (100, 100) + (40, ’40) = (140, 60).

EXERCISE 2.7

True or false: The direction vector from (5, ’2) to (2, 3) is (’3, 5).

EXERCISE 2.8

Explain what the notation ˜0[z1 , z2 ]™ means, if anything. What about ˜1[z1 , z2 ]™ ?

And ˜2[z1 , z2 ]™ ? And ˜(’.5)[z1 , z2 ]™ ?

EXERCISE 2.9

True or false, for mathematicians: (a) 1 [z1 , z2 ] = 1 1

2 (z1 + z2 ); (b) 3 [z1 , z2 ] =

2

z1 + 2 z2 ; (c) t[z1 , z2 ] = (1 ’ t)[z2 , z1 ].

1

3 3

Let™s conclude this chapter by using ¦

¦

¦

mediation to help specify the ¬ve points in the ¦

¦

¦

stick-¬gure ˜ ™ shown enlarged at the right. The ¦

¦

¦

distance between points 1 and 5 should be a, ¦

¦

and point 3 should be b pixels above the base- (Figure 2e will be in-

line; these values a and b have been predeter- b

¦

serted here; too bad

¦ you can™t see it now.)

¦

mined by some method that doesn™t concern ¦

¦

¦

us here, and so has a “sidebar” parameter s ¦

¦

¦

that speci¬es the horizontal distance of points ¦

¦

1 and 5 from the edges of the type. We shall

assume that we don™t know for sure what the

s ← ’ ’a’ ’ ’ s

’’ ’’

height of the bar line should be; point 2 should

be somewhere on the straight line from point 1

to point 3, and point 4 should be in the corresponding place between 5 and 3,

but we want to try several possibilities before we make a decision.

The width of the character will be s + a + s, and we can specify points

z1 and z5 by the equations

bot z1 = (s, 0); z5 = z1 + (a, 0).

There are other ways to do the job, but these formulas clearly express our in-

tention to have the bottom of the pen at the baseline, s pixels to the right of

the reference point, when the pen is at z1 , and to have z5 exactly a pixels to the

right of z1 . Next, we can say

1

z3 = 2 [x1 , x5 ], b ;

Chapter 2: Coordinates 11

this means that the x coordinate of point 3 should be halfway between the golden ratio

dangerous bend

x coordinates of points 1 and 5, and that y3 = b. Finally, let™s say ELLIS

Descartes

z2 = alpha [z1 , z3 ]; z4 = alpha [z5 , z3 ]; BELL

the parameter alpha is a number between 0 and 1 that governs the position of

the bar line, and it will be supplied later. When alpha has indeed received a

value, we can say

draw z1 . . z3 ; draw z3 . . z5 ; draw z2 . . z4 .

will draw the characters ˜ ™ when alpha varies from 0.2 to

0.5 in steps of 0.05 and when a = 150, b = 250, s = 30. The illustration on the

√

previous page has alpha = (3 ’ 5 )/2 ≈ 0.38197; this value makes the ratio of

√

the area above the bar to the area below it equal to ( 5 ’ 1)/2 ≈ 0.61803, the

so-called “golden ratio” of classical Greek mathematics.

(Are you sure you should be reading this paragraph? The “dangerous bend”

sign here is meant to warn you about material that ought to be skipped on ¬rst

reading. And maybe also on second reading. The reader-beware paragraphs sometimes

refer to concepts that aren™t explained until later chapters.)

EXERCISE 2.10

Why is it better to de¬ne z3 as ( 1 [x1 , x5 ], b), rather than to work out the

2

explicit coordinates z3 = (s + 1 a, b) that are implied by the other equations?

2

EXERCISE 2.11

Given z1 , z3 , and z5 as above, explain how to de¬ne z2 and z4 so that all of

the following conditions hold simultaneously:

the line from z2 to z4 slopes upward at a 20—¦ angle;

the y coordinate of that line™s midpoint is 2/3 of the way from y3 to y1 ;

z2 and z4 are on the respective lines z1 . . z3 and z3 . . z5 .

(If you solve this exercise, you deserve an ˜ ™.)

Here, where we reach the sphere of mathematics,

we are among processes which seem to some

the most inhuman of all human activities

and the most remote from poetry.

Yet it is here that the artist has the fullest scope for his imagination.

” HAVELOCK ELLIS, The Dance of Life (1923)

To anyone who has lived in a modern American city (except Boston)

at least one of the underlying ideas of Descartes™ analytic geometry

will seem ridiculously evident. Yet, as remarked,

it took mathematicians all of two thousand years

to arrive at this simple thing.

” ERIC TEMPLE BELL, Mathematics: Queen and Servant of Science (1951)

(page 12)

3

Curves

Chapter 3: Curves 13

Albrecht D¨rer and other Renaissance men attempted to establish mathematical

u D¨ rer

u

curves

principles of type design, but the letters they came up with were not especially four-point method for curves

beautiful. Their methods failed because they restricted themselves to “ruler midpoints

and compass” constructions, which cannot adequately express the nuances of

good calligraphy. gets around this problem by using more powerful

mathematical techniques, which provide the necessary ¬‚exibility without really

being too complicated. The purpose of the present chapter is to explain the

simple principles by which a computer is able to draw “pleasing” curves.

The basic idea is to start with four points (z1 , z2 , z3 , z4 ) and to construct

the three midpoints z12 = 1 [z1 , z2 ], z23 = 1 [z2 , z3 ], z34 = 1 [z3 , z4 ]:

2 2 2

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

Then take those three midpoints (z12 , z23 , z34 ) and construct two second-order

midpoints z123 = 1 [z12 , z23 ] and z234 = 1 [z23 , z34 ]; ¬nally, construct the third-

2 2

order midpoint z1234 = 1 [z123 , z234 ]:

2

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

This point z1234 is one of the points of the curve determined by (z1 , z2 , z3 , z4 ).

To get the remaining points of that curve, repeat the same construction on

(z1 , z12 , z123 , z1234 ) and on (z1234 , z234 , z34 , z4 ), ad in¬nitum:

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

The process converges quickly, and the preliminary sca¬olding (which appears

above the limiting curve in our example) is ultimately discarded. The limiting

curve has the following important properties:

It begins at z1 , heading in the direction from z1 to z2 .

It ends at z4 , heading in the direction from z3 to z4 .

It stays entirely within the so-called convex hull of z1 , z2 , z3 , and z4 ;

i.e., all points of the curve lie “between” the de¬ning points.

14 Chapter 3: Curves

The recursive midpoint rule for curve-drawing was discovered in 1959 by Paul de Casteljau

Bernshte˜ polynomial

±n

de Casteljau, who showed that the curve could be described algebraically by

Bernshte˜

±n

the remarkably simple formula B´zier

e

mediation

z(t) = (1 ’ t)3 z1 + 3(1 ’ t)2 t z2 + 3(1 ’ t)t2 z3 + t3 z4 ,

as the parameter t varies from 0 to 1. This polynomial of degree 3 in t is called

a Bernshte˜ polynomial, because Serge˜ N. Bernshte˜ introduced such functions in

±n ± ±n

1912 as part of his pioneering work on approximation theory. Curves traced out by

Bernshte˜ polynomials of degree 3 are often called B´zier cubics, after Pierre B´zier

±n e e

who realized their importance for computer-aided design during the 1960s.

It is interesting to observe that the Bernshte˜ polynomial of degree 1, i.e., the

±n

function z(t) = (1’t) z1 +t z2 , is precisely the mediation operator t[z1 , z2 ] that

we discussed in the previous chapter. Indeed, if the geometric construction we have just

seen is changed to use t-of-the-way points instead of midpoints (i.e., if z12 = t[z1 , z2 ]

and z23 = t[z2 , z3 ], etc.), then z1234 turns out to be precisely z(t) in the formula above.

No matter what four points (z1 , z2 , z3 , z4 ) are given, the construction on

the previous page de¬nes a curved line that runs from z1 to z4 . This curve is not

always interesting or beautiful; for example, if all four of the given points lie on

a straight line, the entire “curve” that they de¬ne will also be contained in that

same line. We obtain rather di¬erent curves from the same four starting points

if we number the points di¬erently:

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

Some discretion is evidently advisable when the z™s are chosen. But the four-

point method is good enough to obtain satisfactory approximations to any curve

we want, provided that we break the desired curve into short enough segments

and give four suitable control points for each segment. It turns out, in fact, that

we can usually get by with only a few segments. For example, the four-point

method can produce an approximate quarter-circle with less than 0.06% error; it

never yields an exact circle, but the di¬erences between four such quarter-circles

and a true circle are imperceptible.

All of the curves that draws are based on four points, as just

described. But it isn™t necessary for a user to specify all of those points, because

the computer is usually able to ¬gure out good values of z2 and z3 by itself. Only

the endpoints z1 and z4 , through which the curve is actually supposed to pass,

are usually mentioned explicitly in a program.

For example, let™s return to the six points that were used to introduce

the ideas of coordinates in Chapter 2. We said ˜draw z1 . . z6 ™ in that chapter,

Chapter 3: Curves 15

in order to draw a straight line from point z1 to point z6 . In general, if three ..

control points

or more points are listed instead of two, will draw a smooth curve cycle

through all the points. For example, the commands ˜draw z4 . . z1 . . z2 . . z6 ™ bean-like shape

tension

and ˜draw z5 . . z4 . . z1 . . z3 . . z6 . . z5 ™ will produce the respective results

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

(Unlabeled points in these diagrams are control points that has

supplied automatically so that it can use the four-point scheme to draw curves

between each pair of adjacent points on the speci¬ed paths.)

Notice that the curve is not smooth at z5 in the right-hand example,

because z5 appears at both ends of that particular path. In order to get a

completely smooth curve that returns to its starting point, you can say ˜draw

z5 . . z4 . . z1 . . z3 . . z6 . . cycle™ instead:

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

The word ˜cycle™ at the end of a path refers to the starting point of that path.

believes that this bean-like shape is the nicest way to connect the

given points in the given cyclic order; but of course there are many decent curves

that satisfy the speci¬cations, and you may have another one in mind. You can

obtain ¬ner control by giving hints to the machine in various ways. For example,

the bean curve can be “pulled tighter” between z1 and z3 if you say

draw z5 . . z4 . . z1 . . tension 1.2 . . z3 . . z6 . . cycle;

the so-called tension between points is normally 1, and an increase to 1.2 yields

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

16 Chapter 3: Curves

An asymmetric e¬ect can be obtained by increasing the tension only at point 1

but not at points 3 or 4; the shape

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

comes from ˜draw z5 . . z4 . . tension 1 and 1.5 . . z1 . . tension 1.5 and 1 . . z3 . . z6 . .

cycle™. The e¬ect of tension has been achieved in this example by moving two of the

anonymous control points closer to point 1.

It™s possible to control a curve in another way, by telling

what direction to travel at some or all of the points. Such directions are given

inside curly braces; for example,

draw z5 . . z4 {left } . . z1 . . z3 . . z6 {left } . . cycle

says that the curve should be traveling leftward at points 4 and 6. The resulting

curve is perfectly straight from z6 to z5 to z4 :

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

We will see later that ˜left ™ is an abbreviation for the vector (’1, 0), which

stands for one unit of travel in a leftward direction. Any desired direction can

be speci¬ed by enclosing a vector in {. . .}™s; for example, the command ˜draw

z4 . . z2 {z3 ’ z4 } . . z3 ™ will draw a curve from z4 to z2 to z3 such that the tangent

direction at z2 is parallel to the line z4 . . z3 , because z3 ’ z4 is the vector that

represents travel from z4 to z3 :

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

The same result would have been obtained from a command such as ˜draw

z4 . . z2 {10(z3 ’ z4 )} . . z3 ™, because the vector 10(z3 ’ z4 ) has the same direction

as z3 ’ z4 . ignores the magnitudes of vectors when they are simply

being used to specify directions.

Chapter 3: Curves 17

EXERCISE 3.1 curl

What do you think will be the result of ˜draw z4 . . z2 {z4 ’ z3 } . . z3 ™, when

points z2 , z3 , z4 are the same as they have been in the last several examples?

EXERCISE 3.2

Explain how to get to draw the wiggly shape

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

in which the curve aims directly at point 2 when it™s at point 6, but directly

away from point 2 when it™s at point 4. [Hint: No tension changes are needed;

it™s merely necessary to specify directions at z4 and z6 .]

allows you to change the shape of a curve at its endpoints

by specifying di¬erent amounts of “curl.” For example, the two commands

draw z4 {curl 0} . . z2 {z3 ’ z4} . . {curl 0} z3 ;

draw z4 {curl 2} . . z2 {z3 ’ z4} . . {curl 2} z3

give the respective curves

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

which can be compared with the one shown earlier when no special curl was

requested. (The speci¬cation ˜curl 1™ is assumed at an endpoint if no explicit

curl or direction has been mentioned, just as ˜tension 1™ is implied between points

when no tension has been explicitly given.) Chapter 14 explains more about this.

It™s possible to get curved lines instead of straight lines even when only

two points are named, if a direction has been prescribed at one or both of the

points. For example,

draw z4 {z2 ’ z4 } . . {down } z6

asks for a curve that starts traveling towards z2 but ¬nishes in a

downward direction:

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

18 Chapter 3: Curves

Here are some of the curves that draws between two points, when for

it is asked to move outward from the left-hand point at an angle of 60—¦ , and step

until

to approach the right-hand point at various angles: cm

dir

in¬‚ection point

...

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

This diagram was produced by the program

for d = 0 step 10 until 120:

draw (0, 0){dir 60} . . {dir ’d}(6cm , 0); endfor;

the ˜dir™ function speci¬es a direction measured in degrees counterclockwise from a

horizontal rightward line, hence ˜dir ’d™ gives a direction that is d—¦ below the horizon.

The lowest curves in the illustration correspond to small values of d, and the highest

curves correspond to values near 120—¦ .

A car that drives along the upper paths in the diagram above is always turning

to the right, but in the lower paths it comes to a point where it needs to turn to

the left in order to reach its destination from the speci¬ed direction. The place where a

path changes its curvature from right to left or vice versa is called an “in¬‚ection point.”

introduces in¬‚ection points when it seems better to change the curvature

than to make a sharp turn; indeed, when d is negative there is no way to avoid points

of in¬‚ection, and the curves for small positive d ought to be similar to those obtained

when d has small negative values. The program

for d = 0 step ’10 until ’90:

draw (0, 0){dir 60} . . {dir ’d}(6cm , 0); endfor

shows what does when d is negative: