19.1 Introduction

19.1.1 Name

The name of this component is "Interpolation". This name shall be used when referring to this component in the COMPONENT statement (see 7.2.5.4 Component statement).

19.1.2 Overview

This subclause describes the Interpolation component of this part of ISO/IEC 19775. Table 19.1 provides links to the major topics in this subclause.

19.2 Concepts

This clause includes six Interpolator nodes all of which provide keyframe-based animation capability.

19.2.1 Interpolators

The Interpolator nodes provide interpolation between animation key frame values. The following node types are Interpolator nodes, each based on the type of value that is interpolated:

• ColorInterpolator
• CoordinateInterpolator
• CoordinateInterpolator2D
• NormalInterpolator
• OrientationInterpolator
• PositionInterpolator
• PositionInterpolator2D
• ScalarInterpolator
• SplinePositionInterpolator
• SplinePositionInterpolator2D
• SplineScalarInterpolator
• SquadOrientationInterpolator
• EaseInEaseOut

All Interpolator nodes are based on the abstract type X3DInterpolatorNode.

19.2.2 Linear interpolation

The X3D interpolator nodes specified in this clause are designed for linear key framed animation. Each of these nodes defines a piecewise-linear function, f(t), on the interval (−∞,∞). The piecewise-linear function is defined by n values of t, called key, and the n corresponding values of f(t), called keyValue. The keys shall be monotonically non-decreasing, otherwise the results are undefined.

An interpolator node evaluates f(t) given any value of t (via the fraction field) as follows: Let the n keys t₀, t₁, t₂, ..., t_n−1 partition the domain (−∞,∞ ) into the n+1 subintervals given by (-∞, t₀), [t₀, t₁), [t₁, t₂), ... , [t_n−1, +∞ ). Also, let the n values v₀, v₁, v₂, ..., v_n-1 be the values of f(t) at the associated key values. The piecewise-linear interpolating function, f(t), is defined to be:

    f(t) = v₀,    if t ≤ t₀,
         = v_n−1,   if t ≥ t_n−1,
         = linterp(t, v_i, v_i+1),    if t_i≤ t ≤ t_i+1,

     where linterp(t,x,y) is the linear interpolant,
           i belongs to {0,1,..., n−2}.

The third conditional value of f(t) allows the defining of multiple values for a single key, ( i.e., limits from both the left and right at a discontinuity in f(t)). The first specified value is used as the limit of f(t) from the left, and the last specified value is used as the limit of f(t) from the right. The value of f(t) at a multiply defined key is indeterminate, but should be one of the associated limit values.

19.2.3 Non-linear interpolation

This component also provides non-linear interpolator nodes that provide for smoother animation than the linear interpolator nodes. Linear interpolators tend to produce animations that have a discontinuous velocity vectors. The transitions at the keys produce a noticeably jerky effect which will not occur when using non-linear interpolator nodes.

The non-linear interpolator nodes consist of three spline interpolator nodes for 3D, 2D, and scalar interpolation. These three nodes use the Hermite spline interpolation with adjustments to accommodate non-uniform key intervals (see 19.2.4 Hermite spline interpolation). The SquadOrientationInterpolator node supports non-linear orientation interpolation.

Each of non-linear interpolator nodes provides a SFBool closed field that specifies whether the interpolator should provide a closed loop, with continuous velocity vectors as the interpolator transitions from the last key to the first key. If the velocity vectors at the first and last keys are specified, the closed field is ignored. If the keyValues at the first and last key are not identical, the closed field is ignored.

The SFBool normalizeVelocity field specifies whether the velocity vectors are to be transformed into tangency vectors. If the normalizeVelocity field has value TRUE, the keyVelocity values are normalized, thus converting them to tangency vectors. In this case, the vectors are normalized to produce smooth speed transitions, as described mathematically below in 19.2.4 Hermite spline interpolation. The magnitude of the specified velocity vectors is ignored.

If the normalizeVelocity field has value FALSE, the units specified in the velocity field are defined to be length/cycleInterval.

EXAMPLE  Using a SplinePositionInterpolator, in which the velocity at a key is specified to be (0, 0, 1), and the cycleInterval that drives the interpolator is 4 seconds, the actual speed of the object at that key is 0.25 metres per second (assuming the initial base units have been specified).

In addition to the interpolation nodes, this component provides a node that modifies the time fraction that is typically fed from the TimeSensor node into the interpolator node. This is the EaseInEaseOut node. It allows for a deceleration as the interpolator approaches a key, and an acceleration as the interpolator exits a key. Authors can route time fraction events into the EaseInEaseOut node. The EaseInEaseOut node will then send out a modified time fraction, which can them be routed into one or more interpolators.

19.2.4 Hermite spline interpolation

The SplinePositionInterpolator, SplinePositionInterpolator2D, and the SplineScalarInterpolator nodes all use the Hermite spline interpolation with adjustments to accommodate non-uniform key intervals. These three nodes all use the same algorithm which is described below.

The algorithm used by these interpolators is as follows. It defines the output value sent form the value_changed field for a given segment of the interpolation, between key(i), and key(i+1). This segment is valid when the fraction value satisfies (t_i ≤ fraction < t_i+1), where t_i is the key at (i), and t_i+1 is the key at (i+1).

The local fraction will vary from zero to one between the two keys, as follows:

s = (t - t_i) / (t_i+1 - t_i)

The velocity vectors at key (i) and key (i+1) are denoted by T_i and T_i+1 respectively. These velocity vectors need not be unit vectors. The magnitude of these vectors specifies the relative speed of the interpolation.

If the size of the keyVelocity field is equal to the size of the keyValue field, the values of T used below should come from the keyVelocity field. If the size of the keyVelocity field is 2, the first value is used as the velocity vector for the first key, and the second value is used as the velocity for the last key. If the size of the keyVelocity field is anything other than those two values, the keyVelocity field is ignored. Any velocity vectors that are not specified will be calculated using the following algorithm:

The keyValue at key (i) is denoted as v_i and the keyValue at key (i+1) is denoted as v_i+1.

With those parameters defined, the value_changed value ( v_s) can be calculated as follows:

v_s = S^T H C

where

S=	s3		H=	2	-2	1	1		C=	vi
	s2			-3	3	-2	-1			vi+1
	s			0	0	1	0			T0i
	1			1	0	0	0			T1i+1

The values of T⁰_i and T¹_i+1 are defined as follows:

The standard Hermite spline assumes that the keys are equally spaced. Since this is not a valid assumption, these values are ajusted to calculate T⁰_i and T¹_i+1 as follows. If the velocity vector is specified by the author, the value of T_i is extracted from the keyVelocity field for the specific key.

If the velocity vector is not specified, it is calculated as follows:

T_i = ( v_i+1 - v_i-1) / 2

There are special cases as specified below:

If the velocity vector is specified, and the normalizeVelocity flag has value FALSE, the velocity at the key is set to the corresponding value of the keyVelocity field:

T_i = keyVelocity[ i ]

If the velocity vector is specified, and the normalizeVelocity flag is TRUE, the velocity at the key is set using the corresponding value of the keyVelocity field:

T_i = keyVelocity[i] × (D_tot / |keyVelocity[i]| )

where:

D_tot is the sum of the distance between all adjacent keys.

or

D_tot = SUM{i=0, i < n-1}(|vi - vi+1|)

Lastly, to accommodate the non-uniform key intervals, the values of T⁰_i and T¹_i are calculated as follows:

T⁰_i = F⁺i T_i
T¹_i = F^-_i T_i

where:

F^-_i  = 2 (t_i+1 - t_i) / (t_i+1 - t_i-1)
F⁺i = 2 (t_i - t_i-1) / (t_i+1 - t_i-1)

If the interpolator is closed, the values of the key and keyValue used in these calculations should wrap appropriately:

t_-1 = t_N-2
v_-1 = v_N-2
t_N = t₁
v_N = v₁

If the interpolator is not closed, and the first and last velocity vectors are not specified by the author, the values are calculated as follows:

T⁰₀ = T¹₀ = T⁰_N-1 = T¹_N-1 = 0

If the interpolator is not closed, and the first and last velocity vectors are specified by the author, the values are calculated as follows:

T⁰₀ = T₀
T¹_N-1 = T_N-1

where N is the size of the keyValue field.

Additional information on the Hermite algorithm is available in [CATROM].

19.3 Abstract types

19.3.1 X3DInterpolatorNode

X3DInterpolatorNode : X3DChildNode { 
  SFFloat      [in]     set_fraction       (-∞,∞)
  MFFloat      [in,out] key           []   (-∞,∞)
  MF<type>     [in,out] keyValue      []
  SFNode       [in,out] metadata      NULL [X3DMetadataObject]
  [S|M]F<type> [out]    value_changed
}

The abstract node X3DInterpolatorNode forms the basis for all types of interpolators specified in this clause.

The key field contains the list of key times, which might appear as:

    key [0 0.25 0.65 0.75 1]

to indicate there are five key frames in this node. The keyValue field contains values for the target field, one complete set of values for each key. Interpolator nodes containing no keys in the key field shall not produce any events. However, an input event that replaces an empty key field with one that contains keys will cause the interpolator node to produce events the next time that a set_fraction event is received..

The set_fraction inputOnly field receives an SFFloat event and causes the interpolator node function to evaluate, resulting in a value_changed output event of the specified type with the same timestamp as the set_fraction event.

The contents of the keyValue and value_changed fields are dependent on the type of the node ( e.g., the PositionInterpolator fields use MFVec3f values). Each value or set of values in the keyValue field corresponds in order to the parameter value in the key field.

For interpolator nodes that produce a single value, results are undefined if the number of values in the key field is not the same as the number of values in the keyValue field.

For interpolator nodes that produce multiple values, the keyValue field is an nx m array of values, where n is the number of values in the key field and m is the number of values at each key frame. Each m values in the keyValue field correspond, in order, to a parameter value in the key field. Each value_changed event shall contain m interpolated values. Results are undefined if the number of values in the keyValue field is not a positive integer multiple of the number of values in the key field.

If an X3DInterpolatorNode value_changed outputOnly field is read before it receives any inputs, keyValue[0] is returned if keyValue is not empty. If keyValue is empty ( i.e., [ ]), the initial value for the respective field type is returned (EXAMPLE  (0, 0, 0) for SFVec3f); see 5 Field type reference for initial event values.

The location of an X3DInterpolatorNode in the transformation hierarchy has no effect on its operation. For example, if a parent of an interpolator node is a Switch node with whichChoice set to −1 ( i.e., ignore its children), the interpolator continues to operate as specified (receives and sends events).

A typical simplified structure for a key frame animation implementation involves a TimeSensor, ROUTEs, and the target node.

  Transform { 
    Shape 
       IndexedFaceSet { coordIndex='... −1 ... >
           Coordinate DEF='Moved' point [ x y z, ... ] #   t0Geometry
       }                  
    } 
  } 

  CoordinateInterpolator DEF='Mover' 
      key [t0 t1 t2 ]            #    list of key times, 0 to 1
      keyValue ' x y z, ... '    #    one geometry per key time 

  TimeSensor DEF='Timer' cycleInterval 5 loop TRUE 

  ROUTE Timer.fraction_changed TO Mover.set_value  
  ROUTE Mover.value_changed TO Moved.point 

In typical operation, the key frame set_fraction event arrives from a TimeSensor to signal that the time value has advanced. This value varies from 0 to 1 depending upon where the TimeSensor is in its cycle time.

EXAMPLE  If the TimeSensor has a cycleTime of 10 seconds, and 5 seconds has elapsed in its cycle, the set_fraction value will be 0.5.

In this sample structure, the IndexedFaceSet contains a Coordinate field named Moved. This defines the time equals zero geometry for the node. The CoordinateInterpolator node named Mover contains the list of key frame times and the corresponding sets of coordinates in the keyValue field. When the set_fraction event arrives for key, the corresponding interpolated keyValue is sent to the target Coordinate node for rendering.

19.4 Node reference

19.4.1 ColorInterpolator

ColorInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFColor [in,out] keyValue      []   [0,1]
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  SFColor [out]    value_changed
}

The ColorInterpolator node interpolates among a list of MFColor key values to produce an SFColor (RGB) value_changed event. The number of colours in the keyValue field shall be equal to the number of key frames in the key field. The keyValue field and value_changed events are defined in RGB colour space. A linear interpolation using the value of set_fraction as input is performed in HSV space (see [FOLEY] for description of RGB and HSV colour spaces). The results are undefined when interpolating between two consecutive keys with complementary hues.

19.4.2 CoordinateInterpolator

CoordinateInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFVec3f [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  MFVec3f [out]    value_changed
}

The CoordinateInterpolator node linearly interpolates among a list of MFVec3f values to produce an MFVec3f value_changed event. The number of coordinates in the keyValue field shall be an integer multiple of the number of key frames in the key field. That integer multiple defines how many coordinates will be contained in the value_changed events.

19.4.3 CoordinateInterpolator2D

CoordinateInterpolator2D : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFVec2f [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  MFVec2f [out]    value_changed
}

This node linearly interpolates among a list of MFVec2f values to produce an MFVec2f value_changed event. The number of coordinates in the keyValue field shall be an integer multiple of the number of key frames in the key field. That integer multiple defines how many coordinates will be contained in the value_changed events.

19.4.4 EaseInEaseOut

EaseInEaseOut :  X3DChildNode {
  SFFloat [in]     set_fraction                  (-∞,∞)
  MFVec2f [in,out] easeInEaseOut            []   (-∞,∞)
  MFFloat [in,out] key                      []   (-∞,∞) 
  SFNode  [in,out] metadata                 NULL [X3DMetadataObject]
  SFFloat [out]    modifiedFraction_changed
}

The EaseInEaseOut node supports controlled gradual transitions by specifying modifications for TimeSensor node fractions. The EaseInEaseOut node receives a set_fraction field event. It uses the values of the key field and the easeInEaseOut field to modify that fraction which is then issued as a modifiedFraction_changed event.

The values of the easeInEaseOut field range from zero to one. At zero, there is no modification of the fraction.

The scope of the easeOut effect on the local fraction is equal to the easeOut value.

EXAMPLE 1  If the easeOut value is 0.4, the object will accelerate out of the previous key and reach a constant speed at 40% of the way from the previous key to the next key.

The scope of the easeIn effect on the local fraction begins when the local fraction reaches (1.0 - easeIn).

EXAMPLE 2  If the easeIn value is 0.3, the object will transition from a constant speed, and begin to decelerate when unmodified local fraction reaches 0.7 (70% of the way from the previous key to the next key).

If the sum of the previous easeIn value, plus the next easeIn value is greater than 1.0, both values are scaled by the same amount so that the sum of the values is equal 1.0. In that case, there is no period of constant speed.

The algorithm for computing the modifiedFraction_changed value is:

1. Let u be the value of the set_fraction field, representing the proportion the distance between key_i and key_i+1.
2. Let e_out be the easeOut value for key_i; ( i.e., easeOut = easeInEaseOut_i.y).
3. Let e_in be the easeIn value for key_i+1; ( i.e., easeIn = easeInEaseOut_i+1.x).
4. Let S be the sum of e_inand e_out.
5. If S < 0, modifiedFraction_changed is set to u.
6. If S > 1.0, divide e_in and e_out by S.
7. Compute t = 1.0 / (2.0 - e_out - e_in).
8. If u < e_out, modifiedFraction_changed is set to:
       (t / e_out) × u²
9. If u < 1.0 - e_in, modifiedFraction_changed is set to:
       (t × (2u - e_out))
10. Else, modifiedFraction_changed is set to:
        1.0 - ((t × (1.0 - u)²) / e_in)

Figure 19.1 illustrates the algorithm above.

The easeInEaseOut field values shall be monotonically non-decreasing, otherwise results are undefined.

19.4.5 NormalInterpolator

NormalInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFVec3f [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  MFVec3f [out]    value_changed
}

The NormalInterpolator node interpolates among a list of normal vector sets specified by the keyValue field to produce an MFVec3f value_changed event. The output vector, value_changed, shall be a set of normalized vectors.

Values in the keyValue field shall be of unit length. The number of normals in the keyValue field shall be an integer multiple of the number of key frames in the key field. That integer multiple defines how many normals will be contained in the value_changed events.

Normal interpolation shall be performed on the surface of the unit sphere. That is, the output values for a linear interpolation from a point P on the unit sphere to a point Q also on the unit sphere shall lie along the shortest arc (on the unit sphere) connecting points P and Q. Also, equally spaced input fractions shall result in arcs of equal length. The results are undefined if P and Q are diagonally opposite.

19.4.6 OrientationInterpolator

OrientationInterpolator : X3DInterpolatorNode {
  SFFloat    [in]     set_fraction       (-∞,∞)
  MFFloat    [in,out] key           []   (-∞,∞)
  MFRotation [in,out] keyValue      []   [-1,1] or (-∞,∞)
  SFNode     [in,out] metadata      NULL [X3DMetadataObject]
  SFRotation [out]    value_changed
}

The OrientationInterpolator node interpolates among a list of rotation values specified in the keyValue field to produce an SFRotation value_changed event. These rotations are absolute in object space and therefore are not cumulative. The keyValue field shall contain exactly as many rotations as there are key frames in the key field.

An orientation represents the final position of an object after a rotation has been applied. An OrientationInterpolator interpolates between two orientations by computing the shortest path on the unit sphere between the two orientations. The interpolation is linear in arc length along this path. The results are undefined if the two orientations are diagonally opposite.

If two consecutive keyValue values exist such that the arc length between them is greater than π, the interpolation will take place on the arc complement. For example, the interpolation between the orientations

(0, 1, 0, 0) and (0, 1, 0, 5.0)

is equivalent to the rotation between the orientations

(0, 1, 0, 2π) and (0, 1, 0, 5.0).

19.4.7 PositionInterpolator

PositionInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFVec3f [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  SFVec3f [out]    value_changed
}

The PositionInterpolator node linearly interpolates among a list of 3D vectors to produce an SFVec3f value_changed event. The keyValue field shall contain exactly as many values as in the key field.

19.4.8 PositionInterpolator2D

PositionInterpolator2D : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFVec2f [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  SFVec2f [out]    value_changed
}

The PositionInterpolator2D node linearly interpolates among a list of 2D vectors to produce an SFVec2f value_changed event. The keyValue field shall contain exactly as many values as in the key field.

19.4.9 ScalarInterpolator

ScalarInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction       (-∞,∞)
  MFFloat [in,out] key           []   (-∞,∞)
  MFFloat [in,out] keyValue      []   (-∞,∞)
  SFNode  [in,out] metadata      NULL [X3DMetadataObject]
  SFFloat [out]    value_changed
}

The ScalarInterpolator node linearly interpolates among a list of SFFloat values to produce an SFFloat value_changed event. This interpolator is appropriate for any parameter defined using a single floating point value.

EXAMPLE 1  width fields

EXAMPLE 2  radius fields

EXAMPLE 3  intensity fields

The keyValue field shall contain exactly as many numbers as there are key frames in the key field.

19.4.10 SplinePositionInterpolator

SplinePositionInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction            (-∞,∞)
  SFBool  [in,out] closed            FALSE
  MFFloat [in,out] key               []    (-∞,∞)
  MFVec3f [in,out] keyValue          []    (-∞,∞)
  MFVec3f [in,out] keyVelocity       []    (-∞,∞)
  SFNode  [in,out] metadata          NULL  [X3DMetadataObject]
  SFBool  [in,out] normalizeVelocity FALSE
  SFVec3f [out]    value_changed
}

The SplinePositionInterpolator node non-linearly interpolates among a list of 3D vectors to produce an SFVec3f value_changed event. The keyValue, keyVelocity, and key fields shall each have the same number of values.

The normalizeVelocity field is as defined in 19.2.3 Non-linear interpolation.

19.4.11 SplinePositionInterpolator2D

SplinePositionInterpolator2D : X3DInterpolatorNode {
  SFFloat [in]     set_fraction            (-∞,∞)
  SFBool  [in,out] closed            FALSE
  MFFloat [in,out] key               []    (-∞,∞)
  MFVec2f [in,out] keyValue          []    (-∞,∞)
  MFVec2f [in,out] keyVelocity       []    (-∞,∞)
  SFNode  [in,out] metadata          NULL  [X3DMetadataObject]
  SFBool  [in,out] normalizeVelocity FALSE
  SFVec2f [out]    value_changed
}

The SplinePositionInterpolator2D node non-linearly interpolates among a list of 2D vectors to produce an SFVec2f value_changed event. The keyValue, keyVelocity, and key fields shall each have the same number of values.

The normalizeVelocity field is as defined in 19.2.3 Non-linear interpolation.

19.4.12 SplineScalarInterpolator

SplineScalarInterpolator : X3DInterpolatorNode {
  SFFloat [in]     set_fraction            (-∞,∞)
  SFBool  [in,out] closed            FALSE
  MFFloat [in,out] key               []    (-∞,∞)
  MFFloat [in,out] keyValue          []    (-∞,∞)
  MFFloat [in,out] keyVelocity       []    (-∞,∞)
  SFNode  [in,out] metadata          NULL  [X3DMetadataObject]
  SFBool  [in,out] normalizeVelocity FALSE
  SFFloat [out]    value_changed
}

The SplineScalarInterpolator node non-linearly interpolates among a list of floats to produce an SFFloat value_changed event. The keyValue, keyVelocity, and key fields shall each have the same number of values.

The normalizeVelocity field is as defined in 19.2.3 Non-linear interpolation.

19.4.13 SquadOrientationInterpolator

SquadOrientationInterpolator : X3DInterpolatorNode {
  SFFloat    [in]     set_fraction            (-∞,∞)
  MFFloat    [in,out] key               []    (-∞,∞)
  MFRotation [in,out] keyValue          []    (-∞,∞)
  SFNode     [in,out] metadata          NULL  [X3DMetadataObject]
  SFBool     [in,out] normalizeVelocity FALSE
  SFRotation [out]    value_changed
}

The SquadOrientationInterpolator node non-linearly interpolates among a list of rotations to produce an SFRotation value_changed event. The keyValue field shall have the same number of values and the key field.

The normalizeVelocity field is as defined in 19.2.3 Non-linear interpolation.

The SquadOrientationInterpolator uses the industry standard Squad method for smoothly interpolating orientations. Squad is an acronym for Spherical Cubic Interpolation. The Linear OrientationInterpolator described in 19.4.6 OrientationInterpolator provides spherical linear interpolation. The SquadOrientationInterpolator applies the spline interpolation approach described above to interpolation in quaternion space. For more information on Squad interpolation, see [SHOE].

19.5 Support levels

The Interpolation component provides three levels of support as specified in Table 19.2.