CS791 A2 Q3: Celtic Knotwork

Edgar Bering



Introduction

This page represents my submission for assignment two question three. In it I describe my implementation of a knotwork drawing program using the modified plaitwork described in Cromwell's article as well as the extension of this technique (it turned out that a complete re-write was an easier way to actually implement the extension) to drawing knotwork friezes along curving paths, a first step towards a knotwork based font decoration system. I then discuss future steps necessary to reach font decoration, a discussion that is likely to reappear in my project proposal. The svgs generated by this program are sufficiently lightweight that no png mode of this website is provided (unlike my submission for assignment 1).


The above rendering was done by creating several knotwork patterns with my program and assembling the outputs in Inkscape with some extra colouring and features added. Even though path intersection and sharp turns are not supported, the ability to create curved knotworks provides for artistic expressivity sufficent to begin to create designs evocative of the cross-carpet pages found in the Lindisfarne Gospels and other Celtic works. In this design we see demonstrations of P112.

Implementation

Language and Tools

I chose C as my implementation language; I considered Scheme, as the initial problem is rather abstract, there are nice bindings for my graphics library of choice, and it is a happy language, however I put some thought into my extension before starting, which changed my mind. As you will see, working on curved paths requires some numeric work, and I have never had much fun doing numerical programming in Scheme (though Gerald Sussman seems to have done well in SICM). I selected Cairo as a vector drawing library, it has a clean interface and is very versitile. For the basic implementation no other tools were used (or really necessary). In my extension I used some of the libraries described in Graphics Gems, namely Schneider's implementation of An Algorithm for Automatically Fitting Digitized Curves, p. 612-626, modified slightly to fit my purposes a bit better (only in organization of code, not in the algorithm, more on the algorithm in the extension section) and Glassner's utility vector library (a dependancy of Schneider's and also very useful).

Drawing Knots

Looking at Cromwell's paper and the suggestion on the assignment description one can see that a knot can be divided in to tiles, with the corners of the tiles formed by points in both the dual and primal grids (using Cromwell's terminology). Up to rotation and reflection there are only four types of tile: a corner, with two breaks in a corner; a straight piece, with two break marks on opposite sides; an elbow, with one break mark on a side; and a diagonal, with no breakmarks. In my implementation I have only 4 actual drawing routines, that draw these tiles in one orientation, relying on the cairo transformation stack to have the coordinite system set up so that the drawing routine just draws in a unit square.

In my program I have a notion of cell parity. This refers to the direction a strand in that cell would travel if unimpeded by break markers, cells of even parity go from bottom left to upper right, and odd are rotated by 90 degrees. Cells are drawn in rows alternating even and odd, starting with an even cell on even rows and an odd cell on odd rows. Exploiting this symmetry turns out to make interlacement determination rather easy.

With a set up drawing the four types of tile in the correct orientation complete, the remaining detail to add was an indication of interlacement. Since break markers preserve interlacement order, I simply had to choose an order on an unadultered plaitwork and determine each cell's crossing type in the absense of break markers. Looking at an unadultered plaitwork it is easy to see that on an even row, even cells go under in the top right, and odd cells go under in the bottom right, so the 90 degree rotational relation between even and odd cells is maintained, and the opposite corners pass under on an odd row. This meant that the only modification to the drawing routines needed to display interlacement was an indication of row parity and the appropriate foreshortening as if the cell were even (the routine calling the drawing routine dealt with rotating the coordinate system appropriately).

The simplicity of the drawing routines made the implementation of a few different line styles easy (as well as accomodating user selected line width and some ammount of colouring), and leaves the door open for more. At present I have implemented a 'Skeleton' style, an 'Outline' style, and a 'Ribbon' style, seen here in bands of the two sided frieze P112:




User Interface

Perhaps a more appropriate title for this section is "Lack of User Interface". My program reads in a knot description from an input specified on the command line, produces an output as specified on the command line, and has a bunch of terse switches to determine drawing style, ribbon width, outline width, colour, output size, etc. The invocation to create the ribbon seen above was:

knotwork -o p112-ribbon.svg -i knotwork-p112-band -w 1600 -h 200 -s -W.45 -L.1 -C17491a -R

As for interface to help with the design and placement of break markers, I invested in some sheets of graph paper, and for repition of translational units, a quick perl script. By modern standards this is not at all user friendly, and the program has much room for improvement, though in typical unix style a nice interface at this point could simply be a wrapper around the command line program written in a nicer language than C.

Extension

Extension Concept

My original idea for an extension was to implement drawing knotwork patterns on fonts in a way that could preserve frieze symmetries along strokes. This was inspired by Cameron Browne's paper Font Decoration by Automatic Mesh Fitting which produced the idea of a Celticly decorated font, but his method lacked an obvious way to guarantee preservation of symmetry; even starting with a symmetric figure can fail, see Fig 18a (left image) in his paper for an example. At the suggestion of Craig Kaplan I read the paper Skeletal Strokes by Hsu, Lee and Wiseman. The method described in Hsu's paper seems much more amicable to adaptation to knotwork. Hsu's approach focused on finding a global deformation of affine space around a curve that could then be used as a texture map to transfer an image to the new coordinate system. I took inspiration from this idea, and while not using a "skeletal stroke" exactly, came up with a method of mapping Cromwell's grids to paths and producing usable renderings of knotwork under these transforms. In the time for the assignment I did not reach a full font decoration, I completed what I consider the first major milestone: the drawing of knotwork on smooth paths composed of lines, arcs, and Bezier splines. In the next section I will discuss ideas for moving on to a system for decorating fonts.

Bending Knots

The basic idea was to take a smooth plane curve a(t) and simply transform the knot grid under (x,y) = a(x)+y*n(x), where n(x) is the unit normal to a(x); and the knot grid is in a suitable coordinate system to appear nicely. This sounds very nice theoretically, but can be an arbitrarily complex deformation of the input curve in each cell. Instead of trying to produce these deformations analytically I (with some direction again from Dr. Kaplan) instead approximated the deformed knot paths using Schneider's algorithm for curve fitting, found in Graphic Gems, to produce Bezier splines, which were then easily drawin with Cairo.

The paths were described peicewise, and in my proof of concept implementation only one segment was decorated at a time (this is discussed more later). The coordinate system I used had x vary from 0 to 1 along the path (possibly scaled to admit multiple repititions of a pattern), and y vary between -width/2 andwidth/2 with the width specified by the user. This admittedly has a disadvantage (other than the breaking into segments) in that in attempting regular spacing of grid elements I have assumed a unit-speed parametrization of the path segment, which almost never happens in practice. Also in practice this hasn't seemed to matter much, with the distortion produced feeling natural. A way of overcoming this is discussed later.

Implementation Details

Implementing this extension turned out to be easiest as a complete re-write of my original program, identical in spirit but with a different approach to the drawing. The reason for this is to approximate transformed strand paths I first needed a sample of points, then Schneider's FitCurve function would call back to something to draw the resulting Bezier spline. So, where in the old program the knotwork cell was drawn, in this program a set of samples was generated and returned which were then passed to the curve fitting function. In the draw callback, instead of actually drawing the next curve, I simply added it to the current Cairo path, and after FitCurve returned (indicating the full spline had been 'drawn') this combined path was then stroked. In my current implementation stroke width is not scaled; this is not a limitation, in looking at the Lindisfarne Gospels and the Book of Kells stroke width distortion is not observed in knotworks decorating round paths.

For simplicity, only the skeleton style of knotwork was written in this new form. Ribbons and outlines could be brought along using the same technique, with care taken while drawing ribbons to ensure paths are closed and filled at the right time in the drawing process.

Paths were described in a text in the following format:

As paths do not have to close back on themselves, the knotwork description was modified. The input is now a text file with 3 lines, the first indicating a knotwork description of a startcap, the second a description of a translational unit, the last an endcap knot (the user can ignore these and place a complex band pattern in the translational unit and tell the program the path is closed to disable this). The user is also in control of the number of repititons of a translational unit of a frieze along each segment (as stated previously at present each segment is treated seprately). An example invocation might look like:

./knotwork -o p211-circle.svg -k knotwork-spec-p211 -a circlepath -w 600 -h 600 -s -r27 -W 1.5 -L.12

And as you can probably guess, will produce a circle that if cut and flattened out would be a frieze with frieze group P211, thusly:


Two renderings of a first attempt at a letter 'S' (really just two semi circles stuck together). This illustrates the endcapping, as well as the implementation's correct preservation of the unit normal to the path (a more naive approach would produce a mirror reflection at the join between the two semicircles):

P121
P222

Note how the diagonals of P222 transform in the coordinate space of the 'S' becoming smooth arcs, retaining continuity through breaks for interlacement, and the smooth transition between the two path segments in both images.

Limitations

The careful reader will notice that I said 'smooth' plane curves. I did in fact mean smooth, in the sense that the tangent directions agree at joint points. My current implementation does not support sharp corners. Sharp corners pose a unique problem, and interfere with the other major limitation: they make it difficult to preserve symmetry, to do a 45 degree mitre symmetricly the artist is required to have a pattern that satisfies:

where the light green section is a a 90 degree clockwise rotation of the dark green section, and a similar relation holds between the orange sections. This only gets 45 degree mitres, and the relation holding breaks others. It also requires that the end of a translational unit to land on the joint, vastly increasing the difficulty of spacing translational units evenly along the entire path instead of just a path segment, working contrary towards fixing the second limitation.

The second limitation is of course that at present my implementation treats each path segment seprately and draws translational units along the individual segment, in a quantity specified by segment. This is OK, but the more elegant solution is to reparameterize the entire path by arc length, giving a unit speed parametrization, and by extension an even spacing of translational units along the entire input path. This reparameterization was somewhat within reach, but I did not find time to implement it.

General Font Decoration

I fell short of my goal of implementing a general font decoration, however decorating smooth paths is a good first step. In this section I will discuss some ideas I had for moving closer to a full font-decoration scheme.

The next logical step is to handle mitre joints in a sensible fashion, though noting the earlier discussion this presents issues with symmetry preservation. Looking at original Celtic art one sees that mitre joints were often handled in the following manner: a square join knotwork was illustrated using motifs evocative of the surrounding symmetry, with a translational unit exiting each corner. A method to allow the user to specify these joins, and correctly line up the ends of translational units is certainly one approach. This could possibly generalize to non right-angled mitres by simply shearing the square join. This does seem to be a solution used by Celtic artists (indeed examples of corners being pinched outward intentionally can be seen as well) to some degree.

More complex intersections follow mitres. A perpendicular crossing could be handled by simply placing a user specified grid similar to the mitre case, and non perpendicular crossings produced by shearing. Non-perpendicular T-joins probably can't be handled by shearing a perpindicular user case: in examining Celtic works I've found that when a non-perpendicular T occurs the edge that does not continue through the intersection is subordinate to the join, often with a frieze continuing past the join with only the boundary perturbed. Producing this effect will take more thought.

Once mitres, crossings, T-joins, and multiple strokes are implemented a full font could be drawn, and focus turned to rendering styles, user interface, etc. Another direction is to handle variable widths. While not lending itsself easily to symmetry, Browne's method does handle variable width characters very nicely, paring down the knotwork grid bit by bit as the width changes. Creating this effect automatically from one frieze translational unit might be accomplished by removing pairs of rows in the underlying grid, though my intuition is that this will inadvertently add or remove symmetries to a pattern and potentially destroy the artist's intent. A labor intensive alternative is to have the artist specify the removal order for rows, but I still believe there is an automated solution.

A few more samples

A first attempt at typography

A composite illuminated letter

This examples was composed using a few runs of the program and inkscape. The frieze in the strokes has symetry group P2'11