If all you wanted to do was "lerp in 2D", the answer could be rather trivial, for example in the case of a rectangle, where given the values at the four corners, you can trivially interpolate values along two opposing edges, and then get any value in the middle by picking the corresponding pair of points on those edges and interpolate between those. The bit about arbitrary vertices however makes this more complicated.

But, Shaders…​?⌗

If you’ve ever took a closer look at computer graphics, or even just played a videogame, you might think "hold on, they do that all the time, it can’t be that complicated, right?" And once you know what to do, it really isn’t, however finding out what to do is the hard part.

As you may know if you’ve written a shader yourself, you usually have a vertex shader, where you can modify attributes of each vertex, and then a fragment shader, where you suddenly have values for each pixel. The part in-between, where the interpolation happens, is something that’s done automatically in the background.

It may be something you need to do when writing your own game engine (I wouldn’t know), or you may hear about it in one off-hand comment in a multi-hour seminar on shader programming (like this one by Freya Holmér (which I only saw afterwards)). Otherwise, you never really need to worry about it.

Why I wanted this⌗

You may be wondering: if this happens automatically in shaders, why did I need to find out how to do it myself?

My goal was to create a orchestrator for my RGB LED strips where users could create their own small lua programs to produce dynamic color effects. This was done by having the script place colored vertices on a canvas, and having the backend compute the colors on the canvas and sample at the LEDs positions.

Initially it seemed so simple that I wouldn’t need any sort of graphics programming or shader software in there, especially at the low resolution needed to satisfy an LED strip. I didn’t expect to write what at this point might qualify as half of a shader (since that lua program could technically be classified as a kind-of vertex shader).

Prerequisite: Triangulation⌗

As you may have guessed the moment I brought shaders into this story, this whole thing doesn’t just work with an unordered list of vertices. Rather, all the math below is designed to work on triangles. I suppose it could be extended to work with larger polygons, but such experiments will be left as an excersise to the reader.

If your data isn’t already in the form of a list of (non-overlapping) triangles, my recommnedation would be to find a triangulation library for your language of choice (keyword Delaunay, like this one for go) and leave the task of converting your list of vertices to a nice set of triangles up to it (unless you want to do even more math yourself of course, in which case all power to you).

The Math⌗

The thing we want are called barycentric coordinates. They describe a point in a plane as a linear combination of the three vertices of a triangle. We calculate them by solving this linear combination based on the position of the vertices and our target point, and can then apply them as weights to any other properties that the vertices might have, such as color or similar.

Note

The following formulae, except for the last one, are taken from the wikipedia article on barycentric coordinates here. If math is your thing, you will find some further reading there.

If on the other hand math isn’t your thing, you can skip right to the pseudocode.

Given the three vertices of a triangle, $\begin{bmatrix}x_1 \\ y_1 \end{bmatrix}$, $\begin{bmatrix}x_2 \\ y_2 \end{bmatrix}$ and $\begin{bmatrix}x_3 \\ y_3 \end{bmatrix}$, as well as our target point $\begin{bmatrix}x \\ y \end{bmatrix}$, the barycentric coordinates $\begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix}$ are defined as follows:

$$ \begin{bmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{bmatrix} \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} $$

To turn this into a solveable equation, we need to add the condition that the sum of the barycentric coordinates is one: $ \lambda_1 + \lambda_1 + \lambda_1 = 1 $

$$ \begin{bmatrix} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{bmatrix} \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix} = \begin{bmatrix} 1 \\ x \\ y \end{bmatrix} $$

We then rearrange for the barycentric coordinates:

$$ \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix} = { 1 \over 2A } \begin{bmatrix} x_2 y_3 - x_3 y_2 & y_2 - y_3 & x_3 - x_2 \\ x_3 y_1 - x_1 y_3 & y_3 - y_1 & x_1 - x_3 \\ x_1 y_2 - x_2 y_1 & y_1 - y_2 & x_2 - x_1 \end{bmatrix} \begin{bmatrix} 1 \\ x \\ y \end{bmatrix} $$

where $2A = x_1 (y_2-y_3) + x_2 (y_3-y_1) + x_3 (y_1-y_2)$ is twice the signed area of our triangle.

And are thus left with the following complex looking, but ultimately trivial equation:

$$ \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix} = { 1 \over x_1 (y_2-y_3) + x_2 (y_3-y_1) + x_3 (y_1-y_2) } \begin{bmatrix} x_2 y_3 - x_3 y_2 + x(y_2 - y_3) + y(x_3 - x_2) \\ x_3 y_1 - x_1 y_3 + x(y_3 - y_1) + y(x_1 - x_3) \\ x_1 y_2 - x_2 y_1 + x(y_1 - y_2) + y(x_2 - x_1) \end{bmatrix} $$

Which we can transcribe into (pseudo)code as follows:

// given p1, p2 and p3 as the vertices, and t as the target position
// each as arrays of length two, with x at index 0 and y at index 1

l1 = p2[0]*p3[1] - p3[0]*p2[1] + t[0]*(p2[1]-p3[1]) + t[1]*(p3[0]-p2[0])
l2 = p3[0]*p1[1] - p1[0]*p3[1] + t[0]*(p3[1]-p1[1]) + t[1]*(p1[0]-p3[0])
l3 = p1[0]*p2[1] - p2[0]*p1[1] + t[0]*(p1[1]-p2[1]) + t[1]*(p2[0]-p1[0])

// 1 over twice signed area
area2 = 1 / (p1[0]*(p2[1]-p3[1]) + p2[0]*(p3[1]-p1[1]) + p3[0]*(p1[1]-p2[1]))

l1 *= area2
l2 *= area2
l3 *= area2

// and now given prop1, prop2 and prop3 as further properties of the vertices
targetProp = l1*prop1 + l2*prop2 + l3*prop3

Conclusion⌗

So now that we have these coordinates, there are a few additional helpful tricks. First: based on the barycentric coordinates, it is trivial to determine whether the target point is inside or outside the triangle in question, simply by checking whether all three values are positive (→ inside) or not (→ outside).

To then check which of a list of triangles the target point lies within, I resorted to simply iterating over said list and checking each one (though with a cache of which one the previous, adjacent point was in). There may be a smarter way of doing this hidden deep in shader (and/or graphics driver) development theory, but for my use-case I haven’t needed that level of optimization yet.

Thank you for reading! If you have any feedback or comments, you can leave them under this fedi post here.