Barycentric Coordinates a:link, a:hover, a:focus, a:visited { color: #7d162f; text-decoration: none; } a:focus, a:hover { text-decoration: underline; border-bottom: none; } a:visited { color: #600; }
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. The definition and calculation of these coordinates is discussed here. Lines Consider two points <circle cx=4 cy=10 r=3.5 fill= > and <circle cx=4 cy=10 r=3.5 fill= > ; the displacement (vector) from to is . We can scale this displacement by any value between 0 and 1 to travel along the line segment between and : ; this is just good ole lerp.
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`<figure id="line" ><svg width=${ewidth} height="64"> <line x1="${a_0[0]}" y1="${a_0[1]}" x2="${a[0]}" y2="${a[1]}" stroke="black" stroke-dasharray="1%"></line> <line x1="${a[0]}" y1="${a[1]}" x2="${b[0]}" y2="${b[1]}" stroke="black"></line> <line x1="${b[0]}" y1="${b[1]}" x2="${b_0[0]}" y2="${b_0[1]}" stroke="black" stroke-dasharray="1%"></line> <g fill="${d3.schemeCategory10[0]}"> <circle r="5" cx="${a[0]}" cy="${a[1]}"></circle> <text x="${a[0]+5}" y="${a[1]+15}">a</text> </g> <g fill="${d3.schemeCategory10[1]}"> <circle r="5" cx="${b[0]}" cy="${b[1]}"></circle> <text x="${b[0]+5}" y="${b[1]+15}">b</text> </g> <g> <circle r="5" fill="black" stroke="transparent" cx="${p[0]}" cy="${p[1]}"></circle> <text transform="translate(5,15)" x="${p[0]}" y="${p[1]}">p</text> </g> </svg> <figcaption style="max-width:640px;text-align:center">Barycentric Coords. for ${tex`\overrightarrow{\mathbf{ab}}`}: ${tex`[\textcolor{${d3.schemeCategory10[0]}}{\alpha}, \textcolor{${d3.schemeCategory10[1]}}{\beta}]=`}[${fmt(1-t)},${fmt(t)}]</figcaption></figure>` }
viewof t = { const line_form = slider({min:-1,max:2, format:fmt}); line_form.style.cssText = "display:block;max-width:640px;margin:auto;"; line_form.input["oninput"] = (e) => { e && e.preventDefault(); if((line_form.input.value < 0 || line_form.input.value > 1) && constrain_line == "constrain") { line_form.input.value = Math.min(1, Math.max(0, line_form.input.value)); line_form.output.value = line_form.input.value; e.stopPropagation(); e.preventDefault(); line_form.dispatchEvent(new CustomEvent("input")); return; } }; return line_form; }
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 and half of , we are in the middle of the line; changing the ratio changes the position. Mathematically, this is a simple change in the equation: where . are the barycentric coordinates of . [1] 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 and other than that their sum must be one: the parametric term is less than zero when (and thus we are to the left of ) and when (and thus we are to the right of ). We can demonstrate this by removing the constraints on above.
viewof constrain_line = checkbox({ options: [{ value: "constrain", label: "Constrain to segment" }], value: "constrain" })
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 individually. This distinction is important when we generalize to polygons. Triangles In the plane, three non-colinear points <circle cx=4 cy=10 r=3.5 fill= > , <circle cx=4 cy=10 r=3.5 fill= > , <circle cx=4 cy=10 r=3.5 fill= > 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):
triangle = { const tri = html`<figure id="triangle"><svg width=${ewidth} height="300"> <path class="abc" stroke="transparent" fill="whitesmoke" /> <line class="bc" stroke="${d3.schemeCategory10[0]}" /> <line class="ac" stroke="${d3.schemeCategory10[1]}" /> <line class="ab" stroke="${d3.schemeCategory10[2]}" /> <line class="ap" stroke-dasharray="1%" stroke="black" /> <line class="bp" stroke-dasharray="1%" stroke="black" /> <line class="cp" stroke-dasharray="1%" stroke="black" /> <g style="cursor:move" class="vertex a"> <circle r="5" fill="${d3.schemeCategory10[0]}" stroke="transparent" stroke-width="30"></circle> <text fill="${d3.schemeCategory10[0]}" transform="translate(5,15)">a</text> </g> <g style="cursor:move" class="vertex b"> <circle r="5" fill="${d3.schemeCategory10[1]}" stroke="transparent" stroke-width="30"></circle> <text fill="${d3.schemeCategory10[1]}" transform="translate(5,15)">b</text> </g> <g style="cursor:move" class="vertex c"> <circle r="5" fill="${d3.schemeCategory10[2]}" stroke="transparent" stroke-width="30"></circle> <text fill="${d3.schemeCategory10[2]}" transform="translate(5,15)">c</text> </g> <g style="cursor:move" class="point p"> <circle r="5" fill="black" stroke="transparent" stroke-width="30"></circle> <text transform="translate(5,15)">p</text> </g> </svg> <figcaption style="max-width:640px;text-align:center"></figcaption></figure>` 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; }
To calculate the coordinates, we embed our affine triangle into a space with a known inner-product; in this case, the familiar Eucliean space. In addition, we limit ourselves to the plane; if our triangle is off the plane, we can first change our frame so that the vertices are rotated unto it. We can then use the signed ratio of distances to calculate the coordinates. [2] An affine coordinate (say ) is 1 when lies on its corresponding vertex (in this case, ) and is 0 when it is on the edge oppostite ( ); thus, the ratio of these distances will give us . [3] This distance is signed to represent that the point could be on the far side of where : where is the normal in the plane to the line . A similar ratio can be used for and with similar normals, though only one of the pair needs to be calculated directly.
calc_barycentric = (pt, vert_a, vert_b, vert_c) => { const ab = sub(vert_b, vert_a); const ac = sub(vert_c, vert_a); const ap = sub(pt, vert_a); const nac = [vert_a[1] - vert_c[1], vert_c[0] - vert_a[0]]; const nab = [vert_a[1] - vert_b[1], vert_b[0] - vert_a[0]]; const bary_beta = dot(ap, nac) / dot(ab, nac); const bary_gamma = dot(ap, nab) / dot(ac, nab); const bary_alpha = 1.000 - bary_beta - bary_gamma; return [bary_alpha, bary_beta, bary_gamma]; }
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 's Cartesian coordinates. Thus, we can solve a simple linear system to also find the coordinate values.
Tetrahedra The 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. We can also define the coordinates algebraically. In addition to interpolation and point-in-simplex tests, barycentric coordinates on tetrahedra are extensively used in flow visualization, e.g. particle tracing.
Summary Barycentric 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.
Footnotes [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).
[2] The ratio of the areas of to can also be used to calculate and similarly for the other coordinates. Areas definitions are useful for calculating the barycentric coordinates in 3D directly without any transforms (see Shirley & Marschner): where the are the normals to their respective triangles found via cross products of the differences of their edges. We have to correct for the signed nature of the coordinates which we can do by noting that any triangle formed from a negative coordinate will be oriented clockwise (assuming standard counter-clockwise representation for positive triangles); thus, taking the dot product with our triangle's normal will correct for the sign:
{ const tri = html`<figure id="areas"><svg width=${ewidth} height="300"> <path class="pbc" stroke="${d3.schemeCategory10[0]}" fill="${d3.schemeCategory10[0]}88"/> <path class="apc" stroke="${d3.schemeCategory10[1]}" fill="${d3.schemeCategory10[1]}88"/> <path class="abp" stroke="${d3.schemeCategory10[2]}" fill="${d3.schemeCategory10[2]}88"/> <g style="cursor:move" class="vertex a"> <circle r="5" fill="${d3.schemeCategory10[0]}" stroke="transparent" stroke-width="30"></circle> <text transform="translate(5,15)">a</text> </g> <g style="cursor:move" class="vertex b"> <circle r="5" fill="${d3.schemeCategory10[1]}" stroke="transparent" stroke-width="30"></circle> <text transform="translate(5,15)">b</text> </g> <g style="cursor:move" class="vertex c"> <circle r="5" fill="${d3.schemeCategory10[2]}" stroke="transparent" stroke-width="30"></circle> <text transform="translate(5,15)">c</text> </g> <g style="cursor:move" class="point p"> <circle r="5" fill="black" stroke="transparent" stroke-width="30"></circle> <text transform="translate(5,15)">p</text> </g> </svg> <figcaption style="max-width:640px;text-align:center">Areas for ${tex`\Delta\mathrm{\textcolor{${d3.schemeCategory10[0]}}{a}\textcolor{${d3.schemeCategory10[1]}}{b}\textcolor{${d3.schemeCategory10[2]}}{c}}`}</figcaption></figure>` 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; }
[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 (the cevian through if we are solving for )—this direclty 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 directly.
Appendix: Implementation This notebook uses some ideas from Kelley van Evert's Notebook "2D point in triangle test" and Mike Bostok's Notebook "De Casteljau's Algorithm". This formalism I learned at the feet of Dr. Ken Joy at UC Davis while a student; Ken was influenced by Dr. Tony DeRose's coordinate-free approach to Computer Graphics. Shirley & Marschner also proved helpful.
add = ([x1, y1], [x2, y2]) => [x1+x2, y1+y2]
sub= ([x1, y1], [x2, y2]) => [x1-x2, y1-y2]
dot = ([px,py],[qx, qy]) => px * qx + py * qy
cross = ([px, py, pz=0], [qx, qy, qz=0]) => [py*qz-qy*pz, qx*pz-px*qz, px*qy-py*qx]
scale = (s, [x,y]) => [s*x, s*y]
d3 = require("d3-drag","d3-selection","d3-dispatch", "d3-format", "d3-scale-chromatic")
fmt = d3.format(" 6.2f")
ewidth = Math.min(width, 640)
import {slider,checkbox} from "@jashkenas/inputs"
mutable a = [Math.min(300, ewidth) * 0.5 + (0.5* ewidth-150), 150 - 150.0 / (2 * Math.cos(30 * Math.PI / 180.))]
mutable b = [Math.min(300,ewidth)*0.25+(0.5*ewidth-150), 150 + 0.5 * 150 * Math.tan(30 * Math.PI / 180.)]
mutable c = [Math.min(300,ewidth) * 0.75+(ewidth/2-150), 150 + 0.5 * 150 * Math.tan(30 * Math.PI / 180)]
mutable p = scale(0.33333, add(a, add(b, c)))
mutable alpha=0.3333
mutable beta=0.3333
mutable gamma=0.3333
function dragging() { const draggable = { "a": mutable a, "b": mutable b, "c": mutable c, "p": mutable p}; const dragged = draggable[this.parentElement.classList[1]]; dragged[0] = d3.event.x; dragged[1] = d3.event.y; }
function update() { const [bary_alpha, bary_beta, bary_gamma] = calc_barycentric(mutable p, mutable a, mutable b, mutable c); mutable alpha = bary_alpha; mutable beta = bary_beta; mutable gamma = bary_gamma; }
{ // 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")`; }