Tetrahedral symmetry

I was curious how one would go about rendering a triangle group using Möbius transforms. It took a while! I wanted to jot down the underlying theory so I wouldn’t forget it later. Perhaps these notes will be of interest to others as well. Here goes:

Given a triangle with angles π/l, π/m, π/n, you can tile a plane if 1/l + 1/m + 1/n = 1. For instance if l,m,n = 2, 4, and 4 respectively, then the sum of the angles of the triangle is π/2 + π/4 + π/4 = π, and you can tile a plane with isosceles right triangles which would look something like this [1]:

A (2,4,4) tiling of the plane.

That’s what a tiling of a Euclidean plane looks like. What does a tiling of a sphere look like?

The sum of the angles of a spherical triangle is always greater than π. There are only a few values for l,m,n that form a pattern covering the sphere just once without any overlaps or gaps. The possible values for (l,m,n) are[2]:

(p p 1), (p 2 2), (3 3 2), (4 3 2), (5 3 2).

The sides of these triangles form great circles or geodesics.

Let’s look in detail at the (3 3 2) tiling. This fundamental region is a triangle with angles: π/3, π/3, π/2. This is another isosceles right triangle. The total sum of the angles is 7π/6. The area of a single triangle (for sphere radius = 1) is π/6. Since the total area of the unit sphere is 4π, it will take 24 of our triangles to the tile the sphere. If we did so, we’d get a result like this:

A (2,3,3) tiling of the plane.

There are 6 points where 4 vertices (each of angle π/2) meet, and 8 points where 6 vertices (each of angle π/3) meet. The symmetries consist of rotations and reflections.

Rotations: there are 3 axes with order 2 rotation and 4 axes with order 3 rotation (antipodal points share an axis). And we count the identity (no rotation) as one of the rotations. So altogether:

  • 1 identity rotation (no rotation)
  • 4×2 rotations, (not 4×3 since we don’t want to double count the identity),
  • 3×1 rotations, (not 3×2 since we don’t want to double count the identity),

1 + 4×2 + 3×1 = 12 rotational symmetries altogether.

Reflections: The illustration immediately below shows 3 possible reflection planes for our tiling. But this is not all of the possible planes of reflection of course. Each plane in the illustration corresponds to one of the great circles (aka geodesics) traced out by the sides of the triangles: each such great circle is a plane of rotation. There are 6 of these great circles in this tiling. To these 6 reflections are added 6 so-called roto-reflections, in which, using the same 6 planes, a rotation by π is followed by a reflection.

3 of the 12 possible reflection symmetry planes for the (3,2,2) triangle tiling.

The group of 12 rotations and 12 reflections corresponds to the group S4, which is of order 4! = 24.

So what about tetrahedrons? At some point this article has to mention tetrahedrons, given the title.

Wikipedia says: “A regular tetrahedron has 12 rotational (or orientation-preserving) symmetries, and a symmetry order of 24 including transformations that combine a reflection and a rotation.

The group of all symmetries is isomorphic to the group S4, the symmetric group of permutations of four objects, since there is exactly one such symmetry for each permutation of the vertices of the tetrahedron.

And indeed the following diagram also from wikipedia [4] shows that the rotations and reflections of a tetrahedron correspond exactly to those of the (3,3,2) triangle group that we have been working with.

The proper rotations, (order-3 rotation on a vertex and face, and order-2 on two edges) and reflection plane (through two faces and one edge) in the symmetry group of the regular tetrahedron.

This tetrahedral group “arises if we inscribe a regular tetrahedron in a sphere and mark its vertices together with the projections of the centers of the faces and the midpoints of the edges on the the sphere, the center of projection being the center of the sphere.”[3] That article goes on to say that the defining relations of the group are:

L²=M²=N²=1,  (LM)³=(MN)³=(NL)²=1

where L, M, N are the reflections in the side of the (3,3,2) triangle.

So to summarize, there are 24 symmetries of the (3,3,2) triangle group and these consist of 12 rotations and 12 reflections.

Now, rotations are orientation-preserving transformations, whereas reflections are orientation-reversing motions. Triangle groups are not examples of Keinian groups. Kleinian groups are groups of möbius transformations, which are orientation-preserving.[5]

Triangle groups were studied first in the 19th century and the study of Kleinian groups and eventually hyperbolic geometry grew out of those foundations. So lets pursue this analysis into the world of Kleinian groups.

Every group of motions, which is generated by reflections has a subgroup of index two. This subgroup consists of directly conformal motions, that is of, möbius transformations.“[5]

If we throw out the reflections, we are left with a set of 12 rotations. This subgroup is isomorphic with A4, the alternating group of permutations of four symbols. Wikipedia says: “The set of orientation-preserving symmetries forms a group referred to as the alternating subgroup A4 of S4″.

Generators for A4 satisfy these relations:

u³ = v³ = (uv)² = I

We can generate A4 with two three-cycles [6]:

U = (123), and V=(124).

It is interesting to work out all the permutations of these generators and see that there are indeed only 12 of them:

Generators Result Already Seen?
I 1234
U 2314
V 2431
UU 3124
UV 4321
VU 3412
VV 4132
UUU 1234 I
UUV 3241
UVU 4132 VV
UVV 1342
VUU 1423
VUV 3124 UU
VVU 4213
VVV 1234 I
UVVU 2143
UVVV UI=U
VUUU VI=V
VUUV 2143 UVVU
VUVU 1234 (VU)^2=I
VUVV 3241 UUV
VVUU 4321 UV
VVUV 1423 VUU
VVVU IU=U
VVVV IV=V

So the set of generators we can use for A4 are: I, U, V, UU, UV, VU, VV, UUV, VVU, UVV, VUU, UVVU.

Nomenclature seems inconsistent across writers, but lets call the tetrahedral group that is isomorphic with S4, T*(3,3,2). And the tetrahedral group that is isomorphic with A4, we’ll call T(3,3,2). As above, the defining relations of T(3,3,2) are

u³ = v³ = (uv)² = 1,

where u = LM and v = MN and  L, M, N are the reflections in the side of the (2,3,3) triangle [3].

From [3], we get some sample values for U and V:

Finding an appropriate fundamental domain was not easy, but a triangle with vertices at these corners works:
[0, -x + xi, x+xi]
where x= -0.366025393.

In spherical coordinates (phi, theta) these corners correspond to:

[(0,0), (-PI/4,len), (+PI/4,len)]
where len = acos((cos(PI/3.)+cos(PI/3.)*cos(PI/2.))/(sin(PI/3.)*sin(PI/2.))) = 0.955316618 rad.

Given this fundamental domain and the list of generators above, we can finally tile the Riemann Sphere with (2,3,3) tirangles using Möbius transformations! The fact that we are using only the orientation preserving symmetries means we get a triangle tiling that covers half of the sphere and leaves empty space elsewhere:

3,3,2 Triangle tiling on the Riemann Sphere, as well as an equirectangular projection of same. Rotated using Möbius transformations. You can explore it further here.

So to summarize, the triangle tiling was formed by repeatedly applying the 2 Möbius transformations to the given fundamental domain in the 12 combinations indicated by A4 symmetry. Implementation note: we are rotating this sphere not by rotating the camera or the mesh, but again by applying Möbius transformations to the texture as discussed in this article, which is why the equirectangular projection to the right in the picture above is morphing in that weird way.


Addendum 1: Conjugacy Classes of A4

There are 4 conjugacy classes of A4:
1. One class containing the identity.
2. One class containing the three 180 degree rotations through opposite edges.
3. One class for the four forward rotations of π/3 around each corner.
4. One class for the four reverse rotations of  π/3 around each corner.
Note that classes 3 and 4 are merged in S4 but disjoint in A4 because A4 does not have a reflection.[8]

If the identity is { 1, 2, 3, 4},
Class 2 consists of these permutations:
{ (2 1 4 3), (3 4 1 2), (4 3 2 1) }
Class 3 consists of these permutations:
{ (2 3 1 4), (1 4 2 3), (3 2 4 1), (4 1 3 2) }
Class 4 consists of these permutations:
{ (3 1 2 4), (1 3 4 2), (4 2 1 3), (2 4 3 1) }
To visualize this, label the vertices of the tetrahedron 1,2,3 and 4 in any order. Then the numbers listed in the conjugacy class are the permutations of the vertices for that class.

You could also label the permutations using our generators:
The identity is I,
Class 2 consists of these permutations:

{ UVVU, VU, UV }

Class 3 consists of these permutations:

{ U, VUU, UUV, VV}

Class 4 consists of these permutations:

{ UU, UVV, VVU, V }

 

Note, the transformation of U is a rotation around vertex 4 and the V transformation is a rotation around vertex 3.

 


Addendum 2:

In the first chapter of the book Finite Möbius Groups, Minimal Immersions of Spheres, and Moduli, Gabor Toth works out a set of Möbius transforms corresponding to all 3 polyhedral symmetry groups. These are different from the ones I used above. Here I apply his tetrahedral rotations to a so-called 360 photo (taken on a Ricoh Theta):

And just for kicks, here is the same process applied to another photo using his octahedral symmetries:

Octahedral symmetries are double those of the tetrahedron which makes intuitive sense when you consider that you can fit 2 tetrahedrons in a cube, e.g. [7]:


[1] https://commons.wikimedia.org/wiki/File:Tile_V488_bicolor.svg#/media/File:Tile_V488_bicolor.svg

[2] Coxeter, H. S. M. (1974) Regular Complex Polytopes, Cambridge Unitvesity Press, London. Page 19.

[3] Noneuclidean Tesselations and Their Groups. Academic Press, Oct 18, 1974. Page 73 on.

[4] By I, Cronholm144, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=2295116

[5] Geometry of Group Representations: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference Held July 5-11, 1987 with Support from the National Science Foundation. William Mark Goldman, Andy R. Magid. American Mathematical Soc., 1988 – Mathematics. Page 4.

[6] http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf

[7] By Steelpillow (Own work) [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

[8] http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/conjclass.pdf

 

Congruence Group Γ(2)

Modular Group Γ(1) generated the hyperbolic tessellations seen previously. Its generators are:

S: z\mapsto -1/z

T: z\mapsto z+1

Or in matrix form:  [0,1;-1,0], [1,1;1,0].

The Congruence Group Γ(2) can be generated by these matrices:

[1,2;0,1], [1,0;-2,1]

The tiling looks like this:

You can view a version I wrote in Three.js/WebGl here. You can spin it and pan and zoom. It is clear in this version that the tessellation lives on the upper-half plane of the Reimann sphere.

As before the orange region is the fundamental domain. It and all of the tiles are 4 sided and touch the rim at 4 points. Here is another representation of the fundamental domain from Wolfram Alpha[1]:

The 4 corners of this fundamental domain are -1, 0, 1, and ∞. The red letters indicate the effect of the initial tiling of 1 letter words (e.g. T, T¯¹, S, S¯¹). These areas correspond to the yellow quadrilaterals in the tiling above.

The imaginary axis cutting the fundamental domain in two is an additional axis of symmetry we could impose on the tiling. Then it would look just like the Farey graph depicted in the previous post and the disk would be tiled by ideal triangles. Ideal triangles in hyperbolic space have interesting properties (to quote wikipedia)[3]:

  • All ideal triangles are congruent to each other.
  • The interior angles of an ideal triangle are all zero.
  • An ideal triangle has infinite perimeter.
  • An ideal triangle is the largest possible triangle in hyperbolic geometry.

The Modular Necklace

If you have read the book “Indra’s Pearls” you will be familiar with a similar tiling which they describe as “The modular necklace”:

“A modular necklace is a tangent chain of four circles in which adjacent disks are paired by two transformations a and b… The transformations a, b, and ab are all parabolic and S = Fix(a), Q = Fix(b), a(P)=R, b(R) = P so that P = Fix(ba) and R = Fix(ab)… The four points P, Q, R and S always lie on a circle (or line) which is the limit set of the group. The limit circle is perpendicular to all circles in the chain. Both inner and outer tiles have their sides matched in the same way and the surfaces made by gluing up these tiles are each spheres with three punctures or cusps.”[2]

Following their naming, P, Q, R and S are the tangency points of the four circles a, A, b, andwhich are positioned where the letters T, T¯¹, S, S¯¹ are in the diagram above, respectively. The möbius transform corresponds to T and the möbius transform b corresponds to S.

If we look at the tiling this way, then it makes no sense to restrict ourself to the upper half plane and the limit set is very clear:

Another point of view on the same tiling:

 


[1] Weisstein, Eric W. “Modular Group Lambda.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/ModularGroupLambda.html

[2] “Indra’s Pearls: The Vision of Felix Klein”. By David Mumford, Caroline Series, David Wright. Page 214.

[3] https://en.wikipedia.org/wiki/Ideal_triangle

 

Ford Circles and Farey Graphs

Here is an image of a tessellation or tiling of the upper half-plane. Under some group of symmetries, an initial triangle (for instance the one in orange) covers the plane without overlaps. (The initial triangle is not ideal because only one of its angles is 0). The group of symmetries used are those of the modular group. See my previous post where I go into this in greater detail.

Tessellation of the upper half plane using the symmetries of the Modular Group.

Note that each triangle has a vertex on the rim of the circle. The rim of the circle is the real projective number line.

The orange initial triangle, aka the fundamental domain, is touching the real number line at the point of infinity. The green triangle right below the orange triangle touches the real number line at the point 0. The green triangle = S(orange triangle), where S -> -1/z. Every other vertex touching the rim of the disc can be obtained by applying some combination of S and T. (T->z+1).

Ford Circles

Lets start with 2 circles, one with a radius=1 touching at 0. Another is a line, Im(z) = 1 (a circle with an infinite radius that is). These are the 2 large circles in the picture below. If we then apply S and T repeatedly we get the Ford circles.

The set of points where the circles touch the real number line is the set of rational numbers, Q. This is the same set of points where the vertexes of the tessellated initial triangles touch the rim.

From [4], I learned the following interesting facts:

  1. The circle touching the real axis at the reduced fraction a/c has radius 1/2c². This  explains why the circles for reduced fraction a/c and a’/c have the same radius.
  2. The circles touching z = a/c and z = b/d > a/c are tangential to each other because ad − bc = 1. Such circles are images of the 2 initial circles touching z = 0 and z = ∞ under SL(2, Z) (determinant = 1).
  3. The circle between these tangential circles touches at (a+b)/(c+d). Because the latter circle is the image of the circle between the circles touching z = 0 and z = ∞, namely the circle touching z = 1, under

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

The formula (a+b)/(c+d) is the formula for calculating a mediant between 2 Farey neighborsa/b and c/d.

Ford Circles

 

“The Farey graph is the PSL(2,Z) images of the imaginary axis, and so contains all of Q* as its points at infinity. It is not hard to see that p/q and r/s are connected by an edge iff ps-qr = +/-1, so it is in some sense a geometric recording of the matrix group.” [1]

Here the images of the imaginary axis are highlighted and the Farey graph is evident:

Farey Graph


[1] http://mduchin.math.tufts.edu/notes/hyp-groups-course.pdf

[2] “Indra’s Pearls”, pages 210-213.

[3] http://homepages.warwick.ac.uk/~masbb/HypGeomandCntdFractions-2.pdf

[4] http://www.maths.ed.ac.uk/~aar/Whittaker2012A

 

Tessellation of the Hyperbolic Plane on the Riemann Sphere

I’m interested in learning more about the modular group and this article looking into hyperbolic tessellations represents my initial efforts to collect my thoughts on the topic.

We are familiar with hyperbolic tessellations from the artwork of M.C. Escher and from numerous renderings of the Poincare Disk (which was really invented by Beltrami, not Poincaré):

 

 

The disk model is not the only model of hyperbolic space. There is also the Klein model, the hyperboloid model, and the upper half plane model, and probably some others. Let’s consider the upper half plane model. One way to look at the Poincaré half plane model is as a view on that part of complex plane where the imaginary part is positive. So we’re only considering half of the complex plane, the upper half. Here is what a tiling of the upper half plane looks like:

 

 

By Fropuff (from en wikipedia) [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], via Wikimedia Commons

 

To quote wikipedia: “The projective linear group PGL(2,C) acts on the Riemann sphere by the Möbius transformations. The subgroup that maps the upper half-plane, H, onto itself is PSL(2,R)”. So Möbius transformations with real coefficients preserve the upper half-plane. That means that any such transformation will keep all points that are already on the upper half-plane on the upper half plane. (And incidentally, the real numbers are mapped to themselves).

If we look at the upper half plane model this way (as the upper half of the complex plane), then when we render it on the Riemann Sphere, it looks like this:

In this depiction, the tiled portion is the upper half plane. The red hemisphere is not the upper half plane, it is the lower half plane. The green axis points to (∞, ∞i), the blue axis intercepts the sphere at (-1,0i) and the red axis intercepts the sphere at (0,-i).

The tessellation depicted above is of the modular group, PSL(2,Z), where Z indicates the set of integers. So in other words the modular group Γ is those mobius transformations with integer coefficients and unit determinant. It is a subgroup of PSL(2,R) (but not a normal subgroup).

To quote wikipedia again:

“The modular group can be shown to be generated by the two transformations

    S: z -> -1/z
    T: z -> z + 1

so that every element in the modular group can be represented (in a non-unique way) by the composition of powers of S and T. Geometrically, S represents inversion in the unit circle followed by reflection with respect to the imaginary axis, while T represents a unit translation to the right.” z is a complex number of course. And as mentioned above, S and T are Möbius transforms with integer coefficients and determinant = 1.

So we can use those 2 transformations and apply them over and over. What region should we start with as our initial tile (or to use the technical terminology: what fundamental domain should we choose?). A common choice is depicted in the grey region in the upper half plane figure above. It is that region where |z| is > 1 and |Re(z)| < 1/2. The orange triangle in the spherical tiling above is the very same region.

You can view my Three.js version of this tessellation here where you can spin and zoom it as you please.

Note that we are drawing this diagram using WebGL shaders. Pixel shaders (aka fragment shaders) are called once for each pixel. In our case a pixel maps to a complex coordinate. So our code is called repeatedly and handed a different complex coordinate on each call. The pixel shader has to decide what color to use for this given pixel/complex coordinate. So it has to do the Möbius transforms in reverse. (I discuss this issue in greater detail here). This shows how the tesselation works [3]:

Thus, in code, the logic is:

 if |z| < 1 then apply S-1 else if Re(z) < -.5 apply T, else T-1

 

(remember we’re doing everything backwards because we’re working with pixel shaders).

By a suitable placement of the camera you can get a view that looks just like the Poincaré disk:

This provides an intuition for believing that there is a simple mapping from the upper half plane model to the disk model, and indeed there is, it is called the Cayley transform.

 

Rational Numbers, Q

In case it wasn’t clear, the rim of the upper half plane is the real line, or the projective real line (the real line plus a point at infinity) to be precise. A cool thing about the modular group is that each point where a tessellation intersects the real line is a rational number. That makes sense because any combinations of powers of S and T can only generate a rational number.

In other words, the points where the tessellations of the fundamental domain hit the boundary are those points s ∈ R ∪ {∞} that are fixed by a parabolic element of Γ. The points are precisely Q ∪ {∞}, where Q stands for the set of rational numbers. The parabolic element is the transform T above. You can tell it is parabolic because the Trace of the 2×2 matrix corresponding to the Möbius transform for T is 2.

For z ∈ SL2(R), z is parabolic if z can be conjugated to T . Any parabolic element z generates an infinite discrete subgroup of SL2(R) consisting solely of parabolic elements; and z fixes no points of H and a unique point of P1(R). The parabolic points for SL2(Z) are P1(Q). [4]

The fundamental domain in orange above has one point on the real axis. Each transformation in the tessellation moves that point around the rim and generates a new rational number.

Hyperbolic Tesselations

So what does this have to do with hyperbolic tesselations? We’ve explained how a special set of Möbius transformations, those that generate the modular group, can tile the upper half plane. The upper half plane is a model of hyperbolic geometry. This was the famous insight that came to Poincaré in a flash:

“At that moment which I put my foot on the step the idea came to me, without anything in my former thoughts seeming to have paved the way for it, that the transformations I had used to define the Fuscian functions were identical with those of non-Euclidean geometry” L’Invention Mathématique, Henri Poincaré

Or as wikipedia says: “Möbius transformations are also isometries of the hyperbolic plane“. This seems a strange statement. Möbius transformations are conformal on the complex plane: they preserve angles, but the don’t preserve lengths. Isometry means ‘length preserving’. This is possible because in hyperbolic space, in marked contrast to Euclidean space, equal angles guarantee that corresponding side lengths are equal in the hyperbolic metric.[1] A hyperbolic triangle’s size is determined by its angles.

Algebraic vs Geometric

The matrices [0,1,-1,0] and [1,1,1,0] generate SL(2Z). Both matrices have determinant = 1. That means they are volume and orientation preserving.

The analogous Möbius transforms:

    S: z -> -1/z
    T: z -> z + 1
generate the modular group. They are not volume preserving in the upper half plane but they are in the hyperbolic plane: all tiles are the same size in the hyperbolic plane.

And finally….

As a final note, since we’re working with the Riemann sphere we can do all sorts of fun mappings from 360 video footage, as I detailed elsewhere. So piping video through the tessellation gives you:

 

Video 5 from Robert Woodley on Vimeo.

.

—————-

[1] http://www.mathematica-journal.com/issue/v9i3/contents/ModularGroup/ModularGroup.pdf

[2] https://math.dartmouth.edu/~m125x15/quat-book-chap29-072315.pdf

[3] http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/SL(2,Z).pdf

[4] https://homepages.warwick.ac.uk/~masiao/modforms/examples2.pdf

[5] http://www.math.cornell.edu/~hatcher/TN/TNch1.pdf

 

Crib Sheet on Mathematical Groups

This is just a bunch of quotes I’ve pulled off of Wikipedia and elsewhere. I tried to get a handle on some of the basic groups used in hyperbolic tilings and complex analysis.
——————–
In mathematics, the general linear group of degree n is the set of n×n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, and the inverse of an invertible matrix is invertible. The group is so named because the columns of an invertible matrix are linearly independent, hence the vectors/points they define are in general linear position, and matrices in the general linear group take points in general linear position to points in general linear position.
To be more precise, it is necessary to specify what kind of objects may appear in the entries of the matrix. For example, the general linear group over R (the set of real numbers) is the group of n×n invertible matrices of real numbers, and is denoted by GLn(R) or GL(nR).
———————-
The special linear group, written SL(nF) or SLn(F), is the subgroup of GL(nF) consisting of matrices with a determinant of 1, with the group operations of ordinary matrix multiplication and matrix inversion. Matrices of this type form a group since the determinant of the product of two matrices is the product of the determinants of each matrix. The special linear group SL(nR) can be characterized as the group of volume and orientation preserving linear transformations of Rn; this corresponds to the interpretation of the determinant as measuring change in volume and orientation.
———————–
the special linear group SL(2,R) or SL2(R) is the group of 2 × 2 real matrices with determinant one. SL(2,R) acts on the complex upper half-plane by fractional linear transformations
———————–
There is an action of SL(2,R) on C, which takes R U ∞ to itself and stabilizes the upper and lower half-planes. Intuition: It takes R to itself because the entries are real.  R U ∞ is the boundary of the upper half-plane. The transformation is orientation preserving; as you progress along the real line in the positive direction, the upper half-plane is on your left. This relationship is preserved by any Möbius transformation. So we require that the real line is not only mapped to itself, but it is mapped to itself in the same direction.
———————
PGL(2,R) takes the real line to itself.
PSL(2,R) takes the upper-half plane to itself.
[4]
———————
The Möbius transformations are the projective transformations of the complex projective line. They form a group called the Möbius group, which is the projective linear group PGL(2,C).
The Möbius group PGL(2,C) consists of 2×2 matrices with non-zero determinant: Möbius transformations are defined on the extended complex plane, C*. Stereographic projection identifies C* with a sphere, which is then called the Riemann sphere; alternatively, C*  can be thought of as the complex projective line CP1. The Möbius transformations are exactly the bijective conformal maps from the Riemann sphere to itself, i.e., the automorphisms of the Riemann sphere as a complex manifold; alternatively, they are the automorphisms of CP1 as an algebraic variety. Therefore, the set of all Möbius transformations forms a group under composition. This group is called the Möbius group, and is sometimes denoted, Aut(C*).
The Möbius group is isomorphic to the group of orientation-preserving isometries of hyperbolic 3-space and therefore plays an important role when studying hyperbolic 3-manifolds.
————
From [2]:
We already know that S² is the same object as CP¹. The result should be understood as follows. Consider CP¹ made out of equivalence classes [z0:z1]=c[z0:z1]. This means that each equivalent class is characterized by a nonzero complex number c which we shall consider as a point (kind of a coordinate) in CP¹. Thus there is a one-to-one correspondence between points in CP¹ and lines in C².
Thurston [1] continues:
The complex plane embeds naturally in the complex projective line CP¹, the set of complex lines (one-dimensional subspaces) of CP¹. The embedding maps a point z in C to the complex line spanned by (z, 1), seen as a point in CP¹; we call z the inhomogeneous coordinate for this point, while any pair (tz, t) in , with t in C*=C\{0}, is called a set of homogeneous coordinates for it.
Two non-singular linear maps of  give the same projective transformation of CP¹ if and only if one is a scalar multiple of the other. Thus, identifying together scalar multiples in the linear group GL(2,C) give the group of projective transformations of CP¹ which we naturally denote by PGL(2,C) = GL(2,C)/C*. This group is also known as PSL(2,C), because it can be obtained by identifying together scalar multiples in the special linear group SL(2,C), consisting of linear transformations of  with unit determinant.
A Möbius transformation of S^n-1 can be extended to a unique isometry of H^n. Since PGL(2,C) actor on S² by  Möbius transformations, this action can be extended to all of H³… The group of orientation-preserving isometries of H³ is PGL(2,C), identified via the action on S²=CP¹.
————
Kleinian Group – is a discrete subgroup of PSL(2, C). (Note that PSL(2,C) ≅ PGL(2,C) but PSL(2,R) is not ≅ to PGL(2,R). I’m not sure why. Thurston mentions it above and there are articles in math overflow about it). Discreteness implies points in B3 have finite stabilizers, and discrete orbits under the group G. But the orbit Gp of a point p will typically accumulate on the boundary of the closed ballB3.
Let T be a periodictessellation of hyperbolic 3-space. The group of symmetries of the tessellation is a Kleinian group
————-
Fuchsian Group – Any Fuchsian group (a discrete subgroup of SL(2, R)) is a Kleinian group, and conversely any Kleinian group preserving the real line (in its action on the Riemann sphere) is a Fuchsian group. More generally, any Kleinian group preserving a circle or straight line in the Riemann sphere is conjugate to a Fuchsian group. “Indra’s Pearls” says that any group which can be conjugated to a group meeting the above requirements is also a Fuschian group, which seems reasonable. In other words, the traces of Fuscian matrices must be real; traces don’t change under conjugation.
A quasi-Fuchsian group is a Kleinian group whose limit set is contained in an invariant Jordan curve. In other words the limit set divides the ordinary set into an inside and an outside. The limit set can be crinkly. The special case when the Jordan curve is a circle or line is called a Fuchsian group.
————-
The modular group is the projective special linear group PSL(2,Z) of 2 x 2 matrices with integer coefficients and unit determinant. It acts on the upper half of the complex plane because Z is real. Some authors define the modular group to be PSL(2, Z), and still others define the modular group to be the larger group SL(2, Z).
It is a subgroup of PSL(2,R) and therefore the modular group is a subgroup of the group of orientation-preserving isometries of (the upper half plane).
Note that any member of the modular group maps the projectively extended real line one-to-one to itself, and furthermore bijectively maps the projectively extended rational line (the rationals with infinity) to itself, the irrationals to the irrationals, the transcendental numbers to the transcendental numbers, the non-real numbers to the non-real numbers, the upper half-plane to the upper half-plane, et cetera.
The modular group can be shown to be generated by the two transformations:
S: z -> -1/z
T: z -> z + 1
so that every element in the modular group can be represented (in a non-unique way) by the composition of powers of S and T. Geometrically, S represents inversion in the unit circle followed by reflection with respect to the imaginary axis, while T represents a unit translation to the right.

The matrices [0,1,-1,0] and [1,1,1,0] generate SL(2Z). Both matrices have determinant = 1. That means they are volume and orientation preserving.

The analogous Möbius transforms:

    S: z -> -1/z
    T: z -> z + 1
generate the modular group. They are not volume preserving in the upper half plane but they are in the hyperbolic plane: all tiles are the same size in the hyperbolic plane.
—————

Γ(N) is a normal subgroup of the modular group Γ. The group Γ(N) is given as the set of all modular transformations

 z\mapsto\frac{az+b}{cz+d}

for which ad ≡ ±1 (mod N) and bc ≡ 0 (mod N).

The principal congruence subgroup of level 2, Γ(2), is also called the modular group Λ. Since PSL(2, Z/2Z) is isomorphic to S3, Λ is a subgroup of index 6. The group Λ consists of all modular transformations for which a and d are odd and b and c are even.

The subgroups \Gamma _{0}(n), sometimes called the Hecke congruence subgroup of level n, is defined as the preimage by  \pi _{n} of the group of upper triangular matrices. That is,

 {\displaystyle \Gamma _{0}(n)=\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\in \Gamma :c\equiv 0{\pmod {n}}\right\}}.

The subgroups {\displaystyle \Gamma _{1}(n)} are the preimage of the subgroup of unipotent matrices:

 {\displaystyle \Gamma _{1}(n)=\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\in \Gamma :a,d\equiv 1{\pmod {n}},c\equiv 0{\pmod {n}}\right\}}

The theta subgroup  \Lambda is the congruence subgroup of  \Gamma defined as the preimage of the cyclic group of order two generated by {\displaystyle {\bigl (}{}_{1}^{0}\,{}_{0}^{-1}{\bigr )}} in  {\displaystyle \mathrm {SL} _{2}(\mathbb {Z} /2\mathbb {Z} )}. It is of index 3 and is explicitly described by:[2]

{\displaystyle \Lambda =\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\in \Gamma :ac\equiv 0{\pmod {n}},bd\equiv 0{\pmod {n}}\right\}}.

It is also called the Modular Group Lambda. It is the set of transforms where a and d are odd and b and c are even. Same as above.


The group of 2 by 2 matrices with determinant 1, SL2(Z) acts on the upper half complex plane:

[a,b;c,d]z -> (az+b)/(cz+d)
The triangles drawn by this program are Fundamental domains for SL2(Z). These triangles are used to construct the Fundamental domains for other subgroups of SL2(Z). For this nomenclature:

Gamma_0(N), Gamma_1(N), Gamma(N), Gamma^1(N) and Gamma^0(N),
where N is a positive integer. These subgroups consist of matrices in SL2(Z) of the following forms respectively:

[a,b;Nc,d], , [Na+1,Nb;Nc,Nd+1], [Na+1,Nb;Nc+1,d] and [a,Nb;c,d].
Here a,b,c,d are integers.

from [3]

 


SU(2) is the group of unit quaternions. They can be used to define regular polyhedra. A M ̈obius transformation is an isometry of the Riemann sphere (for the chordal metric) if, and only if, it is represented by a 2×2 matrix that is a member of SU(2). This chordal metric is nothing more than the Euclidean metric between the two points that z1 and z2 are mapped to on the unit sphere by stereographic projection.
——————–
[1] Three-Dimensional Geometry and Topology. William P. Thurston. Pages 98-99.
[2] Applications of Contact Geometry and Topology in Physics
By Arkady L Kholodenko, page 360.
[3] http://wstein.org/Tables/fundomain/index2.html
[4] Complex Functions. Gareth Jones & David Singerman. Page 31.
 

Möbius Transformations on Spherical Photos and Videos

Spherical Video presents some interesting challenges, for instance, how do you zoom? Or how do you rotate on any arbitrary axis? As the mathematician Henry Segerman pointed out in a post for EleVR, you can achieve both of the above using Möbius transformations. The transformations are conformal (they preserve angles), and they map circles to circles (considering a line to be a circle of infinite radius). Professor Segerman’s work is the inspiration for the project I am describing here.

I wrote an implementation using Möbius transformations to manipulate spherical images in WebGL/Three.js. The implementation is here. Click on the ‘?’ for help or watch this video.

So what is going on here?

The mathematical procedure:

Spherical cameras such as the Ricoh Theta save images in an equirectangular format. This is then wrapped around a sphere to give the spherical effect. (With three.js you create a material whose texture is the saved image from the Theta and then create a mesh using this material and a sphere geometry.) The X and Y of the equirectangular format map to the longitude and latitude of the sphere.

The Riemann sphere is a representation of the complex plane as a sphere using reverse stereographic projection. Möbius transformations are transformations of the complex plane. Our three.js sphere is a normal sphere in 3-d cartesian space (R3); each point on its surface has an (x,y,z) coordinate where x, y and z are real numbers. We can convert our x,y,z point to a point in the complex plane if we take our sphere to be a Riemann sphere. Or in jargon we can say equivalently:  P¹(C) is diffeomorphic to the sphere S². The formulas are here (and elsewhere).

So for instance the south pole is (0,0,-1) in cartesian/R3 space and (0,0i) in complex space. The north pole is (0,0,1) in cartesian space/R3 and (∞, ∞i) in complex space. (The Reimann sphere is really the complex plane plus one point which is the point at the north pole, but I digress).

The technical procedure:

To implement our transformations, we are going to move pixels around on the texture. We can only do this in the shader since doing it in javascript would be way to slow. Specifically we are going to do it in the fragment shader. Our vertex shader will be short and boring, doing only what is necessary to build the sphere’s vertices. Nothing special there. The fragment shader is where the work is done.

The fragment shader is called when the graphics layer needs to know what color to put at a given UV coordinate. We will pluck that pixel from our transformed texture. The steps to execute on each call to the fragment shader are:

1 – Get the UV coordinates. ‘UV’ is industry nomenclature for the X and Y coordinates of the texture that the graphics layer is trying to draw.

2 – We know that the rectangular texture must map to a sphere. The top of the rectangle maps to the north pole, the bottom to the south pole. So we can calculate the X, Y, and Z coordinate of the sphere corresponding to the UV coordinate. That is, we know which point of the sphere we are drawing.

3 – This sphere is also a Riemann sphere as mentioned above, so we calculate the point (a + bi) on the complex plane corresponding to the cartesian point (X,Y,Z) on the sphere, using the formulas mentioned above.

4 – We now know our location on the complex plane and we apply as many transformations as we’d like. When we are done we have our new complex point (c + di).

5 – We reverse the above steps and calculate the cartesian X,Y,Z corresponding to (c + di). Then we calculate the UV corresponding to this X,Y,Z and we use the color at that pixel, UV.

The only Möbius transformations I’ve implemented for now are those to do rotation and zoom. By default the fixed points are antipodal though you can explicitly set the fixed points using the Epsilon 1 and Epsilon 2 buttons. The video linked to above gives a good overview of what all the different buttons do.

This is a rotation around 2 non-antipodal fixed points:

screen-shot-2016-09-12-at-11-00-57-pm-2

In addition to Möbius transforms to do rotation and zoom, there are some other complex transformation options.

screen-shot-2016-09-12-at-11-02-36-pm-2

You may have noticed that we start with the point on the complex plane (a + bi) for which we need a pixel. We then transform (a + bi) into (c + di) to get the pixel we will draw. Thus the transformation is really a reverse transformation.

Infinities of volleyball players on North Avenue Beach (Works at 60FPS on video!):
screen-shot-2016-09-12-at-11-46-17-pm-2

This article by Henry Segerman gives a comprehensive overview of the math behind these transformations and includes more examples of other transformations you can do.

 

Thought Bubbles

A window is a two-dimensional hole in a two-dimensional plane that allows you to see into a three-dimensional world. So what if we could make three-dimensional holes?

The original idea came from a three.js demo by altered qualia where he was demo’ing fresnel shaders:

I didn’t care much about fresnel shaders, but was intrigued by the bubbles. I realized that rendering the outer sphere was not needed to render the bubbles:

These bubbles are three-dimensional windows that can be taken anywhere. Spherical holograms.



To render the above image, you need 2 cameras, each one looking at a separate texture. Now look at this next image. If we flood Michigan avenue we need 2 cameras as well, one for the surrounding sphere, and one to capture the reflection as well.

We can view the scene of a flooded Michigan Avenue at home, via one of our holo-bubbles from above. The camera count is now 3, and you have to deal with the fact that while you want them all to turn in sync, some will need to be more wider angle than others.



We can make the inner camera have such a wide angle that it captures the zenith and the nadir, and the cursor both zooms and moves in space. It is a very sensitive. (Try it!).



This final image is one of the strangest I’ve made to date. Only one camera, with the sphere in the middle seemingly refracting the surroundings but even though the image is in the sphere is reversed it tracks the outer image as they rotate. How is this possible?


Most of the above images can and should be clicked to see the rendering in WebGL.

 

Complex Surfaces

I wrote a separate version of formula toy that handles complex functions. So, you can type in a function like: f=sqrt(g). Both f and g are expected to be complex functions:

    g = u + iv

and

    f = w + ix

where u is the real component of g, v is the imaginary component of g, etc.

To draw this surface we need 4 axes, so formula toy uses a color gradient for the 4th axis. We name these as follows:
– fR – the real component of f.
– fI – the imaginary component of f.
– gR – the real component of g.
– gI – the imaginary component of g.

And you can choose which complex axis maps to which cartesian axis.

29

f=sqrt(g)

This flexible way of doing the mappings allows for simple multi-valued functions/Riemann surfaces:

30

f=log(g)

32

f=atan(g)

31

Lambert W function

Click on the images to open the surface in formula toy. More details here.

 

 

Torus Knots

Formula Toy is a simple and free WebGL app I wrote that allows you to enter in 3-d formulas and see the resulting surface. Sort of like Desmos, but for 3D.

When I first wrote it you could express your formulas in 3 different coordinate systems: cartesian, spherical (polar), and cylindrical. I recently add toroidal which is not very useful except for drawing toruses:

     radius=.5+sin(phi)/(15)*3

torus

AND I added parametric surfaces. If you choose this option, the system is expecting formulas for X, Y, and Z. You are given U and V. For instance a helix could be expressed as:

u=u*(2*pi);
v=v*(6*pi);
x=u*cos(v);
y=u*sin(v);
z=v;

helix

Parametric equations that are functions of a single variable (t) instead of 2 variables (u,v), don’t display because they have zero thickness. For instance the parametric formula for a trefoil knot is a function of 1 variable. To make this visible in formula toy, you need a tube geometry so that the knot doesn’t have zero thickness/volume. Three.js offers a tube geometry but you can also achieve the same effect using the parametric geometry, but with a little extra math. We can start with a torus, and make that our ‘tube’ that will be bent into a trefoil. Here is the parametric formula for a torus:

u=u*(2*pi);
v=v*(2*pi);
x=(4+cos(v))*cos(u);
y=(4+cos(v))*sin(u);
z=sin(v);

torusp

So to plot a trefoil:

// Setup
u=u*(2*pi);
v=v*(2*pi);
phi=u;
// Parametric formula for a trefoil
pp=2;     // A trefoil is a (2,3) torus ring.
qq=3;
rr=cos(qq*phi)+2;
// xx,yy,zz are the formula for the trefoil, a function of one variable (phi)
xx=rr*cos(pp*phi);
yy=rr*sin(pp*phi);
zz=-3*sin(qq*phi);
// Modified Torus formula to bend a torus into a trefoil shape:
x=(4*xx+cos(v)*xx/rr);
y=(4*yy+cos(v)*yy/rr);
z=sin(v)+zz/rr;

trefoil

A trefoil is just on example of a torus knot. It is a (2,3) torus knot when means it winds 3 times around a circle in the interior of the torus, and 2 times around the torus’ axis of rotational symmetry. There is a whole family of torus knots (p,q). p and q correspond to pp and qq in the parametric formula above.

For instance, here is a (3,7) knot:

37knot

Below is another example which shows a (5,6) torus knot winding around a torus. This was not done in Formula Toy since it draws 2 surfaces (the knot and the torus), and Formula Toy only draws one surface. (but it was all done with three.js).

56torus

 

Rotations, Transformations – Geometries and Meshes

I was driving myself batty trying to get all my rotations and transformations to behave correctly in three.js. So in these kind of cases one must always pare down to essentials. As follows:

Lets create a simple mesh and place it on the scene:

// Example 1
var geo = new THREE.BoxGeometry(5,5,20,32);
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());

Then in the render loop, we rotate it around the Z axis (the blue axis):

_mesh.rotation.z = -_tick * Math.PI/256;    

The result:
snap
This just a screen grab, an animated gif. Hence the jerk when the animation restarts.

Now what happens if we rotate the mesh in the initial setup:

// Example 2
var geo = new THREE.BoxGeometry(5,5,20,32);
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
_mesh.rotateY(Math.PI/2);

Code in the render loop is the same as before:

_mesh.rotation.z = -_tick * Math.PI/256;    

Now the block rotates along the X (red) axis, even though we told it to rotate it along the Z axis.
snap

If we specify rotation order in the initial setup, then it will rotate around the Z axis:

// Example 3
_mesh.rotation.order = 'ZXY';

The result:
snap

Now lets try some translation. Initial setup:

// Example 4
var geo = new THREE.BoxGeometry(5,5,20,32);
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
_mesh.rotation.order = 'ZXY';
_mesh.rotateY(Math.PI/2);
_mesh.position.set(0,-6,0);
_scene.add( _mesh);

Render loop is the same, rotate around Z axis. The result is that the translation is applied and the object rotates around the its new local axis which was also shifted downwards:
snap

Three.js also supports the axis/angle method of specifying rotations:

// Example 5
var geo = new THREE.BoxGeometry(5,5,20,32);
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
// these have no effect because in render() we will directly modify the internal rotation matrix
//_mesh.rotateY(Math.PI/4);
//_mesh.rotation.order = 'ZXY';

Render loop:

var axis = new THREE.Vector3( 0, 0, 1 );
var angle = _tick * Math.PI / 256;
   // matrix is a THREE.Matrix4()
_matrix.makeRotationAxis( axis.normalize(), angle ); 
_mesh.rotation.setFromRotationMatrix( _matrix );

The result is identical to what we achieved above in Example 1 with mesh.rotation. But often it is easier to conceptualize an axis of rotation rather than a succession of Euler angles.
snap

We can mimic the Example 3 result using makeRotationY and applying it to the geometry.

// Example 6
var geo = new THREE.BoxGeometry(5,5,20,32);
geo.applyMatrix( new THREE.Matrix4().makeRotationY( Math.PI/2 ) );
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
_scene.add( _mesh);

Render loop is same as Example 5, with the desired result.
snap
Now why did that work whereas mesh.rotationY is ignored? Because we rotated the geometry; the vertices were changed. This will be clearer if we translate the geometry:

// Example 7
var geo = new THREE.BoxGeometry(5,5,20,32);
geo.applyMatrix( new THREE.Matrix4().makeRotationY( Math.PI/2 ) );
geo.applyMatrix( new THREE.Matrix4().makeTranslation(0,-6,0) );
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
_scene.add( _mesh);

// put sphere at mesh origin
var sphere = new THREE.Mesh(
    new THREE.SphereGeometry(1,20,20),
    new THREE.MeshNormalMaterial());
sphere.position.set(0, 0, 0,);  // we could put the sphere anywhere
                                // and the box would rotate around it

Render loop code is the same as the previous 2 examples:

var axis = new THREE.Vector3( 0, 0, 1 );
var angle = -_tick * Math.PI / 256;
   // matrix is a THREE.Matrix4()
_matrix.makeRotationAxis( axis.normalize(), angle ); 
_mesh.rotation.setFromRotationMatrix( _matrix );

The result:
snap
The sphere represents the center of our geometry, its origin. The vertices have been rotated and translated from the local origin, where the sphere is.

If we’re rotating geometries, it is helpful to create a set of axes to show the local rotation axes of the geometry.

// Example 8:
// put axes at mesh origin with mesh rotation
// drawAxes is my routine which is based on THREE.AxisUtils(). See animation link below.
_scene.add(drawAxes(10, _mesh.position, _mesh.rotation));

Since we’re just rotating the mesh around the Z (blue) axis, we can use this more compact syntax in the render loop:

_mesh.rotation.z = -_tick * Math.PI/128;

The result:
snap

So to review: we wanted a geometry to rotate around a point that was external to the geometry. We did that by transforming the vertices of the geometry using applyMatrix.

There is another way to accomplish the same result: attach the box mesh to a parent mesh. Set the child’s position (that is to say, the box’s position) to be relative to the parent. And then place the parent where one wants, and rotate the parent if appropriate:

// Example 9:
var geo = new THREE.BoxGeometry(5,5,20,32);
_mesh = new THREE.Mesh(geo, new THREE.MeshNormalMaterial());
_mesh.rotation.y = -Math.PI/2;
_mesh.position.set(0,-6,0);    // _mesh will be the child

_sphere = new THREE.Mesh(      // _sphere will be the parent
    new THREE.SphereGeometry(1,20,20),
    new THREE.MeshNormalMaterial());
_sphere.position.set(0,-12,0);
_sphere.rotation.x -= Math.PI/8;
_sphere.add(_mesh);      // add child to parent
_scene.add(_sphere);

// put axes at parent origin with parent rotation
_scene.add(drawAxes(10, _sphere.position, _sphere.rotation));

And in the render loop, rotate the _sphere, not the _mesh.

When is this method (building a parent child relationship) preferable to changing the geometry? I couldn’t see much difference until I had to work with physi.js to apply physics to some of my meshes. Physi.js only works with meshes that have certain simple geometries (sphere, cone, box, etc). It will however work with compound meshes and thus with more complicated geometries, but in this case a parent/child relationship between the meshes is required.

Full three.js animation is here.

Using r69 of three.js.

 

Drawing Pentatope Cross-Sections in three.js

A triangle is the simplest regular figure in 2 dimensions. Its 3 dimensional analogue is a tetrahedron. Its 4 dimensional analogue is the pentatope. Another term for these 3 geometries is: simplex. Many articles online explain these further.

I wanted to view what it would look like if a pentatope passed through our 3-dimensional space. There are many examples of what the projection of a pentatope onto 3-d space would look like (ie its shadow), but I didn’t want to do that because while projections can be pretty, they seem less intuitive than cross-sections.

To summarize, the plan was: take 3-dimensional cross-sections of the pentatope (a 4 dimensional shape). The actual drawing will be done using the 3-dimensional drawing toolkit called three.js.

Our equation for the 3-dimensional cross-section is:

    ax+by+cz+K = w

This is a linear equation; we’re not dealing with curved cross-sections for now, though that would be fun. a,b, and c are constants. x,y,z, and w are the 4 axes. K is a constant that we change to get different cross-sections.

But why do we need 4 dimensions to describe a 3-dimensional space? Because we are locating that 3-d space in 4 dimensions. Just as the equation for a plane in 3-d space requires 3 dimensions (e.g. x+y = z describes a plane in 3-d space).

What about our equation for pentatope? Well we don’t have an equation, but we have a collection of points. Our pentatope has 5 corners. Lines connect each point to every other point, resulting in 10 lines. These 10 lines in turn form 10 faces (2-d planes). These 10 faces in turn from 5 3-d tetrahedrons.

Note that:
– The intersection of a 4-d line and a 3-d space is a point.
– The intersection of a 4-d plane and a 3-d space is a line.
– The intersection of a 4-d volume and a 3-d space is a plane.

Our cross-section is going to look like a wire-frame, in other words a collection of lines. So we will capture the intersection of the pentatope’s faces with our cross-sectional space.

Our pseudo-code would look like this:

foreach (face in faces) {   // 10 of these
  // Each face is a triangle. Lets name the vertices p0, p1, p2. These points have 4-d coords.
  // point1 and 2 will be the points we use to draw a line in 3-d space using three.js.
  // they have 3-d coords of course.
  point1 = calculateIntersectionOfLineWithSpace(p0,p1); 
  point2 = calculateIntersectionOfLineWithSpace(p0,p2);
  drawLineUsingThreeJS(point1, point2);
}

So the interesting bit is in ‘calculateIntersectionOfLineWithSpace()’:

We must use parametric equations to work with lines in dimensions higher than 2. The parametric form for a line defined by the points p0 and p1 is:

    p = p0 + t*v   (1)

    where v = p1 - p0.

We need to calculate what the value of t is at the intersection with our cross-sectional space. (p0 and p1 are the vertices of one of the faces of our pentatope.) So we need to solve for t.

    t = (Pt - P0)/V

Pt is the point of intersection of the line with the cross-sectional space. Given our formula above for our 3-d cross-sectional space, the equation for t is:

    t = (W0-aX0-bY0-cZ0-K)/(aXv+bYv+cZv-Wv)

    Where P0 = (X0, Y0, Z0, W0) and V is (Xv, Yv, Zv, Wv). 

Plugging t into equation (1) above we calculate the point of intersection of our 4-d line with our 3-d space. We return (x,y,z) from ‘calculateIntersectionOfLineWithSpace()’ above, discarding w.

And we simply change K to see different cross-sections. Here is the animated result:
http://rwoodley.org/MyContent/WIP/30-Simplex/index.html

A still:
snap

 

Minecraft Menger Sponge – STEAM project.

What has zero volume and an infinite surface area? A Menger Sponge of course. If your child is a Minecraft fan like my 7 year old, then this simple fractal can be used to make a good afternoon STEAM project that teaches math and programming concepts. (Note you should already know how to modify Minecraft code. That would take more than afternoon to get a grip on. And of course you should know Java).

First we built a Level 1 Menger cube with snap cubes. Then we came up with the X,Y, and Z coordinates for each of the 20 blocks that make up the Level 1 cube. This was a major goal of our project: increased fluency with 3-d coordinates.

Screen Shot 2014-11-11 at 11.51.32 PM

Then it was not a difficult leap to see how our Java code used these 20 coordinates to place blocks.

    public static void drawblock(World world, int x, int y, int z, int startx, int starty, int startz) {
        int metadata = world.getBlockMetadata(x, y, z);
        Block block = Block.getBlockById(35);
        boolean res = world.setBlock(startx + x, starty + y, startz +  z+5, block, metadata, 3);
        System.out.println("Placing block at " + x + "," + y + ", res = " + res);
    }
    public boolean onItemUse(ItemStack par1ItemStack, EntityPlayer par2EntityPlayer, World world,
                             int startx, int starty, int startz, int par7, float par8, float par9, float par10) {

        Menger1Item.drawLevel1Cube(world, startx, starty, startz);
        return true;
    }
    public static void drawLevel1Cube(World world, int startx, int starty, int startz) {
        drawblock(world, 0, 0, 0, startx, starty, startz);
        drawblock(world, 1, 0, 0, startx, starty, startz);
        drawblock(world, 2, 0, 0, startx, starty, startz);
        drawblock(world, 0, 1, 0, startx, starty, startz);
        drawblock(world, 2, 1, 0, startx, starty, startz);
        drawblock(world, 0, 2, 0, startx, starty, startz);
        drawblock(world, 1, 2, 0, startx, starty, startz);
        drawblock(world, 2, 2, 0, startx, starty, startz);

        drawblock(world, 0, 0, 1, startx, starty, startz);
        drawblock(world, 0, 2, 1, startx, starty, startz);
        drawblock(world, 2, 0, 1, startx, starty, startz);
        drawblock(world, 2, 2, 1, startx, starty, startz);

        drawblock(world, 0, 0, 2, startx, starty, startz);
        drawblock(world, 1, 0, 2, startx, starty, startz);
        drawblock(world, 2, 0, 2, startx, starty, startz);
        drawblock(world, 0, 1, 2, startx, starty, startz);
        drawblock(world, 2, 1, 2, startx, starty, startz);
        drawblock(world, 0, 2, 2, startx, starty, startz);
        drawblock(world, 1, 2, 2, startx, starty, startz);
        drawblock(world, 2, 2, 2, startx, starty, startz);
    }

Here is the Level 1 Cube in Minecraft:

Level1

At this point we wanted to make higher level cubes. A simple recursive algorithm was called for. This was too much for my son, not surprisingly. It is excerpted below if you want to do something similar. The main concept I tried to convey was that each level was a new power of 20.

Level 1 = 20^1 = 20. Length of side: 3 blocks.
Level 2 = 20^2 = 400. Length of side: 9 blocks.
Level 3 = 20^3 = 8000. Length of side: 27 blocks.
Level 4 = 20^4 = 160,000. Length of side: 81 blocks.
Level 5 = 20^5 = 3,200,000. Length of side 243 blocks.
At this point you could point out how the volume is shrinking with each level. E.g: 400/9^3 < 3200000/243^3. Over time the volume will approach zero! Ah, the mysteries of fractals and limits. Back to the concrete: We started with a level 2 cube. Exploring this next level up was important to understand recursion. My son kindly illuminated the structure with torches as night fell: Level2Night

We skipped right to Level 4 which was beautiful and impressive. When night fell in our Minecraft world, the local wild-life (mobs) colonized our structure and served to give a nice sense of scale and depth.

Level3

Level3Mobs

Level3Sunrise

Take a tour of this level 4 Menger Cube:

Level 4 Menger Cube from Robert Woodley on Vimeo.

Could Minecraft handle a Level 5 cube? That was the question on our minds. 3,200,000 blocks. It took about 5 minutes and the laptop labored mightily. But it worked! There were nice glitch effects as Minecraft struggled to build out the structure. Also the top was truncated as Minecraft prevented us from going into outer space.

sunrise

This incredible fractal structure is best understood through video:

Level 5 Menger Cube in Minecraft from Robert Woodley on Vimeo.

Complete Java class to build a level 5 Menger Cube:

package com.example.examplemod;

import net.minecraft.block.Block;
import net.minecraft.entity.player.EntityPlayer;
import net.minecraft.item.Item;
import net.minecraft.creativetab.CreativeTabs;
import net.minecraft.item.ItemStack;
import net.minecraft.world.World;

public class Menger1Item extends Item {

    public Menger1Item() {
        setMaxStackSize(64);
        setCreativeTab(CreativeTabs.tabMisc);
        setUnlocalizedName("MengaLevel1Cube");
    }
    public static void drawblock(World world, int x, int y, int z, int startx, int starty, int startz) {
        int metadata = world.getBlockMetadata(x, y, z);
        Block block = Block.getBlockById(35);
        boolean res = world.setBlock(startx + x, starty + y, startz +  z+5, block, metadata, 3);
        System.out.println("Placing block at " + x + "," + y + ", res = " + res);
    }
    public boolean onItemUse(ItemStack par1ItemStack, EntityPlayer par2EntityPlayer, World world,
                             int startx, int starty, int startz, int par7, float par8, float par9, float par10) {

        Menger1Item.drawLevel1Cube(world, startx, starty, startz);
        return true;
    }
    public static void drawLevel1Cube(World world, int startx, int starty, int startz) {
        int[][] i5coords = returnCoords(81);
        for (int i5 = 0; i5 < 20; i5++) {
            int[][] i4coords = returnCoords(27);
            for (int i4 = 0; i4 < 20; i4++) {
                int[][] i3coords = returnCoords(9);
                for (int i3 = 0; i3 < 20; i3++) {
                    int[][] i2coords = returnCoords(3);
                    for (int i2 = 0; i2 < 20; i2++) {
                        int[][] coords = returnCoords(1);
                        for (int i1 = 0; i1 < 20; i1++) {
                            drawblock(world,
                                    i5coords[i5][0] + i4coords[i4][0] + i3coords[i3][0] + i2coords[i2][0] + coords[i1][0],
                                    i5coords[i5][1] + i4coords[i4][1] + i3coords[i3][1] + i2coords[i2][1] + coords[i1][1],
                                    i5coords[i5][2] + i4coords[i4][2] + i3coords[i3][2] + i2coords[i2][2] + coords[i1][2],
                                    startx, starty, startz);
                        }
                    }
                }
            }
        }
    }
    public static int[][] returnCoords(int level) {
        int[][] coords = {
                {0, 0, 0},
                {1, 0, 0},
                {2, 0, 0},
                {0, 1, 0},
                {2, 1, 0},
                {0, 2, 0},
                {1, 2, 0},
                {2, 2, 0},

                {0, 0, 1},
                {0, 2, 1},
                {2, 0, 1},
                {2, 2, 1},

                {0, 0, 2},
                {1, 0, 2},
                {2, 0, 2},
                {0, 1, 2},
                {2, 1, 2},
                {0, 2, 2},
                {1, 2, 2},
                {2, 2, 2},
        };
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 3; j++)
                coords[i][j] *= level;
        }
        return coords;
    }
}

 

CVision: Computer Vision Workbench

CVision: A computer vision WorkBench and Utilities written in WinForms that wraps OpenCV. I wrote it for my purposes, there is plenty to improve: https://github.com/rwoodley/CVision.

screenshot

Features:

  • Has all OpenCV color options and color maps.
  • Histogram Equalization
  • 4 Blurs
  • Many Morph Modes:
    • ERODE, DILATE, OPEN, CLOSE, GRADIENT, TOPHAT, BLACKHAT
    • You can specify morph type (RECT, CROSS, ELLIPSE) as well as kernel size.
  • Other transformations: NOT, SOBELX SOBELY, LAPLACIAN, SCHARRX1, SCHARRY1, CANNY, THRESHOLD
  • Ability to group operations into ‘recipes’.
  • Boolean operations.
  • Intelligent contours and rotation.
  • Ability to process in batch mode across a directory full of images.
  • All intermediate transformations are saved.

 

 

The Visual Representation of High Dimension Spaces

Our brains struggle visualizing spaces with more than 3 dimensions. This is a problem we tried to address in our FaceCloud and FaceField projects. We present here a possible solution using fractional dimensions to represent higher dimensions. The examples here are all based on the Eigenfaces face recognition algorithm where we were dealing with high dimension PCA spaces. But the visualization methodology is not specific to PCA.

The model we used for the Face Field project is a 60-dimensional ‘face space’. That is, we work with 60 Eigenvectors (or Eigenfaces) for all of our operations, be it classic face recognition, the anti-face calculation, or synthetic face generation.

We’ve repeatedly tried to create visualizations of this 60-dimensional space. Working with images makes this easier because one can see immediately what many of the Eigenvectors encode. Working with faces is even better because we’re so tuned to reading faces.

For instance the first Eigenface codes for both lighting and gender.

In this picture we see the ‘mean face’ or ‘average face’ in the center, and the results of shifting the first eigenface’s value (that is, its eigenvalue) from -1 to 1. Note that the face on the left is: female, white face on dark background. The face on the right is: male, dark face on light background.

The coordinates for the mean face are {0,0,0,0,0,…..,0} – zeroes for all 60 eigen values.
The coordinates for the face on the left are {-1,0,0,0,0,…..,0} – minus one for the first eigen value, 0 for the remaining 59.
The coordinates for the face on the right are {1,0,0,0,0,…..,0} – one for the first eigen value, 0 for the remaining 59.

—-
Lets take this a step further and look at the first 3 Eigenfaces. All of the faces below have Eigenvalues of 0 for all Eigenfaces beyond the 3rd one. The values for the first 3 are displayed on the diagram. We have just discussed the first Eigenface in our preceding paragraph. It is represented here by the axis that goes from the upper-left to the lower-right. The second Eigenface seems to encode for side lighting. The third Eigenface encodes for top vs bottom lighting which also incidentally encodes for hair.

But wait, you say, where is the face corresponding to these eigenvalues: {1,1,1}. or {1,1,0} or {-1,0,1}? These are indeed not displayed. One could imagine a cube with the X, Y and Z axes being the first 3 eigen vectors and these other missing faces being the vertices and edges of the cube. So go imagine that because I haven’t got a graphic handy that displays that. Even if I did, what would we have accomplished? Simply displaying 3 dimensions of data in 3 dimensions. The topic of this article concerns High Dimensional Spaces.

We can take the ‘Face Sextant’ above a step further and use Adelheid Mers’ fractal 3-line matrix to browse a 6 dimensional face space:

I only typed in the coordinates for a few faces. Hopefully you can easily divine what the other values would be. Once again we are missing the edges and vertices of the fractal cube (i.e. the face at {1,1,1,1,1,1} is not on this diagram).

So this process could be repeated over and over-again, adding 3 new dimensions to our visualization on each iteration. It is a loss-less method of representing higher dimensions using smaller and smaller fractal spaces.

In terms of actually making a usable visualization, the faces would get smaller of course so we would need a pan and zoom capability. Here is a visualization using this approach:

Face Cloud from Robert Woodley on Vimeo.

It displays faces with non-zero eigenvalue for the first 12 eigenfaces. In other words it is a visualization of 12 dimensional space. Note also it is using a tetrahedral approach as opposed to a cubic approach. That is, the coordinates for the first 4 faces to emanate from the Mean Face are: {1,1,1}, {-1,-1,1}, {1,1,-1}, {-1,-1,-1}. This reduces the number of faces, thereby reducing the visual clutter and giving the graphics card a chance to keep up with the calculations.

That was a video. The original was written in javascript using three.js and can be run here using chrome on a computer with a good graphics card.

—–

Separately, many of you have seen the Synthetic Face machine. It allows you to tweak all 60 eigen values to get any face you want from the face space, in real-time:

synthface

So it is not a way to visualize high dimension spaces, but it is useful for browsing those spaces and pulling faces at random from them. Indeed this was how we generated the faces on display at the “Enter The Matrix” show at the Chicago Cultural Center.

 

Face Field Update

10 Synthetic Faces are now on display at the Chicago Cultural Center through August, as part of Adelheid Mers’ “Enter the Matrix” exhibit. They look great in large format and are quite powerful. Some photos below.

These are faces pulled at random from the 60-dimensional PCA space that we have been working with for some time now. You can create your own Synthetic Face at http://facefield.org/SynthFace.aspx. (Click on the face that appears for options.)

P1010554small

P1010557small

P1010561small

 

Formula Toy

Back at the age of 17, thanks to the liberal access policies of Indiana University’s Wrubel Computing Center, I was able to write short little computer programs (on cards!) that would graph 3 dimensional surfaces using a pen plotter. The little nerd that was me was thrilled at the results, and my bedroom wall was plastered with graphs of various mathematical functions of my creation. And incidentally it was an extremely helpful way to get a visual understanding of mathematical geometries, including alternative coordinates systems – cartesian, spherical, and cylindrical.

In these days, there is no shortage of packages that will draw 3-D mathematical surfaces. However, nothing that I found was totally simple. All required a learning curve, or a download or a plugin. I wanted to build something whereby you would simply type in a formula, hit enter, and see the surface. Hence was born Formula Toy. It uses the amazing three.js library which is a wrapper around WebGL. The dependence on WebGL means that it won’t run on every single browser because WebGL is still an emerging standard. However it should work on most MACs and on most Window’s desktops, at least if you use a modern browser like Chrome.

You can either go directly to http://formulatoy.net or you can look at some examples and just click on ones there that intrigue you which will pop you straight into formula toy. There is some help text here.

ft

 

The Hairy Blob, 800 Ping Pong Balls, and a Mindstorms RoboCam

The Hairy Blob:

At the Hairy Blob exhibition at the Hyde Park Art Center last spring, visitors were invited to draw an image of time on a ping pong ball and toss it into a net that was suspended from the ceiling.

  

 

800 Ping Pong Balls:

What to do with over 800 ping pong balls?

 

How to document 800 three dimensional objects in less than 5 years?

Mindstorms RoboCam:

Our ping pong cam was an NXT Mindstorms robot (which rotated the balls) driven by a laptop that was simultaneously taking pictures. Controlling the robot from an external device was suprisingly difficult. NHK.MindSqualls did the job, but just.

Ping Pong Robo Cam and Laptop setup:

We did the scanning over Thanksgiving weekend at the Roger Brown house in New Buffalo, MI.

The installation:

Intalled at the Mers Micro Museum, a Raspberry Pi drives the display. Some javascript randomly selects from the 800, and then starts a few of them spinning. First it shows a random batch of the day time balls and then a random batch of the night time balls. And so on, indefinitely.

You can also spin the balls online.

 

Anti-Face Model Specification and Calculation Details

Update 10/2013: We have implemented this in a free iPhone app which is available here:

https://itunes.apple.com/us/app/anti-face/id690376775

 

Our site FaceField.org (and now the iPhone app) uses the EigenFaces methodology as implemented in Open CV to calculate a special kind of face that we have labelled an ‘Anti Face’.

Model specification:
– Over 1000 faces were used.
– The faces were all facing the camera straight-on. We used a specially designed Haar classifier to ensure that we excluded faces looking to the side.
– The faces that we fed into the PCA calculation are slightly larger than what the Haar classifier detected so that we didn’t cut off the chins.
– The faces were all subject to histogram equalization.
– The faces were all sized to 200×200 pixels.
– We took the first 60 eigenvectors.

The Antiface calculation is simple: we do a subspace projection of the uploaded face into the 60-dimensional EigenFace space. It is interesting to view this ‘reconstructed face’ as we call it. In a normal face recognition calculation you would then compute the nearest face to this reconstructed face. The anti-face is simply the reconstructed face except that every weight is multiplied by -1.

In other words:

Let Ω ∋ R⁶⁰ be the subspace projection of the uploaded face.

Ω=(w₁,w₂,..w₆₀) where wᵢ= uᵢᵀ(Γ-Ψ) for i=1…60.

u ∋ R⁶⁰ is the Eigenface. Γ is the uploaded face image and Ψ is the mean face.

Then the antiface, Ω’ is (-1*w₁,-1*w₂,..-1*w₆₀).

So prominent features in the reconstructed faces (with high weighting, meaning far from the mean) would be equally prominent, though opposite, in the anti-face.

gandhi

Why 60 dimensions? Originally we tried higher numbers like 200 because at that point the reconstructed face looks indistinguishable from the original face. However the anti-face looks very little like a face and is highly distorted and muddied. It seems that it such high-dimension space not everything looks like a face, however in a lower dimension space like 60 you’re likely to get a face no matter where you land.

Two Face/Anti-Face pairs as examples:

Screen Shot 2013-10-04 at 9.10.16 PM

Screen Shot 2013-10-04 at 9.22.28 PM

 

Visualizing Factors and Prime Factorization.

Update 8/2014: The calculator discussed below is also available in the Chrome store here (for free of course).

I’ve previously discussed Brent Yorgey’s factor diagrams. As the father of a 6 year old, I’ve found they are a great way to introduce the concepts of primes and factorization.

Since then, I dabbled with the javascript animations by Sean Seefried to create 2 related products:
1. a calculator, and
2. a factorization game.

Factor Diagram Calculator
The calculator does multiplication and division and allows the young ‘uns to explore the diagrams. I also recently added the ability to do exponentiation after watching Mike Lawler’s video on powers of 3 and Sierpinski’s triangle.

Multiplication:
Multiplication

Division:
Division

Calculator is here.

Factorization Game
Kids learn by playing, that is well known. So how to make a game out of all of this? I scripted up something simple whereby you’d be presented with a large number and have to factor it while the clock is ticking. Do this a few times, get a score. Then compare with friends collect badges, etc. That last bit (prizes, badges) is not written and is a whole separate app of course.

game

Game is here.

So as it now stands it is simple, a germ of an idea really. Any thoughts on how to improve the learning experience?

 

Factor Dominoes

Many have discovered Brent Yorgey’s very cool factorization diagrams. They seem like a great way to teach multiplication and factorization to children.

We also were excited by the domino game suggested by Malke Rosenfeld on her blog and decided to try to take her ideas and see if we could create viable game that also would be a fun way to think about factors and primes. To this end we brought together a math geek, a visual artist and a 6 year old ninja and started playing. Through trial and error we arrived at a set of rules.

Simple version of the rules:

Start by printing out a deck of cards. (We have attached a pdf to this post with numbers up to 24 that can be printed on card stock and cut up.)

Each player gets 6 cards. One card is turned face up in the middle. The first player tries to match the turned up card, following the match rules below. After that, players can choose to match the card at either end of the growing chain. If you can’t match then you draw another card. First person to run out of cards wins.

The whole game comes down to the matching rules:
– The number 1 matches anything
– The number 2 matches any even number
– Primes match primes (or as you can explain to a child: circles match circles)
– Other numbers have a major and minor group. For instance 9 has a major group of 3 and a minor group of 3. 15 has a major group of 5 and a minor group of 3. 18 has a major group of 3 and a minor group of 6.

expl

You can match based on major or minor group. If the card you want to play has the same major group or same minor group as the card to be matched, then you can play it. So 10 can match 15 (major group of 5 matches), and 9 can match 15 (minor group of 3 matches). A prime number can match either the minor or the major group, thus 5 can match 10 (major group), but 3 can match 15 (minor group).

Beyond the simple rules:

We started to think about a rule set that might work if you had numbers higher than 24.

Types of number visualizations: 

Primes are represented as circles.

Here are the types of Minor Groups:

Simple Minor groups are low primes:
1, 2, 3, 5, 7
low primes

Compounded minor groups:
4 (2×2), 6 (3×2)
compound

Doubly compounded minor groups:
8 (2x2x2), 9 (3x3x3), 16 (4x4x4), 18 (2x3x3)

Triple compounded minor groups:
24 (2x2x2x3), etc.

Major groups

A major group is a combination of N copies of one of these minor or compounded groups.

So here are the generalized matching rules:
– 1 matches anything
– 2 matches any even number
– Minor group types can be matched with each other within types, but not across.
– Major groups can be matched if they have an equal number of elements. For that, minor group types do not have to match.

Attachment:

Here is the pdf you can print out on card stock to make your own set of cards:

cards1-24