map points between two triangles in 3D space

Question

EDIT

I don't know is it important, but destination triangle angles may be different than these of source. Does that fact makes transformation non-affine ? (i'm not sure)

I have two triangles in 3D space. Given that i know (x,y,z) of point in first triangle and i know vectors V1,V2,V3. I need to find point (x',y',z'). What transformation i should do to point (x,y,z) with vectors V1,V2,V3 to get that transformed point in the second triangle ?

Thanks for help !!!

Answer 1

The short answer is that this is more complicated than it at first appears, and the nature of the constraints you are placing on the problem require some more advanced techniques than you might think.

So, by way of an explanation, I'm going to change your notation a bit. Consider 3 pairs of vectors (these correspond to your the vertices of the two triangles in your problem):

u = <u0, u1, u2, 1>
u' = <u0', u1', u2', 1>

v = <v0, v1, v2, 1>
v' = <v0', v1', v2', 1>

w = <w0, w1, w2, 1>
w' = <w0', w1', w2', 1>

Ordinarily, your problem would be solved through the identification of the linear transformation of the form:

    |a0,0  a0,1  a0,2  a0,3|
A = |a1,0  a1,1  a1,2  a1,3|
    |a2,0  a2,1  a2,2  a2,3|
    |0     0     0     1   |

such that:

Au = u'
Av = v'
Aw = w'

This formulation is needed because the transformation seems to be a 3-D affine transformation, not a 3-D linear transformation. If it were a linear transformation, any triangle containing the origin would necessarily map to another triangle containing the origin. Extending to a 4-D space allows 4-D linear transformation to be used to perform 3-D affine transformation.

That said, the first thing to notice is that this problem is underconstrained (9 equations with 12 unknowns); there is no unique solution. There are in fact infinitely many. However, your problem is somewhat more constrained than this, so there's some hope. You have the additional constraints given a vector

p = <p0, p1, p2, 1>

find

Ap = p' = <p0', p1', p2', 1>

such that (using your definition vectors a, b, and c)

|u - p|   |u' - p'|
------- = ---------
|u - a|   |u' - Aa|

|v - p|   |v' - p'|
------- = ---------
|v - b|   |v' - Ab|

|w - p|   |w' - p'|
------- = ---------
|w - c|   |w' - Ac|

While this presents an additional constraint on your problem, it changes it from being one that could easily solved using linear methods to one that requires Convex Programming to find a unique solution.

That said, here are some possible aproaches:

• Go ahead and use convex programming to solve the problem. While more difficult to solve than linear problems, they are not really all that hard to solve.
• Revert to the 2D case, rather than the 3D case. This can be done without resorting to the non-linear constraints those distance measurements impose.
• Select a fourth point and instead of working on triangles, work on tetrahedra instead. This again removes the non-linearity from the problem.

UPDATE: I've given this some thought and I see a way to generate the correct affine transformation without using convex programming. It can be done by generating a fourth vertex for each of the triangles, called y and y':

y = u + (v-u)×(w-u)
y' = u' + (v'-u')×(w'-u')

where × is the 3-D cross product of the two vectors (i.e. omit the final 1 in each vector; but remember to append the 1 onto y and y' once you have them calculated). From there, you can apply the standard technique of creating matrices M and M' from column vectors:

 M = <u, v, w, y>
 M' = <u', v', w', y'>

and use the method Steve Emmerson suggested (in 4-D rather than 3-D):

AM = M'
AMM-1 = M'M-1
A = M'M-1