A primer on Bézier curves - by Mike "Pomax" Kamermans

Last updated: 5 December, 2011

Before we begin I'd like to say that all the graphics on the page, except for the Wolfram Alpha images, are interactive graphics, without requiring any special browser plugins. If your browser supports javascript, and the canvas element (sorry IE8 users, you'll have to upgrade to IE9, which supports <canvas> - Get it here,) it will be able to let you use this page, thanks to the most excellent Processing.js project. You will also see rather nicely typeset mathematics, thanks to the equally excellent MathJax library.

So, with that out of the way, let's look at the topic at hand: Bézier curves.

In order to draw things in 2D, we rely on two kinds of drawing primitives: the straight line, and the curved line. While we can draw loads of things freehand, computers are a bit handicapped in that drawing straight lines is dead-easy for them, but they can't draw curves unless there is a mathematical function that describes how it should be drawn.

Over the years the dominant way to draw curves is to use something called the "Bézier" curve, which is a particularly interesting curve because it can be linked up to other Bézier curves while making the combination still look like a single curve. You might be familiar with these curves if you've ever drawn Photoshop "paths" or worked with vector drawing programs like Flash, Illustrator or InkScape. But what if you need to program them yourself? What are the pitfalls? How do you determine bounding boxes, intersections, extrusion, all the things you might want when you do things with curves? That's what this page is for. Prepare to be mathed.

The basics

Bézier curves are a form of "parametric" curve, which means that unlike a normal function, all dimensions have their own function. Normally, function maps some value, say x to some other value, say y, such as in the following two dimensional function:

\[ f(x) = \sin(x) \]

The notation f(x) is the standard way to show that it's a function (f) and its output changes based on one variable (in this case, x). One or more dimensions are variable, in this case x, and the output is a single number, which in the case of a function with one input we usually call y. Change x and y changes too.

Parametric functions are different. Take the following two functions:

\[\begin{matrix} f(a) = \sin(a) \\ f(b) = \cos(b) \end{matrix}\]

There's nothing really remarkable about these functions, until we say what f(a) and f(b) mean: when dealing with parametric curves, a collection of functions does this:

\[ \left \{ \begin{matrix} f_a(t) = \sin(t) \\ f_b(t) = \cos(t) \end{matrix} \right. \]

Multiple functions, but only one variable. If we change the value for t, we change the outcome of both f_a(t) and f_b(t). Now, If we replace the labels f_a(t) and f_b(t) with what we usually mean with them for parametric curves, you might see what's going on better:

\[ \left \{ \begin{matrix} x = \sin(t) \\ y = \cos(t) \end{matrix} \right. \]

Parametric curves don't define y in terms of x, like normal functions, but they link the values for each dimension to a controlling variable. If we vary t, we get two values, which we can use as (x,y) coordinates in a graph. The above set of functions, for instance, generates points on a circle. We can range t from negative to positive infinity, and the resulting (x,y) coordinates will always lie on a circle with radius 1 around the origin (0,0).

Bézier curves are one of many classes of parametric functions, and are characterised by using one specific type of function for all its dimensions. Unlike the above example, where the x and y values use different kind of functions, Bézier curves use the same kind of function for each dimension: the binomial polynomial.

You may remember polynomials from high school, where they're those sums that look like:

\[ f(x) = a \cdot x^3 + b \cdot x^2 + c \cdot x + d \]

If they have a highest order term x³ they're called "cubic" polynomials, if it's x² it's a "square" polynomial, if it's just x it's a line, and if there aren't even any terms with x it's not a polynomial!

Bézier curves are polynomials of t, with "binomial" coefficients. Let's look at what that actually looks like:

\[ \begin{align*} linear &= 1 \cdot t + 1 \cdot (1-t) \\ square &= 1 \cdot t^2 + 2 \cdot (t \cdot (1-t)) + 1 \cdot (1-t)^2 \\ cubic &= 1 \cdot t^3 + 3 \cdot (t^2 \cdot (1-t)) + 3 \cdot (t \cdot (1-t)^2) + 1 \cdot (1-t)^3 \\ hypercubic &= 1 \cdot t^4 + 4 \cdot (t^3 \cdot (1-t)) + 6 \cdot (t^2 \cdot (1-t)^2) + 4 \cdot (t \cdot (1-t)^3) + 1 \cdot (1-t)^4 \\ n^{th}\ order &= \sum_{i=0}^{n}{\binom{n}{i} \cdot t^{n-i} \cdot (1-t)^{i}} = \sum_{i=0}^{n}{\binom{n}{i} \cdot t^i \cdot (1-t)^{n-i}} \end{align*} \]

The last line is a generalised function that just shows you how to get the basic function used in Bézier curves for any order (Σ indicating a series of sums, using the variable that below the Σ, starting at ...= and ending at the value listed on top of the Σ). You might known the binomial coefficient as "Pascal's triangle", and is actually really simple to calculate.

So, now we know what the base function(s) look(s) like, time to add in the magic that makes Bézier curves so special: control points. Let's look at the parametric function for x in a third order, or cubic, Bézier curve:

\[ x_t = {\bf x_1} \cdot t^3 + {\bf x_2} \cdot 3 \cdot (t^2 \cdot (1-t)) + {\bf x_3} \cdot 3 \cdot (t \cdot (1-t)^2) + {\bf x_4} \cdot (1-t)^3 \]

What this function says is: "I am an interpolation of four values, x₁, x₂, x₃ and x₄. If t is near 1, the result is closest to x₁. If t is ⅔, the result is closest to x₂. If it is ⅓, the result is closest to x₃ and if it is near 0 the result is closest to x₄." -- In fact, when t is 1 the outcome will be exactly x₁, and when t is 0, the outcome will be exactly x₄, but at t values ⅔ and ⅓ the result of this function will be closest to, but not actually at, x₂ and x₃. In fact, the mixing ratios across the interval for t from 0 to 1 can be visualised as the following interactive graphic, which lets you pick a value for t and will show the percentages of x₁ through x₄ that you get at that point:

Bézier curves are not the only interpolation functions commonly used for graphics. Other "splines" (functions that interpolate a curvature based on three or more points) are the Catmull-Rom spline and the cumbersomely named Non-uniform rational B-spline (typically called NURBS to make things less cumbersome). We won't be looking at this in this article, but if you want to do computer graphics, you may want to research those more in addition to reading up on Bézier curves.

So with that covered, let's start looking at Bézier curves as used for graphics purposes.

The most common type of Bézier curves in graphics are 2^nd order and 3^rd order Bézier curves, also known as "quadratic" and "cubic" curves, and they look like this:

\[ \left \{ \begin{matrix} x(t) = (1-t)^2 \cdot x_1 + 2 \cdot (1-t) \cdot t \cdot x_2 + t^2 \cdot x_3 \\ y(t) = (1-t)^2 \cdot y_1 + 2 \cdot (1-t) \cdot t \cdot y_2 + t^2 \cdot y_3 \end{matrix} \right. \]

and:

\[ \left \{ \begin{matrix} x(t) = (1-t)^3 \cdot x_1 + 3 \cdot (1-t)^2 \cdot t \cdot x_2 + 3 \cdot (1-t) \cdot t^2 \cdot x_3 + t^3 \cdot x_4 \\ y(t) = (1-t)^3 \cdot y_1 + 3 \cdot (1-t)^2 \cdot t \cdot y_2 + 3 \cdot (1-t) \cdot t^2 \cdot y_3 + t^3 \cdot y_4 \end{matrix} \right. \]

The (x,y) coordinates these functions generate are restricted, in that t is allowed to only run from 0 (inclusive) to 1 (inclusive), and the kind of curves they can generate have particular properties, which I can describe in text but which will be much more immediately visible if we actually draw these curves. So, let's whip out the virtual pens and start drawing (and as noted earlier, remember that all the drawings on this page are interactive).

quadratic Bézier curve (source)

cubic Bézier curve (source)

Things you might notice:

1. The curves "depart" from the start and "arrive" at the end in the direction of the "control points" — point 2 for the quadratic curve, and points 2 and 3, respectively, for the cubic curve.
2. The quadratic curve can only "bend" once, whereas the cubic curve can "bend" (at most) twice.
3. Particularly visible for the cubic curve, the curve seems to have fewer points at the start and end than it does in places where there's a strong bend.

All three points are important properties of Bézier curves:

1. The parametric derivatives at the start (t=0) and end (t=1) points are equal to the lines from those points to their control point(s).
2. The Bézier order indicates the maximum number of curvature changes.
3. Fixed value incrementing of t does not translate to fixed distance on the curve.

So now that we know a little bit about these curves, let's explore the various ways in which we can exploit their mathematical functions, to do things to these curves. Specifically, we'll be looking at how to program things like curve bounding boxes, finding intersections between curves, drawing offset curves (also known as extrusions), and other such useful things.

Finding the extremities of the curves

One of the first things people run into when they start using Bézier curves in their own programs is "I know how to draw the curve, but how do I determine the bounding box?". It's actually reasonably straight forward to do so, but it requires having some knowledge on exploiting math to get the values we need. For bounding boxes, we aren't actually interested in the curve itself, but only in its "extremities": the minimum and maximum values the curve has for its x- and y-axis values. If you remember your calculus (provided you ever took calculus, otherwise it's going to be hard to remember) we can determine function extremities using the first derivative of that function, but this poses a problem, since our function is parametric: every axis has its own function...

The solution: compute the derivative for each axis separately, and then fit them back together in the same way we treat the original. Let's look at how a parametric Bézier curve "splits up" into two normal functions, one for the x-axis and one for the y-axis. Note the the left-most figure is again an interactive curve, without labeled axes (you get coordinates in the graph instead). The center and right-most figures are the component fuctions for computing the x-axis value, given a value for t (between 0 and 1 inclusive), and the y-axis value, respectively.

If you move points in a curve sideways, you should only see the middle graph change; likely, moving points vertically should only show a change in the right graph.

splitting up a quadratic Bézier curve into its component functions (source)

splitting up a cubic Bézier curve into its component functions (source)

So with that little "help" (in quotes, because it's unlikely you will immediately understand why it helps) let's look at finding those curve extremities. In calculus we learn that in order to find curve extremities, we have to solve the equation  f '(...) = 0. What do these derivative functions look like for Bézier curves? While it might be a good exercise in "how's your math?", there really isn't much point to doing so, as Wolfram Alpha can do it better, quicker, and is pretty much the google for higher math, perfect for when you can't remember how to do it yourself, or you when you just want to save some time (I use it a lot).

First, the quadratic curve. Derivatives are one order lower than their parent functions, so the solution is a linear function, nice and easy (as long as A-2B+C ≠ 0):

\[ t = \frac{A-B}{A-2B+C} \]

Then, the cubic curve. The solution is a quadratic function, which makes things slightly more tricky, but not a lot. As long as D ≠ A-3B+3C, the formula is:

\[ t = \pm \frac{\sqrt{-AC+AD+B^2-BC-BD+C^2} - A+2B-C}{-A+3B-3C+D} \]

Which, when D = A-3B+3C, and as long as A-2B+C ≠ 0, simplifies to:

\[ t = \frac{A-B}{2(A-2B+C))} \]

So let's implement some extremity detection. In both cases we simply look for where the derivatives equal zero (with respect to t), and then use those values for t to see where the points are on x/y, rather than just x or just y. The result should be immediately indicative of how we're going to program a bounding box algorithm:

first derivative root finding for quadratic Bézier curves (source)

first derivative root finding for cubic Bézier curves (source)

Computing the bounding box for a Bézier curve

As we've just seen, finding the extremities of the curve gets us lots of interesting points, specifically points that we can use if we want to compute the bounding box for Bézier curves. In fact, it's all the points we need to compute not just the regular bounding box, but also a "tight fit" bounding box. So let's do so right now:

Computing the bounding box for a Bézier curve

1. Find all t value(s) for the roots ("zero-points") of the curve's derivatives for each dimension.
2. Discard any t value that's lower than 0 or higher than 1, because Bézier curves only use [0,1].
3. Determine the lowest and highest value when plugging the values t=0, t=1 and each of the found roots into the original function for a dimension: these two values are the lower and upper bound for our regular bounding box.

Applying this approach to our previous root finding, we get the following bounding boxes:

finding the quadratic bounding box (source)

finding the cubic bounding box (source)

So far so good, but we're not done yet. There's also the "tight fit" bounding box, which we can find with a ridiculously simple procedure, now that we know how to find the regular bounding box:

1. rotate and move any curve so that the first point is on (0,0) and the last point is on (...,0)
2. compute the bounding box for this rotated/translated curve
3. move and rotate this bounding box with the opposite values that we used in step 1.

The only "problem" in this procedure is rotating the curve, but trigonometry helps us out here. First, we simply move all points by (-x1,-y1), so that the curve starts at (0,0). Then, we can compute the angle from the x-axis to the line from (0,0) to the last point using the inverse tangent function, angle = tan^-1(dx/dy) and angle = tan^-1(dy/dx), where dx is the distance from start to end on the x-axis, which — because we moved everything so the first point is on (0,0) — is simply the x coordinate of the last point, and dy is simply the y-coordinate of the last point.

Rotating any coordinate over a specific angle with respect to (0,0) is a really simple trick, too. Noting that the angle computed is usually written as φ, computing the coordinates as rotated over this angle is:

\[ \left \{ \begin{matrix} x' = x \cdot \cos(φ) - y \cdot \sin(φ)\\ y' = x \cdot \sin(φ) + y \cdot \cos(φ) \end{matrix} \right. \]

Note that in order to compute the new x coordinate, we need both the original x and y coordinate values, and the same goes for the new y coordinate. This operation is usually performed using what is known as a "Rotation Matrix", but you don't need to write your code to do matrix math in order to perform the required math.

This trick has as secondary benefit that it drastically simplifies the math: because x₁ and y₁, as well as y₃ (for quadratic curves) or y₄ (for cubic curves) are zero, our parametric functions have become remarkably simpler:

\[ \left \{ \begin{array}{l} x(t) = 2 \cdot (1-t) \cdot t \cdot x_2 + t^2 \cdot x_3 \\ y(t) = 2 \cdot (1-t) \cdot t \cdot y_2 \end{array} \right. \]

for the quadratic curve, and:

\[ \left \{ \begin{array}{l} x(t) = 3 \cdot (1-t)^2 \cdot t \cdot x_2 + 3 \cdot (1-t) \cdot t^2 \cdot x_3 + t^3 \cdot x_4 \\ y(t) = 3 \cdot (1-t)^2 \cdot t \cdot y_2 + 3 \cdot (1-t) \cdot t^2 \cdot y_3 \end{array} \right. \]

for the cubic curve. Clearly, determining the extremities for these much simpler functions is a lot easier too. So, if we put all this together and follow the above recipe, we get a nicely tight-fitting bounding box indeed:

finding tight-fit quadratic bounds (source)

finding tight-fit cubic bounds (source)

This is, strictly speaking, not necessarily the tighest possible bounding box. It is possible to compute the optimal bounding box by determining which spanning lines we need to effect a minimal box area, but because of the parametric nature of Bézier curves this is actually a rather costly operation, and the gain in bounding precision is often not worth it. If there is high demand for it, I'll add a section on how to precisely compute the best fit bounding box, but the math is fairly grueling =)

Calculating intersections

Let's look at some more things we will want to do with Bézier curves. Almost immediately after figuring out how to get bounding boxes to work, people tend to run into the problem that even though the minimal bounding box (based on rotation) is tight, it's not sufficient to perform collision dectection ("does curve C touch, or pass through, curve or line L?"). In order to do this, we need to know whether or not there's an intersection on the actual curve.

We'll do this in steps, because it's a bit of a journey to get to curve/curve intersection checking. First, let's start simple by implementing a line-line intersection checker. While we can solve this the traditional calculus way (determine the functions for both lines, then compute the intersection by equating them and solving for two unknowns), linear algebra actually offers a nicer solution:

if we have two line segments with two coordinates each, segments A-B and C-D, we can find the intersection of the lines these segments are an intervals on by using the procedure outlined on this top coder page. Of course, we need to make sure that the intersection isn't just on the lines our line segments are on, but also on our line segments themselves, so after we find the intersection, we need to verify it lies without the bounds of our original line segments. The following interactive graphic will show this as a red point for an intersection on the lines, and a green point for an intersection of the line segments.

finding the intersection between two lines (source)

Now, let's move up to line-curve intersection. There are two ways in which you can do this, depending on how fast you need it done. The first approach involves "flatting the curve", which means turning the Bézier curve into a series of straight lines, and then testing for line-line intersection for each line generated. With what we've seen so far, this is trivially easy: just run through the curve at some fixed interval k for t, creating line sections from (t_xk , t_yk) to (t_xk+1 , t_yk+1) and then perform an intersection check for each line.

While you might think we can stop once we find an intersection, remember that we're performing intersection checking for curves, and a line can cross a single curve more than once! Depending on whether we're checking this for quadratic or cubic Bézier curves, we can stop early only after finding 2 or 3 intersections, respectively.

The second option is to do things analytically. This is a hard problem, but we can simply it using the earlier "move and rotate" trick. First, we find out how we need to move and rotate our line so that its start coordinate is at (0,0) and its end coordinate somewhere on the x-axis. We then move and rotate our curve by the same values. The problem of finding the intersection between the line and the curve in two dimensions has now become the problem of finding where f_y(t) = 0 for our moved and rotated curve. Back to Wolfram Alpha we go. The solution for the quadratic curve is simple:

The solution for the cubic curve, however, is a massive pain in the backside, and hardly quickly computed at all!

And we're not getting off easy either: there are three possible intersections, so we need to compute all three, not just one of these! However, that cubic formula seems manageable, and we could probably use it if there was some way to reliably chop up a cubic Bézier into a number of smaller quadratic Bézier curves. Long story short: we can, but not without loss of precision. Curve flattening is — as far as I am aware in January 2011 — the best solution.

So, first off, curve flattening. What kind of resolution do you need to get an acceptably flattened curve? There is no hard number that we can rely on, as it has to do with the precision you're going for, so let's simply implement curve flattening with arbitrary precision, and leave it up to the viewer to figure out what an acceptable resolution is, by letting them type "+" or "-" on their keyboard (after having clicked on our application, or in this case, graphic) to increment or decrement the number of segments in the flattened curve:

Flattening a quadratic curve (source)

Flattening a cubic curve (source)

Once we have decided on a flattening parameter, we can start performing our intersection evaluation. The procedure is as simple as it is obvious:

1. Flatten curve
2. for each segment in the flattened curve, see if it intersects our line.

For illustrative purposes, I've used 16 steps for the quadratic curve, and 32 for the cubic curve. Again, you can use "+" and "-" to increment and decrement those numbers:

Finding intersections between a line and a flattened quadratic curve (source)

Finding intersections between a line and a flattened cubic curve (source)

For curve-curve intersection, we perform flattening twice - once for each curve - and then perform the classic double for loop, where we check every line segment in flattened curve C1 against every line segment in flattened curve C2:

Finding intersections between two flattened quadratic curves (source)

Finding intersections between two flattened cubic curves (source)

Having implemented all this, we're now left with only one minor issue: we computed x/y coordinates, but in order to find points on a curve, what we really want are t values. How do we go back from one to the other? By flattening the curve, we have lost some of the precision required to find the exact t values associated with a particular x/y coordinate.

You might think that we could approximate a t value by simply solving the component functions for the desired x and y values, but if you recall the functions for solving the component functions for 0, this would be highly impractical. We're doing programming, and that means we can be clever with data structures. Instead of just flattening a curve, we can tell each segment in the flattened curve what its start and end t values were. This lets us approximate the t value on the original curve through interpolation. And the best part is that the more segments we use, the better our approximated flat curve is to the original curve, and thus the more accurate our estimated t values will be:

Finding intersections between a line and a flattened quadratic curve (source)

Finding intersections between a line and a flattened cubic curve (source)

The same logic of course holds for the curve-curve intersection case, and by extension the self-intersection case (which is a curve-curve intersection check with the same curve used twice), but this is a trivial modification now that we know how to do it. Let's move on.

Splitting curves - de Casteljau's algorithm

Once we know how to find interesting points on a Bézier curve, we can start manipulating the curve for further processing, such as clipping (removing part of a curve based on some criterium) or splitting (turning one curve into two or more curves that are point-for-point identical). Both of these operations require us being able to form a curve that runs from t>0 to t<1.

And that's already one solution: to form subcurves, we don't do any complicated things, we just restrict the interval for our original curve. Intersections and bounding boxes are now computed based on this new t interval, and all is well, problem solved!

Technically, however, these will not be Bézier curves, because Bézier curves are defined as having a t interval [0,1]. So, alternatively, we can generate new curves that use this t interval [0,1], but have different x_1...4 and y_1...4 parameters. The first question now is: "can this be done?", and the answer to that is a resounding "yes!", thanks to what is known as "de Casteljau's algorithm".

de Casteljau's algorithm is easiest understood as a geometric algorithm:

1. For any n^th order Bézier curve, this algorithm starts with the point set {p₀ = first point, p₁ = first control point, p₂ = second control point, ... , p_n = last point}, which contains exactly n+1 elements.
2. It then replaces this set with an interpolated set {p'₀ = point between p₀ and p₁ at distance t, p'₁ = point between p₁ and p₂ at distance t, ... , p'_n-1 = point between p_n-1 and p_n at distance t}. This set will be 1 element shorter.
3. Step 2 is repeated until there is only one point left, and that point will lie on the original curve, at the same t value.

The beauty of this algorithm is that it also "generates" all six or eight values that are required to split up a quadratic or cubic curve into two new, equivalent, curves:

• The start point for the first of the two subcurves is the start point of the original curve.
• The first control point for this curve is the point p₁ from the first iteration.
• (The second control point for this curve is the point p₁ from the second-last iteration)
• The end point for the first of the two subcurves is the point at t.

• The start point for the second of the two subcurves is also the point at t.
• The first control point for this curve is the point p₂ from the second-last iteration.
• (The second control point for this curve is the point p_n-1 from the first iteration)
• The end point for this curve is the end point of the original curve.

So let's see that in action for both the quadratic and cubic curves. Note that the following sketches are both interactive and animated: as long as you turn on animation, you can drag points around and see the result in real-time.

Splitting up a quadratic curve using de Casteljau's algorithm (source)

Splitting up a cubic curve using de Casteljau's algorithm (source)

This operation is crucial in particular to Bézier clipping, where certain parts of a curve have to be discarded, while leaving the remainder a valid Bézier curve, which is the cornerstone for Boolean shape operations, such as joining up two shapes into a single shape, or cutting one shape out of another. The ability to precisely divide a curve is essential.

Invariably people end up asking the question "what if I need to divide my curve into more than one subcurve? what about three? or four? or more?". There are two universal solutions to the problem inherent to this question - getting a subcurve that starts and ends at arbitrary t values. Both solutions share the same idea:

1. Divide the curve into two subcurves at t₁
2. Discard the first subcurve, and divide the second subcurve at t₃ = (t₂-t₁) * 1/(1-t₁). This represents the value of t₂ projected onto the — smaller than the original — subcurve.
3. Of this second division, discard the second subcurve. The first is the interval curve you were looking for.

Solution one consists of doing this for every interval required. Solution two consists of further repeatedly further subdividing the second subcurve, scaling the t values with every division. Solution one costs more than solution two, but yields more precise subcurves. You get to pick which of the two to use in your own code.

Calculating offset curves (extruding curves)

Perhaps you are like me, and you've been writing various small programs that use Bézier curves in some way or another, and at some point you make the step to implementing path extrusion. But you don't want to do it pixel based, but parametric shape based. You find that extruding lines is relatively easy, and tracing outlines is coming along nicely (although junction caps and fillets are a bit of a hassle), and then decide to do things properly and add Bézier curves to the mix. Now you have a problem.

Unlike lines, you can't extrude a Bézier curve simply by taking a copy and moving it around, because of the curvatures; rather than a uniform thickness you get an extrusion that looks too thin in places, if you're lucky, but more likely will self-intersect. The trick, then, is to scale the curve, rather than simply copying it. But how do you scale a Bézier curve?

Of course, you might be thinking in terms of graphics programs, in which case scaling means "mask it using its bounding box, and then move one side of the bounding box for a one dimensions scale, relative to the other side, or move two sides at once, for a uniform scale relative to the opposite corner point". The latter comes close, but not close enough. As it turns out, we can't scale an arbitrary Bézier curve. That sounds a bit problematic and it is: except for a low number of special cases, scaling a Bézier curve simply leads to self intersection or uneven extrusions. The solution lies in the formulation of the problem: except for a low number of special cases, scaling a Bézier curve doesnt work. So what are these special cases?

Any Bézier curve with at most one directional change in its curvature falls in the exception category. Can we perhaps split up a Bézier curve with more than one directional change into a series of Bézier curves with only one? As it turns out, yes, we can. At this point we have a wide array of curve operations available, and we can split up a curve anywhere we like - we just need to express the criterium for curve splitting in terms of specific curve properties.

We've already seen the property for curvature changes, namely the curve's derivative, and we've also seen how to compute it in such a way that the orientation of the curve is irrelevant, by moving/rotating it. If we combine this with a way to scale curves correctly, we will be well on our way to implementing Bézier offset curves.

While for bounding boxes the first derivative was enough, for cubic Bézier curves this is not enough. Remember that the derivative for a function is one order lower than that function's order — cubic Bézier curves are of order three, which means they can change direction twice, but that's per component function. The full curve can change direction three times. If we take the derivative for the component functions, we get quadratic functions. These can only change direction once, but again that's per component function. If we put them together to form the full curve, the curve can still change direction twice. To catch all the points we need for a cubic Bézier curve, we also need the second derivative, which is (like the quadratic Bézier curve's first derivative) a linear function, per component, which can't change direction, with the full curve described by it only able to change direction once. Finally, we're good to go.

curvature change finding for quadratic Bézier curves (source)

curvature change finding for cubic Bézier curves (source)

So now that we know where to chop up our curves, let's look at how we should scale each of these curves so that we end up with a series of curves that, taken together, look like an offset curve. In order for this to be the case, there are a two things we can immediately note:

1. For point → control point, the direction of the curve at the point is the angle to its control point.
2. For control point → point, the direction of the curve at the point is the angle from its control point.
3. On-curve coordinates have to be moved perpendicular ("at a right angle") to the direction of the curve.
4. The angles from points to their control points must be preserved, otherwise the curve's direction changes.

We can visualise this in another graphic. This graphic uses the quadratic Bézier curve for illustrative purposes, as its form yields far more "usable" curves, and saves us the trouble from having to constantly verify that the curve you set up in the graphic is actually illegal. How to read this graphic:

• The curve is visualised as in every other graphic
• There are two blue lines that indicate the lines perpendicular to the curve at t=0 and t=1
• The intersection of these two lines, our scaling origin, is marked in red
• Both start and end point have been scaled in the same direction by 25 pixels, marked as small blue circles
• Lines parallel to the curve's direction have been drawn for both offset curves, in pink

quadratic Bézier curve scaling (source)

Note that the curve conforms to the "special case" curve properties as long as the lines perpendicular to the start and end of the curve do not intersect the curve, and the angle the two lines is no greater than 90°. You can see that things go wrong with our extrusion, and consequently our offset curve, if we violate those criteria. When splitting curves based on first (for quadratic) or first and second (cubic) derivatives, we must ensure that both these criteria are met.

A word of warning before we continue: while it seems obvious that where the pink lines meet is where we place the offset for the control point, the reason for this is because the control points in quadratic curves are linked to two on-curve points, so they must fulfill two criteria:

1. Point p₂, scaled from the origin, has to lie on the line starting at p'₁, in the direction of the curve at p₁, and
2. Point p₂, scaled from the origin, has to lie on the line starting at p'₃, in the direction of the curve at p₃

This means:

1. Point p₂, scaled from the red point, has to lie on the pink line starting at p'₁, and
2. Point p₂, scaled from the red point, has to lie on the pink line starting at p'₃.

Using quadratic curve this ends up being the point where the two lines meet. For the cubic Bézier curve, however, things are different. There, control points are only linked to a single on-curve point, and they need to be scaled to lie on the line parallel to the curve's direction at the on-curve point and going through the on-curve point's offset.

With that said, let's finish up the illustrations on curve extrusion/offset curves with the full cubic curve example, this time necessarily including curve-splitting, so that the extrusion of single cubic curve actually ends up being a series of connected, smaller, special case curves.

You can change the offset distance in the following graphic by using "+" and "-" to increment or decrement the distance. If a curve looks like it's wrong, try changing the offset distance to understand why it's wrong (it'll actually be the correct extrusion, based on the algorithm we just looked at, but it's not the desired offset curve).

cubic Bézier curve scaling (source)

You may notice that for certain curves, this generates odd extrusions. Problem cases present themselves when:

1. A subcurve is so close to being a line that rounding errors may lead to inaccurate extrusion. The resulting offset curve will contain "craters".
2. A subcurve is so small that scaling the control points heavily distorts the curve (such as on curves that approach a ⋏ shape). The resulting offset curve will be useless.
3. Rounding may lead to offsets being off by 1 pixel vertically and/or horizontally
4. The original curve self-intersects. The less spherical the intersection's loop, the more like the resulting offset will exhibit one or more of the previous oddities.
5. A subcurve is extruded with a distance that is too large, meaning that one or both offsets are scaled past the scaling origin. The resulting offset curve will have sections where the distance between the curve and the offset is less than what it should be, and may even self-intersect.

How do we deal with this?

1. Coordinate analysis prior to extrusion, and using a line rather than a scaled curve.
2. Coordinate analysis prior to extrusion, and using a line rather than a scaled curve.
3. Continuity validation after extrusion, to make sure all the coordinates line up.
4. Curve analysis prior to extrusion. This won't let us solve anything, but it lets us flag potential problem curves.
5. The problematic subcurve can be divided further for higher precision (when the distance between divisions reaches 1 pixel, curve extrusion becomes offset stroking. A very expensive operation).

You may notice that under certain circumstances, the offset curve is (necessarily) self intersecting. While this may be the correct offset curve, it's not very pretty, and we'd rather cutt off the bits between the original curve and the offset curve. To do that, we must perform a self-intersection check on the offset curve, and then clip ("trim") the curve so that the undesired parts are removed. This is a topic for a next section

Calculating interpolated offset curves (extruding curves)

But before we look at that, let's look at what you might expect to be a simple extension on offsetting: offsetting with different distances at the start and end point. Doing this for straight lines is easy: set the start offset to one distance, set the end offset to the other distance, and connect the dots. For parametric curves, things are not so easy. While the end points are still offset with obvious values, we need to make sure that the points between start and end are the correct interpolation between the two offset distances.

To make the interpolation more obvious, let's look at what happens on a line. At the start of a line segment, the offset is some value O_s, and at the end the offset is O_e. If, for convenience, we imagine this line is exactly 100 units of length long, and then look at what the interpolated offset looks like, we see the following:

• at t = 0 (start), the offset is 100% O_s and 0% O_e
• at t = 25, the offset is 75% O_s and 25% O_e
• at t = 50 (half way), the offset is 50% O_s and 50% O_e
• at t = 75, the offset is 25% O_s and 75% O_e
• at t = 100 (end), the offset is 0% O_s and 100% O_e

As we move along the "curve", the distance travelled along the curve dictates the interpolation ratio. This also holds for real parametric curves, but that's where things get a bit tricky, because it's not easy to say where you are on a curve: even though we can manipulate the t value freely, the curvature of a parametric Bézier curve is not uniform; The curve is defined over interval t=[0,1], but the curve at point 0.1 · t does not necessarily lie at 10% of the curve's length. This might be a problem, so let's look at what happens if we use t as our interpolation ratio. Rewriting the previous example, we get:

• at t = 0 (start), the offset will be (1-0) · O_s and 0 · O_e
• at t = 0.25, the offset will be (1-0.25) · O_s and 0.25 · O_e
• at t = 0.50 (half way), the offset will be (1-0.5) · O_s and 0.5 · O_e
• at t = 0.75, the offset will be (1-0.75) · O_s and 0.75 · O_e
• at t = 1 (end), the offset will be (1-1) · O_s and 1 · O_e

The following interactive graphs let you see where we need to come with interpolated coordinates in order to form interpolated offset curves. Note that because of the way we deal with curve segmenting, we may only need to interpolate at one or two points (you can use the '+' and '-' keys on your keyboard to make the distance between the two offsets bigger or smaller, respectively)

offsetting with different distances requires interpolation (source for line, quadratic, cubic)

The way to interpret the graphics are as follows: every curve has two offsets, and the first point on the offset nearest the curve must end up connected with the last point on the offset farthest away from the curve. For the line this means connecting two dots. For the parametric curves things are more complicated - In order to offset the curves, they are first converted into a series of "safe" segments, with specific start and end t values. Then, at each end point of each segment, we know the interpolation ratio between near and far offsets and we can figure out "through" which points we have to draw our interpolated offset curve.

For end points of a segment things are simple, because we have all the information we need, but to offset control points we first need to find out between which points we must interpolate, and at which ratio. Luckily we already implicitly know how to do this, because we can find the points between which to interpolate, and their t value, by performing a line/curve intersection check between the offset curves and the line(s) running through the offset's control points. This gives us the following results:

interpolated offsets with interpolation ratios based on t values (source for line, quadratic, cubic)

That looks pretty good, but can we do better? What if we, instead of relying on t values for interpolating, try to rely on distance along the curve? First, it means we have to first figure out how to calculate the distance on a curve for some coordinate, and this problem is known as determining the "arc length" of a curve(segment). If we have a parametric curve with f_x(t) and f_y(t), then the length of the curve, measured from start point to some point t = z, is computed using the following seemingly straight forward (if a bit overwhelming) formula:

\[ \int_{0}^{z}\sqrt{f_x'(t)^2+f_y'(t)^2} dt \]

or, more commonly written using leibnitz notation as:

\[ length = \int_{0}^{z}\sqrt{ \left (dx/dt \right )^2+\left (dy/dt \right )^2} dt \]

This formula says that the length of a parametric curve is in fact equal to the area underneath a function that looks a remarkable amount like pythagoras' rule for computing the diagonal of a straight angled triangle. This sounds pretty simple, right? Sadly, it's far from simple ... cutting straight to after the chase is over: for quadratic curves, this formula generates an unwieldy computation, and we're simply not going to implement things that way. For cubic Bézier curves, things get even more fun, because there is no "closed form" solution, meaning that due to the way calculus works, there is no generic formula that allows you to calculate the arc length. Let me just repeat this, because it's fairly crucial: for cubic and higher Bézier curves, there are values for the parameters such that this function cannot be solved.

Of course, there's more than one way to find a value, as long as you can find another description for what it is that you're looking for. Even though solving the function may be impossible, it is actually quite easy to find the value that it's supposed to yield, provided we're willing to only get "arbitrarily close" to the real value. Of course for graphics programming purposes, arbitrarily close and exactly the same value end up coinciding once you hit machine precision, and approximations become "more than good enough" well before we hit that limitation.

Let's look at two ways in which we can approximate the length of a Bézier curve. The first will be rather simple, and terribly inefficient, involving curve flattening. The second will be rather complex, but terribly efficient, involving integration over intervals using what is known as the "n-point Gauss quadrature" approach.

So let's first look at flatten. Our original flattening algorithm simply segmented a curve into X equal length line segments, and this was fine, but it's not optimal. Different curves have different parts that curve more or less, and ideally we only want to use as long a line segment as possible before we start a new one. Rather than splitting up curves equally, let's introduce some bias, by constructing a flattened curve based on how much of an error each line segment has with respect to the original curve.

• Compute x/y for t=0. Use as start coordinate.
• Determine subsequent x/y coordinates by running through t values. Determine what the error is between the line from {initial x/y coordinate} to {'current' x/y coordinate} and the curve that is described by f(t).
• Continue doing this for as long as the error is below some error threshold value ε. If the error exceeds ε, commit the line from the initial x/y coordinate to the last "still valid" x/y coordinate, and start a new line segment, beginning at the last coordinate of the committed segment.

Following this procedure, we get a different kind of flattened curve, with many segments where the curvature is very strong, and few segments where the curvature is faint. The following graphic lets you set a threshold value using your keyboard's '+' and '-' keys, which will determine how curves get flattened

error threshold based flattening of a quadratic Bézier curve (source)

error threshold based flattening of a cubic Bézier curve (source)

In order to get the length of a Bézier curve in far less time than is required to perform flattening, and with a much smaller error, calculus actually has a phenomenal number of "tricks", all of which involve taking an unsolvable formula, and approximating it in such a way that at least for the values of interest, the approximation yields a result that can be made arbitrarily close to the real value. While we cannot directly compute the length of a Bézier curve, we actually can quite cheaply compute an approximation of the length of a Bézier curve, with the additional guarantee that it will be such a good approximation that we can safely consider it the length of a curve.

The method we'll look at here is the Gauss quadrature. This approximation is a really neat trick, because for any n^th degree polynomial it finds approximated values for an integral really efficiently. Explaining this procedure in length is way beyond the scope of this page, so if you're interested in finding out why it works, I can recommend the University of South Florida video lecture on the procedure, linked in this very paragraph. The general solution we're looking for is the following:

\[ \int_{-1}^{1}\sqrt{ \left (dx/dt \right )^2+\left (dy/dt \right )^2} dt ≃ \left [ C_1 \cdot f\left(t_1\right) + ... + C_n \cdot f\left(t_n\right) \right ] = \sum_{i=1}^{n}{C_i \cdot f\left(t_i\right)} \]

In plain text: "we can express the length either as an integral function, which we know we cannot always solve, or as an infinite sum of rectangular strips, approximated by using some finite but high number of strips (with widths C₁ for the first strip, C₂ for the second, etc., and with heights f(t₁) for the first, f(t₂) for the second, etc.) and then simply add up the areas for all strips.

Since computing the area for a rectangle is just width times height, this second approach is computationally cheap, provided we can also cheaply come up with sensible values for those C₁, C₂, etc. A naive way is to simply create n strips all with the same width, but there is a far better way, using special values for C and f(t) depending on the value of n, which indicates how many strips we'll use.

One requirement for the approach we'll use is that the integral must run from -1 to 1. That's no good, because we're dealing with Bézier curves, and the length of a section of curve applies to values which run from 0 to "some value smaller than or equal to 1" (let's call that value z). Thankfully, we can quite easily transform any integral interval to any other integral interval, by shifting and scaling the inputs. Doing so, we get the following:

\[ \int_{0}^{z}\sqrt{ \left (dx/dt \right )^2+\left (dy/dt \right )^2} dt ≃ \frac{z}{2} \cdot \left [ C_1 \cdot f\left(\frac{z}{2} \cdot t_1 + \frac{z}{2}\right) + ... + C_n \cdot f\left(\frac{z}{2} \cdot t_n + \frac{z}{2}\right) \right ] = \frac{z}{2} \cdot \sum_{i=1}^{n}{C_i \cdot f\left(\frac{z}{2} \cdot t_i + \frac{z}{2}\right)} \]

That may look a bit more complicated, but the fraction involving z is a fixed number, so the summation, and the evaluation of the f(t) values are still pretty simple.

So, now we finally have enough to put everything together. The following two graphics show the approximated Bézier curve length using everything you just read, but does so in spectacular time, compared to the curve-flattening approach. Again, you can click on the graphic and use your keyboard's '+' and '-' keys, which will determine how good the approximation is, except this time higher is better, because rather than the threshold error, the number now represents how many strips we're using in our approximation. The more strips, the better the approximation. Note that the maximum number of strips is 24, since anything higher than that will only lead to higher precision in the 14th and further decimal, which don't even get shown in the graphic.

computing length using Gauss quadrature for quadratic curves (source)

computing length using Gauss quadrature for cubic curves (source)

So, now we have a fast way of determining the lengt of a Bézier curve. Let's put that to use. Rather that interpolating between two offset curves based on the t-ratio, let's actually use the "distance on the curve" measure instead, and see whether that looks any better.

interpolated offsets with interpolation ratios based on distance-on-curve (source for quadratic and cubic)

Does this look better than the t-ratio interpolation? To be honest, that's up to you. For most purposes, the overhead that is incurred by doing distance based interpolation might simply not be worth the gain in interpolation precision, but sometimes it is important to be precise. If you are writing a graphics application that does visualisation, using t values as your interpolation ratio is probably fine. If you're writing a graphics application for actual design, you probably won't be able to get away with t value interpolation, and you'll have to do distance-based interpolation.

Of course, these sketches are not optimised for speed, and so perform some of the operations in a rather inefficient manner. The interpolation can be sped up a great deal further, but how much further depends not just on your code efficiency, but also on what framework you'll rely on. Things like the iPad and Android phones have suddenly made vastly less powerful hardware very attractive again, so remember that you're not just implementing a generic graphics algorithm. It will be running on something, too.

Clipping

We already covered the idea of clipping, "removing unwanted parts", in previous sections - intersection finding can tell us where to split up curves, de Casteljau's algorithm lets us form subcurves for the sections that we want, and then we discard the original curve. However, previously we looked at achieving the first step through curve flattening. This is a potentially very costly way of doing things, because flatting takes time, and doing lots of intersection checks also takes time. There are in fact several ways to perform curve clipping, so in addition to the polygon clipping we've already looked at, let's look at some "pure" ways to clip a Bézier curve. For all of these, the difference is in determining where intersections are, after which the subdivision and discarding unwanted bits are exactly the same.

Subdivision Clipping

The first alternative to finding intersections using flatting is the divide and conquer approach, known as subdivision intersection finding. The concept is remarkably simple, and the pseudo-code for the subdivision algorithm should be pretty clear:

In essence this algorithm "ignores" the curves themselves, and simply checks whether the bounding boxes overlap. If they do, the curves are split, forming smaller bounding boxes, with curves whose bounding boxes no longer overlap being thrown away. At some point the split leads to bounding boxes that span at most 2x2 pixels, at which point line intersection can be performed to find the sub-pixel intersection point. Like before, we track t values when we split of curve segments, so that we have not just the x/y coordinates when we are done, but also the t values for splitting the original curves for clipping.

The following interactive graphic lets you run this algorithm. Simply arrange the curves in some interesting intersecting way, and then press "enter" on your keyboard to start the subdivision algorithm (severely slowed down).

Divide and conquer - the subdivision algorithm (source)

Fat Line Clipping

The second approach is the rather oddly named "Fat line" clipping. This approach relies much more on hardcore math, so buckle up. Like the subdivision algorithm the "fat line" approach is an iterative approach. However, unlike the subdivision, we won't be blindly halving curves and then checking whether or not we can discard any bits yet. Rather, this approach lets us explicitly find curve sections to keep, so that we can converge on the intersections much faster. The downside to this approach is that we'll have some difficulties when two curves intersect more than once, but we'll get to that later. First off: how does it work?

Say we have two curves C₁ and C₂. Instead of subdividing at t=0.5, is there some "informed" way to determine which t value(s) to use at every step, so that we're guaranteed that we've discarded those parts that are not involved in intersections, and are left with parts that are? As it turns out, we can. And it requires some pretty smart stuff.

The basic idea is that we create a "fat line" that bounds the extent of C₁. We've already seen this earlier, when we computed the tight bounding box for Bézier curves. There are tree parts to a fat line: the baseline, which is a straight line from the first point to the last point, and the two bounding box lines parallel to the baseline. These will be a distance d₁ and d₂ away from the baseline. The clever bit is the following:

If we express C₁'s baseline as a generalised formula for a line, L: a · x + b · y + c = 0, then in addition to being able to compute the distance between points on curve C₂ and line L, we can in fact compute the entire distance function that says, for any t value in C₂, what its distance to L is. I'll give you a moment to read that again, because it's not just crucial, it's also remarkable.

So what are a, b and c? These are in fact easily computed. If we pick any random value for t (and we don't even need to be in the interval [0,1] for this check), we can compute X(t) and Y(t) for C₁ in the same way we compute any other x/y values. To find out the values for a and c, we use what we know about the formula for a line. This function has the form y = u · x + v, with the value u being the line's slope, and we can compute the slope quite easily:

\[ u = \frac{Point_{last_y} - Point_{first_y}}{Point_{last_x} - Point_{first_x}} \]

So, your standard Δy/Δx. That leaves finding out what v is, which is just a matter of filling in everything we already know:

\[ Y(t) = u \cdot X(t) + v 　→　 Y(t) - u · X(t) = v \]

So, that just leaves rewriting the formula to the generalised form a · X(t) + b · Y(t) + c = 0:

\[ Y(t) - u · X(t) = v 　→　 Y(t) - u · X(t) - v = 0　→　- u · X(t) + 1 · Y(t) - v = 0 \]

Which gives us:

\[\begin{array}{l} a = -u, 　 b = 1, 　 c = -v \end{array}\]

We're almost done, because there is one more requirement, and that's that a² + b² must be equal to 1. So:

\[\begin{array}{l} a' = \frac{-u}{\sqrt{u^2+1}}, 　 b' = \frac{1}{\sqrt{u^2+1}}, 　 c' = \frac{-v}{\sqrt{u^2+1}} \end{array}\]

Now we simply put everything together. When L (the line from start point to end point for C₁) is defined as a' · x + b' · y + c', and the Bézier curve C₂ has start, control, and end points P₀, ..., P_n, the distance function between C₁'s baseline and any point on C₂ is:

\[\begin{array}{l} D(t) = v_0 \cdot (t-1)^n + v_1 \cdot (t-1)^{n-1} \cdot t + ... + v_{n-1} \cdot (t-1) \cdot t^{n-1} + v_{n} \cdot t^n \end{array}\]

And this is just another Bézier curve, where all the v_... terms are computed in the same manner:

\[\begin{array}{l} v_0 = a' \cdot P_{0_x} + b' \cdot P_{0_y} + c' \\ v_1 = a' \cdot P_{1_x} + b' \cdot P_{1_y} + c' \\ ... \end{array}\]

If you never studied geometry, this may seem strange. Do some substitutions, and we suddenly have a distance function for every point on an n^th order Bézier curve to an arbitrary line... So, let's look at this graphically. The following graphic gives you two curves - one fixed, which represents our C₂, and one interactive, representing C₁. Changing the coordinates for C₁ will show you the fat line over which C₂ will be clipped, as well as the distance function that tells us how far each point on C₂ is from C₁'s baseline.

Parameter extraction for fat line clipping (source)

Notice that no matter what you do in this graphic, the distance function only changes when you change the start or end coordinate for C₁. This is because the baseline is dictated only by those two points. Also note that in the graphic for the distance function, the start, control and end points don't change t-coordinate, no matter what you do. This is because of the formula above: the distance function is actually (very conveniently!) a "plain" Bézier curve, with the start, control, and end points evenly spaced at 0, ⅓ · t, ⅔ · t and t.

The important bit to realise here is that we now have a distance function, and two limits (the lines parallel to C₁'s baseline) which means that with this distance function we can tell at which value of t the curve C₂ will be inside or outside the "fat line". In essence, we can now (almost) immediately tell which part of a curve we should keep, in order for us to keep only that part that's inside a bounding "box". This should speed things right up!

Of course, the downside is that we can't, because if you remember earlier in the article, finding the intersections between a line and a Bézier curve is lots of work. You might think that we're going to have to flatten the curve again, at which point "why bother with the clipping?" but the fact that we're going to iteratively get closer to the intersection means we don't need the exact points at which the curve "clips" the two lines. We just need to make sure we pick values that guarantee at least the correct interval.

We're going to use the seemingly trivial observation that every Bézier curve is fully contained by the polygon that connects all the start/control/end points, known as its "convex hull". Instead of computing the intersection of the Bézier distance curve with the lines L_d1 and L_d2, we're simply going to check where the various lines of the convex hull intersect with those two lines. This requires all of four line intersection checks.

Since the intention is to 'safely' clip C₂ so that we're left with at least that bit of C₂ that lies inside the fat line, we can guarantee we're not clipping off too much if we pick the minimum value that results from checking the intersections between the two lines of the curve's convex hull that join at P₀, and L_d1, as well as the maximum value that results from checking the intersections between the two lines of the curve's convex hull that join at P_n, and L_d2.

If we examine this graphically, using the previous example, this time the convex hull for the distance function's Bézier curve is shown, and the intersections of its edges with the lines L_d1 L_d2 are shown (as dots on the lines where the convex hull intersects them). The part of C₂ that this algorithm says we should keep, based on the resulting t values, is shown in black in the middle drawing.

Cubic fat line clipping (source)

The trick is to perform this clipping alternatingly: First C₂ is clipped to C₁, forming C'₂, then C₁ is clipped to this C'₂, forming C'₁, and so on, until the desired precision is is achieved. This method typically converges on the intersection coordinates much faster than the subdivision problem, but there's a catch: This method can only find one intersection.

That may sound like it's a deal-breaker, but there's a reasonaby effective way to get around that problem, by using a simple rule that says: "if a clipping didn't reduce the curve by at least 10%, 15%, 20%, ...%, then split up the curve, and then run this algorithm in parallel for each of the resulting curve segments".

Boolean shape operations

Of course, where there is clipping, there is clipping of shapes that involve Bézier curves, rather than just simple isolated curves. While I'm cleaning up the section on clipping you can see examples of this here; when the clipping section is all done, I shall be porting the code that uses back to this page, and explain how all this is done. Should you have any questions in the mean time, the comments are right below!

Change log

November 2nd 2011

• Changed the styling a bit
• Replaced comments section with an EasyPageComments section (which was actually derived from this page's comment system =)
• Updated the download with some code fixes.

October 22nd 2011

• Rewrote the start of the article to make it a bit more accessible.
• Wrapped two not necessarily usefully complex sections in note borders.
• Updated Processing.js to version 1.3.6.

June 17th 2011

• Finished the corrections of the fat line clipping implementation. It should now clip correctly.
• Added some js event faking so that MathJax's math conversion triggers "should sketches be loaded?" checks.

June 11th 2011

• Finished the backend rewrite, fixed all syntax errors in the source code and bundled it back up as download.

June 5th 2011

• Added a link for Legendre-Gauss quadrature weight/abscissa value sets for n=2 to n=64.

June 4th 2011

• Updated Processing.js to 1.2.1
• Rewrote all math as LaTeX, and added the MathJax library for nice styling.
• Rewrote the underlying source serving framework (will see additional rewrites).
• Fixed some of the sketch source, because it was technically broken in native Processing.
• Added a section on using Gauss quadrature to determine arc length (much, much faster than flattening).

March 31^st 2011

• Added the section on clipping, covering the subdivision and fat line algorithms.
• Added a boolean shape operation placeholder.

March 24^th 2011

• Switched the sketch loading to "lazy loading", so sketches don't load until they're scrolled into view.

March 18^th 2011

• Fixed cubic distance-interpolated offsetting to actually use distance interpolation.
• Added scale origin caching.
• Fixed a rounding error due to int casting in the line/curve intersection algorithm.

March 17^th 2011

• Fixed up the code for offset curves a bit.
• Fixed coordinate rounding taking place too soon.

March 7^th 2011

• Added a downloads section.

February 17^th 2011

• Updated the article with a section on interpolated offset curves.

January 24^th 2011

• The first version of this primer was put online, in an exercise to unify all the Bezier curve code I had written for various Processing.js sketches.

Downloads

There's quite a number of files used on this page, and it wouldn't very educational if you didn't get to examine them. As such, I've compiled each sketch into its own Processing sketch for you to run on your own computer, each in its own directory because otherwise Processing will complain. The files have been packed with 7 zip, which is ludricrously better at data compression than zip - the download is 38KB in 7z format, vs. 680KB for plain zip. Read those numbers again. Yes, it's that good.

• All sketch code as a individual Processing sketches (7z format)

Comments and questions

If you have any questions about anything on this page (including how the graphics work, etc.), or you just want to leave a comment, this is the place to do it.

Leave your own comment

Please fill in your name, email address and comment (I might contact you via email if your comment warrants personal contact, but it doesn't get put on the page). Also make sure to fill in the security question (the question already instructs you what to write, anyway)