# Find projecting triangle for UV mapping in RuneScape model format

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.

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?

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.