 Extensible 3D (X3D)
Part 1: Architecture and base components

19 Interpolation component # 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:

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 t0, t1, t2, ..., tn−1 partition the domain (−∞,∞) into the n+1 subintervals given by (-∞, t0), [t0, t1), [t1, t2), ... , [tn−1, +). Also, let the n values v0, v1, v2, ..., vn-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) = v0,    if t ≤ t0,
= vn−1,   if t ≥ tn−1,
= linterp(t, vi, vi+1),    if ti ≤ t ≤ ti+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 Catmull-Rom spline interpolation with adjustments to accommodate non-uniform key intervals (see 19.2.4 Catmull-Rom 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 Catmull_Rom 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 will be 0.25 metres per second.

In addition to the interpolation nodes, this component provides a node that modifies the time fraction that is typically feed from the TimeSensor 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 Catmull-Rom spline interpolation

The SplinePositionInterpolator, SplinePositionInterpolator2D, and the SplineScalarInterpolator nodes all use the Catmull-Rom 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 (ti ≤ fraction < ti+1), where ti is the key at (i), and ti+1 is the key at (i+1).

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

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

The velocity vectors at key (i) and key (i+1) are denoted by Ti and Ti+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 vi and the keyValue at key (i+1) is denoted as vi+1.

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

vs = ST 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 T0i and T1i+1 are defined as follows:

The standard Catmull-Rom spline assumes that the keys are equally spaced. Since this is not a valid assumption, these values are ajusted to calculate T0i and T1i+1 as follows. If the velocity vector is specified by the author, the value of Ti is extracted from the keyVelocity field for the specific key.

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

Ti = (vi+1 - vi-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:

Ti = 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:

Ti = keyVelocity[i] × ( Dtot / |keyVelocity[i]| )

where:

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

or

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

Lastly, to accommodate the non-uniform key intervals, the values of T0i and T1i are calculated as follows:

T0i = F+i Ti
T1i = F-i Ti

where:

F-i  = 2 (ti+1 - ti) / (ti+1 - ti-1)
F+i = 2 (ti - ti-1) / (ti+1 - ti-1)

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

t-1 = tN-2
v-1 = vN-2
tN = t1
vN = t1

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:

T00 = T10 = T0N-1 = T1N-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:

T00 = T0
T1N-1 = TN-1

where N is the size of the keyValue field.

Additional information on the Catmull-Rom 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      []
[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 could 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 nxm 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 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. For 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]
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      []   (-∞,∞)
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      []   (-∞,∞)
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 : X3DNode {
SFFloat [in]     set_fraction                  (-∞,∞)
MFVec2f [in,out] easeInEaseOut            []   (-∞,∞)
MFFloat [in,out] key                      []   (-∞,∞)
SFFloat [out]    modifiedFraction_changed
}
```

The EaseInEaseOut node supports controlled gradual transitions by specifying modifications for TimeSensor node fractions. The EaseInEaseOut node receives 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 easeInEaseOut field shall have the same size as the key field, and each Vec2f value of the easeInEaseOut field corresponds to the key value with the same index. The first component of each easeInEaseOut field Vec2f value corresponds to the easeIn feature as the interpolator approaches the key, and the second component of each easeInEaseOut field Vec2f value corresponds to the easeOut feature as the interpolator progresses away from the key.

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_change value is:

1. Let u be the value of the fraction field representing the proportion the distance between keyi and keyi+1.
2. Let eout be the easeOut value for keyi.
3. Let ein be the easeIn value for keyi+1.
4. Let S be the sum of einand eout.
5. If S < 0, modifiedFraction_changed is set to u.
6. If S > 1.0, divide ein and eout by S.
7. Compute t = 1.0 / (2.0 - eout - ein).
8. If u < eout, modifiedFraction_changed is set to:
(t / eout) × u2
9. If u < 1.0 - ein, modifiedFraction_changed is set to:
(t × (2u - eout)
10. Else, modifiedFraction_changed is set to:
1.0 - ((t × (1.0 - u)2) / ein)

## 19.4.5 NormalInterpolator

```NormalInterpolator : X3DInterpolatorNode {
SFFloat [in]     set_fraction       (-∞,∞)
MFFloat [in,out] key           []   (-∞,∞)
MFVec3f [in,out] keyValue      []   (-∞,∞)
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 (-∞,∞)
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      []   (-∞,∞)
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      []   (-∞,∞)
SFVec2f [out]    value_changed
}
```

The PositionInterpolator 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      []   (-∞,∞)
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 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       []    (-∞,∞)
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.

## 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       []    (-∞,∞)
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.

## 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       []    (-∞,∞)
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.

```SquadOrientationInterpolator : X3DInterpolatorNode {
SFFloat    [in]     set_fraction            (-∞,∞)
MFFloat    [in,out] key               []    (-∞,∞)
MFRotation [in,out] keyValue          []    (-∞,∞)
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 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.

Table 19.2Interpolation component support levels

Level Prerequisites Nodes/Features Support
1 Core 1
Grouping 1
Shape 1
X3DInterpolatorNode (abstract) n/a
CoordinateInterpolator All fields fully supported.
OrientationInterpolator All fields fully supported.
PositionInterpolator All fields fully supported.
ScalarInterpolator All fields fully supported.
2 Core 1
Grouping 1
Shape 1
All Level 1 Interpolator nodes All fields fully supported.
ColorInterpolator All fields fully supported.
NormalInterpolator All fields fully supported.
3 Core 1
Grouping 1
Shape 1
All Level 2 Interpolator nodes All fields fully supported.
CoordinateInterpolator2D All fields fully supported.
PositionInterpolator2D All fields fully supported.
4 Core 1
Grouping 1
Shape 1

All Level 3 Interpolator nodes All fields fully supported.
EaseInEaseOut All fields fully supported.
SplinePositionInterpolator All fields fully supported.
SplinePositionInterpolator2D All fields fully supported.
SplineScalarInterpolator All fields fully supported.
5 Core 1
Grouping 1
Shape 1

All Level 4 Interpolator nodes All fields fully supported. 