The bez123 and multiply packages^{∗}

Peter Wilson Catholic University of America^{†}

          Now at peter.r.wilson@boeing.com

1998/10/14

Abstract The bez123 package provides for the drawing of linear, cubic, and ratio-

nal quadratic Bezier curves. The multiply package provides a command to multiply a length without numerical overflow.

Contents

1 Introduction 2 2 Usage 2 3 The bez123 package implementation 11

3.1 Arithmetic in TEX . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Linear Bezier curves . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Cubic Bezier curves . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Quadratic rational Bezier curve . . . . . . . . . . . . . . . . . . . . 16

4 Multiplication without overflow: The multiply package 22

List of Tables

1 Conic forms of the rational quadratic Bezier curve . . . . . . . . . 6

List of Figures

1 Four sets of points and their convex hulls . . . . . . . . . . . . . . 4 2 Four sets of points, the cubic Bezier curves and their control poly-

∗This file has version number v1.1, last revised 1998/10/14.

†This work was originally performed as a Guest Researcher at the National Institute of Standards and Technology.

gons. Left — curves plotted with N = 30; Right — curves plotted with N = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 The angle β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 The effect of weight variation (W ≥ 0) on rational quadratic Bezier

curves (weightscale = 10000 (the default)) . . . . . . . . . . . . 7 5 The effect of weightscale on the drawing of rational quadratic

Bezier curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6 Rational quadratics with weights of ±0.5 and an equilateral trian-

gular convex hull (weightscale = 50000) . . . . . . . . . . . . . 9 7 Three rational quadratics with weights of 0.5 (weightscale =

10000) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8 A rational quadratic that has gone negative; weights of ±2

(weightscale = 10000) . . . . . . . . . . . . . . . . . . . . . . . 10

1 Introduction

This document provides the commented source for a L^{A}TEX package file that extends the L^{A}TEX facilities for drawing Bezier curves. The package was originally developed as part of a suite designed for the typesetting of documents according to the rules for ISO international standards [Wil96]. This manual is typeset according to the conventions of the L^{A}TEX docstrip utility which enables the automatic extraction of the L^{A}TEX macro source files [GMS94].

Drawing a non-rational quadratic Bezier curve is provided as part of the standard L^{A}TEX system. Section 2 provides the user manual for the new commands supplied by this package for drawing a variety of Bezier curves. These include commands for drawing linear and cubic non-rational Bezier curves and rational quadratic curves.

Section 3 describes the implementation of the package. As a side-effect of the implementation, a facility is also provided for performing multiplication in TEX without overflow. This is described in Section 4.

2 Usage

Leslie Lamport provided the means of drawing a quadratic Bezier curve via the L^{A}TEX 2ε \qbezier [Lam94, pp. 125–126] command. This package extends the Bezier facility by providing commands to draw linear, rational quadratic, and cubic Bezier curves.

Bezier curves are named after Pierre Bezier who invented them. They are widely used within Computer Aided Design (CAD) programs and other graphics systems; descriptions can be found in many places, with varying degrees of mathematical complexity, such as [FP81, Mor85, Far90].

The Bezier curve is a parameterized curve of degree n and can therefore be specified by (n + 1) points (i.e., point p_{0} through p_{n}). Among its other properties, a Bezier curve of degree n passes through through the points p_{0} and p_{n} and passes close to the other defining points. The general equation for a Bezier curve of degree n with parameter t is

p(t) = a_{0} + a_{1}t + a_{2}t^{2} + ⋯ + a_{n}t^{n}  (1)

where the coefficients a_{i} depend on the defining points, and traditionally 0 ≤ t ≤ 1. For a linear (degree 1) curve, the equation is

p(t) = p_{0} + (p_{1} − p_{0})t  (2)

By inspection, p(0) = p_{0} and p(1) = p_{1}.

Rearranging equation (1) slightly we get

p(t) − p_{0} = (p_{1} − p_{0})t  (3)

In other words, we can march along the curve from the starting point to the ending point by evaluating the right hand side of equation (3) for increasing values of the parameter t.

In order to shorten the equations slightly, and also make them more convenient to work with numerically, we will use the notation

l_{pq} = p_{p} − p_{q}

Thus, the final form for the linear Bezier curve is

p(t) − p_{0} = l_{10}t  (4)

\lbezier The command \lbezier[⟨N ⟩](⟨p0 ⟩)(⟨p1 ⟩) draws a linear Bezier curve with ⟨N ⟩ plotted points from the point ⟨p0 ⟩ (with coordinates ⟨x0,y0 ⟩) to the point ⟨p1 ⟩ (with coordinates ⟨x1,y1 ⟩). ⟨N ⟩ is an optional argument. If it is either not given or is given with a value of zero, then the command will calculate the number of points to be plotted, subject to a maximum number. There must be no spaces between the arguments to the \lbezier command; this restriction also applies to the other Bezier drawing commands provided by the bez123 package.

Figure 3 shows an example of a dotted line drawn using the \lbezier command. The actual code used is:

 \lbezier[50](15,30)(30,0)

thus drawing a straight line consisting of 50 points.

\qbeziermax The standard L^{A}TEX command \qbeziermax sets a maximum limit on the

number of points used to draw any of the Bezier curves.

\thinlines The ‘points’ used in drawing the Bezier curves are small squares. The size

\thicklines
\linethickness

of these squares are controlled by the standard L^{A}TEX \thinlines, \thicklines and/or \linethickness commands. Consult Lamport [Lam94] for descriptions of these, and \qbeziermax, commands.

It is convenient to introduce some general properties of Bezier curves at this point.

[figure: 0; 1; 2; 3; 0, 3; 1; 2; 0; 2; 3; 1; 0; 1; 2; 3]

Figure 1: Four sets of points and their convex hulls

• A degree n Bezier curve is defined by (n+1) points which we will label as p_{0} through p_{n}. The lines joining the points p_{0}, p_{1}, …, p_{n} are called the control polygon. The Bezier curve is parameterized by a variable we will call t, with 0 ≤ t ≤ 1.

• A degree n Bezier curve starts at point p_{0} and ends at point p_{n}.

• At t = 0 the curve passes through p_{0} and is tangent to the line l_{10} = p_{1} − p_{0}.

• At t = 1 the curve passes through p_{n} and is tangent to the line l_{(n)(n−1)} = p_{n} − p_{(n−1)}.

• A non-rational Bezier curve lies within the convex hull^{1} of the points p_{0} through p_{n}. For examples of convex hulls see figure 1. Note that the shape of a convex hull is independant of the ordering of the points.

The equation for cubic Bezier curves is

p(t) − p_{0} = 3l_{10}t + 3(l_{21} − l_{10})t^{2} + (l_{30} − 3l_{21})t^{3}  (5)

\cbezier The command \cbezier[⟨N ⟩](⟨p0 ⟩)(⟨p1 ⟩)(⟨p2 ⟩)(⟨p3 ⟩) draws a cubic Bezier curve, as defined by equation (5), from point ⟨p0 ⟩ to point ⟨p3 ⟩, where ⟨p1 ⟩ and ⟨p2 ⟩ are the intermediate points defining the control polygon.

1The convex hull can be thought of as the shape that a rubber band will take if it is stretched around pins placed at each point.

Figure 2: Four sets of points, the cubic Bezier curves and their control polygons. Left — curves plotted with N = 30; Right — curves plotted with N = 0

Figure 2 shows four such cubic Bezier curves, their defining points and their control polygons. These are the same points that were used in figure 1 to illustrate convex hulls. It is easy to verify that a cubic Bezier curve does indeed lie within the convex hull of its defining points. The curves on the left of the figure were specified with a value of 30 for the argument ⟨N ⟩, while those on the right had no value given for ⟨N ⟩ and thus were drawn with the number of plotted points calculated by the drawing algorithm. The actual drawing commands used were:

 \cbezier[30](0,0)(10,30)(20,0)(30,30)
 \cbezier[30](0,0)(30,0)(0,30)(0,0)
 \cbezier(0,0)(30,30)(10,30)(20,0)
 \cbezier(0,0)(30,0)(0,30)(10,10)

Note that points are plotted along the curve at equidistant values of the of the parameter t. However, as the relationship between the actual distance in (x, y) coordinate space is a non-linear function of t, the seperation between the plotted points is non-uniform.

The equation for a non-rational quadratic Bezier curve is

p(t) − p_{0} = 2l_{10}t + (l_{20} − 2l_{10})t^{2}  (6)

Using standard L^{A}TEX this can be drawn by the \qbezier command. There is another form of a quadratic Bezier curve called a rational quadratic Bezier curve.

Table 1: Conic forms of the rational quadratic Bezier curve

Conic form  Weight (W)
Hyperbola  ∥W ∥ > 1
Parabola  ∥W ∥ = 1
Ellipse  0 < ∥W ∥ < 1
Circle  ∥l_{10}∥ = ∥l_{21}∥ and W = cos β
Straight line  W = 0

Its equation is

p(t) − p_{0} = \frac{2w_{1}l_{10}t + (w_{2}l_{20} − 2w_{1}l_{10})t^{2}}{w_{0} + 2ω_{10}t + (ω_{20} − ω_{10})t^{2}}  (7)

where the w_{i} are the weights corresponding to the points p_{i} and ω_{pq} = w_{p} − w_{q}. The shape of a non-rational curve can be changed by changing the positions of the defining points. The shape of a rational curve can also be modified by changing the values of the weights. A rational curve has the same general properties, outlined above, as a non-rational curve with the exception that the curve may lie outside the convex hull of the control polygon.

For the purposes at hand, we use a more restricted form of a rational quadratic Bezier curve, obtained by putting W = w_{1}/w_{0} and then making w_{0} = w_{2} = 1 in equation (7). Performing these substitutions we end up with

p(t) − p_{0} = \frac{2W l_{10}t + (l_{20} − 2W l_{10})t^{2}}{1 + 2(1 − W)t + 2(1 − W)t^{2}}  (8)

Note that when W = 1, (8) reduces to equation (6) and when W = 0 it effectively reduces to equation (4).

It turns out that a non-rational quadratic Bezier curve is an arc of a parabola, which is one of the conic curves. All the other conic curves can be represented by the rational quadratic Bezier curve described by equation (8) by suitable choices for the value of W. From now on, we will call W the weight of the rational quadratic Bezier curve. Table 1 lists the value, or value range, of W for the various forms of the conic curve.^{2} For the case of a circle, β is the angle between the lines l_{10} = (p_{1} − p_{0}) and l_{20} = (p_{2} − p_{0}), as shown in figure 3.

\rqbezier The command \rqbezier[⟨N ⟩](⟨p0 ⟩)(⟨p1 ⟩)(⟨p2 ⟩)(⟨W ⟩) draws a rational quadratic Bezier curve from ⟨p0 ⟩ to ⟨p2 ⟩ with weight ⟨W ⟩, according to equation (8). As in the other Bezier commands, ⟨N ⟩ is optional and controls the number of plotted points along the curve. Figure 4 shows several rational quadratic curves, all with the same control polygon but with differing values for the weight W. The code is:

   \rqbezier[100](15,30)(0,0)(30,0)(4)
   \rqbezier[100](15,30)(0,0)(30,0)(2)
   \rqbezier(15,30)(0,0)(30,0)(1)
   \rqbezier[100](15,30)(0,0)(30,0)(0.75)

2We do not deal with the degenerate cases.

[figure: 1; 0; 2; β]

Figure 3: The angle β

[figure: 1; 0; 2]

Figure 4: The effect of weight variation (W ≥ 0) on rational quadratic Bezier curves (weightscale = 10000 (the default))

   \rqbezier[100](15,30)(0,0)(30,0)(0.5)
   \rqbezier[100](15,30)(0,0)(30,0)(0.25)
   \rqbezier(15,30)(0,0)(30,0)(0)

When W > 1 the curve is pulled toward the point p_{1}. Conversely, when W < 1 the curve is pushed away from the point p_{1}. In all cases, though, the curve starts and stops at p_{0} and p_{2} respectively.

Like the case of the cubic curve, points are plotted at equidistant values of the parameter t. The relationship between parameter value and coordinate positions in the rational case are highly non-linear. Thus the distance between the plotted points can vary quite remarkably. This is an inherent disadvantage with this type of curve. The user’s remedy is to increase the number of points to be plotted, but this can lead to TEX running out of memory, not to mention the increased time to generate the drawing.

\setweightscale Because of the way in which TEX performs arithmetic, and especially division, \resetweightscale it is necessary to perform some scaling operations on the divisor when evaluat-

ing equation (8). The optimum value for the scaling is a complex function of the weight and the size and orientation of the control polygon. The algorithm uses a heuristic approach to calculate a ‘good’ value but is not always successful.

            [figure: 1; 0; 2; weightscale = 100; 1; 0; 2; weightscale = 1000; 1; 0; 2; weightscale = 10000; 1; 0; 2; weightscale = 100000]

Figure 5: The effect of weightscale on the drawing of rational quadratic Bezier curves

The \setweightscale{⟨number⟩} command can be used to specify a scale factor. ⟨number⟩ must be a positive integer. The \resetweightscale command resets the scale factor to its default value, which is currently 10000 (ten thousand).

Figure 5 illustrates the effect on changing the weightscale used for drawing the same curves as shown in figure 4. Note that the weightscale has no effect when W = 1 or W = 0 as in these cases the curves are drawn using the algorithms for the \qbezier and \lbezier commands respectively.

It is obvious that some choices give very poorly formed curves. In other cases the curves may be poorly formed but do result in interesting cross-stitch like patterns.

Table 1 indicates that it is possible to draw circular arcs using a rational quadratic Bezier curves. The two legs of the control polygon define the tangents to the curve at the end points. Therefore, to draw a circular arc the two legs must be equal in length. That is, the convex hull is an isosceles triangle. In the special case when the convex hull forms an equilateral triangle, the required weight (cos β, see figure 3) for drawing a circular arc is cos β = 0.5. Further, for any given control polygon the the curves drawn with weights of ±W are complementary. That is, the curve with weight −W is the ‘remainder’ of the curve drawn with weight W. Thus, we have a simple means of drawing a complete circle, as shown in figure 6. The plotting commands of interest were:

     \lbezier[25](0,0)(15,26)
     \lbezier[25](0,0)(30,0)

[figure: 1; 0; 2]

Figure 6: Rational quadratics with weights of ±0.5 and an equilateral triangular

convex hull (weightscale = 50000)

     \setweightscale{50000}
     \rqbezier[100](15,26)(0,0)(30,0)(0.5)
     \rqbezier[200](15,26)(0,0)(30,0)(-0.5)
     \resetweightscale

where the \lbezier drawing commands were used to draw the dotted outline of the control polygon.

A more robust picture of the same circle is shown in figure 7 where the complete circle is pieced together from three non-complementary circular arcs. The drawing commands of interest were

     \rqbezier[100](15,26)(0,0)(30,0)(0.5)
     \rqbezier[100](30,0)(60,0)(45,26)(0.5)
     \rqbezier[100](45,26)(30,52)(15,26)(0.5)

The astute reader will have realised that the divisor in equation (8) can go to zero, and can even be negative. This has interesting consequences, both when trying to do computer arithmetic, and also on the the kind of curve that results. Essentially, the curve tends to ∞ as W → +0. At W = −0 the curve is at −∞ and then it tends to −0 as W → −∞. We will get a curve point at ∞ whenever W = −1 and a ‘negative’ curve for W < −1.

This effect is shown in figure 8 which draws the two branches of a hyperbola. The basic code for the illustration was

     \lbezier[25](30,20)(0,10)
     \lbezier[25](0,10)(30,0)
     \rqbezier[100](30,20)(0,10)(30,0)(2)

[figure]

Figure 7: Three rational quadratics with weights of 0.5 (weightscale = 10000)

[figure]

Figure 8: A rational quadratic that has gone negative; weights of ±2 (weightscale

= 10000)

     \rqbezier[100](30,20)(0,10)(30,0)(-2)

where the control polygon was drawn using the \lbezier commands.

3 The bez123 package implementation

L^{A}TEX provides a facility for drawing quadratic Bezier curves. This package provides additional facilities for drawing linear, rational quadratic, and cubic Bezier curves.

Announce the name and version of the package, which requires L^{A}TEX 2ε.

1 ⟨∗bez⟩

 2 \NeedsTeXFormat{LaTeX2e}
 3 \ProvidesPackage{bez123}[1998/10/14 v1.1 Bezier curves]

The package also requires the multiply package.

 4 \RequirePackage{multiply}[1998/10/14]

5 ⟨/bez⟩

3.1 Arithmetic in TEX

All arithmetic in TEX is based on integer arithmetic, with a maximum integer value of M = 1073741823. For example, 8/3 = 2, 9/3 = 3, and 10/3 = 3. In other words, division always reduces the absolute value of the dividend, and also possibly truncates the value. One consequence of this is that the ordering of multiplication and division is important. For instance, (8 × 3)/3 = 8 but (8/3) × 3 = 6! Thus, in arithmetic calculations involving both multiplication and division, the dividend should be maximised and the divisor minimised, with multiplication preceeding division; also remembering that there is a limit on the size of an integer. To avoid multiplication overflow when calculating say, a × b, we must ensure that ∥a∥ ≤ ∥M/b∥.

When calculating polynomials, such as that in equation (1), we use a technique called Horner’s schema, which is also known as nested multiplication. A general cubic equation, for example, can be written as:

p(t) − a_{0} = t(a_{1} + t(a_{2} + ta_{3}))  (9)

The following pseudo-code shows one way to implement Horner’s schema for plotting N points in the interval 0 ≤ t ≤ 1 of equation (9) using integer arithmetic.

 procedure plot_cubic(a0, a1, a2, a3:vector; N:integer);
   local p:vector; end_local;
   a3 := a3/N;
   repeat i := 0 to N by 1;
     p := a3*i;
     p := p + a2; p := p/N; p := p*i;
     p := p + a1; p := p/N; p := p*i;
     draw(p + a0);

   end_repeat;
   return;
 end_procedure;

We use the above algorithm, with suitable modifications according to the degree of the polynomial, for plotting the points along Bezier curves.

3.2 Linear Bezier curves

6 ⟨∗bez⟩

As a linear curve is simpler than a quadratic curve there is no need to declare extra variables from those used in the kernel by the \qbezier macro.

\lbezier The user command to draw a linear Bezier curve represented by equation (4). The form of the command is:

\lbezier[⟨N ⟩]{(⟨p0 ⟩)(⟨p1 ⟩)

where ⟨pN ⟩ is the comma seperated X and Y coordinate values of point pN.

 7 \newcommand{\lbezier}[2][0]{\@lbez{#1}#2}

\@lbez The drawing macro.

 8 \gdef\@lbez#1(#2,#3)(#4,#5){%
 9 %%%%\def\lbezier#1(#2,#3)(#4,#5){%
10 \ifnum #1<\@ne

When the number of plotting points are not given, then we calculate how many are needed. First determine the X distance between the end points.

11  \@ovxx = #4\unitlength
12  \advance\@ovxx by -#2\unitlength
13  \ifdim \@ovxx < \z@
14  \@ovxx = -\@ovxx
15  \fi

Similarly calculate the Y distance.

16  \@ovyy = #5\unitlength
17  \advance\@ovyy by -#3\unitlength
18  \ifdim \@ovyy < \z@
19  \@ovyy = -\@ovyy
20  \fi

Temporarily store the maximum distance in \@multicnt.

21  \ifdim \@ovxx > \@ovyy
22  \@multicnt = \@ovxx
23  \else
24  \@multicnt = \@ovyy
25  \fi

We use a small square as the visual representation of a point. Calculate the number of points required to give 50% overlap of adjacent squares, making sure that it doesn’t exceed the limit. Store the result in \@multicnt.

26  \@ovxx = 0.5\@halfwidth
27  \divide\@multicnt by \@ovxx
28  \ifnum \qbeziermax < \@multicnt
29  \@multicnt = \qbeziermax\relax
30  \fi
31 \else

The number of points is given.

32  \@multicnt = #1\relax
33 \fi

Now we can prepare the constants for the plotting loop.

34 \@tempcnta = \@multicnt
35 \advance\@tempcnta by \@ne
36 \@ovdx = #4\unitlength
37  \advance\@ovdx by -#2\unitlength
38  \divide\@ovdx by \@multicnt
39 \@ovdy = #5\unitlength
40  \advance\@ovdy by -#3\unitlength
41  \divide\@ovdy by \@multicnt

The next bit of code defines the size of the square representing a point.

42 \setbox\@tempboxa\hbox{\vrule \@height\@halfwidth
43  \@depth \@halfwidth
44  \@width \@wholewidth}%

Start the plot at the first point.

45 \put(#2,#3){%
46  \count@ = \z@
47  \@whilenum{\count@ < \@tempcnta}\do

Evaluate the polynomial (simple in this case) using Horner’s schema.

48  {\@xdim = \count@\@ovdx
49  \@ydim = \count@\@ovdy

Plot this point.

50  \raise \@ydim
51  \hb@xt@\z@{\kern\@xdim
52  \unhcopy\@tempboxa\hss}%
53  \advance\count@\@ne}}%

The end of the definition of \@lbez.

54 }

3.3 Cubic Bezier curves

As cubic curves are more complex than quadratic curves we need some extra variables.

{\@wxc \atop \@wyc} Lengths.
55 \newlength{\@wxc}
56 \newlength{\@wyc}

\cbezier The user command for drawing a cubic Bezier curve as represented by equation (5). It is called as: \cbezier[⟨N ⟩](⟨p0 ⟩)(⟨p1 ⟩)(⟨p2 ⟩)(⟨p3 ⟩).

57 \newcommand{\cbezier}[2][0]{\@cbez{#1}#2}

\@cbez The drawing macro for cubic Bezier curves.

58 \gdef\@cbez#1(#2,#3)(#4,#5)(#6,#7)(#8,#9){%
59 \ifnum #1<\@ne

We have to calculate the number of plotting points required. We will use the maximum of the box enclosing the convex hull as a measure. First do the X value, using \@ovxx to store the maximum X coordinate and \@ovdx the minimum.

60  \@ovxx = #2\unitlength
61  \@ovdx = \@ovxx
62  \@ovdy = #4\unitlength
63  \ifdim \@ovdy > \@ovxx
64  \@ovxx = \@ovdy
65  \fi
66  \ifdim \@ovdy < \@ovdx
67  \@ovdx = \@ovdy
68  \fi
69  \@ovdy = #6\unitlength
70  \ifdim \@ovdy > \@ovxx
71  \@ovxx = \@ovdy
72  \fi
73  \ifdim \@ovdy < \@ovdx
74  \@ovdx = \@ovdy
75  \fi
76  \@ovdy = #8\unitlength
77  \ifdim \@ovdy > \@ovxx
78  \@ovxx = \@ovdy
79  \fi
80  \ifdim \@ovdy < \@ovdx
81  \@ovdx = \@ovdy
82  \fi

Store the maximum X in \@ovxx.

83  \advance\@ovxx by -\@ovdx

Repeat the process for the maximum Y value, finally storing this in \@ovyy.

84  \@ovyy = #3\unitlength
85  \@ovdy = \@ovyy
86  \@ovdx = #5\unitlength
87  \ifdim \@ovdx > \@ovyy
88  \@ovyy = \@ovdx
89  \fi
90  \ifdim \@ovdx < \@ovdy
91  \@ovdy = \@ovdx
92  \fi
93  \@ovdx = #7\unitlength

 94  \ifdim \@ovdx > \@ovyy
 95  \@ovyy = \@ovdx
 96  \fi
 97  \ifdim \@ovdx < \@ovdy
 98  \@ovdy = \@ovdx
 99  \fi
100  \@ovdx = #9\unitlength
101  \ifdim \@ovdx > \@ovyy
102  \@ovyy = \@ovdx
103  \fi
104  \ifdim \@ovdx < \@ovdy
105  \@ovdy = \@ovdx
106  \fi
107  \advance\@ovyy by -\@ovdy

Temporarily store the max of X and Y in \@multicnt.

108  \ifdim \@ovxx > \@ovyy
109  \@multicnt = \@ovxx
110  \else
111  \@multicnt = \@ovyy
112  \fi

Calculate the number of points required to give 50% overlap, making sure that it doesn’t exceed the limit. Store the number of points in \@multicnt.

113  \@ovxx = 0.5\@halfwidth
114  \divide\@multicnt by \@ovxx
115  \ifnum \qbeziermax < \@multicnt
116  \@multicnt = \qbeziermax\relax
117  \fi
118 \else

The number of points is given.

119  \@multicnt = #1\relax
120 \fi

Now we can prepare the constants for the plotting loop. First the control counts.

121 \@tempcnta = \@multicnt
122 \advance\@tempcnta by \@ne

Then the cubic coefficients, firstly for X.

123 \@ovdx = #4\unitlength  \advance\@ovdx by -#2\unitlength
124 \@ovxx = #6\unitlength  \advance\@ovxx by -\@ovdx
125 \multiply\@ovdx by \thr@@
126 \advance\@ovxx by -#4\unitlength  \multiply\@ovxx by \thr@@
127 \@wxc = #4\unitlength  \advance\@wxc by -#6\unitlength
128 \multiply\@wxc by \thr@@  \advance\@wxc by #8\unitlength
129 \advance\@wxc by -#2\unitlength \divide\@wxc by \@multicnt

And similarly for Y.

130 \@ovdy = #5\unitlength  \advance\@ovdy by -#3\unitlength
131 \@ovyy = #7\unitlength  \advance\@ovyy by -\@ovdy

132 \multiply\@ovdy by \thr@@
133 \advance\@ovyy by -#5\unitlength  \multiply\@ovyy by \thr@@
134 \@wyc = #5\unitlength  \advance\@wyc by -#7\unitlength
135 \multiply\@wyc by \thr@@  \advance\@wyc by #9\unitlength
136 \advance\@wyc by -#3\unitlength \divide\@wyc by \@multicnt

Set up the plotting box.

137 \setbox\@tempboxa\hbox{\vrule \@height\@halfwidth
138  \@depth \@halfwidth
139  \@width \@wholewidth}%

Start the plot at the first point.

140 \put(#2,#3){%
141  \count@ = \z@
142  \@whilenum{\count@ < \@tempcnta}\do
143  {\@xdim = \count@\@wxc
144  \advance\@xdim by \@ovxx
145  \divide\@xdim by \@multicnt
146  \multiply\@xdim by \count@
147  \advance\@xdim by \@ovdx
148  \divide\@xdim by \@multicnt
149  \multiply\@xdim by \count@
150  \@ydim = \count@\@wyc
151  \advance\@ydim by \@ovyy
152  \divide\@ydim by \@multicnt
153  \multiply\@ydim by \count@
154  \advance\@ydim by \@ovdy
155  \divide\@ydim by \@multicnt
156  \multiply\@ydim by \count@

Plot the point.

157  \raise \@ydim
158  \hb@xt@\z@{\kern\@xdim
159  \unhcopy\@tempboxa\hss}%
160  \advance\count@\@ne}}%

The end of the definition of \@cbez.

161 }

3.4 Quadratic rational Bezier curve

This is the most complex of the Bezier curves that we deal with. We need yet more variables.

\@ww \@wwa \@wwb \@wwo \@wwi Variables for the weight calculations.

162 \newlength{\@ww}
163 \newlength{\@wwa}
164 \newlength{\@wwb}
165 \newlength{\@wwo}
166 \newlength{\@wwi}

\c@@pntscale Scale factor for points.

167 \newcounter{@pntscale}

\c@weightscale Scale factor for divisor.

168 \newcounter{weightscale}

\botscale Scale factor for bottom weights.

169 \newlength{\botscale}

\setweightscale User level command \setweightscale{⟨number⟩} for setting the divisor scaling.

170 \newcommand{\setweightscale}[1]{\setcounter{weightscale}{#1}}

\resetweightscale User level command for setting the divisor scaling to its default value (10^{4}). We also ensure that the scaling is set to this value.

171 \newcommand{\resetweightscale}{\setcounter{weightscale}{10000}}
172 \resetweightscale

\rqbezier The user level command for drawing a rational quadratic Bezier curve as represented by equation (8). The form of the command is

\rqbezier[⟨N ⟩](⟨p0 ⟩)(⟨p1 ⟩)(⟨p2 ⟩)(⟨W ⟩)

where the arguments are as per the other Bezier drawing commands, but with the final argument being the weight.

173 \newcommand{\rqbezier}[2][0]{\@rqbez{#1}#2}

\@rqbez The drawing macro for a rational quadratic Bezier curve. If the weight is such that the curve is either rational quadratic (W = 1) or linear (W = 0), we use the simpler drawing macro.

174 \gdef\@rqbez#1(#2,#3)(#4,#5)(#6,#7)(#8){%
175 \@ovxx = #8\unitlength
176 \ifdim\@ovxx = \unitlength
177  \PackageWarning{bez123}{Rational quadratic denerates to quadratic}
178  \qbezier[#1](#2,#3)(#4,#5)(#6,#7)
179 \else
180  \ifdim\@ovxx = \z@
181  \PackageWarning{bez123}{Rational quadratic degenerates to linear}
182  \lbezier[#1](#2,#3)(#6,#7)
183  \else

Calculate the maximum length of the control polygon’s bounding box. Store the result in \@wwi.

184  \@ovxx = #4\unitlength
185  \advance\@ovxx by -#2\unitlength
186  \ifdim \@ovxx < \z@
187  \@ovxx = -\@ovxx
188  \fi
189  \@ovdx = #6\unitlength
190  \advance\@ovdx by -#4\unitlength
191  \ifdim \@ovdx < \z@

192  \@ovdx = -\@ovdx
193  \fi
194  \ifdim \@ovxx < \@ovdx
195  \@ovxx = \@ovdx
196  \fi
197  \@ovyy = #5\unitlength
198  \advance\@ovyy by -#3\unitlength
199  \ifdim \@ovyy < \z@
200  \@ovyy = -\@ovyy
201  \fi
202  \@ovdy = #7\unitlength
203  \advance\@ovdy by -#5\unitlength
204  \ifdim \@ovdy < \z@
205  \@ovdy = -\@ovdy
206  \fi
207  \ifdim \@ovyy < \@ovdy
208  \@ovyy = \@ovdy
209  \fi
210  \ifdim \@ovxx > \@ovyy
211  \@multicnt = \@ovxx
212  \else
213  \@multicnt = \@ovyy
214  \fi
215  \@wwi = \@multicnt sp

Now determine the number of points to be plotted.

216 \ifnum #1<\@ne
217  \@ovxx = 0.5\@halfwidth
218  \divide\@multicnt by \@ovxx
219  \ifnum\qbeziermax < \@multicnt
220  \@multicnt = \qbeziermax\relax
221  \fi
222 \else

Number of points is a given.

223  \@multicnt = #1\relax
224 \fi

We are going to plot the curve in two halves in an attempt to reduce roundoff problems. At a minimum this should at least make a symmetrical curve look symmetric about its mid point.

225 \@tempcnta = \@multicnt
226 \advance\@tempcnta by \@ne
227 \divide\@tempcnta by \tw@
228 \advance\@tempcnta by \@ne

We now have to deal with a possible multiplication overflow problem due to multiplication by the weight. In equation (8) the potentially largest term is the coefficient of t^{2} (i.e., (l_{20} − 2W l_{10})). The maximum length likely to be encountered is, say, 10 inches for a drawing on either A4 or US letterpaper. This is approximately 4.8×10^{8}sp. Doing a little arithmetic, and remembering that the maximum length in TEX is M = 1073741823sp, it means that we must have ∥W ∥ ≤ 1 to prevent overflow. However, a typical range for W is −10 ≤ W ≤ 10. Therefore we might have to do some scaling. Being pessimistic, we’ll assume that l_{20} = −l_{10} and that l_{10} is the largest dimension in the drawing. To prevent overflow we then have to meet the condition ∥W ∥ ≤ (M − l_{20})/2l_{20}, where all lengths are positive. We will use \c@@pntscale as a scale factor on W to meet this condition. Earlier we set \@wwi to be the positive value of the largest dimension in the drawing.

Set the distance scale factor. First evaluating the test condition.

229 \@wwo = \maxdimen
230  \advance\@wwo by -\@wwi
231  \divide\@wwo by \tw@
232  \divide\@wwo by \@wwi

Now perform the check and set the scale factor. We have to get a positive integer value for W as it may be a fraction. Actually, we only need to be concerned if ∥W ∥ > 1.

233 \@wwi = 10sp
234 \@wwi = #8\@wwi
235  \ifdim\@wwi < \z@
236  \@wwi = -\@wwi
237  \fi
238  \divide\@wwi by 10\relax
239 \ifdim\@wwi < \@wwo
240  \c@@pntscale = \@ne
241 \else
242  \divide\@wwi by \tw@
243  \ifdim\@wwi < \@wwo
244  \c@@pntscale = \tw@
245  \else
246  \divide\@wwi by \tw@
247  \ifdim\@wwi < \@wwo
248  \c@@pntscale = 4\relax
249  \else
250  \divide\@wwi by \tw@
251  \ifdim\@wwi < \@wwo
252  \c@@pntscale = 8\relax
253  \else
254  \c@@pntscale = 16\relax
255  \fi
256  \fi
257  \fi
258 \fi

Calculate the constants for the top line of the function.

259 \@ovxx = #4\unitlength \advance\@ovxx by -#2\unitlength
260  \multiply\@ovxx by \tw@
261  \divide\@ovxx by \c@@pntscale
262  \@ovdx = #8\@ovxx
263 \@ovxx = #6\unitlength  \advance\@ovxx by -#2\unitlength
264  \divide\@ovxx by \c@@pntscale

265  \advance\@ovxx by -\@ovdx
266  \divide\@ovxx by \@multicnt
267 \@ovyy = #5\unitlength \advance\@ovyy by -#3\unitlength
268  \multiply\@ovyy by \tw@
269  \divide\@ovyy by \c@@pntscale
270  \@ovdy = #8\@ovyy
271 \@ovyy = #7\unitlength  \advance\@ovyy by -#3\unitlength
272  \divide\@ovyy by \c@@pntscale
273  \advance\@ovyy by -\@ovdy
274  \divide\@ovyy by \@multicnt

Now the constants for the bottom line. We also need to do some scaling here. This scaling can be set by the user.

275 \setlength{\botscale}{\c@weightscale sp}
276 \@wwo = \botscale
277 \@wwi = #8\@wwo
278 \@wwa = \@wwo  \advance\@wwa by -\@wwi
279  \multiply\@wwa by \tw@
280 \@wwb = \@wwa
281  \divide\@wwb by \@multicnt

Prepare for the drawing.

282 \@wwi = \botscale
283 \setbox\@tempboxa\hbox{\vrule \@height\@halfwidth
284  \@depth \@halfwidth
285  \@width \@wholewidth}%

Draw the first half of the curve.

286 \put(#2,#3){%
287  \count@ = \z@
288  \@whilenum{\count@ < \@tempcnta}\do
289  {\@xdim = \count@\@ovxx
290  \advance\@xdim by \@ovdx
291  \divide\@xdim by \@multicnt
292  \multiply\@xdim by \count@
293  \@ydim = \count@\@ovyy
294  \advance\@ydim by \@ovdy
295  \divide\@ydim by \@multicnt
296  \multiply\@ydim by \count@
297  \@ww = \count@\@wwb
298  \advance\@ww by -\@wwa
299  \divide\@ww by \@multicnt
300  \multiply\@ww by \count@
301  \advance\@ww by \@wwo
302  \divide\@ww by \c@@pntscale
303  \ifdim\@ww = \z@

We are about to divide by \@ww which is zero. Treat \@ww as unity.

304  \else
305  \divide\@xdim by \@ww
306  \divide\@ydim by \@ww
307  \fi

For reasons I don’t understand, the % signs at the end of the next few lines are important!

308  \multnooverflow{\@xdim}{\botscale}%
309  \multnooverflow{\@ydim}{\botscale}%
310  \raise \@ydim
311  \hb@xt@\z@{\kern\@xdim
312  \unhcopy\@tempboxa\hss}%
313  \advance\count@\@ne}}

We now repeat the above process for plotting the second half of the curve, starting at the end point.

Calculate the constants for the top line of the function.

314 \@ovxx = #4\unitlength \advance\@ovxx by -#6\unitlength
315  \multiply\@ovxx by \tw@
316  \divide\@ovxx by \c@@pntscale
317  \@ovdx = #8\@ovxx
318 \@ovxx = #2\unitlength  \advance\@ovxx by -#6\unitlength
319  \divide\@ovxx by \c@@pntscale
320  \advance\@ovxx by -\@ovdx
321  \divide\@ovxx by \@multicnt
322 \@ovyy = #5\unitlength \advance\@ovyy by -#7\unitlength
323  \multiply\@ovyy by \tw@
324  \divide\@ovyy by \c@@pntscale
325  \@ovdy = #8\@ovyy
326 \@ovyy = #3\unitlength  \advance\@ovyy by -#7\unitlength
327  \divide\@ovyy by \c@@pntscale
328  \advance\@ovyy by -\@ovdy
329  \divide\@ovyy by \@multicnt

The constants for the bottom line are the same as before as the function is symmetric. Similarly we don’t need to recalculate the size of the rule box.

Draw the second half of the curve.

330 \put(#6,#7){%
331  \count@ = \z@
332  \@whilenum{\count@ < \@tempcnta}\do
333  {\@xdim = \count@\@ovxx
334  \advance\@xdim by \@ovdx
335  \divide\@xdim by \@multicnt
336  \multiply\@xdim by \count@
337  \@ydim = \count@\@ovyy
338  \advance\@ydim by \@ovdy
339  \divide\@ydim by \@multicnt
340  \multiply\@ydim by \count@
341  \@ww = \count@\@wwb
342  \advance\@ww by -\@wwa
343  \divide\@ww by \@multicnt
344  \multiply\@ww by \count@
345  \advance\@ww by \@wwo
346  \divide\@ww by \c@@pntscale
347  \ifnum\@ww = \z@

We are about to divide by \@ww which is zero. Treat \@ww as unity.

348  \else
349  \divide\@xdim by \@ww
350  \divide\@ydim by \@ww
351  \fi

For reasons I don’t understand, the % signs at the end of the next few lines are important!

352  \multnooverflow{\@xdim}{\botscale}%
353  \multnooverflow{\@ydim}{\botscale}%
354  \raise \@ydim
355  \hb@xt@\z@{\kern\@xdim
356  \unhcopy\@tempboxa\hss}%
357  \advance\count@\@ne}}
358 % End of definition of |\@rqbez|.
359 %    \begin{macrocode}
360 \fi\fi}

The end of this package.

361 ⟨/bez⟩

4 Multiplication without overflow: The multiply package

TEX provides for integer arithmetic, subject to an upper limit given by \maxdim. For at least the bez123 package we need to be able to multiply without overflow.

Announce the name of the package.

362 ⟨∗mult⟩

363 \ProvidesPackage{multiply}[1998/10/14 v1.1 Multiplication of lengths without overflow]

\n@fl@wa \n@fl@wb \n@fl@wc \ifch@nge We need three length variables for this function. We also need a boolean flag for dealing with negative numbers.

364 \newlength{\n@fl@wa}
365 \newlength{\n@fl@wb}
366 \newlength{\n@fl@wc}
367 \newif\ifch@nge

\multnooverflow The routine \multnooverflow{⟨a⟩}{⟨b⟩} sets a to the minimum of ab and \maxdimen, preserving signs. ⟨a⟩ must be a length; it must not be a number literal.

368 \newcommand{\multnooverflow}[2]{%
369 \n@fl@wa = #1\relax%
370 \n@fl@wb = #2\relax%
371 \ch@ngefalse%

Easy if −1 ≤ b ≤ 1.

372 \ifnum\n@fl@wb = \@ne%

373 \else%
374  \ifnum\n@fl@wb = \z@%
375  \n@fl@wa = \z@%
376  \else%
377  \ifnum\n@fl@wb = \m@ne%
378  \ch@ngetrue%
379  \else%

Also easy if −1 ≤ a ≤ 1.

380  \ifnum\n@fl@wa = \z@%
381  \else%
382  \ifnum\n@fl@wa = \@ne%
383  \n@fl@wa = \n@fl@wb%
384  \else%
385  \ifnum\n@fl@wa = \m@ne%
386  \n@fl@wa = -\n@fl@wb%
387  \else%

We have to check for potential overflow. First make sure that we deal only with positive values.

388  \ifnum\n@fl@wa < \z@%
389  \ch@ngetrue%
390  \n@fl@wa = -\n@fl@wa%
391  \fi%
392  \ifnum\n@fl@wb < \z@%
393  \n@fl@wb = -\n@fl@wb%
394  \ifch@nge%
395  \ch@ngefalse%
396  \else%
397  \ch@ngetrue%
398  \fi%
399  \fi%

Check for overflow.

400  \n@fl@wc = \maxdimen%
401  \divide\n@fl@wc by \n@fl@wb%
402  \advance\n@fl@wc by -1sp% \m@ne
403  \ifnum\n@fl@wa > \n@fl@wc%

We have overflow. Set the multiplication result to \maxdimen.

404  \n@fl@wa = \maxdimen%
405  \PackageWarning{multiply}{Multiplication overflow}%
406  \else%

It is safe to do the multiplication.

407  \multiply\n@fl@wa by \n@fl@wb%
408  \fi%
409  \fi%
410  \fi%
411  \fi%
412  \fi%
413  \fi%

414 \fi%

The result of ab is in \n@fl@wa. Adjust the sign if necessary.

415 \ifch@nge%
416  \n@fl@wa = -\n@fl@wa%
417 \fi%

Return the result in the first argument variable.

418 #1 = \n@fl@wa%

419 }

The end of this package.

420 ⟨/mult⟩

References

[Far90] Gerald Farin. Curves and Surfaces for Computer Aided Geometric Design — A Practical Guide. Academic Press, Inc., second edition, 1990.

[FP81] I. D. Faux and M. J. Pratt. Computational Geometry for Design and Manufacture. Ellis Horwood, 1981.

[GMS94] Michel Goossens, Frank Mittelbach, and Alexander Samarin. The LaTeX Companion. Addison-Wesley Publishing Company, 1994.

[Lam94] Leslie Lamport. LaTeX: A Document Preparation System. Addison-Wesley Publishing Company, second edition, 1994.

[Mor85] Michael E. Mortenson. Geometric Modeling. John Wiley & Sons, Inc., 1985.

[Wil96] Peter R. Wilson. LaTeX for standards: The LaTeX package files user manual. NIST Report NISTIR, June 1996.

Index

Numbers written in italic refer to the page where the corresponding entry is described, the ones underlined to the code line of the definition, the rest to the code lines where the entry is used.

Symbols

\@cbez . . . . . . . . . 57, \underline{58} \@depth … 43, 138, 284

\@halfwidth . . . . 26,

42, 43, 113, 137, 138, 217, 283, 284

\@height . . 42, 137, 283 \@lbez . . . . . . . . . . 7, \underline{8}

                          \@multicnt . . 22, 24,

27–29, 32, 34, 38, 41, 109, 111, 114–116, 119, 121, 129, 136, 145, 148, 152, 155, 211, 213, 215, 218–220, 223, 225, 266, 274, 281, 291, 295, 299, 321, 329, 335, 339, 343 \@ovdx 36–38, 48, 61, 66, 67, 73, 74, 80, 81, 83, 86– 88, 90, 91, 93– 95, 97, 98, 100– 102, 104, 105, 123–125, 147, 189–192, 194, 195, 262, 265, 290, 317, 320, 334

\@ovdy 39–41, 49, 62– 64, 66, 67, 69– 71, 73, 74, 76– 78, 80, 81, 85, 90, 91, 97, 98, 104, 105, 107, 130–132, 154, 202–205, 207, 208, 270, 273, 294, 325, 328, 338

\@ovxx . . . . . . . . 11– 14, 21, 22, 26, 27, 60, 61, 63, 64, 70, 71, 77, 78, 83, 108, 109, 113, 114, 124, 126, 144, 175, 176, 180, 184– 187, 194, 195, 210, 211, 217, 218, 259–266, 289, 314–321, 333

\@ovyy … 16–19, 21, 24, 84, 85, 87, 88, 94, 95, 101, 102, 107, 108, 111, 131, 133, 151, 197–200, 207, 208, 210, 213, 267–274, 293, 322–329, 337

\@rqbez . . . . . . 173, \underline{174}

\@whilenum . . . . . . .

. 47, 142, 288, 332

\@wholewidth 44, 139, 285

\@width … 44, 139, 285 \@ww . . . . . . \underline{162}, 297–

303, 305, 306, 341–347, 349, 350

\@wwa . . . . . . . . \underline{162},

278–280, 298, 342 \@wwb . . . . . . . . \underline{162},

280, 281, 297, 341 \@wwi . \underline{162}, 215, 230, 232–236, 238, 239, 242, 243, 246, 247, 250, 251, 277, 278, 282

\@wwo . . . . . . . . \underline{162}, 229–232, 239, 243, 247, 251, 276–278, 301, 345

\@wxc . . \underline{55}, 127–129, 143 \@wyc . . \underline{55}, 134–136, 150 \@xdim . . . . . . 48, 51,

143–149, 158, 289–292, 305, 308, 311, 333– 336, 349, 352, 355

\@ydim 49, 50, 150–157, 293–296, 306, 309, 310, 337– 340, 350, 353, 354

B

                   \botscale . . . . \underline{169},

275, 276, 282, 308, 309, 352, 353

C

                   \c@@pntscale . . . . . .

. \underline{167}, 240, 244, 248, 252, 254, 261, 264, 269, 272, 302, 316, 319, 324, 327, 346

                   \c@weightscale   \underline{168}, 275

\cbezier . . . . . . . . 3, \underline{57}

                   \ch@ngefalse . . 371, 395
                   \ch@ngetrue 378, 389, 397

\count@ . . . . . . . 46– 49, 53, 141–143, 146, 149, 150, 153, 156, 160, 287–289, 292, 293, 296, 297, 300, 313, 331– 333, 336, 337, 340, 341, 344, 357

D \do … 47, 142, 288, 332

H \hb@xt@ 51, 158, 311, 355

I \ifch@nge . \underline{364}, 394, 415

L \lbezier … 2, \underline{7}, 9, 182

                                             \linethickness . . . . . 3

M \maxdimen . 229, 400, 404

                                             \multiply . . . . . . . .

. 125, 126, 128, 132, 133, 135, 146, 149, 153, 156, 260, 268, 279, 292, 296, 300, 315, 323, 336, 340, 344, 407

                                             \multnooverflow 308,

309, 352, 353, \underline{368}

N \n@fl@wa . . \underline{364}, 369,

375, 380, 382, 383, 385, 386, 388, 390, 403, 404, 407, 416, 418

\n@fl@wb . . . . . \underline{364}, 370, 372, 374, 377, 383, 386, 392, 393, 401, 407

\n@fl@wc . . \underline{364}, 400–403 \newif . . . . . . . . . . . 367

P

                                             \PackageWarning . . .

…. 177, 181, 405

                                             \ProvidesPackage 3, 363

\put … 45, 140, 286, 330

Q \qbezier . . . . . . . . . 178

                                             \qbeziermax 3, 28, 29,

115, 116, 219, 220

R \raise . 50, 157, 310, 354

                                             \RequirePackage . . . . 4
                                             \resetweightscale 7, \underline{171}

\rqbezier . . . . . . 5, \underline{173}

S

\setweightscale . 7, \underline{170}

T

\thicklines . . . . . . . . 3
\thinlines . . . . . . . . 3

\thr@@ …. 125, 126, 128, 132, 133, 135

U

\unhcopy 52, 159, 312, 356

\unitlength 11, 12, 16,

17, 36, 37, 39, 40, 60, 62, 69, 76, 84, 86, 93, 100, 123, 124, 126–131, 133– 136, 175, 176, 184, 185, 189, 190, 197, 198, 202, 203, 259, 263, 267, 271, 314, 318, 322, 326 V \vrule …. 42, 137, 283