2b:null 2c:["$","title",null,{"children":"Barycentric Coordinates | T.J. Jankun-Kelly | Observable"}] 31:T70c,md`Formally, barycentric coordinates are the coordinates of a point with respect to a simplex in an affine space. Practically, they are a way to express the location of a point with respect to a line, triangle, or tetrahedron with respect to the geometry, not the global coordinates. In computer graphics, barycentric coordinates are used in rasterization, texture mapping, modeling surfaces, and [performing point-in-triangle tests](https://beta.observablehq.com/@kelleyvanevert/2d-point-in-triangle-test). The definition and calculation of these coordinates is discussed here. ## Lines Consider two points ${tex`\color{${d3.schemeCategory10[0]}}\mathrm{a}`} and ${tex`\color{${d3.schemeCategory10[1]}}\mathrm{b}`}; the displacement (vector) from ${tex`\mathrm{\color{${d3.schemeCategory10[0]}}\mathrm{a}}`} to ${tex`\mathrm{\color{${d3.schemeCategory10[1]}}\mathrm{b}}`} is ${tex`\mathbf{ab}`}${tex`=\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}-\color{${d3.schemeCategory10[0]}}\mathrm{a}`}. We can scale this displacement by any value between 0 and 1 to travel along the line segment between ${tex`\color{${d3.schemeCategory10[0]}}\mathrm{a}`} and ${tex`\color{${d3.schemeCategory10[1]}}\mathrm{b}`}: ${tex`\mathrm{p}(t)=\textcolor{${d3.schemeCategory10[0]}}{\mathrm{a}}+t\mathbf{ab}`}; this is just good ole lerp.`32:T55a,line = { const a = [ewidth*0.25, 16]; const b = [ewidth*0.75, 32]; const ab = sub(b,a); const p = add(a, scale(t, ab)); const a_0 = add(a, scale(-1, ab)); const b_0 = add(a, scale(+2, ab)); return html`

Barycentric Coords. for ${tex`\overrightarrow{\mathbf{ab}}`}: ${tex`[\textcolor{${d3.schemeCategory10[0]}}{\alpha}, \textcolor{${d3.schemeCategory10[1]}}{\beta}]=`}[${fmt(1-t)},${fmt(t)}]

` }33:T88a,md`Instead of thinking about how far along the line segment to travel, we can instead think about the point as a *normalized weighted average* of the endpoints: If we take half of ${tex`\textcolor{${d3.schemeCategory10[0]}}{\mathrm{a}}`} and half of ${tex`\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}`}, we are in the middle of the line; changing the ratio changes the position. Mathematically, this is a simple change in the equation: ${tex.block`\begin{aligned} \mathrm{p}(t) &= \mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}} + t\mathbf{ab}\\ &= \mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}} + t\left(\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}-\textcolor{${d3.schemeCategory10[0]}}{\mathrm{a}}\right)\\ &= \mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}} + t\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}-t\textcolor{${d3.schemeCategory10[0]}}{\mathrm{a}}\\ &= \left(1-t\right)\mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}} + t\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}\\ \mathrm{p} &= \textcolor{${d3.schemeCategory10[0]}}{\alpha\mathrm{a}} + \textcolor{${d3.schemeCategory10[1]}}{\beta\mathrm{b}}\\ \end{aligned}`} where ${tex`\textcolor{${d3.schemeCategory10[0]}}{\alpha}, \textcolor{${d3.schemeCategory10[1]}}{\beta}`}. are the **barycentric coordinates** of ${tex`\mathrm{p}`}. \[[1](#footnote_combos "Footnote: Sums")\] So far, we have talked about points only between the endpoints of the line segment. However, as lines are infinite in extent, we can extend our coordinates as well. In fact, there is no limit on the values of ${tex`\textcolor{${d3.schemeCategory10[0]}}{\alpha}`} and ${tex`\textcolor{${d3.schemeCategory10[1]}}{\beta}`} other than that their sum must be one: the parametric term ${tex`t`} is less than zero when ${tex`\textcolor{${d3.schemeCategory10[0]}}{\alpha} > 1`} (and thus we are to the left of ${tex`\textcolor{${d3.schemeCategory10[0]}}{\mathrm{a}}`}) and ${tex`t > 1`} when ${tex`\textcolor{${d3.schemeCategory10[1]}}{\beta} > 1`} (and thus we are to the right of ${tex`\textcolor{${d3.schemeCategory10[1]}}{\mathrm{b}}`}). We can demonstrate this by removing the constraints on ${tex`t`} [above](#line).`34:T42d,md`When we express two (or more) points as a normalized weighted sum, we call the sum an affine combination if the weights are allowed any value and a convex combination if they are limited between ${tex`0\dots 1`} individually. This distinction is important when we generalize to polygons. ## Triangles In the plane, three non-colinear points ${tex`\color{${d3.schemeCategory10[0]}}\mathrm{a}`}, ${tex`\color{${d3.schemeCategory10[1]}}\mathrm{b}`}, ${tex`\color{${d3.schemeCategory10[2]}}\mathrm{c}`} define a triangle, the simplex in two dimensions. As we did before, we can take the normalized weighted sum of the triangle endpoints to generate any point on the plane—the weights are again the point's barycentric coordinates (click the points to interact):`35:T6ea,triangle = { const tri = html`

Areas for ${tex`\Delta\mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}\textcolor{${d3.schemeCategory10[1]}}{b}\textcolor{${d3.schemeCategory10[2]}}{c}}`}

` d3.select(tri).selectAll(".vertex>circle").call(d3.drag() .on("drag", dragging) .on("drag.update", update)); d3.select(tri).selectAll(".point>circle").call(d3.drag() .on("drag", dragging) .on("drag.update", update)); update(); return tri; }39:T852,{ // Triangle edges d3.selectAll(".ab").attr("x1", a[0]).attr("y1", a[1]).attr("x2", b[0]).attr("y2", b[1]); d3.selectAll(".bc").attr("x1", b[0]).attr("y1", b[1]).attr("x2", c[0]).attr("y2", c[1]); d3.selectAll(".ac").attr("x1", a[0]).attr("y1", a[1]).attr("x2", c[0]).attr("y2", c[1]); // Lines to point d3.selectAll(".ap").attr("x1", a[0]).attr("y1", a[1]).attr("x2", p[0]).attr("y2", p[1]); d3.selectAll(".bp").attr("x1", b[0]).attr("y1", b[1]).attr("x2", p[0]).attr("y2", p[1]); d3.selectAll(".cp").attr("x1", c[0]).attr("y1", c[1]).attr("x2", p[0]).attr("y2", p[1]); // Triangle and sub-triangles d3.selectAll(".abc").attr("d", `M${[a, b, c].join("L")} Z`); d3.selectAll(".pbc").attr("d", `M${[p, b, c].join("L")} Z`); d3.selectAll(".apc").attr("d", `M${[a, p, c].join("L")} Z`); d3.selectAll(".abp").attr("d", `M${[a, b, p].join("L")} Z`); // Vertices & Labels d3.selectAll(".vertex>circle").each(function process() { const target = {"a":a, "b":b, "c":c}[this.parentElement.classList[1]]; d3.select(this).attr("cx", target[0]).attr("cy", target[1]); }); d3.selectAll(".vertex>text").each(function process() { const target = {"a":a, "b":b, "c":c}[this.parentElement.classList[1]]; d3.select(this).attr("x", target[0]).attr("y", target[1]); }); // Point & Label d3.selectAll(".point>circle").attr("cx", p[0]).attr("cy", p[1]); d3.selectAll(".point>text").attr("x", p[0]).attr("y", p[1]); const caption_tri = html`Barycentric Coords. for ${tex`\Delta\mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}\textcolor{${d3.schemeCategory10[1]}}{b}\textcolor{${d3.schemeCategory10[2]}}{c}}`}: ${tex`\textcolor{${d3.schemeCategory10[0]}}{\alpha}=`}${fmt(alpha)}, ${tex`\textcolor{${d3.schemeCategory10[1]}}{\beta}=`}${fmt(beta)}, ${tex`\textcolor{${d3.schemeCategory10[2]}}{\gamma}=`}${fmt(gamma)}`; d3.select("#triangle>figcaption").html(caption_tri.innerHTML); return md`Triangle dragging code took a lot of head bashing; [async is fun!](http://infowantstobeseen.org/thoughts/some-noticeable-thoughts-on-observable/ "Some Noticeable Notes on Observable")`; }3a:[] 2f:{"id":"e828ee5776f183b6","slug":"barycentric-coordinates","title":"Barycentric Coordinates ","thumbnail":"233e7c8a384d1b63aeceb57e0a7c20f8f879f73e3dee1e2a8de99f2dc3ba7374","access_level":"public","create_time":"$D2018-08-31T02:16:00.931Z","update_time":"$D2020-08-29T15:41:28.838Z","view_time":null,"first_public_time":"$D2018-09-07T03:35:42.704Z","fork":false,"stars":40,"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":1185,"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":[{"id":"16de6568ecfd9ae7","reply_to_id":null,"content":"Cool. Just fot test comment.","create_time":"$D2020-06-18T16:28:49.557Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"0f5ddc47aefe7f94","login":"voland","name":"Andrew Voron","avatar_url":"https://avatars-next.observableusercontent.com/b9aa1780c7244b883e050e41199e63d78de5e8b65828bf57c1ffa18312ef61f7","tier":null}}],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":14,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"title":"Barycentric Coordinates ","cells":[{"id":0,"value":"md`# Barycentric Coordinates \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":47,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":175,"value":"viewof t = {\n const line_form = slider({min:-1,max:2, format:fmt});\n line_form.style.cssText = \"display:block;max-width:640px;margin:auto;\";\n line_form.input[\"oninput\"] = (e) => {\n e && e.preventDefault();\n if((line_form.input.value < 0 || line_form.input.value > 1) && constrain_line == \"constrain\")\n {\n line_form.input.value = Math.min(1, Math.max(0, line_form.input.value));\n line_form.output.value = line_form.input.value;\n e.stopPropagation();\n e.preventDefault();\n line_form.dispatchEvent(new CustomEvent(\"input\"));\n return;\n }\n };\n return line_form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":91,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":144,"value":"viewof constrain_line = checkbox({\n options: [{ value: \"constrain\", label: \"Constrain to segment\" }],\n value: \"constrain\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":215,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":223,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":352,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":514,"value":"calc_barycentric = (pt, vert_a, vert_b, vert_c) => {\n const ab = sub(vert_b, vert_a);\n const ac = sub(vert_c, vert_a);\n const ap = sub(pt, vert_a);\n\n const nac = [vert_a[1] - vert_c[1], vert_c[0] - vert_a[0]];\n const nab = [vert_a[1] - vert_b[1], vert_b[0] - vert_a[0]];\n\n const bary_beta = dot(ap, nac) / dot(ab, nac);\n const bary_gamma = dot(ap, nab) / dot(ac, nab);\n const bary_alpha = 1.000 - bary_beta - bary_gamma;\n \n return [bary_alpha, bary_beta, bary_gamma];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1107,"value":"md`Our solution is a *geometrically* motivated solution, as opposed to an *algebriacally* motivated approach. In two dimenions, we have two unknowns (any pair of barycentric coordinates) and the two equations to calculate ${tex`\\mathrm{p}`}'s Cartesian coordinates. Thus, we can [solve a simple linear system](https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Conversion_between_barycentric_and_Cartesian_coordinates) to also find the coordinate values.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":237,"value":"md`## Tetrahedra\n\nThe four vertices of a tetrahedra define an affine 3-dimensional space similarly to a triangle for 2D and a line in 1D. Instead of triangle area ratios, [we use tetrahedra subvolume ratios](http://www.iue.tuwien.ac.at/phd/nentchev/node31.html). We can also [define the coordinates algebraically](https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_tetrahedra).\n\nIn addition to interpolation and point-in-simplex tests, barycentric coordinates on tetrahedra are extensively used in flow visualization, e.g. [particle tracing](https://ieeexplore.ieee.org/document/506224/ \"Interactive time-dependent particle tracing using tetrahedral decomposition\").`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1094,"value":"md`## Summary\n\nBarycentric coordinates have a multitude of uses in computer graphics and visualization, and are inexpensive to calculate. These coordinates provide [a clear way of describing many geometric problems](http://web.evanchen.cc/handouts/bary/bary-full.pdf).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":122,"value":"footnote_combos = md`## Footnotes\n\n\\[1\\] Strictly speaking, adding two points or scaling points are not defined in affine space. However, as we demonstrated, these operations are just shorthand for scaling and adding the vectors expressed by the differences of the points (their displacements).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":363,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":909,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":481,"value":"footnote_distance = md`[3] Formally, the ratio of distances in question is not with respect to the edge opposite, but along the line from the vertex in question to the opposite side through ${tex`\\mathrm{p}`} (the [cevian](https://en.wikipedia.org/wiki/Cevian) through ${tex`\\overrightarrow{\\mathbf{bp}}`} if we are solving for ${tex`\\textcolor{${d3.schemeCategory10[1]}}{\\beta}`})—this directly relates to the ratios of triangle areas above. However, all the distances involved are part of similar right triangles and thus the ratios are the same. Calculating the distances from the opposite edge is more straightforward than calculating along ${tex`\\overrightarrow{\\mathbf{bp}}`} directly. `\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":39,"value":"md`## Appendix: Implementation\n\nThis notebook uses some ideas from [Kelley van Evert's](https://kelleyvanevert.nl/) Notebook \"[2D point in triangle test](https://beta.observablehq.com/@kelleyvanevert/2d-point-in-triangle-test)\" and [Mike Bostock's](https://bost.ocks.org/mike/) Notebook \"[De Casteljau's Algorithm](https://beta.observablehq.com/@mbostock/de-casteljaus-algorithm)\". \n\nThis formalism I learned at the feet of [Dr. Ken Joy](http://graphics.cs.ucdavis.edu/~joy/) at [UC Davis](http://www.ucdavis.edu) while a student; Ken was influenced by [Dr. Tony DeRose's](http://graphics.pixar.com/people/derose/) [coordinate-free approach](http://graphics.pixar.com/people/derose/publications/GeometryBook/paper.pdf) to Computer Graphics. [Shirley & Marschner](https://www.cs.cornell.edu/~srm/fcg4/ \"Fundamentals of Computer Graphics, 4th Ed.\") also proved helpful.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":56,"value":"add = ([x1, y1], [x2, y2]) => [x1+x2, y1+y2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":51,"value":"sub= ([x1, y1], [x2, y2]) => [x1-x2, y1-y2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":548,"value":"dot = ([px,py],[qx, qy]) => px * qx + py * qy","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":657,"value":"cross = ([px, py, pz=0], [qx, qy, qz=0]) => [py*qz-qy*pz, qx*pz-px*qz, px*qy-py*qx]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":59,"value":"scale = (s, [x,y]) => [s*x, s*y]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":667,"value":"d3 = require(\"d3-drag@1.2\",\"d3-selection@1.4\",\"d3-dispatch\", \"d3-format\", \"d3-scale-chromatic@1.5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":335,"value":"fmt = d3.format(\" 6.2f\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1117,"value":"ewidth = Math.min(width, 640)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":169,"value":"import {slider,checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":245,"value":"mutable a = [Math.min(300, ewidth) * 0.5 + (0.5* ewidth-150), 150 - 150.0 / (2 * Math.cos(30 * Math.PI / 180.))]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":247,"value":"mutable b = [Math.min(300,ewidth)*0.25+(0.5*ewidth-150), 150 + 0.5 * 150 * Math.tan(30 * Math.PI / 180.)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":249,"value":"mutable c = [Math.min(300,ewidth) * 0.75+(ewidth/2-150), 150 + 0.5 * 150 * Math.tan(30 * Math.PI / 180)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":518,"value":"mutable p = scale(0.33333, add(a, add(b, c)))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":310,"value":"mutable alpha=0.3333","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":315,"value":"mutable beta=0.3333","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":317,"value":"mutable gamma=0.3333","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":901,"value":" function dragging()\n {\n const draggable = { \"a\": mutable a, \"b\": mutable b, \"c\": mutable c, \"p\": mutable p};\n const dragged = draggable[this.parentElement.classList[1]];\n dragged[0] = d3.event.x;\n dragged[1] = d3.event.y;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":904,"value":" function update()\n {\n const [bary_alpha, bary_beta, bary_gamma] = calc_barycentric(mutable p, mutable a, mutable b, mutable c);\n mutable alpha = bary_alpha;\n mutable beta = bary_beta;\n mutable gamma = bary_gamma;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":674,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 30:"$2f:body"