Triangle indexing

Consider an evenly subdivided triangle with a resolution r which will have a triangular number \(\frac{r(r+1)}{2}\) of points. For instance a triangle with \(r=2\) will have 3 points, \(r=3\) will have \(6\) points, and for \(r = 4\) it will have \(10\) points and looks like this:

Every point on the subdivided triangle can be indexed using two integers \(x\) and \(y\). \((0, 0)\) will give you the bottom-left point, \((r-1, 0)\) and \((0, r-1)\) will give you the bottom right point and top point, respectively.

Say that we are given some barycentric coordinates \(\lambda = [u, v, w]\). We can find out exactly which sub-triangle \([(x_0, y_0), (x_1, y_1), (x_2, y_2)]\) we are currently in. First we find out which cell of the grid we are in by using \(i = \lfloor r * v \rfloor\) and \(j = \lfloor r * w \rfloor\). Then we can determine in each cell wether we are in the upper triangle by checking whether \((v \mod 1/r + w \mod 1/r) > 1/r\).

Then depending on the if we are in the upper the triangle or the lower we can find the coordinates of the triangle points. If we are in the upper triangle then the triangle is \([(i + 1, j), (i + 1, j + 1) (i, j + 1)]\) or in the lower \([(i, j), (i + 1, j) (i, j + 1)]\). We can even calculate local barycentric coordinates in those triangles by taking \(\lambda_l = \text{fract}(r * \lambda)\) in the upper triangle we need to take \(1 - \lambda_l\) to have the coordinates in the right order.

Consider now that the positions (or other attributes) of the subdivided triangle points are stored in a single one dimensional array. The positions are stored in such a way that the points are inserted starting from the left bottom row of the triangle and moving to the right. If a row ends we go up a row and start again going left to right until the very top of the triangle.

For ease of acces it would be great if we can directly go from a coordinate \((x, y)\) to some index into the array. It seems easy right? Just some arithmetic with the \(x\), \(y\) and \(r\) parameters. Here is what I came up with some time ago:

\[idx(i, j) = i + (j * (2 + r - (j + 1) / 2)) - j - ((j + 1) \% 2) * (j / 2)\]

Yes, this is correct and, no, I do not remember exactly how I determined this.

After many years I thought I should revisit this a bit and find out if I can find something smarter and more concise than this.

Can we do better?

Clearly the index is going to be \(x\) plus the sum of number of points in the rows up untill row \(y\). So what is the sum of the previous rows at \(y\)? it is \(\sum^{y - 1}_{i=0} (r - i)\). Now computing this sum for every coordinate does not improve upon the monstrosity of before. So let’s write it out the sum for different values of \(y\) and try to find a closed form expression:

\[\begin{array}{|l|l|l|} \hline \text{y} & \sum^{y - 1}_{i=0} (r - i) & \text{simplified} \\ \hline 1 & r & r \\ \hline 2 & r + (r - 1)& 2*r - 1 \\ \hline 3 & r + (r - 1) + (r - 2) & 3*r - 3 \\ \hline 4 & r + (r - 1) + (r - 2) + (r - 3) & 4*r - 6 \\ \hline 5 & r + (r - 1) + (r - 2) + (r - 3) + (r - 4) & 5*r - 10 \\ \hline 6 & r + (r - 1) + (r - 2) + (r - 3) + (r - 4) + (r - 5) & 6*r - 15 \\ \hline \end{array}\]

Clearly, there is some pattern there! We can substitute the factor before the \(r\) by \(y\), but what about the minus term? It seems familiar because we have seen it before. It is exactly the triangle numbers we used to determine the number of points in a subdivided triangle. Thus the expression can be simplified to

\[\sum^{y - 1}_{i=0} (r - i) = y*r - \frac{y(y-1)}{2}.\]

and the index function then becomes simply:

\[idx(i, j) = i + j*r - \frac{j(j-1)}{2}.\]

Here you can see it in action on shadertoy:

in this example the above procedures are used to interpolate colours defined at the points of triangle subdivision. In this way you can have a texture defined on a triangle without specifying texture coordinates.