# Triangulation...

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

## 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?

##### 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 on other sites
Yes the rays could be considered normals. They point from A to B/C.

And yes I agree doing a line intersection like you propose should work... anyone have a sample algorithm?

##### Share on other sites
I googled "intersection of two lines" and once again came up with a lot of the basic concepts, but nothing using 3d vectors/coordinates. Anyone have a sample using 3d vectors?

##### 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 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 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 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 on other sites
Anyone had a chance to take a look at my code? Something is obviously wrong...

##### 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.

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631785
• Total Posts
3002348
×