28:null 29:["$","title",null,{"children":"Corner cutting | Thomas Oberbichler | Observable"}] 2e:[] 2c:{"id":"f419ecedce5d9f82","slug":"corner-cutting","title":"Corner cutting","thumbnail":"c0f98dd24ae35fb271706b1313fe36673fea655f4edb367660b98af6a0aab123","access_level":"public","create_time":"$D2022-01-20T08:25:40.976Z","update_time":"$D2022-01-20T18:08:52.948Z","view_time":null,"first_public_time":"$D2022-01-20T11:52:04.764Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"63ea0ba327c02e72","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":"starter_2024"},"version":621,"publish_version":621,"role":null,"authored":false,"authors":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null}],"members":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Corner cutting","cells":[{"id":0,"value":"# Corner cutting","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":590,"value":"*inspired by [“A Note On Subdivision Curves”](https://www.maplesoft.com/applications/view.aspx?SID=7066&view=html) by Wieslaw Kotarski and Agnieszka Lisowska*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":208,"value":"context.canvas","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":550,"value":"html`Corner cutting with ${tex`u=v=\\frac{i}{20}`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"viewof i = Inputs.range([0, 20], {label: \"i\", value: 14.5, step: 0.1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"viewof animation = Inputs.toggle({label: \"Animation\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"viewof history = Inputs.toggle({label: \"Show history\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":462,"value":"## The algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":467,"value":"md`The corner cutting algorithm was invented by *Georges De Rham* in 1947 [1]. A polygon is refined by subdividing each segment into three parts. Depending on the ratios ${tex`(u:1-u-v:v)`}, an iterative refinement converges to a smooth limit curve.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"viewof u = Inputs.range([0, 1], {label: \"u\", value: 1/3})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"viewof v = Inputs.range([0, 1], {label: \"v\", value: 1/3})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"viewof steps = Inputs.range([0, 10], {label: \"subdivision steps\", value: 1, step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":578,"value":"viewof showPoints = Inputs.toggle({label: \"Show points\", value: true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"{\n const context = DOM.context2d(width, height);\n\n context.lineEnd = \"round\";\n context.lineJoin = \"round\";\n\n const line = d3.line()\n .x(d => xScale(d.x))\n .y(d => yScale(d.y))\n .context(context);\n\n const polygon = (pts, color, strokeWidth, points) => {\n context.save();\n \n context.strokeStyle = color;\n context.lineWidth = strokeWidth;\n context.beginPath();\n line(pts);\n context.stroke()\n\n if (points) {\n context.fillStyle = color\n for (const pt of pts) {\n context.beginPath();\n context.arc(xScale(pt.x), yScale(pt.y), 3, 0, 2 * Math.PI);\n context.fill();\n }\n }\n\n context.restore();\n };\n \n polygon(controlPolygon, colors.red, 1, showPoints);\n \n let refined = controlPolygon;\n \n for (let i = 0; i < steps; i++) {\n refined = deRham(refined, u, v);\n\n if (history) {\n polygon(refined, colors.gray, 1, showPoints);\n }\n }\n\n polygon(refined, colors.black, 2, showPoints);\n \n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":505,"value":"md`By choosing ${tex`u=v=\\frac{1}{3}`} we obtain a ${tex`C^0`} and with ${tex`u=v=\\frac{1}{4}`} a ${tex`C^1`} curve.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":565,"value":"Inputs.button([\n [\"u=1/3 v=1/3\", () => setUV(1 / 3, 1 / 3)],\n [\"u=1/4 v=1/4\", () => setUV(1 / 4, 1 / 4)],\n])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":563,"value":"md`With other ratios, the algorithm might not converge to a smooth curve. E.g. with ${tex`u=\\frac{1}{7}, v=\\frac{6}{7}`} we obtain a simple polyline and with ${tex`u=\\frac{4}{5}, v=\\frac{2}{3}`} a fractal curve.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"Inputs.button([\n [\"u=1/7 v=6/7\", () => setUV(1 / 7, 6 / 7)],\n [\"u=4/5 v=2/3\", () => setUV(4 / 5, 2 / 3)],\n])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":496,"value":"md`*George Chaikin* reinvented the algorithm in 1974 [2] for the application in *computer aided design* (CAD). He proved that the limit curve for ${tex`u=v=\\frac{1}{4}`} is a quadratic B-Spline.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":519,"value":"## References","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":508,"value":"footnote(1, `Un peu de mathématiques à propos d'une courbe plane. Georges De Rham, Elemente der Mathematik, Volume: 2, page 89-97 (1947)`, `https://eudml.org/doc/140466#:~:text=%C2%A0-,Access%20to%20full%20text,-How%20to%20cite`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"footnote(2, `An algorithm for high-speed curve generation. George Merrill Chaikin. Computer Graphics and Image Processing, Volume 3, Issue 4 (1974)`, `https://www.sciencedirect.com/science/article/abs/pii/0146664X74900288`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3,"value":"controlPolygon = [{x: 0, y: 0}, {x: 0.5, y: 1}, {x: 1, y: 0}, {x: 1.5, y: 1}, {x: 2, y: 0}]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"lerp = function (a, b, t) {\n const x = t * b.x + (1 - t) * a.x;\n const y = t * b.y + (1 - t) * a.y;\n\n return {x, y};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"deRham = function (polygon, u, v) {\n const refined = [];\n\n for (let i = 1; i < polygon.length; i++) {\n const a = polygon[i - 1];\n const b = polygon[i];\n \n const p1 = lerp(a, b, u);\n const p2 = lerp(b, a, v);\n\n refined.push(p1, p2);\n }\n\n return refined;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":420,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":159,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"xScale = d3.scaleLinear().domain([0, 2]).range([10, width - 10])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"yScale = d3.scaleLinear().domain([1, 0]).range([10, height - 10])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"context = DOM.context2d(width, height)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"{\n const line = d3.line().x(d => xScale(d.x)).y(d => yScale(d.y)).context(context);\n \n context.clearRect(0, 0, context.canvas.width, context.canvas.height);\n \n context.fillStyle = \"rgba(255,255,255,0.2)\";\n\n let refined = controlPolygon;\n\n for (let k = 0; k < 10; k++) {\n refined = deRham(refined, i / 20, i / 20);\n \n if (history) {\n context.fillRect(0, 0, context.canvas.width, context.canvas.height);\n context.beginPath();\n line(refined);\n context.stroke();\n }\n }\n \n context.beginPath();\n line(refined);\n context.stroke();\n\n return \"draw\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"value":"{\n const input = viewof i;\n\n let step = 0.1;\n \n while (animation) {\n input.value += step;\n \n if (input.value <= 0 || input.value >= 20) {\n step *= -1;\n }\n \n input.dispatchEvent(new Event(\"input\"));\n \n await Promises.delay(100);\n \n if ((viewof animation).value == false) {\n break;\n }\n\n yield \"run animation\";\n }\n\n yield \"stop animation\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"line = d3.line().x(d => xScale(d.x)).y(d => yScale(d.y));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"function set(input, value) {\n input.value = value;\n input.dispatchEvent(new Event(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":447,"value":"setUV = function (u, v) {\n set(viewof u, u);\n set(viewof v, v);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":601,"value":"footnote = (number, text, link) => {\n if (link === undefined) {\n return html`

${text}

`;\n } else {\n return html`

${text}

`;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"d3 = require(\"d3@7.3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"import {colors} from '@oberbichler/colors'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2e","stdlib":"1","titling":"auto"}} 2d:"$2c:body"