A method for computer generated Celtic knot patterns. This prototype tool was built using Houdini software. The implemented algorithm is based on a paper titled Computer Generated Celtic Design, by Matthew Kaplan and Elaine Cohen.

As always the project files are available for members of my Pateron page.

Algorithm outline

Input: A Planar Graph

For each midpoint on an input edge:

1. Compute a normal vector, N, and store four vectors at 45-degree angles from it.

2. For two vectors on the right side of the normal vector (green), locate a current edge point in that direction.

3. Using this edge point as a pivot, find the next edge connected to it in the clockwise order.

4. Create a curve by interpolating between the starting midpoint and the midpoint on the next found edge. Before interpolation, offset the start and end points in the opposite directions along vertical axis to produce weaving effect.
triangle with calculated normals at midpointsinterpolating curves


MathJax example
The interpolation step in the algorithm involves cubic Hermite interpolation, a specific method chosen due to its requirement for only specifying endpoint vectors and their tangents.

Consider p0 as the starting point in the image below. According to the algorithm, the endpoint is p1, located at the midpoint of the next clockwise edge. It's important to note that if we initiate the direction along the right outward vector (m0), the tangent at our endpoint should align with the left inward vector (m1). Once the variables p0, p1, m0, and m1 are established, the interpolation can be done using the formula below.
$\overrightarrow{p}(t) = (2t^3 - 3t^2 + 1)\overrightarrow{p0} +  (t^3 - 2t^2 + t)\overrightarrow{m0}$
$ +  (-2t^3 +3t^2)\overrightarrow{p1}+  (t^3 - t^2)\overrightarrow{m1}$

where $t \in [0,1]$

$\overrightarrow{p}(t) = (2t^3 - 3t^2 + 1)\overrightarrow{p0} +  (t^3 - 2t^2 + t)\overrightarrow{m0} +  (-2t^3 +3t^2)\overrightarrow{p1}+  (t^3 - t^2)\overrightarrow{m1}$
where $t \in [0,1]$

cubic hermite interpolation between two points