First off, I am using C#, and am using the June 2007 sdk for DX9 math and matrices to get some quick results.

Skip to the bottom if you only want to read the problem I need help with. As a preface: I have asked several people about this, and they basically just sent me to wikipedia's linear algebra page. Well that doesn't work for me. I can't just read top-level gibberish and immediately understand it. I can, however understand a quick tutorial on calculating a face's normals where they actually express it in a readable programming language such as C/C++.

Now, here's onto the description of my program- I want to write an application that can take pre-defined models and piece them together, kind of like an erector set, Hotwheels tracks, and model railroads, stuff of the like. In non-layman's terms, I want to write a modular world builder from pre-defined pieces, in which while the pieces themselves are pre-defined, the layouts are not. This can have several effects in the end, one such being procedurally-generated levels.

I'm going to wind up repeating a few things over and over here, just to iterate and be sure that my question can be understood.

This is a post I made on another forum on the subject, with a few edits:[s]
[/s][spoiler]

I'm working on a project right now, but i've hit a complete stand-still. This problem has to deal with taking 2 3-dimensional models and putting them together, based on things I call "golden areas". I have defined this golden area to be a quadrilateral (ie rectangle) in which all the vertices are parallel on either the X or Y axis (not going to deal with Z axis. Forget that.)

In C#, my vertices are defined basically as any other (textured) vertice, with an XYZ for normals and an XYZ for position. I do believe that I won't have to do jack to the normals, however I do have to translate the vertices, as well as the normals (but that can be changed whenever I rotate them right?)

We can assume a number of things (or I'll go insane, mark my words) 1. All golden areas that are of certain sides will be marked with a tag. +garea## where ## is a number defining the gareas that can attach to them (all garea00's will only attach to other garea00's).

(the below is the reason I'm posting for help!)
Now, here's the real problem(s) I have to determine how much I have to rotate the whole model. This rotation is called yaw.

Thus I gotta somehow use a method so I can find the orientation of the model, such that whenever it is rotated, I won't have, say, a model intersecting a model (ie a box inside a box).

here's a very, very basic example of what I want to do:

Note that I refer to a golden area as a flat plane with 4 verts, and 2 tris where we can attach other golden areas together to. In our case these are somewhat purple.

Edit: the problem is that there's no real way to find out what side of a triangle is on which side.

I'll probably figure this out on my own eventually but if you have any ideas or links please let me know! (wikipedia on linear algebra makes me want to kill small adorable animals)

Editx2: I found the answer to the figuring out of what side a triangle is, via vectors and normals... in my little program, it too, fits the counter-clockwise rule that all normals have to fit under. [s]
[/s][/quote][/spoiler]
[s]
[/s]

A "Golden Area" is an area in which other pieces can attach to - I also call them limbs/branches interchangeably.

A golden area has 2 faces, each face comprising of 3 vertices.
The golden area for a limb always faces the inside of the limb (closed-world)

-The Problem-
I need help with is taking a flat plane that is in one area with whatever rotation (requiring that this plane is parallel to the Z axis or I'll go nuts) and getting how much I need to rotate that plane via yaw (or around the Z axis, Z being up and down by my preferences) in order such that the two golden areas, when they and their corresponding models are lined up, are facing opposite one another.

[s]how i shot web and make one object face another when object is plane that is parallel to at least 1 axis (Z) C# DX 9 Matrix maths[/s]


Edit: After looking around and realizing that my problem wasn't as cut-and-dried as it sounds like it should be, I turned off the raging. Of course, I will be slowly working on my program on my own and perhaps I will figure out what I need, but I'm leaving it de-crappified and not as likely to get the thread locked.Editx5 Or me banned >.>

Edit 9001: IF this is the wrong forum for this kind of thing, please let me know.

Let me get this straight.

You have two models, M1 and M2.

On M1, there is a known subset of vertices, {u[sub]1[/sub], u[sub]2[/sub], ..., u[sub]n[/sub]}, which I will call M1's "connector vertices."
On M2, there is a known subset of vertices, {v[sub]1[/sub], v[sub]2[/sub], ..., v[sub]n[/sub]}, which I will call M2's "connector vertices."

You want to find a rigid body motion (a translation and rotation) that brings the connector vertices of M2 to those of M1. I.e., you want a rotation matrix R and a translation vector d such that

R v[sub]1[/sub] + d = u[sub]1[/sub]
R v[sub]2[/sub] + d = u[sub]2[/sub]
...
R v[sub]n[/sub] + d = u[sub]n[/sub] .

Is that your problem?

Your unknowns are R and d. You have a bunch of equations. Solve. Here's how:

Define V = [v[sub]2[/sub]-v[sub]1[/sub], ..., v[sub]n[/sub]-v[sub]1[/sub]] and U = [u[sub]2[/sub]-u[sub]1[/sub], ..., u[sub]n-[/sub]u[sub]1[/sub]]. Then what you want for 'R' is,

R V = U

which has the least-squares solution,

R = U V[sup]T[/sup] (V V[sup]T[/sup])[sup]-1[/sup] .

If this matrix does not end up satisfying
det R = 1
and
R[sup]T[/sup] R = I
then it is not a rotation matrix; this tells you that your vertex subsets don't match and the pieces won't join up.

Finally,

d = u[sub]1[/sub] - R v[sub]1[/sub]

or, maybe a little more robustly (you should get the same answer),

d = (1/n)[(u[sub]1[/sub]+...+u[sub]n[/sub]) - R (v[sub]1[/sub]+...+v[sub]n[/sub])] .

Now that you have R and d, your problem is solved.

Also note that you need at least 4 connector vertices for this to work; fewer will not uniquely specify the orientation. For the special case of n=4, you can simplify the rotation matrix computation to,

R = U V[sup]-1[/sup][sup][/sup] .

No code from me for this problem, sorry. But a solution (if I made no mistakes) looks like this:

Assuming that you have a part already fixed in the world. Its local-to-global transformation matrix (a.k.a. model matrix) is named M[sub]1[/sub]. W.r.t. this local co-ordinate system, the 4 vertices of the said quad are given. Unfortunately, the quad by itself is not sufficient. Assuming it is not a square, there are still 4 possible solutions to map another, equally sized quad from the 2nd part onto the 1st one. Even using the normals of the quads isn't sufficient, because there are still 2 possible solutions.

For now, let us assume that you doesn't have quads but local co-ordinate axes. Such axes have a position and an orientation in space. They are described by a standard transformation matrix build from translation and rotation, i.e. (using column vectors)
A := T * R
Let us define such an axis in part 1 given w.r.t. the model transformation of said part 1, so that the global counterpart of that axis is
A[sub]1g[/sub] := M[sub]1[/sub] * A[sub]1l[/sub]
and similarly for the 2nd part
A[sub]2g[/sub] := M[sub]2[/sub] * A[sub]2l[/sub]
[sub]
Lets assume further that local z direction of such an axis is ever defined to point to the inside of the respective part. Then what you want to do is to find a transformation matrix X so that the both axes lie one upon the other in global space, but ... there is one caveat. Although both axes' positions should be identical in global space, their orientations should not, because it is defined that the local z direction ever point into the part. Hence the global z direction of the one axis must point opposite to the global z direction of the other axis. This also enforces that another direction must be opposite, or else we have violated the uniform handedness of the both axes. So lets us say that the y directions should fall coincident, but the x and z should be mirrored. This is expressed by a non-uniform scaling matrix build as
S( -1, 1, -1 )

In summary, we have a formula like
X * M[sub][size="1"]2[/sub] * T[sub][size="1"]2l[/sub] * R[sub][size="1"]2l[/sub][size=2][size=2] * [size=2]S = A[sub][size="1"]1g[/sub]
to solve for X, what means
X = A[sub][size="1"]1g[/sub] * ( M[sub][size="1"]2[/sub] * T[sub][size="1"]2l[/sub] * R[sub][size="1"]2l[/sub][size=2][size=2] * [size=2]S )[sup][size="1"]-1[/sup] [/sub]
[sub] [/sub]
[sub]Now remember that you have a quad instead of the axis. One vertex of that quad may be used for the axis' position, but you have to guarantee that the both vertices (i.e. one of both quads) matches. Then you can use the quad normals as local z direction. However, there is still one direction missed. You can use the difference vectors to the 2 neighbored vertices as up and right vectors (after normalization). However, that again means that you make the order of vertices totally clear. In other words, if you can't work with axes directly, go away from quads and use tris instead, where 1 vertex is marked as origin and the other both vertices are given in a defined order (e.g. CCW).[/sub]
[sub] [/sub]
[sub] [/sub]
[sub]EDIT: Ups, in the meanwhile Emergent has given a complete answer, too. However, it uses another method.[/sub]

Thanks for the help guys!

@ Emergent - I'm not used to the notations of upper-level maths, so when you defined U and V, you're talking about a 4x4 Matrix right?
Also, what does the T in V[sup]T [/sup], R[sup]T [/sup]Signify?

@ haegarr I haven't read through your response all the way yet but it sounds pretty thorough, but I do have one question:

don't have quads but local co-ordinate axes[/quote]

Are you talking about using the center point of the quad as an origin for the coordinate axes?

@ Emergent - I'm not used to the notations of upper-level maths, so when you defined U and V, you're talking about a 4x4 Matrix right?

In the line above, I wrote

V = [v[sub]2[/sub]-v[sub]1[/sub], ..., v[sub]n[/sub]-v[sub]1[/sub]] and U = [u[sub]2[/sub]-u[sub]1[/sub], ..., u[sub]n-[/sub]u[sub]1[/sub]].[/quote]

What this means is that V and U are both 3x(n-1) matrices (where, recall, 'n' was the number of "connector vertices"). Each column is a vector difference. I.e., the first column of V is the vector from the vertex v[sub]1[/sub] to the vertex v[sub]2[/sub]; this is v[sub]2[/sub]-v[sub]1[/sub]. The second column of V is v[sub]3[/sub]-v[sub]1[/sub]; the third is v[sub]4[/sub]-v[sub]1[/sub]; etc.

You should also know that 'R' is a 3x3 rotation matrix, and 'd' is a 3x1 vector. If you're more familiar with 4x4 homogeneous matrices, R is the upper left 3x3 subblock, and d is the upper right subblock; i.e., you can put them together into the 4x4 matrix

[ R d ]
[ 0 1 ]


As for the matrix equation R V = U... Remember we started with the vector equations,

R v[sub]1[/sub] + d = u[sub]1[/sub]
R v[sub]2[/sub] + d = u[sub]2[/sub]
...
R v[sub]n[/sub] + d = u[sub]n[/sub] .

If you subtract the first equation from the rest, you get


R v[sub]2[/sub] - R v[sub]1[/sub] = u[sub]2[/sub] - u[sub]1[/sub]
...
R v[sub]n[/sub] - R v[sub]1[/sub] = u[sub]n[/sub] - u[sub]1[/sub]

or just

R (v[sub]2[/sub] - v[sub]1[/sub]) = u[sub]2[/sub] - u[sub]1[/sub]
...
R (v[sub]n[/sub] - v[sub]1[/sub]) = u[sub]n[/sub] - u[sub]1[/sub] .

The matrix equation

R V = U

is just a compact notation for this system of vector equations.

Also, what does the T in V[sup]T [/sup], R[sup]T [/sup]Signify?

The superscript 'T' means "transpose." You rearrange the elements of a matrix so its columns become rows and vice versa. An mxn matrix becomes an nxm one.

I _think_ I understand it now. If I don't please correct me. Matrix math is rough to get right... Here's some pseudo code I wrote up, in lieu of your method:


n = count of vertices

Matrix V[3][n-1]
Matrix U[3][n-1]
Matrix R[3][3]
Matrix D[1][3]
for i = 1; i < 4; i++
v[3] = quadV.vert - quadV.vert[0];
U[3] = quadU.vert - quadU.vert[0];
end for

R = U * VTransposed * (V * VTrans) ^(-1)

if (RTransposed * R == 1) && (Determinant of R == 1)
{
d = (1/n) * ((sum of quadU vertices) - R * (Sum of all quadV vertices))

}
else
Failure


I _think_ I understand it now. If I don't please correct me.

Yeah, that looks about right. I've made a few edits (below), but I think these fix minor oversights more than conceptual issues.

Matrix math is rough to get right...

Good matrix libraries produce more readable code and can help a lot here, I think. Have you tried the matrix library Eigen? It's my favorite by far.

Anyway, here are the edits:


n = count of vertices

Matrix V[3][n-1]
Matrix U[3][n-1]
Matrix R[3][3]
Matrix D[3][1] // was D[1][3]
for i = 1; i < 4; i++
for j = 0; j < 3; ++j // This inner loop does the vector subtraction (there are 3 scalar elements in each vector). Ideally, this loop would live inside an overloaded subtraction operator for whatever vector class you use.
v[j][i-1] = quadV.vert[j] - quadV.vert[0][j]; // Fixed column indexing. And I'm assuming quadV.vert is a 3x1 vector, whose jth scalar element is quadV.vert[j]
U[j][i-1] = quadU.vert[j] - quadU.vert[0][j];
end for
end for

//--- No edits below here

R = U * VTransposed * (V * VTrans) ^(-1)

if (RTransposed * R == 1) && (Determinant of R == 1)
{
d = (1/n) * ((sum of quadU vertices) - R * (Sum of all quadV vertices))

}
else
Failure


I just realized something about this method. It works in rotating the pieces together but it doesn't do anything about the requirement that each quad must face opposite one another. I guess I can just do a normals test to be sure that they are opposite one another after that....

@ haegarr I haven't read through your response all the way yet but it sounds pretty thorough, but I do have one question:

don't have quads but local co-ordinate axes

Are you talking about using the center point of the quad as an origin for the coordinate axes?
[/quote]

The axes (I mean axes like the red arrow for x direction, green arrow for y direction, and blue arrow for z direction together indicating a co-ordinate system as seen in many DDC packages) are complete handles for itself ... err, besides perhaps the attached key value(s) to determine which axes are allowed to match. They have a definite location and orientation. It would be best (IMHO) if stitching could be done by using them alone. However, there is a way to calculate an axis from at least 3 vertices if the requirements are met that are described in my previous post. The quad's center may be used as origin as well as any of its corner, or any other point computed by interpolation if you wish. However, not the origin but the directions are the more problematic thing. To have matching directions, you need a defined order of vertices (similar to the 1:1 mapping need in Emergent's approach). Because of this, I said that dealing with axes will be "smoother" here.