Thursday, September 6, 2018

generating celtic knot patterns

This post describes an algorithm for generating celtic knot patterns - ornamental knots, links, and braids that are laid out in a grid, like the one below:

If you would rather skip reading about how these are generated and start playing around with creating patterns like the one above, please try out the editor and random knot-pattern generator that I've posted on my github pages.

I have tried out various strategies for generating these patterns (for example,  using tiles), but the method described here is closest to how I like to draw them by hand, as described in the book by Aidan Meehan, Celtic Design: Knotwork - The Secret Method of the Scribes. The variation offered here is intended to suggest how to write a program to generate these patterns based on a simplified version of the techniques in Meehan's book.

A knot pattern is made up of strands that represent string or chord, and the gaps between the woven strands. The technique described below actually involves drawing the gaps, with the strands emerging out of the negative space between the gaps. Essentially, a grid of dots are drawn, and lines are selectively drawn between adjacent dots - these become the gaps between the strands. Additional rules are applied to connect the dots to create a woven effect, and the dots are replaced with polygons to  create a more stylised effect.

1. define primary grid points
A knot pattern is laid out on a square coordinate system using a set of "primary" points that are set at one unit distances in the horizontal and vertical directions. We'll say that (0,0) is the top left corner of the grid, and the positive x direction is towards the right and positive y direction is down.  The dimensions of the primary grid must be odd (there must be a total odd number of dots in both the x and y directions). Because we are starting with (0,0) in the top left, the top right point (x, 0) must have x even (4 in the example below), and the bottom left point (0,y) must have y even (6 in the example below).

the primary grid

(Note: In Meehan's account, things are layered a little differently so what we are calling the primary grid is referred to as the tertiary grid.)

2. identify secondary grid points
Some of the points on the grid are special - these form a secondary grid. The special secondary grid points are those where both x and y values are even, or both are odd.

the secondary grid

In step 4 below, the secondary grid points where both x and y are even will be referred to as even nodes, and those that have both x and y odd will be referred to as odd nodes. The requirement to have the primary grid have odd dimensions (step 1) was needed to ensure that the corners of the pattern are all secondary points.

3. draw a quadrilateral around the nodes
Each node will become a gap in the node pattern - the basic shape of a gap is quadrilateral whose vertices lie 1/4 unit above, below, and to the right and left of each node.

the basic node polygon

With all of the polygons drawn for the nodes, we get a grid of 'diamonds' like this:

node polygons drawn for
secondary grid points

4. extend lines from node polygon vertices
To create a woven affect, we extend lines from the vertices of each node polygon

Doing this for all nodes creates an image like the one below.

lines extended from node
polygon vertices

If you exchange the rules for odd and even nodes, you end up with a correct "opposite" weave: strands that were going under instead go over, and vice-versa.

5. place barriers, drop lines
In the above image, the simple woven pattern seems to extend off the sides. To create an edge boundary for the pattern, and to create more interesting twists and turns, we follow some rules for drawing boundaries.

boundary rule 1: A boundary can connect any two non-diagonally adjacent nodes (secondary points), as long as rule 2 is not violated. The midpoint of a boundary segment will be a primary point.

boundary rule 2: A primary point cannot have more than one boundary going through it.

The example below shows boundaries drawn along the edge of the image, as well as some internal boundaries.
legal boundary examples, showing
primary and secondary points
(node polygons are hidden)

Now that we have introduced boundaries, we refine how lines are drawn coming out of the nodes (adjusting step 4):

node-line rule: Only draw a line from a node vertex if there is no boundary across from the vertex.

Applying the node-line rule, and drawing the polygons (and dropping the primary grid points) we get an image like the one below, where the weaving respects the boundaries - the strands (in white) that emerge seem to bounce off the edges and twist to avoid internal boundaries.

node polygons, boundaries, and lines 

6. refine node polygons
We can apply some styling rules to make the pattern look smoother - these changes to our original node polygon (step 3) will be based on whether or not there are boundaries next to the node.

node-style rule: Truncate (chop off) the vertex of a node polygon that is next to a boundary.

Below is the same pattern above, but with the node polygons following the node-style rule. You can see the effects of the rule most clearly by looking at the nodes near the edge of the image, and particularly the corner nodes.

pattern using truncated
node polygons

It is possible to add further adjustments to how the nodes and lines are drawn to create smoother looking knot patterns. I have experimented a bit, but have not obtained great results. Here's an example of the same patter above that adjusts the node polygons and line thicknesses:

a slightly different style applied
to the knot pattern

I hope you enjoy playing around with this - either implementing the process described above yourself or playing around with this version.