I am using an old Runescape model format, also used by Thief and Quake. In this format, instead of specifying UV coordinates for each vertex ABC, we specify a second trio of vertices PMN. Those vertices are then used to project UV texture coordinates onto ABC.

Some previous Q&A explains this projection algorithm and how to reverse it.

I have a mesh with UVs that I want to save in this format. To do that, I want to find a trio of vertices PMN for each triangle ABC that reproduce the correct UVs.

These PMN vertices are chosen from the collection of vertices already in my mesh.

I could search every possible ordered triangle in my mesh, but that scales as \$O(n^3)\$ and would be impractical for meshes with high vertex counts.

How can I more efficiently find a PMN triangle that produces my desired UV coordinates on each triangle ABC?


1 Answer 1


First, it's helpful to develop some geometric intuition about how this UV projection algorithm works. We define a 2D UV space using the \$PMN\$ points to form our origin and basis vectors:

  • Point \$P\$ corresponds to (u, v) = (0, 0)
  • Point \$M\$ corresponds to (u, v) = (1, 0)
  • Point \$N\$ corresponds to (u, v) = (0, 1)

Then we project that UV space along the normal perpendicular to the plane of \$\triangle PMN\$, onto \$\triangle ABC\$.

My answer to the earlier question shows how to find a particular choice of \$\triangle PMN\$ in the plane of \$\triangle ABC\$ itself. Let's call them \$P_0\$, \$M_0\$, \$N_0\$. We can use this as the starting point of our search for other \$\triangle PMN\$ candidates.

First, check a small sphere or box around \$P_0\$, \$M_0\$, and \$N_0\$. If you already have a vertex in all three spots (maybe even the vertices of \$\triangle ABC\$ itself) then we can just use those and skip any wider search.

If we don't have a good candidate there, then we can look at each candidate point P that's not in \$\triangle ABC\$'s plane.

For each such candidate \$P\$, take the vector \$P - P_0\$. This forms our projection axis, the normal to the plane of \$\triangle PMN\$. We can use that to find the positions where \$M\$ and \$N\$ would need to be:

$$\begin{align} M = M_0 + t (P - P_0) \quad \text{such that} \quad(M - P) \cdot (P - P_0) &= 0\\ (M_0 + t(P - P_0)) \cdot (P - P_0) &= 0\\ M_0 \cdot (P - P_0) + t (P - P_0)^2 &= 0\\ t (P - P_0)^2 &= M_0 \cdot (P_0 - P)\\ t &= \frac {M_0 \cdot (P_0 - P)}{(P_0 - P)^2} \end{align}$$

...and likewise for \$N\$.

Check a small sphere or box around these points to see if you have a suitable vertex in your mesh. If both check out, then you have a candidate \$\triangle PMN\$.

If you find multiple candidates, you can score them by computing the UVs each candidate triangle assigns to \$A\$, \$B\$, and \$C\$, and summing the squared error. Choose the candidate with the least error.

If you continue this search to check all candidate \$P\$ vertices in your mesh, then it scales as \$O(n)\$, a major improvement over \$O(n^3)\$ checking every possible triangle.

And you can restrict this search to a subset of promising candidates \$P\$ for further savings. Ideally we want to find a \$\triangle PMN\$ that's reasonably close to \$\triangle ABC\$ - otherwise when we do the subtractions we could get catastrophic cancellation that lowers our precision. And we'd like its plane to be roughly parallel to \$\triangle ABC\$, so we don't lose precision to a shallow oblique projection.

With those two constraints in mind, searching a double-cone of restricted height, with its point at \$P_0\$ and its axis perpendicular to the plane containing \$\triangle ABC\$ should cover the best candidates. You can adjust the cone's angle and maximum height to widen your search to less-promising candidates if your initial pool lacks good matches.


You must log in to answer this question.

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