Skip to content

Instantly share code, notes, and snippets.

@Sphinxxxx

Sphinxxxx/bezier-curve.markdown

Created September 13, 2023 21:15
Show Gist options
  • Save Sphinxxxx/559897cfe348de77302f6a97dc88cdb9 to your computer and use it in GitHub Desktop.
Save Sphinxxxx/559897cfe348de77302f6a97dc88cdb9 to your computer and use it in GitHub Desktop.
Download ZIP
Bezier curve
Raw
index.html
<script>console.clear();</script>
<script src="https://unpkg.com/vue@2"></script>
<script src="https://unpkg.com/drag-tracker@1"></script>
<script src="https://unpkg.com/@sphinxxxx/[email protected]"></script>
<h2>Bezier curve</h2>
<section id="app">
<label id="t-marker">
<span><i>t</i></span>
<input type="range" v-model.number="svg.t" min="0" max="1" step=".001">
<output>{{ svg.t.toFixed(3) }}</output>
</label>
<div id="config">
<p></p>
<label>
<input type="radio" v-model.number="svg.approx" :value="false">
<span>Curve</span>
</label>
<label>
<input type="radio" v-model.number="svg.approx" :value="true">
<span>Approximated polyline <i>({{ subcurves.length }} segments)</i></span>
</label>
<!--label>
<span>...accuracy</span>
<input type="range" v-model.number="svg.subdiv.accuracy" min="0" max="100">
<output>{{ svg.subdiv.accuracy }}</output>
</label-->
<label>
<span>...tolerance</span>
<input type="range" v-model.number="svg.subdiv.tolerance" min="0" max=".2" step=".01">
<output>{{ svg.subdiv.tolerance }}</output>
</label>
<label>
<span>...max subdivisions</span>
<input type="number" v-model.number="svg.subdiv.max" min="0">
</label>
</div>
<div id="wrapper" ref="wrapper">
<svg ref="svg" viewBox="-100 -100 500 500">
<!--
https://en.wikiversity.org/wiki/CAGD/B%C3%A9zier_Curves
"The curve of the first derivative of a standard Bézier curve is known as a hodograph. If the curve passes through the origin of the hodograph, it corresponds to a cusp on the original curve."
-->
<path class="axes" d="M-200,0 h400 M0,-200 v400" />
<bezier class="deriv" :bez="svg.curve.derivative()" :t="svg.t" :interactive="false" />
<g class="divided">
<bezier v-for="sub in subcurves" :bez="sub" :interactive="false" />
</g>
<polyline v-if="svg.approx" :points="subcurves.map(c => [c.a, c.d])" />
<bezier :bez="svg.curve" :t="svg.t" :interactive="true" :class="{ hidecurve: svg.approx }" />
</svg>
</div>
<!--details>
<summary>Advanced</summary>
<div>
<label>
<input type="radio" v-model="svg.divideByDist" :value="true">
<span>Divide by distance</span>
</label>
<label>
<input type="radio" v-model="svg.divideByDist" :value="false">
<span>Divide by <i>t</i></span>
</label>
<label>
<input type="checkbox" _model="debugSinglePath">
<span>Single path</span>
</label>
</div>
</details-->
</section>
Raw
script.js
/**
* https://gamedev.stackexchange.com/questions/5373/moving-ships-between-two-planets-along-a-bezier-missing-some-equations-for-acce
* https://gamedev.stackexchange.com/a/5427
*/
class Bezier {
constructor(controls) {
this.controls = controls;
}
get a() { return this.controls[0]; }
get b() { return this.controls[1]; }
get c() { return this.controls[2]; }
get d() { return this.controls[3]; }
pointAtT(t) {
const _t = 1 - t,
[a, b, c, d] = this.controls;
const x = _t * _t * _t * a[0]
+ 3 * _t * _t * t * b[0]
+ 3 * _t * t * t * c[0]
+ t * t * t * d[0];
const y = _t * _t * _t * a[1]
+ 3 * _t * _t * t * b[1]
+ 3 * _t * t * t * c[1]
+ t * t * t * d[1];
return [x, y];
}
derivative() {
const [a, b, c, d] = this.controls;
function coordMath(u, v, expr) {
return [expr(u[0], v[0]), expr(u[1], v[1])];
}
//https://en.wikipedia.org/wiki/B%C3%A9zier_curve
//
// The derivative of the cubic Bézier curve with respect to t is
// B′(t) = 3(1−t)²(P1−P0) + 6(1−t)t(P2−P1) + 3t²(P3−P2)
//
// A quadratic Bézier curve is (...)
// B(t) = (1−t)²(P0) + 2(1−t)t(P1) + t²(P2)
//
//So, the derivate of a *cubic* Bezier curve (C0-C3) is a *quadratic* Bezier curve (Q0-Q2) with control points:
// Q0 = 3(C1 - C0)
// Q1 = 3(C2 - C1)
// Q2 = 3(C3 - C2)
//
const q0 = coordMath(b, a, (c1, c0) => 3 * (c1 - c0)),
q1 = coordMath(c, b, (c2, c1) => 3 * (c2 - c1)),
q2 = coordMath(d, c, (c3, c2) => 3 * (c3 - c2));
//console.log('Q', q0, q1, q2);
//For convenience, we want to present this as another cubic curve, so:
//https://stackoverflow.com/questions/3162645/convert-a-quadratic-bezier-to-a-cubic-one
const deriv = new Bezier([
q0,
coordMath(q0, q1, (q0, q1) => q0 + 2/3 * (q1 - q0)),
coordMath(q2, q1, (q2, q1) => q2 + 2/3 * (q1 - q2)),
q2,
]);
return deriv;
}
//https://jeremykun.com/2013/05/11/bezier-curves-and-picasso/
subdivide() {
function midpoint(p, q) {
return [(p[0] + q[0]) / 2, (p[1] + q[1]) / 2];
}
function midpoints(pointList) {
const midpointList = new Array(pointList.length - 1);
for (let i = 0; i < midpointList.length; i++) {
midpointList[i] = midpoint(pointList[i], pointList[i + 1]);
}
return midpointList;
}
const points = this.controls,
firstMidpoints = midpoints(points),
secondMidpoints = midpoints(firstMidpoints),
thirdMidpoints = midpoints(secondMidpoints);
return [new Bezier([points[0], firstMidpoints[0], secondMidpoints[0], thirdMidpoints[0]]),
new Bezier([thirdMidpoints[0], secondMidpoints[1], firstMidpoints[2], points[3]])];
}
//https://agg.sourceforge.net/antigrain.com/research/adaptive_bezier/index.html#toc0013
isFlat(accuracy) {
/* accuracy: 0 (sloppy) - ~100 (detailed) */
const [xA, yA] = this.a,
[xD, yD] = this.d;
const dx = (xD - xA),
dy = (yD - yA),
minLen2 = (dx * dx + dy * dy),
tol2 = minLen2 / accuracy**2;
function closeEnough(p, offset) {
const xTarget = xA + (dx * offset),
yTarget = yA + (dy * offset),
xErr = xTarget - p[0],
yErr = yTarget - p[1];
const err2 = (xErr * xErr + yErr * yErr);
return (err2 <= tol2);
}
//console.log('l', level);
return (closeEnough(this.b, 1/3) && closeEnough(this.c, 2/3));
}
isFlat2(tolerance) {
/* tolerance: 0 (detailed) - 1 (sloppy) */
function vector(from, to) {
return [to[0] - from[0], to[1] - from[1]];
}
function magn2(v) {
return (v[0]**2 + v[1]**2);
}
function dot(v1, v2) {
return (v1[0] * v2[0]) + (v1[1] * v2[1]);
}
//https://www.cuemath.com/geometry/angle-between-vectors/
function cos2(v1, v2) {
const d = dot(v1, v2),
c2 = (d * d) / (magn2(v1) * magn2(v2));
return c2;
}
const [a, b, c, d] = this.controls,
vAD = vector(a, d),
vAB = vector(a, b),
vAC = vector(a, c);
//Check that both control points (B and C) are projected on (i.e. "in-between") the line segment AD,
//and that they don't overlap (i.e. B should be closer to A, and C should be closer to D):
//https://stackoverflow.com/a/3122532/1869660
const lenAD2 = magn2(vAD),
t1 = dot(vAB, vAD) / lenAD2,
t2 = dot(vAC, vAD) / lenAD2;
if((t1 < 0) || (t2 > 1) || (t1 > t2)) { return false; }
//The curve is flat if the angle between AD/AB and DA/DC is small.
//Dot products can be used to measure the cosine of an angle between vectors,
//so here we'll check if the cosine (squared) is accordingly large:
const tol2 = tolerance**2,
cosB = cos2(vAB, vAD),
errB = 1 - cosB;
//console.log('cosB', cosB, errB, Math.acos(Math.sqrt(cosB)) * 180.0/Math.PI);
if(errB > tol2) { return false; }
const errC = 1 - cos2(vector(d, c), vector(d, a));
if(errC > tol2) { return false; }
//console.log('flat2');
return true;
}
subcurves(/*accuracy = 100,*/tolerance = .01, level = 0, maxLevel = 10) {
if ((level > maxLevel) || this.isFlat2(tolerance)) {
return [this];
} else {
return this.subdivide().map(b => b.subcurves(tolerance, level + 1, maxLevel)).flat();
}
}
}
(function() {
"use strict";
//Global state model. Can be changed from within Vue or from the outside.
const _svgState = {
//size: [400, 400],
curve: new Bezier(
[[65, 178], [336, 201], [113, 456], [282, 348]]
//[[202.1114044189453,190.51483154296875], [-110.42572021484375,136.91456604003906], [50.04252243041992,5.081179618835449], [-3.977078914642334,255.50296020507812]]
//.map(([x, y]) => [x*100, y*100])
),
t: .5,
approx: true,
subdiv: {
accuracy: 10,
tolerance: .1,
max: 8,
},
};
Vue.component('drag-node', {
template: '<circle data-draggable @dragging="onDragging" :cx="absCoord[0]" :cy="absCoord[1]" :r="r" />',
props: {
coord: Array,
//If 'coord' is relative to some other point:
offsetCenter: Array,
r: {
default: 16,
}
},
model: {
prop: 'coord',
event: 'do_it',
},
computed: {
absCoord() {
const point = this.coord,
center = this.offsetCenter,
absCoord = center ? [ point[0] + center[0], point[1] + center[1] ]
: point;
return absCoord;
},
},
methods: {
onDragging(e) {
const point = e.detail.pos,
center = this.offsetCenter,
relCoord = center ? [ point[0] - center[0], point[1] - center[1] ]
: point;
this.$emit('do_it', relCoord);
},
},
});
Vue.component('connector', {
template: '<line class="connector" :x1="start[0]" :y1="start[1]" :x2="end[0]" :y2="end[1]" />',
props: ['start', 'end'],
});
Vue.component('bezier', {
template:
`<g class="bezier">
<circle class="t-marker" v-if="tPoint" :cx="tPoint[0]" :cy="tPoint[1]" />
<path :d="pathData" />
<g v-if="interactive" class="controls">
<connector :start="bez.a" :end="bez.b" />
<connector :start="bez.c" :end="bez.d" />
<drag-node class="control" v-model="bez.controls[0]" />
<drag-node class="control" v-model="bez.controls[1]" _offsetCenter="bez.a" />
<drag-node class="control" v-model="bez.controls[2]" _offsetCenter="bez.d" />
<drag-node class="control" v-model="bez.controls[3]" />
</g>
<g v-else class="controls">
<connector :start="bez.a" :end="bez.b" />
<connector :start="bez.c" :end="bez.d" />
</g>
</g>`,
props: ['bez', 't', 'interactive'],
data() {
return {
}
},
computed: {
pathData() {
const bez = this.bez;
return `M${bez.a} C${bez.b} ${bez.c} ${bez.d}`;
},
tPoint() {
const t = this.t;
if(t || (t === 0)) {
return this.bez.pointAtT(t);
}
},
},
});
new Vue({
el: '#app',
data: {
svg: _svgState,
},
computed: {
subcurves() {
//const subs = this.svg.curve.subcurves(this.svg.subdiv.accuracy, 1, this.svg.subdiv.max);
const subs = this.svg.curve.subcurves(this.svg.subdiv.tolerance, 1, this.svg.subdiv.max);
return subs;
}
},
watch: {
'svg.curve.controls': function(nu, old) {
//console.log('cc', ''+newVal);
}
},
mounted() {
console.log('MTD');
const svg = this.$refs['svg'];
dragTracker({
container: svg,
selector: '[data-draggable]',
callback: (node, pos) => {
//Transform to SVG coordinates:
//https://www.sitepoint.com/how-to-translate-from-dom-to-svg-coordinates-and-back-again/
const svgBounds = svg.getBoundingClientRect(),
screenCoord = svg.createSVGPoint();
screenCoord.x = pos[0] + svgBounds.left;
screenCoord.y = pos[1] + svgBounds.top;
const svgCoord = screenCoord.matrixTransform(svg.getScreenCTM().inverse()),
pos2 = [svgCoord.x, svgCoord.y];
//var event = new CustomEvent('dragging', { detail: { pos } });
var event = document.createEvent('CustomEvent');
event.initCustomEvent('dragging', true, false, { pos: pos2 });
node.dispatchEvent(event);
},
});
Vue.nextTick(() => {
zoomableSvg(svg, {
container: this.$refs['wrapper'],
onChanged: function() {
const zoomer = this;
svg.style.setProperty('--screen-px', 1 / zoomer.getZoom());
},
});
});
},
methods: {
},
});
})();
Raw
style.scss
body {
display: flex;
margin: 0;
min-height: 100vh;
flex-flow: column nowrap;
align-items: center;
font-family: Georgia, sans-serif;
h2 {
font-size: 1.1em;
text-align: center;
}
input {
font-size: inherit;
}
}
#app {
width: 100%;
padding: 0 1em;
box-sizing: border-box;
display: flex;
flex-flow: column nowrap;
gap: .5em;
summary, label {
cursor: pointer;
}
}
#t-marker, #config {
position: relative;
z-index: 1;
}
#t-marker {
display: flex;
gap: 1ch;
input {
flex: 1 1 auto;
}
}
#config {
align-self: start;
label {
display: block;
input[type="number"] {
width: 3em;
}
}
}
#wrapper {
position: absolute;
top:0; left:0; bottom:0; right:0;
}
svg {
--screen-px: 1;
display: block;
width: 100%;
height: 100%;
path, polyline, line, circle {
fill: none;
stroke-width: 2;
vector-effect: non-scaling-stroke;
}
path, polyline {
stroke: black;
}
.axes {
stroke: lightskyblue;
}
.connector, .control {
stroke: dodgerblue;
stroke-dasharray: 8;
}
.control {
r: calc(var(--screen-px) * 16);
stroke-dasharray: 6 4;
fill: transparent;
cursor: move;
}
.t-marker {
r: calc(var(--screen-px) * 12);
fill: gold;
fill-opacity: .5;
}
.hidecurve path {
stroke: none;
}
.divided {
pointer-events: none;
.bezier {
color: lime;
&:nth-child(2n) {
color: red;
}
path {
stroke: currentColor;
stroke-opacity: .25;
stroke-width: 8;
stroke-linecap: round;
}
.connector {
stroke: currentColor;
stroke-width: 6;
stroke-dasharray: none;
}
}
}
.deriv {
path {
stroke: silver;
}
line {
stroke: #eee;
stroke-dasharray: none;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment