How to smootly interpolate between möbius transformations?

Question

If you have two Möbius transformations represented as:

$f(z) = \frac{az + b}{cz + d}$

$g(z) = \frac{pz + q}{rz + s}$

where $a, b, c, d, p, q, r, s, z \in \mathbb{C}$

Is it possible to derive a third function $h(z, t)$, where $t \in \mathbb{R}$ and $0 \leq t \leq 1$, which "smoothly" interpolates between the transformations represented by $f(z)$ and $g(z)$?

Let me try to clarify the meaning of "smoothly". I'm working in a the Poincaré Disc model of Hyperbolic geometry. The functions $f$ & $g$ represent transformations which preserve congruence within the model, i.e. a Poincaré line segment $PQ$ will have the same Poincaré distance as $P'Q'$, where $P' = f(P)$ & $Q' = f(Q)$. I would like the interpolated transform to preserve this property as well.

Clarification:

The answers involving diagonalization of the matrix "almost" work. Let me be clearer about how these mobius transformations are used, so that I can give some more context.

$f$ represents the position and orientation of a tile on the Poincare disc. I use this to transform a tile centered at the origin. $g$ represents a neighboring tile. I'd like to "animate" the $f$ tile moving it smoothly on top of the $g$ tile. While animating, the center of $f$ should travel along the poincare line connecting the two tiles at rest position.

The problem with the diagonalization approach is that the centers of the two tiles will travel about a corner of one of the tiles, sometimes the "long" way around.

Of course it could just be a bug in my code...

P.S. This is for an iphone game I'm developing called Circull

http://www.youtube.com/watch?v=DiWijYb-xus

Answer 1

I'd like to address two issues about how to implement these interpolations and what they mean. The group that you ask about is actually equivalent to the group of real M\"obius transformations. If you were in the upper half plane model, the coefficients would be real numbers. You actually don't need to explicitly use the upper half plane model, but you do need the fact that comes from it that all of the motions are elliptic, hyperbolic, or parabolic. The group is called $\mathrm{PSL}(2,\mathbb{R})$.

It is widely understood that a good way to make smooth motions in a Lie group is with geodesics. This is an important principle in ordinary 3D computer graphics, where the Lie group is instead $\mathrm{SO}(3)$. A standard method to find the geodesics in this comparison case is with quaternions. As it happens, this introduces a wrinkle with doubled angles that also appears in your case.

I assume that you are using $f$ and $g$ as follows: $z$ is a point in the standard bit map of your bird, and then $f(z)$ or $g(z)$ is the mapped position of the bird in your Poincare disk model of the hyperbolic plane. If this is what you are doing, then a correct derivation of the geodesic is $h_t(f(z))$, where $h_t(z)$ is an exponential path from the identity to $g(f^{-1}(z))$. I suppose that the swapped formula that other people have used, $f^{-1} \circ g$, is equivalent.

You can find the exponential path by diagonalizing the matrix of $h_1 = g \circ f^{-1}$. However, there is the important wrinkle that the group of matrices is $\mathrm{SL}(2,\mathbb{R})$, which is twice as big as $\mathrm{PSL}(2,\mathbb{R})$. Let $M$ be the matrix of $h_1$. If $M$ is hyperbolic, then it has real eigenvalues. In this case, you should first switch to $-M$ if the eigenvalues are negative. In the basis in which $M$ is diagonal, you should then specifically use $$M_t = \begin{bmatrix} \exp(ct) & 0 \\\\ 0 & \exp(-ct)\end{bmatrix}.$$ If you use some other choice, you will not follow the geodesic at a constant rate. If $M$ is elliptic, then you should use $$M_t = \begin{bmatrix} \exp(i\theta t) & 0 \\\\ 0 & \exp(-i\theta t)\end{bmatrix},$$ again in a (complex) basis in which $M$ is diagonal. But here, how do you choose between $M$ and $-M$? The total geometric rotation is $2\theta$, not $\theta$. You should negate $M$ if after you diagonalized, $\theta$ is more than $\pi/2$; if you don't do that you might rotate by more than 180 degrees. In the parabolic case (which you might not see because it requires a numerical coincidence), $$M_t = \begin{bmatrix} 1 & t \\\\ 0 & 1\end{bmatrix}.$$

Finally, in computer graphics you might want a smooth trajectory accelerate from 0 at the beginning and decelerate to 0 at the end. With the confidence that $t$ in the above formulas follows the geodesic at a uniform rate, you can do something like $t = \sin(s)^2$ and use $s$ as the time parameter instead.

Answer 2

An explicit interpolation is pretty easy to find. (I'll use the upper half plane model.)

$f$ is given by $\left( \begin{array}{cc} a & b \\\ c & d \end{array} \right)$.

$f$ is elliptic, parabolic, or hyperbolic if the trace has absolute value less than 2, 2, or greater than 2.

In each case you can easily find, using linear algebra, a $w$ conjugating $f$ to the usual rotation matrix, a matrix like $\left( \begin{array}{cc} t & 0 \\\ 0 & t^{-1} \end{array} \right)$, or $\left( \begin{array}{cc} 1 & t \\\ 0 & 1 \end{array} \right)$, respectively.

This easily gives you a path to the identity. (In the elliptic case, you just take the angle to zero.)

Answer 3

The most elegant way to interpolate would probably be $$f \exp(t \log(f^{-1} g)).$$

where $\exp$ and $\log$ are given by their power series expressions. That can probably be simplified a lot since we are just dealing with $2 \times 2$ matrices; does anyone want to give it a try?

Answer 4

Yes, it's easy to interpolate. Let $r(z) = f^{-1}g(z) = \frac{r\_1z + r\_2}{r\_3z + r\_4}$, where $r\_1r\_4 - r\_2r\_3 = 1$. Diagonalize the matrix (if possible): $$R = \begin{bmatrix}r\_1 & r\_2 \\\\ r\_3 & r\_4\end{bmatrix} = V\begin{bmatrix}\lambda & 0 \\\\ 0 & \lambda^{-1}\end{bmatrix}V^{-1} = V\begin{bmatrix}e^{c} & 0 \\\\ 0 & e^{-c}\end{bmatrix}V^{-1}.$$ Let $$S(t) = V\begin{bmatrix}e^{ct} & 0 \\\\ 0 & e^{-ct}\end{bmatrix}V^{-1} = \begin{bmatrix}s\_1(t) & s\_2(t) \\\\ s\_3(t) & s\_4(t)\end{bmatrix}$$ for $0 \leq t \leq 1$ (so $S(0) = I$ and $S(1) = R$), and let $$s(z,t) = \frac{s\_1(t)z + s\_2(t)}{s\_3(t)z + s\_4(t)}$$ (so $s(z,0) = z$ and $s(z,1) = r(z) = f^{-1}g(z)$) and finally define $h(z,t) = f(s(z,t))$, so $h(z,0) = f(z)$ and $h(z,1) = f(f^{-1}g(z)) = g(z)$. It seems like a lot of steps, but conceptually, it's very simple. By postcomposing by the inverse of one of your transformations, you effectively reduce the problem to the case where one transformation is the identity. Then it's clear how to interpolate: embed the other transformation in a one-parameter subgroup of the isometry group of the hyperbolic plane, which diagonalizing makes easy. (Exercise: show that $s(s(z,t\_2),t\_1) = s(z,t\_1+t\_2)$, so $t\mapsto (z\mapsto s(z,t))$ is indeed an embedding of $\mathbb{R}$ into the group of hyperbolic isometries (i. e., a one-parameter subgroup).)

If the matrix $R$ is not diagonalizable, then you can repeat the above construction using the Jordan canonical form instead:

$$R = V\begin{bmatrix}1 & 1 \\\\ 0 & 1\end{bmatrix}V^{-1},$$ and use $$S(t) = V\begin{bmatrix}1 & t \\\\ 0 & 1\end{bmatrix}V^{-1}.$$

Answer 5

That you can interpolate follows from the fact that those maps are elements of $\mathrm{PGL}(\mathbb C,2)$ and this group is connected.

Answer 6

By now you may have more ideas than you need, but heck, here's another non-matrix viewpoint.

In the disk model, you can identify your transformations with lists of three distinct points $(a,b,c)$ on the unit circle, in counterclockwise order. The explicit correspondence is this: For a tranformation $f$, these correspond to $(f(1), f(i), f(-1))$. On the other hand, given three points $(a,b,c)$, you can use the fact that cross ratios are preserved to easily get the formula for $f$ by solving $[z,1,i,-1] = [f(z),a,b,c]$ where $[z_1, z_2, z_3, z_4]$ is the cross-ratio. (There's nothing special about $1,i,-1$ and other choices may make the algebra easier.)

Your problem then reduces to interpolating in the space of counterclockwise lists of 3 distinct points on the circle. This is much simpler to think about, and also suggests ways of optimizing to find interpolation arcs that are relatively "short". (I think a "short" path between lists of 3 points will correspond to a visually simple path between transformations, but I haven't verified this.)

p.s. Very appealing video! good luck with your game!