 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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.
Unfortunately there is no simple formula/algorithm and you'll need to do
a bit of maths and geometry if you're coding it all yourself.
Start by splitting the curve up into segments between each point and
have a separate f(t) for each segment. A cubic bezier will likely be
your best bet and it is guaranteed to actually go through all points and
you can control the gradient (in space and time) at the start and end of
each segment to match with the neighbours.
Here is a good demo to get the feel of what the control points do:
http://blogs.sitepointstatic.com/examples/tech/canvas-curves/bezier-curve.html
Wikipedia has the formulas you need, use the 2nd one from this section:
http://en.wikipedia.org/wiki/B%C3%A9zier_curve#Cubic_B.C3.A9zier_curves
P0 and P3 are your start and end points in each section, P1 and P2 are
"control points" that control the shape of the curve. Looking at the
equation further down for B'(t) you can figure out that for the adjacent
segments to match in gradient you need P1-P0 of one segment to equal
P3-P2 of the next section.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Lars Rohwedder <rok### [at] gmx de> wrote:
> Now I want a formula f(t) that returns a "smooth path" going through all
> these points.
Then what you want is probably this:
http://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline
(It links to some example implementations.)
You could also achieve it by drawing a bezier curve between each pair
of points, but in that case you need to generate the two control points
between them. (This, in fact, gives you more control over the curvature
of the spline, and even its tangent at each point.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I've been where you are chasing down formulas for my Polygon/Prism c++
program. I don't know where I got my first parametric equations from
(they where not perfect) I had to play with them until I got something
close to what POV prisms does. Of course prisms uses 4 types of splines
linear, quadratic, cubic and bezier. I have the formulas for the last 3.
void PCanvasPane :: ConDraw(point P,point P1, point P2, point P3)
{ double a_x,b_x,c_x,d_x,a_y,b_y,c_y,d_y,t;
int Xp,Yp,Ox,Oy;
if (Spl == 3)
{ a_x = P.x-3*P1.x+3*P2.x -P3.x; a_y = P.y-3*P1.y+3*P2.y
-P3.y;
b_x = 3*P1.x-6*P2.x+3*P3.x; b_y = 3*P1.y-6*P2.y+3*P3.y;
c_x = 3*P2.x-3*P3.x; c_y =
3*P2.y-3*P3.y;
d_x = P3.x; d_y = P3.y;
}
if (Spl == 2)
{a_x=-.5*P.x+1.5*P1.x-1.5*P2.x+.5*P3.x;
a_y=-.5*P.y+1.5*P1.y-1.5*P2.y+.5*P3.y;
b_x= P.x-2.5*P1.x+2.0*P2.x-.5*P3.x; b_y=
P.y-2.5*P1.y+2.0*P2.y-.5*P3.y;
c_x=-.5*P.x +.5 *P2.x; c_y=-.5*P.y
+.5 *P2.y;
d_x= P1.x; d_y= P1.y;
}
if (Spl == 1)
{a_x=0; a_y=0;
b_x= .5*P.x-P1.x+.5*P2.x; b_y= .5*P.y-P1.y+.5*P2.y;
c_x=-.5*P.x +.5*P2.x; c_y=-.5*P.y +.5*P2.y;
d_x= P1.x; d_y= P1.y;
}
t = 0;
do{
/*if(Spl == 3 || Spl==2){
Xp = ax*pow(t,3) + bx*pow(t,2) + dx * t + P.x;// X function
Yp = ay*pow(t,3) + by*pow(t,2) + dy * t + P.y;// Y function
}
Xp = a_x*pow(t,3) + b_x*pow(t,2) + c_x * t + d_x;// X funtion
Yp = a_y*pow(t,3) + b_y*pow(t,2) + c_y * t + d_y;// Y funtion
if (t>0) DrawLine (Xp*Dx+cx,Yp*Dy+cy,Ox,Oy);
Ox=Xp*Dx+cx;
Oy=Yp*Dy+cy;
t+=.005;}
while (t <= 1);
}
Here is what used. Hope it helps.
Spl means spline; 3 is bezier 2 is cubic 1 is cubic
You'll need to play with until you get what you want!
Have Fun!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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).
I know that. :-/
> 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)
That depends on how complicate the formulae become.
At the moment I implemented a simple linear interpolation, so I got
straig lines between the points. The "edges" are pretty visible in the
animation, so a bit more "smoothiness" would be nice. So I'd try
quadratic splines at next?
> 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).
That's already true for linear interpolation.
> (notice that the coordinates of the points are independent on the
> spline: only t and a selected axis influences the value along that
> axis)
So I can calculate the interpolation for each axis independently?
> The hard part is of course the computation of the coefficients.
ACK. :-/
Thanks so far for your answer.
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 10.09.2014 um 19:49 schrieb Warp:
> Lars Rohwedder <rok### [at] gmxde> wrote:
>> Now I want a formula f(t) that returns a "smooth path" going through all
>> these points.
>
> Then what you want is probably this:
>
> http://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline
These looks fine. The "Chordal" one is the favourite at the moment.
> (It links to some example implementations.)
I see. I try to use it in my program.
> You could also achieve it by drawing a bezier curve between each pair
> of points, but in that case you need to generate the two control points
> between them. (This, in fact, gives you more control over the curvature
> of the spline, and even its tangent at each point.)
The control points are the problem for Bezier splines. So I'll try the
Catmull-Rom-Curves. (btw, their name sounds better :-DD)
Thanks a lot!
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 11/09/2014 12:08, Lars Rohwedder a écrit :
> So I can calculate the interpolation for each axis independently?
Yes.
--
Just because nobody complains does not mean all parachutes are perfect.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
