Warping Coordinates with Matrices

• Download source - 2.9 Kb
• Download demo software - 13.2 Kb
• Download demo source - 24 Kb

Introduction

This article is centered around one function, which takes three points defining one coordinate system, and three defining another, and creates a matrix to transform any point from one system to the other. It's more interesting than it sounds, honest!

Four years ago, I had a problem of translating a set of coordinates from a CAD model of an aircraft to the coordinate system of some large test equipment. As the part would not necessarily be loaded even in the same orientation as it was in the model, I had to translate the coordinates about. I managed to get something together to do the job. It was ugly. Fortunately, the parts were never quite the same at this stage of manufacture as they would be on the aircraft, so the whole exercise was a waste of time.

Two years ago, I had a similar problem. I had to put a CAD overlay on my data on the screen. It had three known points to match up with three specific points on the data. As this was a close problem to the first one, my brain had a head start. This time I could do the job properly, and write a nice reusable class.

A few days ago, a question on the message boards[^] brought it all back to mind. So I've written this article as a thank you to other authors here whose code has helped me so much.

Theory

This section will go in to the math in a little detail. I've tried to pitch it so it's easy on the novice, but not patronizing for the expert. Not an easy task!

I will explain the theory in two dimensions. As with most of the graphics, going to 3D makes the variables bigger, not the ideas.

To define a coordinate system, you need three points in 2D, and four in 3D. You can cheat a bit in 3D and use the cross product of the three other points, but that makes the system less flexible. For simplicity's sake (and because I can't just cut and paste my original code!), I'm going to concentrate on 2D.

Vectors

As most folks know, a Cartesian coordinate (x,y), can be represented as a vector. That in turn can be broken into a group of unit vectors and scalars.

i = X axis unit vector.
j = Y axis unit vector.
k = Z axis unit vector. (But we're not doing 3D today!)

X Axis unit vector.

A simple vector.

The same vector broken into scalars and unit vectors.

A vector broken down into unit vectors and scalars, but written more compactly.

Matrices

Now that we've covered the extreme basics, we can start to get a little more complicated…

We want to make a matrix which will make the X axis unit vector transform to (0.866, 0.5), and make the Y axis unit vector transform to (-0.5, 0.866).

It doesn't take a math genius to solve the equation above.

a = 0.866, b = 0.5, c = -0.5, d = 0.866.

If we fill in the matrix, and group a & b, and c & d together, we get the following:

So we can make up any transformation matrix by knowing what happens to each unit vector. If i transforms to p, and j transforms to q, then we can make the matrix by setting its columns, to p & q.

We can use this matrix to transform any point on the X/Y plane to a new coordinate system. To transform back, just multiply by M^-1.

Transforming from one coordinate system to another.

So far, we dealt with going to / from an arbitrary coordinate system to Cartesian coordinates. Both systems have been transforming about (0,0).

Extending that to be more general needs three points in each coordinate system. An origin, and two Eigen vectors acting as unit-vectors for that system. We can specify the two vectors as the vectors from the origin to two points.

Calling the three points in the first system A, B & C, and the three points in the second system as A', B', and C', where A & A' are acting origins, we can proceed.

To create a matrix to change a vector V to its corresponding V', we would do the following steps:

1. Make a translation T, matrix from -A.
2. Use that matrix on B & C to give us AB and AC.
3. Now we have Eigen vectors, create a matrix E which would transform any point in the "Unit" system to these coordinates.
4. Calculate its inverse, as that's what we really want to do.
5. Do steps (1) and (2) for A', B' and C', giving T' and E'.

Now we can put these steps together to give us a matrix M:

Using the Code

The core classes (imcMatric / imcVector) do not depend on MFC. The only time MFC is used in them is in the operators / constructors using CPoint as a convenience. Remove those and you have classic C++.

You could use the vector and matrix classes that come with DirectX, as I started to do. But I found I was having precision problems with a sizable data set, and lots of scaling. Instead, I rolled my own matrix / vector classes. These do nothing radical that other libraries don't (including matrix classes here on CodeProject). But they are adequate to the needs of this project. As I've rolled my own classes, the only dependence they have on MFC (as mentioned above) is on CPoint. The demo project uses MFC heavily, but that is only a quick project.

The important member function for this article is the imcMatrix::WarpVectors method. This sets the matrix up from two sets of three vectors, three from each coordinate system.

struct imcVector
{
    double x, y;
    // Bunch of operators to make life easy.
    …
}

// Handy grouping of three vectors. Make its harder to miss one than an array!
struct imcVectorTriple
{
    imcVectorTriple (imcVector v1, imcVector v2, imcVector v3);
    imcVectorTriple (CPoint p1, CPoint p2, CPoint p3);
    imcVectorTriple ();

    imcVector v [3];

    void operator+= (const imcVector &v); // Useful for subtracting "origin".
    void operator-= (const imcVector &v);
};

class imcMatrix
{
public:
    …
    BOOL    WarpVectors (imcVectorTriple coordinatesystemFrom, 
                          imcVectorTriple coordinatesystemTo);
    …
};

If you have three coordinates in one system (p1, p2, p3) and three in another (q1, q2, q3), you can make a matrix to transform from P to Q.

imcVectorTriple vtFrom (p1, p2, p3), vtTo (q1, q2, q3);

imcMatrix M;
M.WarpVectors (vtFrom, vtTo);

Q = M * P;

And back again…

imcMatric M_Back;

M_Back.WarpVectors (vtTo, vtFrom);

P = M_Back * Q;

Computing the matrix is expensive, so you wouldn't want to do it in a loop. But using it to transform a vector is very efficient. Just a bunch of multiply / accumulates. What a processor does best!

There are most of the other matrix and vector functions you would think of. They are missing some functions, e.g., cross product, but they are not necessary for this job. Feel free to add any I've missed and email them. I'll be happy to add them for completeness.

Demo Application

This is a quick scribble like application I put together to demonstrate and prove the classes.

Drag the mouse to add a stroke. To move anchor points, select the view and press keys 1, 2, or 3. You can create a new window (Window | New) to see the same strokes in another coordinate system.

Acknowledgements:

One of the biggest problems I had was doing the equations! Fortunately, tbw's [^] Formula Editor [^] came to the rescue.

Also, Keith Rule's [^] CMemDC [^] class came to the rescue as it does in almost every drawing routine I write. Flicker is baaaaad.

History

20 Jan 2005 - Initial release.