1
$\begingroup$

I have a 3D triangular mesh(vertices, indices, uv coords) that I'm rendering to the screen. Let's assume that the UV mapping is one-to-one. I'm trying to find a way to find the 3D position of the point with UV coordinates equal to (0,0). I searched the internet but I only find answers that I don't find convincing. The solution that I found:

  • Find, in UV space, the triangle that contains (0,0).. let's call it T
  • Calculate barycentric coordinates for (0,0) with respect to T
  • interpolate the 3D positions of T's vertices using barycentric coords to get the result.

this seems wrong to me. Here's why: Let M be the mapping between 3D space and UV space that associates UV coords for every vertex. Let A,B and C be the vertices of T. Let P be the origin of UV space ( P = (0,0) ).

We have P = alpha*A + beta * B + gamma*C (alpha,beta and gamma are the barycentric coords of P with respect to T). We assumed the UV mapping to be one-to-one, so let M° be the inverse of M. We have :

M°(P) = M°(alpha*A + beta * B + gamma*C)

The solution in question assumes that M° is linear.. if that was the case you can have:

M°(P) = alpha*M°(A) + beta * M°(B) + gamma*M°(C)

But that is not the case (correct me if I'm wrong).

So is there a way to find the 3D position of a point with specific UV coords?

Thanks in advance.

$\endgroup$
1
$\begingroup$

I realize that the solution I'm giving further below is basically the one you mentioned in your question. So let's begin by addressing this:

The solution in question assumes that M° is linear.. if that was the case you can have:

M°(P) = alpha*M°(A) + beta * M°(B) + gamma*M°(C)

But that is not the case (correct me if I'm wrong).

The solution in question works directly in UV space. I don't see where it would make any assumptions concerning the nature or even existence of a "mapping from 3D to UV space"!? All it does assume is that UV coordinates vary linearly across each triangle (note: each triangle, not the entire mesh)…

$$ \def\mvec#1{\begin{pmatrix}#1\end{pmatrix}} \def\ivec#1{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)} \def\mmat#1{\begin{bmatrix}#1\end{bmatrix}} \def\vec#1{\mathrm{\mathbf{#1}}} \def\mat#1{\mathrm{\mathbf{#1}}} $$

In general, the $u$ and $v$ coordinates at a point on a triangle's plane given by the affine coordinates $\lambda_1$ and $\lambda_2$ are \begin{align} u &= u_1 + \lambda_1 (u_2 - u_1) + \lambda_2 (u_3 - u_1) \\ v &= v_1 + \lambda_1 (v_2 - v_1) + \lambda_2 (v_3 - v_1) \end{align} where $u_i$, $v_i$ are the $u$, $v$ coordinates at vertex $i$. We can rewrite this as \begin{equation} \mmat{ u_2 - u_1 & u_3 - u_1 \\ v_2 - v_1 & v_3 - v_1 } \cdot \mvec{ \lambda_1 \\ \lambda_2 } = \mvec{ u - u_1 \\ v - v_1 }. \end{equation} Knowing $u_i$ and $v_i$ at each vertex of a given triangle, we can compute \begin{equation} \mat M = \mmat{ u_2 - u_1 & u_3 - u_1 \\ v_2 - v_1 & v_3 - v_1 }. \end{equation} We can then find the affine coordinates corresponding to the point with whatever $u$, $v$ coordinates we want: \begin{equation} \mvec{ \lambda_1 \\ \lambda_2 } = \mat M^{-1} \cdot \mvec{ u - u_1 \\ v - v_1 }. \end{equation} Note that these affine coordinates always exist as long as $\mat M^{-1}$ exists (which makes sense; there will always be exactly one point somewhere in the plane of the triangle where $u$ and $v$ reach whatever value you may be looking for as long as $u$ and $v$ vary independently). However, they will not necessarily fall inside the triangle.

So one way to find the point you're looking for would be to iterate over all triangles of the mesh and, for each triangle, compute $\mat M^{-1}$, and $\lambda_1$ and $\lambda_2$ for $u = 0$ and $v = 0$, and check whether \begin{align} \lambda_1 &\geq 0 & &\land & \lambda_2 &\geq 0 & &\land & \lambda_1 + \lambda_2 &\leq 1. \end{align} If this is the case, you have found a triangle that contains a point at which $u = 0$ and $v = 0$. You can then compute the coordinates of that point as \begin{equation} \vec p = (1 - \lambda_1 - \lambda_2) \vec v_1 + \lambda_1 \vec v_2 + \lambda_2 \vec v_3 \end{equation} where $\vec v_1$, $\vec v_2$, and $\vec v_3$ are the coordinates of the respective triangle vertices.

It may make sense to, for example, use an initial check against a given triangle's bounding rectangle in UV space and/or other methods to quickly rule out triangles that cannot contain the coordinates of interest to speed up the search…

$\endgroup$
  • $\begingroup$ Yeah, that's basically the solution that I was talking about. The specific thing that I don't understand is how can you write p=v1 + lambda_1*v2 + lambda_2*v3 $\endgroup$ – stackmann0 Jan 13 at 20:42
  • $\begingroup$ @stackmann0 that's how u/v coordinates (or any attribute really) are interpolated over a triangle. General barycentric coordinates are not unique. So we turn to affine coordinates instead, which are just a normalized form of barycentric coordinates. Every linear combination of a triangle's vertices where all the coefficients sum to one uniquely identifies a point on the triangle's plane. If we know two of the coefficients, the third one is given by 1 - the rest. If you think about it: a triangle/plane is a 2D entity, so there's inherently only two degrees of freedom to fix on any point on it. $\endgroup$ – Michael Kenzel Jan 13 at 21:12
  • $\begingroup$ Furthermore, any point inside a triangle is uniquely identified by a convex combination of the vertices, which is just a further constrained version of the affine coordinates from before where, in addition to summing to 1, all coordinates are nonnegative. $\endgroup$ – Michael Kenzel Jan 13 at 21:12
  • $\begingroup$ Also, this all makes a lot of sense if you just think about it geometrically: Basically, you start at any of the three vertices, walk some distance along the direction of one edge, and then some distance along the direction of another edge. Any unique combination of distances along two of the edges will take you to a unique point in the triangle's plane. And you'll never be able to leave this plane by just walking along triangle edges. $\endgroup$ – Michael Kenzel Jan 13 at 21:37
  • $\begingroup$ And if you walk both distances in the direction that each edge is pointing, and you never walk all the way to the next vertex along the first edge and you always stop short of the distance remaining to the third edge along the second edge from there, then you can never leave the triangle… $\endgroup$ – Michael Kenzel Jan 13 at 21:38
0
$\begingroup$

Michael Kenzel's answer gives a good general algorithm, but here's a "20% of the effort, 80% of the value" answer. Because $(u,v) \in [0,1]$ space is a square being filled with convex polygons, $(0,0)$ can only be mapped in one of two conditions:

  1. $(0,0)$ is at a vertex; or
  2. Some vertices have negative co-ordinates.

Generally 2 is avoided when unwrapping your mesh unless you're using a texture in wrapped mode, which is quite unusual because it makes the seams on your mesh look bad. It's also ruled out by the condition in your question that "the UV mapping is one-to-one". So most of the time, if $(0,0)$ is present at all, it's at a vertex. That makes your algorithm very simple: just look through your vertices until you find one with those exact texture co-ordinates, and then read out the object-space position of that vertex.

It's actually more common for $(0,0)$ to not be present at all, (a) because you need to take special care with texture filtering when going up to the edge of the texture, and (b) unwrapping a shape into a mesh doesn't usually give you a convenient corner to place there. The examples on this Google Image search are a good illustration: of a few dozen examples on the first few pages, I only found a couple of UV maps where the net touched any of the corners.

$\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.