timeline from structure

fsk's picture

the idea is to have a patch that, given a structure of points (with time values), would interpolate between them. i think this is easy enough to do that i could make it but, there is one thing that confuses me. how to get the two points that are needed for the current time. i mean, there has to be a smarter way of doing it than going through the whole array looking for the two points with the time closest to the current one.

this has been bugging me for some time before i got the idea for this patch (i wondered how the timelines and value historian patches do it).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

cwright's picture
Re: timeline from structure

your friend, the binary search

lunelson's picture
Re: timeline from structure

I've been wondering about this too because I want to implement bezier speed curves; but bezier curves are parametric so you need to plot them out first and then sample y for a given x by first finding the x you want

-- did you manage to get this working? Also, how do you generate this structure in the first place and how do you choose how detailed the structure should be i.e. how many data points?

usefuldesign.au's picture
Re: timeline from structure

Given that it's a (linear) time based patch you are making, why can't it keep track of which part of the sequence it is up to? Interpolate from Point A to Point B over period A, then from Point B to Point C over period B,…?

I made a similar thing that spins { X_Rotation, Y_Rot, Z_Rot } on 3D transform patch according to an array of Rotation values in a structure { [30,45,30] , [90,270,-90] , … }. Randomise patches chooses the next with Structure element by index patch. It flip flops between two [X_Rot, Y_Rot, Z_Rot] generating macros which have the randomisation patches joined to the structure which comes in as XML with all the pre-determined spin positions.

usefuldesign.au's picture
Re: timeline from structure

Toneburst posted a bezier curve generator way back I seem to remember. Try a search. Gave reference to the code source (web page explaining the algorithm) too.

lunelson's picture
Re: timeline from structure

Yeah I've got the math worked out already, at least as far as generating the curve. It's just the section of the curve from 0 to 1 so the formula ends up having a few terms removed also. I attached some shots of it in Grapher, where "inf" represents the length of the control handles, which would be positioned horizontally relative to the start/end points. You can see how it affects the curvature, in the three different shots. The problem is that if you generate a structure of x-y values, the index of this structure isn't useful because it relates only to the progression of "t" (not to be confused with "time"), which both coordinates are functions of. It has no linear relation to either x or y; to use this as an interpolation curve I need y vs x, and that means searching the structure for the sub-structure where x is equal to my reference (current time for example) and returning the correlated y value. Basically I figure: one JS patch to generate the structure (once, at the beginning of the run-time), and one to parse the structure on each frame, finding the nearest matching x and returning the y. But to do this I need to understand more about structures and arrays etc., plus a search routine and it's just over my head (I did try looking at "binary search" but it beat me)

PreviewAttachmentSize
influence_00.png
influence_00.png115.81 KB
influence_05.png
influence_05.png116.74 KB
influence_10.png
influence_10.png115.54 KB

fsk's picture
Re: timeline from structure

well, i did kind of manage to get it working. you feed it a structure of structures (a 2D array) where the first element of the second structure is time (structure[i][0]). it will then return the value(s) for a given time. right now it just uses linear interpolation. i didnt finish it because i think this is not the right approach for a qc patch (and i had other stuff to do). the problem is, that a user can put anything inside the structure and i would have to check for all the types and stuff to keep it from crashing if the user mixed types (what to do if someone "wants" to interpolate between an image and a number:)).

im thinking now that it should just be a quick search patch which would return the required index and let you deal with the interpolation of the stuff with other patches. so it boils down to thinking about what output would be most useful to reduce the work needed in qc.

Quote:
Also, how do you generate this structure in the first place and how do you choose how detailed the structure should be i.e. how many data points?

i dont. one has to generate the structure outside the patch using a queue, javascript or kinemes structure tools. the requirement for it to work are that the time values need to be the first element and that times are sorted from smallest to biggest.

fsk's picture
Re: timeline from structure

heres the quick search plugin. it performs a quick search on the provided structure. It searches based on time. The provided structure can be:

a) an array of numbers (times)

b) an array of arrays which have the time value as its first element

c) an array of dictionaries which have an element with the key 'time'

In all cases the elements MUST be sorted by time. there is nothing in QC that will prevent you from giving the patch a structure it cant handle in which case the behavior is undefined.

If elements share the same time value the patch will return the index of the last one with that value. the "interpolation time" output ranges from 0-1. if its value is 0 a match was found (or the closest answer is the first element) and its index is "index1". if its value is 1 the answer is the last element (or the closest answer is the last element) and its index is "index2". if its anything in-between then "index1" is the index of the first element below the searched value and "index2" is the index of the first one above it.

i hope thats clear enough:).

PreviewAttachmentSize
Quick Search.plugin.zip21.58 KB
QStest.qtz11.65 KB

cybero's picture
Re: timeline from structure

Interesting plugin, just been experimenting with getting randomized structures out so I'll be looking forward to trying this out . Iespecially like the fact that if I do without the Boolean Demultiplexer that I can have all three types of structuring running concurrently.

Is there some way of making time run negatively in QC with this patch?

lunelson's picture
Re: timeline from structure

Thanks for posting this fsk

-- but somehow I can't get it to work. I copied the JS code nearly exactly from another post on the forum which was generating a structure of 3d coordinates, and yet I can't get my 2d set right. Something missing, that I don't see although the code is virtually identical to ones that do work

This is what I have for the JS patch, attempting to generate a bezier curve structure spanning from [0,0] to [1,1] -- the math is based on the graphs in my post above...

Also attached my attempt in QTZ form

var result = new Array();
result.Curve = new Array();
 
function (__structure Curve) main (__number Samples, __number Influence)
{
    var i = 0;
    for(i=0;i<Samples;i++) {
      t = i/Samples;
      x = (1-3*(1-2*Influence))*t*t*t + (3(1-2*Influence)-3*Influence)*t*t + 3*Influence*t; 
      y = -2*t*t*t + 3*t*t;
      result.Curve[i] = new Array();
      result.Curve[i][0] = x;
      result.Curve[i][1] = y;}
    return result;
}
PreviewAttachmentSize
Bezier Structure.qtz4.96 KB

usefuldesign.au's picture
Re: timeline from structure

I'm on 10.5† Managed to fix your Javascript though and the structure patches to parse the data to your Interpolate patch.

var result = new Array();
result.Curve = new Array();
 
function (__structure Curve) main (__number Samples, __number Influence)
{
   var i = 0;
   var inf = Influence;
   for(i=0; i< Samples; i++) 
       {
      t = i / Samples;
      x = (1-3*(1-2* inf))*t*t*t + (3*(1-2* inf) - 3 * inf)*t*t + 3* inf *t; 
/*
old line was:         x = (1-3*(1-2*Influence))*t*t*t + (3   missing "*" here    (1-2*Influence)-3*Influence)*t*t + 3*Influence*t; 
*/
      y = -2*t*t*t + 3*t*t;
//      changed from array to object seems to work can tell you why ;) ud      
      result.Curve[i] = new Object();
      result.Curve[i]["X"] = x - .5;
      result.Curve[i]["Y"] = y - .5;
//      result.Curve[i]["Z"] = 0;
      }
    return result;
}

That comment should read "can't tell you why" not "can…" :)

† Part of your .qtz file didn't load on my Mac maybe comp is 10.5 incompatible (you can highlight incompatability from a menu option – at least you can in QC3 for Tiger incompatible patches).

PreviewAttachmentSize
Bezier Structure II.qtz6.76 KB

usefuldesign.au's picture
Re: timeline from structure

Nice work fsk!

I've hacked together numerous attempts at envelope patches in the past using standard patches. Being a plugin seems to make your Quick Search Plugin ultra responsive.

Why not add a third element to each point's array for the interpolation mode (ie. index values [0-12] where 0 is linear, 1 is Quadratic In,…). This can be patched to the interpolate patch and so adjust the curve shape for each step of the envelope.

ps Can you make plugins with standard C or do you have to use Cocoa (I'm still trying to get my head around the syntax of Cocoa as my C is pretty novice level). I'd really like to make some very simple data-array crunching plugins to get a speed bump.

fsk's picture
Re: timeline from structure

Quote:
Is there some way of making time run negatively in QC with this patch?

At first i didnt really understand what you mean here. but i guess you want to search for negative numbers. i think i did a time based patch because the timeline patch was still on my mind. it doesnt really make sense with quick search. ill change that in the update. i also noticed that i copy the whole array before searching which makes it really slow for no reason. this is also fixed.

lunelson's picture
Re: timeline from structure

Thanks usefuldesign, and everyone else --

I also finally managed to fix the JS code and get the structure generating correctly, just about half an hour ago;

but let me point out re: your solution, usefuldesign: this way of parsing the array is what I am trying to work around, because you are parsing by index (essentially, with the "t" value), and not by the x value. Take a look at my attached graph example and you'll see how the spacing of the dots gives it away: these are tracking with y in relation to x, whereas the dot positions in your solution are tracking with x and y independently in relation to t.

fsk, would you be willing to post a javascript version of your quicksearch? I realize your plugin (coded in C?) is probably working much faster, but what I am building needs to run on systems that have only a standard Leopard or Snow Leopard install, so no custom patches or plugins.

Thanks again, for all the feedback here.

PreviewAttachmentSize
Graphed Bezier2.qtz15.34 KB

lunelson's picture
Re: timeline from structure

OK so my pathetic attempt to do this same thing in JS (allowing only for the restricted example of my own 2D bezier curve structure) is below. I've tried to do something that will spit out two indexes: the two nearest in value to what I'm looking for. But it's just crashing QC.

Any tips on making this work? Like I said in my post above, I need my comp to be able to run on other machines with only standard patches....

Any help appreciated

var result = new Object();
function (__index Index1, __index Index2) main (__structure Struct, __number Time, __index Length) {
   lo = 0;
   hi = Length-1;
   mid = Math.floor((lo+hi)/2);
   while ((hi-lo)>1) {
      sample = Struct[mid][0];
      if (sample > Time) {hi = mid-1;}
      else if (Time > sample) {lo = mid+1;}}
   result.Index1 = mid; 
   result.Index2 = mid+1;
   return result;
}

cybero's picture
Re: timeline from structure

I do love the way result.Curve = new Object(); makes for a very straggly line **:-)*. Good example with result.Curve = new Array(); BTW. The attached redraft really shows the distinct difference between the two approaches.

PreviewAttachmentSize
Graphed Bezier2-Compared.qtz27.21 KB

fsk's picture
Re: timeline from structure

here is an updated version.

-it has a new name (have no idea where i pulled quick search from)

-its faster (fixed the line that would copy the structure before searching it :/)

-its no longer time based so you can search for negative values

-it no longer supports (it never really did) the keyed approach

-you can now set the index in which it searches the arrays

i also made a new example composition

PreviewAttachmentSize
Binary Search.plugin.zip19.57 KB
BStest.qtz17.85 KB

fsk's picture
Re: timeline from structure

Quote:
fsk, would you be willing to post a javascript version of your quicksearch?

i cant. i didnt write any binary search code. the plugin uses the function which comes with CFArray. im sure there are some javascript binary searches out there though:).

usefuldesign.au's picture
Re: timeline from structure

Neat!

lunelson's picture
Re: timeline from structure

Nice work fsk

lunelson's picture
Re: timeline from structure

fsk,

would you care to share the source code of this? Or are you sharing it for free use? It's forming kind of a key point in what I'm building right now....

thanks LMN

fsk's picture
Re: timeline from structure

hey lunelson,

heres a simple "licence".

you can use however you like. you cant blame me for any problems:). giving credit is not necessary but it doesnt hurt.

cheers

cybero's picture
Re: timeline from structure

Smart work fsk, you should be designing rollercoaster rides :-)

Just opened up the example, and I'm wondering, why does the green square 'fail' to follow some line points as closely as it does some others ?

edit - just noticed, it's traversing the red key points - love the way it reverses BTW :-) -

N.B - no shouting letters •~

lunelson's picture
Re: timeline from structure

fsk wrote:
you can use however you like. you cant blame me for any problems:). giving credit is not necessary but it doesnt hurt

thanks fsk

L