CODEWITHSUNDEEP
mathgeometrycomputational-geometry
Agnius Vasiliauskas
Agnius Vasiliauskas

Reputation: 11267

map points between two triangles in 3D space

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)

alt text

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 !!!

Upvotes: 3

Views: 4125

Answers (6)

chain
chain

Reputation: 31

check andand's comments for theory

// Qt code

QMatrix4x4 m;
QMatrix4x4 t1;
QMatrix4x4 t2;

QVector3D v1(0,0,0);
QVector3D v2(0,1,0);
QVector3D v3(1,0,0);
QVector3D v4 = v1 + QVector3D::crossProduct(v2-v1, v3-v1);

QVector3D v1p(0,0,2);
QVector3D v2p(0,3,2);
QVector3D v3p(1,0,1);
QVector3D v4p = v1p + QVector3D::crossProduct(v2p-v1p, v3p-v1p);

t1.setColumn(0, QVector4D(v1, 1));
t1.setColumn(1, QVector4D(v2, 1));
t1.setColumn(2, QVector4D(v3, 1));
t1.setColumn(3, QVector4D(v4, 1));

t2.setColumn(0, QVector4D(v1p, 1));
t2.setColumn(1, QVector4D(v2p, 1));
t2.setColumn(2, QVector4D(v3p, 1));
t2.setColumn(3, QVector4D(v4p, 1));

m = t2 * t1.inverted();

for(float i=0.0; i<2.5; i+=0.05)
{
    QVector4D p(0.2+i,i,0,1);
    QVector4D pp( m * p );

    glBegin(GL_LINE_STRIP);
    glColor4f(1,1,1,1);
    glVertex3d(p.x(), p.y(), p.z());

    glColor4f(1,0,1,1);
    glVertex3d(pp.x(), pp.y(), pp.z());
    glEnd();
}

And a video of this code in action: http://www.youtube.com/watch?v=yOU90pBoyZY

Upvotes: 3

andand
andand

Reputation: 17487

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

Upvotes: 5

tfinniga
tfinniga

Reputation: 6849

I think you might be looking for barycentric coordinates?

Upvotes: 3

Steve Emmerson
Steve Emmerson

Reputation: 7832

You want a matrix transformation T such that T X = X', where X is the matrix whose columns are the co-ordinates of the vertexes of the first triangle and X' is the same for the second triangle. Multiplying each side by the inverse of X yields T = X' X-1.

Upvotes: 1

Colin Fine
Colin Fine

Reputation: 3364

Let

 x = αx1 + βx2 + γx3

Then x' = αx1' + βx2' + γx3' So 

x' = α(x1+V1) + β(x2+V2) + γ(x3+V3)

Upvotes: 0

KeithS
KeithS

Reputation: 71565

Simply add the vectors to each point. Point + Vector == new Point. This is basically the opposite of creating the Vector in the first place: V1 == (x1'-x1, y1'-y1, z1'-z1), so (x1', y1', z1') == (x1+V1x, y1+v1y, z1+V1z).

Upvotes: 0

Related Questions