Fastest way to get angle between two points
BlitzMax Forums/BlitzMax Programming/Fastest way to get angle between two points
| ||
| I was just experimenting a bit and wondering how to get the angle between two points fast, e.g. when two spheres are checking for collision. I'm familiar with code like this:
Function GetAngle2D:Float(X1:Float,Y1:Float,X2:Float,Y2:Float)
local dx# = x2 - x1
local dy# = y2 - y1
Return ATAN2(dy#,dx#)+360) MOD 360
End Function
But I'm wondering if there is a faster way without the Atan2 which I presume is slow? So I thought of this.. Precalculate a lookup table which is basically in the shape of a hollow square - ie two sides, top and bottom. It'll represent a square of fixed size, preferably bigger than your objects. You can make it as detailed as you like with as much precision as is necessary. Then let's say you have a circle centered in the middle of the square (object A), and another circle about to collide with it (object B). Both are inside the lookup table `box`. To find the angle from the center of A to B, you'd a) find out how much distance there is between object B and the edge of the lookup box (separately for X and Y), b) Figure out what portion of the half-height/half-width of the box that distance represents (without doing a divide?), c) multiply the distance between the circles by that amount to basically extend the line from object A, through object B, and collide with the lookup box, d) read the value at that position in the lookup table - that's your angle. I haven't written it in code but I believe it would work in theory... just not sure how you'd find out how much to scale/extend the line by without using a divide. Also not sure if it'd be faster than Atan2 or not. But it's an idea. |
| ||
| Sounds interesting.. but what is ATAN2 doing? [Edit] Oops - seems like the standard bmx ATan2 is calling into maths.h. Now I do not know details about the C atan2 implementation, but i'd assume it is *very* fast and highly optimized .. do you need a special deal of performance, or are you proposing your concept just out of interest? Last edited 2010 Last edited 2010 |
| ||
| Just out of interest. I don't really need it for anything. Just wondered if it'd help others, if it works better. |
| ||
| Sounds like a perfect candidate for the proposed monthly programming challenge... :) |
| ||
| One way to speed it up is to change the way you view the angle. Seems that game programmers have gotten into the habit of viewing 0 degrees as pointing up and going to 360 degrees as you turn clockwise. In math, 0 degrees points along the positive x axis, which is toward the right of the screen. Positive degrees moves toward the positive y axis, which is clockwise on the screen, and negative degrees move toward the negative y axis, or counter-clockwise. The range is -180 to 180 degrees. ATan2() is a mathematical function and therefore returns angles with that standard. If we program games the same way, then there is no need to shift the returned angle into what we are using. So you can get rid of the +360 Mod 360 portion of the function. Even though the docs say that SetRotation accepts an integer from 0 to 360, it will also accept -180 to 180 range as well and still work properly as long as you use that system throughout. Only problem is that GetAngle will not return the proper angle any more, but I tend to store the angle in a separate variable anyway. At first, it might seem odd, or even wrong to do things that way; but like learning hexadecimal, if you force yourself to do it that way, you eventually see the logic in it and prefer it in certain conditions. Also, if you are wondering exactly what ATan2(y,x) does, it is returning the arctangent of y/x, but eliminates the possibility of a divide by zero (if x = 0) as well as correcting for quadrant (Atan(y/x) only returns valid if both x and y are positive or both x and y are negative). |
| ||
| Sounds fine, but the thread is really about how to get rid of Atan2 entirely. |
| ||
| I was just experimenting a bit and wondering how to get the angle between two points fast, e.g. when two spheres are checking for collision. Why would you need the angle to check sphere collision? Just get the radius of each one, and if the distance from the center of each is lower than the sum of both radius, you have a collision. |
| ||
| Not specific to collision detection, that was just an example. |
| ||
| Make the points constant, then the angle will never change. If anyone thinks I'm being facetious, I'm not, but I'd prefer not to explain my answer unless it's truly necessary. |
   |