I need to translate 3d points relative to a triangle as if the triangle was somewhere else

Question

I posted this on twitter a while ago but seeing how none of my followers appears to be a math/programming genius, I'll try my luck here as well. I got here because I found this which might contain part of my solution.

I described my problem in the following pdf document, containing a picture of what I'm trying to achieve.

To give some more details, I divided the pentagon's of a dodecahedron (12 pentagons) into triangles (5/pentagon, 60 triangles in total), then collected a set of data points relative to each of these triangles.

The idea is to generate terrain meshes for each individual triangle. To do so, the data must be represented flat, in a 32K x 32K square (idTech4 Megatexture)

I have vaguely heard of transformation matrices, which when set up properly, could do the trick of passing all the data points trough them to have them show up in the right place.

I looked at this source code here but I don't understand how I'm supposed to get the points in and/or out of there, not to mention how to do the setup so I can present each point in turn and get the result point back.

I got as fas as identifying the point that belongs in the back right corner. All my 3D points are originally stored in latitude / longitude pairs. I retrieve the 3D vectors this way:

coord getcoord(point* p) 
{
    coord c;
    c.x=cos(p->lat*pi/180.l) * cos(p->lon*pi/180.l);
    c.y=cos(p->lat*pi/180.l) * sin(p->lon*pi/180.l);
    c.z=sin(p->lat*pi/180.l);
    return c;
};

My thought is that if I can find the center of my triangle, and discover how to offset my angles so the vector from the center of my sphere to the middle of the triangle moves to 90N then my points would already be in the right plane if I rotated them all along the same angles. If I then convert them all to 3d and subtracti the radius from y, they'll be at the correct y position as well.

Then all I'd need to do is the rotation, the scaling, and the moving to the final position.

There are several kinds of 'centers' for a triangle, I think the one I need is the one that is equidistant to the corners of the triangle (Circumcenter?)

But then there might be an easier approach to the whole problem so while I continue my own research, perhaps some of you can help pointing me in the right direction.

It appears as if some sample data is in order, here are a few of these triangles in obj file format:

v 0.000000 0.000000 3396.000000
v 2061.582356 0.000000 2698.646733
v 637.063983 1960.681333 2698.646733
f 1 2 3

And another:

v -938.631230 2888.810129 1518.737455
v 637.063983 1960.681333 2698.646733
v 1030.791271 3172.449325 637.064076
f 1 2 3

You will notice that each point is at a distance of 3396 from 0,0,0 I mentioned 'on the sphere' meaning that the face away from the center of the sphere is the face that needs to become the 'top' when translated into the square.

Theoretically all these triangles should in fact have identical sizes, but due to rounding errors in the math that generated them, this might not be entirely true.

If I'm not mistaken I already took measures to ensure that the first point you see here is always the one opposite the longest border, so it's the one that should go in the far left corner (testing the above 2 samples confirms this, but I'm measuring anyway just to be sure) Both legs leading away from this point should theoretically have the same length as well, but again rounding errors might slightly offset that.

If I've done it correctly then the longer side is 1,113587 times longer than the 2 shorter sides. Assuming those are identical, then doing some goal seeking in excel, I can deduct that the final points, assuming I was just translating this triangle, should look like:

v 16384.000000 0.000000 16384.000000
v -16384.000000 0.000000 9916.165306
v 9916.165306 0.000000 -16384.000000
f 1 2 3

So I need to setup the matrix to do this transformation, preferably using the 4x4 matrix as explained below.

Answer 1

I would recommend using transform matrices. The 3d transform matrix is a 4x4 data structure which describes a translation and rotation (and possibly a scale). Once you have a matrix you can transform a point like so

 result.x = (tmp->pt.x * m->element[0][0]) + 
            (tmp->pt.y * m->element[1][0]) + 
            (tmp->pt.z * m->element[2][0]) + 
            m->element[3][0];

 result.y = (tmp->pt.x * m->element[0][1]) + 
            (tmp->pt.y * m->element[1][1]) + 
            (tmp->pt.z * m->element[2][1]) + 
            m->element[3][1];
 result.z = (tmp->pt.x * m->element[0][2]) + 
            (tmp->pt.y * m->element[1][2]) + 
            (tmp->pt.z * m->element[2][2]) + 
            m->element[3][2];
 int w = (tmp->pt.x * m->element[0][3]) + (tmp->pt.y * m->element[1][3])
      + (tmp->pt.z * m->element[2][3]) + m->element[3][3];
 if (w!=0 || w!=1)
 result.x/=w; result.y/=w; result.z/=w;

This will transform the 3D point pt by the matrix m. If you now a little matrix math you'll see i'm just multiplying my origin point as a vector against the matrix (and doing a little normalization if it is a skew matrix.) Matrices can be multiplied together to form complicated transformations so they are very useful.

For details on making matrices suggest reading this link. http://en.wikipedia.org/wiki/Transformation_matrix