Fast ATan2 (4° precision)

This code has been declared by its author to be Public Domain code.

Fast ATan2 (4° precision) by Bobysait

2013

/!\ This function does not return the "true" values
but a value near the real (in worst case, 4.07° of difference)

it uses a square algorithm to get a value really closed to what the ATan2 function returns, but the function is 2 times faster.

Really usefull for game Physics to get approximate angles between 2 vectors (can be usefull for a kid of random but accurate behavior due to the approximative result of the function)
can also be usefull to performs checking.
For ex, if you're searching for an object in a orientation field, then you probably does not require a perfect angle

(like for NPCs searching a target in their "field of view")
for this purpose, you 'll check it 100% faster than with the Atan2 function

this function can also be used for previous test before using a real precise test.
ex: you need to check a lot of vectors alignment
For each vectors1
For each vectors2
If abs(ATan2F(vectors2.y,vectors2.x)-ATan2F(vectors1.y,vectors1.x))<4.08
; here you should have a lot of pairs removed, so it only performs a precise test only if require
if abs(ATan2(vectors2.y,vectors2.x)-ATan2(vectors1.y,vectors1.x))<.001
; Vectors are aligned
endif
else
; vectors are not aligned
endif
next
next

Then it should optimize a bit the framerate (like 1 to 50% faster according to the number of vectors aligned
In worst case, the function would be slower ... for exemple if all vectors are aligned it would performs the both Atan2 and Atan2F test...)

I've checked for the maximum difference between both function, the maximum degree of difference is 4.07458

Function Atan2F#(y#, x#)
	If y=0 :If x=0 :Return 0:EndIf:Return 180:EndIf
	Local abs_y#=Abs(y):If(x>=0.0):Return(45+45*(abs_y-x)/(x+abs_y))*Sgn(y):EndIf:Return(135+45*(x+abs_y)/(x-abs_y))*Sgn(y)
End Function







; exemple : check vectors are aligned
Type v
	Field x#,y#
End Type

For n = 1 To 2000
	v.v=New v
	v\x=Rnd(-1,1)
	v\y=Rnd(-1,1)
Next

Local NbAligned=0
Local NbAlignedF=0
Local angle#,angleF#

Local t0 = MilliSecs()
For a.v = Each v
	angle=ATan2(a\y,a\x)
	For b.v=Each v
		If a<>b
			If Abs(angle-ATan2(b\y,b\x))<0.0001
				NbAligned=NbAligned+1
			EndIf
		EndIf
	Next
Next

Local t1 = MilliSecs()
For a.v = Each v
	angleF=Atan2F(a\y,a\x)
	angle=ATan2(a\y,a\x)
	For b.v=Each v
		If a<>b
			If Abs(angleF-Atan2F(b\y,b\x))<4.08
				If Abs(angle-ATan2(b\y,b\x))<0.0001
					NbAlignedF=NbAlignedF+1
				EndIf
			EndIf
		EndIf
	Next
Next

Local t2 = MilliSecs()

Print "NbAligned  = "+NbAligned
Print " time      = "+(t1-t0)
Print ""
Print "NbAlignedF = "+NbAlignedF
Print " time      = "+(t2-t1)
WaitKey
End

Comments

virtlands

2013

Well, 4° of separation is better than 6° of separation. Thanks.

2013

Function Atan2F#(y#, x#)
	Return 180*(0.5*Sgn(y)+-0.4526*x*Sgn(y)/(6+Abs(y)+Abs(0.7981*x)))
EndIf

Bobysait

2013

@GW
On my machine my function runs faster than yours ...
And yours gives some wired results (more than 30° of difference)
so inaccurate actually and not precise at all.
There may be a mistake inside ? (as you ended it with "Endif" there is probably something else that is mispelled ?)

2013

It might not be completely correct, I tested it with several thousand iterations of random x,y at {-1000,1000} It has a smaller delta to atan2 than your function, but just by a tiny bit.
What kind of inputs are you seeing strange outputs with?

|edit|
ok, this one should be more accurate. not sure about the speed..

Function Atan2F_2#(y#,x#)
	Local ax# = Abs(x)
	Local ay# = Abs(y)
	Local sy# = Sgn(y)
	Local sx# = Sgn(x)
	Return 180 * (0.5*sy + (sx*sy - 0.5*x*sy)/Abs(0.5*ay + ((ay*ay) - ay)/(ax + ay) + ax))
End Function

Bobysait

2013

well, have a look

Function Atan2F#(y#, x#)
	Local abs_y#=Abs(y):If(x>=0.0):Return(45+45*(abs_y-x)/(x+abs_y))*Sgn(y):EndIf:Return(135+45*(x+abs_y)/(x-abs_y))*Sgn(y)
End Function

Function Atan2F_2#(y#,x#)
	Local ax# = Abs(x)
	Local ay# = Abs(y)
	Local sy# = Sgn(y)
	Local sx# = Sgn(x)
	Return 180 * (0.5*sy + (sx*sy - 0.5*x*sy)/Abs(0.5*ay + ((ay*ay) - ay)/(ax + ay) + ax))
End Function

; calculate difference
Local maxBoby, maxGW, diff, j#,i#
For j = -100.1 To 100 Step 10
For i = -100.1 To 100 Step 10
	diff = (ATan2(j,i)-Atan2F(j,i))
	If diff>maxBoby Then maxBoby=diff
	diff = (ATan2(j,i)-Atan2F_2(j,i))
	If diff>maxGW Then maxGW=diff
Next
Next

Print "Difference Boby : "+maxBoby
Print "Difference GW   : "+maxGW
Print "-----------"


; benchmark
Const ntest = 5000000
Local seed = 123, x#,y#

Local t0 = MilliSecs()
SeedRnd(seed)
For n = 1 To ntest
	ATan2(Rnd(-1000,1000),Rnd(-1000,1000))
Next

Local t1 = MilliSecs()
SeedRnd(seed)
For n = 1 To ntest
	Atan2F(Rnd(-1000,1000),Rnd(-1000,1000))
Next

Local t2 = MilliSecs()
SeedRnd(seed)
For n = 1 To ntest
	Atan2F_2(Rnd(-1000,1000),Rnd(-1000,1000))
Next
Local t3 = MilliSecs()

Print "blitz Atan2 : "+(t1-t0)
Print "Boby Atan2F : "+(t2-t1)
Print "GW Atan2F_2 : "+(t3-t2)
WaitKey
End

I find 18° at max of difference for your function
4° on mine

and the bench returns :
- blitz : 605 ms
- boby : 460 ms
- GW : 810 ms

[edit]
At some values (near 0,0) your function totally fails and returns a 31576.2 degrees ... :/

And actually, it makes sense.
you're dividing a number by a near "0" value
it then depends on the ratio between the numerator and the denominator

Function Atan2F#(y#, x#)
	If y=0 :If x=0 :Return 0:EndIf:Return 180:EndIf
	Local abs_y#=Abs(y):If(x>=0.0):Return(45+45*(abs_y-x)/(x+abs_y))*Sgn(y):EndIf:Return(135+45*(x+abs_y)/(x-abs_y))*Sgn(y)
End Function

Function Atan2F_2#(y#,x#)
	Local ax# = Abs(x)
	Local ay# = Abs(y)
	Local sy# = Sgn(y)
	Local sx# = Sgn(x)
	Return 180 * (0.5*sy + (sx*sy - 0.5*x*sy)/Abs(0.5*ay + ((ay*ay) - ay)/(ax + ay) + ax))
End Function

; calculate difference
Local j#,i#, diff#
Local maxBoby#, maxbi#,maxbj#
Local maxGW#, maxgi#,maxgj#
For j = -10 To 10 Step .123
For i = -10 To 10 Step .231
	diff = (ATan2(j,i)-Atan2F(j,i))
		If diff=180
			Print "["+i+","+j+"] bb:"+ATan2(j,i)+" boby :"+Atan2F(j,i)
		Else
			If diff>maxBoby Then maxBoby=diff:maxbi=i:maxbj=j
		EndIf
	diff = (ATan2(j,i)-Atan2F_2(j,i))
		If diff=180
			Print "["+i+","+j+"] bb:"+ATan2(j,i)+" GW   :"+Atan2F_2(j,i)
		Else
			If diff>maxGW Then maxGW=diff:maxgi=i:maxgj=j
		EndIf
Next
Next

Print "Difference Boby : "+maxBoby+" at "+maxbi+","+maxbj
Print "Difference GW   : "+maxGW+" at "+maxgi+","+maxgj
Print "-----------"

ps :
I added a check on my function to return 180 on y=0
(as, don't know why but, the Blitz Atan2 function returns 180 in this special case ... where my function returned 0)

2013

I don't think I can get any faster than your method.
This is best I can do. It has the same 4deg of slippage and is just a hair slower.

Function Atan2F_2#(y#,x#)
	Local sy# = Sgn(y)
	Local sx# = Sgn(x)
	Return 180*(0.5*sy + -22.5*x/(45*y + 45*x*sx*sy))
End Function

Good job!

Kryzon

2013

It uses a square algorithm to get a value really closed to what the ATan2 function returns

Hi. Could you please elaborate on this method you're using to approximate ATan2?

Bobysait

2013

everything is explained on this site
http://dspguru.com/dsp/tricks/fixed-point-atan2-with-self-normalization
it was originally designed in radian but the conversion is quite easy.

I replaced most of the algorithm with the ease of the blitz syntax :)

MCP

2013

That's an interesting link Bobysait thanks :)
BTW There's also an algorithm to compute the square root of a number on there. Do you know if that was also faster than the standard Blitz function?

Bobysait

2013

Already tested, it's way slower and only returns round integer of the square root

Code Archives Forum