Skip to content

Instantly share code, notes, and snippets.

@balint42
Last active June 4, 2024 02:16
Show Gist options
  • Save balint42/8c9310605df9305c42b3 to your computer and use it in GitHub Desktop.
Save balint42/8c9310605df9305c42b3 to your computer and use it in GitHub Desktop.
Javascript De Casteljau's algorithm splitting n-th degree Bezier curve

De Casteljau's algorithm

De Casteljau's algorithm for splitting n-th degree Bezier curves. Control points can be 1 or 2 dimensional, thus x only or [x, y] vectors. Does not return the values of a Bezier curve at a given point, but rather the correct new control points of the resulting partial curves, if the Bezier curve is split in two curves at the given point. This allows for animated drawing of Bezier curves as well: simply split at the point up to which you want to draw and only draw the first resulting curve, repeat on every animation frame while advancing the split point.

But beyond the well known "animated drawing of Bezier curves" scenario, this code also serves cases where you just want to have the control points of the split curves, not curve values. The whole thing is not optimized for speed but readability. See it here!

<!DOCTYPE HTML>
<html lang="en">
<head>
<title>Bezier splitting</title>
<meta charset="utf-8">
<script type="text/javascript"
src="http://cdnjs.cloudflare.com/ajax/libs/raphael/2.1.0/raphael-min.js">
</script>
<script type="text/javascript">
/**
* @brief De Casteljau's algorithm splitting n-th degree Bezier curve
*/
function bsplit(points, t0) {
var n = points.length - 1; // number of control points
var b = []; // coefficients as in De Casteljau's algorithm
var res1 = []; // first curve resulting control points
var res2 = []; // second curve resulting control points
var t1 = 1 - t0;
// multiply point with scalar factor
var pf = function(p, f) {
var res = [];
for(var i = 0; i < p.length; i++) {
res.push(f * p[i]);
}
return res;
};
// add points as vectors
var pp = function(p1, p2) {
var res = [];
for(var i = 0; i < Math.min(p1.length, p2.length); i++) {
res.push(p1[i] + p2[i]);
}
return res;
};
// set original coefficients: b[i][0] = points[i]
for(var i = 0; i <= n; i++) {
points[i] = (typeof points[i] == "object") ? points[i] : [points[i]];
b.push([ points[i] ]);
}
// get all coefficients
for(var j = 1; j <= n; j++) {
for(var i = 0; i <= (n-j); i++) {
b[i].push( pp(
pf(b[i][j-1], t1),
pf(b[i+1][j-1], t0)
));
}
}
// set result: res1 & res2
for(var j = 0; j <= n; j++) {
res1.push(b[0][j]);
res2.push(b[j][n-j]);
}
return [res1, res2];
};
</script>
<script type="text/javascript">
var paper;
/**
* @brief example using bsplit
*/
window.onload = function() {
// load Raphael
paper = Raphael("paper", 1100, 560);
// original Bezier curve
p0 = [0, 0];
p1 = [1000, 100];
p2 = [500, 500];
draw(p0, p1, p2).attr({
"stroke-width": "3",
"stroke": "#FDD1BD"
});
// split at 0.3
var points = bsplit([p0, p1, p2], 0.3);
// part1 split Bezier curve
var curve1 = points[0];
draw(curve1[0], curve1[1], curve1[2], 50).attr({
"stroke-width": "3",
"stroke": "#E0AE9F"
});
// part2 split Bezier curve
var curve2 = points[1];
draw(curve2[0], curve2[1], curve2[2], 50).attr({
"stroke-width": "3",
"stroke": "#573E44"
});
};
var draw = function(p0, p1, p2, dx, dy) {
dx = (typeof dx == "undefined") ? 0 : dx;
dy = (typeof dy == "undefined") ? 0 : dy;
return paper.path("M "+(p0[0]+dx).toString()+" "+(p0[1]+dy).toString()+
" Q "+(p1[0]+dx).toString()+" "+(p1[1]+dy).toString()+
" "+(p2[0]+dx).toString()+" "+(p2[1]+dy).toString()
);
};
</script>
</head>
<body style="background: #9B8586;">
<div id="center">
<div id="paper"></div>
</div>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment