Sign in to follow this  

Triangulation...

This topic is 2632 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I googled a few articles, but none of them are working with the same elements I am (2x 3d rays and 2x 3d positions), so I thought I would just ask here. I am sure one of you math wizards can answer this without even thinking!

I am trying to triangulate the position of point A. From point A I have two normalized 3d rays pointing to two points B and C. I know the 3d position of points B and C (but not A obviously). Given this information, can anyone provide a algorithm that calculates the 3d position for point A?

Thanks in advance!

Share this post


Link to post
Share on other sites
By "normalized rays" do you just mean normals? In that case you can construct two rays that start at B and C and extend in the reverse direction of the normals, and compute their intersection. I think that should give A's position.

Share this post


Link to post
Share on other sites
Let me get this right.

You have two points, b and c, and two unit vectors -- call them ub and uc -- which point from some unknown point a to b and c respectively, and you want to find a. That's the problem?

So, for some scalar t,

a + ub t = b
and
a + uc t = c

This is 2x3=6 scalar equations, and 4 scalar unknowns (a is 3; t is 1). So, in general, you can't expect there to always be a solution; the equations can easily be inconsistent. Just imagine, for instance, if b and c were both sitting on the floor, and ub pointed up but uc pointed down.

Instead, the best we can do is get a least squares solution. Basically, in general we expect that our answer will contradict the equations somewhat, but we'll pick the answer that contradicts the equations the least.

First, let me write out the equations in (block) matrix form as


[ I ub ] [ a ] [ b ]
[ ] [ ] = [ ]
[ I uc ] [ t ] [ c ]
6x4 4x1 6x1


or just

A x = B

with A and B defined by the above. Multiply both sides by A^T to get

A^T A x = A^T B ;

(this projects the equations onto a lower-dimensional subspace; we're saying that any residual has to lie outside the row space of A. A full derivation of why this is the least squares solution is outside the scope of this post, but suffice to say that it follows simply from the Pythagorean Theorem)

now A^T A is a 4x4 matrix which is presumably invertible, so we can now write

x = (A^T A)^(-1) A^T B

which is the least squares solution.

Share this post


Link to post
Share on other sites
Quote:

You have two points, b and c, and two unit vectors -- call them ub and uc -- which point from some unknown point a to b and c respectively, and you want to find a. That's the problem?


Exactly. You could also say I have two points, and two unit vectors that point FROM b/c TO a.

Hrmm but youre saying you cant solve this problem with a simple line intersection equation? I came across this...

http://mathforum.org/library/drmath/view/63719.html

I havent had time to try and implement it yet... I guess I dont care HOW its done just so long as it works... if anyone could whip up a working c/c++ example function it would be greatly appreciated.

Share this post


Link to post
Share on other sites
I found another article and took a stab at implementing it...

http://mathforum.org/library/drmath/view/63719.html

I am using his second method (setting x's and y's equal). Please look it over and tell me how badly I messed it up.

So given two points (p1/p2) and two normalized vectors (v1/v2) pointing to point A (the mystery point we are trying to find), this is the function I have thus far...


p1 = Ogre::Vector3(0,0,0); v1 = Ogre::Vector3(1,0,0);
p2 = Ogre::Vector3(1,1,0); v2 = Ogre::Vector3(0,-1,0);

// Attempt to find magnitude m1/m2 by setting the x and y values equal
// p1.x + (v1.x*m1) = p2.x + (v2.x*m2)
// p1.y + (v1.y*m1) = p2.y + (v2.y*m2)

// Which reduces to...
// (v1.x*m1) - (v2.x*m2) = p2.x - p1.x
// (v1.y*m1) - (v2.y*m2) = p2.y - p1.y

// So...
float xDif = p2.x - p1.x;
float yDif = p2.y - p1.y;

// This next part I dont quite understand... what does multiplying the
// equation by xDif/yDif accomplish? And how are we able to ignore p2/v2?
// xDif*(v1.x*m1) - _???_ = xDif*xDif
// yDif*(v1.y*m1) - _???_ = yDif*yDif

// Add em up, and use (xDif*xDif)+(yDif*yDif) to solve for m1...
float m1 = ((xDif*xDif)+(yDif*yDif)) / ((xDif*v1.x) + (yDif*v1.y));

// How to calculate m2 now? Although it should not be needed right?

// The intersection is...
return p1 + (v1*m1);

// Which is wrong! But why!


[Edited by - ZealGamedev on October 2, 2010 12:04:30 PM]

Share this post


Link to post
Share on other sites
Gah I have gone over the math a few times... The m1 value is coming up as 2 (it should be 1). I am sure it has to be a problem on my end, I mean the guys equation cant be wrong can it? He is a MATH DOCTOR!

Ahhhh

Share this post


Link to post
Share on other sites
I haven't looked at your code. However, I'll point out that if your equations are consistent -- if ua and ub really do point from the same point a -- then the least-squares solution that I gave has zero error and is actually an exact solution to the equations.

Basically, two lines in 3d don't always intersect. But if they do, you'll get the point where this happens.

Share this post


Link to post
Share on other sites

This topic is 2632 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this