The Laves Graph

A new Shadertoy, the Laves Graph: https://www.shadertoy.com/view/wddBRX


Quaternions and Reflections

It’s well known that quaternions can be used to represent rotations in 3- and 4-dimensional space. It seems less well known that they can also be used to represent reflections and, in fact, we can derive the representation of rotations from this in a straightforward way (since all rotations can be constructed as a sequence of rotations).

We shall write quaternions p and q as:

p = x+X
q = y+Y

where x and y are scalars and X and Y are 3-vectors. Now quaternion multiplication can be defined as:

pq = (x+X)(y+Y) = (xy - X.Y) + (xY + yX + XxY)

with brackets in the result indicating the scalar and vector parts (and where X.Y and XxY are the usual dot and cross product). Quaternion multiplication is associative: p(qr) = (pq)r = pqr but not commutative (in fact, pq = qp just when XxY is zero).

We also define conjugation, the conjugate of p, which we write as p' (overbar is conventional, but I think is harder to read onscreen), is p with the vector part negated:

p' = x-X

Combining multiplication and conjugation we have:

pq' = (x+X)(y-Y) = (xy + X.Y) + (-xY + yX - XxY)
qp' = (y+Y)(x-X) = (xy + X.Y) + (+xY - yX + XxY) (since YxX = -XxY)

and adding both equations, the vector parts cancel and we have:

pq' + qp' = 2(xy + X.Y)

But xy + X.Y is just the dot product of p and q, considered as normal 4-dimensional vectors, so we can write:

pq' + qp' = 2p.q

This nicely relates quaternion algebra directly to the geometry of 4-space and we can now rewrite expressions using dot product purely in terms of quaternion arithmetic (quaternion addition and subtraction and operations with scalars are the same as for ordinary vectors, of course).

So, the usual definition, valid in any dimension, for a reflection in a (hyper)plane with normal n (assumed to be a unit vector) is:

p → p - 2(p.n)n

we can rewrite as:

p → p - (pn' + np')n = p - pn'n - np'n = p - p - np'n = -np'n

ie. reflection of p in n is just -np'n. Note that a 4-dimensional reflection is in a 3-dimensional hyperplane (or perhaps it is clearer to think of the reflection as being along the normal vector), so vectors parallel to the normal are reversed, vectors orthogonal to the normal (ie. in the normal hyperplane) are unchanged.

Interestingly, the relation pq' + qp' = 2p.q is also true for complex numbers (with the usual complex multiplication and conjugation) and we have exactly the same represention for a 2-dimensional reflection, but we can further simplify using the commutativity of complex multiplication:

z → z - 2(z.n)n = -nz'n = -n²z'

Returning to quaternions, we can combine two reflections, with normals n and m, say, to get a (simple) rotation:

p → -m(-np'n)'m = mn'pn'm

and geometry tells us that the rotation is about an angle twice that between the the planes of reflection.

In 4-space, this rotation can be thought of as in the plane spanned by n and m (ie. vectors in that plane rotate to other vectors in the plane), or around an axis of another plane, orthogonal to the first, in fact the intersection of the two hyperplanes normal to n and m.

A general 4-dimensional rotation needs 4 reflections:

p → j(l(mn'pn'm)'l)'j = jl'mn'pn'ml'j

and we lose any simple relation between the left and right quaternion – in fact p → qpr is a rotation for any unit quaternions q and r (an interesting case arises if q or r is the identity – a Clifford translation).

We can derive expressions for reflections and rotations in 3-space from this, with 3-space points represented as pure quaternions, ie. with zero scalar part, so if n and m are pure, then n' = -n and nm = (mn)'

A reflection now is:

p → -np'n = npn

and a rotation is:

p → mn'pn'm = mnp(mn)'

and we have the usual definition of a rotation in 3-space:

p → qpq'

Representing rotations as compositions of reflections also has practical uses. Consider the problem of finding a rotation to take a vector p to a vector q (assumed to both be of unit length) – we can do this as two reflections, first reflect p in the (hyper)plane normal to p+q, this aligns p with q, but in the opposite direction, so reflect again in the plane orthogonal to q (it may help to sketch a picture – the construction makes sense in 2 or more dimensions). Using the 3-space formulation above, and the fact that qq = -1 for pure q, we have:

p → qpq' where q = -q(p+q)/|p+q| = (-qp-qq)/|p+q| = (1-qp)/|p+q|

and since we know that the result is of unit length, we can just use:

p → normalize(1-qp)

(with a special case when qp = 1, ie when q = -p, when the rotation is not uniquely defined).

Also, if we have two vectors x0,y0 and wish to rotate them to new vectors x1,y1 (assume |x0| = |x1|, |y0| = |y1|, and |x0-y0| = |x1-y1|, first reflect x0 to x1 along x1-x0 (ie. in the plane orthogonal to x1-x0), this also reflects y0 to a new point y2, but we can then reflect y2 to y1 along y2-y1 (this leaves x1 unchanged as it is equidistant from from y1 and y2):

n = x1-x0
y2 = y1 - 2(y1.n/n.n)n
m = y2-y1
r = normalize(mn)

There is always a unique rotation, but two special cases are: if x0 = x1, then swap x0 with y0 and x1 with y1 (if y0 = y1 as well, there is nothing to do); and if y2 = y1, then reflect along cross(x1,y1) rather than y2-y1.

A similar construction is also possible in 4-dimensional space: 3 point pairs define a general rotation (the first three reflections map the 3 points, the last reflection, in the hyperplane containing those points, ensures we have a proper rotation).

Much of this is taken from Coxeter’s 1946 paper, “Quaternions and Reflections”, https://www.jstor.org/stable/2304897, which of course goes into much more depth and with much greater rigour.


Drawing the Clebsch Surface as Particles

clebsch

http://matthewarcus.github.io/polyjs/clebsch.html

https://github.com/matthewarcus/polyjs/blob/master/js/clebsch.js

Instead of using a triangulated mesh, we can display a surface in 3d by simply generating a set of random points on the surface and displaying them as a sort of particle system. Let’s do this with the famous Clebsch cubic surface: the points are stored as homogeneous coordinates, to display we multiply by a quaternion to rotate in projective space before doing the usual perspective projection to Euclidean space.

The Clebsch surface is the set of points (x0,x1,x2,x3,x4) (in projective 4-space) that satisfy the equations:

x0 + x1 + x2 + x3 + x4 = 0
x03 + x13 + x23 + x33 + x43 = 0

To simplify things, we can eliminate x0 (= x1 + x2 + x3 + x4) and rename a little, to get the single cubic equation:

(x + y + z + w)3 = x3 + y3 + z3 + w3     [***]

defining a surface in projective 3-space, with the familiar 4-element homogeneous coordinates.

Since coordinates are homogeneous, we can just consider the cases of w = 1 and w = 0 (plane at infinity), but for w = 0, it turns out the solutions are some of the 27 lines which we shall later draw separately, so for now just consider the case w = 1 for which we have:

(x + y + z + 1)3 = x3 + y3 + z3 + 1

and given values for x and y, we can solve for z easily – the cubes drop out and we just have a quadratic equation that can be solved in the usual way:

3Az2 + 3A2z + A3 - B = 0 where A = x+y+1, B = x3 + y3 + 1

We can now generate points on the surface by randomly choosing x and y and solving for z to give a set of homogeneous points (x,y,z,w) satisfying [***] and we can get further solutions by permuting the coordinates. We don’t need all permutations since some of the coordinates are arbitrary, and points that are multiples of each other are equivalent. The random points themselves are generated by this Javascript function, that generates points between -Infinity and +Infinity, but clustered around the origin.

function randpoint() {
        var x = 1/(2*Math.random()-1);
        if (x < 0) x -= 1;
        if (x > 0) x += 1;
        return x;
    }

The Clebsch surface of course is famous for its 27 lines, so we draw these in as well, also as random selection of points rather than a solid line. 15 lines are points of the form (a,-a,b,-b,0) and permutations – since we are working in 4-space, this becomes 12 lines of form (a,-a,b,0) and three of form (a,-a,b,-b). These 15 lines are drawn in white and can be seen to intersect in 10 Eckardt points where 3 lines meet (though it’s hard to find a projection where all 10 are simultaneously visible). The other 12 lines are of the form (a,b,-(φa+b),-(a+φb),1) where φ is the golden ratio, 1.618.. and can be seen to form Schläfli’s “Double Six” configuration – each magenta or cyan line intersects with exactly 5 other lines, all of the opposite color.

All that remains is to project into 3-space – as usual we divide by the w-coordinate, but to get different projections, before doing this we rotate in projective space by multiplying by a quaternion & then varying the quaternion varies the projection. (Quaternion (d,-a,-b,-c) puts plane (a,b,c,d) at infinity – or alternatively, rotates (a,b,c,d) to (0,0,0,1) – it is well known that quaternions can be used to represent rotations in 3-space, but they also work for 4-space (with 3-space as a special case) – a 4-space rotation is uniquely represented (up to sign) by x -> pxq where p and q are unit quaternions). Here we multiply each point by a single quaternion to give an isoclinic or Clifford rotation – every point is rotated by the same angle.

We are using Three.js, which doesn’t seem to accept 4d points in geometries – we could write our own vertex shader to do the rotation and projection on the GPU, but for now, we do it on the CPU; updating the point positions is reasonably fast with the Three.js BufferGeometry. Actually displaying the points is simple with the THREE.Points object – we use a simple disc texture to make things a little more interesting, and attempt to color the points according to the permutations used to generate them.

The mouse and arrow keys control the camera position, square brackets move through different display modes, space toggles the rotation.

An excellent reference giving details of the construction of the surface (and good French practise) is:

http://www.mathcurve.com/surfaces/clebsch/clebsch.shtml


Drawing Uniform Polyhedra with Javascript, WebGL and Three.js

Screenshot from 2015-06-21 22:46:59

I’ve been meaning to write this up properly for a long time, but for now, this link will have to do:

http://matthewarcus.github.io/polyjs/

The idea is to use some fairly straightforward vector geometry to generate uniform polyhedra and their derivatives, using the kaleidoscopic construction to generate Schwarz triangles that tile the sphere. We use spherical trilinear coordinates within each Schwarz triangle to determine polyhedron vertices (with the trilinear coordinates being converted to barycentric for actually generating the points). Vertices for snub polyhedra are found by iterative approximation.

We also can use Schwarz triangles to apply other symmetry operations to the basic polyhedra to generate compound polyhedra, including all of the uniform compounds enumerated by John Skilling (as well as many others).

There are some other features including construction of dual figures, final stellations, inversions, subdividing polyhedra faces using a Sierpinksi construction, as well as various colouring effects, exploding faces etc..

Much use was made of the work of others, notably George Hart and Zvi Har’El as well as the wonderful Three.js library by Mr.doob.

Screenshot from 2015-06-22 19:21:43
Screenshot from 2015-06-22 19:27:19
Screenshot from 2015-06-21 22:52:41
Screenshot from 2015-06-21 23:02:21
Screenshot from 2015-06-21 23:11:30