Curve design; blending parabolas on the TRS-80. Kimball M. Rudeen.
Writing a program to draw straight lines is not very difficult. There are several ways to draw lines connecting any arbitrary set of points. Curved lines are another problem entirely. When a programmer wants a curve, he usually must find some equation that will generate it for him. This is fine for circles, ellipses, or if your education in analytic geometry extends a bit further, parabolas and hyperbolas. But if the figure you want doesn't fit one of these categories, you have a problem.
I once tried to create a Valentine heart for my wife, using the spiral of Archimedes. This is a simple equation producing a spiral described as "one half of a heart shaped figure." Draw two of these spirals from the same point, one clockwise and one counter-clockwise, and you have a heart. In theory, that is. In fact, what you have is a skinny thing that becomes a heart only after an evening of fudging, patching, and swearing.
Fortunately, there is a better way. I recently took a very good course in computer graphics, courtesy of my employer. This course presented several methods of constructing and shaping curves. This article describes one of the simpler methods, parabolic blending.
Parabolic blending begins with a means of generating a parabola connecting three arbitrary points. Suppose we wish to draw a line between two points (XA, YA) and (XB, YB). This can be done using the equations X=XB*T+XA*(1-T) and Y=YB*T+YA*(1-T) This can be more compactly expressed as the single equation (1)(X(T), Y(T))=(XB, YB)*T+(XA, YA)*(1-T) As the value of T goes from 0 to 1, the value of the two equations will range from (XA, YA) to (XB, YB). For T between 0 and 1, the two equations will produce points on the straight line connecting the two points. This method is known as parametric representation. The X and Y values of the line are defined as functions of a third value, the parameter T.
Parametric representation uses three points to define a parabola. The parametric equations for a parabola are as follows: (2)(X(T), Y(T))=(XA, YA)*(TB-T)*(TC-T)/(TB-TA)*(TC-TA))+ (XB, YB)*(TA-T)*(TC-T)/((TA-TB)*(TC-TB))+ (XC, YC)*(TA-T)*(TB-T)/((TA-TC)*(TB-TC)) for numbers TA, TB, TC. TA, < TB < TC, and the parameter T starts at TA and goes through TB to TC. TA, TB, TC can have any convenient value so long as the relative order TA < TB < TC is maintained. In this article, I shall call points of this kind reference values. Note that for T=TA, (X(T), Y(T))=(XA, YA) and similarly for T=TB and T=TC. As T goes from TA to TC, the points generated fall on the unique parabola connecting (XA, YA), (XB, YB) and (XC, YC). In effect, the parabola is formed by generating a weighted average of the three points. Equation (1) is the parametric equation for a straight line, with reference vlaues TA=0 and TB=1.
Parametric representation could be used to connect more than three points. This is done simply by following the pattern shown in equation (2), and forming functions using T and the reference values T1, ..., TN such that for T=TI, the function for (XI, YI) is equal to 1 and the functions for all other points are equal to zero. Curves generated in this way will always pass through the set of points defining the curve. However, it is hard to see how to write a program which could generate all the functions for an arbitrary number of points. Also, the curves generated in this way tend to be very "wiggly." That is, while the curve will go through the points (X1, Y1) through (XN, YN), in between it is liable to take on extremely large or small values of (X, Y). This method is therefore not very useful for graphic curve generation.
Another possibility is to construct a curve connecting a set of points out of parabolas by drawing a parabola first from P1 to P2 to P3, then from P3 to P4 to P5, and so on. But this approach would not connect an even number of points. Also, the curve generated tends to have cusps. or sharp corners, where the parabolas join. Blending Parabolas
The way to get more than a simple parabola between three points is by blending pairs of parabolas together. As an example, consider Figure 1. Two overlapping parabolas have been drawn between points P1, P2, P3 and P2, P3, P4. This was done by applying equation (2) to P1, P2, P3, and P2, P3, P4 and using reference values 1.0, 2.0, 3.0, 4.0. The first parabola was generated using reference values 1.0, 2.0, 3.0 and the second using reference values 2.0, 3.0, 4.0. Now comes the blending. This was done in much the same manner as was used to draw a straight line between two points in equation (1). However, instead of applying to two single points, the method is applied to pairs of points. There are two step to the process.
First, as T goes from T2 to T3, it is applied in two separate parabolic equations of type (2) to generate points (XF(T), YF(T)) and (XS(T), YS(T)) on the first and second parabolas.
Next, the same value of T is used in the following equation to blend the two points into one point: (3) (X(T), Y(T))=(XS(T), YS(T))*(T-T2)/T3-T2)+ (XF(T), YF(T))*(T3-T)/(T3-T2) which for reference values T2=2.0, T3=3.0 becomes (X(T), Y(T))=(XS(T), YS(T))*(T-2.0)+(XF(T), YF(T))*(3.0-T)
As T goes from 2.0 to 3.0, the points generated by equation (3) range from (XF(2.0), YF(2.0))=P2 to (XS(3.0), YS(3.0))=P3. The blending process uses a single value of T to compute first two points on two parabolas and then uses the same value of T to combine these points into a single point.
The curve generated by this blending is shown by the dotted line in Figure 1. Notice that the dotted line merges smoothly into the curves ending at P2 and beginning at P3.
For an arbitrary set of points P1, P2, ..., PN it is necessary to generate a set of parabolas connecting first P1, P2, P3, then P2, P3, P4 and so on. Then the parabolas must be blended between P2 and P3, etc. where they overlap. In two places, between the first two and last two points, only a single parabola is generated. However, these single parabolas will merge smoothly with the blended curves.
Generating this set of parabolas requires a set of reference values T1, T2, ..., TN for the parabolic eauations. Again, the only requirement is that T1 < T2 < ... < TN. Values of T must be generated from T1 to TN, and then loaded into parabolic and blending equations of form (2) and (3). For any value of T, we can determine the correct equations to use from the position of T on the T1-TN range. Any value on this range will be bracketed by two reference values. For example, at some time we have T5 < T < T6. Then the reference values to use at this time are T4, T5, T6 for the first parabola, connecting points P4, P5, P6, and T5, T6, T7 for the second parabola, connecting points P5, P6, P7. Generating A Closed Curve
The curve generated in this way is open. That is, it begins at one point and ends at another, separate point. This same method can be used to generate a curve that is closed, beginning and ending at P1. It might seem to be enough just to load P1 in as an extra point and connect points P1, ..., PN, P1. However, this does not quite do the job. For an open curve, there is only one parabola between points P1, P2 and between points PN-1, PN, as was mentioned earlier. Also, there is no need to draw a curve between points P1 and PN. With a closed curve, it is necessary to generate and blend overlapping parabolas for every pair of points. For points P1 and P2, we can blend the two parabolas connecting points PN, P1, P2 and points P1, P2, P3. For points PN-1 and PN, we can blend the two parabolas connecting points PN-2, PN-1, PN and points PN-1, PN, P1. Finally, for points PN and P1, we can blend the two parabolas connecting points PN-1, PN, P1 and points PN, P1, P2. This requires loading PN into the point list as a new first point, and P1 and P2 as new last points.
So, we end up using points PN, P1, ..., PN, P1, P2 to generate the closed curve. The curve begins and ends at P1. The additional points inserted in the list as shown will provide the data to generate and blend parabolas between every pair of points defining the curve. The Program
Listing 1 is a program implementing parabolic blending to draw curves. It was written for my computer, a TRS-80 Model III. There should be little difficulty in converting this program to other machines. The program generates a curve by computing a series of points lying on the curve and then connecting them by straight lines.
First, the points defining the curve to be drawn are input visually. A single screen pixel is turned on and can then be moved anywhere on the screen. The input subroutine uses the Model III numeric keypad as a control. This pad is laid out in the pattern: Pressing a number key moves the pixel in the corresponding direction. For example, pressing the 8 key moves the pixel straight up one unit. Pressing the 9 key moves the pixel one unit up and one unit to the right. The pixel keeps moving as long as the key is depressed. Note: the continuously moving pixel is accomplished by using a special feature of the TRS-80 Model III. Users of other computers will have to implement this capacity differently. If it is left out, the pixel will move once every time a key is depressed. The X, Y location of the pixel is reported at the upper lefthand side of the screen. The pixel will not move off the screen on any side.
Pressing key 5 selects a point defining the curve to be generated. It will not move the pixel. The point selected will be marked by a set pixel. Pressing key 0 terminates visual point input.
This form of input is especially useful for curve design. It enables you to shape a curve intuitively by nudging points on a screen instead of refiguring X, Y coordinates. A few minutes of experimentation will give you a good feel as to what kind of curve is generated by a given set of points.
Once the points are entered, the program asks for the number of line segments making up the curve. There must be at least enough to connect every pair of points, or an error message is output and the number of segments is requested again. The more segments you allow, the longer the curve will take to draw and the more precise it will be.
Next, the program sets the control points defining the curve on the screen and branches to the appropriate subroutine to generate an open or closed curve. Both open and closed curve subroutines generate reference points T1, ..., TN and a series of T parameter values. For convenience, the reference values are 1.0, 2.0, ..., up to N. This greatly simplifies equations (2) and (3), since many of their factors are reduced to constant whole numbers like 1.0.
The open curve subroutine generates and blends two sets of parabolic points together, except for the two cases in which only one parabola exists. It then calls the line-drawing subroutine to connect the previous point to the new point.
The closed curve subroutine first loads additional points into the set of control points defining the curve to close it, as was described earlier. The subroutine then generates and blends parabolic points together and calls the line-drawing subroutine.
The subroutine which generates the parabolas uses equation (3) in three steps. Again, notice that this equation has been simplifiecd by the reference values used.
Following curve generation, the program asks whether you want to draw the curve again with a different number of segments or start a new curve. Any answer other than yes or no will terminate the program.
Parabolic blending allows you to shape curves directly, without trying to come up with an equation to do the job. Figure 2 is a cursive R which I was able to draw in only a few minutes. Only ten control points were required, and I am sure it could be done with fewer. The control points generating the R are shown in Figure 3, numbered in the order they are connected. Ninety line segments were used for the curve.
It is possible to generate straight lines with this program. A set of three points only, set in a straight line, will be connected by a very flat parabola identical to a straight line. Straight lines can be included in a curved figure by setting five points in a straight line. The straight line would be between the inner three points.
With parabolic blending and visual input, you are free to think about the curve you want to draw while the computer does the dirty work.