segment envelopes in AV editors
BlitzMax Forums/BlitzMax Programming/segment envelopes in AV editors
| ||
| Imagine those audio or video editors where you place segment-envelopes over a track (to change, say: level, panning, or brightness, contrast, etc. over time). How does one create such a mechanism? I imagine an array of point types, where each point has a "time" and "value" field. How to know which value belongs to any given time index? Related: how to know which points are visible within a given time lapse? (assuming you also need the first points outside of the visible area in case a segment-line start or ends outside that ara.) I figure running through the whole envelope content, brute-force, is not really a nice solution.. :P |
| ||
| I think you have to make a sort of interpolation based on time. Like keyframing. If Point A is on time 00:00 and has a value of 100, and point B is on 1:00 and has a value of 50, If you're viewing the value placed at 0:30, the value should be value of: formula: (AValue * (CurrentTime-ATime) + BValue * (BTime - CurrentTime)) / (Btime -ATime) First of All, in this example, convert all time to millisecs: A Time = 0 B Time = 60000 Current Time = 30000 then with the given values: A Value = 100 B Value = 50 Current Value = ? Apply the formula: (100 * (30000 - 0) + 50 * (60000 - 30000)) / (60000-0) = 75 Current Value is 75. It is logical as it is the middle point between this two keyframes. |
| ||
| Interpolation itself is not a problem, I was more aiming at: How to find the two segmentpoints a given time-index is on, out of -say- 1000 points? You do need those 2 points to interpolate! |
| ||
| The nearest smaller one, and the nearest bigger one. Store them sorted by time and make a quick search. It is fast and easy. If you store them on an array sorted by time, you can perform a indexed search wich would be ultra fast to get the two interpolation points with their values. |
| ||
| That indexed search was what I wasn't sure about, that's like brute-force, I wondered if there would be a faster way perhaps. I mean, imagine those AV apps, with 40+ tracks and possibly with more than one envelope per track. Are they searching those arrays all the time for each processed sample/frame? |
| ||
| Well, it is a very fast way to make that search. Let me elavorate: Imagine you have all this keyframes on a sorted array (sorted by time). Imagine an array of 1000 values, ok? the pseudocode should be something like:
Array:KeyFrames[Size]
MinValue:int = 0 'Minimum array bound on search
MaxValue:int = len(array) 'Maximum array bound on search
curValue:int = MaxValue/2 'Current seach position
CurTime = CurrentPositionOnTime 'Current position on time to search for the two interpolation points.
Done = False 'Simple flag
InterPolate = True 'Indicates if interpolation is needed or not
PointA:KeyFrame 'Smaller interpolation point
PointB:KeyFrame 'Bigger interpolation point
While Not done
if Array[curValue].Time<curTime then
if Array[CurValue+1].Time > CurTime
Done = True
PointA = Array[curValue]
PointB = Array[curValue+1]
Elseif Array[CurValue+1].Time<CurTime
MinValue = curValue
CurValue = MaxValue - MinValue / 2
ElseIf Array[CurValue].Time > CurTime Then
If Array[CurValue-1].Time < CurTime Then
Done = True
PointA = Array[CurValue-1]
PointB = Array[CurValue]
Done = True
Elseif Array[CurValue-1].Time > CurTime then
MaxValue = curValue
CurValue = MaxValue - MinValue / 2
Else
Done = True
Interpolate = False
endIf
Wend
If Iterpolate = True then
Iterpolate(PointA, PointB, curTime)
else
Value = Array[CurValue].Value
EndIf
This is a quick interpolation keyframe point search algorithm. It may need some fixing as it is pseudocode, but it works as a indexed search. |
| ||
| I haven't been able to get it right. There were all kinda illegal address readouts, and values were wrong. I'll C/P my stuff here, can you fill in the routine in that Value method? Don't bother about sorting variables and other potential methods, atm it's possible to have any envelope in that array, I'll sort out the sorting and the other luxe stuff myself. I figure the best would be to clip the low end of the requested time to 0, and the upper end to the biggest .time present in the whole array. So, if there's this segment in the array: 0.time 0 0.value 0 1.time 8 1.value 3 then the requested time should be limited to '8'. At least I think that would feel natural then.. ^_^ tnx |
| ||
| There is a faster way than linear brute force search. Use segment or interval trees. They will give you the next points to interpolate in O(log2(n)) instead of O(n) |
| ||
| example? |
| ||
Here you have some working BMX code.SuperStrict Type TKeyframe Field time:Int Field value:Float Method Set(t:Int,v:Float) time=t;value=v End Method Method Compare:Int(otherObject:Object) Local TempObj:TKeyframe = TKeyFrame(otherObject) If tempobj = Null Then Return -1 If TempObj.time>=time Return 1 Return -1 End Method End Type Type TTimeline Field array:TKeyframe[] Method Value:Float(curtime:Float) Local CurVal:Float = 0 Local MinValue:Int = 0 'Minimum array bound on search Local MaxValue:Int = Len(array) 'Maximum array bound on search Local curValue:Int = MaxValue/2 'Current seach position Local done:Int = False 'Simple flag Local DoInterPolate:Int = True 'Indicates if interpolation is needed or not Local PointA:TKeyframe 'Smaller interpolation point Local PointB:TKeyframe 'Bigger interpolation point ?Debug Local Counter:Int = 0 Local MaxIterations:Int = array.Length ? If curtime < Array[0].time Then Return array[0].value If curtime > array[Len(array)-1].time Then Return array[Len(array)-1].value While Not done ?Debug counter:+1 If counter > MaxIterations Then Throw "Array is not properly sorted." End If ? If Array[curValue].Time<curTime Then If Array[CurValue+1].Time > CurTime Done = True PointA = Array[curValue] PointB = Array[curValue+1] ElseIf Array[CurValue+1].Time<CurTime MinValue = curValue CurValue = MinValue + (MaxValue - MinValue) / 2 Else Done = True DoInterpolate = False CurValue = CurValue + 1 EndIf ElseIf Array[CurValue].Time > CurTime Then If Array[CurValue-1].Time < CurTime Then Done = True PointA = Array[CurValue-1] PointB = Array[CurValue] Done = True ElseIf Array[CurValue-1].Time > CurTime Then MaxValue = curValue CurValue = MinValue + (MaxValue - MinValue) / 2 Else Done = True DoInterpolate = False CurValue = CurValue - 1 EndIf Else Done = True DoInterpolate = False EndIf Wend If DoInterpolate = True Then CurVal = Interpolate(PointA, PointB, curTime) Else CurVal = Array[CurValue].Value EndIf Return CurVal End Method Method Interpolate:Float(PointA:TKeyframe, PointB:TKeyframe, Time:Float) Try Local Val1:Float = PointA.value * ((PointB.time - PointA.Time)-(Time -PointA.time)) Local Val2:Float = PointB.value * ((PointB.time - PointA.Time)-(PointB.Time -time)) Return (Val1 + Val2) / (Pointb.time - pointa.time) Catch Err:String Print "Error Calculation interpolation." + err Return 0 End Try End Method Method AppendKeyframe(time:Int,value:Float) Local s:Int=Len(array) array=array[..s+1] array[s]=New TKeyframe array[s].Set time,value 'maxindex=s+1 ' experimental, do keep these in mind, these were related to your algo! 'curvalue=maxindex/2 ' this one too.. End Method Method PrintKeyframes() If Not Len(array) Return Local value:Float Print "[ n] [time] [ value]" For Local t:Int=0 To Len(array)-1 value=array[t].value Print "["+RSet(t,2)+"] ["+RSet(array[t].time,4)+"] ["+RSet(Int(value),4)+"."+Replace(LSet(value-Int(value),5),".","")+"]" Next End Method Method SortArray() Array.Sort() End Method End Type Local t:TTimeline=New TTimeline t.AppendKeyframe 0,1 t.AppendKeyframe 5,4 t.AppendKeyframe 6,40 t.AppendKeyframe 16,100 t.AppendKeyframe 20,1 t.AppendKeyframe 28,-41 t.AppendKeyframe 31,27 t.PrintKeyframes ' to read out a value (and thus test the whole shebang) : ' Local i:Float For i = 1 To 50 Print "value "+ i + ": " + t.Value(i) Next End Remember this quick search and interpolation code won't work if the array isn't sorted by its time field. You can add the method compare to your TKeyFrame object to make the array sortable with the method Array.Sort() Anyway, I've added a array check on debug mode, to prevent infinite loops while you're creating your app. Just curiosity, what kind of app are you doing? I've tested it with an array of more than 1000 values, and in the worst case, it takes only 9 iterations in the while loop, this is much more less than the 999 iterations it would take in a linear calculation. |
| ||
| Will check after I finished a movie .. :P Apps: anything, it's just a segment-styled controller value that could be used for everything and its mother. Move things according to a segment-path, fade in/out according to a path.. just anything. I might just try to create an editor for it, in which one can select/move/create nodes, and scroll through the whole timeline. |
| ||
| Just to let you know how it performs: It took 1 milliseconds to process 2972 time interpolations with an array of 1000 keyframes, and it took 470 milliseconds to process 1011048.00 time interpolations with 20,000 keyframes. Making 1000 interpolations per second, thats a video of 17 minutes, calculated in 0.47 seconds), in my pentium IV 2.2 GHz |
| ||
| It seems to work \o/ tnx! btw, do you know this segment/interval tree stuff? |
| ||
| Segment search is what the algorithm I've provided is using. (just nine iterations to search a value in an array of 1000 values, as instance). Interval trees is not a good practicle in this particular case (IMHO), becouse you're using a sort of delta-timing and this would complicate a lot the interval calculation (I think). And in addition, you would need to get the nodes using also a search algorithm if there's any 'jump' on the time line, or if the timeline uses delta timing in the most optimized way. Not to mention the accumulation of rounding errors using float time values with float keyframes values. The algorithm provided could be surely optimized in some ways, but it performs great as it is. A hole minute of interpolations (calculating 1000 interpolations per second) with a total number of 10,000 keyframes took 1 millisecond on my computer. |
| ||
| Little Q in between: If I have an array of instances of a type with more than one field, what field is picked as 'key' when I do a .sort() ? |
| ||
The one defined in the compare function of the type in question. Type TKeyframe Field time:Int Field value:Float Method Set(t:Int,v:Float) time=t;value=v End Method Method Compare:Int(otherObject:Object) Local TempObj:TKeyframe = TKeyFrame(otherObject) If tempobj = Null Then Return -1 If TempObj.time>=time Return 1 Return -1 End Method End Type In this example, this compare method defined in the TKeyFrame, will permit a sort of an array of TKeyFrames by the field Time. |
| ||
nono, more in general I mean something like this:Type bla Field a:Int Field b:Int End Type Local m33p:bla[16] For Local t:Int=0 To 15 m33p[t]=New bla m33p[t].a=Rand(100) m33p[t].b=t Print m33p[t].a+" "+m33p[t].b Next Print "-------" m33p.sort() ' <- obviously doesn't do a thing For t=0 To 15 Print m33p[t].a+" "+m33p[t].b Next End How to sort the 'a' field, so that the 'b' field (and any other fields I might add later) will look mixed-up? Simply said: the way a database works.. |
| ||
| Yes I understand your question, but there is not anything more general. to make an object sortable it has to have a compare method. This method has to have this definition: Method Compare:Int(otherObject:Object) And it has to return -1 if the given object is smaller than the current one, and has to give 1 if it is bigger. Example of how to sort your bla object with the a field Type bla Field a:Int Field b:Int Method Compare:Int(otherObject:Object) 'First, we ensure the given object is another bla object. if not return -1 Local TempObj:bla = bla(otherObject) If tempobj = Null Then Return -1 'Then we make comparison If TempObj.a>=a Return 1 Return -1 End Method end type Adding this method to your object, makes it sortable, so: Type bla Field a:Int Field b:Int Method Compare:Int(otherObject:Object) 'First, we ensure the given object is another bla object. if not return -1 Local TempObj:bla = bla(otherObject) If tempobj = Null Then Return -1 'Then we make comparison If TempObj.a>=a Return 1 Return -1 End Method end type Local m33p:bla[16] For Local t:Int=0 To 15 m33p[t]=New bla m33p[t].a=Rand(100) m33p[t].b=t Print m33p[t].a+" "+m33p[t].b Next Print "-------" m33p.sort() ' <- obviously doesn't do a thing For t=0 To 15 Print m33p[t].a+" "+m33p[t].b Next End works as spected. If you want to sort ascending, use this method instead: Method Compare:Int(otherObject:Object) 'First, we ensure the given object is another bla object. if not return -1 Local TempObj:bla = bla(otherObject) If tempobj = Null Then Return -1 'Then we make comparison If a>=tempobj.a Return 1 Return -1 End Method |
| ||
| huh? So you're saying that the .sort() method automatically expects a user-made "Compare" method, and then it works automagically? |
| ||
| Yes, the sort method calls the compare method of each element in the array. If there is not a compare method, sometimes nothing happens, and sometimes it gives an unhandled exception. Also, The array can't contain null elements. But as you can see, this method is ultra easy to implement, and using this sort() algorithm sorts an array of about 10000 elements in more or less 20 milliseconds, so it is ultra fast. |
| ||
Aha, rite, I already couldn't figure out why there was a method like that, and nothing from the source calling it.  |
| ||
| On segment and interval trees. They are an extended type of full binary tree. But instead of simple nodes they use cross reference data within nodes to create intervals (interval trees use the hierarchy to connect parts *nodes* to an interval of the desired length with easily can be retrieved including points within) Segment trees instead use a different data structure on the nodes to create segments of static size (simpler) or if desired of any dynamic size using a given unit size and min - max as leaf set of the binary tree. Both are described in datastructure and algorithmic books normally. Don't think they are on too many pages on the net as they are not used that much in games. Games tend to use bin trees, quad trees, oct trees as well as bin triangle trees and the like for their handling. In BM, if you want something that is fast and simple, use a TMap This has 2 very usefull sideeffects: 1. as ziggy mentions you need sorted keys for interpolation. TMap do that for you at nearly free 2. they allow you easily retrieval of keys if you need to modify their data for some reason. (if you try to approximate something with the keyframes for example, this can be very important and usefull) You just get the value, remove it from tree, put the modified value with the key back into the tree |
| ||
| Just to add something to what dreamora has posted, The working BMX sample posted below, uses an array to store data (sorted by a key), and has a hash-table-like algorithm to find a value in the array. If the value is not found, it returns a weigted interpolation between the inmediate lower value and the inmediate upper value. The search algorithm is a modified segment quick search algorithm (or whatever it is called in english). Database indexes work in a very similar way. I would recomend this method as I don't see a good method (I can be wrong) to get the inmediate smaller value of a unexisting key value on a hashtable, and the inmediate upper one, without making what it is being already done in the example below. This method also allows duplicate 'key' values (duplicate keys support can be easily disabled if needed, but if you're automating different things like Pan and Volume, sometimes a Pan and volume keyframe can happen in the same timecode). |
| ||
| Working on a viewer which displays the whole bunch. Got a problem tho, When adding these fields to the Timeline object: Field rA:Int Field rB:Int Can you fill them in that Value method (after you found the correct value) with the correct keyframe indexes? So rA should contain the index of the startkeyframe and rB should contain the endkeyframe of the segment the value is on. If you get my point.. :P This way I can always read 'em out after I've found a value. I've tried to insert some lines here and there, but in some cases these segments are correct.. ..and since I'm usually crap in reading source which are not mine.. :-) |
| ||
| You want the two keyframes instead of the interpolated single value? |
| ||
| yes, well, I *also* want the two keyframes as well as the single version. The Value method is fine as it is.. as long as the two keyframes the value is on will be put into those 2 vars.. First I filled those vars in those If-EndIf parts, but that partly works. In my current viewer sometimes the first segment isn't drawn. E.g. My viewer checks x=offset and x=offset+canvaswidth-1, for the x=offset check I store rA as startarray, and for the x=offset+canvaswidth-1 I store rB for the endarray. Now I should have the first keyframe left outside my canvas and the first keyframe right outside my canvas. Then it's a matter of a 'for t=startarray to endarray-1' and line functions draw the line. But if the first keyframe starts at time:0 while the second keyframe starts at time:15, then an offset of 1 completely wipes the first segment (which was going from time:0 to time:15), etc. for other segments as well.. but NOT all! So I figure I get the wrong values back from that Value method. |
| ||
| I'm doing an application and I've changed to function to work on complex interpolations with more than one values. I've done a lot of changes to the source code, but it works ok here. Are you sure it is not a drawing issue? Are you rounding floats to Int? If you do so, take in consideration there could be a truncation so 0.99999 can be considered 0 instead of 1. That could give you the offest of 1 in some (not all) segments. |
| ||
| do you have maxgui? |
| ||
| yes, why? |
| ||
| ok, do you mind if you send you what I have, to take a peek at? |
| ||
| Send it to me, and I'll take a look |
   |