Add your own alternative version
Stats
68.7K views 2.5K downloads 59 bookmarked
Posted
29 Dec 2007

Comments and Discussions


Your project is very nice,But,can you write your code in C#,Because I use C# coding,your code use VB,I can not understand cleraly.Thank you!
ambitionlike






Tested !
Nice interface and explanations.





wow. don't go to microsoft. go to teach to uni





BTW: there is some system error with your demo. If you make two support points and doubleclick the form to maximize, and doubleclick to minimize it falls unhandled excp. But beautiful sample.
Although I have some problems with this article (I'm pretty poor mathematician), at least playing with your demo is good way to understand (compared to this article, for me) difference between spline and cubic curve. jFYI I had for example big problem to catch the train in BinarySearch article section (just starting), because I don't initially know what are points searched thru for, and why do you search bezier section, it's, for poornonmathers just, pretty shortcircuited starting of article, or like yanked from context. I'll give it try with looking in code attached. (Article is informative enough although, but there are some problems with people like me and some sections of article )
Later: Um, this seem of yanking of context is caused by not notifiing reader that "Bezier general info" section is ended, and repeating for this stupid reader, that you're going to compute some distinct point of bezier from known X.
Even more later (or laterer for PoorEnglish): OIC, again. You should write better intro, and rethink section names. For example I noticed, that you actually drawn bezier using DrawCurve, and that you are just going to show, how to calculate distinct point on it in this article, somewhere in the middle of article. If this would started this article, with some changes to #captions, it would be as easy to understand, as your more recent articles are. Please forgive me such extensive revision, I actually think that also this article is very good.
Even laterer than latest laterer: To not just cast as stupid myself here, I've just noticed, that your demo is limited for XY bezier layout (I mean, it can't draw vertical bezier (combined at result), nor compute point for two support points of same X). Maybe it would be helpful to think if there is something interesting for others, if you'd tried to make both computations and drawings possible? I don't know, maybe it will just blur whole article and code, but you will know better if this remark has some value.
Finally: OIC //"They are mathematically undefined only if two supportpoints set on the same Xposition (as vertical line)."
P.S.: also code is pretty beautiful. so just try to reconsider my previous remarks on your own, and make your conclusion if there is something to repair in app or update in article. all my previous words here except those two 'beautiful' ratings, those on complicated orientation in article, and system bug with resizing can be just mismatch, because they were written in the middle of reading.
modified on Thursday, January 7, 2010 5:20 AM





Would you happen to have a nonmouse example that still uses the routines?
I'd like to be able to insert points from a data array and get interpolated values back.
TIA!
Tom





How do I open this project in VS2005?





Sorry, you're right, to this I haven't thought.
I will make an Update soon, include a VB8 Solution.





Nice article. Does anyone know if there is a recognised way of determining the distance *along the curve* between two points that lie on the curve? I googled till I was blue in the face but drew a blank TIA...





The Bezier curve is defined by two equation:
x(t) = a_x*t^3 + b_x*t^2 + c_x*t + x_0
y(t) = a_y*t^3 + b_y*t^2 + c_y*t + y_0
The coefficients a_x .. c_x and a_y .. c_y can be found from the 4 points which frame (define) the curve:
x_1 = x_0 + c_x/3
x_2 = x_1 + (c_x+b_x)/3
x_3 = x_0 + c_x + b_x + a_x
The same relations for the y flavour of the points and coefficients.
Now some simple math:
If t == 0: x(t=0) = x_0
if t == 1: x(t=1) = x_3
To calculate the distance along the Bezier curve,
1) divide your t in small steps, e.g. 0.001 (for t=0; t<=1; t+=0.001) and calculate the accompanying x(t) and y(t) values. 1001 X and Y values.
2) calculate the differences between adjacent points, in both X and Y: This gives you a set of 1000 values DX and DY. DX(i) = X(i+1)  X(i)
3) Take the square of these differences DX and DY and then the square root of these. This provide you with 1000 DS values: DS = sqrt(DX*DX + DY*DY)
4) Sum all DS values. This is a fair approximation of the length of the curve.
There is a better analytical solution of this question, but i doubt whether the integral involved can be solved analytically. Then it forves you to a numerical solution for the integral, which is nice as well, but the brute force solution is easier.
21 cm: the universal wavelength of hydrogen





Hi!
Thank you. You pointed me to look again at the maths of bezier, and that leaded me to another approach to compute the points:
''' <summary>
''' computes the point on a beziercurve which is defined by 4 constructionpoints
''' </summary>
Private Shared Function PointOfFraction( _
ByVal t As Single, ByVal ptBeziers() As PointF) As PointF
Dim X = _
(1  t) ^ 3 * ptBeziers(0).X + _
3 * t * (1  t) ^ 2 * ptBeziers(1).X + _
3 * t ^ 2 * (1  t) * ptBeziers(2).X + _
t ^ 3 * ptBeziers(3).X
Dim Y = _
(1  t) ^ 3 * ptBeziers(0).Y + _
3 * t * (1  t) ^ 2 * ptBeziers(1).Y + _
3 * t ^ 2 * (1  t) * ptBeziers(2).Y + _
t ^ 3 * ptBeziers(3).Y
Return New PointF(CSng(X), CSng(Y))
End Function
the casteljaualgorithm actually isn't needed (although I understand it better) in this case.
Since the beziersegments always consist of 4 constructionpoints, one can compute the points on with that formula.





G'day,
Your math leads to the same result, as a matter of fact when i expand your equation, it is the same polynomial in t, with the same coefficients. In this particular case the t^3 term is not a problem, since 0 <= t <= 1, so all terms in t are positive.
This is a more general remark with polynomial expressions, not referring to your article: i prefer expanding a polynomial like
at^3 + bt^2 + ct + d
into
((at+b)t+c)t+d
The advantages are:
1) prevents powers of negative numbers
2) adds up terms of comparable value
The latter point is especially important when the terms t^n and t^(n1) are not or not nearly orthogonal.
21 cm: the universal wavelength of hydrogen





Thanks for that. It's pretty much the way I was doing it, although I've made one modification which seems to work well (for me at least, with the beziers that I normally deal with):
Divide the curve into a number of steps, say t=0.1, and calculate the length. Call it L1.
Now double the number of steps by halving t, calculate the length again and call it L2.
In practice, it seems that L2+(L2L1) is very close to the value you would get by using a much larger number of steps  and much faster to calculate.
As I said it works for me using the curves I normally deal with (kite design), it may not work so well for you & yours...





petert1401 wrote: Divide the curve into a number of steps, say t=0.1, and calculate the length. Call it L1.
Now double the number of steps by halving t, calculate the length again and call it L2.
In practice, it seems that L2+(L2L1) is very close to the value you would get by using a much larger number of steps  and much faster to calculate.
You seem to be surprised that your new approximation (New = 2 * L2  L1) is better than either L2 or L1. The trick you applied is called Richardson extrapolation, see http://en.wikipedia.org/wiki/Richardson_extrapolation[^]
In order to understand the wiki article, assume that the order of the error of your calculation process is of type h^1, (n=1), h being the stepsize, so according to Richarson:
R(h) = (2^1 * A(h/2)  A(h))/(2^1 1)
which in your notation:
R(h) = (2*L2  L1) / (2 1) = L2 + (L2  L1)
and the latter formula is equal to your formula.
21 cm: the universal wavelength of hydrogen





Thanks henk21cm,
I'm not surprised that my new approximation is better than either L2 or Li, because you can intuitively see that it is likely to be. I am surprised though that 2*L2  L1, where the corresponding values of t are 0.1 and 0.05 respectively, is so close to the value for t=0.0001.
I'm even more surprised, nay shocked and stunned, that 'my new approximation' is neither new nor mine since I arrived at it purely empirically and indepentently. It's good to see that it has some validity





... welcome to the club...
... of clever guys, unfortunately born some years too late





Imports System
Imports System.Diagnostics
Namespace TridexConsultants.Engine.Math
Public Class CRSpline
' Methods
Public Shared Function Interpolate(ByVal time As Single, ByVal vectors As Vector3()) As Vector3
Dim num1 As Integer = CInt(time)
' Debug.Assert((num1 >= 0))
' Debug.Assert(((num1 + 3) < vectors.Length))
Return CRSpline.Interpolate((time  num1), vectors(num1), vectors((num1 + 1)), vectors((num1 + 2)), vectors((num1 + 3)))
End Function
Public Shared Function Interpolate(ByVal time As Single, ByVal pre As Vector3, ByVal from As Vector3, ByVal [to] As Vector3, ByVal post As Vector3) As Vector3
' Debug.Assert(((time >= 0!) AndAlso (time <= 1!)), "Time not in the interval 0.0f  1.0f")
Return DirectCast((0.5! * (((((((((Vector3.op_UnaryNegation(pre) + (3.0! * from))  (3.0! * [to])) + post) * time) * time) * time) + ((((((2.0! * pre)  (5.0! * from)) + (4.0! * [to]))  post) * time) * time)) + ((Vector3.op_UnaryNegation(pre) + [to]) * time)) + (2.0! * from))), Vector3)
End Function
Public Shared Function Interpolate(ByVal time As Single, ByVal pre As Single, ByVal from As Single, ByVal [to] As Single, ByVal post As Single) As Single
'Debug.Assert(((time >= 0!) AndAlso (time <= 1!)), "Time not in the interval 0.0f  1.0f")
Return (0.5! * (((((((((pre + (3.0! * from))  (3.0! * [to])) + post) * time) * time) * time) + ((((((2.0! * pre)  (5.0! * from)) + (4.0! * [to]))  post) * time) * time)) + ((pre + [to]) * time)) + (2.0! * from)))
End Function
End Class
End Namespace





Hi,
Love this code, You have helped me more than you know,
I am going to update thecode to reflect ther 3D Vectors, as I need ed some thing like this for My level Editor movement paths for obects Vector3
I will let you know once this is done tonight, and send you the first BETA of my engine,
I hope its oky to use the code!!!
maybe you could help
this is teh intrepolation code I would use to process the points List :
'**************************************************************************************************************************
'* BezierInterpolation.
'*
'**************************************************************************************************************************
Public Shared Function BezierInterpolation(ByVal ptos As Vector3(), ByVal weigth As Single) As Vector3
Dim single16 As Single = weigth
Dim vector1 As Vector3 = ptos(0)
Dim vector2 As Vector3 = ptos(1)
Dim vector3 As Vector3 = ptos(2)
Dim vector4 As Vector3 = ptos(3)
Dim single4 As Single = single16
Dim single5 As Single = (single4 * single4)
Dim single6 As Single = (single5 * single4)
Dim single7 As Single = (((vector1.X + (3.0! * vector2.X))  (3.0! * vector3.X)) + vector4.X)
Dim single8 As Single = (((vector1.Y + (3.0! * vector2.Y))  (3.0! * vector3.Y)) + vector4.Y)
Dim single9 As Single = (((vector1.Z + (3.0! * vector2.Z))  (3.0! * vector3.Z)) + vector4.Z)
Dim single10 As Single = (((3.0! * vector1.X)  (6.0! * vector2.X)) + (3.0! * vector3.X))
Dim single11 As Single = (((3.0! * vector1.Y)  (6.0! * vector2.Y)) + (3.0! * vector3.Y))
Dim single12 As Single = (((3.0! * vector1.Z)  (6.0! * vector2.Z)) + (3.0! * vector3.Z))
Dim single13 As Single = ((3.0! * vector1.X) + (3.0! * vector2.X))
Dim single14 As Single = ((3.0! * vector1.Y) + (3.0! * vector2.Y))
Dim single15 As Single = ((3.0! * vector1.Z) + (3.0! * vector2.Z))
Dim single1 As Single = (((single7 * single6) + (single10 * single5)) + (single13 * single4))
Dim single2 As Single = (((single8 * single6) + (single11 * single5)) + (single14 * single4))
Dim single3 As Single = (((single9 * single6) + (single12 * single5)) + (single15 * single4))
Return New Vector3((vector1.X + single1), (vector1.Y + single2), (vector1.Z + single3))
End Function
Public Shared Function Bezier(ByVal p0 As Vector3, ByVal p1 As Vector3, ByVal p2 As Vector3, ByVal t As Single) As Vector3
Dim vector As Vector3 = Vector3.Lerp(p0, p1, t)
Dim vector2 As Vector3 = Vector3.Lerp(p1, p2, t)
Return Vector3.Lerp(vector, vector2, t)
End Function
Thank You,
and happy new year...TRIDEX ...
modified on Wednesday, January 02, 2008 6:19:30 AM






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.

