June 17: Calculating SVG bézier curve intersections (without Snap!)
Humble thanks to Particle in Cell, a California-based tech consultancy, and this fantastic article on their blog. The code is now a bit out of date so I’ve taken the liberty of updating/adapting it. Their work has been incredibly helpful in my personal projects! This blog post wouldn’t have been possible without it!
Today I’m following up on a previous blog post about one of my favorite subjects: vector graphics — just about the easiest way to make your web app stand out in a crowd. A talented vector artist can please nearly any taste: minimalism to realism and nearly everything in between. And SVGs are light, fast and a natural fit for manipulation and animation.
To recap: we’re focusing again on <path>s (sequences of lines and curves), which form 90% of most vector graphics. I explained last time that paths have commands with parameters, expressed in either absolute (viewbox coordinates) or relative (distance from previous coordinate) terms. Today we’ll be covering one particular very important command: the C/c cubic bézier curve command.
Background: ahead of the curve
Remember in my last post on SVG paths I explained the <path> tag can replace every other shape tag? As it turns out, within <path> descriptors, the C and c commands can replace every other command except the initial M/m. (Like a toolkit with a Swiss army knife where one of the layers is a Go-Gadget.) You can see using my PathParser from last time that the two shapes below have the same absolute points and appear identical:
const sameShape = [
"M 25 25 L 75 25 L 75 75 L 25 75 Z",
"M 25 25 C 25 25 75 25 75 25 C 75 25 75 75 75 75 C 75 75 25 75 25 75 Z"
];PathParser.parse( sameShape[ 0 ] )
-> [ [ 25, 25 ], [ 75, 25 ], [ 75, 75 ], [ 25, 75 ], [] ]
PathParser.parse( sameShape[ 1 ] )
-> [ [ 25, 25 ], [ 75, 25 ], [ 75, 75 ], [ 25, 75 ], [] ]
C/c commands are called bézier (bezYAY) curves, created/formalized by and named for two French engineers, de Casteljau and Bézier, pioneers of computer-aided design (CAD). Bézier curves make lots of curve operations/calculations easier, so they’re very important. In particular, C/c commands are easier to transition (or tween), so they’re central to vector animation.
This article from Michigan Tech does a much better job than I ever could of explaining Bézier-de Casteljau curves, but in a nutshell, they’re defined by control points. Editing these control points has become a natural user feature in vector graphics editors like Illustrator and Inkscape — if you have one you can see for yourself how changing a curve’s control points changes its shape:
One quirk of bézier and other curves is that their borders don’t necessarily correspond directly to their points:
That’s a problem if you’re, say, working at Particle in Cell on one of their advanced simulation software products, rendering engineering plans as 3D objects with SVG. How will you calculate exactly where a line intersects with a curve to account for, say, perspective?
Solving the cube
Pop your dramamine now and make sure your will is filed - this one’s a real doozy, thanks to some truly painful high-school algebra. It’s older code that’s been simplified and adapted for this React demo which you can see here. When the mouse button is down, crosshairs appear, and points indicate where the mouseDown event’s x and y horizontals/verticals intersect with the curve on the screen.
The bulk of the action here is happening in utilities/bezierIntersections.js. Remember from high school algebra that a linear equation takes the form ax + b, and that a cubic equation takes the form a * Math.pow( x, 3 ) + b * Math.pow( x, 2 ) + c * x + d. We don’t know the roots (possible values for x) or the coefficients (a, b, c and d), but we can calculate them from the curve’s command. Let’s do that with a curveDefinition— [ zero, one, two, three, four, five, six, seven ], representing the path M ${ zero } ${ one } C ${ two } ${ three } ${ four } ${ five } ${ six } ${ seven }— and a line defined by its lineStart and lineEnd coordinates. Then let’s solve with the curve’s/line’s definitions to find their intersection algebraically:
const bezierCoefficients = ( p0, p1, p2, p3 ) => {
return [
-p0 + 3 * p1 + -3 * p2 + p3,
3 * p0 - 6 * p1 + 3 * p2,
-3 * p0 + 3 * p1,
p0
];
}const computeIntersections = ( curveDefinition, lineStart, lineEnd ) => { const A = lineEnd[ 1 ] - lineStart[ 1 ];
const B = lineStart[ 0 ] - lineEnd[ 0 ];
const C = lineStart[ 0 ] * ( lineStart[ 1 ] - lineEnd[ 1 ] ) + lineStart[ 1 ] * ( lineEnd[ 0 ] - lineStart[ 0 ] ); const xBezierCoefficients = bezierCoefficients( curveDefinition[ 0 ], curveDefinition[ 2 ], curveDefinition[ 4 ], curveDefinition[ 6 ] );
const yBezierCoefficients = bezierCoefficients( curveDefinition[ 1 ], curveDefinition[ 3 ], curveDefinition[ 5 ], curveDefinition[ 7 ] ); const P = [
A * xBezierCoefficients[ 0 ] + B * yBezierCoefficients[ 0 ],
A * xBezierCoefficients[ 1 ] + B * yBezierCoefficients[ 1 ],
A * xBezierCoefficients[ 2 ] + B * yBezierCoefficients[ 2 ],
A * xBezierCoefficients[ 3 ] + B * yBezierCoefficients[ 3 ] + C
]; return solveCubicRoots( P ).reduce( ( result, root ) => {
return [ ...result, [
xBezierCoefficients[ 0 ] * root * root * root + xBezierCoefficients[ 1 ] * root * root + xBezierCoefficients[ 2 ] * root + xBezierCoefficients[ 3 ],
yBezierCoefficients[ 0 ] * root * root * root + yBezierCoefficients[ 1 ] * root * root + yBezierCoefficients[ 2 ] * root + yBezierCoefficients[ 3 ]
] ];
}, [] );}
We calculate xBezierCoordinates and yBezierCoordinates, operate on them with our intersecting line’s points, then use a function solveCubicRoots to solve for our intersections:
const solveCubicRoots = P => { let [ a, b, c, d ] = P; var A = b / a,
B = c / a,
C = d / a,
Q = ( 3 * B - Math.pow( A, 2 ) ) / 9,
R = ( 9 * A * B - 27 * C - 2 * Math.pow( A, 3 ) ) / 54,
D = Math.pow( Q, 3 ) + Math.pow( R, 2 ),
Im; let t = []; if ( D >= 0 ) { // complex or duplicate roots
const S = Math.sign( R + Math.sqrt( D ) ) * Math.pow( Math.abs( R + Math.sqrt( D ) ), ( 1 / 3 ) );
const T = Math.sign( R - Math.sqrt( D ) ) * Math.pow( Math.abs( R - Math.sqrt( D ) ), ( 1 / 3 ) );
t = [
-A / 3 + ( S + T ), // real root
-A / 3 - ( S + T ) / 2, // real part of complex root
-A / 3 - ( S + T ) / 2 // real part of complex root
];
// complex part of root pair
Im = Math.abs( Math.sqrt( 3 ) * ( S - T ) / 2 );
// discard complex roots
if ( Im !== 0 ) {
t[ 1 ] = -1;
t[ 2 ] = -1;
}
} else { // distinct real roots
let th = Math.acos( R / Math.sqrt( -Math.pow( Q, 3 ) ) );
t = [
2 * Math.sqrt( -Q ) * Math.cos( th / 3 ) - A / 3,
2 * Math.sqrt( -Q ) * Math.cos( ( th + 2 * Math.PI ) / 3 ) - A / 3,
2 * Math.sqrt( -Q ) * Math.cos( ( th + 4 * Math.PI ) / 3 ) - A / 3
];
Im = 0.0;
}
// discard out of spec roots
for ( let i = 0; i < 3; i ++ ) if ( t[ i ] < 0 || t[ i ] > 1.0 ) t[ i ] = -1;
return t;
}
One thing to note is that a cubic can have up to three roots:
Limits
This code always generates three roots, and frequently some are junk coordinates for out-of-spec roots on flatter curve segments. These coordinates usually lie outside the viewbox… but not always, so some cleanup is required; Particle in Cell’s original code does it with some fancy sorting, but filter()ing would probably do the trick too. This is just a demo, so I didn’t clean up junk coordinates — I wanted to focus on the algebra.
Conclusion: dead man’s curve
I’ll freely admit that none of this awful math is terribly necessary thanks to a large selection of SVG libraries available to choose from. Snap has path.intersection, Paper.js has intersections and there are many others.
I adapted this code mostly as a learning experience, but also because there are circumstances where loading a project up with dependencies isn’t ideal; for example, I’m incorporating this code into a web API that needs to be fast and lightweight. Consider your use case and consult documentation if you’re choosing whether to use an SVG library; not all are created equal and some are poorly documented and buggy/slow.
