326 Research Andrew McCaleb Reach is with Virginia Tech. E-mail:
<EMAIL_ADDRESS>Chris North is with Virginia Tech. E-mail:
<EMAIL_ADDRESS>Reach et al.: Dynamical Systems in Hyperbolic Space

# Smooth, Efficient, and Interruptible Zooming and Panning

Andrew McCaleb Reach and Chris North

###### Abstract

This paper introduces a novel technique for smooth and efficient zooming and
panning based on dynamical systems in hyperbolic space. Unlike the technique
of van Wijk and Nuij, the animations produced by our technique are smooth at
the endpoints and when interrupted by a change of target. To analyze the
results of our technique, we introduce world/screen diagrams, a novel
technique for visualizing zooming and panning animations.

##  1 Introduction

Zooming and panning is an interaction technique that solves the problem of
fitting too-much data on a too-small screen. _Zooming_ refers to the
manipulation of scale—zooming in shows less in more detail, and zooming out
shows more in less detail. _Panning_ refers to the manipulation of the viewing
window—panning left or right slides more information into view from one side
of the screen, while information on the other side slides out of view.

In many user interfaces, the user zooms and pans manually by pinching a touch
screen, rolling a scroll wheel, or by dragging the mouse. This paper does not
focus on these problems—instead, this paper introduces techniques for
_automatically_ zooming and panning in response to user interactions.

For example, consider a home search application that shows homes matching the
user’s query in two ways: in a list and on a map. A user who hovers the mouse
over a home in the list will likely want to also see the home’s location on
the map, and if this home is currently off-screen, this will require zooming
and panning. If the user interface performs this navigation abruptly, jumping
instantaneously from the old view to the new view, then the user loses all
context about the spatial relationship between the current house and the
previous house. By smoothly zooming and panning from one view to the next, the
user gains a clearer understanding of the locations of the houses.

It can also be useful to combine manual zooming and automatic zooming. For
example, imagine a stock price time series visualization in which the user
manually zooms and pans on the time axis. As the user adjusts the time axis
view, previously off-screen data will become visible, and some of this data
may be outside the current range of the price axis. To prevent the user from
having to manually readjust the price axis after zooming and panning on the
time axis, it would be helpful for the interface to automatically zoom and pan
on the price axis in order to continually accommodate the current range of
prices.

The current state-of-the art technique for automatic zooming and panning is
the smooth and efficient technique introduced by van Wijk and Nuij [18], which
seeks to find a navigation animation that satisfies two properties:

  1. 1.

The animation is _smooth_ in the second order, i.e. both position and velocity
are continuous.

  2. 2.

The animation is _efficient_ , i.e. it minimizes perceptual cost. For example,
panning directly from a zoomed-in view of Seattle to a zoomed-in view of
London is perceptually costly because the animation will require a long
duration in order to avoid excessive motion blurring. By contrast, an
animation that first zooms out from Seattle, then pans, then zooms into London
is perceptually cheaper, since this animation can be made significantly
shorter without excessive motion blurring.

The perceptual cost is quantified in terms of the _optical flow_ , and a cost-
minimizing zooming and panning animation is found via methods from
differential geometry.

The animations produced by the technique of van Wijk and Nuij are smooth and
efficient while in motion, but they technically violate the smoothness
property at the beginning and end of the animation, where the velocity
abruptly jumps from and to zero respectively. Moreover, if the animation is
interrupted, then each interruption will, in general, introduce a velocity
discontinuity. Prior research has shown preliminary evidence that animations
without velocity discontinuities allow users to more easily track objects than
animations with velocity discontinuities [7]. For the home-finding example, an
interruption occurs every time the user hovers over a different home, and for
the stock price example, interruptions occur continuously while the user zooms
or pans. This renders the smooth and efficient zooming and panning technique
unsuitable for situations in which animations are frequently interrupted by a
change of target.

We solve the problem of smooth, efficient, and interruptible zooming and
panning by applying ideas from the fields of signal processing and Riemannian
geometry. Specifically, this paper makes the following contributions:

  * •

We introduce the _hyperbolic model of zooming and panning_ , in which a zoom
and pan position is represented by a point in the Poincaré upper half-plane
model of hyperbolic space. The hyperbolic model is a simplified version of
$u,w$-space.

  * •

Using this model, we show that smooth, efficient, and interruptible zooming
and panning can be achieved by generalizing signal processing techniques to
hyperbolic space.

  * •

To visualize the results of our technique, we introduce _world/screen
diagrams_ , a novel method for visualizing zooming and panning trajectories
that emphasizes the perceptual aspects of zooming and panning.

##  2 Background

Zooming and panning is conceptually simple, but the details can be difficult
to get right, and so several models have been proposed to aid in the
understanding of zooming and panning. The space-scale diagrams of Furnas and
Bederson [8] provide one way to represent zooming and panning. In this model,
we imagine _world space_ (i.e. the large information space that we are
navigating) is projected from a stationary projector located at the origin. To
zoom and pan, we maneuver a blank screen through the space-scale diagram. By
bringing the blank screen closer to the projector, the projected image appears
smaller on the screen, and so this motion corresponds to zooming out; and by
moving the blank screen farther away from the projector, the projected image
appears larger on the screen, and so this motion corresponds to zooming in. By
moving the blank screen from side to side, different portions of the projected
image will fall onto the screen, and so this motion corresponds to panning. A
zooming and panning animation can be plotted as a screen-trajectory in a
space-scale diagram, allowing zooming and panning animations to be visualized
and compared.

Another model of zooming and panning is the $u,w$-space model of van Wijk and
Nuij [18, 19]. In the $u,w$-space model, we imagine that world space is a
stationary plane that is viewed through a camera. To zoom out, we move the
camera away from the world plane, and to zoom in, we move the camera towards
the world plane. To pan, we move the camera from side to side. In $u,w$-space,
the location of the camera is represented by $u$, which gives the pan
position, and $w$, which gives the zoom factor. Specifically, $u$ is the
world-space point that is mapped to the center of screen space, and $w$ is the
world-space length spanned by the width of the screen. The camera has a angle
of view of approximately $53^{\circ}$. Additionally, in $u,w$-space, there is
a _metric_ , which approximates the perceptual cost of a zooming and panning
animation. Using this metric, cost-minimizing animation paths were found by
van Wijk and Nuij. This metric has a parameter $\rho$ that controls the trade-
off between zooming and panning, and when $\rho=1$, this model is equivalent
to hyperbolic geometry [19]. A diagram depicting $u,w$ space is shown in
Figure 1.

Figure 1: In $u,w$ space, a view is encoded by a point in two-dimensional
space that represents the location of a camera. The $u$ coordinate specifies
the location in world space that is mapped to the center of screen space. The
$w$ coordinate specifies the width of the world-space span that is shown
onscreen. A zooming and panning animation can be depicted as a path through
$u,w$ space, as shown.

Like $u,w$-space, the model we use in this paper is based on a camera analogy
and a perceptual cost metric. Unlike $u,w$-space, we do not assume that the
camera has a specific angle of view, and in exchange, our perceptual cost
metric is simpler without loss of generality. Specifically, our metric is
always the metric for hyperbolic geometry, and the trade-off between zooming
and panning is instead expressed by varying the camera’s angle of view rather
than by varying the metric.

This paper considers methods for automatically zooming and panning between
views. There is much prior work on manual zooming and panning [9, 2, 5] where
the user controls the zoom and pan positions directly. Prior work on automatic
zooming and panning includes the speed-dependent automatic zooming technique
of Igarashi and Hinckley [10], which automatically controls the zoom position
in response to user-performed scrolling. Specifically, in the technique of
Igarashi and Hinckley, the user controls the rate of scrolling, and the system
automatically adjusts the zoom factor to accommodate the current scroll rate,
i.e. the system zooms out as the scroll rate increases and zooms back in as
the scroll rate decreases. A technique based on the $u,w$-space model has also
been applied to this problem [19]. While ideas presented in this paper may
have applications to the problem of speed-dependent automatic zooming, this
paper will only focus on the problem of automatic zooming and panning between
specified views.

##  3 Zooming and panning representations

This section introduces a representation of zooming and panning in which each
specific zooming and panning view is represented by the location of a camera.
This model is the same as the $u,w$-space model of van Wijk and Nuij except
for one aspect: we do not make any assumptions about the field of view of the
camera. By not assuming a particular field of view, we simplify calculations
in the following sections compared with $u,w$-space. We will consider both the
case of zooming and panning over a two-dimensional space and the case of
zooming and panning over a one-dimensional space.

For zooming and panning in a one-dimensional space, each zoom and pan position
can be described as a point $\mathbf{x}\in\mathbb{H}^{2}$ that represents the
location of a camera, where the set $\mathbb{H}^{2}$ is defined by

$\mathbb{H}^{2}=\left\\{\begin{bmatrix}u\\\
v\end{bmatrix}:u\in\mathbb{R}\hskip 1.0pt,\,v\in\mathbb{R}_{>0}\right\\}$

We can decompose a camera position $\mathbf{x}\in\mathbb{H}^{2}$ into two
parts as follows:

$\mathbf{x}=\begin{bmatrix}u\\\ v\end{bmatrix}$

We will refer to the $u$ component as the _footprint_ of the camera, and to
the $v$ component as the _altitude_ of the camera. The camera points straight
down at the $u$ axis, and whichever portion of the $u$ axis is captured by the
camera is the portion of world-space that is shown onscreen.

For zooming and panning in two dimensions, each zoom and pan position can be
represented as a point $\mathbf{x}\in\mathbb{H}^{3}$ that gives the location
of a camera in three-dimensional space, where the set $\mathbb{H}^{3}$ is
defined by

$\mathbb{H}^{3}=\left\\{\begin{bmatrix}\mathbf{u}\\\
v\end{bmatrix}:\mathbf{u}\in\mathbb{R}^{2},\,v\in\mathbb{R}_{>0}\right\\}$

As before, we will decompose this point into two parts:

$\mathbf{x}=\begin{bmatrix}\mathbf{u}\\\
v\end{bmatrix}=\begin{bmatrix}u_{1}\\\ u_{2}\\\ v\end{bmatrix}$

where $\mathbf{u}$ is the footprint and $v$ is the altitude. This camera
points down at the $v=0$ plane.

To avoid needless repetition, we will describe our solution in a manner that
applies at once to both the one-dimensional and two-dimensional cases. We will
use $\mathbb{H}^{n}$ to denote the set of zooming and panning positions, where
$n=2$ for one-dimensional zooming and panning and $n=3$ for two-dimensional
zooming and panning. The camera location is therefore a point
$\mathbf{x}\in\mathbb{H}^{n}$, and the footprint
$\mathbf{u}\in\mathbb{R}^{n-1}$ is then either a one-dimensional vector or a
two-dimensional vector.

The relationship between a world-space point $\mathbf{p}\in\mathbb{R}^{n}$ and
the corresponding screen-space point $\mathbf{r}\in\mathbb{R}^{n}$ is given by

$\mathbf{p}=v\mathbf{r}+\mathbf{u}$ (1)

This can, of course, be written in inverse form as

$\mathbf{r}=\frac{\mathbf{p}-\mathbf{u}}{v}$

which better reflects the more common operation in visualization of mapping
from world space to screen space111The choice of having a simpler mapping from
screen space to world space than the other way around may seem odd, but it is
the price paid for the camera analogy, and, more importantly, this choice
simplifies later equations..

The specific cropping of screen space defines the field of view of the camera.
For a $90^{\circ}$ camera, screen space is the interval $[-1,1]$ when $n=1$
and the square region $[-1,1]\times[-1,1]$ when $n=2$.

##  4 The perceptual cost metric

In this section, we will now introduce a _metric_ , i.e. a way to quantify
distance. Our metric will define distance in the space of zooming and panning
positions to be an approximation of perceptual cost.

We will quantify the perceptual cost $ds$ incurred by a small change
$d\mathbf{x}$ in camera position by

$ds=\frac{\lVert d\mathbf{x}\rVert}{v}.$ (2)

where $\lVert d\mathbf{x}\rVert$ is the Euclidean norm of $d\mathbf{x}$ and
$v$ is the altitude of the camera position $\mathbf{x}$. In other words,
perceptual cost is proportional to the Euclidean distance that the camera
moves (which includes both changes in footprint and altitude), and inversely
proportional to the camera’s altitude. Notice that unlike Euclidean space, in
which distance depends only on the displacement vector, the metric we have
introduced depends on both the camera’s displacement vector $d\mathbf{x}$ and
on the camera’s altitude $v$.

The set $\mathbb{H}^{n}$ together with Equation 2 is the Poincaré upper half-
space model of hyperbolic space, which has been widely studied in the field of
Riemannian geometry. We will therefore frequently refer to camera positions as
points in hyperbolic space.

This choice of metric can be explained intuitively. Imagine a camera with a
$90^{\circ}$ field of view. For an altitude of one meter, panning by half of
the screen will require a movement of one meter. For an altitude of two
meters, panning half the screen will require a movement of two meters. For an
altitude of three meters, panning half the screen will require a movement of
three meters. Clearly then, the onscreen effect of panning depends on both the
distance that the camera moves and the altitude of the camera. For a given
altitude, moving the camera a greater distance will, of course, result in a
greater onscreen movement: therefore perceptual cost should be proportional to
the distance the camera moves. However, since a proportionally larger distance
is required for the same perceptual cost at higher altitudes, the perceptual
cost of panning should be inversely related to altitude.

Now consider zooming. At an altitude of one meter, the camera must move
upwards (i.e. in the direction of increasing altitude) by one meter to zoom
out by a factor of two. We assume that zooming out by a constant factor will
have the same perceptual cost regardless of where the camera is located. At an
altitude of two meters, the camera must move upwards by two meters to zoom out
by a factor of two. At an altitude of three meters, the camera must move
upwards by three meters to zoom out by a factor of two. Therefore, like
panning, the perceptual cost of zooming depends on both the distance traveled
and the altitude, and like panning, the cost of zooming should be proportional
to the distance zoomed and inversely proportional to altitude222It might seem
as though the relationship between camera distance and the perceptual cost of
zooming is more complicated than this, since we would expect zooming out by a
factor of two to have the same perceptual cost as zooming in by a factor of
two, but at an altitude of two meters a two-meter movement is required to zoom
out by a factor of two, whereas only a one-meter movement is required to zoom
in by a factor of two. However, this discrepancy becomes smaller with shorter
movements of the camera, and since the metric quantifies the effect of an
infinitesimal movement of the camera, this discrepancy disappears..

The perceptual cost of panning is related to the camera’s angle of view—the
distance required to pan one screen for a camera with a narrow angle of view
is much smaller than that required to pan one screen for a camera with a wide
angle of view. The perceptual cost of zooming, however, is not related to the
camera’s angle of view—zooming out by a factor of two requires the same camera
movement regardless of the angle of view. Therefore, by varying the camera’s
angle of view, different trade-offs can be made between zooming and panning. A
narrow angle of view expresses a preference for panning rather than zooming,
and a wide angle of view expresses a preference for zooming rather than
panning.

###  4.1 Comparison with $u,w$-space

In the $u,w$-space model, the camera’s field of view is fixed, and a parameter
$\rho$ that appears in the metric controls the trade-off between zooming and
panning. By contrast, in the hyperbolic model, the metric has no parameter to
control the trade-off between zooming and panning—instead the camera has a
variable field of view. By increasing the field of view, the same trajectory
appears to zoom more and pan less, and by decreasing the field of view, the
trajectory appears to pan more and zoom less. This is because the same
onscreen view will map to different camera locations depending on the angle of
view—a camera with a narrow angle of view will need to be located at a higher
altitude to capture the same image as camera with a wide angle of view. In
Smooth and Efficient Zooming and Panning [18], a user study found that the
user-preferred value of $\rho$ was 1.42, which is roughly $\sqrt{2}$.
Interestingly, for $\rho=\sqrt{2}$ in the $u,w$-space model, the corresponding
angle of view in the hyperbolic model is exactly $90^{\circ}$, as is shown
later in this section.

Our model has the following advantages over $u,w$-space:

  1. 1.

The hyperbolic model of zooming and panning is precisely the same as the
Poincaré upper half-space model of hyperbolic space, which has been well-
studied in Riemannian geometry. Therefore, a large body of work in
differential geometry on the half-space model immediately applies to zooming
and panning.

  2. 2.

In $u,w$-space, the parameter $\rho$ appears in many of the equations that
define the optimal zooming and panning trajectory. These equations are simpler
in the hyperbolic model.

  3. 3.

In the coordinates of $u,w$-space, the optimal path is an elliptical
trajectory, where the eccentricity of the ellipse is determined by the
parameter $\rho$. As we will see, in the coordinates of the hyperbolic model,
the optimal path is always a simpler circular path.

  4. 4.

In $u,w$-space, the $w$ parameter is less intuitive if the screen is not
square, since it gives the length of only one of the screen’s sides, and the
other must be calculated from the screen’s aspect ratio. By contrast, in the
hyperbolic model, we simple use two angles of view instead of one.

The hyperbolic model and $u,w$-space are related by a change of coordinates.
Under this change of coordinates, the models are _equivalent up to scaling_ ,
by which we mean that the optimal paths are the same with respect to this
change of coordinates and the distances between points are related by a
constant factor. We will now describe more precisely what it means for two
models to be equivalent up to scaling. One way to interpret the condition of
equivalence up to scaling is that the two models agree in every way except
that distances are calculated in different units, e.g. one model might give
the distance in inches whereas the other model gives the distance in
centimeters. In practice this difference is unimportant, since even if a
parameter was added to scale the metric by an arbitrary factor, this parameter
would be redundant with other existing parameters that control how the optimal
path is used. For example, in the model of van Wijk and Nuij, there is a
parameter $V$ that controls how quickly the optimal path is traversed. If the
metric is scaled by a factor of two, and so all points are twice as far away
from each other, then an animation that matches the original can be produced
by similarly scaling $V$ by a factor of two, therefore traversing the path at
twice the speed and reaching the destination at the same time as traversing
the original path at the original speed. Therefore, when we say that two
models are equivalent up to scaling, we mean that they are equivalent in all
useful ways.

Specifically, the hyperbolic model is equivalent up to scaling to the
$u,w$-space model using the change of coordinates333In the case of
$\rho=\sqrt{2}$, which was the user-preferred value as found by van Wijk and
Nuij, this formula becomes $w=2v$, which is easily remembered since the
character $w$ visually appears to be the concatenation of two $v$ characters.

$w=\rho^{2}v.$

Hyperbolic distance $s$ is related to $u,w$-space distance $\sigma$ by

$s=\rho^{2}\sigma.$

The angle of view $\theta$ in the hyperbolic model is related to $\rho$ in
$u,w$-space by the equation

$\theta=2\arctan\frac{\rho^{2}}{2}.$

As mentioned earlier, for $\rho=\sqrt{2}$, as was preferred by users in the
study of van Wijk and Nuij [18], the above equation gives $\theta=90^{\circ}$.

In the appendix to Smooth and Efficient Zooming and Panning [18], an embedding
of $u,w$-space in three-dimensional space is shown. In hyperbolic geometry,
the well-known _pseudosphere_ gives such an embedding, and can be written in
terms of the footprint $u$ and altitude $v$ as:

$\displaystyle x$ $\displaystyle=(\cos u)/v$ $\displaystyle y$
$\displaystyle=(\sin u)/v$ $\displaystyle z$
$\displaystyle=\operatorname{acosh}v-\tanh(\operatorname{acosh}v).$

Here $\tanh$ denotes the hyperbolic tangent and $\operatorname{acosh}$ denotes
the inverse hyperbolic cosine. It should be noted that, like the embedding of
van Wijk and Nuij, this is only a _partial_ embedding—in particular, it does
not work for $v<1$, since $\operatorname{acosh}v$ is imaginary for $v<1$.
Moreover, this mapping is ambiguous, since a point $(x,y,z)$ corresponds to
multiple values of $u$.

##  5 Hyperbolic space

In this section we will explore the properties of hyperbolic space and how
they relate to zooming and panning. Fist, we will discuss the geodesics of
hyperbolic space, which correspond to perceptually optimal zooming and panning
paths. Second, we will discuss vectors in hyperbolic space and operations that
relate vectors and geodesics. We will use the properties and operations from
this section later in this paper to develop algorithms for smooth, efficient,
and interruptible zooming and panning.

We begin by exploring the geodesics of hyperbolic space. It is known that
every geodesic in the Poincaré upper half-plane model is either a half-circle
whose endpoints lie at altitude zero or a vertical line [4].

###  5.1 Geodesics and distance

We will define the function

$\operatorname{geo}(\mathbf{x},\mathbf{y},s)$

to be optimal path between $\mathbf{x}\in\mathbb{H}^{n}$ and
$\mathbf{y}\in\mathbb{H}^{n}$, parameterized by arc length $s$ as measured by
the hyperbolic metric Equation 2.

We will also define the function

$\operatorname{dist}(\mathbf{x},\mathbf{y})$

to be the hyperbolic distance between two camera locations; i.e. the
perceptual cost of the optimal path between these two points. This function is
the hyperbolic analog of Euclidean distance. We have the identities

$\displaystyle\operatorname{geo}\left\lparen\mathbf{x},\mathbf{y},0\right\rparen$
$\displaystyle=\mathbf{x}$
$\displaystyle\operatorname{geo}\left\lparen\mathbf{x},\mathbf{y},\operatorname{dist}(\mathbf{x},\mathbf{y})\right\rparen$
$\displaystyle=\mathbf{y}$
$\displaystyle\operatorname{dist}\left\lparen\mathbf{x},\operatorname{geo}\left\lparen\mathbf{x},\mathbf{y},s\right\rparen\right\rparen$
$\displaystyle=s$

The function $\operatorname{geo}$ is depicted in Figure 2.

Figure 2: The function $\operatorname{geo}(\mathbf{x},\mathbf{y},s)$ returns
the point arrived at by traveling from $\mathbf{x}$ along a geodesic to
$\mathbf{y}$ for a hyperbolic distance $s$.

Finally, we will define a third function, $\operatorname{gerp}$, in terms of
$\operatorname{geo}$ and $\operatorname{dist}$ as

$\operatorname{gerp}(\mathbf{x},\mathbf{y},\alpha)=\operatorname{geo}\Big{\lparen}\mathbf{x},\mathbf{y},\alpha\operatorname{dist}(\mathbf{x},\mathbf{y})\Big{\rparen}$
(3)

This function interpolates between $\mathbf{x}$ at $\alpha=0$ and $\mathbf{y}$
at $\alpha=1$ along a perceptually optimal path.

The functions $\operatorname{geo}$ and $\operatorname{dist}$ can be calculated
as

$\displaystyle\operatorname{dist}\left\lparen\left[\begin{smallmatrix}\mathbf{u}_{0}\\\
v_{0}\end{smallmatrix}\right],\left[\begin{smallmatrix}\mathbf{u}_{1}\\\
v_{1}\end{smallmatrix}\right]\right\rparen$ $\displaystyle=S$ (4a)
$\displaystyle\operatorname{geo}\left\lparen\left[\begin{smallmatrix}\mathbf{u}_{0}\\\
v_{0}\end{smallmatrix}\right],\left[\begin{smallmatrix}\mathbf{u}_{1}\\\
v_{1}\end{smallmatrix}\right],s\right\rparen$
$\displaystyle=\left[\begin{smallmatrix}\mathbf{u}(s)\\\
v(s)\end{smallmatrix}\right]$ (4b) where, for
$\mathbf{u}_{0}\neq\mathbf{u}_{1}$, $\displaystyle\mathbf{u}(s)$
$\displaystyle=\mathbf{u}_{0}+v_{0}\frac{\sinh(s)}{\cosh(s+r_{0})}\frac{\mathbf{u}_{1}-\mathbf{u}_{0}}{\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(4c) $\displaystyle v(s)$
$\displaystyle=v_{0}\frac{\cosh(r_{0})}{\cosh(s+r_{0})}$ (4d) $\displaystyle
S$ $\displaystyle=r_{1}-r_{0}$ (4e) $\displaystyle r_{i}$
$\displaystyle=\operatorname{asinh}\frac{v_{1}^{2}-v_{0}^{2}+(-1)^{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert^{2}}{-2v_{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(4f) and, for $\mathbf{u}_{0}=\mathbf{u}_{1}$, $\displaystyle\mathbf{u}(s)$
$\displaystyle=\mathbf{u}_{0}$ (4g) $\displaystyle v(s)$
$\displaystyle=v_{0}e^{sk}$ (4h) $\displaystyle k$
$\displaystyle=\operatorname{sign}(v_{1}-v_{0})$ (4i) $\displaystyle S$
$\displaystyle=|\log(v_{1}/v_{0})|.$ (4j)

In these equations, $\sinh$ and $\cosh$ denote the hyperbolic sine and cosine
functions respectively, and $\operatorname{asinh}$ denotes the inverse
hyperbolic sine. The notation $\operatorname{sign}$ denotes the sign function,
which returns $-1$ when its argument is negative, $0$ when its argument is
zero, and $1$ when its argument is positive. Finally, the notation $\log$ is
used to denote the natural logarithm. These equations were adapted from those
given by van Wijk and Nuij [18], but were reformulated to decrease numerical
error by removing sums and differences that caused catastrophic cancellation.
Figure 7 visualizes the path produced by the function
$\operatorname{geo}(\mathbf{x},\mathbf{y},s)$ between two views $\mathbf{x}$
and $\mathbf{y}$ as a world/screen diagram.

###  5.2 Vectors in hyperbolic space

The functions defined in the last subsection operated on points in hyperbolic
space. In the following subsections, we will define functions that manipulate
both points and _vectors_ in hyperbolic space. In the same way that a point in
hyperbolic space can be used to represent the _position_ of a camera, a vector
in hyperbolic space can be used to represent the _velocity_ of a camera. In
this subsection we will introduce a notion of vectors in hyperbolic space.
These ideas can be found in most textbooks on differential and Riemannian
geometry [6, 12, 11].

In Euclidean space, a vector has a direction and a magnitude. In Riemannian
geometry, a vector additionally has a point at which it’s based. This is
necessary because the fundamental properties of the space change depending on
where the base point is located. We will use bold capital letters, e.g.
$\mathbf{X}$, to denote vectors in hyperbolic space, and we will use the
notation $\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ to denote the set of all
vectors located at point $\mathbf{x}$.

The hyperbolic magnitude $|\mathbf{X}|$ of a vector
$\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ is defined as

$|\mathbf{X}|=\frac{\|\mathbf{X}\|}{v}$

where $\|\mathbf{X}\|$ is the Euclidean norm of $\mathbf{X}$, and $v$ is the
altitude of $\mathbf{x}$. This definition mirrors the definition of the
metric. This must be the case because the magnitude of a velocity vector must
gives a notion of speed, i.e. the rate of change of distance, and this notion
must match the notion of length defined by the metric.

###  5.3 Exponential map

We will now define a function, the _exponential map_ , that takes a vector in
hyperbolic space as input. The exponential map
$\operatorname{Exp}(\mathbf{X})$ of the vector
$\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ gives the point arrived
at by traveling a hyperbolic distance $|\mathbf{X}|$ from $\mathbf{x}$ along
an optimal path with initial direction matching $\mathbf{X}$. This process is
depicted in Figure 3.

Figure 3: The hyperbolic exponential map $\operatorname{Exp}(\mathbf{X})$
sends a vector $\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ to the
point $\mathbf{y}=\operatorname{Exp}(\mathbf{X})$ by finding a geodesic
$\boldsymbol{\upgamma}(t)$ whose initial velocity
$\boldsymbol{\upgamma}^{\prime}(0)$ is equal to $\mathbf{X}$ and then
calculating $\mathbf{y}=\boldsymbol{\upgamma}(1)$. The hyperbolic logarithmic
map $\operatorname{Log}_{\mathbf{x}}(\mathbf{y})$, by contrast, sends two
points $\mathbf{x}$ and $\mathbf{y}$ to the vector
$X=\operatorname{Log}_{\mathbf{x}}(\mathbf{y})$ by finding a geodesic
$\boldsymbol{\upgamma}(t)$ whose endpoints are
$\boldsymbol{\upgamma}(0)=\mathbf{x}$ and
$\boldsymbol{\upgamma}(1)=\mathbf{y}$ and then calculating
$\mathbf{X}=\boldsymbol{\upgamma}^{\prime}(0)$, where
$\boldsymbol{\upgamma}^{\prime}(0)$ is the initial velocity of
$\boldsymbol{\upgamma}(t)$. The exponential and logarithmic maps are therefore
inverses of each other.

For a vector $\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ with
footprint and altitude components $\mathbf{U}$ and $V$ respectively located at
the base point $\mathbf{x}$ with footprint $\mathbf{u}_{0}$ and altitude
$v_{0}$, the exponential map can be calculated as

$\operatorname{Exp}(\mathbf{X})=\left[\begin{smallmatrix}\mathbf{u}_{1}\\\
v_{1}\end{smallmatrix}\right]$ (5a) where, for $\mathbf{U}\neq 0$,
$\displaystyle\mathbf{u}_{1}$
$\displaystyle=\mathbf{u}_{0}+\frac{v_{0}\sinh|\mathbf{X}|}{\cosh(|\mathbf{X}|+r_{0})}\frac{\mathbf{U}}{\lVert\mathbf{U}\rVert}$
(5b) $\displaystyle v_{1}$
$\displaystyle=v_{0}\frac{\cosh(r_{0})}{\cosh(|\mathbf{X}|+r_{0})}$ (5c)
$\displaystyle r_{0}$
$\displaystyle=-\operatorname{asinh}\frac{V}{\|\mathbf{U}\|}.$ (5d) and, for
$u_{0}=u_{1}$, $\displaystyle U$ $\displaystyle=0$ (5e) $\displaystyle W$
$\displaystyle=v_{0}\log(v_{1}/v_{0})$ (5f)

###  5.4 Logarithmic map

The logarithmic map takes two points $\mathbf{x},\mathbf{y}\in\mathbb{H}^{n}$
as arguments and produces a vector
$\operatorname{Log}_{\mathbf{x}}(\mathbf{y})$ that points in the direction of
$\mathbf{y}$ along an optimal path from $\mathbf{x}$, where the magnitude of
this vector is equal to $\operatorname{dist}(\mathbf{x},\mathbf{y})$. The
logarithmic map can be defined by

$\operatorname{Log}_{\mathbf{x}}(\mathbf{y})=\operatorname{gerp}^{\prime}(\mathbf{x},\mathbf{y},0)$

where $\operatorname{gerp}^{\prime}$ denotes the derivative of
$\operatorname{gerp}$ with respect to its last parameter. Then
$\operatorname{Log}_{\mathbf{x}}\mathbf{y}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$
is the initial velocity in hyperbolic space of the optimal path from
$\mathbf{x}$ at $t=0$ to $\mathbf{y}$ at $t=1$, and so this operation is
analogous to the subtraction $\mathbf{y}-\mathbf{x}$ in Euclidean space.

Calculations reveal that for $\mathbf{x}_{0},\mathbf{x}_{1}\in\mathbb{H}$ with
respective footprints $\mathbf{u}_{0},\mathbf{u}_{1}$ and altitudes
$v_{0},v_{1}$, the logarithmic map is given by

$\operatorname{Log}_{\mathbf{x}_{0}}(\mathbf{x}_{1})=\mathbf{X}$ (6a) where,
for $\mathbf{u}_{0}\neq\mathbf{u}_{1}$, the footprint $\mathbf{U}$ and
altitude $V$ components of $\mathbf{X}$ are given by $\displaystyle U$
$\displaystyle=v_{0}S\operatorname{sech}(r_{0})\frac{\mathbf{u}_{1}-\mathbf{u}_{0}}{\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(6b) $\displaystyle W$ $\displaystyle=-v_{0}S\tanh r_{0}$ (6c) $\displaystyle
S$ $\displaystyle=r_{1}-r_{0}$ (6d) $\displaystyle r_{i}$
$\displaystyle=\operatorname{asinh}\frac{v_{1}^{2}-v_{0}^{2}+(-1)^{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert^{2}}{-2v_{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(6e) If $\mathbf{u}_{0}=\mathbf{u}_{1}$, then $(\mathbf{U},W)$ is given by
$\displaystyle U$ $\displaystyle=0$ (6f) $\displaystyle W$
$\displaystyle=v_{0}\log(v_{1}/v_{0})$ (6g)

The exponential and logarithmic maps are inverses of each other, i.e.

$\operatorname{Exp}\left\lparen\operatorname{Log}_{\mathbf{x}}(\mathbf{y})\right\rparen=\mathbf{y}.$

A useful identity that we will use later relating the exponential map,
logarithmic map, and geodesic interpolation is

$\operatorname{Exp}\left(t\operatorname{Log}_{\mathbf{x}}(\mathbf{y})\right)=\operatorname{gerp}(\mathbf{x},\mathbf{y},t)$
(7)

###  5.5 Covariant derivative

In Euclidean space, we can calculate acceleration by differentiating velocity.
However, the second derivative of
$\operatorname{gerp}(\mathbf{x},\mathbf{y},t)$ will generally be nonzero,
since geodesics in hyperbolic geometry are generally curved. However,
geodesics are the hyperbolic analog of straight lines in Euclidean space, and
so its reasonable to desire a hyperbolic analog of acceleration for which
geodesics have zero hyperbolic acceleration.

In Riemannian geometry, this notion is provided by the _covariant derivative_
, which provides a way to differentiate time-varying vectors. Hyperbolic
acceleration is then given by the covariant derivative of velocity. The
covariant derivative can be defined in terms of the metric [6], and
calculations reveal that the covariant derivative for hyperbolic space is
given by

$\frac{D\mathbf{X}}{dt}=\mathbf{X}^{\prime}$ (8a) where the footprint
$\mathbf{U}^{\prime}$ and altitude $V^{\prime}$ components of
$\mathbf{X}^{\prime}$ are given by $\displaystyle\mathbf{U}^{\prime}$
$\displaystyle=\frac{d\mathbf{U}}{dt}-\frac{1}{v}\left\lparen\frac{dv}{dt}\mathbf{U}+\frac{d\mathbf{u}}{dt}V\right\rparen$
(8b) $\displaystyle V^{\prime}$
$\displaystyle=\frac{dV}{dt}+\frac{1}{v}\left\lparen\frac{d\mathbf{u}}{dt}\cdot\mathbf{U}-\frac{dv}{dt}V\right\rparen$
(8c)

in which $\mathbf{u}$ and $v$ are the footprint and altitude of $\mathbf{x}$,
the base point of $\mathbf{X}$.

###  5.6 Transport map

In Euclidean space, vectors do not need to keep track of their base points,
because a vector formed at one point can be easily used at any other point.
For example, consider the expression $\mathbf{z}+(\mathbf{y}-\mathbf{x})$. In
this expression, the subtraction $\mathbf{y}-\mathbf{x}$ is used to form a
vector from base point $\mathbf{x}$ pointing to $\mathbf{y}$, and then this
vector is used in an operation with a different point $\mathbf{z}$. In
hyperbolic space, things are not so simple. If we try to directly change the
base of a vector, e.g. change
$\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ to
$\mathbf{Y}\in\mathbb{T}_{\mathbf{y}}\mathbb{H}^{n}$, then basic properties of
the vector may change, e.g. the hyperbolic magnitude of these two vectors will
not match if the altitude of $\mathbf{x}$ does not equal the altitude of
$\mathbf{y}$.

In Riemannian geometry, the _parallel transport_ operation allows a vector to
be moved to another location. The result of parallel transporting a vector
depends not just on the end points and the vector, but also on the specific
path taken. We will now define a _transport map_ , which moves vectors to
another location along a geodesic.

For points $\mathbf{x}_{0},\mathbf{x}_{1}$ with respective footprints
$\mathbf{u}_{0},\mathbf{u}_{1}$ and altitudes $v_{0},v_{1}$, the transport map
of a vector $\mathbf{X}\in\mathbb{T}_{\mathbf{x}_{0}}\mathbb{H}^{n}$ to
$\mathbf{x}_{1}$ is given by
$\mathcal{T}_{\mathbf{x}_{1}}(\mathbf{X})=\left[\begin{smallmatrix}\mathbf{U}_{1}\\\
V_{1}\end{smallmatrix}\right]$ (9a) where, for
$\mathbf{u}_{0}\neq\mathbf{u}_{1}$, $\displaystyle\mathbf{U}_{1}$
$\displaystyle=\frac{v_{1}}{v_{0}}\mathbf{U}_{0}^{\perp}+\frac{v_{1}}{v_{0}}\operatorname{Re}(z_{1})\frac{\mathbf{u}_{1}-\mathbf{u}_{0}}{\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(9b) $\displaystyle V_{1}$
$\displaystyle=\frac{v_{1}}{v_{0}}\operatorname{Im}(z_{1})$ (9c)
$\displaystyle z_{1}$
$\displaystyle=\vartheta_{1}\overline{\vartheta_{0}}z_{0}$ (9d) $\displaystyle
z_{0}$ $\displaystyle=U_{0}^{\parallel}+W_{0}\boldsymbol{i}$ (9e)
$\displaystyle U_{0}^{\parallel}$
$\displaystyle=\mathbf{U}_{0}\cdot\frac{\mathbf{u}_{1}-\mathbf{u}_{0}}{\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(9f) $\displaystyle\mathbf{U}_{0}^{\perp}$
$\displaystyle=\mathbf{U}_{0}-U_{0}^{\parallel}\frac{\mathbf{u}_{1}-\mathbf{u}_{0}}{\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(9g) $\displaystyle\vartheta_{i}$ $\displaystyle=\tanh
r_{i}+\boldsymbol{i}\operatorname{sech}r_{i}$ (9h) $\displaystyle r_{i}$
$\displaystyle=\operatorname{asinh}\frac{v_{1}^{2}-v_{0}^{2}+(-1)^{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert^{2}}{-2v_{i}\lVert\mathbf{u}_{1}-\mathbf{u}_{0}\rVert}$
(9i) and, for $\mathbf{u}_{0}=\mathbf{u}_{1}$, $\displaystyle\mathbf{U}_{1}$
$\displaystyle=\frac{v_{1}}{v_{0}}U_{0}$ (9j) $\displaystyle V_{1}$
$\displaystyle=\frac{v_{1}}{v_{0}}V_{0}$ (9k)

In these equations, $\boldsymbol{i}$ denotes the imaginary unit, and
$\overline{\vartheta_{0}}$ denotes the complex conjugate of $\vartheta_{0}$.
The functions $\operatorname{Re}$ and $\operatorname{Im}$ the real and
imaginary parts of their respective arguments. Imaginary numbers are used in
these equations to perform rotations. The result of the transport map is shown
in Figure 4.

Figure 4: The transport map $\mathcal{T}_{\mathbf{y}}(\mathbf{X})$ of the
hyperbolic vector $\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ is the
vector $\mathbf{Y}\in\mathbb{T}_{\mathbf{y}}\mathbb{H}^{n}$ obtained by
parallel transporting $\mathbf{X}$ to the new base point
$\mathbf{y}\in\mathbb{H}^{n}$ along a geodesic from $\mathbf{x}$ to
$\mathbf{y}$. In hyperbolic space, the transport map causes the Euclidean
magnitude to change so that the hyperbolic magnitude remains the same—if the
target altitude is higher than the starting altitude, then the Euclidean
magnitude will grow, and if the target magnitude is lower than the starting
altitude, then the Euclidean magnitude will shrink. The vector will also
rotate, keeping a constant Euclidean angle with the geodesic.

##  6 Visualizing zooming and panning animations

A simple way to visualize a zooming and panning path in $\mathbb{H}^{n}$ is to
simply plot the footprint on the $x$ axis and the altitude on the $y$ axis,
i.e. simply plot the path the camera takes. This corresponds to the
$u,w$-space diagrams of van Wijk and Nuij. However, it can be difficult to
discern the perceptual effect of zooming and panning from these
footprint/altitude diagrams.

To visualize a zooming and panning animation in a way that emphasizes the
perceived motion, we introduce a novel visualization technique: _world/screen
diagrams_. A world/screen diagram consists of two sub-diagrams that share a
common time axis. The upper part of the world/screen diagram is a _screen
bounds diagram_ , which plots the screen center and screen bounds in world
space over time. The lower part of the world/screen diagram is an _optical
pathline diagram_ , which plots world points in screen space over time. An
optical pathline diagram has time on the horizontal axis and screen space on
the vertical axis, and each curve in the diagram is a constant point in world
space. For each world-point curve in the optical pathline diagram, the slope
of the curve corresponds to the onscreen velocity of the world point. Example
world/screen diagrams are shown in Figures 5, 6 and 7. By mapping time to a
dedicated axis, the world/screen allows for precise visualizations of the
temporal aspects of a zooming and panning animation. By contrast, in a
$u,w$-space diagram, time must be encoded by color or by dots placed at
regularly-spaced intervals in time.

Figure 5: A _world/screen diagram_ for a zooming-out animation. The upper
plot, the _screen bounds diagram_ , shows the screen center and screen bounds
plotted in world space over time. The lower plot, the _optical pathline
diagram_ , shows world points plotted in screen space over time. The slope of
each line in the optical pathline diagram at each instant in time corresponds
to the velocity of an onscreen point at that instant. As the animation
progresses, the screen occuppies an increasingly large portion of world-space,
as can be seen in the screen bounds diagram. At the same time, a given portion
of world space occupies an increasingly small portion screen space, as can be
seen from the optical pathline diagram. Figure 6: A world/screen diagram for a
panning animation. The world bounds diagram (above) shows that the screen
moves through world space at a constant rate, and the optical pathline diagram
(below) shows that world points move through screen space at a constant rate.
Figure 7: A world/screen diagram for optimal zooming and panning. This diagram
depicts zooming out, followed by panning, followed by zooming in. The specific
zooming and panning path used was calculated using the smooth and efficient
technique of van Wijk and Nuij.

One advantage of world/screen diagrams over other representations of zooming
and panning trajectories is that the optical pathline diagrams corresponds
more closely to the perception of zooming and panning than other diagrams. In
fact, the root-mean-square optical flow velocity, which van Wijk and Nuij
originally used to define their metric, can be determined for each time
instant in the world/screen diagram by finding the root-mean-square slope of
all pathlines at that instant. By contrast, points taken from a perceptually
uniform trajectory at equally-spaced moments in time will appear to be
unevenly spaced if plotted in a footprint/altitude diagram or a space-scale
diagram, and so these diagrams do not accurately represent perception.

###  6.1 Optical pathline diagrams

We will now describe the algorithm we used to create the optical pathline
diagrams in this paper. In principle, an optical pathline diagram can be
created by taking any set of world-space points and plotting their paths in an
optical pathline diagram. However, this approach leads to diagrams in which
curves are closely spacing in some regions widely spaced in others. To remedy
this problem, we add and remove world-point curves from the diagram as space
allows.

We will now show that the problem of adding and removing world-point curves
can be seen as a problem of adding and removing isolines (i.e. contour lines)
from a scalar field. Consider the scalar field $\varphi$ that maps time $t$
and screen point $r$ to the corresponding world point
$p=\varphi(t,r)=v(t)r+u(t)$. The isolines of this field are the world-point
curves in the optical pathline diagram. Therefore, we must choose when to add
and remove isolines from the diagram.

Note that if $\varphi(t,r)$ is linear, then the gradient magnitude
$\lVert\nabla\varphi(t,r)\rVert$ is constant over all $t$ and $r$. In this
case, if we add isolines at equally-spaced wold-points, then the isolines will
also be equally spaced. The wold-point spacing $P$ and screen-space isoline
spacing $R$ are related by

$P=R\lVert\nabla\varphi(t,r)\rVert$

In practice, the function $\varphi(t,r)$ will not be linear, but provided that
it is sufficiently smooth, the above relationship will approximately hold.
This relationship provides the intuition behind the algorithm we will
describe.

Let the set $C_{\alpha}\subset\mathbb{R}^{2}$, for parameter $\alpha>0$ that
controls the spacing, be the set of all points in the optical pathline diagram
at which a contour should be drawn. We define $C_{\alpha}$ as the set of all
$(t,r)$ such that there exists a power of two not less than
$\alpha\lVert\nabla\varphi(t,r)\rVert$ that divides $\varphi(t,r)$. Using the
notation

$\llceil x\rrceil=2^{\left\lceil\log_{2}(x)\right\rceil}$

the definition of $C_{\alpha}$ can be written as

$C_{\alpha}=\left\\{(t\in\mathbb{R},r\in\mathbb{R}):\llceil\alpha\lVert\nabla\varphi(t,r)\rVert\rrceil\mathrel{\text{divides}}\varphi(t,r)\right\\}.$

This can be seen as a discretized version of the dense isocontour imaging
technique of Matvienko and Krüger [14].

Now that we have defined $C_{\alpha}$, we will describe an algorithm for
computing the optical pathline diagrams. The optical pathline diagram will
take as input the parameter $\alpha$ which controls the spacing of the
pathlines, the footprint and altitude functions $u(t)$ and $v(t)$, and the
screen-space bounds $r_{\text{\tiny low}}$ and $r_{\text{\tiny high}}$.

Notice that

$\displaystyle\lVert\nabla\varphi(t,r)\rVert^{2}$
$\displaystyle=\left(\frac{\partial}{\partial
t}p(t,r)\right)^{2}+\left(\frac{\partial}{\partial r}p(t,r)\right)^{2}$
$\displaystyle=\left(rv^{\prime}(t)+u^{\prime}(t)\right)^{2}+\left(v(t)\right)^{2}$

where $v^{\prime}(t)$ and $u^{\prime}(t)$ are the derivatives of $v(t)$ and
$u(t)$ respectively. Because

$\left|v(t)\right|=\left|\frac{\partial}{\partial
r}p(t,r)\right|\leq\lVert\nabla p(t,r)\rVert,$

a necessary condition for $(t,r)\in C_{\alpha}$ is that $\llceil\alpha\lvert
v(t)\rvert\rrceil$ divides $p(t,r)$. Taking advantage of this necessary
condition, we can use the following algorithm to find the optical pathline
diagram:

  * •

Let $A$ be an empty hash map.

  * •

For each time step $i$:

    * –

Calculate

$\displaystyle P$ $\displaystyle=\llceil\alpha\lvert v(t_{i})\rvert\rrceil$
$\displaystyle p_{\text{\tiny low}}$
$\displaystyle=P\left\lceil\frac{v(t_{i})r_{\text{\tiny
low}}+u(t_{i})}{P}\right\rceil$ $\displaystyle p_{\text{\tiny high}}$
$\displaystyle=P\left\lfloor\frac{v(t_{i})r_{\text{\tiny
high}}+u(t_{i})}{P}\right\rfloor.$

    * –

For each $p$ in $p_{\text{\tiny low}},\,p_{\text{\tiny
low}}+P,\,p_{\text{\tiny low}}+2P,\,p_{\text{\tiny
low}}+3P,\,\dots,\,p_{\text{\tiny high}}$:

      * *

Calculate

$\psi=\lVert\nabla\varphi(t,r)\rVert=\sqrt{\Big{\lparen}v(t)\Big{\rparen}^{2}+\Big{\lparen}rv^{\prime}(t_{i})+u^{\prime}(t_{i})\Big{\rparen}^{2}}$

If the derivatives $v^{\prime}$ and $u^{\prime}$ are not available (e.g.
because the zooming and panning animation is computed frame-by-frame rather
than as a continuous path), then they can be approximated by finite
differences.

      * *

If $\llceil\alpha\psi\rrceil$ does not divide $p$ then continue to the next
$p$.

      * *

Otherwise, check to see if $A[p]$ exists.

        * ·

If $A[p]$ does not exist, assign to $A[p]$ a list containing $i$ as its sole
element.

        * ·

If $A[p]$ does exist, append $i$ to the list $A[p]$.

  * •

For each key $p$ in $A$:

    * –

For each $i$ in $A[p]$:

      * *

Calculate the screen-space point $r$ corresponding to $p$ using

$r=\frac{p-u(t_{i})}{v(t_{i})}.$

      * *

If $i$ is the first element in $A[p]$, or if the previous element in $A[p]$
was not $i-1$, then begin a new pathline at $(t_{i},r)$.

      * *

Otherwise, add a new segment to the current pathline that connects to
$(t_{i},r)$.

##  7 The problem of interruptions

The previous sections have developed the hyperbolic model of zooming and
panning. We will now use this model to solve the interruptible zooming and
panning problem.

In the interruptible zooming and panning problem, we are given as input a
_target signal_ $\mathbf{x}(t)$ and we must compute as output a _smoothed
signal_ $\mathbf{y}(t)$. At each instant $t$, the target camera position is
given by $\mathbf{x}(t)\in\mathbb{H}^{n}$, and the smoothed camera position
$\mathbf{y}(t)\in\mathbb{H}^{n}$ must be computed. Importantly, the
computation of the smoothed camera position $\mathbf{y}(t)$ must depend only
on $\mathbf{x}(\tau)$ for all $\tau<t$. In other words, the transformation
from the target signal to the smoothed signal must be _causal_ —the smoothed
camera position must be computed at each instant using only the past and
present behavior of the input signal. This models the real-world usage of
interruptible zooming and panning in user interfaces, where future user input
is unknowable.

(a) Constant speed

(b) Easing curve

(c) Cascaded one-pole filter

(d) Clipped cascaded one-pole filter

Figure 8: These world/screen diagrams depict the result of different zooming
and panning approaches applied to the same target signal. In these diagrams
the target signal is depicted as a pair of bold lines that shows the desired
world span. The constant-speed technique uses the optimal navigation approach
of van Wijk and Nuij [18] to produce an animation towards the current target.
The easing curve technique shows an straightforward modification of optimal
navigation. As can be seen, neither the constant-speed technique (a) nor the
easing curve technique (b) are smooth when interrupted. For both of these
techniques, interruptions produce velocity discontinuities in screen space. By
contrast, a geodesic one-pole filter cascaded four times (c) is smooth even
when interrupted, as is the clipped cascaded one-pole filter (d).

Before we introduce the signal-processing-based solutions that are the main
focus of this paper, we first describe two simple techniques and analyze their
disadvantages. These simpler techniques assume that the target signal is a
step function, i.e. the target camera position changes abruptly at times
$t_{1},t_{2},t_{3},\dots$ but is otherwise constant.

###  7.1 Constant speed

The obvious way to handle an interruption is to simply begin a new path from
the current position to the new target. With this approach, the output always
moves towards the target at a constant hyperbolic speed. Specifically, for
each change of target, follow the path
$\operatorname{geo}(\mathbf{y}_{0},\mathbf{x}_{1},ct)$, where $\mathbf{y}_{0}$
is the current output at the time of the target change, $\mathbf{x}_{1}$ is
the new target, $c$ is the speed of the animation, and $t$ is the time elapsed
since the target change. When
$ct\geq\operatorname{dist}(\mathbf{y}_{0},\mathbf{x}_{1})$, the target has
been reached, and so the output should remain at the target until the next
change of target.

The problem with this technique is that every time the target is reached, and
every time the target is changed444Except, of course, for the edge case where
the new target happens to lie on the same geodesic as the current target, and
in the same direction., a velocity discontinuity is introduced into the
smoothed signal. These discontinuities are easily seen in a world/screen
diagram, as illustrated in Figure 8a.

###  7.2 Easing curves

Another simple solution is to use an _easing curve_. As we will show, this
solves the problem of velocity discontinuities at the endpoints, but does not
solve the problem of interruptions.

The easing curve can be specified as follows: for each change of target,
follow the path $\operatorname{gerp}(\mathbf{y}_{0},\mathbf{x}_{1},f(t/d))$,
where $\mathbf{y}_{0}$ is the current output at the time of the target change,
$\mathbf{x}_{1}$ is the new target, $d$ is the desired duration of the
animation, $t$ is the elapsed time since the target change, and $f$ is an
_easing curve_ , which satisfies $f(0)=0$ and $f(\alpha)=1$ for all
$\alpha\geq 1$. The easing curve should also satisfy
$f^{\prime}(0)=f^{\prime}(1)=0$, where $f^{\prime}$ denotes the derivative of
$f$. One easing curve that satisfies these properties is

$f(\alpha)=\begin{cases}(1/2)-(1/2)\cos(\pi\alpha)&\alpha<1\\\ 1&\alpha\geq
1,\end{cases}$

but there are many other options as well.

Provided that $f^{\prime}(0)=f^{\prime}(1)=0$, this approach does not suffer
from velocity discontinuities at the endpoints. However, it does not handle
the case of interruptions, since an interruption would cause the velocity to
abruptly jump to zero as the new animation segment begins. The velocity
discontinuities introduced by interruptions in the easing approach are easily
seen in the world/screen diagram, as shown in Figure 8b.

One difference between this technique and the previous technique is that the
duration of the animations produced using this technique is fixed, whereas for
the previous technique, the duration of the animations produced is
proportional to the distance between the start point and the target point. We
do not claim that having a fixed duration is superior to a variable duration
or vice versa—the choice depends on the specific effect the interaction
designer is trying to achieve.

##  8 Smoothing using geodesic one-pole filters

To solve the problem of smoothing both the endpoints and interruptions, we
introduce a novel technique for smooth and efficient zooming and panning that
draws inspiration from signal processing. While signal processing techniques
have previously been used to animate Euclidean attributes [17], to process
orientation signals [13], and to process signals on a sphere [15], to our
knowledge signal-processing techniques have not been applied to signals in
hyperbolic space.

The techniques of the previous section were formulated in terms of target
changes, and each target change triggered a change in the formulation of the
output. In this section, we take a different approach. Instead of processing
target change events, we instead process the target signal directly,
transforming the target signal into the smoothed signal using differential
equations. There are many ways to perform this transformation, and different
methods will produce different animations. This section introduces a
particularly simple method, which is based on the _one-pole low-pass filter_ ,
a common filter in signal processing. We call our technique the _geodesic one-
pole filter_.

For the target signal $\mathbf{x}(t)$, the output $\mathbf{y}(t)$ of the
geodesic one-pole filter is defined by the differential equation

$\frac{d}{dt}\mathbf{y}(t)=\alpha\operatorname{Log}_{\mathbf{y}(t)}\mathbf{x}(t)$
(10)

where $\alpha$ controls the speed of the animation. This equation is depicted
in block diagram form in Figure 9. This differential equation can be explained
as follows: at every instant, walk along a geodesic towards the target with
hyperbolic speed proportional to the hyperbolic distance to the target. This
system is clearly causal, since the derivative of the output depends only on
the current output and input. The output of this system is shown in Figure
10a.

Figure 9: The geodesic one-pole filter, given by Equation 10, can be depicted
as a block diagram. Each wire in this diagram represents a signal: solid wires
represent signals whose values are hyperbolic points, and wavy wires represent
signals whose values are hyperbolic vectors. The triangular element represents
multiplication. The integral block represents the following relationship: the
input to the block is the derivative of the block’s output. The arrow with a
bar pointing to Log denotes the subscript argument.

(a) Geodesic one-pole filter

(b) Clipped geodesic one-pole filter

(c) Cascaded one-pole filter

(d) Clipped cascaded one-pole filter

Figure 10: The geodesic one-pole filter (a) produces faster zooming and
panning animations for targets that are farther away. The clipped one-pole
filter (b), by contrast, limits the maximum speed of the animation. For
discontinuous input, neither of these systems produces smooth zooming and
panning animations, but they can be combined with additional one-pole filters
to produce smoother animations, as shown in (c) and (d).

###  8.1 Cascading filters

While the one pole filter does smooth its input, it is not strong enough for
our purposes. As can be seen from Equation 10, the derivative of the output is
proportional to the difference between the input and the output. Because the
output’s derivative is always defined, the output will be continuous even if
the input is not. However, it is clear from the definition that a
discontinuity in the input will introduce a velocity discontinuity in the
output.

To create a more powerful filter, we can cascade multiple instances of the one
pole filter, i.e. place them in series. An example of this is shown in Figure
11. The output of the cascaded one-pole filter is shown in Figure 8c. Each
additional one-pole filter used in a cascaded arrangement increases the order
of smoothness. A single one-pole filter produces an output with continuous
position. Cascading two one-pole filters produces an output with continuous
velocity. Cascading three one-pole filters produces an output with continuous
acceleration. Cascading four one-pole filters produces an output with
continuous jerk.

Figure 11: The output of a single one-pole filter is continuous in position,
but may not be continuous in velocity. In order to guarantee that the output
is smooth to a higher degree, one-pole filters can be chained together. The
filter depicted in this diagram, in which four one-pole filters are cascaded,
produces an output with continuous position, velocity, acceleration, and jerk.
Each block $\operatorname{OnePole}(\alpha)$ denotes the filter structure shown
in Figure 9.

###  8.2 Limiting the hyperbolic speed

Like the easing curve method, the one-pole filter will produce animations
where the hyperbolic speed is greater for far-away targets than for nearby
targets. For some use-cases, this can be undesirable, and so we will now
discuss a simple modification of the one-pole filter that limits the maximum
speed of the animation.

To accomplish this, we first define the function
$\operatorname{clipvec}(\mathbf{X},c)$ as follows:

$\operatorname{clipvec}(\mathbf{X},c)=\begin{cases}\mathbf{X}&|\mathbf{X}|<c\\\
c\frac{\mathbf{X}}{|\mathbf{X}|}&|\mathbf{X}|\geq c\end{cases}$ (11)

This function takes a vector
$\mathbf{X}\in\mathbb{T}_{\mathbf{x}}\mathbb{H}^{n}$ and modifies its
magnitude hyperbolic $|\mathbf{X}|$ so that it does not exceed a threshold
$c$. Using this function, we can then define the clipped geodesic one-pole
filter as

$\frac{d}{dt}\mathbf{y}(t)=\operatorname{clipvec}\left\lparen\alpha\operatorname{Log}_{\mathbf{y}(t)}\mathbf{x}(t),c\right\rparen$
(12)

where $c$ is a threshold that sets the maximum allowed hyperbolic speed. The
output of this system is shown in Figure 10b. By placing in series a clipped
one-pole filter followed by three geodesic one-pole filters, a system is
formed whose output is smooth and whose speed is limited. We call this system
the _clipped cascaded geodesic one-pole filter_. The video demo that
accompanies this paper uses the values $c=1\text{ Hz}$ for the first filter
and $\alpha=6\text{ Hz}$ for all four filters555These definitions of $c$ and
$\alpha$ assume that distance in hyperbolic space is unitless, as is the case
when the metric is unitless. If the metric were defined strictly as the root-
mean-square velocity of the optical flow on a physical screen, then $c$ would
instead have units of speed (meters per second). However, in this case, the
value of $c$ would depend on the size of the screen..

###  8.3 Discretizing the one-pole filter

The previous section described solutions to the interruptible zooming and
panning problem in terms of cascaded first-order differential equations. To
write a program that implements one of these solutions, any ordinary
differential equation (ODE) solver can be used to numerically approximate
these differential equations. In this section, however, we take an alternative
approach: we convert the continuous-time systems described in the last section
into discrete-time systems. The solution we arrive at is quite simple, and
does not require the use of an external ODE solver.

Notice that the geodesic one-pole filter Equation 10 and the clipped geodesic
one-pole filter Equation 12 have the form

$\frac{d}{dt}\mathbf{y}(t)=f(\mathbf{y}(t),\mathbf{x}(t))$ (13)

where $f(\mathbf{y}(t),\mathbf{x}(t))\in\mathbb{T}_{\mathbf{y}(t)}$. A
differential equation of this form can be approximated by

$\mathbf{y}[i]=\operatorname{Exp}(Tf(\mathbf{y}[i-1],\mathbf{x}[i]))$ (14)

where $T$ is the sampling period and
$f(\mathbf{y}[i-1],\mathbf{x}[i])\in\mathbb{T}_{\mathbf{y}[i-1]}$. To see that
this does approximate the continuous-time system, note that Equation 14 can be
written as

$\mathbf{y}(t)=\operatorname{Exp}(Tf(\mathbf{y}(t-T),\mathbf{x}(t))).$

Taking the logarithmic map of both sides with base $\mathbf{y}(t-T)$ and then
dividing both sides by $T$ gives

$\frac{\operatorname{Log}_{\mathbf{y}(t-T)}\mathbf{y}(t)}{T}=f(\mathbf{y}(t-T),\mathbf{x}(t))$

Taking the limit as $T$ goes to zero gives Equation 13.

Applying this approximation to the geodesic one-pole filter Equation 10 and
simplifying using Equation 7 gives

$\mathbf{y}[i]=\operatorname{gerp}(\mathbf{y}[i-1],\mathbf{x}[i],b)$ (15)

where $b=\alpha T$ for sampling period $T$. In other words, at each frame, we
take step towards the target, where the length of the step is proportional to
the distance to the target. A block diagram of this approximation is shown in
Figure 12. Note that this approximation oscillates for $b>1$ and is unstable
for $b>2$, and so the sampling period $T$ should be small enough that $b<1$.

To approximate the cascaded one-pole system shown in Figure 11, we can simply
cascade the discrete one-pole filters as shown in Figure 13.

Applying the approximation given by Equations 13 and 14 to the clipped one-
pole filter Equation 12 and simplifying gives

$\displaystyle\mathbf{y}[i]$
$\displaystyle=\operatorname{geo}\left\lparen\mathbf{y}[i-1],\mathbf{x}[i],s[i]\right\rparen$
(16a) $\displaystyle s[i]$ $\displaystyle=T\min\left\lparen c,\alpha
S[i]\right\rparen$ (16b) $\displaystyle S[i]$
$\displaystyle=\operatorname{dist}(\mathbf{y}[i-1],\mathbf{x}[i])$ (16c)

where $T$ is the sampling period.

Figure 12: The discrete-time hyperbolic one-pole filter is an approximation to
the continuous-time one-pole filter depicted in Figure 9. The element $z^{-1}$
denotes a delay by one sample, i.e. a delay by the sampling period $T$. The
block $\operatorname{gerp}(b)$ denotes
$\operatorname{gerp}(\mathbf{x}_{0},\mathbf{x}_{1},b)$, where the arrowhead
with a bar in the diagram corresponds to $\mathbf{x}_{0}$ and the arrowhead
without a bar in the diagram corresponds to $\mathbf{x}_{1}$. Figure 13: The
cascaded one-pole system depicted in Figure 11 can be discretized by cascading
the discrete one-one pole blocks depicted in Figure 12.

##  9 Smoothing using geodesic two-pole filters

The technique discussed in the previous section formed higher-order filters by
cascading one-pole filters. Animations that make use of these filters travel
directly to their target, settling in slowly. Suppose that we instead wanted
an animation where the camera overshoots the target slightly before settling
in a spring-like motion. To achieve this effect, we can use a two pole filter,
which models the behavior of a spring-mass-damper system.

In Euclidean space, a spring-mass-damper system experiences two forces: a
spring force that pulls the mass towards the equilibrium position and is
proportional to the displacement from this equilibrium position, and a damping
force that pushes against the mass’s velocity. The spring-mass-damper system
can be adapted to hyperbolic space as follows:

$\frac{D}{dt}\frac{d}{dt}\mathbf{y}(t)=\omega_{0}^{2}\operatorname{Log}_{\mathbf{y}(t)}(\mathbf{x}(t))-2\zeta\omega_{0}\frac{d}{dt}\mathbf{y}(t)$
(17)

The variable $\omega_{0}$ controls the rate of the animation, and the
parameter $\zeta$ controls the damping. When $\zeta<1$, the system oscillates
in a spring-like motion as it settles. A block diagram of this is shown in
Figure 14. The response of the two-pole filter for discontinuous input is
shown in Figure 15.

Figure 14: The geodesic two-pole filter defined by Equation 17 can be depicted
as a block diagram. Here, the integral with a circle represents the following
relationship: the input to the block is the covariant derivative of the
output. Figure 15: The geodesic two-pole filter defined by Equation 17
produces spring-like motion.

The system defined by Equation 17 can of course be placed in series with a
one-pole filter or another two-pole filter. Like the one-pole filter and
easing curves, animation produced by the two-pole filter will be faster for
distant targets than for nearby targets. A simple way to address this is to
place the clipped one-pole filter in series with the two-pole filter. We call
the system consisting of a single clipped one-pole filter followed by a two-
pole filter the _clipped geodesic two-pole filter_. Another way to reduce the
speed for distant targets would be to use quadratic damping instead of linear
damping, but this paper does not explore this option.

###  9.1 Discretizing the two-pole filter

As with the continuous-time one-pole filter, the differential equation given
by Equation 17 can be approximated using a standard ODE solver. However, we
can also write a simple approximation by converting the continuous-time system
to a discrete-time system.

Notice that the geodesic two pole filter has the form

$\frac{D}{dt}\frac{d}{dt}\mathbf{y}(t)=f\left\lparen\mathbf{y}(t),\mathbf{\dot{y}}(t),\mathbf{x}(t)\right\rparen$
(18)

where $\mathbf{\dot{y}}(t)$ denotes the time derivative of $\mathbf{y}(t)$. A
system of this form can be approximated by

$\displaystyle\mathbf{\dot{y}}[i]$
$\displaystyle=\mathbf{\dot{y}}[i-1]+Tf\left\lparen\mathbf{y}[i-1],\,\mathcal{T}_{\mathbf{y}[i-1]}\mathbf{\dot{y}}[i-1],\,\mathbf{x}[i]\right\rparen$
(19) $\displaystyle\mathbf{y}[i]$
$\displaystyle=\operatorname{Exp}(T\mathbf{\dot{y}}[i])$ (20)

Here both $\mathbf{y}[i]\in\mathbb{H}^{n}$ and
$\mathbf{\dot{y}}[i]\in\mathbb{T}_{\mathbf{y}[i-1]}\mathbb{H}^{n}$ are state
variables that are updated at each frame. The parallel transport in this
formula is necessary to move the vector variable $\mathbf{\dot{y}}[i]$ to the
correct location each time the position variable $\mathbf{y}[i]$ is updated.

Applying this approximation to the geodesic two-pole filter gives

$\displaystyle\mathbf{\dot{y}}[i]$
$\displaystyle=(1-2T\zeta\omega_{0})\mathcal{T}_{\mathbf{y}[i-1]}(\mathbf{\dot{y}}[i-1])$
(21)
$\displaystyle\quad{}+T\omega_{0}^{2}\operatorname{Log}_{\mathbf{y}[i-1]}(\mathbf{x}[i])$
$\displaystyle\mathbf{y}[i]$
$\displaystyle=\operatorname{Exp}(T\mathbf{\dot{y}}[i]).$ (22)

The demo videos that accompany this paper have sixty frames per second, and so
$T=(1/60)\text{ s}$.

##  10 Conclusion and future work

We have introduced the hyperbolic model of zooming and panning. This model
exploits the Poincaré half-space model of hyperbolic space to model zooming
and panning. Using this model, we have introduced novel zooming and panning
animation techniques based on signal processing and Riemannian geometry. These
animation techniques produce smooth zooming and panning animations to a target
value, and these animations remain smooth even when the animation is
interrupted by a change of target. Such interruptions are common in
interactive uses, where user input can interrupt zooming and panning
animations at any time.

We have also introduced world/screen diagrams to visualize zooming and panning
animations. These diagrams emphasize the perceptual aspects of zooming and
panning, and are useful for evaluating different zooming and panning
techniques.

There are many avenues for future work. For example, if instead of the
interactive zooming and panning problem we have investigated in this paper, we
merely wish to interpolate a set of target points, the Bézier curve
generalization of Park and Ravani [16] can be straightforwardly applied to
zooming and panning using the definitions we presented here. The animation
model in this paper could also be applied to other navigation problems, e.g.
lenses [1, 3] or zooming and panning on a globe. Finally, there are possible
variations on the specific signal processing systems we have introduced that
could be explored in future work.

This paper has used the Poincaré half-space model to represent zooming and
panning positions. However, there are many other possible coordinate systems
that could be used for hyperbolic space. While the results remain the same
regardless of coordinate system, different coordinate systems might be more
convenient for particular purposes. Other well-known representations for
hyperbolic space include the Poicaré disk model, the Klein model, and the
hyperboloid model [4]. Another option would be to use space-scale diagrams.
Yet another option would be to a model in which the altitude of the camera is
constant and the angle of view is varied to zoom and pan. Such a model would
match the term “zooming” more closely, since zooming on a camera involves
changing the angle of view rather than changing the position of the
camera.666In fact, it might be more accurate to refer to the model used in
this paper as dollying and panning rather than zooming and panning.

##  11 Acknowledgments

This research was supported in part by NSF grant IIS-1447416.

## References

  * [1] C. Appert, O. Chapuis, and E. Pietriga.  High-precision magnification lenses.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 273–282. ACM, 2010.
  * [2] B. B. Bederson, J. Meyer, and L. Good.  Jazz: an extensible zoomable user interface graphics toolkit in java.  In Proceedings of the 13th annual ACM symposium on User interface software and technology, pages 171–180. ACM, 2000.
  * [3] E. A. Bier, M. C. Stone, K. Pier, W. Buxton, and T. D. DeRose.  Toolglass and magic lenses: the see-through interface.  In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pages 73–80. ACM, 1993.
  * [4] J. W. Cannon, W. J. Floyd, R. Kenyon, W. R. Parry, et al.  Hyperbolic geometry.  Flavors of geometry, 31:59–115, 1997.
  * [5] A. Cockburn, A. K. Karlson, and B. B. Bederson.  A review of overview+ detail, zooming, and focus+ context interfaces.  ACM Comput. Surv., 41(1):2–1, 2008.
  * [6] M. P. Do Carmo and J. Flaherty Francis.  Riemannian geometry, volume 115.  Birkhäuser Boston, 1992.
  * [7] P. Dragicevic, A. Bezerianos, W. Javed, N. Elmqvist, and J.-D. Fekete.  Temporal distortion for animated transitions.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 2009–2018. ACM, 2011.
  * [8] G. W. Furnas and B. B. Bederson.  Space-scale diagrams: Understanding multiscale interfaces.  In Proceedings of the SIGCHI conference on Human factors in computing systems, pages 234–241. ACM Press/Addison-Wesley Publishing Co., 1995\.
  * [9] Y. Guiard, M. Beaudouin-Lafon, J. Bastin, D. Pasveer, and S. Zhai.  View size and pointing difficulty in multi-scale navigation.  In Proceedings of the working conference on Advanced visual interfaces, pages 117–124. ACM, 2004.
  * [10] T. Igarashi and K. Hinckley.  Speed-dependent automatic zooming for browsing large documents.  In Proceedings of the 13th annual ACM symposium on User interface software and technology, pages 139–148. ACM, 2000.
  * [11] J. Lee.  Riemannian manifolds : an introduction to curvature.  Springer, New York, 1997.
  * [12] J. Lee.  Introduction to smooth manifolds.  Springer, New York London, 2012.
  * [13] J. Lee and S. Y. Shin.  General construction of time-domain filters for orientation data.  Visualization and Computer Graphics, IEEE Transactions on, 8(2):119–128, 2002.
  * [14] V. Matvienko and J. Krüger.  Dense isocontour imaging.  In SIGGRAPH Asia 2013 Technical Briefs, page 16. ACM, 2013.
  * [15] J. M. Osborne and G. P. Hicks.  The geodesic spring on the euclidean sphere with parallel-transport-based damping.  Notices of the American Mathematical Society, 60(5):544–557, 2013\.
  * [16] B. Ravani and F. C. Park.  Bézier curves on riemannian manifolds and lie groups with kinematics applications.  1995\.
  * [17] A. M. Reach and C. North.  The signals and systems approach to animation, 2017.
  * [18] J. J. van Wijk and W. A. Nuij.  Smooth and efficient zooming and panning.  In Information Visualization, 2003. INFOVIS 2003. IEEE Symposium on, pages 15–23. IEEE, 2003.
  * [19] J. J. Van Wijk and W. A. Nuij.  A model for smooth viewing and navigation of large 2D information spaces.  IEEE Transactions on Visualization and Computer Graphics, 10(4):447–458, 2004.