Optimising Challenge

BlitzMax Forums/BlitzMax Programming/Optimising Challenge

Robert Cummings

(Posted 2006) [#1]

Hi all,
I got this interpolation code from code archives from Freborg and I need to speed it up (see Tween360 below).

It is used to tween the last rotation to the next rotation, however it is too slow for the number of items I want to use it for. Thing is, I believe this routine is overkill for just tweening between angles...

All I want to do is tween between two angles, for example a = 350 and b= 10 using 0..1 as the time so I can get any tweened position between them... As you might have thought, it will actually spin the other way with normal tweening like this:

Fast but doesn't account for 360 degrees:

Function Tween:Float(p1:Float,p2:Float,t:Float)
	Return p1 + t * (p2 - p1)
End Function

But the following routine is too slow, so any ideas how I can get a tween for angles that works like the above but with the reliability of the routine below? I suspect I don't actually need all those cosines and atan2!

Slow but works:

Function Tween360:Float( a:Float , b:Float , time:Float )
	Local ix:Float = Sin(a)
	Local iy:Float = Cos(a)
	Local jx:Float = Sin(b)
	Local jy:Float = Cos(b)
	Return ATan2(ix-(ix-jx)*time,iy-(iy-jy)*time)
End Function

undomiel

(Posted 2006) [#2]

My first impulse is to precompute all of those sines and cosines. Just precalculate an array at the beginning of your program and then just use like mySin[a] myCos[b] instead of having to recalculate them every single time. Then you would only have the ATan2 to worry about. Of course there's probably a better way of doing it mathematically but I'll have to confess to being less than a math genius.

Robert Cummings

(Posted 2006) [#3]

That is my suspicion. As you can see, Tween works perfect - even for rotations, and is incredibly fast. However the problem is, when the target angle goes back to >=0, the source angle might be 360 or less. This causes the Tween function to rotate the opposite way rapidly, which looks very bad!

If only there was a way to modify the original fast tween? Perhaps BRL or someone will know?

Dreamora

(Posted 2006) [#4]

You don't even need to modify the tween. But you have to "modulo wrap" the values you give it so you make sure that angles are 0<= x < 360. Even the best function breaks if the input is "wrong" :-)

Robert Cummings

(Posted 2006) [#5]

Please explain further. Also, is this 'modulo' slow to use?

Dreamora

(Posted 2006) [#6]

The problem is within the (p2 - p1). If p1 goes below 0, this will result in a positive rotation, which is most likely not the direction you want it to turn.

Thus you must make sure that p1 is a valid, positive angle. To do so, you simply call the function like:

Tween(p1 mod 360,p2 mod 360,t)

Or better, you already wrap the angles to valid positives when you set them instead of converting them when you need them, as this would eat up useless time again.

Robert Cummings

(Posted 2006) [#7]

I'm afraid your usage with mod didn't seem to make it work. Thanks for trying though.

[edited]

Dreamora

(Posted 2006) [#8]

What exactly is not working?
I just realized that BM uses Cs modulo operator. This means that you must use (value + modvalue) mod modvalue to get correct behavior for negative values, assuming that it can't jump in its angle to more than +- modvalue in one go.



Strict
Local v1:Float	= (400 +360) Mod 360
Local v2:Float	 = (-270 +360) Mod 360

While v1 < v2 - 0.1 Or v1 > v2 + 0.1    ' Means v1 must be within a +- 0.1 range of v2

	v1	 = tween(v1 , v2 , 0.001)
	Print "V1: " + v1 + " , V2:" + v2

Wend



End


Function Tween:Float(p1:Float,p2:Float,t:Float)
	Return p1 + t * (p2 - p1)
End Function

If it is a different thing, you perhaps have a code that shows the actual problem?

Robert Cummings

(Posted 2006) [#9]

Let me explain: The inputs are within 0..360 already, the problem is source might be 359 and dest might be zero when we are moving clockwise. What do you think will happen?

Right! it'll spin backwards again. That is why I am trying to optimise the second routine by fredborg but I don't pretend to understand how it works.

However if anyone out there has experience in tweening rotations with a time value between 0...1 then I would love to hear from you! :)

Robert Cummings

(Posted 2006) [#10]

Note: source and dest are not interchangable, I will always be moving in the direction from source to dest, that is why the following conditions break it:

Frame One:
source = 350
dest = 359

Frame Two:
source = 359
dest = 8

As you can see I am moving clockwise, but

Function Tween:Float(p1:Float,p2:Float,t:Float)
	Return p1 + t * (p2 - p1)
End Function

... will break and cause it to spin the other way. I need to modify Tween so it doesn't do this but I can't think out the box enough to do so.

Dreamora

(Posted 2006) [#11]

Function TweenAngle:Float(p1:Float , p2:Float , t:Float)
	If Abs(p2 - p1) < 180
		Return p1 + t * (p2 - p1)
	EndIf
	Return (p1 + t * (p2 + p1)) Mod 360
End Function

Thats faster than the Tween360. There might be faster ways perhaps.

Here the "benchmarking"


Strict
Local v1:Float	= 190 Mod 360
Local v2:Float	 = 0 Mod 360


Local time1:Int	 = MilliSecs()

For Local i = 1 To 1000
	v1	 = 190
	v2	 = 0
	
	While v1 < v2 - 0.1 Or v1 > v2 + 0.1
	
		v1	 = TweenAngle(v1 , v2 , 0.001)
	
	Wend
Next
time1	 = MilliSecs() - time1
Print "TweenAngle Time: " + time1

Local time2:Int	 = MilliSecs()

For Local i = 1 To 1000
	v1	 = 190
	v2	 = 0
	
	While v1 < v2 - 0.1 Or v1 > v2 + 0.1
	
		v1	 = tween360(v1 , v2 , 0.001)
	
	Wend
Next
time2	 = MilliSecs() - time2
Print "Tween360 Time: " + time2

End


Function TweenAngle:Float(p1:Float , p2:Float , t:Float)
	If Abs(p2 - p1) < 180
		Return p1 + t * (p2 - p1)
	EndIf
	Return (p1 + t * (p2 + p1)) Mod 360
End Function

Function Tween360:Float( a:Float , b:Float , time:Float )
	Local ix:Float = Sin(a)
	Local iy:Float = Cos(a)
	Local jx:Float = Sin(b)
	Local jy:Float = Cos(b)
	Return ATan2(ix-(ix-jx)*time,iy-(iy-jy)*time)
End Function

Robert Cummings

(Posted 2006) [#12]

Nice work - very fast and very close but it still "breaks" on some angles and spins the other way? It still has bugs...

Dreamora

(Posted 2006) [#13]

If you have me the situations it breaks, I will try to get the bugs out :-)

Robert Cummings

(Posted 2006) [#14]

Ok :-)

'demonstration code to break tween angle

'note that angle1 and angle 2 will both move at their own pace
'with a gap between them from 0..360 to test

SuperStrict
Graphics 640,480,0

Global sourceAngle:Float , destAngle:Float
Global angle1:Float = 0
Global angle2:Float = 15

While Not KeyHit(KEY_ESCAPE)
	Cls
	
	'test tweenAngle
	angle1:+1
	angle2:+1
	If angle1>360 angle1 :- 360
	If angle2>360 angle2 :- 360
	
	Local ang:Float = TweenAngle( angle1 , angle2 , 0.5 )
	
	'draw	
	DrawLine 320 , 240 , 320-Cos(ang)*32 , 240-Sin(ang)*32
	Flip
Wend

Function TweenAngle:Float( p1:Float , p2:Float , t:Float)
	If Abs(p2 - p1) < 180
		Return p1 + t * (p2 - p1)
	EndIf
	Return (p1 + t * (p2 + p1)) Mod 360
End Function

Remember it has to work both ways :)

Floyd

(Posted 2006) [#15]

Tween360 doesn't really do what you want. It interpolates tangents of angles.

This TweenAngle should work, assuming I understand the goal here.
It must be used with non-negative angles less than 360, and t in the range 0 to 1.

Here's an example which also shows how Tween360 is a kind of interpolation, but is not linear.

Print

For f# = 0 To 1 Step 0.125             ' step will be 0.125 * 80 = 10 degrees
	a# = TweenAngle( 100 , 180 , f )
	b# = Tween360( 100 , 180 , f )	
	Print a + "  " + b
Next

' Assumes p1 and p2 are in the range [0,360) and t is in [0,1].
Function TweenAngle#( p1# , p2# , t# )
	
	Local angle# = p1 + t * (p2 - p1)
	
	If p1 <= p2 Then Return angle
	
	angle :+ t * 360.0
	
	If angle < 360.0
		Return angle
	Else
		Return angle - 360.0
	End If
	
End Function

Function Tween360:Float( a:Float , b:Float , time:Float )
	Local ix:Float = Sin(a)
	Local iy:Float = Cos(a)
	Local jx:Float = Sin(b)
	Local jy:Float = Cos(b)
	Return ATan2(ix-(ix-jx)*time,iy-(iy-jy)*time)
End Function

Eric	(Posted 2006) [#16]

Is this any closer?

SuperStrict
Graphics 640,480,0

SuperStrict
Graphics 640,480,0
Global Target:Float  
Global Angle:Float 
While Not KeyHit(KEY_ESCAPE)
	Cls
	Target=ATan2(320-MouseY(),240-MouseX()) +180
	Angle:+TweenAngle(Angle , Target , 0.05 )
	If Angle>360 Then Angle:-360
	If Angle<0 Then Angle:+360
 
	DrawLine 320 , 240 , 320+Cos(angle)*32 , 240+Sin(angle)*32
	Flip
Wend

Function TweenAngle:Float( C:Float , T:Float , S:Float)
		Local DX:Float = T-C
	 	If Abs(DX)>180 Then DX=DX-Sgn(DX)*360
		Return (DX*S)
	
End Function

Regards,
Eric

Dreamora

(Posted 2006) [#17]

There is an error in:

Function TweenAngle:Float( C:Float , T:Float , S:Float)
		Local DX:Float = T-C
	 	If Abs(DX)>180 Then DX=DX-Sgn(DX)*360
		Return (C + DX*S)
	
End Function

But even that does not seem to be correct for tweening. It only works for the given sample with the drawing. When tweening from 0 to 190, it gets stuck at -169.99999994

I modified mine as well:

SuperStrict
Local v1:Float
Local v2:Float

Local time1:Int	= MilliSecs()
For Local i:Int = 1 To 1000
	v1 = 0
	v2 = 190
	While v1 < v2 - 0.1 Or v1 > v2 + 0.1
		v1	= tweenangle1(v1,v2,0.1)
	Wend
Next
time1	= MilliSecs() - time1
Print "Time1: " + time1

Local time2:Int	= MilliSecs()
For Local i:Int = 1 To 1000
	v1 = 0
	v2 = 190
	While v1 < v2 - 0.1 Or v1 > v2 + 0.1
		v1	= tweenangle(v1,v2,0.1)
		Print v1 + "," + v2
	Wend
Next
time2	= MilliSecs() - time2
Print "Time2: " + time2

End


Function TweenAngle1:Float( p1:Float , p2:Float , t:Float)
	If Abs(p2-p1) > 180
		If p2 < 180 Return wrapangle(p1 - t * (p1 - p2) + 180)
		Else Return wrapangle(p1 - t * (p1 - p2))
	EndIf
	Return wrapangle(p1 + t * (p2 - p1))
	
	Function WrapAngle:Float(angle:Float)
		Return (angle + 360) Mod 360
	End Function
End Function

Function TweenAngle:Float( C:Float , T:Float , S:Float)
		Local DX:Float = T-C
	 	If Abs(DX)>180 Then DX=DX-Sgn(DX)*360
		Return (C + DX*S)
	
End Function

*mine takes 31ms for 1000 full tweens with 0.1 iteration. Can't say for the other as it stucks*

Eric	(Posted 2006) [#18]

I changed my section "Loop 2" to run as designed... Try it now...Does it help?

SuperStrict
Local v1:Float
Local v2:Float

Local time1:Int	= MilliSecs()
For Local i:Int = 1 To 1000
	v1 = 0
	v2 = 190
	While v1 < v2 - 0.1 Or v1 > v2 + 0.1
		v1	= tweenangle1(v1,v2,0.1)
	Wend
Next
time1	= MilliSecs() - time1
Print "Time1: " + time1

Local time2:Int	= MilliSecs()
For Local i:Int = 1 To 1000
	v1 = 0
	v2 = 190
	While Abs(V1-V2)>.1
		v1:+ tweenangle(v1,v2,0.1)
		If v1>360 Then v1:-360
		If v1<0 Then v1:+360

	Wend
Next
time2	= MilliSecs() - time2
Print "Time2: " + time2

End


Function TweenAngle1:Float( p1:Float , p2:Float , t:Float)
	If Abs(p2-p1) > 180
		If p2 < 180 Return wrapangle(p1 - t * (p1 - p2) + 180)
		Else Return wrapangle(p1 - t * (p1 - p2))
	EndIf
	Return wrapangle(p1 + t * (p2 - p1))
	
	Function WrapAngle:Float(angle:Float)
		Return (angle + 360) Mod 360
	End Function
End Function

Function TweenAngle:Float( C:Float , T:Float , S:Float)
		Local DX:Float = T-C
	 	If Abs(DX)>180 Then DX=DX+Sgn(DX)*360
		Return (DX*S)
	
End Function

Dreamora

(Posted 2006) [#19]

So the function should look like this?

Function TweenAngle:Float( C:Float , T:Float , S:Float)
		Local DX:Float = T-C
	 	If Abs(DX)>180 Then DX=DX+Sgn(DX)*360
		Return (C + DX*S + 360) Mod 360
	
End Function

*as it should output the tweened angle in the valid range of 0 ... 360*

Eric	(Posted 2006) [#20]

If it suits your needs... My function returned an offset to the Angle. It works for what I needed.

If you notice in my loop I add DX to the Angle.

Robert Cummings

(Posted 2006) [#21]

Thank you for all your kind replies - trying them all out now. I can't get Floyd's one working properly because I am giving it bad data.

What is the cleanest, most consistent way to point one thing at another to get an angle between 0 and 360?

It seems to me atan2 returns some strange values sometimes. I'm trying to get atan2 working with floyds at the moment.

Will try all your suggestions though, and thanks!

Robert Cummings

(Posted 2006) [#22]

Basically I want to use Floyds routine to make one item look at another item but with tweening.

Here is the new code. How can I make it work with atan2 to make something point at something else? I tried but get negative spinning again.


Angle = Atan2( y2 - y1 , x2-x1 ) + 90
If Angle<360 Angle:+360
if Angle>360 Angle:-360

'NOTE: I assume something is wrong with how I generate Angle... it somehow breaks floyd's code below despite being in the range.

' Assumes p1 and p2 are in the range [0,360) and t is in [0,1].
Function TweenAngle#( p1# , p2# , t# )
	
	Local angle# = p1 + t * (p2 - p1)
	
	If p1 <= p2 Then Return angle
	
	angle :+ t * 360.0
	
	If angle < 360.0
		Return angle
	Else
		Return angle - 360.0
	End If
	
End Function

Brucey

(Posted 2006) [#23]

Atan2 can return either positive or negative results, depending on which quadrant of the unit circle the angle lies.

That is probably why you think it sometimes returns strange results.

:-)

Brucey

(Posted 2006) [#24]

This is the code I use in my game for determining angles between two points :

  Local angle:Float = ATan2(myVehicle.y - p.y, myVehicle.x - p.x)
  If angle < 0 Then
    angle = 360 + angle
  End If

..which always gives me the range, 0 >= angle < 360

Robert Cummings

(Posted 2006) [#25]

That and a little fiddling, has cleared it all up for me.

I want to say a big thank you, to everyone who took the time out to help me on this thread. Thanks to you, my game is even closer to completion! :)

Robert Cummings

(Posted 2006) [#26]

EDIT!

Told a lie! it's still buggy. I think the problem is with Floy'ds routine now, as it just doesn't work with this:

  Local angle:Float = ATan2(myVehicle.y - p.y, myVehicle.x - p.x)
  If angle < 0 Then
    angle = 360 + angle
  End If

Going to try yet more alternatives!

Robert Cummings

(Posted 2006) [#27]

No joy - it seems like an impossible task to get atan2 working with tweening. Do you think it needs a re-think?

None of the code above actually works when you test it in a simple point at the mouse cursor situation.

AntonyWells

(Posted 2006) [#28]

Not tested but should work

Function Tween#( ang1#,ang2#,tween# )
   local d1#,d2#
   if ang1>ang2
          d1 = ang1-ang2
         d2 = 360-ang1+ang2
         if d1<d2
               return ang1-d1*tween
         else
              return ang1+(d2*tween) mod 360
        endif
   else
         d1 = ang2-ang1
         d2 = 360-ang2+ang1
         if d1<d2
              return ang2-d1*tween
         else
              return ang2+(d2*tween) mod 360
         endif 
   endif
end function