Archive for September, 2009

Quadratic Hermite Curves Part 5

September 3, 2009 1 comment

Part four of this series illustrated how to join two quadratic Hermite curves with C-1 continuity at the join.  This part examines the mathematical foundation of creating a spline that interpolates an arbitrary number of knots using quadratic Hermite segments.

To begin, review the two-segment case that interpolates three points, P0, P1, and P2.   The start tangent vector for the first segment is T0 and the start tangent for the second segment is T1.  Both tangents are functions of t.  T0 is shorthand notation for the tangent at t=0 for the first segment. T1 refers to the tangent at t=0 for the second segment.  T0(1) refers to the end tangent of the first Hermite segment.  T1(1) refers to the end tangent for the second segment.  It is necessary to introduce superscripts and subscripts into the notation at this time.

The boundary condition at the join (P1) is that T0(1) = T1.  Recall from part 2 of this series that T0(1) = 2(P1 – P0) – T0, so T1 = 2(P1 – P0) – T0 or T0 + T1 = 2(P1 – P0).   Note that T1 can not be computed until T0 is fixed.   If another segment is added, there is a similar boundary condition for T2 in terms of T1(1).  You can show that that the vector of tangents is represented by the equation AT = b, where

A = | 1 1 0 0 0 ... 0 |
    | 0 1 1 0 0 ... 0 |
    |       . . .     |
    | 0 0 0 0 ... 1 1 |

T = [ T0 T1 ... Tn-1 ]t
b = 2[P1-P0 P2-P1 ... Pn-1-Pn-2]t

For n data points, A is n-1 x n.   The system of equations is underdetermined as expected since the choice of initial start tangent is arbitrary.  Once this value is fixed, the system of equations can be easily solved.  With T0 fixed, there are n-1 tangents to be computed.  The first row of A yields one equation in one unknown, T1.  Once T1 is computed, the second row yields an equation for T2 in terms of T1.  Solving the complete system is a generalization of the approach in part four of this series.

To draw the spline it is not strictly necessary to compute the last tangent, although it is handy to have in the case that new knots are added onto the spline.

Notice that the polynomial coefficients are not directly part of the solution.  They follow once the start tangents are set for each segment.  It is possible to create a matrix equation for the coefficients, but that requires more effort and we already have software that automatically computes the coefficients once the start tangents are provided.

Although it’s nice to see how the theory all ‘fits together,’ I know you want to see some code, so the final part of this series will introduce a quadratic (interpolative) spline in Degrafa 🙂

Categories: Flex, Math Tags: , ,

Quadratic Hermite Curves Part 4

September 1, 2009 Comments off

Part 3 of this series introduced a method to draw the tangent segment to the quadratic Hermite curve at a fixed length at any parameter value.  This was contrasted to the geometric interpretation of the end  tangent to the first segment.

By directly computing the end tangent using the methodology in part 2, we have a vector that can be used as an initial tangent for a second Hermite curve with a common join point at P1.  What is the maximum continuity that could be achieved at the join?  The derivative of a quadratic curve is linear in t (first-degree polynomial) so the second derivative is a constant, namely 2c in terms of the polynomial coefficients.

Recall from part 1 that c = P1 – P0 – T1 for the first curve (where T1 is the start tangent for the first segment).  If the join point is P1 and the second curve interpolates some point P2, then its corresponding coefficient is P2 – P1 – T2.  The second derivatives can only be equal if P1 – P0 – T1 = P2 – P1 – T2 or 2P1 = P0 + P2 + (T1-T2).

In general, only C-1 continuity can be achieved.

This continuity is easy to achieve based on the simplicity of the curve construction.   The end tangent for the first curve is used to set the start tangent for the second curve.  This is illustrated in following screenshot.

Joining two quadratic Hermite curves with C-1 continuity

Joining two quadratic Hermite curves with C-1 continuity

To experiment with the demo, the first Hermite curve is drawn as in prior demos.  A crosshair appears in the drawing area.  Click to define the P2 point and the second segment is drawn.  You may study the code to see the algorithm in action.

In the next part of this series, we will look at extending this method to an aribtrary number of interpolation points.

View demo.

View source.