two sets of 3d points

Question

Hi everybody,

I´ve got a question concerning two sets of points in a 3d space. I defined a volume by 40 coordinates in one cartesian coordinate system, in another coordinate system with different (0,0,0) i have s slightly different volume also defined by 40 coordinates. I know the matching pairs of the point sets and I want to measure the difference of each point pair (euclidian distance). Now 1) how can i reference both coordinate systems (same scale) to each other and 2) how would i best calculate the transformation to register both volumes?

Thank you for your help.

Answer 1

If you take three common points that define a triangle, you can determine the rotation transformation that turns one into the other by comparing the angle differences between the surface normals. You get scale from difference in magnitude and once you have those two, translation falls out of it.

Make AOrigin and BOrigin by putting one corner of A and B at the origin. You do this by defining Subtracting A[0] from each of A[0] through A[2] and do the same with B, ie:

AOrigin[1] = A[1] - A[0] // this is vector math - you have to subtract each coordinate individually
AOrigin[2] = A[2] - A[0]
AOrigin[0] = <0 0 0>

BOrigin[1] = B[1] - B[0]
BOrigin[2] = B[2] - B[0]
BOrigin[0] = <0 0 0>

Then you get the unit normals, ANormal and BNormal

ANormal = AOrigin[1] x AOrigin[2]
ANormal = ANormal / |ANormal|
BNormal = BOrigin[1] x BOrigin[2]
BNormal = BNormal / |BNormal|

Then you find the angle between them is:

acos(ANormal . BNormal)

The question is what axis is that rotated about? You find that by taking the cross product of ANormal and BNormal. That now gives you a single rotation about a single axis that will transform A into the the same rotation orientation as B.

The next trick is to get A and B to have the same scale, you do that by taking two points from A and B, finding the length of of each and then getting that ratio. That's the scale.

See where this is going? All of the math for this will be in any decent Calculus book.

Answer 2

I'm not sure I understand the first part of your question, but if you want a transformation that carries one set of points to the other, here is a simple method to understand (though certainly not the most elegant). I will use the point sets you mentioned, A {1(87,159,28) 2(-97,216,15) 3(60,237,9)} and B {1´(96,6,35) 2´(-86,62,23) 3`(71,82,14)}.

I start with A

(87,159,28) (-97,216,15) (60,237,9)

and translate it to bring point 1 to the origin:

(0,0,0) (-184,57,-13) (-27,78,-19)

Then I rotate about the z-axis to bring point 2 to the x-z plane:

(0,0,0) (-192.6,0,-13) (-48.9,66.5,-19)

then about the y-axis to bring point 2 to the z-axis:

(0,0,0) (0,0,193.1) (-15.7,66.5,50.0)

finally about the z-axis again to bring point 3 to the x-z plane:

(0,0,0) (0,0,193.1) (-68.3,0,50.0)

These steps, taken in order, carry things from space A to a new space, call it C. Call this transformation Tca. These steps are reversible-- call the inverse transformation Tac. Now do the same with B to get Tcb and Tbc. The two sets of points will match when they are both in C. Now to carry set A to set B, just apply Tca and then Tbc. To go from set B to set A, apply Tcb then Tac.

Answer 3

Thank you all. Its really amazing to have complete strangers helping you out with problems. Thats the cool thing about the whole net thing. So I´ll try your approaches.

Answer 4

If you know the matching pairs, then this can be solved very tersely using the pseudo-inverse (pinv() in Matlab or numpy).

1. Put the points into two arrays, A & B, of size 3x40.
2. Add a row of 1s to the bottom of each, so they are now size 4x40.
3. The 4x4 matrix that transforms B into A (including any translations) is A * pinv(B).

With 40 points in (mostly) general position, this will even handle arbitrary scales, rotations, or perspective transformation.