# Navigating though the surface of a hypersphere in a computer game

People in StackOverflow seems not so into this theme, so I thought I could have better luck in here.

I had the idea of an spaceship game where the world is confined in the surface of an 4-D hypersphere (also called a 3-sphere). Thus, in seeing it from inside, it would look like a 3-D world, but by navigating in every direction, I would never leave the limited volume of the 3-sphere.

To represent the 3-shpere as a "flat" 3-D space, I use a stereographic projection, which is very simple to implement, just need to divide the point in the 3-sphere by one minus its w coordinate.

To represent the vertices of the objects I am using normalized 4d vectors, such that x²+y²+z²+w²=1, thus keeping them inside the 3-sphere.

The first problem to solve was rotation. But I soon figured out that ordinary 3d rotation matrices would suffice to rotate the world around the viewer in the 3d projection, since it does not mess up with the w coordinate (pretty much like rotating a sphere around the z-axis would also rotate its stereographic projection).

Then I figured out that any rotation that included the w coordinate would be equivalent of translation inside the 3d projection (just not commutative, as ordinary 3d translations on "flat" spaces), then I could translate along the axis by using a simple around axis rotation matrix (x', y') = (x * cos a - y * sin a, x * sin a + y * cos a), but variating w along with another axis.

This is so far where I got, and I could not figure out how to navigate forward, based on the position the viewer is facing from the projection. I can apply the inverse transform to derive the normalized 4-D vector (called F) the viewer is facing in the hypersphere coordinates, but I don't know how to navigate in that direction by using a 4x4 matrix (what is optimal in OpenGL). I could think on a hackish solution: for every vertex V, do V' = normalize(d*F + V), where d is the distance moved forward (in some strange unit I can not exactly precise). This way only works for small values of d, there is no direct correlation between d and the angle variation.

Thus the question is: how to move forward (using a 4x4 matrix transform) being in the surface of a 4-D hypersphere? In other words: if I am at (x, y, z, w) now and want to be at (x', y', z', w') next (both vectors of norm 1), how can I derive M such that $M \times (x, y, z, w) = (x', y', z', w')$ ?

-

The $M$ you asked in your final question is in general non-unique, given the data you specified. The way to see this is as follows:

Given a point $(x,y,z,w)$ and another $(x',y',z',w')$, add to it the third point $(0,0,0,0)$ in four dimensional space. Assuming that the two original points do not coincide and that they are not antipodes, this three points are not collinear and so defines a plane in four dimensional space. So you can take a rotation in that plane that carries $(x,y,z,w)$ to $(x',y',z',w')$ while fixing the directions perpendicular to that plane fixed. Call this transformation $M_1$.

However, since your ambient space is four dimensional, the directions perpendicular to the given plane also is two dimensional (4-2 = 2). So you can equally take an arbitrary rotation in that plane which fixes all directions perpendicular to it. Call such a rotation $O$. Then you can check that $M_2 = OM_1$ also sends $(x,y,z,w)$ to $(x',y',z',w')$.

To be explicit. Assume your initial coordinate is $(1,0,0,0)$ and the final coordinate is $(0,1,0,0)$. Then we have

$$M_1 = \begin{pmatrix} 0 & -1 & 0 & 0\\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}$$

If you take $O$, parametrized by $\theta$, to be

$$O(\theta) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & \cos\theta & \sin\theta \\ 0 & 0 & -\sin\theta & \cos\theta\end{pmatrix}$$

then you can check that $O(\theta)M_1$ will send $(1,0,0,0)$ to $(0,1,0,0)$ for any $\theta$, but the matrices $O(\theta)M_1$ are all different for $\theta$ in the range $0 \leq \theta < 2\pi$.

So what does this mean physically? Moving "forward" in Euclidean space is not as simple an issue as you think. The analogue of the different $O(\theta)$ in 3 dimension Euclidean space corresponds to rotating the whole space along the axis of travel! In other words, imagine you have a spaceship in Euclidean space and it spins (with the axis of spinning in the same direction of its travel) while it moves forward. This is what $O(\theta)$ captures, the spinning.

Without getting too much into the gory details, I will note that this ambiguity lies in the heart of differential/Riemannian geometry, and is closely connected with the notion of parallel transport.

In any case, using a bit of differential geometry, you can see that the matrix $M_1$ defined above is the "correct" notion of translation is you do not want "spinning".

Okay, enough about that. How to actually implement this? Let's say that the viewer is sitting at coordinates $(x,y,z,w)$. And let's say the viewer is facing in the direction of $(\delta x, \delta y, \delta z, \delta w)$ with $\delta x^2 + \delta y^2 + \delta z^2 + \delta w^2 = 1$. Notice that since the direction the viewer is facing is tangential to the hypersphere, it must be perpendicular to the coordinates, that is

$$x\cdot \delta x + y\cdot \delta y + z \cdot \delta z + w \cdot \delta w = 0$$

Given these two vectors, you can use some linear algebra to complete them to an orthonormal basis of four dimensional space (which can be obtained by solving some linear equations based on orthogonality to the two given vectors), call the two additional vectors $(a,b,c,d)$ and $(a',b',c',d')$. Then your translation matrix should be given by

$$M(\phi) = \begin{pmatrix} x & \delta x & a & a'\\ y & \delta y & b & b' \\ z & \delta z & c & c' \\ w & \delta w & d & d'\end{pmatrix} \begin{pmatrix} \cos(\phi) & \sin(\phi) & 0 & 0\\ -\sin(\phi) & \cos(\phi) & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix} x & y & z & w\\ \delta x & \delta y & \delta z & \delta w \\ a & b & c & d \\ a' & b' & c' & d'\end{pmatrix}$$

A quick explanation: by fixing the orthonormal basis, we can use it to construct an orthogonal transformation to a coordinate system in which the viewer sits at $(1,0,0,0)$ and is facing in the $(0,1,0,0)$ direction. Then all we need to do is to conjugate back the transportation matrix for that situation. The $\phi$ parameter measures the (angular) distance you travelled on the hypersphere.

-
Note, if you do want a spinning effect, you can replace the identity matrix in the bottom right corner of the center matrix in the last expression with the rotation matrix $[ \cos, \sin; -\sin, \cos]$ acting on some function $f(\phi)$. –  Willie Wong Mar 3 '11 at 10:37
Thank you so much. I am no mathematican, and you clarified many concepts that helped me build my walk ahead matrix based on yours M(ϕ). But more importantly, you helped me grasp many concepts that simply made no sense on those long past linear algebra classes. –  lvella Mar 9 '11 at 4:11