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.
- Subdivide the Curve into Line Segments
- Offset Line Segments
- 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