Polygonal Tessellation

Now that I've got the hang of quickly drawing lots of shapes with shader instancing, what should I draw? All that geometric repetition got me thinking about the artwork of M. C. Escher, which led me to this page about regular and semi-regular tessellation. The diagrams near the bottom looked nice, so I started playing with drawing similar images with XNA code.

Regular tessellations are tessellations of the plane with a single regular polygon. This is only possible with triangles, squares, and hexagons. Things get more interesting when you allow multiple kinds of polygons. Semiregular tessellations have the same sequence of polygons around each vertex, such as (4, 6, 12) for a square, hexagon, and dodecagon. There are eight possible semiregular tessellations.

To draw these, I first needed to make meshes for various polygons: squares, hexagons, octagons, etc. And I needed to be able to move and rotate them around relative to each other. Rather than gobs of the usual sines and cosines, I thought I'd try using turtle graphics, like the old Logo programming language. Here's my quick and dirty turtle class:

public class Turtle
    public Vector2 pos = Vector2.Zero;
    public float theta = 0;
    public void Reset()
        pos =
        theta = 0;
    public void Fwd(float amt)
        Vector2 delta = new Vector2(amt * (float)Math.Cos(theta), amt * (float)Math.Sin(theta));
        pos += delta;
    public void RotRadians(float radians)
        theta += radians;
    public void RotDegrees(float degrees)

So that was handy, both for creating polygons and for placing them relative to each other. Note that the origin of the polygon meshes is at one of the vertices, rather than in the center. That made it easy to place several polygons that share a vertex. (That is, they mathematically share a vertex in the tessellation...they don't share Direct3D vertices when they are rendered).

I separated my mesh code from the InstancedShapeManager, so I could pass various different polygons to a single shape manager for drawing. I still kept separate lists for all the squares, all the hexagons, etc., and draw all polygons of a given type at once.

The actual algorithm for generating the tessellations is a bit of a hack. I start at a vertex and rotate around, placing polygons as specified by the tessellation type. For example, for a (3, 4, 6, 4) tessellation, I would place a triangle, rotate 60 degrees, place a square, rotate 90 degrees, place a hexagon, rotate 120 degrees, and place a square. After placing each polygon, I'd enqueue a "task" to handle the vertex one unit away from the current vertex at the current orientation. When the current vertex was finished, I'd dequeue the next task and repeat the process. The neighboring vertices would have to start from a different orientation, which I called the "magic rotation" value and determined by trial and error. There's probably a simple way to derive it, but I didn't come up with it.

I had to add code to keep from re-adding vertices which were already processed (or in the task queue), and also to keep from placing polygons where one had already been placed.

I show square markers to represent unfinished vertex tasks. The green marker shows the current task, and red markers are enqueued tasks. When a task is complete, I remove the marker.

I use arbitrary hues to color each polygon -- again, there's probably a clever algorithm for coloring them such that adjacent polys are not the same color -- but I didn't go there.

The result is fun to watch, as the tessellation grows from the center point.

I didn't get some of the tessellations working, such as (4, 6, 12). With these, some vertices are (4, 6, 12) and others are (12, 6, 4). I was able to cope with that, but then I couldn't come up with magic rotation values to make the subsequent polygons appear in the right place. Oh well.

I'm probably not going to do anything further with this tessellation code (though it might be fun to try some hyperbolic tessellations), but it was fun to make some pretty pictures.




Skip to main content