Angle between two points.
Author
I''ve run in to a bit of a trig problem.
My program is running under a very limited environment: no floating point, no trig functions, no sqrt.
That said, I''ve created fixed point sin, cos, and tan tables. I''ve implemented a fixed point multiply, but have avoided division. Assume that my division has 0 decimal places of accuracy.
My problem is:
Give two points on a plane, A(x,y), B(x,y), how can I determine the angle between them?
Is this even possible with what I have? If not, what function(s) would I need to solve this problem?
Thanks,
Will
I''m not sure how you want to calculate an angle between two points. It only forms a line, to calculate an angle you''d need two lines. (or three points). 
Assuming you mean the angle between the lines from the origin to the two points (you really should be clearer/specific as Blue Phoenix said...), you could use the dot product
(Ax, Ay).(Bx, By) = |A||B|cos(angle)
where (Ax, Ay) is the vector A, (Bx, By) is the vector B, |A| and |B| are the magnitudes of the vectors A and B respectively and angle is the angle (in radians) between the vectors.
Ax*Bx + Ay*By = sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By)*cos(angle)
cos(angle) = (Ax*Bx + Ay*By)/(sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By))
So you''d need to have an inverse cosine function to find the angle, I believe...
(Ax, Ay).(Bx, By) = |A||B|cos(angle)
where (Ax, Ay) is the vector A, (Bx, By) is the vector B, |A| and |B| are the magnitudes of the vectors A and B respectively and angle is the angle (in radians) between the vectors.
Ax*Bx + Ay*By = sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By)*cos(angle)
cos(angle) = (Ax*Bx + Ay*By)/(sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By))
So you''d need to have an inverse cosine function to find the angle, I believe...
Geoff, did you even read RP's post? he's using fixed-point...
Will, if you're okay with receiving an approximation of the angle you can use the following instead of acos.
angle = fixedpoint(90) - dotproduct(a,b)/(length(a) * length(b))) * fixedpoint(90);
where dotproduct(a,b) is a.x*b.x + a.y*b.y
The problem comes in with the length(a) and length(b) as well as the division required there with the fixed-point. But at least you can eliminate acos.
by the way, what is the bit-depth of your fixed point operations?
16.16, 8.8, 32.32, 24.8, 8.16? Division in fixed-point is a bit more tricky, you may have to use intermediate variables to store the high-part for you. Also, there are some good fixed-point square root functions out there - classic example is one of John Carmack's Quake1/2/3 (not sure which version)...
if you understand ASM, here's an interesting tutorial...
http://www.geocities.com/SiliconValley/Lakes/4543/fix1.txt
BTW, what hardware are you developing for?
[edit]
another link:
http://www.mactech.com/articles/mactech/Vol.10/10.03/FixedPointMath/
has some c++ 16.16 fixed point sqrt code.
[/edit]
[edited by - FReY on November 11, 2003 8:45:42 AM]
Will, if you're okay with receiving an approximation of the angle you can use the following instead of acos.
angle = fixedpoint(90) - dotproduct(a,b)/(length(a) * length(b))) * fixedpoint(90);
where dotproduct(a,b) is a.x*b.x + a.y*b.y
The problem comes in with the length(a) and length(b) as well as the division required there with the fixed-point. But at least you can eliminate acos.
by the way, what is the bit-depth of your fixed point operations?
16.16, 8.8, 32.32, 24.8, 8.16? Division in fixed-point is a bit more tricky, you may have to use intermediate variables to store the high-part for you. Also, there are some good fixed-point square root functions out there - classic example is one of John Carmack's Quake1/2/3 (not sure which version)...
if you understand ASM, here's an interesting tutorial...
http://www.geocities.com/SiliconValley/Lakes/4543/fix1.txt
BTW, what hardware are you developing for?
[edit]
another link:
http://www.mactech.com/articles/mactech/Vol.10/10.03/FixedPointMath/
has some c++ 16.16 fixed point sqrt code.
[/edit]
[edited by - FReY on November 11, 2003 8:45:42 AM]
Author
Thanks to everyone who has replied.
Blue Phoenix and kin: Yes, I should have said the angle between two vectors.
Thanks very much for the links, I'll check them out.
I'm using 18.14 fixed point. My environment is Java 2 Micro Edition.
The only thing that worries me about the proposed soltions is the division.
When I get home I'll try implementing the proposed solutions. I'll check if I the 64 bit Long is actually implemented supported.. This would make life a bit easier.
Thanks,
Will
[edited by - RPGeezus on November 11, 2003 1:44:36 PM]
Blue Phoenix and kin: Yes, I should have said the angle between two vectors.
Thanks very much for the links, I'll check them out.
I'm using 18.14 fixed point. My environment is Java 2 Micro Edition.
The only thing that worries me about the proposed soltions is the division.
When I get home I'll try implementing the proposed solutions. I'll check if I the 64 bit Long is actually implemented supported.. This would make life a bit easier.
Thanks,
Will
[edited by - RPGeezus on November 11, 2003 1:44:36 PM]
Its also easy to make a division lookup table.
1/n, then multiply. Best ofcourse to set the fixed point at the most significant bit here.
There are some very fast (but less accurate) methods to calc the sqrt with superspeed. Back in the assembly days, these were often used for phong shading.
Like FReY said, carmacks sqrt use might be good. But if i remember correctly, he used them for texture perspective.
The phong shading could be a better example to lookup. Because this is more focussed on a 1/sqrt for normalization (like you need).
1/n, then multiply. Best ofcourse to set the fixed point at the most significant bit here.
There are some very fast (but less accurate) methods to calc the sqrt with superspeed. Back in the assembly days, these were often used for phong shading.
Like FReY said
, carmacks sqrt use might be good. But if i remember correctly, he used them for texture perspective.The phong shading could be a better example to lookup. Because this is more focussed on a 1/sqrt for normalization (like you need).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
