0
\$\begingroup\$

I found this algorithm in some old codebase, it takes two triangles from a mesh ABC and PMN, where ABC is the triangle that will be rendered and PMN is an extra triangle that is only used to generate the UV coordinate for ABC and is not rendered.

I am trying to create a reverse algorithm to calculate the PMN triangle positions based on UV coordinates of a triangle and ABC positions of the same triangle.

Vector3f A = /* stored in mesh data */;
Vector3f B = /* stored in mesh data */;
Vector3f C = /* stored in mesh data */;

Vector3f P = /* stored in mesh data */;
Vector3f M = /* stored in mesh data */;
Vector3f N = /* stored in mesh data */;

Vector3f PM = M.sub(P, new Vector3f());
Vector3f PN = N.sub(P, new Vector3f());
Vector3f PA = A.sub(P, new Vector3f());
Vector3f PB = B.sub(P, new Vector3f());
Vector3f PC = C.sub(P, new Vector3f());

Vector3f PMxPN = PM.cross(PN, new Vector3f());

// Calculate the U coordinates    
Vector3f U = PN.cross(PMxPN, new Vector3f());
float Mu = 1.0F / U.dot(PM);
float Ua = U.dot(PA) * Mu; /* 1st U coordinate (for vertex A) */
float Ub = U.dot(PB) * Mu; /* 2nd U coordinate (for vertex B) */
float Uc = U.dot(PC) * Mu; /* 3rd U coordinate (for vertex C) */

// Calculate the V coordinates
Vector3f V = PM.cross(PMxPN, new Vector3f());
float Mv = 1 / V.dot(PN);
float Va = V.dot(PA) * Mv; /* 1st V coordinate (for vertex A) */
float Vb = V.dot(PB) * Mv; /* 2nd V coordinate (for vertex B) */
float Vc = V.dot(PC) * Mv; /* 3rd V coordinate (for vertex C) */

Formatted LaTex represention of the same algorithm: $$ \vec{PM} = \vec{M} - \vec{P} \\ \vec{PN} = \vec{N} - \vec{P} \\ \vec{PA} = \vec{A} - \vec{P} \\ \vec{PB} = \vec{B} - \vec{P} \\ \vec{PC} = \vec{C} - \vec{P} \\ \vec{PMPN} = \vec{PM} \times \vec{PN} \\ $$

$$ \vec{U} = \vec{PN} \times\vec{PMPN} \\ Mu = \frac{1} {\vec{U} \cdot \vec{PM}} \\ Ua = \vec{U} \cdot \vec{PA} \times Mu \\ Ub = \vec{U} \cdot \vec{PB} \times Mu \\ Uc = \vec{U} \cdot \vec{PC} \times Mu \\ $$

$$ \vec{V} = \vec{PM} \times\vec{PMPN} \\ Mv = \frac{1} {\vec{V} \cdot \vec{PN}} \\ Va = \vec{V} \cdot \vec{PA} \times Mv \\ Vb = \vec{V} \cdot \vec{PB} \times Mv \\ Vc = \vec{V} \cdot \vec{PC} \times Mv \\ $$

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

Because this is a projection from 3D down to 2D, it's not invertible. So we can't recover the triangle \$\triangle PMN\$ that was used to create the original projection. But we can find a member of a family of triangles that fits that bill.

For simplicity, let's choose the member of that family that lies in the same plane as our mesh triangle \$\triangle ABC\$. That means our points \$PMN\$ are linear combinations of the points \$ABC\$. That is, they'll be of the form:

$$A + s (B - A) + t (C - A)$$

...for some real numbers \$s\$ and \$t\$. Taking a look at the UV coordinates of our points in \$\triangle ABC\$, we can define:

$$u_1 = U_b - U_a \quad u_2 = U_c - U_a\\ v_1 = V_b - V_a \quad v_2 = V_c - V_a$$

And with that, we can take any point \$(s, t)\$ and get its uv coordinates under this mapping with a matrix multiplication:

$$\begin{bmatrix}u\\v\end{bmatrix} = \begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix} \begin{bmatrix}s\\t\end{bmatrix} + \begin{bmatrix}U_a\\V_a\end{bmatrix}$$

You can verify that for the points A, B, and C, this gives exactly the UVs we expect, and so it gives correct UVs for any linear combination of them too. And since we decided to place our \$\triangle PMN\$ in the same plane, this formula also gives the corresponding UVs for \$P\$, \$M\$, and \$N\$.

Now we can work backwards from their 2D UV coordinates to find their 3D positions on the plane.

By construction, the plane projection mapping algorithm always assigns \$P\$ the coordinates \$(u, v) = (0, 0)\$ (we always subtract \$P\$ from the input point, getting zero if \$P\$ was the input, and the subsequent multiplications keep it at zero)

Now we'll solve...

$$\begin{align} \begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix} \begin{bmatrix}s_P\\t_P\end{bmatrix} + \begin{bmatrix}U_a\\V_a\end{bmatrix} &=\begin{bmatrix}0\\0\end{bmatrix}\\ \begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix} \begin{bmatrix}s_P\\t_P\end{bmatrix} &=\begin{bmatrix}-U_a\\-V_a\end{bmatrix}\\ \begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix}^{-1} \begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix} \begin{bmatrix}s_P\\t_P\end{bmatrix} &=\begin{bmatrix}u_1 & u_2\\v_1 & v_2\end{bmatrix}^{-1}\begin{bmatrix}-U_a\\-V_a\end{bmatrix}\\ \begin{bmatrix}s_P\\t_P\end{bmatrix} &=\frac 1 {u_1v_2 - u_2v_1} \begin{bmatrix}v_2 & -u_2\\-v_1 & u_1\end{bmatrix} \begin{bmatrix}-U_a\\-V_a\end{bmatrix} \end{align}$$

Now we have

$$P = A + s_P(B-A) + t_P(C-A)$$

There's a similar trick for finding \$M\$ and \$N\$.

First, note that we get our \$u\$ coordinate for a point \$X\$ as \$U_X = \frac {\vec U \cdot (X - P)} {\vec U \cdot (M - P)}\$. So if our input point was \$M\$ itself, then this can only give us the number one!

The v coordinate is a bit harder to see, but note that \$\vec V = (M - P) \times \vec {PMPN}\$. So it must be orthogonal to \$(M - P)\$, so the dot product \$\vec V \cdot (M - P)\$ must be zero.

The same argument applies in turn to \$N\$, and so we get a clearer picture of what these three points signify: \$P\$, \$M\$, and \$N\$ define three corners of our UV-mapping square:

$$P \rightarrow (0, 0)\\ M \rightarrow (1, 0)\\ N \rightarrow (0, 1)$$

So, we can substitute those UV values, and solve for \$M\$ and \$N\$ in exactly the same way:

$$\begin{bmatrix}s_M\\t_M\end{bmatrix} =\frac 1 {u_1v_2 - u_2v_1} \begin{bmatrix}v_2 & -u_2\\-v_1 & u_1\end{bmatrix} \begin{bmatrix}1 -U_a\\-V_a\end{bmatrix}\\ M = A + s_M(B - A) + t_M (C-A)$$

$$\begin{bmatrix}s_N\\t_N\end{bmatrix} =\frac 1 {u_1v_2 - u_2v_1} \begin{bmatrix}v_2 & -u_2\\-v_1 & u_1\end{bmatrix} \begin{bmatrix}-U_a\\1 - V_a\end{bmatrix}\\ N = A + s_N(B - A) + t_N(C-A)$$

In my tests with random triangles, using single-precision floats throughout, this correctly reproduces the UV mapping to within 0.001, which I'd attribute to rounding errors along the way. If you have more sensible triangles, and use double-precision intermediates, you could probably reduce the deviation even further.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.