Compuer Animation(Postgraduate Course): Lecture 4:Keyframe interpolation and velocity control

Lecture 4: Keyframe interpolation and velocity control

动画中的运动感控制：

• 运动的表示： 用数学方法来表示各类物体的运动

• 运动的控制和编辑： 给动画师提供能够表达他意图的方便、直观的控制工具

• 运动的生成： 计算每一帧所需的各种运动参数

Goal：再现物理世界的运动，超越物理世界的运行。

I.Interpolation between key frames

1.Parameters to be interpolated:

• Position of an object

• Scale of an object

• Orientation of an object

• Joint angle between two joints

• Color attribute of an object

2.Interpolation between frames is not trivial:

• Appropriate interpolation function

• Parameterization of the function

• Maintain the desired control of the interpolated values over time

3.Solution:

• Generate a space curve

• Distribute points evenly along curve

• Speed control: vary points

4.Interpolation v.s. Approximation:

• An interpolating spline in which the spline passes through the interior control points.

• An approximating spline in which only the endpoints are interpolated; the interior control points are used only to design the curve.

5.Interpolation function:

• Complexity -> computational efficiency:

• Polynomials

• Lower than cubic: No inflection point, may not fit smoothly to some data points

• Higher than cubic: Doesn’t provide any significant advantages, costly to evaluate

• Piecewise cubic: Provides sufficient smoothness; Allows enough flexibility to satisfy constraints such as end-point position and tangents.

• Continuity within a curve:

• Zero-order

• First order(tangential): Suffices for animation applications

• Second order: Important when dealing with time-distance curve

• Continuity between curve segments: Hermite, Catmull-Rom, cubic Bezier provide first order continuity between segments.

Local control: moving one control point only change the curve over a finite bounded region

Global control: moving one control point changes the entire curve; distant sections may change only slightly.

6.Types of Curve Representation

• Explicit: $y=f(x)$

• Good for generating points

• For each input, there is a unique output

• Implicit $f(x,y)=0$

• Good for testing if a point is on a curve

• Bad for generating a sequence of points

• Parametric $x=f(u),y=g(u)$

• Good for generating a sequence of points

• Can be used for multi-valued function of $x$

Parametric form: $P(u)=\left(P_x(u),P_y(u),P_z(u)\right)$:$$x=P_x(u),y=P_y(u),z=P_z(u)$$

II.Polynomial Interpolation

• An $n$-th degree polynomial fits a curve to $n+1$ points, called Lagrange Interpolation.

• Result is a curve that is too wiggly, change to any control affects entire curve(nonlocal)—this method is poor.

• We usually want the curve to be as smooth as possible:

• minimize the wiggles

• high-degree polynomials are bad

• Composite Segment

• Divide a curve into multiple segments

• Represent each in a parametric form

• Maintain continuity between segments

• position

• Tangent(C1-continuity v.s. G1-continuity)

• curvature

• Spline:Piecewise Polynomials

• A spline is a piecewise polynomial - many low degree polynomials are used to interpolate(pass through) thr control points

• Cubic polynomials are the most common

• lowest order polynomials that interpolate two points and allow the gradient at each point to be defined -C1 continuity is possible

• Higher or lower degree are possible, of course.

• A Linear Piecewise Polynomial

$$p(u)=up_1+(1-u)p_2$$

III.Hermite Interpolation

• Hermite Curves-cubic polynomial for two points $$P(u)=au^3+bu^2+cu+d$$ $$P(u)=\left(P_x(u),P_y(u),P_z(u)\right)$$

• Hermite interpolation requires: Endpoint positions, derivatives at endpoints

• To create a composite curve, use the end of one as the beginning of the other and share the tangent vector.

• Solution:$$\begin{cases}a_x=2(P_x(0)-P_x(1))+P_x'(0)+P_x'(1)\\ b_x=3(P_x(1)-P_x(0))-2P_x'(0)-P_x'(1)\\ c_x=P_x'(0)\\ d_x=P_x(0)\\\end{cases}$$

• Blending Functions of Hermite Splines

Each cubic Hermite spline is a linear combination of 4 blending functions

$$P(u)=U^TMB$$

$$p(u)=\begin{bmatrix}2u^3-3u^2+1\\ -2u^3+3u^2\\ u^3-2u^2+u\\ u^3-u^2\\\end{bmatrix}\begin{bmatrix}p_1\\p_2\\p_1'\\p_2'\end{bmatrix}$$

• Composite Hermite Curve: Continuity between connected segments is ensured by using ending tangent vector of one segment as the beginning tangent vector of the next.

IV.Bezier Curves

Instead of endpoints and tangents, four control points are given:

• points $P_1$ and $P_4$ are on the curve

• points $P_2$ and $P_3$ are used to control the shape

• $p_1=P_1, p_2=P_4$

• $p_1'=3(P_2-P_1),p_2'=3(P_4-P_3)$

$$p(u)=\begin{bmatrix}u^3&u^2&u&1\\ \end{bmatrix}\begin{bmatrix}-1&3&-3&1\\ 3&-6&3&0\\ -3&3&0&0\\ 1&0&0&0\\ \end{bmatrix}\begin{bmatrix}P_1\\P_2\\P_3\\P_4\\\end{bmatrix}$$

Another representation: Blend the control point position using Bernstein polynomials

$p(u)=\sum\limits_{k=0}^n B_{k,n}(u)P_k$

where $B_{k,n}(u)$ are Bernstein polynomials

$B_{k,n}(u)=C(n,k)u^k(1-u)^{n-k}$

How to control the continuity between adjacent Bezier segment? by using ending tangent vector of one segment as the beginning tangent vector of the next.

De Casteljau Construction

Variant of the Hermite spline: basis matrix derived from the Hermite basis (or from scratch)

Givens more uniform control knobs (series of points) than Hermite.

V. Catmull-Rom Splines

With Hermite splines, the designer must arrange for consecutive tangents to be collinear, to get $C^1$ continuity. Similar for Bezier. This gets tedious.

Catmull-Rom: an interpolating cubic spline with built-in $C^1$ continuity.

Compared to Hermite/Bezier: fewer control points required, but less freedom.

Given n control points in 3-D: $p_1,p_2,...,p_n$,

• Tangent at $p_i$ given by $s(p_{i+1}-p_{i-1})$ for $i=2,...,n-1$, for some $s$

• Curve between $p_i$ and $p_{i+1}$ is determined by $p_{i-1},p_i,p_{i+1},p_{i+2}$

• What about endpoint tangents? (several good answers: extrapolate, or use extra control points $p_0$,$p_{n+1}$)

• Now we have positions and tangents at each knot - a Hermite specification

Drawback:

An interval tangent is not dependent on the position of the internal point relative to its neighbors.

VI. Speed Control

• The speed of tracing a curve needs to be under the direct control of the animator.

• Varying $u$ at a constant rate will not necessarily generate $P(u)$ at a constant speed.

Generally, equally spaced samples in parameter space are not equally spaced along the curve

$$u_2-u_1\neq s(u_2)-s(u_1)$$

$$s(u)=\int \sqrt{P_x(u)^2+P_y(u)^2+P_z(u)^2}\,du$$

Arc Length Reparameterization

• To ensure a constant speed for the interpolated value, the curve has to parameterized by arc length (for most applications)

• Computing arc length

• Analytic methods (many curves do not have, e.g., B-splines)

• Numeric methods:

• Table and differencing

• Gaussian quadrature

• Space curve vs. time-distance function: Relates time to the distance traveled along the curve, i.e., relates time to the arc length along the curve.

Given an arc-length parameterized space curve, how to control the speed at which the curve is traced ? By a speed-control function that relates an equally spaced time interval to arc length:

• Input time $t$, output are length: $s=S(t)$

• Linear function: constant speed control

• Most common: ease-in/ease-out: Smooth motion from position, accelerate, reach a max velocity, and then decelerate to a stop position.