[x3d-public] cubic spline interpolation, glTF alignment

Sat Aug 11 08:12:55 PDT 2018

Since the formatting may have not survived email transport, I put a
formatted version here:

https://github.com/andreasplesch/x3dom/wiki/SplineInterpolator-nodes-with-glTF-spline-interpolation

-Andreas
On Fri, Aug 10, 2018 at 11:29 AM Andreas Plesch <andreasplesch at gmail.com> wrote:
>
> 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) = (2t3 - 3t2 + 1)p0 + (t3 - 2t2 + t)m0 + (-2t3 + 3t2)p1 + (t3 - t2)m1
>
> 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) = (2t3 - 3t2 + 1)p0 + (t3 - 2t2 + t)m0 + (-2t3 + 3t2)p1 + (t3 - t2)m1
>
> 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
> >
>
>

-- 
Andreas Plesch
Waltham, MA 02453