Approximating Cubic Bezier Curves in Flash MX  By Timothée Groleau  

Introduction This *article* is intended for Flash developer and to anyone interested in bezier curves. Although I try to have a mathematical approach, it is certainly not as rigorous as it should be and most of what I use here is find from trial and errors. Mathematicians, please don't be offended. I present in this paper four approximation approaches, a BSpline approximation (Thanks to Jon Bradley's work and to Martin Wood), a generic midPoint approximation based on the Casteljau method (Thanks to Robert Penner for getting me on track), a fixed midPoint approximation (Thanks to Helen Triolo) and a tangent approximation. This is my first paper. So I am not much experienced in structuring those stuff. I know I'll send a link to this page to many of my friends who may not be very familiar with Flash or bezier curves altogether. For this reason, I'll start simple to move to more complicated stuff as we go along. Bear with me and hopefully, it will keep you interested untill the end.
Acknowledgment I would like to thank Martin Wood for posting a dynamic BSpline animation sample on the Flashcoder list and Jon Bradley who is the original author of the BSpline code that Martin used. This animation is the one that got me interested in cubic bezier approximation. I would also like to thank Helen Triolo for sharing with me her midPoint approximation technique, which, so far, I feel is the most effective approximation algorithm for Flash.
What are Bezier Curves ? Quick Description Bezier curves are named after a French enginneer named Pierre Bezier, who used them to design the Body of a Renault Car in the 1970's. To put it very simply a bezier curve is a curve which is exactly determined by a set of control Points. Each point of the curve is calculated from a parametric mathematical function which uses the coordinates of the control points as parameters. Applications Bezier curve changed the way graphics were thought of and introduced the concept of vector graphics as opposed to raster images. A raster image is described in term of pixels. Each pixel is coded with a color, depending of various algorithm available (jpg, gif, png, bmp, etc.). The two major problems of raster images is that they are generally big in term of file size and they are not scallable, meaning that if you zoom into the image, you will just see the square pixels getting bigger and bigger. Bezier curves were the adopted solution to describe an image in term of its mathematical representation. The vector graphic file will contain the coordinates of control points to describe a serie of curves. The viewer application (renderer) will then draw the graphic. If the user wants to zoom in, the renderer know it is only a matter of increasing the space between the control points and it can redraw a perfectly smooth curve again. Vector graphic are therefore perfectly scallable. Also, unless cases of very complexe vector graphics, it is generally more size effective to store control points coordinates rather than pixel informations. Nowadays, bezier curves are the standard for the typesetting industry (ever notice that in MS word, you can change the size of your font at will and it never pixelises?). Many tools produce vector graphics, Adobe Illustrator and Macromedia Freehand to name just 2. Of course, bezier curves are not fit to describe real word photography. A Bit of Math Given N+1 control Points Pk with k=0 to N, The bezier parametric curve is given by B(u) as follow: Bezier curves are parametric curves, it means the formula above is applied independently to the x and y coordinate of the points for a 2D curve. The following shows a hybrid between a Math formula and a ActionScript dot syntax to make the formula easier to grab (hopefully it does): There are a lot of very interesting property for bezier curves. Below are the fews that are relevant to us in this article:
The Cubic Bezier Curve As you have noticed above, the formula for the bezier curves is in fact a polynomial formula of degree N (one less than the number of control points). To describe a curve with a lot of control points, it means having high degree and high factoriels as well. It can therefore be quite expensive in term of processing power to draw such a curve. Most vector drawing applications therefore adopted an approach of 4 control points per curves. The polynomial degree is then 3 and thus the name "cubic bezier" curves. Below are snapshots from various applicationpopular applications
Wanna play with a cubic bezier curve? Click here. More Math So, back to our formulas, given 4 control points (P0, P1, P2, P3), we can derive the mathematical formula of the cubic bezier as follow: From the MoshPlant website, we can use a nice optimization in term of number of operations: Let the formula be: Then the parameters can be calculated as:
Flash MX In the latest version of Flash called Flash MX a new drawing API (Application Programming interface) is available for developpers so that they can draw vector graphics from script. Let aside the color functionality, two main functions are available from this drawing API, lineTo and curveTo. given the current location, lineTo draws a straight segment to another point. curveTo as you might have guessed will draw a bezier curve from the current location to the next anchor. As I started to play with the API, I realized that curveTo takes only one control point parameter, which means the curves contains 2 anchors and 1 handle only. This type of 3 control points bezier curve is called quadratic bezier curve. While it is clearly a great achivement, there are numerous things that quadratic bezier curves cannot achieve in comparison to cubic bezier curves, for instance a quadratic curve cannot create a loop while cubic can. There is another great example of what the quadratic bezier cannot do right inside the Flash documentation from Macromedia. In the documentation of curveTo, there is a piece of code to approximate a circle based on 4 quadratic curves, I used that copied and run the movie, the result is below on the left (does that look like a circle to you?). In the middle is a circle as you can draw it by hand from the Flash IDE, and on the right is a circle approximated with 4 cubic bezier curves.
Well, I guess you got the picture. Wanna play with a quadratic bezier curve? Then click here. Don't get me wrong, it is very possible to approximate a circle with quadratic bezier curves. But 4 is just not enough. In fact each cubic curve in the sample on the right is approximated with 4 quadratic bezier curves. The circle on the right is then an approximation with 16 quadratic curves. So while it is possible, imagine deriving those 16 quadratic curves and their control point by hand, it would be a real pain. Clearly, Flash lacks a cubic bezier curve drawing fonction.
Approximating Cubic Curves from Quadratics Before we go any further, I would like to bring up a property of the quadratic curve. From the very first section of this article, we mentionned that "At u=0 the curve is tangent to the segment [P0, P1] and at u=1, the curve is tangent to the segment [PN, PN1]". For quadratic curves, there are only 3 control points P0, P1 and P2. Therefore the quadratic bezier is tangent in P0 to the line (P0, P1) and is tangent in P2 to the line (P1, P2). Thus, the handle point for a quadratic bezier curve is the intersection of its tangents at u=0 and u=1. This is very important, wanna play with the quadratic curve again to make sure you got it straight ? Click here =) . OK, with that in mind, so how do we go about approximating a cubic bezier curves from quadratic? Well, that's when things start to become interesting in this paper. I will be presenting 4 techniques here each with their pros and cons which I will detail. At the very bottom, I have a .as Flash file with the functions ready to use. Along the way there will be some interractive demo where you can play with the various approximations and compare them to a real cubic curves. What I call real cubic curves in the demos are in fact approximations using the tangent technique with 20 quadratic curves (see below). They are so close to the true cubic Beziers that I will name them as "real" for the purpose of these demos.
BSpline approach This technique doesn't really approximate a cubic bezier but it is a smart approach to draw a continuous curve with 4 control points (2 anchors and 2 handles), just like with a cubic bezier curve. The idea in this case is that we want to approximate the cubic curve with 2 quadratic curves only. We therefore need to find a point where the two quadratic curves will meet with first order continuity. An obvious choice for such a point is the middle of the segment [P1, P2] from the {P0, P1, P2, P3} control points of the cubic bezier. This choice is interesting because we will use the line (P1, P2) as the tangent to the curve. The curve must also be tangent to the line (P0, P1) in P0 and to the line (P2, P3) in P3. Therefore, the handle points for the two quadratic curves will be the intersection of the lines (P0, P1) and (P1, P2) for the first quadratic curve and the intersection of the lines (P1, P2) and (P2, P3) for the second. Very obviously, the points we are talking about are P1 and P2. This is very good because it means we don't need to perform further calculation to derive any other control points. Let's go through the process step by step. Click here. So how is this approximation good? Well, the main thing about it is that it is very cheap in term of processing power. Indeed we don't calculate any point on the cubic curve through a polynomial equation, we don't have to derive any new control points as they are already available to us, the only thing we need to do is to calculate the middle of a segment, which is straightforward. Now, the bad things. The most obvious is that the approximation, is not even close to a cubic bezier curve. It clearly cannot be use for exact rendering. Also, it differs fondamentally from bezier curves in that, with bezier curves, changing the location of any of the control points change the look of the whole curve. With the BSpline approach, playing with the anchor points modify only half of the curves (can you see why?). As usual, no talk beats a little playing. Wanna try the BSpline curve? click here. (Note: the true cubic bezier is drawn in red.)
Tangent approach One way to approximate a curve is to try to bring into the approximated curve as much information about the real curve as possible. With a curve, what information are we talking about? Well, points on the curve of course, which we can calculate from the formula above. We can therefore extract exact points on the cubic bezier at regular intervals for u (and we can control the interval) and we can approximate the cubic bezier with a serie of quadratic curves which pass through those points. Furthermore, we know that the curve must be continuous, two adjacent quadratic curves in the approximation must therefore have the same tangents at their common point. Since that point is on the cubic curve and since we know the formula for the cubic bezier, we can calculate the exact tangent to the bezier curve. So what do we have so far, we got a bunch of points at exact location on the true cubic bezier plus their respective exact tangent to the cubic curve. AND, what did we mentionned earlier? The control points for the quadratic curves are the intersection of the tangents. Wow, wonderful. It seems very straightforward. we can now derive the control points for the successive quadratic curves by calculating the intersections of these tangents. Let's have a look at a step by step graphic demo. It looks like we have a damn good method here, we can approximate a cubic bezier by retaining a lot of exact information about the cubic curve (points location AND tangents) and it is easy to specify the number of quadratic curves we want to use to increase the quality of the approximation as needed. However, we are assuming that the cubic curve can be splitted in quadratic curves for each segment and unfortunately, this assumption is wrong. This can lead to problem as illustrated below:
What the hell was that????? Well, simply one of the segment we were trying to approximate with a quadratic curve is not fit for such an approximation. Specifically the tangents at two adjacent points are parallel or almost parallel. Of course if the two tangents are parallel, there is no intersection and we can therefore not derive a control point. In the sample above, the lines are not parallel but their direction are very close. For this reason, the intersection point is very far from the cubic bezier curve and it pulls very strongly the quadratic curve, producing that weird effect. Above, what is even worse, is that the intersection of the tangents is not even on the right side of the curve, so that's why the curve goes backward. Given an arrangement of four control points for a cubic bezier curve and a given interval which produces this unwanted effect, we can simply change the interval and the problem will likely disappear. So how can we detect when the curve is going nuts? That's actually a tough piece. I won't detail the process I went through to find a fix for it but here is what I chose to do: I chose (arbitrarily) that a control point derived from the intersection of the tangents to the cubic curve at two points on the curve is considered too far from the cubic curve if its distance to any of the two points is longer that the distance between the two points. In the library available below, I have a function that uses the tangent techniques. It takes as a parameters the number of quadratic curves that you want to use to approximate the curve (the bigger the more processing expensive but the better the quality). For each one of the potential quadratic, I check whether the handle point's location derived from the tangents is OK, if it is, I go ahead and I draw the curve, if not, I slice that specific quadratic curve (not the other pieces) recursively into more quadratics untill all control points are fine. I set a maximum of 10 recursion levels. If that level is reached, the two points are obviously very close together and the tangents are almost identical. For that reason, I approximate that last small segment with a line and there you go, no more trouble! So how is this approximation good? Well, the good thing about this approximation is that we retain a lot of the original information about the original curve. The approximation is therefore very close to the real curve. Furthermore, it is easy to change the number of quadratic segments that one wants to use to approximate the cubic curve. There is therefore a direct control over the quality. Note that 4 gives a good approximation, 8 gives an almost perfect approximation and above that, you cannot see the difference. Now, the bad things. This technique is absolutely exhausting for the poor CPU. We need to calculate the points on the cubic curve plus the tangents at those points, determine the intersection of lines, and finally do extra checking to avoid two tangents being parallel (and this extra checking can lead to more points , tangents and intersections to calculate). So this approach might not be usable to render complex graphic unless you got some supercomputer at home. Alright demo time!! In this demo, the cubic bezier is drawn in red and the approximation is drawn in black above it. You can change on the fly the number of quadratic you want to use to make up the approximation. You can see how close the two curves are (note that if you cannot see any red at all, it means the black approximation is pretty damn good and covers the red one). You will also see the real number of quadratic used, that is if there are detection of parallel tangents and if the function needs to use more curves than what you specify. Remember, the "real" cubic bezier in red is an approximation with 20 quadratics. Click here to play. Remarks:
Generic MidPoint approach The day after I published the first version of this article, Robert Penner posted a approximation method on the FlashCoder list. This motivated me to do extra research on this new method and here it is described. I do not include this method into my bezier library as Robert Penner did a fantastic job in coding it already so I will simply give a link to his library here and there will be another one at the bottom of this article. The method was discovered in 1959 by Casteljau who showed that a cubic bezier curve can be split in exactly two cubic bezier curves halves with new control points. Specifically, given a cubic bezier curve, determined by four control points {P0, P1, P2, P3} as shown below: the cubic curve can be splitted in two exact cubic halves determined by {P0, P01, PA, PC} and {PC, PB, P23, P3}. I rewrote the proof here if you are interested (6 pages, 58 KB pdf file). OK, that was the first step, another important thing to note is that for some agencement of the cubic control points, you can have a rather good approximation of the cubic curve with a unic quadratic as shown in the graphics below (the cubic curve is shown in red and the quadratic in black): PQ in both cases is the intersection of lines formed by (P0,P1) and (P2,P3). In the graphics above, I inserted the middle point of the cubic curve and the middle point of the quadratic curve. A quality factor for a given approximation could be based on the distance between the two middles. It can be proven (although I haven't redone the proofmyself, but I will when I find time) that if we split a cubic curve into two, the distance between the middle points reduces in comparison to the distance in the original cubic. It is a convergent process. With that in mind, here is how we can use the generic midpoint approach:
So how is this approximation good? This technique is great because it also keeps a large number of real information from the real cubic curve and it is very stable. Also, having control of the quality is again a very strong advantage. Now, the bad things. Although this mehod is (a lot) cheaper than the tangent approach, it is still quite heavy as one round of recursion is generally not enough and clearly recursion is not cheap, I would say in most cases, two rounds would not even be enough. In Flash which is a rather slow interpreted environment, generating graphics with large number of path with this approach may also be quite difficult.
Fixed MidPoint approach In Flash, processing is a very important constraint. So one way of cutting down the processing is to fix a reasonnable quality for all curves and not give any quality control to the user. This may be frustrating but the advantage of doing this is that we can optimized the calculations involved for a specific quality. This is exactly the approach that Helen Triolo choose to create a SVG renderer in Flash. The technique I am showing now is very similar to the generic midPoint approach above fixed at two levels of recursion on each side. which means the cubic curve is approximated with 4 quadratics. How does it go? we derive control points based on middle of middles from the four original bezier control points. Since it is very similar to the generic midPoint approach so I suggest we jump straight into the graphic demo. Showing midpoints makes it easy to understand, but in coding, it is easy to find better ways to calculate those points. Basic geometry can show you where segments are and what proportion of which segment we can use. Look at the code in the library to get the idea. So how is this approximation good? This technique is great for three reasons, it gives a reasonnably good approximation of the cubic bezier, it is cheap in term of processing and it is stable (no parallel tangent crap). Also a last point to note, is that by choosing the control point where we do for the first and last quadratic segment, we ensure that two cubic curves which had first order continuity will retain that continuity after being approximated with quadratic curves. Now, the bad things. "bad" is to be put in quote here. The only thing is that the approximation is not exact and we specifically fixed the quality of the curve which may not suit everybody's need. I have to add a paragraph here. from the four techniques presented here, the midPoint technique surpasses clearly the three first in term of usability. It may not be as exact as the tangent technique or the generic midPoint but it is a lot cheaper in term of processing and it is stable for any arrangement of cubic control points. Alright, wanna play with it? Click here. Note that the less red you see the closest the black approximation is to the red bezier curve.
Conclusion In this paper, we have seen four approximation techniques
Here is the library file: bezier_lib.as. It extends the Math object to add a bunch of functions we need (line and segment functions), it creates a Bezier global object with methods specific to bezier calculations (you can add new methods to this object if you want to) and it extends the MovieClip prototype with three new methods:
Each of these methods take 4 control point objects as parameters. drawCubicBezier also takes an optional parameter to specify the number of quadratics to use (default is 4). These three methods are hidden and protected with ASSetPropFlags so it won't mess up your for..in loops in movie clips. There is no documentation but the code is (hopefully) well commented. I haven't implemented the generic midPoint approach as Robert Penner already did it and he posted his own library on the Flash coder list. You can access it from this link. Also, I must stress here than althgough the fixed midPoint approaches is the cheapest of all, even with it, it can still be very difficult to render a large vector graphic in one Frame in Flash. So people interested in rendering very large vector graphics may need to split the drawing process over several frames to ensure Flash to not hang in the middle.
This is the end, I hope that this article was informative and hopefully it was clear. Do feel free to send me any comment or questions. It would be very much appreciated. Also, feel free to use and modify the library file as much as you want.
References a few websites which deal with bezier curves. There are much more but those are the ones I feel were most relevant to me or simply got me started. http://www.moshplant.com/director/bezier/ http://astronomy.swin.edu.au/~pbourke/curves/bezier/ http://www.tinaja.com/cubic01.asp http://actionscripttoolbox.com/svgnotes.php


