Add your own alternative version
Stats
233K views 9K downloads 128 bookmarked
Posted
17 Dec 2008

Comments and Discussions



Hi Oleg & Peter,
thank you both so much for posting this really helpful article.
I ported your algorithm to Java and use it in Android now.
It works as expected and was no big deal to implement.
Cheers,
Markus





Hallo together,
is it possible to modify the code to support supplying a start and end tangent to method generating the bezier control points?
Thanks and greetings.





<pre lang="text"></pre>Good but I was confused about the numbering of control points and knot points. Reading the code it seems that the schema is as follows 1.Pi – ith knot point (i=0,..,n) 2.P1i – first control point for spline i (close to Pi) (i=0,..,n1) 3.P2i – second control point for spline i (close to P_i+1) (i=0,..,n1)
HTH To answer the WOW question, the code solves a system of equations with a strong diagonal matrix, as follows for n=5 (using Q_i instead of P1_i)
Q = P 0 1 2 3 4 0 1 2 3 4 5 2 1 1 2 1 4 1 4 2 1 4 1 4 2 1 4 1 4 2 2 7 8 1
(so for example the first line means 2*Q_0 + 1*Q_1 = 1*P_0 + 2*P_1) In the code the final line is actually divided by 2 to give .. 1 3.5 .... 4 0.5 The routine is given the right hand side calculations as rhs[] but it "knows" the coefficients on the left hand side, and uses b as a device to allow for the change of pattern in the first and final lines This explains the "4 ? 3.5" since the final line has been divided by 2 in the rhs calculation which makes the coefficient 3.5 instead of the usual 4.
HTH2 JJ





At first, thanks for this article and this is really helpful and easy to understand.
I read this article again and again very carefully.
and I finished understanding all things before the code section.
As following by using (2), (3), (4), (5), I got these,
if the number of knots is 2,
P1_{1} = (2P_{0} + P_{1})/3
P2_{1} = (P_{0} + 2P_{1})/3
in other cases,
2P1_{1} + P1_{2} = P_{0} + 2P_{1}
P1_{i1} + 4P1_{i} + P1_{i+1} = 4P_{i1} + 2P_{i} (i = 2, 3, ..., n1)
2P1_{n1} + 7P1_{n} = 8P_{n1} + P_{n}
But How can I make following form in the "other cases"?
P1_{i} = ...?
P2_{i} = ...?
In this article, it goes to code section without any explanation about that.
I tried to read and understand the code section,
but I failed...
What is the number (double b = 2.0) for?
and where does (i < n1 ? 4.0 : 3.5) come from?
I cannot find these things before the code section.
I feel that it just popped up. WOW.
Please help me.





Hello Oleg. i cannot see equations in the article. What do I need to do to be able to see them? Thank you.





Hi Oleg,
Would you mind checking the format of all the formulae? Maybe it's because of CodeProject has changed the format of formulae.
Thanks.
Peter Lee





Hi, I have problem with using Bezier spline. Please, look at the screeshot
http://screencast.com/t/Ikgy6nxgB[^]
Is it right that I'll get such control points for second and third knots? If so, how can I fix it?





I spy lots of <sub>s and <sup>s!





how can i generate different number of Points from constant number of knots ??????





Very easy to understand, efficient, and very well done.





Oleg and Peter you guys did a great job. I used this for a pet silverlight project. Thanks. Поздравляю вас(my russian is a bit rusty).





I was annoyed that this wasn't set up for 3D splines, but then I noticed that the pattern used for calculating the X values is the same as the one used for calculating the Y values. So I added some code that used the same pattern for the Z values and it worked like a charm. This is a very handy piece of code, thank you! =)





Hi,
Using the above draw function, when my knots array has more than 3 elements, I am getting blocks of points in the curve. I have uploaded the screen shot here:
https://sites.google.com/site/gpdeepti/upload
This what I am doing 
1) Compute the control Points using your logic
2) Interpolating line strips between ptvCtrlPts[i],firstCntrlPts[i], secondCntrlPts[i], ptvCtrlPts[i+1] as done here : http://www.gamedev.net/page/resources/_/technical/graphicsprogrammingandtheory/beziercurvesandsurfacesr1808
Kindly let me know what I am missing here.
Thanks!
Deepti





Needed this! thanks for the clear code and excellent description!





I need an idea that how can i make a signature smooth taken by signature pad . As when a user sign on the signature pad, it is not smmoth
How can BezierSpline be usefull for that






Hi
Could you explain how you get those equations, please?
Now, we have 2n conditions (25) for n control points P1 and n control points P2. Excluding P2, we'll have n equations for n control points P1:
2P11 + P12 = P0 + 2P1 P11 + 4P12 + P13 = 4P1 + 2P2 .... P1i1 + 4P1i + P1i+1 =
4Pi1 + 2Pi (6) .... P1n2 + 4P1n1 + P1n = 4Pn2 + 2Pn1 2P1n1 + 7P1n = 8Pn1 + Pn
thnks for this article





Hi i am facing the problem like this,
i am drawinng around two hundred curves in silverlight application by using pathdata,
For Each curve i have two end points and n control points(n<4 && n>12)
so while drawing i am using "S" for spline drawing in path data while i will take only one control point
that is centeral control point but i am not getting the smooth curve as i am using single control point.
if i use all control points i am not getting like curve.
Please do suggest





Hello Oleg,
Many thanks for this great article.
I'm using this code for some experimentation and I get, in most cases, very good results. But sometimes the generated curve give me unexpected behaviours like drawing a curl between 2 knots.
Unfortunately I didn't find any way to fix this issue and even didn't find any singularity in my set of points.
I can provide 2 or 3 concrete examples, if you are interested.
JeanLuc





Hello JeanLuc,
It would be greate if you give me some examples of wrong behavior of twoknots curves.
Regards,
Oleg V. Polikarpotchkin
ovp





Thanks for your interest, Oleg
Here below you'll find 3 examples :
sample1:
return new Point[]
{ new Point(76476, 799283),
new Point(74225, 803603),
new Point(73971, 803997),
new Point(68303, 805135),
new Point(68174, 805271)
};
sample2:
return new Point[]
{ new Point(95046,801135),
new Point(101218,800002),
new Point(101456,800086),
new Point(103836,800890),
new Point(104048,801004)
};
sample3:
return new Point[]
{ new Point(97953,104865),
new Point(97963,105291),
new Point(96956,106931),
new Point(96728,107188),
new Point(94425,106846),
new Point(94203,106804)
};





Hello Jean Luc,
Sorry, but I need additional explanations:
1. We are talked on twoknots Bezier curves, isn't it? But your samples contains from 5 to 6 points. What these points are?
2. What are the measurement units in your samples. Obviously they aren't the pixels.
Regards,
Oleg V. Polikarpotchkin
ovp





Hello Oleg,
In fact I am sorry, i should explain in my previous message.
1. Yes you're right, the curl I'm talking about appears between two knots but I thought you'll need the coordinates of previous and next points. These points are part of a closed polygon, this polygon is the resulting AlphaShape of a set of points. I know your other article on Closed Smooth Curve with Bezier Spline but I had more curls on the resulting curve.
2. Unit here is meter. The points are geographical points in a particular map projection. So I can convert coordinates from meter to pixel according to a resolution in m/px.
Regards,
JeanLuc





Hello JeanLuc,
1. To calculate Bezier spline of either openended curve or closed polygon you MUST use all the points available, not just some prev and next.
2. I'm not sure but I can suppose that it's better to normalize the points coordinates before the Bezier spline calculation (e.g. convert them to pixels) to mitigate possible rounding errors.
Regards,
Oleg V. Polikarpotchkin
ovp





Hello Oleg,
I provided you only 6 points because I had same "curl effect" between the same 2 knots with 6 points than with all the points of the polygon.
For second point, indeed I normalized the points coordinates after the Bezier spline calculation, thus I made a test converting coordinates before the calculation but I get the same behaviour.
I just used your sample to introduce these coordinates points in a custom curve as you explain in your article, and I get the same result :
Below you'll find the same samples than my previous message but in px this time, and working with your interface
Point[] CustomCurve()
{
Point[] points = new Point[]
{ new Point(470, 323),
new Point(380, 150),
new Point(370, 134),
new Point(143, 89),
new Point(64, 226),
new Point(50, 188)
};
for (int i = 0; i < 6; ++i)
{
double x = points[i].X;
double y = points[i].Y;
points[i] = new Point((ScaleX / 100) * x, (ScaleY / 100) * y);
}
return points;
}
Sample 2 :
Point[] points = new Point[]
{ new Point(113, 249),
new Point(360, 294),
new Point(369, 291),
new Point(464, 258),
new Point(473, 254),
new Point(474, 264)
};
Sample 3 :
Point[] points = new Point[]
{ new Point(179, 99),
new Point(180, 82),
new Point(139, 17),
new Point(130, 6),
new Point(38, 20),
new Point(29, 22)
};
I can provide coordinates of all points of the polygon if you need, but it may be better to send you by email to avoid too long thread  like this one .
Thanks you Oleg
Regards,
JeanLuc





Hello JeanLuc,
Thank you very much for your samples. They prove that the approach to defining the Bezier spline smoothness conditions used in this article doesn’t prohibit from having “curl” features which are not desirable in most cases. Could we elaborate an another one without this pitfall? I’ll try, but it’ll take a time.
I presumed that such thing could happen although did not have the samples. That’s because I’m often using an another technique described in my another article Draw a smooth curve through a set of 2D points with Cubic Spline. Unfortunately it isn’t appropriate to multivalued functions (including closed curves).
Best regards,
Oleg V. Polikarpotchkin
ovp





Hello JeanLuc,
Thank you very much for your samples. They prove that the approach to defining the Bezier spline smoothness conditions used in this article doesn’t prohibit from having “curl” features which are not desirable in most cases. Could we elaborate an another one without this pitfall? I’ll try, but it’ll take a time.
I presumed that such thing could happen although did not have the samples. That’s because I’m often using an another technique described in my another article <a href="http://www.csharpcorner.com/UploadFile/ovp/CubicSpline12222008025501AM/CubicSpline.aspx?ArticleID=2056a269a4844c69b2585b41f8bcc8fb">Draw a smooth curve through a set of 2D points with Cubic Spline</a>. Unfortunately it isn’t appropriate to multivalued functions (including closed curves).
Best regards,
Oleg V. Polikarpotchkin
ovp





Hello Oleg,
It seems that this behaviour occurs when big differences exist in the set of point distribution. As example, I noticed that often curl appears for knots(n,n+1) when these 2 knots are very close in comparaison with the distance between knots (n1,n) and distance between knots(n+1,n+2). My previous samples are example of this.
For my needs I found a solution to avoid having this distribution by clustering my set of points before the Bezier spline calculation. Your code works perfectly in this case and the resulting curve is very good.
I would prefer finding a solution during the Bezier spline calculation to avoid delete some points from my set, but it was below my limits in mathematics
Anyway, thanks a lot for this great code and for your support
JeanLuc





Hi,
sorry about that stupid question but I didn´t get the point how you get these these equations for the control points
3P<sub>1</sub> = 2P<sub>0</sub> + P<sub>3</sub> and P<sub>2</sub> = 2P<sub>1</sub> – P<sub>0</sub>
out of this equation.
B(t)=(1t)<sup>3</sup>P<sub>0</sub>+3(1t)<sup>2</sup>tP<sub>1</sub>+3(1t)t<sup>2</sup>P<sub>2</sub>+t<sup>3</sup>P<sub>3</sub> (1)
If you set the coefficients with the power of 2 and 3 to zero as you descriped it I do not get to the equations. Or I did not understand which coefficients you mean





Hi,
The zero condition of the coefficient at t^{2} gives
P_{2} = 2P_{1}  P_{0} (x)
The zero condition of the coefficient at t^{3} is
P_{0} + 3P_{1}  3P_{2} + P_{3} = 0 (xx)
Substitution of P_{2} from (x) into (xx) gives
3P_{1} = 2P_{0} + P_{3}
Regards,
ovp






What is "visual layer rendering" that you mentioned?







Thank you for a great article!
Luc Pattyn [Forum Guidelines] [My Articles]
 before you ask a question here, search CodeProject, then Google
 the quality and detail of your question reflects on the effectiveness of the help you are likely to get
 use the code block button (PRE tags) to preserve formatting when showing multiline code snippets





Thank you, I appreciate your opinion!
ovp





Hi Oleg,
I believe there is a mistake in the last equation:
P1[n1] + 2P1[n]= 3P[n1]
I calculated a lot of times, and I got:
P1[n1] + 3.5P1[n] = (8P[n1] + P[n])/2
After I modified your code according to this, the updated function removed a strange behavior in your sample, that is, when there are only 3 points, the first Bezier curve is always a straight line. Using the updated function, this issue disappears.
You can check this in your sample, select Curve=Arc, Point count=3, I'm also sending the files to your mail box. Please check.
Peter Lee Mar 16, 2009
<code> /// <summary> /// Bezier Spline methods /// </summary> /// <remarks> /// Modified: Peter Lee (peterlee.com.cn < at > gmail.com) /// Update: 20090316 /// /// see also: /// Draw a smooth curve through a set of 2D points with Bezier primitives /// http://www.codeproject.com/KB/graphics/BezierSpline.aspx /// By Oleg V. Polikarpotchkin /// /// Algorithm Descripition: /// /// To make a sequence of individual Bezier curves to be a spline, we /// should calculate Bezier control points so that the spline curve /// has two continuous derivatives at knot points. /// /// Note: `[]` denotes subscript /// `^` denotes supscript /// `'` denotes first derivative /// `''` denotes second derivative /// A Bezier curve on a single interval can be expressed as: /// /// B(t) = (1t)^3 P0 + 3(1t)^2 t P1 + 3(1t)t^2 P2 + t^3 P3 (*) /// /// where t is in [0,1], and /// 1. P0  first knot point /// 2. P1  first control point (close to P0) /// 3. P2  second control point (close to P3) /// 4. P3  second knot point /// /// The first derivative of (*) is: /// /// B'(t) = 3(1t)^2 P0 + 3(3t^2–4t+1) P1 + 3(2–3t)t P2 + 3t^2 P3 /// /// The second derivative of (*) is: /// /// B''(t) = 6(1t) P0 + 6(3t2) P1 + 6(1–3t) P2 + 6t P3 /// /// Considering a set of piecewise Bezier curves with n+1 points /// (Q[0..n]) and n subintervals, the (i1)th curve should connect /// to the ith one: /// /// Q[0] = P0[1], /// Q[1] = P0[2] = P3[1], ... , Q[i1] = P0[i] = P3[i1] (i = 1..n) (@) /// /// At the ith subinterval, the Bezier curve is: /// /// B[i](t) = (1t)^3 P0[i] + 3(1t)^2 t P1[i] + /// 3(1t)t^2 P2[i] + t^3 P3[i] (i = 1..n) /// /// applying (@): /// /// B[i](t) = (1t)^3 Q[i1] + 3(1t)^2 t P1[i] + /// 3(1t)t^2 P2[i] + t^3 Q[i] (i = 1..n) (i) /// /// From (i), the first derivative at the ith subinterval is: /// /// B'[i](t) = 3(1t)^2 Q[i1] + 3(3t^2–4t+1) P1[i] + /// 3(2–3t)t P2[i] + 3t^2 Q[i] (i = 1..n) /// /// Using the first derivative continuity condition: /// /// B'[i1](1) = B'[i](0) /// /// we get: /// /// P1[i] + P2[i1] = 2Q[i1] (i = 2..n) (1) /// /// From (i), the second derivative at the ith subinterval is: /// /// B''[i](t) = 6(1t) Q[i1] + 6(3t2) P1[i] + /// 6(13t) P2[i] + 6t Q[i] (i = 1..n) /// /// Using the second derivative continuity condition: /// /// B''[i1](1) = B''[i](0) /// /// we get: /// /// P1[i1] + 2P1[i] = P2[i] + 2P2[i1] (i = 2..n) (2) /// /// Then, using the socalled "natural conditions": /// /// B''[1](0) = 0 /// /// B''[n](1) = 0 /// /// to the second derivative equations, and we get: /// /// 2P1[1]  P2[1] = Q[0] (3) /// /// 2P2[n]  P1[n] = Q[n] (4) /// /// From (1)(2)(3)(4), we have 2n conditions for n first control points /// P2[1..n], and n second control points P2[1..n]. /// /// Eliminating P2[1..n], we get (be patient to get a set of n /// equations for solving P1[1..n]: /// /// 2P1[1] + P1[2] + = Q[0] + 2Q[1] /// P1[1] + 4P1[2] + P1[3] = + 4Q[1] + 2Q[2] /// ... /// P1[i1] + 4P1[i] + P1[i+1] = + 4Q[i1] + 2Q[i] /// ... /// P1[n2] + 4P1[n1] + P1[n] = + 4Q[n2] + 2Q[n1] /// P1[n1] + 3.5P1[n] =( + 8Q[n1] + Q[n])/2 /// /// From this set of equations, P1[1..n] are easy but tedious to solve. /// (Elimination method /// </remarks>
public static class BezierSpline { /// <summary> /// Get openended Bezier Spline Control Points. /// </summary> /// <param name="knots">Input Knot Bezier spline points.</param> /// <param name="firstControlPoints">Output First Control points array of knots.Length  1 length.</param> /// <param name="secondControlPoints">Output Second Control points array of knots.Length  1 length.</param> public static void GetCurveControlPoints(Point[] knots, out Point[] firstControlPoints, out Point[] secondControlPoints) { int n = knots.Length  1; if (n < 1) { firstControlPoints = new Point[0]; secondControlPoints = new Point[0]; return; }
// Calculate first Bezier control points // Right hand side vector double[] rhs = new double[n];
// Set right hand side X values for (int i = 1; i < n  1; ++i) rhs[i] = 4 * knots[i].X + 2 * knots[i + 1].X; rhs[0] = knots[0].X + 2 * knots[1].X; rhs[n  1] = (8 * knots[n  1].X + knots[n].X) / 2.0; // Get first control points Xvalues double[] x = GetFirstControlPoints(rhs);
// Set right hand side Y values for (int i = 1; i < n  1; ++i) rhs[i] = 4 * knots[i].Y + 2 * knots[i + 1].Y; rhs[0] = knots[0].Y + 2 * knots[1].Y; rhs[n  1] = (8 * knots[n  1].Y + knots[n].Y) / 2.0; // Get first control points Yvalues double[] y = GetFirstControlPoints(rhs);
// Fill output arrays. firstControlPoints = new Point[n]; secondControlPoints = new Point[n]; for (int i = 0; i < n; ++i) { // First control point firstControlPoints[i] = new Point(x[i], y[i]); // Second control point if (i < n  1) secondControlPoints[i] = new Point(2 * knots[i + 1].X  x[i + 1], 2 * knots[i + 1].Y  y[i + 1]); else secondControlPoints[i] = new Point((knots[n].X + x[n  1]) / 2, (knots[n].Y + y[n  1]) / 2); } }
/// <summary> /// Solves a tridiagonal system for one of coordinates (x or y) of first Bezier control points. /// (Elimination method /// </summary> /// <param name="rhs">Right hand side vector.</param> /// <returns>Solution vector.</returns> private static double[] GetFirstControlPoints(double[] rhs) { int n = rhs.Length; double[] x = new double[n]; // Solution vector. double[] tmp = new double[n]; // Temp workspace.
double b = 2.0; x[0] = rhs[0] / b; for (int i = 1; i < n; i++) // Decomposition and forward substitution. { tmp[i] = 1 / b; b = (i < n  1 ? 4.0 : 3.5)  tmp[i]; x[i] = (rhs[i]  x[i  1]) / b; } for (int i = 1; i < n; i++) x[n  i  1] = tmp[n  i] * x[n  i]; // Backsubstitution.
return x; } }</code>





Sorry, I cannot find your email address, so I cannot send you the files.
Peter Lee





Hi, Peter!
Sorry for delay and thank you for your submission, I'll see what is wrong there.
You could contact me at ovp@yandex.ru
Regards,
Oleg V. Polikarpotchkin
ovp





Hi Peter. How did you get "P1[n1] + 3.5P1[n] = (8P[n1] + P[n])/2"?
I know that the original equation isnt exact because there is no P1[n+1] and hence one cant use it. I dont understand though how you calculated the above. Ive been trying for about an hour already and cant see how you arrived at it.
Please help.
Also, Im writing a port for Matlab and want to know if you mind me sending it through to the Mathswork website when Im finished.
Thanks
Aaron





Is this curve fitting algorithm subject to the same problem cubic splines sometimes have; specifically, goofy oscillations between points that have a little noise in them?
I've seen articles that state that piecewise Hermite cubic polynomial fits can eliminate this nasty oscillation problem, but I haven't seen any code that implements the methodology.





Hello, bstrack!
Cubic spline interpolation (as well as any other interpolation) not always gives the result you could expect. In the article we draw the "smooth" curve and the "smoothness" means there just that the curve have two first derivatives continuous, that’s all.
For example (the classic example on where Hermite spline can behave better than the cubic one) you could invent the function with nonnegative first derivative and such the set of points that the cubic spline will have negative first derivative in some of them. You can regard this behavior as oscillations and, if so, you can try eliminate that oscillations with Hermite spline – at a price of the additional information on the first derivative nonnegativeness.
But in the most cases cubic spline gives very satisfactory results. Can you give me concrete example where you have got an inadequate spline behavior?
Regards,
Oleg V. Polikarpotchkin
ovp





Dear Oleg,
You have posted a very nice code.
But, I also need the code for the closed curves.
Please help. Thanks.





Hello, wang2002!
I'm going to propose such a solution in the nearest future. But, unfortunately, I'm busy now full out with a project. May be in two or three weeks I'll take the time.
Let me know, please, if you'll find the solution in a different way!
Regards,
Oleg V. Polikarpotchkin
ovp






Thanks for this article, it will be very usefull for me . I developped a chart control that I submitted to codeproject and some time ago I wanted to add a smoothing feature for line series. After googling for some time I couldn't find anything usefull except for the Bezier curve but I still had to provide the control points. I didn't want to spend way to much time on that (and I have to say that this is a bit far for me), I decided to drop it. Well, now I have a good example that solves the problem for me.
Thanks for that !





Hello Cédric!
Thank you for your post! I'm glad the contribution seems to be useful for your.
As to me I still pair this approach with drawing with natural cubic spline to be sure that all goes ok (just in testing). Cubic spline is as easy to calculate as Bezier spline but the former is harder to draw. Nevertheless cubic spline is so approved that it should be used as good reference point.
Regards,
Oleg V. Polikarpotchkin
ovp





You REALLY have to work on your variable names.
"Why don't you tie a kerosenesoaked rag around your ankles so the ants won't climb up and eat your candy ass..."  Dale Earnhardt, 1997  "...the staggering layers of obscenity in your statement make it a work of art on so many levels."  Jason Jystad, 10/26/2001





Hi!
Thank you for your advice but give me please a bit more info on what do you mean. Some examples of what you are seeing improper.
Oleg V. Polikarpotchkin
ovp





Your variable names look ok to me. Perhaps he means they aren't in the style that Microsoft's recommends. Since he didn't give any concrete advice I would recommend ignoring him until he does so.







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

