I need to find a way to parametrise $\mathbb{R^3}$ coordinates relative to a mesh, which is a deformed $UV$ sphere with triangular faces. Every vertex on the mesh has a $UV$ coordinate, and I want to associate every $\mathbb{R^3}-$ point with a coordinate ($u,v$, signed distance). So for instance, points on the mesh would simply be assigned $(u,v,0)$. If a point starts on the mesh at a vertex and then moves outwards by $1$ in the direction of the vertex normal, the new point should be assigned $(u,v,1)$. If a point starts on the mesh inside a face, its normal is a barycentric combination of the surrounding vertex normals, then $(u,v,1)$ is defined as above. Moving inwards gives a negative signed distance. It seems intuitive to me that this formulation assigns a coordinate to every point in $\mathbb{R^3}$, since it is like inflating the mesh until you reach any arbitrary point in $\mathbb{R^3}$. However, I have not been able to find an efficient (or any) way to compute this on an arbitrary $\mathbb{R^3}$ point for a given set of vertex positions. Can anyone see such a way, or is there another approach which is easier altogether?
Parametrising $\mathbb{R^3}$ coordinates using a mesh with barycentric coordinates, and signed distance to the mesh
barycentric-coordinatesgeometrylinear algebra
Related Solutions
Using a 2D problem as an example, you can see that if three lines meet at a point, and you offset the lines by a fixed amount, the resulting lines won't meet at a single point. Each combination of two lines meets at a point.
Here is a visualization with three lines
The three dashed lines meet at a point. I offset the lines by the same amount (shown with circles) to create three solid blue lines. The three solid lines do not meet at a single point.
Something similar is going on in 3D, where the planes do not meet at a single point. It is not a numeric artifact, but a result of the geometry.
So now you have to make a decision on how to handle this situation. Each, three planes defines a vertex, and so you can define capping geometry by the number of vertices you have.
For example, four planes result in two vertices and thus can be capped with a line. An example is shown below of this.
This is as far as I can go with this at this point. You need to choose how to proceed. In my opinion, deriving points, lines, and planes from other points, lines, and planes is done easiest with homogeneous coordinates.
$$ \begin{aligned} \mbox{Point} & = \left( \matrix{ \overrightarrow{\mbox{position}} \\ 1 } \right) & \mbox{Plane} & = \left[ \matrix{ \overrightarrow{\mbox{normal}} \\ -\mbox{distance} } \right] & \mbox{Line} & = \left\{ \matrix{ \overrightarrow{\mbox{direction}} \\ \overrightarrow{\mbox{position}} \times \overrightarrow{\mbox{direction}} } \right\} \end{aligned} $$
The operations between these constructs are very well explained in Foundations of Game Engine Development, Volume 1: Mathematics, page 129, in the section named "Plucker Coordinates".
First, a bit of background so that others also understand what this is about.
We have a non-degenerate triangle (one that has nonzero area, so is not a point or a line) with vertices $\vec{p}_1$, $\vec{p}_2$, and $\vec{p}_3$. Any point $\vec{p}$ within this triangle can be specified via barycentric coordinates $u$, $v$, $w$: $$\begin{aligned} \vec{p} &= u \vec{p}_1 + v \vec{p}_2 + w \vec{p}_3 \\ u + v + w &= 1 \\ 0 &\le u \le 1 \\ 0 &\le v \le 1 \\ 0 &\le w \le 1 \\ \end{aligned}$$ This also implies that $w = 1 - u - v$, i.e. $$\vec{p} = u \vec{p}_1 + v \vec{p}_2 + (1 - u - v) \vec{p}_3$$ Reordering the terms above we can also write it equivalently as $$\vec{p} = \vec{p}_3 + u (\vec{p}_1 - \vec{p}_3) + v (\vec{p}_2 - \vec{p}_3)$$ which is equivalent to a linear (but not necessarily orthogonal) coordinate system in $u$,$v$ with origin at $\vec{p}_3$, $u$ axis $\vec{p}_1-\vec{p}_3$, and $v$ axis $\vec{p}_2-\vec{p}_3$. This, in turn, means that the transformation from barycentric coordinate system $\overline{b} = (u, v)$ (with $0 \le u, v, w \le 1$ and $w = 1 - u - v$) to Euclidean 2D coordinate system can be described as $$\begin{aligned} \vec{p} &= \vec{p}_3 + \mathbf{M} \overline{b} \\ \mathbf{M} &= \left[ \begin{matrix} \vec{p}_1 - \vec{p}_3 & \vec{p}_2 - \vec{p}_3 \end{matrix} \right ] \\ \end{aligned}$$ (Note, $\mathbf{M}$ is a matrix with 2 columns, and as many rows as there are dimensions in the Euclidean coordinate system.)
With this, we have accidentally proven that the transform between Euclidean coordinates and barycentric coordinates is an affine transformation, because it is the composition of two functions: a translation and a linear map.
By definition, affine transformations preserve lines and parallelism.
In two dimensions, the inverse mapping is $$\overline{b} = \mathbf{M}^{-1} \left(\vec{p} - \vec{p}_3\right)$$ where $$\mathbf{M} = \left[\begin{matrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{matrix}\right] \quad \iff \quad \mathbf{M}^{-1} = \left[\begin{matrix} \frac{m_{22}}{m_{11} m_{22} - m_{12} m_{21}} & \frac{- m_{12}}{m_{11} m_{22} - m_{12} m_{21}} \\ \frac{- m_{21}}{m_{11} m_{22} - m_{12} m_{21}} & \frac{m_{11}}{m_{11} m_{22} - m_{12} m_{21}} \end{matrix}\right]$$ In three dimensions, the easiest is to check which component in $(\vec{p}_1 - \vec{p}_3)\times(\vec{p}_2 - \vec{p}_3)$ is the largest in magnitude, and drop that Euclidean coordinate component, and do the above transform using only the two coordinate axes left. It is guaranteed to provide exact correct results, if the triangle is nondegenerate.
If the triangle is degenerate, then the common denominator is zero, $m_{11} m_{22} - m_{12} m_{21} = 0$, and no inverse exists.
There are many different ways to describe lines in barycentric coordinates. Remember, that although there are three coordinates, one of them can always be trivially eliminated ($w = 1 - u - v$), and is usually omitted, especially in computer programs and simulations using barycentric coordinates. (It can be confusing to see barycentric coordinates with only two components, but one only needs to remember that the third is always related to the two via $w = 1 - u - v$, because full barycentric coordinates sum to 1.)
(If we allow full real range in $u$ and $v$ and $w$, with $w = 1 - u - v$, the barycentric coordinates can cover the full plane the non-degenerate triangle is in. This means that if we know the triangle has nonzero area – is not a point or a line –, we can safely use $u$, $v$ coordinates anywhere on the plane, not only inside the triangle. It is then useful to remember that the triangle edges are at $u = 0$, $v = 0$, and $w = 0$ i.e. $u + v = 1$.)
However, affine transforms do not necessarily conserve distance. Even though the distance between the two lines were to stay constant in Euclidean coordinates, just rotating them can change their distance in barycentric coordinates. This is because barycentric coordinates are not orthonormal.
Therefore, I would recommend describing each line in the barycentric coordinates using two points. (This means that if you actually have a point and a direction, you can use the point+direction as the second point, even though it may be outside the triangle.) Then, transform the four points back to Euclidean coordinates. Convert back to point ($\vec{a}_0$ for one line, $\vec{b}_0$ for the other) and direction (difference between the two points, $\vec{a}_\Delta$ for one line, and $\vec{b}_\Delta$ for the other).
The cosine of the angle $\varphi$ between the two lines is $$\cos\varphi = \frac{\left\lvert \vec{a}_\Delta \cdot \vec{b}_\Delta \right\rvert}{\left\lVert\vec{a}_\Delta\right\rVert ~ \left\lVert\vec{b}_\Delta\right\rVert}$$ We take the absolute value of the dot product, because we consider line $\vec{a}_0$,$\vec{a}_\Delta$ the same as $\vec{a}_0$,$\vec{a}_\Delta$. If the cosine is close enough to 1, you can consider them parallel.
When the two lines are parallel, we can solve their distance $d$ by using a temporary variable $t$ so that $\vec{a}_0 + t \vec{a}_\Delta$ is at minimum distance to $\vec{b}_0$. This occurs when their distance reaches an extremum, and the solution is $$t = \frac{\vec{a}_\Delta \cdot \left( \vec{b}_0 - \vec{a}_0 \right) }{\left\lVert \vec{a}_\Delta \right\rVert^2}$$ Then, $$d = \left\lVert \vec{a}_0 + t \vec{a}_\Delta - \vec{b}_0 \right\rVert$$
Depending on how you describe your lines, it is usually possible to combine the above steps, so that fewer actual arithmetic operations are needed as plain reading of the above would indicate. That is, I didn't write the above to be "optimum" in any way; I tried to make it as easy to understand as possible.
I recommend you use a Computer Algebra System such as free Maxima (wxMaxima is the graphical user interfaced one) available for all operating systems to explore the details. In particular, if the direction vectors have unit lengths in Euclidean coordinates, you'll find a lot of the math related to lines becomes much, much simpler. (You'll be able to omit many $\lVert\vec{a}_\Delta\rVert$ and $\lVert\vec{b}_\Delta\rVert$ multipliers and divisors, in particular.)
Best Answer
This sounds like a computer graphics problem.
Suppose $P$ is the point you want to parametrize. Let $T$ be a triangle with vertices $x_1,x_2,x_3$, vertex normals $n_1,n_2,n_3$ and UV coordinates $u_1,u_2,u_3$. You want to find a point $X=ax_1+bx_2+(1-a-b)x_3$ with normal $N=an_1+bn_2+(1-a-b)n_3$ such that $N$ is parallel with the line $XP$. This will be the case if the cross product $C=N\times(P-X)=0$. The vector $C$ will have three components that are 2nd degree functions in $a$ and $b$ so you have to solve for $a$ and $b$. This is essentially solving for the intersection of three conics. Best to find an existing solver, but check out this question and answers: Algorithm: Intersection of two conics
Once you have this information, compute the signed distance $w$. And $(u,v)=au_1+bu_2+(1-a-b)u_3$, so the parametrization of $P$ with respect to $T$ is $(u,v,w)$.
It remains to choose a triangle $T$. Depending on how much the sphere is deformed, there may be more than one $(u,v,w)$ coordinate for a point. But your best bet should be to choose the triangle closest to $P$.