31:T7f0,chart = { const p0 = DOM.uid("p0"); const p1 = DOM.uid("p1"); const p2 = DOM.uid("p2"); const svg = d3.select(DOM.svg(width, height)) .attr("fill", "none") .property("p0", p0) .property("p1", p1) .property("p2", p2); const m0 = svg.append("marker") .attr("id", p0.id) .attr("markerUnits", "userSpaceOnUse") .attr("viewBox", "-1 -1 2 2") .attr("markerWidth", 7) .attr("markerHeight", 7); m0.append("circle") .attr("r", 1) .attr("fill", d3.schemeCategory10[0]); m0.clone(true) .attr("id", p1.id) .select("circle") .attr("fill", d3.schemeCategory10[1]); m0.clone(true) .attr("id", p2.id) .select("circle") .attr("fill", d3.schemeCategory10[2]); svg.append("path") .attr("class", "bezier3") .attr("stroke-width", 1.5) .attr("stroke", "#000"); svg.append("path") .attr("class", "line0") .attr("stroke", d3.schemeCategory10[0]); svg.append("path") .attr("class", "line1") .attr("marker-start", p1) .attr("marker-mid", p1) .attr("marker-end", p1) .attr("stroke", d3.schemeCategory10[1]); svg.append("path") .attr("class", "line2") .attr("marker-start", p2) .attr("marker-mid", p2) .attr("marker-end", p2) .attr("stroke", d3.schemeCategory10[2]); svg.append("circle") .attr("class", "dot") .attr("fill", "black") .attr("r", 3.5); const point = svg.append("g") .attr("class", "points") .attr("fill", d3.schemeCategory10[0]) .attr("cursor", "move") .attr("pointer-events", "all") .attr("stroke", "transparent") .attr("stroke-width", 30) .selectAll("circle") .data(mutable B0) .enter().append("circle") .attr("r", 3.5) .call(d3.drag() .subject(([x, y]) => ({x, y})) .on("drag", dragged)); function dragged(d) { d[0] = d3.event.x; d[1] = d3.event.y; mutable B0 = mutable B0; } return svg.node(); }32:T4d0,{ const svg = d3.select(DOM.svg(width, height)) .attr("fill", "none"); svg.append("path") .attr("stroke", d3.schemeCategory10[3]) .attr("d", `M${B0[0]}L${B1[0]} ${B2[0]} ${B3[0]}`); svg.append("path") .attr("stroke", d3.schemeCategory10[4]) .attr("d", `M${B3[0]}L${B2[1]} ${B1[2]} ${B0[3]}`); svg.append("path") .attr("stroke-width", 1.5) .attr("stroke", d3.schemeCategory10[3]) .attr("d", `M${B0[0]}C${B1[0]} ${B2[0]} ${B3[0]}`); svg.append("path") .attr("stroke-width", 1.5) .attr("stroke", d3.schemeCategory10[4]) .attr("d", `M${B3[0]}C${B2[1]} ${B1[2]} ${B0[3]}`); svg.selectAll("circle") .data([ {point: B0[0], color: d3.schemeCategory10[0]}, {point: B0[3], color: d3.schemeCategory10[0]}, {point: B1[0], color: d3.schemeCategory10[1]}, {point: B1[2], color: d3.schemeCategory10[1]}, {point: B2[0], color: d3.schemeCategory10[2]}, {point: B2[1], color: d3.schemeCategory10[2]}, {point: B3[0], color: "black"} ]) .enter().append("circle") .attr("cx", d => d.point[0]) .attr("cy", d => d.point[1]) .attr("fill", d => d.color) .attr("r", 3.5); return svg.node(); }33:[] 2f:{"title":"De Casteljau’s Algorithm","cells":[{"id":0,"value":"md`# De Casteljau’s Algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"t = (now / 10000) % 1","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"md`Say we have a cubic Bézier ${tex`B`} defined by four control points ${tex`\\beta_0`}, ${tex`\\beta_1`}, ${tex`\\beta_2`} and ${tex`\\beta_3`} . (Drag the control points above to change the shape of the curve, and click the array below to inspect its control points.)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"mutable B0 = [[0.05, 20], [0.25 ,360], [0.75, 460], [0.95, 20]].map(([x, y]) => [x * Math.min(640, width), y])","pinned":true,"hidden":false,"mode":"ojs"},{"id":382,"value":"md`We can interpolate linearly (or “lerp”) between two points ${tex`p_0`} and ${tex`p_1`} given a parameter ${tex`t \\in [0,1]`}: ${tex.block`\\begin{aligned}\np_t = p_0 (1 - t) + p_1 t\n\\end{aligned}`}\n\nFor example, if ${tex`t = 0`}, then ${tex`p_t = p_0`}; if ${tex`t = 1`}, then ${tex`p_t = p_1`}; for other values of ${tex`t`}, ${tex`p_t`} lies somewhere inbetween.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"function lerp([x0, y0], [x1, y1], t) {\n const s = 1 - t;\n return [x0 * s + x1 * t, y0 * s + y1 * t];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":216,"value":"md`Using this method of interpolation, define new control points ${tex`\\beta_0^{(1)}`}, ${tex`\\beta_1^{(1)}`} and ${tex`\\beta_2^{(1)}`} between each pair of adjacent control points ${tex`\\{\\beta_0,\\beta_1\\}`}, ${tex`\\{\\beta_1,\\beta_2\\}`} and ${tex`\\{\\beta_2,\\beta_3\\}`}:${tex.block`\\begin{aligned}\n\\beta_0^{(1)} &:= \\beta_0(1 - t) + \\beta_1t \\\\\n\\beta_1^{(1)} &:= \\beta_1(1 - t) + \\beta_2t \\\\\n\\beta_2^{(1)} &:= \\beta_2(1 - t) + \\beta_3t \\\\\n\\end{aligned}`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"B1 = [lerp(B0[0], B0[1], t), lerp(B0[1], B0[2], t), lerp(B0[2], B0[3], t)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":497,"value":"chart1 = {\n const svg = d3.select(DOM.svg(width, height))\n .attr(\"fill\", \"none\");\n\n svg.append(\"path\")\n .attr(\"class\", \"line0\")\n .attr(\"stroke\", d3.schemeCategory10[0]);\n\n svg.append(\"path\")\n .attr(\"class\", \"line0\")\n .attr(\"marker-start\", chart.p0)\n .attr(\"marker-mid\", chart.p0)\n .attr(\"marker-end\", chart.p0)\n .attr(\"stroke-dasharray\", \"2,2\")\n .attr(\"stroke\", d3.schemeCategory10[1]);\n\n svg.append(\"path\")\n .attr(\"class\", \"line1\")\n .attr(\"marker-start\", chart.p1)\n .attr(\"marker-mid\", chart.p1)\n .attr(\"marker-end\", chart.p1)\n .attr(\"stroke\", d3.schemeCategory10[1]);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":273,"value":"md`Now repeat this process to define control points ${tex`\\beta_0^{(2)}`} and ${tex`\\beta_1^{(2)}`} :${tex.block`\\begin{aligned}\n\\beta_0^{(2)} &:= \\beta_0^{(1)}(1 - t) + \\beta_1^{(1)}t \\\\\n\\beta_1^{(2)} &:= \\beta_1^{(1)}(1 - t) + \\beta_2^{(1)}t \\\\\n\\end{aligned}`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"B2 = [lerp(B1[0], B1[1], t), lerp(B1[1], B1[2], t)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":501,"value":"chart2 = {\n const svg = d3.select(DOM.svg(width, height))\n .attr(\"fill\", \"none\");\n\n svg.append(\"path\")\n .attr(\"class\", \"line1\")\n .attr(\"marker-start\", chart.p1)\n .attr(\"marker-mid\", chart.p1)\n .attr(\"marker-end\", chart.p1)\n .attr(\"stroke\", d3.schemeCategory10[1]);\n\n svg.append(\"path\")\n .attr(\"class\", \"bezier2a\")\n .attr(\"stroke-dasharray\", \"2,2\")\n .attr(\"stroke\", d3.schemeCategory10[2]);\n\n svg.append(\"path\")\n .attr(\"class\", \"bezier2b\")\n .attr(\"stroke-dasharray\", \"2,2\")\n .attr(\"stroke\", d3.schemeCategory10[2]);\n\n svg.append(\"path\")\n .attr(\"class\", \"line2\")\n .attr(\"marker-start\", chart.p2)\n .attr(\"marker-mid\", chart.p2)\n .attr(\"marker-end\", chart.p2)\n .attr(\"stroke\", d3.schemeCategory10[2]);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"md`Note that ${tex`\\beta_0^{(2)}`} and ${tex`\\beta_1^{(2)}`} follow two quadratic Béziers with control points ${tex`\\beta_0`}, ${tex`\\beta_1`}, ${tex`\\beta_2`} and ${tex`\\beta_1`}, ${tex`\\beta_2`}, ${tex`\\beta_3`} respectively.\n\nRepeat this process one last time to define ${tex`\\beta_0^{(3)}`} :${tex.block`\\begin{aligned}\n\\beta_0^{(3)} &:= \\beta_0^{(2)}(1 - t) + \\beta_1^{(2)}t\n\\end{aligned}`}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":140,"value":"B3 = [lerp(B2[0], B2[1], t)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":508,"value":"chart3 = {\n const svg = d3.select(DOM.svg(width, height))\n .attr(\"fill\", \"none\");\n\n svg.append(\"path\")\n .attr(\"class\", \"line2\")\n .attr(\"marker-start\", chart.p2)\n .attr(\"marker-mid\", chart.p2)\n .attr(\"marker-end\", chart.p2)\n .attr(\"stroke\", d3.schemeCategory10[2]);\n\n svg.append(\"path\")\n .attr(\"class\", \"bezier3\")\n .attr(\"stroke-dasharray\", \"2,2\")\n .attr(\"stroke\", \"black\");\n\n svg.append(\"circle\")\n .attr(\"class\", \"dot\")\n .attr(\"fill\", \"black\")\n .attr(\"r\", 3.5);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":293,"value":"md`More generally, given a Bézier curve of degree ${tex`n`} (${tex`n = 3`} for a cubic Bézier), for each ${tex`j=1,\\ldots,n`} and ${tex`i=0,\\ldots,n-j`}, we can define a recurrence relation:${tex.block`\\begin{aligned}\n\\beta _{i}^{(0)} &:= \\beta _{i} \\\\\n\\beta _{i}^{(j)} &:= \\beta _{i}^{(j - 1)}(1 - t) + \\beta_{i+1}^{(j - 1)}t\n\\end{aligned}\n`}\nThe resulting ${tex`\\beta_0^{(n)}`} is a point along the Bézier curve! The curve can also be cut at this point into two curves with respective control points:${tex.block`\\begin{aligned}\n&\\beta_{0}^{(0)},\\beta_{0}^{(1)},\\ldots,\\beta_{0}^{(n)} \\\\\n&\\beta_{0}^{(n)},\\beta_{1}^{(n-1)},\\ldots,\\beta_{n}^{(0)}\n\\end{aligned}`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":454,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":467,"value":"md`This is [De Casteljau’s algorithm](https://en.wikipedia.org/wiki/De_Casteljau's_algorithm).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":589,"value":"md`---\n\n## Further Reading\n\nJason Davies, [Animated Bézier Curves](https://www.jasondavies.com/animated-bezier/)\n
Pomax, [A Primer on Bézier Curves](https://pomax.github.io/bezierinfo/)\n
Wikipedia, [Bézier curve](https://en.wikipedia.org/wiki/Bézier_curve)\n
Wikipedia, [De Boor’s algorithm](https://en.wikipedia.org/wiki/De_Boor's_algorithm)\n
Wikipedia, [De Casteljau’s algorithm](https://en.wikipedia.org/wiki/De_Casteljau's_algorithm)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":587,"value":"md`---\n\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":455,"value":"height = 480","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"{\n d3.selectAll(\".line0\").attr(\"d\", `M${B0.join(\"L\")}`);\n d3.selectAll(\".line1\").attr(\"d\", `M${B1.join(\"L\")}`);\n d3.selectAll(\".line2\").attr(\"d\", `M${B2.join(\"L\")}`);\n d3.selectAll(\".dot\").attr(\"cx\", B3[0][0]).attr(\"cy\", B3[0][1]);\n d3.selectAll(\".bezier2a\").attr(\"d\", `M${B0[0]}Q${B0.slice(1, 3).join(\" \")}`);\n d3.selectAll(\".bezier2b\").attr(\"d\", `M${B0[1]}Q${B0.slice(2, 4).join(\" \")}`);\n d3.selectAll(\".bezier3\").attr(\"d\", `M${B0[0]}C${B0.slice(1).join(\" \")}`);\n d3.selectAll(\".points circle\").attr(\"cx\", d => d[0]).attr(\"cy\", d => d[1]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}