SAM: Steady Affine Motion

Consider two instances, F0 and F0, of some shape or image F. Each instance is obtained by transforming F by an orientation-preserving affinity (i.e., an invertible combination of arbitrary translations, rotations, scalings, and shears).
Let F0 = B0F and F1 = B1F. Because B1 is invertible, we can compute an affinity A=B1B0-1 to have F1 = AF0. A morph between F0 and F1 associates an instance Ft with each value of time t between 0 and 1.

The morph is an affine motion when a one-parameter set of affinities At exist such that Ft=AtF.

The morph is a Steady Affine Motion (abbreviated SAM), when At = At. Steady affine motions were introduced by Jarek Rossignac and Alvar Vinacua in the paper "Steady Affine Motions" (under review), where they propose a closed form solution for computing At in two and three dimensions, present several beautiful properties of SAMs, and show that a SAM is unique and exist for all orientation-preserving affinities that do not combine excessive shear and rotation.

We present here videos comparing SAM to other affine motions.

In two dimensions, A may be easily computed from three pairs (red, yellow, cyan) of matching points. In each such pair (P0,P1), P1 is the image AP0 of P1 by the affinity A. Hence, given such three pairs of matching points,each comprising a starting point on F0 and an ending point on F1, A is easily computed by solving a system of three linear equalities (provided of course that the three starting points are not collinear and that the three ending points aren't either). To emphasize this point-based design paradigm for affine motions, we show the motions as animations of a triangle that morphs from the triangle spanning the three starting points to the triangle spanning the three ending points, even though an affine motion may be applied to any shape.

Each animation compares two affine motions: SAM is shown at the bottom. On the top, we show a non-steady alternative from the following set:
- Linear: Each point moves with constant velocity.
- rARAP: The combination of the "As-Rigid-As-Possible" linear deformation (which only deforms the shape, without moving it) with a linear motion of the center of mass of the evolving triangle.
- ASAP (As-Similar-As-Posible): An improved version of the rARAP, by factoring out a best-fit spiral morph and compositing it with the ARAP of the residue, which is the identity when A is a similitude.
- TSB (Triple Spiral Blend): A morph where the trajectory of each point is computed as the weighted average of logarithmic spiral, each defined by an two instances of the same edge of the triangle.

Note that the trajectories of the vertices are less convoluted and more natural in SAM than in the other approaches.

Because of its many beautiful and important mathematical properties, SAM is prime candidate for interpolating affine motions in numerous applications, where the motions must be analyzed precisely. However, in many artistic applications, the designers avoid linear motions and seek instead more natural motions that follow pleasing arched trajectories. We find that SAMs produce such motions, but realize that this is a subjective judgment. Because it is hard to compare the beauty of two morphs by viewing how they move a triangle, we include in most videos a second animation that moves a rectangular image. Note that the SAM morph produces steady, arched motions and avoids the surprising changes of size or accelerations produced by the other solutions.
The first important property of SAM is that, given two shapes F0 and F1 related by an affinity A such that Ft=AtF, a SAM if it exists that morphs F0 to F1 is unique.

Another beautiful property of SAMs is that the velocity of any point remains constant throughout the animation, both for a static point in the global coordinate system and for a moving point, when the velocity is expressed in the evolving frame. Specifically, the velocity of a moving point remains constant when expressed in the barycentric coordinates of the moving triangle. We visualize this property by showing short velocity vectors for the three vertices of the triangle. Notice how these velocities appear to remain attached to the triangle for SAMs and how they usually change over time for the other motions. For example, we compare below SAM to rARAP. Notice the twisted vertex trajectories of rARAP.

Below we show the velocity field of a 2D SAM that morphs between the green and the red stick figures. The large magenta dot is the fixed point. Notice the linear variations of the velocity vectors along lines that emanate from it.
velocity field

The original ARAP solutions does not produce any overall motion and only interpolates the linear part of the affinity. To better compare it here with SAM, we combine it with a linear motion of the center of mass of the triangle. (We do so, because we do not know how to compute a better motion.) To show that this motion is not the main reason for the difference between SAM and rARAP, we show below an animation where both the ARAP and SAM are snapped so that the enter of mass of the evolving triangle moves with constant velocity. Notice that the two deformations are different.
Another important property of SAM is that the area of the triangle always changes monotonically for SAM, which implies that if the initial and final shapes have the same area, then the area will be preserved throughout the animation. The other techniques do not offer this guarantee. To illustrate this, we show below the intermediate frames produced by rARAP (top) and by SAM (bottom) for the same configuration. the triangles are filled with color that depends on their area. The color ramp (dark is small and light is large) is normalized independently for each morph (so that the smallest area triangle is always dark and the larges is always light). Notice that although in this example the area remains almost constant, SAM shows a monotonic evolution of the color, and hence of the area, while rARAP shows a non-monotonic variation of color from dark to light and to dark again, which indicates a temporary inflation of the area, which is quite visible in this example.
area

We show this color coding at the beginning of various animations. In the video below, we illustrate this advantage of SAM by showing an animation where the area of the triangle and of the rectangular image remains constant throughout a SAM, while it grows significantly during an rARAP. Note that this temporary inflation appears as a distracting 3D effect in the animation of the rectangular image.


Now, consider the region swept by a moving shape. It is bounded by portions of the boundary of the initial and final shapes and also by curves traced by silhouette vertices (with one incident edge facing the motion and the other one facing back), which are shown as cyan and orange curves, or by grazing points along edges (where the velocity is tangent to the edge). Note that these silhouette vertices and grazing points are constant throughout a SAM, while they usually change over time for other motions (as illustrated below on the rARAP). We first show this property on a static image considering only one edge as it moves along a motion. Notice that for the rARAP motion (top) the grazing point changes over time. We trace in dark green the path of a point that is grazing for an instant towards the middle of the animation. Notice that at the start and end of the animation it is not grazing. Hence, to produce the envelop (concave curve bounding the swept region from below), we must compute a different grazing point at each frame. In contrast, when a SAM is used, the grazing point may be computed for the initial frame. It remains fixed throughout the animation. Its green path traces the desired envelop exactly.
grazing

The animation of a triangle, shown below, illustrates the fact that a vertex of a triangle may by silhouette only for part of an rARAP motion, while its status (silhouette or not) is fixed during a SAM.

In some cases, SAM defaults to simpler affine motions, as shown in the figure below. Given only one pair of starting and ending points, SAM produces a translation with constant velocity (top row). Given a starting point and direction and an ending point and a different direction, SAM produces a rotation of constant angular velocity around a fixed point (next row). Given two pairs of points, or equivalently a starting edge and an ending edge with possibly different length and orientation, SAM produces a logarithmic spiral motion (next row). Note that the spacing between consecutive key frames (or equivalently the instantaneous velocity) grow as the size of the edge grows. Finally, when three pairs of points are given, the more general form of SAM is used (bottom row). If the initial and final triangle are similar, SAM defaults back to the logarithmic spiral. If the two triangles are congruent, SAM defaults to a pure rotation, or a translation if they happen to be aligned,
special cases
The animation below shows that as the starting and ending triangles become similar, the motions produced by ASAP and SAM converge to pleasant arched motions, where each point follows a logarithmic spiral.

The definition, computation, and properties of SAMs extend naturally to three dimensions. The designer may create a 3D animation using a SAM by selecting 4 points (shown as the vertices of a wireframe tetrahedron) on or around a desired shape, and then create and modify a copy of this tetrahedron by translating, scaling, rotating of the new tetrahedron or by selecting and moving any one if its vertices with a simple mouse click-and-drag. The resulting SAM may be shown in stroboscopic mode as a series of key frames (which evolve in realtime as the final tetrahedron is manipulated) or as an animation. Below, we shown the stroboscopic version, where the SAM is applied to two deformed instances of a cube.

sam3d

A 3D SAM may be easily edited by the designer. Below, we show a sequence of such edits, where the designer uses the mouse to grab and move one of the vertices of the right or the left tetrahedron. First we show the starting (green) and ending (red) instances of a phantom cube with their control tetrahedra (the vertices are color-coded to clarify the matching).

sam3D1

Then, we show a stroboscopic depiction of the animation using 7 intermediate frames (yellow).

sam3d2

We can adjust the number of intermediate frames.

sam3d3 sam3d4

Below, we edit the SAM by clicking and dragging the right-most (magenta) vertex of the ending (red) frame. Notice that small motions typically result in small changes in the SAM.

sam3d5

We can also click and drag a vertex (magenta) of the starting (green) instance.

sam3d6

Until we obtain the desired starting and ending shapes.

sam3d8

Below, we show how the user may interact with a SAM in 3D, by translating, rotating, or scaling the two control tetrahedra or by picking and moving their vertices with the mouse in a plane parallel to the screen or in depth (when a key is pressed).

In the animation below, we keep the left control tetrahedron fixed, and let the designer specify an initial and a final pose for the right control tetrahedron. We compute a SAM between these initial and final poses and use it to animate back and forth the ending pose. We show the resulting SAM as a series of frames. Note that the designer may edit the initial and final poses or their control vertices during the animation, which reflects these changes in realtime.

the SAM interpolation may be used to produce two-dimensional (and even higher-dimensional) tensor-products patterns of 2D or 3D shapes, which may be used in design or for averaging motions. To do so, we use SAM to produce a series of intermediate frames that interpolate between to top left (A) and the top right (B) control tetrahedra. We use SAM to generate the same number of intermediate frames in a series that interpolates between to bottom left (C) and the bottom right (D) control tetrahedra. Then, we consider pairs (top and bottom) of corresponding tetrahedra, compute a SAM between them and show it using a series of intermediate frames (columns of shapes). We call this a bi-SAM pattern. Even though all columns and the first and last rows are SAMs, the other rows are not steady. We can ensure that both the rows and the columns of the bi-SAM are steady by forcing one of the corner control tetrahedra (say D) to match a simple expression the other three (say D is the result of applying to C the affinity that maps A to B).

bisam

Below is a short animation sweeping through the columns of a bi-SAM. The color indicates the different situations, each requiring a different solution for computing the SAM.

Here is another animation, showing how the designer may interact with the bi-SAM in realtime.

Our SAM construction may also be used to compute an unsteady motion controlled by more than two poses. For example, the ScrewBender scheme, which was developed by Powell and Rossignac
[ScrewBender: Smoothing Piecewise Helical Motions Alex Powell and Jarek Rossignac IEEE Computer Graphics and Applications, 28(1):56-63 Jan/Feb 2008. GVU Tech Report GIT-GVU-05-05.]
to produce smooth rigid motions that approximate or interpolate a series of arbitrary poses starts with a piecewise helical motion that interpolates pairs of consecutive congruent poses and subdivides that motion by modifying and inserting poses. All new poses are formulated in terms of screw motions that interpolate two original or previously computed poses. The same subdivision process may be used on a piecewise SAM interpolation of a series of affine (non-congruent) poses and to subdivide it using steady motions rather than screw motions. Although the subdivision process will usually converge to a smooth and pleasing motion, the limit motion will in general not be steady. Nevertheless, the use of a SAM as the primitive interpolation for such constructions extends the domain beyond screw motions and may lead to steadier and hence more pleasing results than those produced when using unsteady primitives. The subjective validation of such a claim falls outside the scope of this paper. Below we show a simple example of a cubic Bezier-SAM motion defined by 4 poses. The tetrahedron defining the current frame at time t is produced by the call bezierSAM(A,B,C,D,t), which is implemented as: 

Tet bezierSAM(Tet A, Tet B, Tet C, Tet D, float t) { return SAM( SAM(SAM(A,t,B),t,SAM(B,t,C)) ,t, SAM(SAM(B,t,C),t,SAM(C,t,D)) ); },

where SAM(A,t,B) returns the tetrahedron produced for time t by a SAM that interpolates from tetrahedron A to tetrahedron B. Although the resulting motion is not steady, it is smooth, pleasing, and easily controllable.

Below we show a Bezier-SAM applied to the model of a horse.

A series of poses may be interpolated by a piecewise SAM motion. However, the motion may exhibit visible discontinuities (perceived as sudden accelerations) at the poses. An smooth non-steady motion may be created through subdivision, as discussed above. Unfortunately, it does not interpolate the intermediate poses. However, one may compute a series of new retrofit poses, the subdivision of which generates a smooth (unsteady) motion that nearly interpolates the original poses. Below we show an example using a quadratic Bezier SAM. The first part of the animation shows the piecewise SAM (composed of two SAMs) defined by three control poses A, B, and C. Notice the sharp change of velocity when the moving cube passes at B. The second part of the animation shows the result of the retrofit process, where we have computed T=SAM(SAM(A,1/2,C),2,B) and use a Bezier subdivision of the polySAM on control frames A, T, and C. Not that this simple retrofit construction does not guarantee that the resulting motion interpolates B.

When computing the SAM, we need to distinguish a variety of cases (shown in different colors here). Many deal with singular configurations, such as a pure translation, a pure shearing (orange), or a particular combination of a rotation with a shearing (cyan), which are detected by considering the eigenvalues of the linear part of the matrix representation of A.

cases1

When we are not in a singular position, we still must distinguish between two general cases: when the linear part of A is diagonalizable (blue) and when it is not (green).

For some configurations of starting and ending poses related by an affinity that combines a shear with a large rotation there may be not steady solution. The existence of SAM is not affected by scaling or translation. We observe that SAM exists when the relative affinity between the two poses does not correspond to a combination of an excessive rotation and shear. To chart the space of affinities for which a SAM exists, we have considered the family of cases where the ending pose is produced from the first one by a shear of magnitude d (adding or subtracting d from the coefficients of the identity matrix), by a rotation of angle b around an arbitrary direction, by an arbitrary uniform scaling, and by an arbitrary rotation. We have observed that a SAM exists for all of the millions of random tests where b is less than 45 degrees and d is less than 0.5. This was also true for millions of random tests where b is less than 120 degrees and d is less than 0.29.

To visualize the good and bad space in an interactive manner (as shown in the video below), we let the operator translate, rotate, scale, and deform the two control frames as before. For each configuration, we test a two-dimensional array of alternative locations for the magenta vertex of the tetrahedron defining the second control frame. When a particular alternative location defines a configuration where SAM exists, it is shown as a green sphere. Otherwise it is shown as a red sphere. Each one of these alternative locations is used to test the existence of a SAM for a slightly different shear. The operator explores the rotations interactively and drags the other vertices to increase the shear explored in this array of alternative locations. Remember that global scaling and translation need not be explored, since they do not affect the result. The video shows that red spheres only appear for a rotation approaching 180 degrees and for a strong shear. Towards the end of the video, we show a green cube around the initial control tetrahedron and its deformed image (red shape) around the final control tetrahedron. Notice that, in order to produce configurations where no SAM exists, we need a strong shear, which elongates and flattens the red shapes to an extreme. As a rule of thumb, we conclude that, when the rotation is lees than 90 degrees and for most reasonable deformations, a SAM always exists.

In the bad cases where no SAM exists, one may use an unsteady interpolating approach. When the designer is available a new frame may be inserted to guide the solution. The composite image below shows such a scenario. The initial configuration (top/left) has a SAM. Rotating and shearing the right ending pose changes the SAM (top/right). Further rotation and shearing produces a bad configuration for which no SAM exists. The designer inserts an intermediate pose (middle/left). A polySAM solution is produced that uses one SAM to interpolate between the starting frame and the inserted one and another SAM to interpolate between the inserted pose and the final one. Notice the discontinuity in velocities at the inserted pose (middle/right). Treating these three poses as the control poses of a quadratic Bezier curve in the space of affinities produces a smooth (although unsteady) motion between the starting and ending poses (bottom/left). Unfortunately, in general, this motion does not interpolate the intermediate pose, which may frustrate the designer. We use SAMs to create two new control poses automatically that we use to produce a pleasing unsteady motion that is the composition of two such Bezier curves and that interpolates all three poses (bottom/right).

The video below shows an animation of this scenario. First the designer edits the right-most control tetrahedron until the SAM sequence disappears, indicating that no SAM exists. Then an intermediate frame is inserted by the designer and the resulting polySAM is shown as a sequence of poses updated in realtime during interactive editing (orange blocks) and then as a forth-and-back animation (cyan blocks) to better appreciate its smoothness and dynamics. Notice the sharp change of velocities at the intermediate pose. Then the same thing is shown for the quadratic Bezier animation. Notice that it does not interpolate the intermediate pose. Then we show the same for the retrofitted solution that creates a pair of Bezier animations. Notice that it interpolates the intermediate control pose and produce a smooth pleasing motion. Finally, to shown that this solution is stable, we move the intermediate control pose and show in realtime how these edits alter the solution.

The figure below shows a PolySam interpolating four control poses (red blocks). The resulting motion is piecewise steady (concatenates three SAM spans), which facilitates processing in some applications, but has velocity discontinuities at the control poses. Successive applications of the four-point subdivision process in the space of affinities increases the number of SAM spans, but decreases the velocity discontinuities at span junctions. Our experiments suggest that 3 or 4 subdivision steps suffice to produce polySAMs that appear smooth.

Our implementation of the four-point subdivision is only a few lines of code (see below) that use as input n entries in the array P of tetrahedra. For simplicity, we compute the subdivided sequence of 2n-1 tetrahedra in a separate array Q and then copy them back into P.

void subdivide() {
for(int i=1; i<n-1; i++) { L[i]=left(P[i-1],P[i],P[i+1]); R[i]=left(P[i+1],P[i],P[i-1]); };
for(int i=0; i<n; i++) Q[2*i]=P[i];
for(int i=1; i<n-2; i++) Q[2*i+1]=SAM(R[i],0.5,L[i+1]);
Q[1]=L[1]; Q[2*n-3]=R[n-2];
n=2*n-1;
for(int i=0; i<n; i++) P[i]=Q[i];
}

The implementation exploits the fact that each new control point in the four-point scheme is the average of two parabolic predictions, which we pre-compute in the arrays of tetrahedra L and R. For each control point, except the last, we compute such a left prediction. For each control point, except the first, we compute the right prediction (using a call to "left", but passing the points in reverse order). Then, for each edge, we take the average of the right prediction of the left vertex of the edge and of the left prediction of the right vertex (when they exist). For the parabolic prediction (function "left") returns a point L at one quarter along a parabolic (quadratic bezier) arc through 3 points (A,B,C). We chose to construct L be displacing (A+B)/2 by AB/8 and then by CB/8. Note that reversing the order of these two displacements may slightly alter the result and that other constructions are possible. The one we propose only requires computing SAMs between pairs of consecutive control poses, which is important, since a SAM between non-consecutive control poses is more likely not to exist.

Tet left(Tet A, Tet B, Tet C) {return SAM(SAM(SAM(A,0.5,B),A,.125,B),C,.125,B); }

"left" uses two different SAM functions (below) that return tetrahedra. The first one calls S() to compute affinity A between tetrahedra T0 and T1, such that T1=A T0, and returns the image At T of some third tetrahedron T. The second one returns At T0.

Tet SAM(Tet T, Tet T0, float t, Tet T1) {return S(T0,t,T1).map(T);}
Tet SAM(Tet T0, float t, Tet T1) {return S(T0,t,T1).map(T0);}

Below is the corresponding animation.

Source code (Zipped Processing sketch) for a 2D interactive demo of SAM and bi-SAM: sam.zip