[x3d-public] cubic spline interpolation, glTF alignment

[Andreas Plesch]

Alignment of SplineInterpolator nodes with glTF spline interpolation for
X3D 4.0

Summary:

X3D and glTF spline interpolation agree well on the interpolation method
but currently differ on how tangents are derived from input data. There are
two significant differences: X3D uses only one input tangent, whereas glTF
uses two input tangents. And X3D weights tangents in terms of a fraction,
eg. unitless time, whereas glTF weights by the current interval in units of
time, eg seconds. This has implications on the magnitude of the supplied
tangent data, and requires a conversion.
To align X3D with glTF, a new mode field for the spline interpolator nodes
is proposed which can be used for switching processing to a glTF compatible
mode. The mode field's default value (say 'useVelocity') would not lead to
any changes in behaviour. A value of say 'useTangents' would lead to the
following changes in behaviour:

Expect and require a and b type tangents in a keyValue triplet: inTangent
(a_i) value (p_i) outTangent (b_i).
Ignore the keyVelocity field.
Use
  *p*(*t*) = (2*t*3 - 3*t*2 + 1)*p*0 + (*t3* - 2*t*2 + *t*)*m*0 + (-2*t*3 +
3*t*2)*p*1 + (*t*3 - *t*2)*m*1

t is the fractional time in the current interval t_i to t_i+1
where the tangents are
*m_*0 = (*t_i*+1 - *t_**i*)*b_i*
*m_*1 = (*t_i*+1 - *t_**i*)*a_i*+1

As an implementation note, it is important to recognize that time t is not
the fraction_changed relative time used in the key field but the time in
seconds since the start of the current cycle, eg. fraction_changed times
cycleInterval. This is how glTF tangents are defined. It would be also
possible to define t_i as fractional time (eg. key) and require conversion
of glTF tangents a and b during import by multiplication with the glTF
animation duration (cycleInterval).

It is possible to convert old keyVelocity values to new in and outTangent
values, so over time the default for the mode could become the new
behaviour.

Detailed discussion:

x3d
http://www.web3d.org/documents/specifications/19775-1/V3.3/index.html
gltf
https://github.com/KhronosGroup/glTF/blob/master/specification/2.0/README.md#appendix-c-spline-interpolation

fractional time is identical:
s in x3d
t in gltf

velocity/tangent:
T vector in x3d
m vector in gltf, m is input weighted by interval

x3d calculation if velocities are given:
v_s = S^T H C

S=
s^3
s^2
s
1
H=
2 -2 1 1
-3 3 -2 -1
0 0 1 0
1 0 0 0
C=
v_i
v_i+1
T0_i
T1_i+1

S^T H C =
(2 v_i- 2 v_i+1 + T0_i + T1_I+1)s3 +
(-3 v_i  + 3 v_I+1 -2 T0_i - T1_i+1)s2 +
(T0_i)s +
v_i

S^T H C =
v_i(2s3 - 3s2 +1) +
v_i+1(-2s3 +3s2 +1) +
T0_i(s3 -2s2 +s) +
T1_i(s3 - s2)

glTF:

  *p*(*t*) = (2*t*3 - 3*t*2 + 1)*p*0 + (*t3* - 2*t*2 + *t*)*m*0 + (-2*t*3 +
3*t*2)*p*1 + (*t*3 - *t*2)*m*1

The formula's for X3D and glTF are identical if
p_0 = v_i
p_1 = v_i+1
m_0 = T0_i
m_1 = T1_i

So the only difference is how the tangents are derived. In glTF they are:

*m_*0 = (*t_**k*+1 - *t_**k*)*b_*k
*m_*1 = (*t_**k*+1 - *t_**k*)*a_*k+1
where a and b are provided. a is called the in-tangent and b the
out-tangent.

In x3d the tangents are:

T0_i = F+i T_i
T1_i = F-i T_i

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 keyVelocities T_i are provided. So here they are also weighted by
time intervals but in a different way. There are two significant
differences: Only one input tangent is used, T_i, whereas glTF uses two
input tangents. And weight is in terms of a fraction, eg. unitless time,
whereas glTF uses the current interval in units of time, eg seconds. This
has implications on the magnitude of the supplied tangent data.

Is it possible to keep the x3d definition of a tangent and align with glTF
by treating the keyVelocity field as in-tangent and adding a keyVelocityOut
field as out-tangent ?

If the keyVelocityOut field is empty, no changes in behaviour.
If the keyVelocityOut field is populated, use its values Tout_i in

T0_i = F+i Tout_i
instead of
T0_i = F+i T_i

How to convert the glTF tangent data to x3d tangent data ?
m_1 = T1_i
(*t_i*+1 - *t_**i*)*a_i* =  2 T_i  (t_i+1 - t_i) / (t_i+1 - t_i-1)
T_i = *a_i *(t_i+1 - t_i-1) / 2 ; conversion during loading of glTF

T_i: keyVelocity derived from
a_i: in-tangent glTF data
t_i absolute time; fraction_changed * duration (!);

Tout_i : keyVelocityOut field
m_0 = T0_i
(*t_i*+1 - *t_**i*)*b_i* =  2 Tout_i  (t_i - t_i-1) / (t_i+1 - t_i-1)
Tout_i =  (*t_i*+1 - *t_**i*) *b_i *(t_i+1 - t_i-1)/2(t_i - t_i-1);
conversion during loading of glTF

So, yes, this would be possible for maximum backward compatibility.

Alternatively, propose a new mode='useTangents' field for the
SplineInterpolators which switches processing to directly expect the a and
b type tangents in a keyValue triplet: inTangent (a_i) value (v_i)
outTangent (b_i). Variants of this alternative include new nodes
(Spline2PositionInterpolator ..) or a mode field for the regular
Interpolators (PositionInterpolator mode='spline').

Using above relationships, if desired old x3d keyVelocity type tangents
could be converted as:

m_0 = T0_i
(*t_i*+1 - *t_**i*)*b_i* =  2 T_i  (t_i - t_i-1) / (t_i+1 - t_i-1)
*b_i* =  2 T_i  (t_i - t_i-1) / [(t_i+1 - t_i-1) (*t_i*+1 - *t_**i*)]

and
T_i = *a_i *(t_i+1 - t_i-1) / 2
*a_i = 2 *T_i / (t_i+1 - t_i-1)

Similar relationships could be found for the case where keyVelocity was not
provided, following the spec procedures.
For mode='useTangents' the keyVelocity field would be ignored.

inTangent and outTangents are required. This has two advantages. It makes
implementation simple and unambiguous. And it provides maximum flexibility
on exactly what kind of cubic spline is achieved since they differ only
(mostly?) in the tangent calculation. Since the tangents almost necessarily
come from a editor tool, the tool will already have calculated these
tangents for export.

x3dom currently uses the regular Interpolator plus mode field variant.

-Andreas

On Mon, Aug 6, 2018 at 1:42 AM Don Brutzman <brutzman at nps.edu> wrote:
>
> Andreas, this sounds like an excellent rationale to modify the X3D spline
interpolators in X3D v4 for better alignment with glTF.
>
> When ready, if you might state the precise gap issue and suggest an
improvement, that would be great.  We'll enter it in Mantis Issue Tracker
for continued consideration.
>
>         Web3D Standards Comment Form
>         http://www.web3d.org/content/web3d-standards-comment-form
>
> On 7/31/2018 4:06 AM, Andreas Plesch wrote:
> > As I am looking to add glTF animation support for x3dom, I am
considering convenient ways to do cubic spline and step wise interpolation
with x3d interpolators.
> > glTF has three modes of interpolation: linear, cubic spline, step.
> >
> > Linear corresponds to the linear interpolation of the regular x3d
interpolators.
> >
> > Step produces jumps at key times, and can be represented with x3d
interpolators also, by repeating keys. However, implementation could be
optimized for a special step mode.
> >
> > Cubic spline almost corresponds to the x3d spline interpolators but not
exactly. With glTF, the velocity derived tangent can be different towards
and away from a key frame, while in x3d there is only a single velocity.
Also, in glTF, the tangents are requied and part of a 3 tuple for each
frame. This makes computing the cubic spline interpolation straightforward
and performant.
> >
> > So it turns out to be most convenient and efficient to forgo the x3d
spline interpolators and instead add a mode SFString init only field to the
regular interpolators with a 'linear' default. I currently have it not
exposed declaratively and for use with glTF only but why not expose it.
> >
> > Such a mode field allows for optimization of step and cubic spline
interpolation over regular, and NURBS interpolators, and allows for full
glTF animation support.
> >
> > Other browsers may have similar goals but likely differing strategies
which would be great to hear about.
> >
> > Any feedback or comment much welcome,
> thank you
>
> all the best, Don
> --
> Don Brutzman  Naval Postgraduate School, Code USW/Br
brutzman at nps.edu
> Watkins 270,  MOVES Institute, Monterey CA 93943-5000 USA
 +1.831.656.2149
> X3D graphics, virtual worlds, navy robotics
http://faculty.nps.edu/brutzman
>






On Mon, Aug 6, 2018 at 1:42 AM Don Brutzman <brutzman at nps.edu> wrote:
>
> Andreas, this sounds like an excellent rationale to modify the X3D spline
interpolators in X3D v4 for better alignment with glTF.
>
> When ready, if you might state the precise gap issue and suggest an
improvement, that would be great.  We'll enter it in Mantis Issue Tracker
for continued consideration.
>
>         Web3D Standards Comment Form
>         http://www.web3d.org/content/web3d-standards-comment-form
>
> On 7/31/2018 4:06 AM, Andreas Plesch wrote:
> > As I am looking to add glTF animation support for x3dom, I am
considering convenient ways to do cubic spline and step wise interpolation
with x3d interpolators.
> > glTF has three modes of interpolation: linear, cubic spline, step.
> >
> > Linear corresponds to the linear interpolation of the regular x3d
interpolators.
> >
> > Step produces jumps at key times, and can be represented with x3d
interpolators also, by repeating keys. However, implementation could be
optimized for a special step mode.
> >
> > Cubic spline almost corresponds to the x3d spline interpolators but not
exactly. With glTF, the velocity derived tangent can be different towards
and away from a key frame, while in x3d there is only a single velocity.
Also, in glTF, the tangents are requied and part of a 3 tuple for each
frame. This makes computing the cubic spline interpolation straightforward
and performant.
> >
> > So it turns out to be most convenient and efficient to forgo the x3d
spline interpolators and instead add a mode SFString init only field to the
regular interpolators with a 'linear' default. I currently have it not
exposed declaratively and for use with glTF only but why not expose it.
> >
> > Such a mode field allows for optimization of step and cubic spline
interpolation over regular, and NURBS interpolators, and allows for full
glTF animation support.
> >
> > Other browsers may have similar goals but likely differing strategies
which would be great to hear about.
> >
> > Any feedback or comment much welcome,
> thank you
>
> all the best, Don
> --
> Don Brutzman  Naval Postgraduate School, Code USW/Br
brutzman at nps.edu
> Watkins 270,  MOVES Institute, Monterey CA 93943-5000 USA
 +1.831.656.2149
> X3D graphics, virtual worlds, navy robotics
http://faculty.nps.edu/brutzman
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://web3d.org/pipermail/x3d-public_web3d.org/attachments/20180810/50d6da34/attachment-0001.html>