Interpolation woes

[pekkavaa]

I'm not sure if I'm missing something here but Rocket's behaviour in between keys really bugs me. Let me present the problem visually:

I apologize for using Ground Control for the screenshot :)
I'd expect the first key to finish its interpolation and instantly change to interpolating the next key. But the curve seems to stay constant for a while which is very visible in some animations.

Is this the way it should work?

[kusma]

Yeah, this unfortunately is the way it should work, and it's not ideal. The reason is that the two keyframes are on different rows, and as such have different positions in time, so there will be a gap of one row there (your drawing shows half a row, but the gap is one row). The problem is with the model, it's not a bug; what you've specified is three segments, one with interpolation to next one, then one without. followed by another one with interpolation again. If you try moving the keys to have some spaces between them, you'll see that this (below) is what fundamentally happens:

The problem here is that the segment between 2 and 3 isn't zero-length, it's one row long.

There's been several ideas for how to fix this, but the problem is that they all require to change the network protocol, which breaks compatibility with other clients.

The seemingly simplest fix would be to allow the protocol to specify an incoming and an outgoing value for each key. This way, the same keyframe-location can be used for both values at the discontinuity. The bad part about this is that it doesn't directly lead to an easy editing model. Two values at the same location would need a more involved editor, with some switching between incoming/outgoing here, and displaying two values per row in a clean way. I suspect that this can be solved by diverging between the editor model and the player model, though.

However, this bring me to the next thing, and that is that if we want to break the protocol, I would like that we broke it a lot more at once; that is switch into sending arbitrary quadratic polynomial segments instead of the current list of row. value and mode per key. This will allow further editor features in the future without breaking the protocol again.

[pekkavaa]

Thanks for the explanation. My current workaround is just to make the tracker speed very fast, then the constant segments are much shorter.

[kusma]

@seece: Yeah, that's what I've been doing myself. It's kind of something you probably want to do anyway, because it allows for more precise sync-details (for demos where that matter). But it still sucks that it has to be worked around.

[eteeselink]

How about a button that marks a cell as "the value in this cell counts for the last frame of this row, not the first frame of this row"? I.e. just like you toggle interpolation mode with i, you could toggle value aligment with, say a and mark it visually somehow (i'd steal excel's "bottom align" icon).

This'll only get you in trouble if you want a single-row-long interpolation between two values, which is pretty uncommon and kusma's workaround works fine for that.

[kusma]

@eteeselink: Yeah, that could be an option. It'd still need a protocol extension to communicate this with the player, though.

[eteeselink]

Ah too bad. Somehow I had always assumed the protocol was per-frame but now that I think about that I realize how stupid it is :-) (i haven't touched this codebase for a decade or so) (fuck we're old)

[kusma]

So, this isn't really a bug per the current definition, even if it's annoying. I'll close this for now, but keep the problem in mind for the future.

[xwize]

Could approximate the behaviour with two extra interpolation modes, one that is linear that takes you to max - slope/row of the value. Then another that goes from there to 100% and quickly back down? Seems kind of hacky but it would be simpler than modifying things. You would just have to remember to use them both together.

[kusma]

I think a more appropriate hack would be to have an extra modifier that causes the interpretation of the value to be at the end of the row rather than the beginning. But this needs to be communicated to the player somehow, and that can't be done without breaking the protocol, I think. There's a lot of alternative client libraries for various programming language, which makes me a bit hesitant about this. I really wish I at least added some sort of "capabilities"-negotiation to the protocol so we could at least only communicate this with clients that knows how to deal with it...

But if we could, perhaps this could be encoded in the interpolation mode, and it would look at least a bit like what you suggest here, @xwize?

[eteeselink]

Hi! I still feel a bit responsible despite my inactivity, because this flaw is all my fault.

I think if I'd redesign this now, I'd make it implicit: if an interpolation ends on a value, assume that that value should hold at the end of the row. If an interpolation starts at that row, assume that that value should hold at the beginning of that row.
This makes for unambiguous behavior for everything with hard cuts, eg

1.0 |
    |
    |
5.0 
1.0 |
    |
    |
5.0

Then, if you don't want a hard cut, you'd just have to repeat the middle value on two rows:

1.0 |
    |
    |
5.0 
5.0 |
    |
    |
1.0

This means you kind of "abuse" the just-before-the-beat row for interpolation end values. If this gets you too low resolution, then just double the speed and the amount of rows (just like we did back in FT2 when we needed more control). While this is obviously hacky, it's also the kind of hack that fits, in spirit, with how trackers work, I think. It also matches with my intuition in other domains, eg financial reporting, where "all revenue in July" is the same as "all revenue between July 1 and July 31", i.e. both the start and end dates are inclusive.

The upside of this is that the editor does not need to change much, there's nothing new to understand for new users, and no new interpolations etc are needed either. The big downside of this is that it breaks semantics in the editor, i.e. files aren't backward compatible. It'd need a version selector somewhere, which sucks. In the protocol, I think that this could do exactly what kusma suggests in #63 (comment), send an incoming and outgoing value for each key (but I know nothing about the protocol)

I guess that all I'm trying to say is that what kusma calls the "seemingly simplest fix" doesn't require that the editor becomes more complex :-)

[kusma]

Hmm, that sounds like a quite clean semantic change. Yes, it'll change behavior, but only slightly, and it'll mostly do what people expect, I think. And it would be a player-only change, which seems neat. So no protocol behavioral change, and alternative clients can follow in suit as they like. Old players will just get the old behavior.

Should we just make the switch?

[kusma]

Hmmpf, this is a bit more awkward to code up than I thought. I kinda figured I could just adjust the calculation of t, but that's just half the story. We also need to change the way we find the keyframe to interpolate from, which gets very ugly quickly.

I'm starting to think this isn't reasonable to do without changing the protocol. Otherwise, the player ends up having to to too much strange magic...

[eteeselink]

Hmm, I'm not 100% sure I follow.

We also need to change the way we find the keyframe to interpolate from

By "from", do you mean that you need to find the start keyframe? Now I don't know anything about either the protocol or the player code, so pardon me for saying something stupid here, but if yes: why is this different than before? It's always just the (beginning of) the row that started the interpolation, right?

Not sure if this is related, but note that the design I propose loses one feature that the current behavior support: having a "middle" interpolation point. Eg this:

1.0 |
    |
    |
5.0 |
    |
    |
1.0

is currently a thing, but in what I propose it's meaningless, because it means this:

After all, when the 5.0 is the end of the first interpolation, the row value counts towards the last "tick" of that row, whereas when it's the start of the next interpolation, it counts towards the first "tick" of the same row. Unless I'm missing something fundamental, I think we should simply not allow this.

The user would need to be explicit about what they mean by putting an explicit end value and an explicit beginning value.
Does this make sense? I suppose that the easy way to do this is to not allow enabling an interpolation if the start or end value is already "taken" by another interpolation (but I'm not sure if and to what extent that would hurt editor UX).

Does this help address the problem or am I totally missing something?

[kusma]

Hmm, I'm not 100% sure I follow.

We also need to change the way we find the keyframe to interpolate from

By "from", do you mean that you need to find the start keyframe?

Yeah, pretty much. It's easy to adjust the interpolation within a set of keyframes based on the interpolation modes of both. I understood your suggestion to be about that (adjusting the interpretation of where the "target" row was). Perhaps I misunderstood.

Sadly that's not enough to fix this problem, because we get one linear segment of one row, and it's not as easy to make that one fill the missing part of the previous curve.

Now I don't know anything about either the protocol or the player code, so pardon me for saying something stupid here, but if yes: why is this different than before? It's always just the (beginning of) the row that started the interpolation, right?

Well, that's exactly the problem. We can't easily make these three segments into two continuous segments without complicated "searching" in the neighborhood and lots of conditionals on key-types. This get convoluted quickly.

Not sure if this is related, but note that the design I propose loses one feature that the current behavior support: having a "middle" interpolation point. Eg this:

1.0 |
    |
    |
5.0 |
    |
    |
1.0

is currently a thing, but in what I propose it's meaningless, because it means this:

After all, when the 5.0 is the end of the first interpolation, the row value counts towards the last "tick" of that row, whereas when it's the start of the next interpolation, it counts towards the first "tick" of the same row. Unless I'm missing something fundamental, I think we should simply not allow this.

Uhm, this is the trivial case. I don't think we should change behavior here. When there's no step key-frames, we should stick with the current interpretation of having the value on the beat (the start of the row). This is how things currently work, and what people would expect.

The interesting case is IMO this:

0.0 |
1.0
0.0 |
1.0 

Here, I think we want to see a saw-tooth shape instead.

For that to work, we would have to interpret this as a ramp up from 0 to 1 starting at row 0 and ending at row 2, where a new ramp up starting at row 2, and ending at row 4. This would mean that we would somehow have to "move" the interpretation of the 1.0-keyframes to the following row.

Since we're binary searching (without considering the interpolation-type) for the segment to interpolate, this gets tricky. And because the editor pretty much just sends the keyframes verbatim to the client, as delta-changes as we edit, we kinda need to keep this representation as-is.

The only viable option I can see is to have two versions of the track-data, one from the editor and one that has been modified to fixup interpolation quirks. Now, I have some patches going in this direction anyway, so maybe I'll play a bit more around in that direction; I kinda wanted to "bake polynomials" out of the keyframes instead anyway.

You can have a look at that work here. This branch isn't quite what we want, because it doesn't make two versions, but rather computes the b, c and d terms from the a terms and the interpolation mode. But I think it can be nudged where we need it.

The user would need to be explicit about what they mean by putting an explicit end value and an explicit beginning value.
Does this make sense? I suppose that the easy way to do this is to not allow enabling an interpolation if the start or end value is already "taken" by another interpolation (but I'm not sure if and to what extent that would hurt editor UX).

Does this help address the problem or am I totally missing something?

Right, but this kinda misses the point; this breaks the protocol, and with the number of alternative clients, I really want to avoid that.

If we were to redesign the protocol, I would do things quite differently. First off, I would rather send a list of polynomials directly instead. That would allow for much more flexibility; the editor could implement pretty much any curve-type, and send an approximation to the client using piece-wise polynomials, for instance. Secondly, I would add sub-row precision. Third, I would add capability negotiation so we could add more features later.