2c:null 2d:["$","title",null,{"children":"Chaikin's Curves | T.J. Jankun-Kelly | Observable"}] 32:T9a9,chaikin = { const ids = d3.range(11).map(x => DOM.uid("level" + x)); const svg = d3.select(DOM.svg(ewidth, height)) .attr("fill", "none") .attr("id", "top"); ids.map(id => svg.property(id, id)); const marker = svg.append("marker") .attr("id", ids[0].id) .attr("markerUnits", "userSpaceOnUse") .attr("viewBox", "-1 -1 2 2") .attr("markerWidth", 7) .attr("markerHeight", 7); marker.append("circle") .attr("r", 1) .attr("fill", "black"); for(let i = 1; i <= max_depth; ++i) { marker.clone(true) .attr("id", ids[i].id) .select("circle") .attr("fill", d3.schemeCategory10[i]); } svg.append("path") .attr("class", "chaikin") .attr("stroke-width", 1.5) .attr("stroke", "#000") .attr("marker-start", ids[0]) .attr("marker-mid", ids[0]) .attr("marker-end", ids[0]); svg.append("path") .attr("class", "level0") .property("level", 0) .attr("stroke", d3.schemeCategory10[0]); for(let i = 1; i <= max_depth; ++i) { svg.append("path") .attr("class", "level" + i) .property("level", i) .style("stroke", d3.schemeCategory10[i]) .attr("marker-start", ids[i]) .attr("marker-end", ids[i]); } const point = svg.append("g") .attr("class", "control") .attr("fill", d3.schemeCategory10[0]) .attr("cursor", "move") .attr("pointer-events", "all") .attr("stroke-opacity", 0) .attr("stroke-width", 30) .selectAll("rect") .data(mutable control_points) .enter().append("rect") .attr("width", 9) .attr("height", 9) .attr("fill",d3.schemeCategory10[0]) .call(d3.drag() .subject(([x, y]) => ({x, y})) .on("drag", dragged)); function dragged(d) { if(d3.event.x < 0 || d3.event.x >= ewidth || d3.event.y < 0 || d3.event.y >= height) return; d[0] = d3.event.x; d[1] = d3.event.y; mutable control_points = mutable control_points; } mutable control_points = mutable control_points; // Fire intial redraw const base = html`

Chaikin's Curve. Drag control points to generate curve.

`; base.insertBefore(svg.node(), base.firstChild); return base; }33:Tc0b,md`Chaikin's algorithm provides a succinct and numerically stable means of generating an approximating curve from a control polygon ${tex`\color{${d3.schemeCategory10[0]}}\mathrm{p}_0\color{black},\dots,\color{${d3.schemeCategory10[0]}}\mathrm{p}_n`}. Chaikin's curves use the control polygon itself for point generation via *corner-cutting*. ## Cutting Corners Previous to corner-cutting or subdivision approaches, [polynomial splines](https://en.wikipedia.org/wiki/Spline_(mathematics) "Wikipedia: Splines (Mathematics)") were primarily used for curve generation: To generate a curve point, set of piecewise polynomials were evaluated or convolved depending on the formulation. Thus, there was an indirect relation between the spline's control polygon and the geometry of the curve—[the first and last edges might represent the slope at the endpoints](https://en.wikipedia.org/wiki/B%C3%A9zier_curve "Wikipedia: Bézier curve") or [control points could be interpolated by the spline](https://en.wikipedia.org/wiki/Cubic_Hermite_spline "Wikipedia: Cubic Hermite Spline"). As an alternative to spline evaluation, Chaikin proposed a *geometrically* motivated approach: Curve points are generated by operating on the control polygon directly. Consider the control polygon ${tex`\color{${d3.schemeCategory10[0]}}\mathrm{p}_0\color{black},\dots,\color{${d3.schemeCategory10[0]}}\mathrm{p}_n`}. For each control polygon edge ${tex`\color{${d3.schemeCategory10[0]}}\overline{\mathrm{p}_i \mathrm{p}_{i+1}}`}, ${tex`i=0\dots n-1`}, generate two new points ${tex`\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{2i}`}, ${tex`\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{2i+1}`} between them, favoring each endpoint in turn: ${tex.block`\begin{aligned} {\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{2i}} &= \frac{3}{4}{\color{${d3.schemeCategory10[0]}}\mathrm{p}_{i}}+\frac{1}{4}{\color{${d3.schemeCategory10[0]}}\mathrm{p}_{i+1}}\\ {\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{2i+1}} &= \frac{1}{4}{\color{${d3.schemeCategory10[0]}}\mathrm{p}_{i}}+\frac{3}{4}{\color{${d3.schemeCategory10[0]}}\mathrm{p}_{i+1}} \end{aligned} `} The ${tex`{\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{0}},\dots,{\color{${d3.schemeCategory10[1]}}\mathrm{p}^{(1)}_{2n-1}}`} become the new control polygon at *subdivision level* 1 (the base control polygon is level 0). When visualized, it appears we "cut" the corners off of the old control polygon to form the new one:`34:T666,cut_1 = { const id1 = DOM.uid("level1"); const svg = d3.select(DOM.svg(ewidth, height)) .attr("fill", "none"); svg.property(id1, id1); const marker = svg.append("marker") .attr("id", id1.id) .attr("markerUnits", "userSpaceOnUse") .attr("viewBox", "-1 -1 2 2") .attr("markerWidth", 7) .attr("markerHeight", 7); marker.append("circle") .attr("r", 1) .attr("fill", d3.schemeCategory10[1]); svg.append("path") .attr("class", "level0") .property("level", 0) .attr("stroke-dasharray", "4") .attr("stroke", d3.schemeCategory10[0]); svg.append("path") .attr("class", "level1") .property("level", 1) .attr("stroke-width", 2) .attr("stroke", d3.schemeCategory10[1]) .attr("marker-start", id1) .attr("marker-mid", id1) .attr("marker-end", id1); const point = svg.append("g") .attr("class", "control") .attr("fill", d3.schemeCategory10[0]) .attr("stroke", "none") .selectAll("rect") .data(mutable control_points) .enter().append("rect") .attr("width", 9) .attr("height", 9) .attr("fill",d3.schemeCategory10[0]); // Force draw mutable control_points = mutable control_points; const base = html`

Corner cutting of subdivision level 0 (base) to subdivision level 1.

`; base.insertBefore(svg.node(), base.firstChild); return base; }35:T629,cut_3 = { const id2 = DOM.uid("level2"); const id3 = DOM.uid("level3"); const svg = d3.select(DOM.svg(ewidth, height)) .attr("fill", "none"); svg.property(id2, id2); svg.property(id3, id3); const marker = svg.append("marker") .attr("id", id2.id) .attr("markerUnits", "userSpaceOnUse") .attr("viewBox", "-1 -1 2 2") .attr("markerWidth", 7) .attr("markerHeight", 7); marker.append("circle") .attr("r", 1) .attr("fill", d3.schemeCategory10[2]); marker.clone(true) .attr("id", id3.id) .select("circle") .attr("fill", d3.schemeCategory10[3]); svg.append("path") .attr("class", "level2") .property("level", 2) .attr("stroke-dasharray", "4") .attr("stroke", d3.schemeCategory10[2]) .attr("marker-start", id2) .attr("marker-mid", id2) .attr("marker-end", id2); svg.append("path") .attr("class", "level3") .property("level", 3) .attr("stroke-width", 2) .attr("stroke", d3.schemeCategory10[3]) .attr("marker-start", id3) .attr("marker-mid", id3) .attr("marker-end", id3); // Force draw mutable control_points = mutable control_points; const base = html`

Corner cutting of subdivision level 2 to subdivision level 3.

`; base.insertBefore(svg.node(), base.firstChild); return base; }36:T5a2,curve = { const id0 = DOM.uid("level0"); const svg = d3.select(DOM.svg(ewidth, height)) .attr("fill", "none"); svg.property(id0, id0); const marker = svg.append("marker") .attr("id", id0.id) .attr("markerUnits", "userSpaceOnUse") .attr("viewBox", "-1 -1 2 2") .attr("markerWidth", 7) .attr("markerHeight", 7); marker.append("circle") .attr("r", 1) .attr("fill", "black"); svg.append("path") .attr("class", "level0") .property("level", 0) .attr("stroke-dasharray", "4") .attr("stroke", d3.schemeCategory10[0]); svg.append("path") .attr("class", "chaikin") .attr("stroke", "black") .attr("marker-start", id0) .attr("marker-mid", id0) .attr("marker-end", id0); const point = svg.append("g") .attr("class", "control") .attr("fill", d3.schemeCategory10[0]) .attr("stroke", "none") .selectAll("rect") .data(mutable control_points) .enter().append("rect") .attr("width", 9) .attr("height", 9) .attr("fill",d3.schemeCategory10[0]); // Force draw mutable control_points = mutable control_points; const base = html`

Final subdivision at level ${subdivision_level} becomes the curve.

`; base.insertBefore(svg.node(), base.firstChild); return base; }37:T799,md`By default, a Chaikin's curve is *open*, meaning the first and last vertices of the control polygon are not connected and the curve does not connect to itself. By *closing* the curve, the first vertex is considered the last vertex during subdivision at each level (generating ${tex`2n+1`} points instead of ${tex`2n-1`} for that level) and the final curve is connected when rendered. This closed curve can then be rendered as a polygon assuming it can be properly tesselated. The "Closed Polygon" option above will toggle between open an closed curves. ## Summary Chaikin's curve provide a simple and numerically stable method for generating curves geometrically instead of via a convolution of basis functions. These curves are mathematically equivalent to a [quadratic B-spline](https://en.wikipedia.org/wiki/B-spline "Wikipedia: B-Spline"), and thus share their properties of [curve and geometric continuity](http://en.wikipedia.org/wiki/Smoothness "Wikipedia: Smoothness") when adjoining the splines. Their 3D extension are the [Doo-Sabin surfaces](https://en.wikipedia.org/wiki/Doo%E2%80%93Sabin_subdivision_surface "Wikipedia: Doo-Saving Subdivision Surface"). ## Appendix: Implementation I used [Mike Bostock's](https://bost.ocks.org/mike/) Notebook "[De Casteljau's Algorithm](https://beta.observablehq.com/@mbostock/de-casteljaus-algorithm)" as a template for the presentation and code, customized for iterative intead of continuous subdivision as that is more appropriate for Chaikin's. Everything I know about Chakin's curves I learned from [Dr. Ken Joy](http://graphics.cs.ucdavis.edu/~joy/) at [UC Davis](http://www.ucdavis.edu) whose [Chakin's Curves Notes](http://graphics.cs.ucdavis.edu/education/CAGDNotes/Chaikins-Algorithm/Chaikins-Algorithm.html "On-line Geometric Modeling Notes: Chaikin's Curves") still seem to be the gold-standard reference about them online.`38:[] 30:{"id":"17c4a37c90d9af16","slug":"chaikins-curves","title":"Chaikin's Curves","thumbnail":"f77c04dc5e252db952d1bff241706eaa285c5df6b208c42735c8984186409e01","access_level":"public","create_time":"$D2018-09-24T16:42:22.891Z","update_time":"$D2020-08-29T15:40:18.800Z","view_time":null,"first_public_time":"$D2019-09-29T17:03:59.555Z","has_unpublished_edits":null,"fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":"starter_2024"},"version":266,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null}],"members":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"titling":"auto","title":"Chaikin's Curves","cells":[{"id":0,"value":"md`# Chaikin's Curves\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"viewof subdivision_level = number({value:0, min:0, max:10, title:\"Subdivision Level\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"viewof closed = checkbox({\n options: [{ value: \"closed\", label: \"Closed Polygon\" }],\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"mutable control_points =[[0.05, 20], [0.25 ,360], [0.75, 460], [0.95, 20]].map(([x, y]) => [x * ewidth, y])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"{\n const reset = html``;\n \n reset.onclick = (e) => {\n for (let pair of d3.zip([[0.05, 20], [0.25 ,360], [0.75, 460], [0.95, 20]].map(([x, y]) => [x * ewidth, y]), \n mutable control_points))\n {\n pair[1][0] = pair[0][0];\n pair[1][1] = pair[0][1];\n }\n mutable control_points = mutable control_points;\n }\n d3.selectAll(\".control\").data(mutable control_points).select(\"circle\").attr(\"cx\", d => d[0]).attr(\"cy\", d => d[1])\n return reset;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"control_points_1 = (() => \n{\n const ctrl = control_points.slice(0,-1).map((p,i) => [lerp(p, control_points[i+1], 0.25), lerp(p, control_points[i+1], 0.75)]).flat();\n if(closed)\n {\n ctrl.push(lerp(control_points[control_points.length-1], control_points[0], 0.25));\n ctrl.push(lerp(control_points[control_points.length-1], control_points[0], 0.75));\n }\n return ctrl;\n})()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"md`Here is the control polygon at subdivision level 3:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":191,"value":"control_points_2 = (() => \n{\n const ctrl = control_points_1.slice(0,-1).map((p,i) => [lerp(p, control_points_1[i+1], 0.25), lerp(p, control_points_1[i+1], 0.75)]).flat();\n if(closed)\n {\n ctrl.push(lerp(control_points_1[control_points_1.length-1], control_points_1[0], 0.25));\n ctrl.push(lerp(control_points_1[control_points_1.length-1], control_points_1[0], 0.75));\n }\n return ctrl;\n})()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"control_points_3 = (() => \n{\n const ctrl = control_points_2.slice(0,-1).map((p,i) => [lerp(p, control_points_2[i+1], 0.25), lerp(p, control_points_2[i+1], 0.75)]).flat();\n if(closed)\n {\n ctrl.push(lerp(control_points_2[control_points_2.length-1], control_points_2[0], 0.25));\n ctrl.push(lerp(control_points_2[control_points_2.length-1], control_points_2[0], 0.75));\n }\n return ctrl;\n})()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"md`We can repeat cutting corners until some error tolerance for the curve is reached, some maximum number of curve points are generated, or some other criterion. Four or five levels of sudivision are good in practice. Once satisfied, a line strip is rendered between the points of the final control polygon to represent the curve:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"ewidth = Math.min(width,640)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"height = 480","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"max_depth = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"import {number,checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"d3 = require(\"d3-selection@1.4\", \"d3-drag@1.2\", \"d3-scale-chromatic@1.5\",\"d3-array@2.4\",\"d3-transition@1.3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"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":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"levels = {\n const levels = [control_points];\n for(let i = 1; i <= subdivision_level; ++i)\n {\n const new_level = [];\n for(let j = 0; j < levels[i-1].length - 1; ++j)\n {\n const p0 = levels[i-1][j];\n const p1 = levels[i-1][j+1];\n new_level.push(lerp(p0, p1, 0.25));\n new_level.push(lerp(p0, p1, 0.75));\n }\n if(closed)\n {\n new_level.push(lerp(levels[i-1][levels[i-1].length-1], levels[i-1][0], 0.25));\n new_level.push(lerp(levels[i-1][levels[i-1].length-1], levels[i-1][0], 0.75));\n }\n levels.push(new_level);\n }\n return levels;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"{\n const controls = [control_points, control_points_1, control_points_2, control_points_3];\n \n for(let i = 0; i <= max_depth; ++i)\n {\n if(i < subdivision_level)\n d3.selectAll(\"#top .level\" + i).attr(\"d\", `M${levels[i].join(\"L\")}${closed?\"Z\":\"\"}`);\n if(i < 4)\n d3.selectAll(\".level\" + i).attr(\"d\", `M${controls[i].join(\"L\")}${closed?\"Z\":\"\"}`);\n d3.selectAll(\"#top .level\" + i).style(\"visibility\", i < subdivision_level ? \"visible\" : \"hidden\");\n }\n d3.selectAll(\".chaikin\").attr(\"d\", `M${levels[subdivision_level].join(\"L\")}${closed?\"Z\":\"\"}`);\n d3.selectAll(\".control rect\").attr(\"x\", d => d[0]-4.5).attr(\"y\", d => d[1]-4.5);\n \n return md`Update Display`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1"}} 31:"$30:body"