ZealGamedev 100 Report post Posted October 1, 2010 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! 0 Share this post Link to post Share on other sites
Gage64 1235 Report post Posted October 1, 2010 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. 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 1, 2010 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? 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 1, 2010 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? 0 Share this post Link to post Share on other sites
Emergent 982 Report post Posted October 1, 2010 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 = banda + 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 6x1or justA x = Bwith A and B defined by the above. Multiply both sides by A^T to getA^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 writex = (A^T A)^(-1) A^T Bwhich is the least squares solution. 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 1, 2010 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.htmlI 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. 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 2, 2010 I found another article and took a stab at implementing it... http://mathforum.org/library/drmath/view/63719.htmlI 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] 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 2, 2010 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 0 Share this post Link to post Share on other sites
ZealGamedev 100 Report post Posted October 4, 2010 Anyone had a chance to take a look at my code? Something is obviously wrong... 0 Share this post Link to post Share on other sites
Emergent 982 Report post Posted October 4, 2010 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. 0 Share this post Link to post Share on other sites