John Conway came up with a tiny language for building polyhedra: start from a simple shape and apply one-letter operators to it. d takes the dual, k raises a pyramid on every face, and you can chain them. With a handful of letters you can get from a cube to almost any polyhedron you've seen.

This is the first post of a small series. Today: how to store a polyhedron, and three operators.

Want to play right away? Grab conway.py and run python3 conway.py. It's plain Python with nothing to install, and it draws every picture in this post.

A polyhedron is a list of points and a list of faces

Each face is a list of vertex indices, in counterclockwise order when you look at it from outside. That order matters: it tells us which side of a face is "out".

def cube():
    vertices = [(x, y, z) for x in (-1, 1) for y in (-1, 1) for z in (-1, 1)]
    faces = [[0, 1, 3, 2], [4, 6, 7, 5], [0, 4, 5, 1],
             [2, 3, 7, 6], [0, 2, 6, 4], [1, 5, 7, 3]]
    return vertices, faces

Two helpers: the centre of some points, and a push onto the unit sphere so shapes stay round as we keep adding vertices.

from math import sqrt

def centroid(points):
    n = len(points)
    return tuple(sum(p[i] for p in points) / n for i in range(3))

def on_sphere(p):
    length = sqrt(sum(c * c for c in p))
    return tuple(c / length for c in p)

d: dual

The dual swaps vertices and faces: a new vertex in the middle of every face, and a new face around every old vertex. The dual of a cube is an octahedron.

The fun part is walking around a vertex in order. Every edge a → b belongs to exactly one face, and its reverse b → a belongs to the neighbour, so we can hop from face to face across edges:

def dual(vertices, faces):
    """A vertex for every face, a face for every vertex."""
    new_vertices = [on_sphere(centroid([vertices[i] for i in f])) for f in faces]
    face_of_edge = {}                      # directed edge (a, b) -> the face it belongs to
    for fi, f in enumerate(faces):
        for a, b in zip(f, f[1:] + f[:1]):
            face_of_edge[a, b] = fi
    new_faces = []
    for v in range(len(vertices)):
        start = next(fi for fi, f in enumerate(faces) if v in f)
        ring, fi = [], start
        while True:                        # walk around v, one face at a time
            ring.append(fi)
            f = faces[fi]
            before = f[f.index(v) - 1]     # the edge (before, v) is shared with the next face
            fi = face_of_edge[v, before]
            if fi == start:
                break
        new_faces.append(ring)
    return new_vertices, new_faces

Apply it twice and you get the cube back.

k: kis

Kis puts a point above the middle of every face and splits the face into triangles meeting there. A square becomes four triangles:

def kis(vertices, faces):
    """Raise a pyramid on every face."""
    new_vertices = list(vertices)
    new_faces = []
    for f in faces:
        apex = len(new_vertices)
        new_vertices.append(on_sphere(centroid([vertices[i] for i in f])))
        for a, b in zip(f, f[1:] + f[:1]):
            new_faces.append([a, b, apex])
    return [on_sphere(p) for p in new_vertices], new_faces

t: truncate, for free

Here's the nice thing. Truncating (cutting off every corner) doesn't need new code. Kis adds a point on every face; in the dual world, faces are corners. So t = dkd:

def truncate(vertices, faces):
    """Cut off every corner: dual, kis, dual."""
    return dual(*kis(*dual(vertices, faces)))

Quick check with Euler's formula, V − E + F = 2:

shape	V	E	F
cube	8	12	6
d cube	6	12	8
k cube	14	36	24
t cube	24	36	14

Drawing them

To draw a polyhedron: rotate it a little, drop the faces that point away from us, and colour the rest by how much they face the light. It prints an SVG, so there's nothing to install.

from math import cos, sin

def svg(vertices, faces, size=300, turn=(0.6, 0.5)):
    """Draw the faces that point at us, lighter when they face the light."""
    a, b = turn
    def rotate(p):
        x, y, z = p
        x, z = x * cos(a) + z * sin(a), -x * sin(a) + z * cos(a)
        y, z = y * cos(b) - z * sin(b), y * sin(b) + z * cos(b)
        return x, y, z
    points = [rotate(on_sphere(p)) for p in vertices]
    shapes = []
    for f in faces:
        p, q, r = (points[i] for i in f[:3])
        u = [q[i] - p[i] for i in range(3)]
        w = [r[i] - p[i] for i in range(3)]
        normal = (u[1] * w[2] - u[2] * w[1], u[2] * w[0] - u[0] * w[2], u[0] * w[1] - u[1] * w[0])
        if normal[2] <= 0:
            continue                       # facing away
        light = normal[2] / sqrt(sum(c * c for c in normal))
        pink = f'hsl(340, 55%, {45 + 40 * light:.0f}%)'
        corners = ' '.join(f'{size / 2 * (1 + 0.9 * points[i][0]):.1f},'
                           f'{size / 2 * (1 - 0.9 * points[i][1]):.1f}' for i in f)
        shapes.append(f'<polygon points="{corners}" fill="{pink}" '
                      f'stroke="#4b3a4f" stroke-width="1" stroke-linejoin="round"/>')
    return (f'<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 {size} {size}">'
            + ''.join(shapes) + '</svg>')

And now, art

Once the operators exist, chaining them is addictive. This is dktkt of a cube, a little ball of hexagons around a square:

c = cube()
with open('ball.svg', 'w') as f:
    f.write(svg(*dual(*kis(*truncate(*kis(*truncate(*c)))))))

Next time: more operators (ambo, gyro, snub) and making the faces flat again.