SingSurf Home help maths

Wallpaper patterns - the mathematics

Basic transformations

The wallpaper patterns are produced by combining a number of transformations. The basic transformations are

A translation	A reflection - M	A glide-reflection: a translation follow by a reflection - G
180° rotation - P2	120° rotation - P3	90° rotation - P4	60° rotation - P6

 

Each wallpaper pattern is based on a pair of translations in different directions. The translations are applied multiple times to give a repeating image. This defined a regular grid of points called a lattice.
The blue shape in the program is called the fundamental domain. The image inside it is translated, rotated and reflected to produce the final image. The yellow parallelogram is one cell in the lattice, the image inside every other cell will be identical to this.
The symmetry lines can be shown. In this pattern the final image is produced by reflecting in the magenta lines. This pattern also has rotational symmetry: each cyan-rectangle is a center of 180° rotation.
Some groups allow some flexibility in the shape of the fundamental domain. For instance the P1 group allows curved edges as used in some of Escher's woodcuts. Here, for simplicity, the fundamental domain is restricted to be a polygon although alternate version of the P1 and P2 rules based on hexagonal cells and the P31M rule with a kite-shaped fundamental domain. Other groups are more restrictive, if the group contains rotation points then the fundamental domain must pass through these point and if the pattern contains a line of reflection then that line will form one edge of the fundamental domain.

The patterns

Lattice type: parallelogram
	P1: the simplest pattern, two translations in different directions.		P2: this pattern has an extra 180° rotation.
Lattice type: diamond
	CM: a reflection along a diagonal		CMM: two reflections along the diagonal
Lattice type: rectangle, the translations are at right angles
	PM: A reflection		PG: A glide reflection
	PMG: A reflection and a glide reflection		PGG: Two glide reflections at right angles		PMM: Two reflections at right angles
Lattice type: square
	P4: a 90° rotation		P4M: a 90° rotation and a reflection		P4G: a 90° rotation and a glide-reflection
Lattice type: hexagon
	P3: a 120° rotation		P3M1: a 120° rotation and a reflection. Line of reflections pass through opposite vertices of the hexagon		P31M: a 120° rotation and a reflection. Line of reflections pass through centers of the edges the hexagon
	P3: a 60° rotation		P3M: a 60° rotation and a reflection

Frieze groups, cyclic groups and dihedral groups

As well as the wallpaper groups their are three other families of symetries in the plane.

• The seven frieze groups
• An infinite family of cyclic groups: rotations around a point.
• An infinite family of dihedral groups: generated by two lines of reflection which pass through a point.

Whilst the wallpaper groups repeat in two directions the frieze groups only repeat in a single direction

	F1 translation in one direction Symmetry of the infinite sequence of letters pppppp
	F2 a glide-reflection pdpdpd.
	F3 translation and a parallel reflection CCCCCC
	F4 translation and a pair of parallel reflections pqpqpq
	F5 translation and 180° rotation pdpdpd
	F6 translation and a perpendicular reflection and 180° rotation pdbqpdbq.
	F7 translation, perpendicular reflection, parallel reflection XXXXXX.

Frieze groups are often found in decorative borders. The top border of this page is F2 and the left hand side border is F4.

The cyclic and dihedral groups all have rotational symmetry about a single point. Cyclic groups have n-fold rotation symmetry (rotation by 360°/n). Dihedral groups have an n-fold rotational symmetry and two reflections in lines at 180°/n to each other.

		Cyclic groups
C2	C3	C4	C5	C6
		Dihedral groups
D2	D3	D4	D5	D6

The group D1 is technically classed as a dihedral group it just consists of a single reflection.

D1

Orbifold and topology

An alternative way of specifying the groups is using Thurston's orbifold notation. It uses numbers to represent the order of rotation points, * for a reflection, x for a glide-reflection and o for the "wonder" with no aditional symmetries other than translations. Symbols are listed in order, number before a * represent cyclic rotations and those after dihedral rotations.

Each type of symmetry has a cost:

Symmetry	Symbol	Cost
Cyclic Cn points	n (before a *)	\(\frac{n-1}{n}\)
Reflection	*	1
Dihedral Dn points	n (after a *)	\(\frac{n-1}{2n}\)
Glide-reflection	x	1
The wonder	o	2

The "Magic theorem" states that for Wallpaper groups these costs must sum to 2. The theorem is derived from the calculating the Euler characteristic of a tesselation of the plane from multiple copies of the fundamental domain. Each vertex and edge is given a weighting, for example a C3 vertex has a weight of \(\frac13\) as three copies of the vertex contribute to a single vertex in the tesselations, likewise edge have a weight of \(\frac12\) and D2 vertex has a weight of \(\frac14\). Costs for each symmetry are found from these weights and a calculation show the Euler chararateristic of the plane is \(2-\text{total cost}=0\). A sketch proof of the result can be found in Geometry and the Imagination: The Euler characteristic of an orbifold

Some of the edges of the fundamental domain can be identified, so it forms a topologial manifold, \(M\). If are lines of reflection it will be a manifold with boundary. This manifold is either a sphere (p2, p3, p4, p6) a disk (pmm, p3m1, p4m, p6m, pmg, cmm, p31m, p4g) a cylinder (pm), Klein bottle (pg), Möbius band (cm), real-projective plane (pgg) or torus (p1).

Further structure is added to form an orbifold where cyclic rotations give conical points, reflections lines give boundary points and dihedral rotations form corners on the boundary. There is a group actions \(\mathbb{R}^2/\Gamma\) associated with each symmetry in the orbifold.

Pure gyrations
These patterns are generated by a three or four cyclic rotation points. The two edges adjacent each rotation point are identified so the underlying manifold forms a topological sphere, with Euler chrarateristic, χ=2. Each n-fold rotation point gives a conical point in the orbifold with cost \(1-\frac{1}{n}\).
p2: 2222 Four C2 rotations. Cost: \(\frac12+\frac12+\frac12+\frac12=2\) Manifold: sphere Euler chrarateristic: χ=2 Chromatic number: 4
p3: 333 Three C3 rotations. Cost: \(\frac23+\frac23+\frac23=2\) Manifold: sphere Euler chrarateristic: χ=2 Chromatic number: 4
p4: 442 Two C4 rotations and one C2 rotation. Cost: \(\frac34+\frac34+\frac12=2\) Manifold: sphere Euler chrarateristic: χ=2 Chromatic number: 4
p6: 632 One C6, one C3 and one C2 rotation. Cost: \(\frac5/6+\frac23+\frac12=2\) Manifold: sphere Euler chrarateristic: χ=2 Chromatic number: 4
Pure kalidoscopes
These patterns are generated by three or four dihedral rotations. The edges of the fundamental domain are lines of reflection, giving rise to a boundary of the orbifold. Hence the underlying manifold is a disk with Euler chrarateristic, χ=1. The boundary, *, has a cost of 1 and each n-fold dihedral rotation has a cost of \(\frac{n-1}{2n}\).
pmm: *2222 One reflection, four D2 rotations. Cost: \(1+\frac14+\frac14+\frac14+\frac14=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
p3m1: *333 One reflection, three D3 rotations. Cost: \(1+\frac26+\frac26+\frac26=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
p4m: *442 One reflection, two D4 rotations and one D2 rotation. Cost: \(1+\frac38+\frac38+\frac14=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
p6m: *632 One reflection, one D6, one D3 and one D2 rotation. Cost: \(1+\frac{5}{12}+\frac26+\frac14=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
Parallel reflections
This patterns is generated by two parallel reflections and a translation. Two edges of the fundamental domain are lines of reflection, giving rise to a boundary of the orbifold, the other two are identified. Hence the underlying manifold is a cylinder with Euler chrarateristic, χ=0.
pm: ** Two reflections. Cost: \(1+1=2\) Manifold: cylinder Euler chrarateristic: χ=0 Chromatic number: 4
Hybrid types
These patterns have both cyclic points, reflections and sometimes dihedral rotations. The lines of reflection give a boundary of the orbifold, so the underlying manifold is a disk with Euler chrarateristic, χ=1. The cyclic rotations correspond to conical points and the dihedral rotations give corners.
pmg: 22* Two C2 rotations and one line of reflections. Cost: \(\frac12+\frac12+1=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
cmm: 2*22 One C2 rotation, one reflection and two D2 reflections. Cost: \(\frac12+1+\frac14+\frac14=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
p31m: 3*3 One C3 rotation, one reflection and one D3 rotation. Cost: \(\frac13+1+\frac26=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
p4g: 4*2 One C4 rotation, one reflections and one D2 rotation. Cost: \(\frac34+1+\frac14=2\) Manifold: disk Euler chrarateristic: χ=1 Chromatic number: 4
Glide-reflections and cross-caps
These patterns all have glide refleftions indicated by a x with cost 1. Oposite edges are idetified in a revese direction, yielding non-orientable manifolds.
pg: xx Two parallel glide-reflections. Cost: \(1+1=2\) Manifold: Klein bottle Euler chrarateristic, χ=0. Chromatic number: 6
cm: *x A reflection and a glide-reflections. Cost: \(1+1=2\) Manifold: Möbius band Euler chrarateristic: χ=0. Chromatic number: 6
pgg: 22x Two C2 rotations, and a glide-reflection. Cost: \(\frac12+\frac12+1=2\) Manifold: real-projective plane RP² Euler chrarateristic: χ=1. Chromatic number: 6
The wonder: just translations
This pattern has no aditional symmetries. Oposite edges are identified, so the underlying manifold is a torus with Euler chrarateristic, χ=0.
p1: o Cost: \(2\) Manifold: torus Euler chrarateristic: χ=0. Chromatic number: 7 <

Examples of orbifolds

Given a topological space X and a group G we can form the quotient space by factoring out the group action. Say with the P1 group

Using a motif of Beanish from Tales of the beanworld.

Factoring out the group action generated by the two translations gives a single cell with opposite edges are identified.

We can wrap the image around a cylinder, so the blue arrows match, and then join the top of the cylinder to the bottom to form a torus:

The torus has Euler characteristic χ=0, and following the Heawood conjecture any tiling with this symmetry can be coloured with 7 colours, so that no two faces of the same colour share an edge. One such tiling is based on hexagons.

Unit cell	Wallpaper pattern	Wrapped around a torus

PM: **

The PM pattern has two parallel reflections.

Take a horizontal strip with top and bottom identified, fold along the vertical mirror lines, forming a concertina. Identify top and bottom edges to form a cylinder. The green edges correspond to the two lines of reflection, which always form a boundary on the orbifold.

A strip formed by folding along the reflection lines.	The unit cell has top and bottom identified, so it forms a cylinder.	Joining edges forms a cylinder.

The cylinder has Euler characteristic χ=0, and had chromatic number 4, so four colours surfice.

CM: *x

This pattern has a reflections and a parallel glide-reflection.

Folding along the reflection lines gives a strip with glide-reflection. The fundametal domain has top and bottom identified in opposite directions, and forms a Möbius band.

A strip formed by folding along the reflection lines, has a glide-reflection.	The unit cell has top and bottom identified, but in opposite directions:	Joining edges forms a Möbius band.

The Euler charateristic is 0, and 6 colours surfice. Heres one tiling requiring 6 colours. Note how each colour is adjacent to every other colour, so it can't be coloured with fewer colours.

Unit cell	Wallpaper pattern	Wrapped around a Möbius band

PG: xx

This pattern is generated by two parallel glide reflections. So the motif is translated in one direction and flipped and translated in the other direction. The unit cell has opposite edges identifed, one pair with the same orientation, and the other with reversed orientation. Identifying edges gives a Klein bottle.

Wallpaper pattern	Unit cell

This has Euler characteristic χ=0, and chromatic number 6.

Unit cell	Wallpaper pattern	Wrapped around a Klien bottle.

PGG: 22x

This pattern has two perpendicular glide reflections and two C2 cyclic rotations. So the motif is flipped and translated in the both direction. The unit cell has opposite edges identifed, each pair with reversed orientation, and joining the opposite edges gives a real projective plane.

Wallpaper pattern	Unit cell	Wrapped around a real projective plane.

This has Euler characteristic χ=1, and chromatic number 6.

Unit cell	Wallpaper pattern	Wrapped around a Klien bottle.

The cell division here is adapted from mathcurve.com

The code

Each symmetry group is represented by a member of the class TessRule which defines the type of pattern and a set of vectors which specify a coordinate frame. The origin of this frame is the green dot and the two coordinate axis are the lines from the green dot to the red and blue dots. This frame defines at lattice which tessellate the the plane by parallelograms, and the image inside each parallelogram will be the same.

First consider the case of the simplest group P1. To calculate the tessellated image for each point in the image P_dest we wish to find the point P_src inside the fundamental domain. To achieve this first transform to coordinates in the new frame to give the point Q_dest. As the image in each parallelogram is identical we can take coordinates in this frame mod 1 giving the point Q_src. Finally transform back to image coordinates giving the P_src. Finally the colour of the pixel at P is set to the color at P.

For other transformations a little more work is needed. Consider Pmm which is obtained by reflection in two lines at right angles. In the transformed coordinates this is in the lines x=0.5 and y=0.5. Let Q_mod be the point after the modulus is taken which has coordinates (x_mod,y_mod) with x_mod and y_mod in the range 0 to 1. The y-coordinates of Q_src, x_src is calculate as follow:

• if x_mod < 0.5, x_src = x_mod,
• if x_mod > 0.5, x_src = 1 - x_mod.
• if y_mod < 0.5, y_src = y_mod,
• if y_mod > 0.5, y_src = 1 - y_mod.

Each other group will have similar condition.

In the above the transformation we have used floating point coordinates. The above calculations can be repeated using purely integer arithmetic, this results in faster algorithms and eliminates any rounding problems. Let O be the position of the green dot and u and v be the two vectors of the frame. Let M be the matrix with u and v as columns, this has the determinant det = (u_x * v_y - u_y v_x). . Now the transformation from a point q in the Q-frame to a point p the P-frame is given by p=O + Mq, and the inverse transformation is q = M^-1(p-O). The inverse matrix M^-1 is calculated as 1/det (v_y, -v_x;-u_y u_x). If we multiply through by the determinant giving q' = det M^-1(p-O), observe that q' will have integer coordinates. The above method can be followed through using this scaled frame, with the frame vectors being (det,0) and (0,det).

int Qdest[] = new int[2];
int Qsrc[] = new int[2];
int det = ux * vy - uy * vx;

for(i=0;i<width;++i)
 for(j=0;j<height;++j) {
  // translate
  int x = i - x0; 
  int y = j - y0;
  // calculate Q coodinates of dest
  Qdest[0] = vy * x - vx * y; 
  Qdest[1] = -uy * x + ux * y;
  // apply specific transformation
  fun(Qdest,Qsrc,det); 
  // calculate Psrc
  int srcX = x0 + (Qsrc[0] * ux + Qsrc[1] * vx ) / det;	
  int srcY = y0 + (Qsrc[0] * uy + Qsrc[1] * vy ) / det;	
  // copy src pixel to dest pixel
  pixels[i*width+j] = pixels[srcX*width+srcY];
 }
 
// An example of transformation function for group Pmm 
void fun(int dest[2],int src[2],int det) {
	// find modulus
	int a = dest[0] % det; if(a<0) a+= det;
	int b = dest[1] % det; if(b<0) b+= det;
	// find coordinates of point in fundamental domain
	if(a>det/2) a = det - a;
	if(b>det/2) b = det - b;
}

Hexagonal patterns

The five patterns with 3 or 6 fold rotations require the more complex calculations.

• Let \(det\) be the length of the u vector.
• First calculate coordinates \(\mathbf{in}=(X, Y)\) with respect to the u-v frame.
• Find the "integer"" and "fractional" parts of the input: \(X=a + \frac{\alpha}{det}, Y =b + \frac{\beta}{det}\), where \(a,\alpha, b,\beta\) are integers and \(0 \leq \alpha, \beta < det\). So \(\alpha = X \bmod det\), \(a = \lfloor \frac{X}{det}\rfloor \), \(\beta = Y \bmod det\), \(b = \lfloor \frac{Y}{det}\rfloor \).
• Find \(index = (a + b ) \mod 3\), all points with the same index will have the same source point.
• Next factor out the 3-fold rotation around the center of the tile. This can be found by simple addition with 5 cases depending on the index and \(\alpha\) and \(\beta\). $$\mathbf{out} = \begin{cases} (\alpha,\beta) & index=0 \\ (\beta - \alpha, det - \alpha) & index=1, \alpha < \beta \\ (det - \beta, \alpha - \beta) & index=1, \alpha \ge \beta \\ (det - \beta, \alpha - \beta + det) & index=2, \alpha < \beta \\ (\beta - \alpha + det, det - \alpha) & index=2, \alpha \ge \beta \end{cases}$$
• Further symmetry options depending on the type of pattern

In the above figure, we wish to rotate the point \(\mathbf{in}\) around the center of the tile \(\mathbf{p}\). Orange number are the index of each parallelogram The input point is $$\mathbf{in} = \left(a + \frac{\alpha}{det}\right) \mathbf{u} + \left(b + \frac{\beta}{det}\right) \mathbf{v}$$

Here \(a = 1, b=0, index=1\) and \(\alpha < \beta\). Rotating 120° clockwise around O send \(\mathbf{u}\to\mathbf{w}=-\mathbf{u}-\mathbf{v}\) and \(\mathbf{v}\to\mathbf{u}\) so the rotated points is $$\mathbf{rot}=\left(1 + \frac{\alpha}{det}\right) (-\mathbf{u}-\mathbf{v}) + \left( \frac{\beta}{det}\right) \mathbf{u} = \left(-1-\frac{\alpha}{det}+\frac{\beta}{det}\right)\mathbf{u} + \left(-1-\frac{\alpha}{det}\right)\mathbf{v} $$ Translating by \(\mathbf{u}+2\mathbf{v}\) gives the final output point $$ \mathbf{out}=\left(-\frac{\alpha}{det}+\frac{\beta}{det}\right)\mathbf{u} + \left(1-\frac{\alpha}{det}\right)\mathbf{v} $$ With coordinated \((-\alpha+\beta, det-\alpha)\) in the u-v frame.

Hence the calculation of the output coordinates can be done in integer arithmetic, the only time floating point is used is when calculating the vector \(\mathbf{v}\) which only needs to be done once.

Using lattice points

The calculation can be sped up by using the lattice structure of the tessellation. First find the bounding box enclosing one parallelogram in the lattice, and calculate the full pattern in that rectangle. The find all the lattice points in the region to be drawn. For each lattice point copy the pixels in the rectangle to a new rectangle based on the lattice point. This will result in a certain amount of overlap, but this does not affect the speed as coping arrays can be achieve very quickly.

Speeds of integer and floating point

Using integer arithmetic offers considerable speed advantages over floating point in the inner loops. Compare these two methods for finding division rounded down (rather than to 0 as in the language spec for /):

 int a = (int) Math.floor((float) in[0]/det);
 int b = (int) Math.floor((float) in[1]/det);

and

 int a = (in[0]<0 ? (in[0]+1)/det -1 : in[0]/det); 
 int b = (in[1]<0 ? (in[1]+1)/det -1 : in[1]/det); 

Changing from the first to the second resulted in a four fold speed improvement over the whole algorithm. These two lines represented 67% of the entire speed of the algorithm.

Further information

For more information see Wikipedia.