5
\$\begingroup\$

Say that in a 2D space I have the barycentric coordinates \$B=(B_x, B_y, B_z)\$ of point \$P\$ relative to triangle \$T\$. I now need to calculate the barycentric coordinates \$B'\$ of \$P\$ relative to triangle \$T'\$, where \$T\$ and \$T'\$ share an edge - and thus, two of the three vertices.

Can I somehow simplify the calculation of these new barycentric coordinates given the fact that these two triangles share an edge?

\$\endgroup\$
0

3 Answers 3

0
\$\begingroup\$

In the general case, there is little performance improvement above calculating both triangles independently.

The distance calculation between the shared points gives room for improvement via caching. If an edge is axis aligned the distance formula becomes a simple subtraction.

General caching would cost more memory and CPU than a single shared edge.

Caching in the case of a triangle fan, where a single distance would be saved for the next edge calculation would be a tremendous improvement.

A different view leading to the same outcome

Transform the coordinates to axis align the common edge as the X axis and the center of the common points as the new origin. Calling the transformed \$T\$ third point as \$C\$ and the other transformed \$T'\$ point as \$D\$ and \$B\$ as \$B'\$.

The relationship of the barycenter formed by \$C\$ and the one from \$D\$ is the square root of the ratio of the squared distances \$C\$ and \$D\$. Project, adjusting for sign, the ratio onto \$B'\$ point in the transformed space creating \$E\$.

Invert the original transformation and apply to \$E\$ to get the new point \$B'\$.

This is no faster than calculating the second center, unless transformations are free (GPU)


The main issue is the third point distances must be calculated from the other two points.

Giving a mostly unrelated point \$B\$ does not give more information to the equations required.

\$\endgroup\$
0
\$\begingroup\$

First, let's see what we can do with no pre-computation.

We have a point \$P\$ and a triangle \$\Delta QRS\$, adjoined to another triangle \$\Delta QRS^\prime\$ that shares vertices \$Q\$ and \$R\$, but its third vertex is \$S^\prime\$.

Triangles QRS and QRS' with point P

(Here I've drawn it as though \$P\$ is inside \$\Delta QRS\$, but all of the following math works out the same if it's inside \$\Delta QRS^\prime\$ instead, or outside of both triangles. We will assume though that neither triangle is degenerate).

The barycentric weights \$B\$ of point \$P\$ relative to \$\Delta QRS\$ can then be computed from the areas of the coloured sub-triangles in the diagram above:

$$ B_Q = \frac {A_{\Delta PRS}} {A_{\Delta QRS}}, B_R = \frac {A_{\Delta PSQ}} {A_{\Delta QRS}}, B_S = \frac {A_{\Delta PQR}} {A_{\Delta QRS}} = 1 - B_Q - B_R\\ $$

So we had to compute 3 triangle areas and 2 divisions (or 1 reciprocal), since we can get the last weight with simple subtraction once we know the other two.

We'll hold onto the area \$A_{\Delta QRS}\$ that we just had to compute anyway, and use it to accelerate the computation of the barycentric weights of \$P\$ relative to \$\Delta QRS^\prime\$, \$B^\prime\$:

$$\begin{align} {B^\prime}_{S^\prime} &= \frac {A_{\Delta PQR}} {\color{blue} {A_{\Delta QRS^\prime}}} = \frac {A_{\Delta PQR}} {A_{\Delta QRS}} \cdot \frac {A_{\Delta QRS}} {\color{blue} {A_{\Delta QRS^\prime}}} = B_S \cdot \frac {A_{\Delta QRS}} {\color{blue} {A_{\Delta QRS^\prime}}}\\ {B^\prime}_Q &= \frac {\color{blue} {A_{\Delta PRS^\prime}}} {A_{\Delta QRS^\prime}} \\ {B^\prime}_R &= 1 - {B^\prime}_Q - {B^\prime}_{S^\prime} \end{align}$$

I've coloured in blue above the terms we have to newly-calculate because we don't already know them from a previous step. You can see that's only 2 new triangle areas to calculate, down from 3 for doing the calculation from scratch.

We can also cache some of the difference vectors like \$P - Q\$ and \$P - R\$ that are used in computing multiple of these areas to get slightly more savings.

But we can get even greater savings if we're allowed to do a little pre-computation on these triangles...


If your triangles are fixed, or you need to do many rebasing operations between changes to your triangles, we can save some extra metadata for each edge we want to re-base across to accelerate this.

The idea is that for each triangle pair \$(T, T^\prime)\$ you want to rebase between, you compute and store the barycentric coordinates of the unshared vertex of \$T\$ with respect to \$T'\$. Let's call this point \$C = (C_x, C_y, C_z)\$.

Now you can compute the barycentric coordinates \$B^\prime\$ of an arbitrary point with respect to \$T'\$ using the barycentric coordinates \$B\$ of that point with respect to \$T\$:

$$\begin{align} B_x^\prime &= B_x + C_x B_z\\ B_y^\prime &= B_y + C_y B_z\\ B_z^\prime &= C_z B_z\\ \end{align}$$

(Here I assume \$B_x\$ and \$B_y\$ are the barycentric weights for the vertices on the shared edge, and \$B_z\$ is the weight for the lone unshared vertex. You can swizzle this as needed to handle other arrangements)

This is a much more substantial cost savings: one scalar-vector multiply and one vector addition, with no full area computations and no divisions.

To go the opposite way (to rebase from \$T^\prime\$ back to the original \$T\$), we just replace our coefficients (Cx, Cy, Cz) with \$\left(\frac {-C_x} {C_z}, \frac {-C_y} {C_z}, \frac 1 {C_z} \right)\$. Since these are easily computed from the \$T \rightarrow T^\prime\$ coefficients for the cost of one reciprocal and two multiplications, we can store just one of these triplets and still get meaningful savings.

This is about the amount of data we commonly store for (just one of either) normals, tangents, texture coordinates, or vertex colours when working with 3D meshes, it's not an unreasonable amount of pre-computation and storage/lookup — especially if you plan to do this rebasing operation very frequently.

The downside of course is that we had to compute one set of barycentric weights \$C\$ first, to get the coefficients to use, so it's only a savings if you can do that once in advance and then re-use the result multiple times.


How this is derived:

We can think of the conversion from cartesian to barycentric coordinates as linear transformation that maps \$(x, y, 1)\$ to \$(B_x, B_y, B_z)\$, such that the three vertices of the original triangle get mapped to \$(1, 0, 0), (0, 1, 0), and (0, 0, 1)\$, respectively.

This linear transformation maps the entire plane \$(x, y, 1)\$ to the plane \$B_x + B_y + B_z = 1\$. Importantly, that includes the unshared vertices of any adjacent triangles. Let's select any one of them and say it gets mapped to barycentric coordinates \$P = (P_x, P_y, P_z)\$.

To convert this space of barycentric coordinates relative to \$T\$ to be in terms of the adjacent triangle with the unshared vertex at \$P\$, all we need to do is compute a linear transformation that maps the shared vertices (let's assume, without loss of generality, that those are the ones with barycentric coordinates (1, 0, 0) and (0, 1, 0)) to themselves, and maps the new triangle's unshared vertex \$P\$ to (0, 0, 1).

This will, in general, be some reflection and scale across the XY plane, combined with a shear parallel to that plane. That is, barycentric coordinates already on the XY plane keep their current values, and any shift in the coordinates will be proportional to the Z coordinate of the point we're transforming.

We can find the matrix that expresses this rebasing transformation like so:

$$ \begin{bmatrix} 1 & 0 & Z_x\\ 0 & 1 & Z_y\\ 0 & 0 & Z_z \end{bmatrix} \begin{bmatrix} P_x \\ P_y \\ P_z \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} $$

Solving this gives us:

$$\begin{align} Z_x &= \frac {-P_x} {P_z} \\ Z_y &= \frac {-P_y} {P_z} \\ Z_z &= \frac 1 {P_z} \\ \end{align}$$

So we can use this matrix to re-base barycentric coordinates from one triangle to the other.

Inverting this matrix will give us the transformation that "un-rebases", going from the destination triangle back to the original triangle. The third column of that matrix will be:

$$\begin{align} Z_x &= P_x \\ Z_y &= P_y \\ Z_z &= P_z \\ \end{align}$$

Since this form is neater, I chose to use that one as the "primary rebasing direction" in the answer above, and use the fractional version only when we need to go "backwards".


Note that either approach we take, we'll accumulate some rounding errors with each operation. So if we do multiple rebasing hops to transform a barycentric coordinate from triangle A to B to C to D, the error in each output feeds back as error into the next input, snowballing. So you will still want to compute a barycentric weight from scratch every \$n\$ hops, to keep this error from compounding to a damaging degree.

\$\endgroup\$
-1
\$\begingroup\$

If \$T\$ and \$T'\$ share an edge with vertices \$A\$ and \$B\$, and the barycentric coordinates of \$P\$ relative to \$T\$ are \$B = (B_x, B_y, B_z)\$, then the barycentric coordinates \$B' = (B'_x, B'_y, B'_z)\$ relative to \$T'\$ are:

$$ \begin{align} B'_x &= B_x \\ B'_y &= B_y \\ B'_z &= 1 - B_x - B_y \\ \end{align} $$

\$\endgroup\$
1
  • 2
    \$\begingroup\$ This is plainly false. Since Bx + By + Bz = 1 by construction, you've said that the barycentric coordinates relative to the new triangle must always be identical to the coordinates relative to the original, regardless of the location of the unshared vertex. That cannot be the case except when the second triangle is really just the first triangle again, unchanged. A correct formula must use information about T' somewhere. \$\endgroup\$
    – DMGregory
    Commented Nov 17 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .