cloche
Mechanical
- May 12, 2005
- 112
Hi everybody,
as one might have seen in the topic "Transformation of curve by another curve", I'm dealing with the problem of describing 3D curves.
Originally I thought to use UG's internal functions to model generic 3D curve transformation or generation by applying some kind of manipulation over existing curves. The results on the topic mentioned above prove that the best way to accomplish that is, instead, to give UG the desired set of 3 equations for x, y and z of the curve.
As UG allows to express x, y and z in parametric terms of "t", with t varying from 0 to 1, there is no need to find an implicit expression f(x,y,z)=0 for the curve, nor an explicit one in terms of x. Math theory would prove that these forms would not be analytically expressable for most of the 3D curves of interest. The parametric expression of a curve is instead made of three independent equations: x(t), y(t) and z(t). That's what the program calculates when it builds "internally" a spline, for example.
In the following, only "polynomial" parametric curves will be described. A curve in R^3 is polynomial when P(t)=[F0(t),... Fn(t)]{Qt0,... Qtn}, where F0(t),... Fn(t) are linearly independent polynomials and Q0t,... Qnt are the control points of the curve refered to the parametric interval [ta,tb]=[0,1].
1) LAGRANGE INTERPOLATION
in [0,1], let's consider n+1 points equally spaced where ti=i/n (i=0 to n), and n+1 vectors Qti calculated in correspondance of them.
The Lagrange polynomials are defined as follows:
Li(t)=P(j,i)[(u-uj)/(ui-uj)] where P(j,i) indicates the recursive Product, j varies from 0 to n and i varies from 0 to n with the condition that j.NE.i
A Parametric curve P(t) can be expressed in Lagrangian form by:
P(t)=SUM(i)[Li(t)*Qti], with i varying from 0 to n.
In the particular case of cubic curves, the expression becomes (in matrix form):
P(t)=[t^3;t^2;t;1]*{[-9/2;27/2;-27/2;9/2];[9;-45/2;18;-9/2];[-11/2;9;-9/2;1];[1;0;0;0]}*{Qt0;Qt1;Qt2;Qt3}=[T]{L}{Q}.
The Lagrange polynomials are one of the possible form of the "BLENDING FUNCTIONS" that characterize the parametric curve. Their use is to "weigth" the influence of the vectors Qti.
It can be seen that the blending functions of Lagrange give an equivalent weigth to each of the Qti, each in a different sub-interval of [0,1]. This explains why the Lagrange interpolation is extremely sensitive to the control-points definition, and is characterized by a strong osillatory behaviour when the number of points increases. Moreover, no derivative of the function is involved, so that no control on the tangency or the curvature can be assigned. The curve, anyway, passes exactly through the control points as far as the number of control points is equal to m+1, where m is the maximum exponent of t in the polynomials.
2) HERMITE INTERPOLATION
Let's now consider n+1 points at ti in [0,1], and for each let's have m+1 interpolation conditions Qt1(0), Qti(1)... Qti(m) with i=0...n.
Use the Lagrange polynomials in order to construct the following polynomials:
hil(t)=((u-ui)^l/l!)*[Li(t)]^(1+m)
The Hermite polynomials are defined as follows:
Him(t)=him(t);
Hil(t)=hil(t)-Sum(j)[hilj(ti)*Hij(t)] where l=m-1...0 and j=l+1...m
After some manipulation, we have
P(t)=Sum(l)[Sum(j)[Hjl(t)*Qtjl]] with l=0...m and j=0...n
with the conditions
Pk(ti)=Qtik, k=0...m ("pass-through" conditions).
In the particular case of cubic (3rd-order) interpolating curves, 4 conditions are needed, of which 2 are "pass-through" conditions (i.e., start and end points) and the other 2 are conditions on the first derivative (i.e., start and end tangent vectors):
{Q}={Qt0;Qt1;Q't0;Q't1}
After some manipulation, we have the expression of the blending functions:
H00(t)=2*t^3-3*t^2+1
H10(t)=-2*t^3+3*t^2
H01(t)=-2*t^2+t
H11(t)=t^3-t^2
In matrix form, the curve P(t) becomes:
P(t)=[t^3;t^2;t;1]*{[2;-2;1;1];[-3;3;-2;-1];[0;0;1;0];[1;0;0;0]}*{Qt0;Qt1;Q't0;Q't1}=[T]{H}{Q}.
It is possible to elevate the degree of the derivation, by calculating two more Hermite polynomials and by adding two more conditions Q''t0 and Q''t1. Of course, all The previous 4 blending functions (Hermite Polynomials) must be recalculated (NOTE: they have to be recalculated ONCE for ALL the possible hermitian 5th-order curves!!!), and in addition there will be two more, H02(t) and H12(t).
The Hermite polynomial curve has many advantages over the Lagrange one:
- it is far more "stable" in shape, and doesn't exhibit oscillatory phenomena.
- the tangency, curvature, etc (down to an arbitrary degree of differentiation) can be controlled by vectors
- the approximation of the Hermite curve to the "target" analytical curve (if existing) can be controlled by the magnitude of the derivatives vectors. For example, a "half-ellipse" can not be obtained precisely by a single Hermite curve, but by varying the amplitude of the two tangent vectors, the approximation will change.
That explains why the Hermite interpolation is one of the prefered by the designers when:
- the number of control points is extremely reduced (two points are sufficient to create a curve)
- initial vectorial conditions have to be imposed, and the position of the curve must not be precisely driven between the starting and the ending point (i.e. it depends on the direction and on the magnitude of the vectorial conditions)
Also note that the homothetical shape ("form") of the curve is defined independently from the magnitude of the two sets of derivative vectors. You can then PARAMETRIZE the curve form.
In the example of a 3rd-order curve controlled by position and tangency conditions (also called "1st-order Hermitian Form"), the parameters of the curve will be "t", "m1" and "m2", where m1 and m2 are the magnitude multipliers of the tangent vectors, when the modulus of the tangent vectors is 1.
-----------------------------------------------
At that point, what have we got?
- one very good parametric equation form for 3D/2D curves when only start/end conditions have to be imposed (Hermite interpolation)
- a form that can be easily developed in UG by simply creating the tangent/curvature vectors coefficients and then using the "LAW CURVE -> BY EQUATION"
What is still to be investigated?
- properties of composition / decomposition of parametric curves
- re-parametrization to a different interval
- other curve forms that are useful in other cases: splines, B-Splines, NURBS
------------------------------------------------
Please let me know if you are interested in developing this topic...
Also, any integration / comment / addition are super-welcomed!!! ;-)
Claudio
as one might have seen in the topic "Transformation of curve by another curve", I'm dealing with the problem of describing 3D curves.
Originally I thought to use UG's internal functions to model generic 3D curve transformation or generation by applying some kind of manipulation over existing curves. The results on the topic mentioned above prove that the best way to accomplish that is, instead, to give UG the desired set of 3 equations for x, y and z of the curve.
As UG allows to express x, y and z in parametric terms of "t", with t varying from 0 to 1, there is no need to find an implicit expression f(x,y,z)=0 for the curve, nor an explicit one in terms of x. Math theory would prove that these forms would not be analytically expressable for most of the 3D curves of interest. The parametric expression of a curve is instead made of three independent equations: x(t), y(t) and z(t). That's what the program calculates when it builds "internally" a spline, for example.
In the following, only "polynomial" parametric curves will be described. A curve in R^3 is polynomial when P(t)=[F0(t),... Fn(t)]{Qt0,... Qtn}, where F0(t),... Fn(t) are linearly independent polynomials and Q0t,... Qnt are the control points of the curve refered to the parametric interval [ta,tb]=[0,1].
1) LAGRANGE INTERPOLATION
in [0,1], let's consider n+1 points equally spaced where ti=i/n (i=0 to n), and n+1 vectors Qti calculated in correspondance of them.
The Lagrange polynomials are defined as follows:
Li(t)=P(j,i)[(u-uj)/(ui-uj)] where P(j,i) indicates the recursive Product, j varies from 0 to n and i varies from 0 to n with the condition that j.NE.i
A Parametric curve P(t) can be expressed in Lagrangian form by:
P(t)=SUM(i)[Li(t)*Qti], with i varying from 0 to n.
In the particular case of cubic curves, the expression becomes (in matrix form):
P(t)=[t^3;t^2;t;1]*{[-9/2;27/2;-27/2;9/2];[9;-45/2;18;-9/2];[-11/2;9;-9/2;1];[1;0;0;0]}*{Qt0;Qt1;Qt2;Qt3}=[T]{L}{Q}.
The Lagrange polynomials are one of the possible form of the "BLENDING FUNCTIONS" that characterize the parametric curve. Their use is to "weigth" the influence of the vectors Qti.
It can be seen that the blending functions of Lagrange give an equivalent weigth to each of the Qti, each in a different sub-interval of [0,1]. This explains why the Lagrange interpolation is extremely sensitive to the control-points definition, and is characterized by a strong osillatory behaviour when the number of points increases. Moreover, no derivative of the function is involved, so that no control on the tangency or the curvature can be assigned. The curve, anyway, passes exactly through the control points as far as the number of control points is equal to m+1, where m is the maximum exponent of t in the polynomials.
2) HERMITE INTERPOLATION
Let's now consider n+1 points at ti in [0,1], and for each let's have m+1 interpolation conditions Qt1(0), Qti(1)... Qti(m) with i=0...n.
Use the Lagrange polynomials in order to construct the following polynomials:
hil(t)=((u-ui)^l/l!)*[Li(t)]^(1+m)
The Hermite polynomials are defined as follows:
Him(t)=him(t);
Hil(t)=hil(t)-Sum(j)[hilj(ti)*Hij(t)] where l=m-1...0 and j=l+1...m
After some manipulation, we have
P(t)=Sum(l)[Sum(j)[Hjl(t)*Qtjl]] with l=0...m and j=0...n
with the conditions
Pk(ti)=Qtik, k=0...m ("pass-through" conditions).
In the particular case of cubic (3rd-order) interpolating curves, 4 conditions are needed, of which 2 are "pass-through" conditions (i.e., start and end points) and the other 2 are conditions on the first derivative (i.e., start and end tangent vectors):
{Q}={Qt0;Qt1;Q't0;Q't1}
After some manipulation, we have the expression of the blending functions:
H00(t)=2*t^3-3*t^2+1
H10(t)=-2*t^3+3*t^2
H01(t)=-2*t^2+t
H11(t)=t^3-t^2
In matrix form, the curve P(t) becomes:
P(t)=[t^3;t^2;t;1]*{[2;-2;1;1];[-3;3;-2;-1];[0;0;1;0];[1;0;0;0]}*{Qt0;Qt1;Q't0;Q't1}=[T]{H}{Q}.
It is possible to elevate the degree of the derivation, by calculating two more Hermite polynomials and by adding two more conditions Q''t0 and Q''t1. Of course, all The previous 4 blending functions (Hermite Polynomials) must be recalculated (NOTE: they have to be recalculated ONCE for ALL the possible hermitian 5th-order curves!!!), and in addition there will be two more, H02(t) and H12(t).
The Hermite polynomial curve has many advantages over the Lagrange one:
- it is far more "stable" in shape, and doesn't exhibit oscillatory phenomena.
- the tangency, curvature, etc (down to an arbitrary degree of differentiation) can be controlled by vectors
- the approximation of the Hermite curve to the "target" analytical curve (if existing) can be controlled by the magnitude of the derivatives vectors. For example, a "half-ellipse" can not be obtained precisely by a single Hermite curve, but by varying the amplitude of the two tangent vectors, the approximation will change.
That explains why the Hermite interpolation is one of the prefered by the designers when:
- the number of control points is extremely reduced (two points are sufficient to create a curve)
- initial vectorial conditions have to be imposed, and the position of the curve must not be precisely driven between the starting and the ending point (i.e. it depends on the direction and on the magnitude of the vectorial conditions)
Also note that the homothetical shape ("form") of the curve is defined independently from the magnitude of the two sets of derivative vectors. You can then PARAMETRIZE the curve form.
In the example of a 3rd-order curve controlled by position and tangency conditions (also called "1st-order Hermitian Form"), the parameters of the curve will be "t", "m1" and "m2", where m1 and m2 are the magnitude multipliers of the tangent vectors, when the modulus of the tangent vectors is 1.
-----------------------------------------------
At that point, what have we got?
- one very good parametric equation form for 3D/2D curves when only start/end conditions have to be imposed (Hermite interpolation)
- a form that can be easily developed in UG by simply creating the tangent/curvature vectors coefficients and then using the "LAW CURVE -> BY EQUATION"
What is still to be investigated?
- properties of composition / decomposition of parametric curves
- re-parametrization to a different interval
- other curve forms that are useful in other cases: splines, B-Splines, NURBS
------------------------------------------------
Please let me know if you are interested in developing this topic...
Also, any integration / comment / addition are super-welcomed!!! ;-)
Claudio