On 10/09/2014 16:58, Lars Rohwedder wrote:
> I've got the following problem:
> 
> Given an array of {t, Point} where t is a floating point number, between
> 0 to 1, and Point is a point in the 2D plane. (The array can be sorted
> by ascending t.)
> 
> Now I want a formula f(t) that returns a "smooth path" going through all
> these points.
> 
> It is AFAIK what Povray's spline feature does, right? But I want to use
> that formula in my own C++ program. :-)
> 
> 
> I googled around and found many sites full of explanations and formulae
> about "Bezier splines", "B splines", Lagrange polynomials etc. many math
> stuff I just don't care about.
> 
> I also found libraries (e.g. GNU Scientific Library) but these also look
> too complicated for me, so I cannot even say whether and how they might
> do what I want to. :-(
> 
> Perhaps one of you can give me some hints how to find such a formula.
> The reward would be a nice animation, I could present to you all
> afterwards. :-)
> 
> 
> Lars R.
> 

Splines is the way to go. Now, there is more than a single solution,
even for splines which match their input points (yep, some kinds do not).

Do you want it simple, or with C2 continuity (speed is continuous too),
or even C4 continuity (acceleration is also continuous) ? (in regard to
t's derivatives)

According to the answer, the kinds of spline you can use is different.

And you probably do not need to handle the generic case, so specialising
your code is going to make your life easier.

Do not look at the spline solver of povray (in sphere sweep), it is
dedicated to finding the intersection of a straight line with a 4D
splines (fourth dimension being the radius of the sphere).

You can get some insight in source/backend/math/splines.cpp, but it
covers many type of splines.

Basically, from the list of {t, point} you get a sequence of segments
and for each segment some coefficients are computed based on the around
points and t values. (from 2 to 4 points are used).
(notice that the coordinates of the points are independent on the
spline: only t and a selected axis influences the value along that axis)

When evaluating the point, first find the segment, then use the computed
coefficients to compute the value for an axis (replacing t between start
and end with a value between 0 and 1, the coefficient being used with a
polynomial made so that 0 give the point at start, and 1 the point at end.

The hard part is of course the computation of the coefficients.

-- 
IQ of crossposters with FU: 100 / (number of groups)
IQ of crossposters without FU: 100 / (1 + number of groups)
IQ of multiposters: 100 / ( (number of groups) * (number of groups))

Post a reply to this message