13 replies to this topic

[Spudman]

I need to solve this equation in 'y':

a + b*y + c * sqrt( d + y^2 ) = 0

where a,b,c,d are all constants. Any mathematicians out there ?....

And the reason I need to do this...
I have two normalised 3-vectors 'P' and 'Q at right angles ( P.Q = 0 )
I know the value of all 3 elements of P, but only have the 'x' element of Q.
I wish to get back the 'y' and 'z' elements of Q.

Obviously if I get back 'z' then y = sqrt( 1 - (x*x) + (z*z) ), + or - is valid.
Similarly if I had 'y' then I could get back either value of z.

Px*Qx + Py*Qy + Pz*Qz = 0 (i)
Qz = sqrt( 1 - ( Qx^2 + Qy^2) ) (ii)

Substitute (ii) into (i) gives:

Px*Qx + Py*Qy + Pz*sqrt( 1 - ( Qx^2 + Qy^2) ) = 0 (iii)

The only unknown in (iii) is Qy. This equation is of the form:

a + b*y + c * sqrt( d + y^2 ) = 0

What now ???
Thanks

[hunguptodry]

squaring and re-arranging will get u something like ...

(b^2-c^2)y^2+(2ab)y+(a^2-c^2d) = 0

this is well known quadratic form.

[Reedbeta]

There are infinitely many possible solutions to your problem. Consider: the set of all vectors perpendicular to P forms a plane in three dimensional space. If you fix the x component of Q, that effectively restricts Q to lying along a second plane. So your problem is really to find the intersection of two planes, which in general is a line; then any point on this line would be a possible solution for Q. Solving for the line of intersection of two planes is a well-known problem and there are probably plenty of websites detailing how to do it.

[Spudman]

Thanks for replying, unfortunately thes replies are both wrong:

hunguptodry: This does NOT become a quadratic, squaring will still produce a term in sqrt( d + y^2).

Reedbeta: I agree that if there were no constraints on P and Q then
you would be correct, however since ( p dot Q = 0) and P and Q are both
normalized then we have the situation that Q will lie on a unit circle in the
plane for which P is the normal. Knowing Qx there will be two solutions
for Qy ( + or - ) and similarly if I had solved for Qz instead of Qy there
would be two values, this is consistent with the fact that given any two
components of Q the third is plus or minus the root of 1 less the sum of squares of the other two.

Oh well.... I'll take another look at it....
Cheers anyway

[peterbone]

If you can't solve it analytically then it may be transendental so use a numerical method. e.g. Newton's method. It will probably only need about 5 iterations to converge (depending on the accuracy you require) so it shouldn't slow it down much.

[SigKILL]

Reedbeta is right, there are infinitely many solutions. Simply use an affine transformation so the P vector becomes (1,0,0), then Q.x becomes 0, and you have a circle of possible solutions in the ZY-plane.

-si

[CobraLionz]

Um the first reply was right the whole time.

[monjardin]

I can verify hunguptodry's simplification as well.

ReedBeta's geometric solution works too:

[Reedbeta]

Yeah, sorry I didn't notice that Q was specified to be normalized. That certainly cuts things down. One way to solve this would be to find the line of intersection of the two planes, as I mentioned, and then solve for the points that are of distance 1 from the center point (which is a quadratic; it's just the same as 'ray-tracing' that line against the sphere of radius 1). There will be either zero, one, or two possible solutions.

[cypher543]

Ok, I have to ask this... is math like this required in game programming??? I'm just wondering becuase I'm currently in 9th grade and I hardly understood linear equations and graphing them... and everything guys just said sound like every one of you were from another planet. Sorry about going off topic.

[Spudman]

- 'Is maths like this required in games programming...' - Ever looked at a physics engine ? seriously though this problem arises from my trying to
compress a translation, if I can solve this then I can store a 3x3 matrix
as 2 components for one vector (quantized to 2 bytes is accurate enough)
and 1 component for another of the vectors (again 1 byte), plus 1 bit for which of the y solutions needed, and 1 bit for the sign of the z in the 2nd vector, plus 1 bit for the sign of the cross product needed to get the 3rd basis vector... giving me 3 bytes + 3bits = 27 bits, maybe its a bit extreme
but why not...

[Spudman]

OOPS... I looked at it again, and it appears that HungUpToDry is right...
my most sincere apologies....

a + b*y + c * sqrt( d + y^2 ) = 0
(a + b*y) = -c * sqrt( d + y^2 )
a^2 + 2*a*b*y + b^2 * y^2 = c^2 ( d + y^2 )
(b^2 - c^2)y^2 + ( 2*a*b )y + ( a^2 - d * c^2 ) = 0

ie.a simple quadratic.
God I'm thick.....
Thanks HungUpToDry

[Nils Pipenbrinck]

cypher543 said:

Ok, I have to ask this... is math like this required in game programming???

Hi.

Not nessesarily.. If you do platform games, or other simple straight forward stuff you don't need to deal with that kind of math.

But if you dig a bit deeper you'll run into these kind of problems frequently. Don't worry tough. It's just a matter of practice.. You'll get used to such stuff quicky, and it's only half as complicated as it looks like.

Also any kind of math becomes very *very* very interesting as soon as you find a reason to understand them (read: programming problem that you want to solve the clever way).

[juhnu]

You could try converting a 3x3 matrix (assuming it represents only rotation), to a quaternion and compressing that to a single 32-bit integer.