F-curve (timeline with keyframes)

Monkey Forums/Monkey Programming/F-curve (timeline with keyframes)

Leo Santos

(Posted 2011) [#1]

Hi,

I'm trying to create a Curve class that returns a value for any arbitrary time, like this: GetValue(time).
It contains Keyframe objects which are associated with frames, like this:

(time=0, value=20) ----------- (time=15, value=50) ---------- (time=30, value=100) ----------- etc.

If I use a IntMap<Keyframe> where the map's key is the keyframe's time, I can easily retrieve the values for existing keyframes, but.... how can I figure out the two closest existing keyframes to any arbitrary time? Maybe using a Map isn't the best approach? Stack? List? Help!!!

Here's some code that doesn't work.
The GetNext(time) and GetPrevious(time) methods return null, causing it to fail. Those methods are supposed to find the closest keyframes to 'time'.

Class Curve
	
	Field timeline:= New IntMap<Keyframe>
	
	Method GetValue:Float(time:Float)
		If timeline.Contains(time)
			Return timeline.Get(time).value
		Else
			Local prv:Keyframe = GetPrevious(time)
			Local nxt:Keyframe = GetNext(time)
			Return Interpolate( prv.value, nxt.value, (time - prv.time) / (nxt.time - prv.time) )
		Endif		
	End Method
	
	Method GetPrevious:Keyframe(time)
		'How do i figure out the closest Keyframe to 'time' ?????????
		'This will yeld a NULL object, causing the program to fail at GetValue()
	End Method
	
	Method GetNext:Keyframe(time)
		'How do i figure out the closest Keyframe to 'time' ?????????
		'This will yeld a NULL object, causing the program to fail at GetValue()
	End Method
	
	Method AddKey(value:Float, time:Int)
		Local keyframe := New Keyframe
		keyframe.value = value
		keyframe.time = time
		timeline.Set(time, keyframe)		
	End Method		
	
	Method Interpolate:Float(a:Float, b:Float, x:Float)
		Return  a * ( 1 - x ) + ( b * x )
	End Method

End Class


Class Keyframe

	Field value:Float
	Field time:Int
	
End Class


Function Main()

	Local curve := New Curve()
	
	curve.AddKey(10,0)
	curve.AddKey(8,20)
	curve.AddKey(15,50)
	
	Print curve.GetValue(20) 	'This is an existing keyframe time, so it returns the correct value
	Print curve.GetValue(40)	'Tries to get the value for frame 40 and fails miserably
	
End Function

slenkar

(Posted 2011) [#2]

you may have to iterate through the map to find the closest keyframes

look into the map docs to find the iterator

Leo Santos

(Posted 2011) [#3]

Hi,

I'm doing something like that, but the problem is that it's awfully inefficient... it works fine for a handful of keyframes, but the more you add the longer it takes to find the nearest keys, since it has to basically iterate through the whole list.

A long scene with a few full characters with multiple child parts each can be hundreds, if not thousands, of keyframes that need to be processed per Update... well, I'll go with this for now, and if I run into performance issues I can always "bake" or cache the animation - pre-calculate the whole curve, which would eat more memory but would also process faster.

Here's my most recent example... run it to see a couple sample curves plotted. I can add this to the code archives, but I'm sure you guys can improve it before I do so! :-)

Meanwhile, if anyone knows a good algorithm for this would be awesome! There's gotta be a more efficient way...

Cheers!

Strict

Import mojo

Class Curve
	
	Const LINEAR:Int	= 0
	Const HOLD:Int	= 1	'No interpolation
	Const CUBIC:Int	= 2	'Smooth
	Const COSINE:Int	= 3	'Ease in/out
	
	Field resolution:Int = 5		'Resolution in pixels. The lower this value, the smoother it looks when plotted
	
	Private
	
	Field timeline:= New IntMap<Keyframe>
	Field first:Keyframe, last:Keyframe
	Field max:Float, min:Float
	
	Public
	
	Method GetValue:Float(time:Float)
		If timeline.Contains(time)
			Return timeline.Get(time).value
		Else
			Local prv:Keyframe = GetPrevious(time)
			Local nxt:Keyframe = GetNext(time)
			If prv <> nxt		'if they're the same, no need to interpolate. In fact, it causes a division by zero.
				Return Interpolate( prv.value, nxt.value, (time - prv.time) / (nxt.time - prv.time), prv.style )
			Else
				Return prv.value
			Endif
		Endif		
	End Method
	
	Method GetPrevious:Keyframe(time:Int)
		Local temptime:Int = time
		Local current:Keyframe
		For Local k:Keyframe = Eachin timeline.Values()
			If Not current Then current = first	'gets first value
			If k.time < time + 1
				current = k
			End If
		Next
		Return current
	End Method
	
	Method GetNext:Keyframe(time:Int)
		Local temptime:Int = time
		Local current:Keyframe
		For Local k := Eachin timeline.Values()
			If k.time > time - 1
				current = timeline.Get(k.time)
				Exit
			End If
			current = last	'gets last value
		Next
		Return current
	End Method
	
	Method AddKey:Void(value:Float, time:Int, style:Int=LINEAR)
		Local keyframe := New Keyframe
		keyframe.value = value
		keyframe.time = time
		keyframe.style = style
		timeline.Set(time, keyframe)
		If first
			If keyframe.time < first.time Then first = keyframe
		Else
			first = keyframe
		End If
		If last 
			If keyframe.time > last.time Then last = keyframe
		Else
			last = keyframe
		End If
		If max
			If keyframe.value > max Then max = keyframe.value
		Else
			max = keyframe.value
		End If
		If min
			If keyframe.value < min Then min = keyframe.value
		Else
			min = keyframe.value
		End If
		
	End Method		
	
	Method Draw:Void(xStart:Float, yStart:Float, width:Float, height:Float, drawKnots:Bool=True)
	
		Local x:Float = 0
		Local wx:Float
		Local wy:Float
		Local amplitude:Float = max - min
		Local prevX:Float, prevY:Float
		
		Repeat
			wx = x / (last.time/width)	+ xStart								'fits to width and applies offset
			wy = GetValue(x) / (amplitude/height ) + yStart - first.value		'fits to height and applies offset
			If Not prevX													'first frame fix
				prevX = wx
				prevY = wy
			Endif
			DrawLine( prevX, prevY, wx, wy )								'Draws interpolated values
			prevX = wx
			prevY = wy
			x += ( resolution / (width/DeviceWidth()) )						'adjusts the steps based on the size of the curve on the screen
		Until x > last.time
		
		'Draws last segment
		DrawLine( prevX, prevY, (last.time / (last.time/width) + xStart), (last.value / (amplitude/height ) + yStart - first.value ) )								'Draws final segment
		
		If drawKnots
			For Local k:Keyframe = Eachin timeline.Values()
				wx = k.time / (last.time/width)	+ xStart
				wy = k.value / (amplitude/height ) + yStart - first.value
				DrawCircle( wx , wy , 2 )
			Next
		End If

	End Method
	
	Function Interpolate:Float(a:Float, b:Float, x:Float, style:Int=LINEAR)
		Select style
			Case HOLD
				Return a
			Case COSINE
				Local prc:Float = ( 1 - Cos( RadToDeg( x * PI ) )) / 2
				Return  a * ( 1 - prc ) +  ( b * prc )
			Default 'LINEAR
				Return a * ( 1 - x ) + ( b * x )
		End Select
	End Function
	
	Function RadToDeg:Float( rad:Float )
		Return rad * (180/PI)
	End Function
	
	Function DegToRad:Float( angle:Float )
		Return angle * (PI/180)
	End Function
	
End Class


Class Keyframe
	Field value:Float
	Field time:Int
	Field style:Int
End Class


Function Main:Int()
	Local myApp := New PlotCurve
	Return 0
End Function


Class PlotCurve Extends App

	Field curve := New Curve()
	Field linearcurve := New Curve()

	Method OnCreate:Int()
		'Lets add some keyframes...
		For Local x:Int = 0 To 600 Step 100
			curve.AddKey(Rnd(0,100),x,3)
			linearcurve.AddKey(Rnd(0,100),x,0)
		Next
		SetUpdateRate(10)
		Return 0
	End Method

	Method OnRender:Int()
		Cls
		Local width:Float = DeviceWidth() - 200
		Local height:Float = DeviceHeight() / 4
		
		curve.Draw(100,100,width,height)
		linearcurve.Draw(100,height + 100, width, height)

		Return 0
	End Method

End Class

Samah

(Posted 2011) [#4]

Some suggestions:

Use a dynamic array of KeyFrames rather than a Map. Define the array fairly large, then in AddKey, double the size using array.Resize() if you need extra space.

Get rid of the DegToRad and RadToDeg methods, and instead multiply by a constant float. Two reasons for this:
1) Putting degrees/radians calculations in a separate method is just that: another method call. The less method calls the better if you're compiling for Android (or any platform, really).
2) Division is expensive, and if you can cache the result, all the better. Precalculating 180/PI and PI/180 as separate Const definitions will be much faster as (correct me if I'm wrong, Mark) constants will be calculated and substituted at compile time.

You're using calculations such as last.time/width and amplitude/height multiple times. Consider calculating them once and store them in local variables.

Cache DeviceWidth() in Draw() before entering the Repeat loop.