Linear interpolation of two vector arrays with different lenghts

Math and Physics Programming C++ 2D Graphics

Started by ManitouVR October 10, 2019 04:02 AM

54 comments, last by ManitouVR 4 years, 6 months ago

Author

October 10, 2019 04:02 AM

I have two curves. One handdrawn and one is a smoothed version of the handdrawn. The data of each curve is stored in 2 seperate vector arrays.

Time Delta is also stored in the handdrawn curve vector, so i can replay the drawing process and so that it looks natural.

Now i need to transfer the Time Delta from Curve 1 (Raw input) to Curve 2 (the already smoothed curve).

Sometimes the size of the first vector is larger and sometimes smaller than the second vector.
(Depends on the input draw speed)

So my question is: How do i fill the whole vector PenSmoot.time with the correct interpolated values?

Case 1: Input vector is larger


PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
PenInput.time[5] = 100
PenInput.time[6] = 20
PenInput.time[7] = 3
PenInput.time[8] = 9
PenInput.time[9] = 33

Case 2: Input vector is smaller


PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
                             PenSmoot.time[5] = ?
                             PenSmoot.time[6] = ?
                             PenSmoot.time[7] = ?
                             PenSmoot.time[8] = ?
                             PenSmoot.time[9] = ?

3D Artist

alvaro

21,604

October 10, 2019 10:42 AM

If I understand correctly, you have parametric descriptions of curves ("time" is the parameter), where you know the position for certain set of parameter values, and you want to interpolate between two such descriptions.

I would start by taking the union of the sets of parameter values. Describe both curves using this extended set of parameter value and then interpolate the values at each point.

Does that make sense?

Never mind. I think I misunderstood the question.

ManitouVR

Author

October 10, 2019 02:02 PM

Hello, thanks for trying.

I need to transfer the Time Deltas (milliseconds it took from one point to the next) from the Raw input curve to the smoothed curve.

3D Artist

JohnnyCode

1,084

October 10, 2019 02:37 PM

I don't believe you need to inerpolate, functionalize this information?

Zakwayda

2,389

October 10, 2019 02:48 PM

I'm probably also not understanding the question, but:

Since you can switch back and forth between delta times and absolute times easily enough, it seems like you could assign each of the points of the left-hand curve an absolute time.

For each of the points on the right-hand curve, you can find the closest point on the left-hand curve, using the segments between the points on the left-hand curve and a 'closest point on segment' function. One you have a segment and a closest point, you can compute an interpolation value between the endpoints of the segment. Then you can use that interpolation value to compute an absolute time for the right-hand point in question. Once you have absolute times, you can of course derive the deltas if needed.

Again, I suspect I'm also misunderstanding and that the above solution may be irrelevant or naively incorrect, but maybe it can at least help advance the discussion.

alvaro

21,604

October 10, 2019 05:35 PM

I think I now understand the problem, and I know how to solve it using dynamic programming. I'll post something this evening.

ManitouVR

Author

October 11, 2019 12:43 AM

@JohnnyCode You mean instead of interpolate it shoud be functionalized? What does this mean?

@Zakwayda I actually record the absolute times and calculate the deltatimes after mouse release. So i have both times already.

I think you understand exactly what i mean. Just one thing that i want to point out is that the size/lenght of the curves vectors can and will be different

based on the input draw speed. So sometimes the handdrawn vertex array is larger than the smoothed one and sometimes vice versa.

I store the data in a struct like this and i use SFML


struct Pencil 
{
	sf::VertexArray vertices;
	std::vector<int> pressure;
	std::vector<sf::Int32> timeAbslt;
	std::vector<sf::Int32> timeDelta;
};

@alvaro Dynamic programming. I didnt know about that but what i have found out it sounds like what Zakwayda said. Splitting the problem into sections and solving them one by one.

Thank you all for your help!

3D Artist

Zakwayda

2,389

October 11, 2019 01:01 AM

13 minutes ago, C3D_ said:

I think you understand exactly what i mean. Just one thing that i want to point out is that the size/lenght of the curves vectors can and will be different

based on the input draw speed. So sometimes the handdrawn vertex array is larger than the smoothed one and sometimes vice versa.

alvaro may have something different in mind for you, but for what it's worth, the solution I proposed is intended to account for differing numbers of points between the two curves. The idea is that for each point on the second curve, you find the closest point on the first curve (treating the first curve as a series of line segments), and then use interpolation to find the absolute times based on that. With this approach, the first curve could have 3 points and the second curve 300, or vice versa, and it should still work.

It it's not clear what I'm describing, I'll be happy to elaborate. (Or maybe alvaro will offer a better solution in the meantime.)

ManitouVR

Author

October 11, 2019 02:15 AM

Hello,

Paddy from stackoverflow made a demo here for me.

Iam still integrating it into my program and testing it.

But just so everybody knows.

@Zakwayda Okay. I understand. Thank you very much. I will test paddy's code and then catch up.

3D Artist

Zakwayda

2,389

October 11, 2019 02:32 AM

I looked at the demo code you linked to. I'm not entirely sure it addresses your problem. Among other things, it performs no resampling if the point sets have the same number of points, which doesn't seem to fit your use case.

I'm not saying the demo isn't what you want (I didn't analyze it that carefully), but if you find you're still not getting the behavior you want, you could post back. (I'll also mention that it's possible a solution - not necessarily the solution in the demo, but any solution - could give you results that maybe look correct, at least for certain input, but aren't actually correct.)

[Edit: Thinking about it a bit more, I'm pretty sure that code is not what you're after. I'm not saying that with certainty - I could be wrong ? But it's my initial impression.]

Linear interpolation of two vector arrays with different lenghts

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linear interpolation of two vector arrays with different lenghts

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines