Offset Bézier Curves

Perfect Solution

Short answer it’s impossible to create a perfect offset curve.

The curve at a fixed offset from a given Bézier curve, often called an offset curve (lying “parallel” to the original curve, like the offset between rails in a railroad track), cannot be exactly formed by a Bézier curve (except in some trivial cases). However, there are heuristic methods that usually give an adequate approximation for practical purposes.

-Wikipedia

Imperfect Solution

So here is a heuristic method. Convert the Curve to a poly line spline. Then merge/clip the expanded lines.

  1. Subdivide the Curve into Line Segments
  2. Offset Line Segments
  3. Merge/Clip Intersections

Step #1: Subdivide the Curve into Line Segments

To convert the curve to line segments we use De Casteljau’s algorithm.

public function subDivide( time:Number ):Vector.<CubicBezierCurve>
{
	//Outside Guide Lines
	var outerA:StraightLine = new StraightLine( pointA, controlPointA );
	var outerBridge:StraightLine = new StraightLine( controlPointA, controlPointB );
	var outerB:StraightLine = new StraightLine( controlPointB, pointB );

	//Inner Guide Lines
	var innerA:StraightLine = new StraightLine( outerA.lerp( time ), outerBridge.lerp( time ));
	var innerB:StraightLine = new StraightLine( outerBridge.lerp( time ), outerB.lerp( time ));

	//Point at time
	var newPoint:Point = new StraightLine( innerA.lerp( time ), innerB.lerp( time )).lerp( time );

	//Return Vector
	var newCurves:Vector.<CubicBezierCurve> = new Vector.<CubicBezierCurve>();

	//Left Curve
	var leftCurve:CubicBezierCurve = new CubicBezierCurve();
	leftCurve.pointA = pointA;
	leftCurve.controlPointA = outerA.lerp( time );
	leftCurve.controlPointB = innerA.lerp( time );
	leftCurve.pointB = newPoint;
	newCurves.push( leftCurve );

	//Right Curve
	var rightCurve:CubicBezierCurve = new CubicBezierCurve();
	rightCurve.pointA = newPoint;
	rightCurve.controlPointA = innerB.lerp( time );
	rightCurve.controlPointB = outerB.lerp( time );
	rightCurve.pointB = pointB;
	newCurves.push( rightCurve );

	//Return Vector containing new curves.
	return newCurves;
}

When your flattening a curve some curves need more subdivision than others. You can check the flatness level to determine if the curve needs to be sub divided again and again. This will help optimize your algorithm for offsetting, by breaking the curve into as few of lines as visually required.

Here is a cool method to find flatness of a line.

public function get flatness():Number
{
	var ux:Number = Math.pow( 3 * controlPointA.x - 2 * pointA.x - pointB.x, 2 );
	var uy:Number = Math.pow( 3 * controlPointA.y - 2 * pointA.y - pointB.y, 2 );
	var vx:Number = Math.pow( 3 * controlPointB.x - 2 * pointB.x - pointA.x, 2 );
	var vy:Number = Math.pow( 3 * controlPointB.y - 2 * pointB.y - pointA.y, 2 );

	if( ux < vx )
		ux = vx;

	if( uy < vy )
		uy = vy;

	return ux + uy;
}

This is converted from the great article about curve flattening.
Piecewise_Linear_Approzimation

So now we use these function to subdivide the curve. Here are sample results. This is when using a tolerance of <= 0.15

Original Curve

Subdivided Line Segments (16 lines)

Original Curve

Subdivided Line Segments (26 lines)

Step #2 Offset Line Segments

Next we create parallel lines for each of the lines in our line segment spline.

Offsetting lines is easy and mathematically supported 😉 Here is a sample function.

public function createParrallelLine( difference:Number ):StraightLine {
	var perp_x:Number = -rise
	var perp_y:Number = run;
	var len:Number = Math.sqrt(( perp_x * perp_x ) + ( perp_y * perp_y ));

	perp_x = ( perp_x / len ) * difference;
	perp_y = ( perp_y / len ) * difference;

	var parrallelLine:StraightLine = new StraightLine( new Point( pointA.x - perp_x, pointA.y - perp_y ), new Point( pointB.x - perp_x, pointB.y - perp_y ));

	return parrallelLine;
}

Basically it creates use perpendicular slopes and linear interpolation to create perfectly positioned parallel line. It will also always stay on the correct edge of the curve, as long as the direction of all the lines are the same. Clockwise or Counter-Clockwise.

Offset of 1px

Step #3: Merge/Clip

The next step we connect the expanded curve lines, and we determine if the best course of action is to create a new line between them, or if we should remove/cut a existing line.

Check for intersections if your lines intersect, then clip. else create new line between, or if your fancy, you can use another curve, and use the intersection point as the control point.

Examples

I highlighted the intersections with blue. You can see how they mesh nicely.

Final Results

Here is some final results with a 2px offset curve. Original is red, offset is blue.

Related Documents

Advertisements

20 comments

  1. While a good write-up, I’m missing a last section where the polygon representing the offset shape is converted back into a minimal set of cubic Bezier curves.

    Storing a flattened curve as a series of lines becomes increasingly intractable, illustrated by the following example: if we wish to create an outline for ‘O’, this requires (at least) 4 cubic Bezier curves, which we can efficiently store using 3 instructions (‘start at’, ‘curve to’ and ‘curve to and close’) instructions. These use 24 numerical arguments (2 for the start x/y, three times 6 for three successive cubic curves, and 4 for the last curve because the start coordinate is the last argument of the curve-to preceding it, and the end coordinate is the entire shape’s first coordinate) for a total of 27 values to store. Flattened, with 8 lines per curve segment (as per your example), this still requires three instructions (‘start at’, ‘line to’ and ‘close’) with 65 numerical arguments (2, 62, and none respectively) for a total of 67 values to store for the same shape.

    This difference only gets bigger for curves that can only be flattened without visual loss of precision using more segments, which (sadly) covers the majority of Bezier curves.

  2. @Pomax We convert the curve to straight lines. And never convert them back to curves.

    It’s true that it will take more data to store the same shape. But it’s the only way possible as far as I’m aware of.

  3. Then perhaps this will be nice information: for curves without inflections, we can observe that any scaled version of that curve is a perfect offset.

    To determine whether a curve has inflection points, we first rotate the curve so that the start/end coordinates line up, then determine whether f'(x) or f'(y) have any zero points between start and end (this indicates the curve changing direction in either x or y direction). If this is not the case, there are no inflection points and we are good to go. If there are inflection points, we can reduce the inflecting curve to a set of uninflected curves by chopping up the curve between inflection points. Doing so leaves us with curves that again can simply be scaled to obtain an offset curve.

    This gives us at most four subcurves per complex curve (∝ giving three inflection points, every other curvature two or fewer), and as such any 8 value (to store) cubic Bezier can be represented “lossless” with at most 26 values, but typically only 20 or 14. Already this is less than the number of segments that were needed to approximate the more complex curve in your example.

    In order to determine exactly how to chop up the original curve, we can use “de Casteljau”s algorithm, which is an iterative algorithm that returns all the coordinates needed when splitting up any order bezier curve (http://processingjs.nihongoresources.com/decasteljau/).

  4. Apologies, this holds for curves with a single inflection point (there is no such thing as a bezier curve without inflection points!)

    Also, as an extra note, we need to make sure of two things:

    1) we need to scale over the correct origin (which is determined by the direction of the curve at the start and end coordinates. Wherever the lines that are perpendicular to the curve at start/end intersect is our origin), and
    2) we will need to ‘clip’ or extend the resulting offset curves, because their t-interval [0,1] will be off with respect to the original curve

    (and we will definitely need to perform clipping if we want to colour the region between the original curve and the offset =)

  5. Actually, no, that’s not right, we’re still not there if we do that, apologies – I’m currently working on the offset problem, and got pretty close with this approach, but it still fails for certain curves.

  6. Hi Sean, could you please share more of your code? Ideally in for of util class with a free licence? I have to admit I don’t know how to reuse the snippets you’ve posted here. I know I am asking a lot but karma will pay you back 🙂

    1. Hey Griii2,

      I actually am unable to. This code was developed for a closed source application. The snippets here are Actionscript (Flash). Which part in particular are you confused about. I can’t give source, but I can give some insight.

  7. Hi Sean, I understand, thanks anyway. As of your code: What are the CubicBezierCurve and StraightLine classes? How do they translate to Graphics.curveTo()? Also all 3 of your functions deal with variables that do not enter the function as a parameter, I am confused (what is pointA, controlPointA, raise, run etc?)

    @Pomax thanks, I’ve stumbled upon that article, I know it’s admired, but I have to admit I am unable to covert the math into a code. I’ve even tried to migrate the Processing code into AS3 but I’ve failed, it’s quite mess.

    Does anyone know of a clean written library – in any OO language – that deals with bezier curve offsetting? I’d try to migrate it to AS3 and if I succeed I’ll share it with public. Surprisingly even after hours of googling I didn’t find anything useful.

  8. @Pomax: Wow I’ve just realized you are that Pomax, author of the article! I didn’t mean to say your code is mess, just that it contains much more than I need + it’s combined with the drawing and interaction code. But it’s actually well written, I am going to give it a second try.

    1. haha, no worries. It does have a lot of code! I’ve been trying to update the article with more snippet-style sections specifically for each operation, but I haven’t actually put curve flattening back in, which is the basis for Sean’s approach… perhaps I shouldn’t have recommended taking a look until after I added it back in!

      1. I have a some application in which i want offset the curves. Actually I have a closed paths and I want to convert it to single open path.
        @Sean your article is brief and really gives a good idea about working with beziers.
        @Pomex I also looked at your code and it is huge. I am trying to use that offset function but I could not understand one thing in that function. What is a ‘map’ that takes 5 arguments. I would appreciate your help.

  9. Thank you so much for this. It was really helpful.

    I implemented the flatting splitting thing and I find that while I can see it working (more curvy curves get split more) what I find is that it really doesn’t do a good job of not splitting. If I point all the control points on a nearly perfect line I get still get splits unless I crank the tolerance up to like 100. I tried using tolerance = 16*tol^2 like I mentioned in the paper you linked to but even that doesn’t seem to do well.

    The original paper says

    > Notice that since we are only interested in rejecting non-flat curves, it isn’t a problem if we mistakenly continue the subdivision process for a curve which is already flat enough.

    That’s probably true for postscript but it’s not true for real time graphics where ideally we’d like the a minimal number of points.

    Have you seen any other algorithms that do a better job of handling the straight line case vs just the curvy case?

    1. Let me add if I apply the flatness function to scaled points it comes out with different values of flatness and yet it seems like ideally you’d want the same value for flatness regardless of scale? Example (10,20), (20,30), (30, 40), (40, 51) returns 4 but (1, 2), (2, 3), (3, 4), (4, 5.1) returns 0.04. How is the second flatter than the first? The seem like they’re the same line

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s