Closed manifolds

This article is about non-standard continuous game spaces. In this article I introduce the notion of a closed manifold and how it allows to design a finite space while avoiding to have a boundary to a world. I also extensively introduce the projective plane, a non-oriented closed manifold. This article is not finished yet, but I post the first part now because it might be quite thick to read at once.

Continuous game spaces

When designing spaces with videos games we have to cope with the world boundaries, the end of the play space. Several solutions have been used to design a continuous play space.

  • Mark boundaries with walls,
  • Generate procedurally an infinite world,
  • Work over a closed manifold.

The former solution can be easily added with invisible walls. But invisible walls are frustrating as it bluntly tells it removed a freedom from the player. Smarter walls can be design to match natural features of the world, like a big fire, a thick formation of people or a cliff. These are used extensively in many games. The drawback is that they require a vast amount of work and a lot of imagination. It is no surprise that walls are more use in AAA games than any other type of game: those studios have a staff large enough to afford it.

The second solution, using procedural generators, sounds like a recent innovation. But it is not. I’m of course speaking about randomly generated dungeons in dungeon-crawler game genre, but not only. This is also the solution behind many games happening on an island like “The Elder Scrolls III: Morrowind” or “GTA: Vice City”. In those games the playground is bounded by the coastline of the island (or a little further) but this boundary is not a wall: you can cross it. When you cross the boundary you wander in procedurally generated ocean that extends to the infinity. The procedure is unsophisticated but effective~: you don’t wander off the island because you are forbidden to, but because there is nothing to see there.

Of course the second solution can be used to generate meaningful content, like it does in “Minecraft”. This is also tricky and requires a lot of tweaking and testing, but possibly less repetitive work for the designer. However beware that what repetitiveness the designer escapes may fall back on the player without some caution. Indeed a random generator that spawns always different but very similar situations is likely to give a single experience over the player.

The last solution is the least common. It consists of using non-natural spaces that do not have any boundary, yet are not infinite in the sense that there is a bound of the distance any two points can have together. This last properties implies that such space do have a finite area in 2D or a finite volume in 3D. The surface of a ball, a sphere, is such an example. The surface of a doughnut, a torus, is another. Such a space is called a closed manifold. In the 2D case, they are also called a closed surface.

Oriented surfaces

What types of closed surfaces exist? It turns out that mathematicians classified closed manifolds, up to reversible deformations. In the 2D case it is pretty straightforward. There is the sphere, over which you can dig a hole and have a torus which in turn you can dig another hole and have a torus with two holes, or 2-torus, and so on.

Image of a torus with two holes, a standard torus and a sphere.

The torus is the most common closed surface used in videos games. Indeed consider the simple 2D world that is made of square and that repeat itself when you reach the boundary of a square, like in the image where each square are copies one of each other.

Image of the polygonal representation of a torus

One copy of the box looks like the rectangle below1.

Image of the polygonal representation of a torus

A side with an arrow is to be glued with the side with the same arrow, keeping the arrows with the same orientation. Gluing sides is equivalent to say “when you go through this side, you go out through this other side”. In the above rectangle, gluing the two horizontal gives a tube. The two circular extremities of the tube have to be glued, which gives a torus.

Image of the rectangle folded almost like a torus

Non-oriented surfaces

The sphere and the tori are nice surfaces but they are not all possible 2D surfaces. There are also the non-oriented surfaces. Oriented surfaces are surfaces such that you can paint one side of the surface in blue and the other in orange without having a boundary between blue and orange paint. A non-oriented surface is a surface that hasn’t this property. If you start painting one side in blue and proceed to paint the whole side, you will eventually paint both sides of each point. The typical example of a non-oriented surface is the Mœbius Strip, below.

Image of a Mœbius strip

This surface has a boundary, so it is not closed. However we can extend it into a closed surface. Notice how the Mœbius strip has only one circular line for boundary. You can see it by following the boundary of the picture above. This is also deducible from the fact that the surface is not orientable. If you travel along the middle of strip and keep track of where the right border is, after some trip you will go back to the same point, but on the other side of the strip. There the left side and the right side will be inversed. Therefore you right side joined the left side.

Now there is a famous surface that also has a single circle as its boundary: I am of course speaking of the disk. So you can theoretically glue the disk with the Mœbius strip along their circular border. Don’t try to do this with paper strips at home: I has been mathematically proven it is impossible to do within a 3D space. But it is theorically possible to do.

Actually we do not really care to embed the Mœbius in a 3D space. We’re interested to designing our 2D world space. So like the torus, let us use a polygonal representation of the projective plane so that by folding sides, it is the surface. First let’s start with the polygonal representation of a Mœbius strip. Side without arrows must not be glued yet: they are the boundary of the Mœbius strip.

Image of the polygonal representation of a Mœbius strip

Now, to have a projective plane, we must join add a simple disk on top of it. The disk does not do really anything except gluing the two sides that were the boundary of the Mœbius strip. We obtain the following polygonal representation.

Image of the polygonal representation of a projective plane

The resultant game space would be the following.

Image of the polygonal representation of a torus

Notice an issue with this representation: arrow of the same side are pointing to (or away) from each other. It means that when reaching the corner of the polygon you will actually see the world mirroring itself horizontally and vertically. This is not desirable.

I will speak of a workaround for this issue in a later post, with something called an atlas. Actually this is all for now I believe the subject can already difficult enough to understand if you have notion in mathematical topology. Besides it is sure long enough to write!

  1. Stretching horizontally is a reversible deformation, so it doesn’t really matter we had a square and now we have a rectangle.

Homogeneous coordinates

In this article I introduce the concept of homogeneous coordinates. Homogeneous is an important tool in computer graphics, to project points from 3D space to screen coordinates. It is also the basis to defined the projective plane a curious surface with many interesting properties.

Quaternions

Anyone who tried a little computer graphics must have come sometime and somehow to the notion of quaternions. What is a quaternion ? The set of quaternions can be view as a 4-dimensional vector space over the reals. But a quaternion itself is a number, like is a real or an integer. One can sum quaternions, negate them, multiply them or invert them and quaternions have an neutral element for both the sum and the product.

Summing quaternions is no surprise since a quaternion number is a also a 4-dimensional vector of real numbers and vector can be summed by definition. More surprising is that quaternions have a product that is associative, has a neutral element and an inverse element for each quaternion but \(0\). This product has a lot of other nice properties, especially when combined with the sum. Every graphic programmer knows it; quaternions allow to easily compute a lot of properties of points in 3D space, by using one single matrix product.

Homogeneous coordinates

The niceness of quaternions happens to be a happenstance. The mathematical concept of using 4-dimensional vectors to represent three dimensions is actually called homogeneous coordinates. By cautiously choosing the axes of the four-dimensional quaternion vector space, the operation of quaternions can correspond to rotations, scalar product or other operators.

Unlike quaternions, homogeneous coordinates are not secluded to 4 dimensions. This means that the framework of homogeneous coordinates, although less powerful, is more general than quaternions. Homogeneous coordinates is the encoding of \(n\)–dimensional spaces using \(n+1\)–dimensional coordinates. The coordinates are encoded such that the \( n\) first values are the regular \( n\)-dimensional vector values but the last value is a value that has to be divided to all previous values in the end. For example \((-4,8,4,2)\) represents the vector \((-2,4,2)\). The power of this representation is its ability to handle infinity, when that last value is \(0\).

An example

Let us take the special case of using 3D coordinates for representing a 2 space. In this 3D vector space let us consider the plane that spans along the \( x\) and \( y\) direction, with a height of 1. In the following image, it is the blue semi-transparent plane while the gray opaque plane is the plane \( xy\)–plane that passes through the origin \( (0,0,0)\). Why am I considering this plane ? Simple: dividing by 1 has no effect so the final 2D vector is obtained by dropping the last value.

Image of an opaque xy-plane of z-value 0, a blue semi-transparent xy-plane of z-value 1 and a line going through the origin and cutting the blue semi-transparent plane a point p.

Let \( v\) be some \( 3\)–dimensional vector. In the above image the \( 4\)–dimensional coordinate that represents \( v\) are the points forming the dashed yellow line. \( p\) is the one such that the last value is \( 1\). So basically all points of the yellow line represents the same \( 3\)–dimensional point. We could say that the \( 4\)–dimensional line is the \( 3\)–dimensional point.

Now what happens if the last value is \( 0\)? Dividing by \( 0\) is forbidden so we actually have new types of point. Such a \( 4\)–dimensional point represents a \( 2\)–dimensional point that doesn’t really exists and we shall call it a point at infinity. Should some of these points represent the same points? Yes, let me show you how.

Let’s take two points from from the yellow dashed line, \( q = (q_x,q_y,q_z,q_w)\) and \( q’ = (q’_x,q’_y,q’_z,q’_w)\). Both of these point correspond to the point \( p\) so that the following formula holds~:

\[ p = (\frac{q_x}{q_w},\frac{q_y}{q_w},\frac{q_z}{q_w},1) = (\frac{q’_x}{q’_w},\frac{q’_y}{q’_w},\frac{q’_z}{q’_w},1)\]

Thus,

\[ q’ = \frac{q’_w}{q_w} q \]

In the end any points \( q\) and \( q’\) such that there is some real number \( \lambda\) such that \( q’ = \lambda \cdot q \) are the homogeneous coordinate of the same point. We should not behave differently with points at infinity. If there is some real number such that multiplying one point by this value gives the other, those points represents the same point at infinity. Since such points always lies on a same line going through the origin \( (0,0,0)\), there is as many point at infinity as there is line going through the origin but parallel to the blue semi-transparent plane.

The space obtained by using all the \( 2\)–dimensional points defined by \( 3\)–dimensional lines, including the points at infinity, is called the projective plane. The name comes by viewing the origin as the focal point of a camera and the blue semi-transparent plane as its screen.