Demystifying Pierre Goood ol' Pierre was an engineer who solved a problem for his boss, gaining a small piece of fame as the father of Bezier curves. What exactly M. Bezier did, though, is hard to fathom from the articles and texts that address these and other interesting curves. Not so here, for I shall use our lingua franca, BASIC, to dissect just how these curves work and how to work them. What Bezier really did: For any point that has traversed a certain 'percentage' across a curve between any two end-points, in which the curve is influenced (or shaped) by one or more other control-points, bezier figured out a method of determining the percentages of influence - weighting - that when applied to the original group of end- and control-points would describe that exact point. Here's a BASIC snapshot of a Bezier curve with two control points: xs = [###] : ys = [###] ' starting point cx = [###] : cy = [###] ' control point 1 dx = [###] : dy = [###] ' control point 2 xe = [###] : ye = [###] ' ending point ' given a set of influences ia, ib, ic, id ' which are all 0 < n < 1 and 1 = ia + ib + ic + id ' find the intermediate point. px= xs*ia + cx*ib + dx*ic + xe*id ' figure the x coordinate px= ys*ia + cy*ib + dy*ic + ye*id ' figure the y coordinate Bezier's solution was a set of influences that vary from 0 to 100% and 100 to 0% which apply to the starting ending points respectively, and a cooresponding set of intermediate influences that each vary from 0 to 44% to 0 (and 0 to 75% to 0 when summed) which apply to the control points. Computer literature (surely an oxymoron) calls these influences blending functions, often signaling a departure from readability for the hallowed mists of mathematical obsfuscation. Some observations about Bezier curves: Control- and end-points have order. The weighting applied by each passes from one to another in turn. It is possible to "get them backwards" and generate a curve that is "counter-intuitive" at best and ugly at worst. Interactive programs that allow setting of control points often draw temporary lines to indicate this order. Computer graphic texts often call attention to the fact that Bezier curves are bounded by the polygon described by connecting the control- and end-points. This means that Bezier curves are smaller than their span, and conversely, these points bigger. Pretty obvious stuff, but more obvious is a program that neglects to make possible a Bezier curve that fills the display space because it limits point specification to the same display space. WYSIWYG mouse-input programmers take heed! Bezier curves are traversed (calculated and plotted) in terms of percentage, e.g. 30% of the way through the calculations that plot the points from the starting point to the ending point. t= .3 ' we'll use t as our loop variable, meaning traversal It is important to emphasize that this 30% traversal is not necessarily 30% of the length of the curve: as much as 2/3 of the calculations of Bezier curves involve less than 1/3 of the physical curve length. Bezier curves can be traversed in steps of 100% - a not-so-useful straight line between the end points; or 50% - giving one intermediate point somewhere between the end-points and the control-points; or in fact, any percentage interval. for t=0 to 1.01 step 1 ' connects end-points for t=0 to 1.01 step .5 ' two steps; start to middle and middle to end input "steps", s a = 1/s for t=0 to 1+s step s Although it is computationally handy to step through the calculation loop in uniform increments, it is not necessary. Ordinarily, though, programs don't bother to change the increment because influences are such that as the control-points' influence increases - and the desired curve increases - the plots generated get closer together. If the interval is sufficiently small, the resulting plot approachs a solid line. More usually, the interval is large enough to produce intermediate points which are connected by a line drawing routine. This interval can be remarkably coarse, on the order of 20 or 30 steps for a curve of 600 units length. If the interval does actually produce a solid linge, the transformation of floating point calculations to integer screen locations produces bumps along the line. Although these might be handled by comparing the slopes of the calculated line and the displayed line and filtering out the unwanted perturbations, this leads to intensifying an already heavy calculational overhead. For most purposes, it may be wiser to increase the interval so that points are gereated a certain distance apart. Some possible approaches to dealing with theses conditions may include caluculating the perimeter of the bounding polygon as a guide to setting the interval, using the slope between end- and control-points as means of categorizing the curves, or to evaluate the curve using a large interval in order to sample the slope changes along the curve. This last might be used to tighten the interval in the "critical" portions and loosen it elsewhere. If the set of points generated for a Bezier curve are used to plot a location of something that moves, say a sprite or a camera, a uniform step size will give a motion that slows down for the curved portion and speeds up in the straight line portions. This may not have the desired property; a program may have to take into consideration just how widely each plot is separated and adjust the interval or the speed at which each position is assumed. The influences are functions of the traversal, not of the input points. That has remarkable implications: 1) the influences for all curves are the same 2) they are fixed by the traversal The speed conscious programmer will immediately yell "Table!" and let much of the calculation overhead leak out his loop onto the floor. (I have to credit Bruce Artwick, whose "Applied Concepts in Microcomputer Graphics (1984, Prentice Hall) was forceful in urging the putting into tables things like sines, cosines and even, I have since discovered on page 258, Bezier curve influences as well!) If the table is built using a small interval, by skipping through the table we can mimic a coarser interval. for t=0 to tablesize step s for t=0 to tablesize step s*2 And since looking at an influence table is useful, here's the one for 16 steps (step size s = .0625 or 1/16). For readability each influence has been multiplied by 100, making this a table of percentages. Each row sums to 100%. Column A applies to starting point, B applies to the first control point, C the second control, and D to the ending point. The shifting of the influence weights is easy to see. step: t A B C D 0 0.0 100.0 0.0 0.0 0.0 1 0.0625 82.4 16.5 1.1 0.0 2 0.1350 67.0 28.7 4.1 0.2 3 0.1975 53.6 37.1 8.6 0.7 4 0.25 42.2 42.2 14.1 1.6 5 0.3125 32.5 44.3 20.1 3.1 6 0.3850 24.4 43.9 26.4 5.3 7 0.4475 17.8 41.5 32.3 8.4 8 0.5 12.5 37.5 37.5 12.5 <-------- MIDPOINT 9 0.5625 8.4 32.3 41.5 17.8 10 0.6350 5.3 26.4 43.9 24.4 11 0.6975 3.1 20.1 44.3 32.5 12 0.75 1.6 14.1 42.2 42.2 13 0.8125 0.7 8.6 37.1 53.6 14 0.8850 0.2 4.1 28.7 67.0 15 0.9475 0.0 1.1 16.5 82.4 16 1.0 0.0 0.0 0.0 100.0 Bezier's table is symmetrical about the middle row (when t = .5) so by reapplying the influences in a different order, we can halve its size and plot from both ends of the curve at once. So, our loop can look like this: for t= 0 to .5 + .5/s step s Also since the first and last elements are always 100% starting point and 100% ending point, we can drop them from the table as well. Thus, lxa = xs : lya = xy : lxb = xe : lyb =xe ' read lxa as Last X a for t = 0 to .5 step s ' ' apply table to input points in normal order to get px,py ' plot lxa, lya to px,py ' lxa, lya = px, py ' apply table to input points in reverse order to get px,py ' plot lxb, lyb then set equal to px, py ' next t ' plot lxa, lya to lxb, lyb 'close center of curve What Bezier computes and how to do it: Typically, the general calculation for px (and py, with appropriate changes) for a four-point curve is shown in computer graphics texts like this: x(t) = (t^3 * m11 + t^2 * m21 + t * m31 + m41) * x1 + (t^3 * m12 + t^2 * m22 + t * m32 + m42) * x2 + (t^3 * m13 + t^2 * m23 + t * m33 + m43) * x3 + (t^3 * m14 + t^2 * m24 + t * m34 + m44) * x4 The x(t) means that x is function of t, not an array element. The m's are parts of a 4 x 4 matrix, which is the heart of Bezier's curve: m11 m12 m13 m14 -1 3 -3 1 m21 m22 m23 m24 3 -6 3 0 = m31 m32 m33 m34 -3 3 0 0 m41 m42 m43 m44 1 0 0 0 The values of this matrix come from something called the Bernstein polynomials, a bit of trivia that serves only to make one wonder why Bezier curves aren't named after Bernstein instead. What this means for programmers is the the three 1's become addition and subtraction problems, and six 0's drop out: x(t) = (-t^3 + t^2 * 3 - t * 3 + 1) * x1 + (t^3 * 3 - t^2 * 6 + t * 3 ) * x2 + (-t^3 *3 + t^2 * 3) * x3 + t^3 * x4 As it stands, what we have here is a computational logjam of 22 mulitplies, 7 additions and 4 subtractions. Let's simplify by pulling out the squares and cubes (and return to our BASIC example): ts=t*t tc=t*ts px = (-tc + ts*3 - t*3 + 1) * xs + (tc*3 - ts*6 + t*3) * cx + (-tc*3 + ts*3) * dx + tc * xe Down to 13 multiplies. Now let's reorganize for fewer additions: ts=t*t tc=t*ts px = (1 + ts*3 - tc - t*3 ) * xs + (tc*3 - ts*6 + t*3) * cx + (ts*3 - tc*3) * dx + tc * xe Down to 5 additions. Lots of publish programs let it go here, but not us; let's shuffle our *3's and massage the signs to make the (t-ts)*3's and the (ts-tc)*3's common: ts=t*t tc=t*ts px = (1 - 3*(t-ts) - tc) * xs + (3*(t-ts)- 3* (ts-tc)) * cx + ' -ts*6 same as -ts*3 + -ts*3 3*(ts-tc) * dx + tc * xe Down to 10 multiplies, 3 additions but up to 7 subtractions. We've got two common phrases, so let's pull them out: ts=t*t tc=t*ts h=3*(t-tc) k=3*(ts-tc) px = (1- h - tc) * xs + (h - k ) * cx + k * dx + tc * xe Down to 8 multiplies, 3 additions and 5 subtractions. But, actually, we've a y-coordinate to calculate too, so let's pull the other influences, add the y equation, and drop it back into our half-loop routine: ' ' set values for end-points and control-points ' input "steps ", s s=1/s lxa=xs: lya=xy:lxb=xe:lyb=xe for t=s to .5 step s ts=t*t tc=t*ts h=3*(t-ts) k=3*(ts-tc) a=1-h-tc b=h-k px= a*xs + b*cx + k*dx + tc*xe py= a*ys + b*cy + k*dy + tc*ye ' ' use your BASIC's drawline routine, this is mine ' draw lxa,lya;px,py lxa=px:lya=py ' ' now apply reversed to bring other endpoint into play ' px= tc*xs + k*cs + b*dx + a*xe py= tc*ys + k*cs + b*dy + a*ye draw lxb,lyb;px,py lxb=px:lyb=py next draw lxa,lya;lxb,lyb This two-ends-to-the-middle along with assumed starting point (ie no 100%'s applied) eliminates steps/2+2 * (4 multiplies and 3 subtractions). And if that's quicker in BASIC then it quicker still in what-have-you. But faster still is an array of precalculated influences: input "steps ",s dim i(s,3) 'zero based dimension in my basic, tailor to suit s=.5/s 'remember we're counting only halfway c=0 for t=s to .5 step s ts=t*t tc=t*ts h=3*(t-ts) k=3*(ts-tc) a=1-h-tc b=h-k ' ' notice that ts and h are intermediate values ' i(c,0)=a:i(c,1)=b:i(c,2)=k:i(c,30=tc c=c+1 next s=.5/s 'resets s to index i array . . . . lxa = xs:lya=xy:lxb=xe:lyb=xe for t=0 to s px=i(c,0)*xs + i(c,1)*cx + i(c,2)*dx + i(c,3) * xe py=i(c,0)*ys + i(c,1)*cy + i(c,2)*dy + i(c,3) * ye draw lxa,lya;px,py lxa=px:lya=py px=i(c,3)*xs + i(c,2)*cx + i(c,1)*dx + i(c,0) * xe py=i(c,3)*ys + i(c,2)*cy + i(c,1)*dy + i(c,0) * ye draw lxb,lyb;px,py lxb=px:lyb=py next draw lxa,lya;lxb,lyb Of course, hardcoding the table would be even quicker. Looking under the hood Back to our table, where Column A is equal to 1-3*(t-t^2)-t3 {sic, probably t^3}, Column B equals 3*((t-t^2)-(t^2-t^3)), C is 3*((t^2-t^3) and D is simply t^3. Graphing these and their constituent parts should be fun. The vertical axis represents the influence percentage and the horizontal will represent t. We'll scale our unit square by 100 so we can plot more than one point: x=200:y=200 ' we'll put origin here box x,y,x+100,y-100 ' my screen counts down on y axis for t=0 to 1 step .01 g=100*t px=x*t:py=y-t draw px,py,px,py ' no dot routine in my BASIC next Understanding Columns C and D are key because Columns A and B are just C and D reversed. Taking A, for instance, you can view it as figuring out D from the wrong end of the loop. Similarly, the equation used by Column B figures out Column C from from the wrong end, too. First of all, we have t itself, which when graphed against itself is a straight line. What the graph shows is that t and its counterpart can be used to produce a slow program to draw a straight line between the endpoints: s=.01 for t=0 to 1 step s r=1-t px=xs*t+xe*r:py=ys*t+ye*r:draw px,py;px,py next An intermediate value, one that isn't directly applied to the Bezier points, is the square of t. The real interest we have in t^2 is its relation to t, which has the curious property that when t is between 0 and 1, t^2 does not exceed it. We'll graph in two ways. The first is merely t by t and t by t^2. So far, so clear. But let's rotate the difference between them and graph that on the horizontal axis. Remarkably, t-t^2 goes a long way towards explaining why the table can be halved. This graph also shows the 3*(t-t2) values, which will come in handy shortly. The cube of t, however, is our Column D. Setting its graph along that of column A clearly shows how A is the mirror of D. What both do is to quickly release the influence that respective points apply to the curve, leaving lots of room (in terms of percentage) for the control-points influence as shown in the third graph that sums Column A and D. Just how this reverse t^3 is calculated becomes clear when you notice that this "room" is just 3*(t-t^2). So, now the a=1-h-tc code has a face, though just why 3*(t-t^2) fits beats me. Personally, I've filed it under math-marvels..... Finally, we come to figuring out how to share the control-points's influence. Just dividing h in half and applying the result won't work as advertised: both control points peak at the same moment. In effect, one gets a single strongly weighted and invisible control-point halfway between the two controls. What is used is the three times the difference between the square and cube of t, which gives a parabola with a hump. (The mysterious factor of 3 returns. In "Computer Graphics Principles and Practice" (1990 Addison-Wesley), the principals Foley, vanDam, Feiner and Hughes have left the explanation to practice; they say, "see exercise 11.12" Humph! And that book set me back real money.) Again, an inexpensive subtraction get the other control point's influence, h-k. Altogether, the four influences summed make a pretty picture, reminescent of a set of Bezier curves. In fact, it might be entertaining to bootstrap your own influence table using Bezier curves. Fame beckons.... More control points Continuity locks Abandoning floating point FORTH programmers know in their hearts that there is way around all of these floating point calculations. What they know is that a percentage is just that, per 100. So, given n%, do this: multiply by n then divide by 100. But, you say, we've significance all the way to 1E-38. But, we reply, your display device does adn 1E-4, 0.0001 is enough room even for high-end image typesetters. But, you say, you're adding divides to the routine. But, we reply, we're adding visible divides and getting rid of invisible divides inside the system's floating point routines. But, you say, applying the influence percentage is one thing but calculating squares and cube is another thing: surely you'll have intermediate values that will overflow integer math. But, we reply, we're a 32bit cpu and we can count to more than 4 billion. But intermediate values do approach t^4: displaymax * t* 3 / n^3, where 0