# Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

I have a triangle and the value of the pixel intensity at each of the three corners of the triangle. I want to interpolate to find interpolated pixel intensities for a set of points inside the triangle. How can I do this?

The method I've tried is to do an value determination based on the distance of that fill-in point from each of the corners.

As an example, here is a single triangle example, with three points described in the format of (Value, X, Y), though in practice all values might be floating point.

(1.78, 2337, 1955)
(2.95, 2342, 1948)
(1.12, 2347, 1941)

• Also, what research have you done? We expect you to do some research before asking (e.g., check Google, standard textbooks), and show us in the question what you tried and what approaches you considered and rejected. This helps you craft a more specific question, and helps us give you more useful answers. What interpolation methods have you considered? There are lots of methods for interpolation that have been studied in the image processing world (e.g., for resizing images); are any of them suitable for your needs? Is a linear model OK? See cs.stackexchange.com/help/how-to-ask. – D.W. Jun 17 '15 at 18:19
• Apologies, I was adding too much unnecessary information to the question. I have researched without finding much that tackles this problem exactly. The bottom-line is if I have three X, Y coordinates each with a distinct floating-point value, how do I fill-in the triangle they create: edges, insides, and all. And more importantly is there a way to do this without having to brute force find every edge-point and inside-point and then determine the value for each point by interpolating from the corners? This would not scale well if dealing with several thousand triangles simultaneously. – RunJumpSleep Jun 18 '15 at 15:00
• Also to clarify why I am doing this at all, is I need to produce a complete raster-like array from the points, so the space between them being filled is a requirement. – RunJumpSleep Jun 18 '15 at 15:01
• OK, I've edited the question to remove the extraneous material. Please check my edit to see whether it accurately captures your problem. Right now you say you're doing something based on the distance to the corners. Why have you rejected that method? What is the problem with that method? What are your requirements? How do you plan to evaluate answers? As far as the problem of "finding every point inside the triangles", I think that's a separate problem that you should post separately about. We want questions here to be a single, well-focused technical question. – D.W. Jun 18 '15 at 19:19
• For finding which grid points are in the triangle, take a look at stackoverflow.com/q/10592700/781723 and see if it helps you. (That's about the 3D generalization, but it applies to your 2D situation as well, I think.) If it doesn't, post a new question here about the problem of finding which grid points are in the triangle. – D.W. Jun 18 '15 at 19:44

## 1 Answer

One very simple approach is to use a linear model. Let $I(x,y)$ be the pixel intensity of the pixel at coordinates $(x,y)$. We can fit to a linear model:

$$I(x,y) = \alpha x + \beta y + \gamma,$$

where $\alpha,\beta,\gamma$ are parameters to be determined. If we are given the pixel intensity at each corner of the triangle, then we know the value of $I(x,y)$ for each corner point $(x,y)$. Since a triangle has 3 corners, this gives us 3 linear equations in 3 unknowns. We can solve this system of linear equations to find $\alpha,\beta,\gamma$, and then use this linear model to fill in the value of all other points.

In particular, if the $i$th corner is at $(x_i,y_i)$ and has pixel intensity (value) $v_i$, then we get a system of three equations:

\begin{align*} I(x_1,y_1) &= v_1\\ I(x_2,y_2) &= v_2\\ I(x_3,y_3) &= v_3 \end{align*}

Expanding the linear model, this becomes

\begin{align*} \alpha x_1 + \beta y_1 + \gamma &= v_1\\ \alpha x_2 + \beta y_2 + \gamma &= v_2\\ \alpha x_3 + \beta y_3 + \gamma &= v_3 \end{align*}

Here we have three unknowns ($\alpha,\beta,\gamma$) and the rest are known constants. So, we can solve this system of linear equations for $\alpha,\beta,\gamma$. This involves inverting a $3 \times 3$ matrix and then multiplying it by a $3$-vector, so it should be relatively efficient.

Once you have derived the parameters $\alpha,\beta,\gamma$, you can now evaluate the value $I(x,y)$ at any other point $(x,y)$ in the triangle (or on its interior). This lets you interpolate the value at each fill-in point.

The approach I described above works for black-and-white images. If you have a color image, you can interpolate independently for each of the 3 channels (R, G, and B; you might get better results if you work in a transformed color space, e.g., HSV, CIELAB, CIECAM02).

I recommend you take a look at barycentric coordinates, as they simplify the formulas for interpolation in a triangular mesh.

If you are familiar with interpolation for image processing, bilinear interpolation is a slight generalization of this approach, where you add a $\delta xy$ term to the linear model. However, bilinear interpolation isn't applicable here, because it requires 4 points: 3 points isn't enough.

It's possible to come up with more sophisticated interpolation models. For instance, you could fit a linear model to more than 3 points (e.g., taking the corner points of all adjacent triangles as well), and use ordinary least squares linear regression to find a best-fit linear model, weighting the corners of the adjacent triangles lower than the corners of the target triangle. You could also build generalizations of bicubic interpolation, etc.

More generally, I recommend that you do a bit of research on "tetrahedral interpolation", as I believe that is the catch-phrase for the kind of problem you are asking about (or the generalization of it to 3 dimensions).