CS 791: Assignment 2 - Symmetry and Celtic Knots

Overview

This webpage describes my implementation for part 3 of the assignment for creating Celtic knotwork. The report is organized as follows:

Implementation

Extensions

Results

Implementation

My implementation for this assignment was developed under Windows XP using C++. I used openGL for rendering and the Gtkmm libraries for the user interface. The Cairo graphics library is used to generate PDF files.

The Gtk application framework was based on donated code for CS 488 - specifically for assignment 3.

Interface

A simple user interface was created for the celtic knot program:

The menus are shown below:

The File menu allows for opening knot description files and writing knots as PDFs or as knot description files.
The Knot menu sets knot editing options:

Grid Size creates a new empty grid of a given size (forced to be even width and height).

Interlacing: Odd sets to odd interlacing mode.

Interlacing: Even sets to even interlacing mode (opposide of odd mode).

Borders On turns on all break markers along the outside edge of the grid.

Borders Off turns off all break markers along the outside edge of the grid.

Edit Break Markers switches to break marker editing mode.

Edit Cells Markers switches to cell editing mode.

Edit Square Corners switches to corner editing mode.

Clear clears the grid.

The Render menu sets rendering options:

The knot can be set to render as lines, ribbons with square corners or ribbons with curved corners.

The grid and break markers can be toggled on/off.

Rendering with different colours for separate knot strands can be turned on/off.

The render property dialog can be displayed which allows editing of knot and border widths and colours.

Algorithm

The technique described in Cromwell's paper is used to render Celtic-style knotwork. Each square in Cromwell's primal grid is split into four cells and the knot is rendered on a cell-by-cell basis. The contents of each cell is determined by how many of the cells edges are blocked by a break marker. Because of the layout of the grid and that break markers cannot intersect, each cell can have 0, 1 or 2 edges blocked, never 3 or 4.

There are four possibilities for cells with no borders, as shown to the right. They are really all just mirror images of each other with different interlacings.
There are 16 variations for cells with only one border - four posibilities (due to interlacing) for each of the four possible cell borders.
There are six variations for cells with two borders - two cases where opposite sides of the cell have a border (creating a "channel") and four where the borders form a corner.
These other cases are shown below.

Implementation Overview

Without getting into the nitty-gritty details, here's a basic summary of the main implementation classes:

PlaitCell - represents a cell, contails cell properties such as active borders, which knot strand is the main strand in the cell and which is the interlaced strand.
PlaitGrid - keeps track of all the cells in the grid, handles saving and loading of files, toggling of break markers and cells, selections and assigns knot strands (described in the extensions).
RenderTarget and PdfRenderTarget - these encapsulate the openGL and cairo rendering calls and are used by the knot renderers when rendering to draw to the appropriate device.
KnotRenderer - basic rendering of the knot as a single line, used for debugging, mainly.
RibbonKnotRenderer - inherits from KnotRenderer, renders the knot as an interlaced ribbon with square corners, handles knot properties common to it and curved knots such as ribbon and border width.
CurvedKnotRenderer - inherits from RibbonKnotRenderer, handles rendering of cells containing corners using curves.

Other classes in the implementation handle the UI and store render properties.

Rendering Details

Knots are rendered interactively using polygons and lines in openGL (and their equivalent when writing PDFs with cairo, though curved corners are rendered as paths with bezier curves). The width of a ribbon is specified as a percentage of a cell width (where cells are assumed to be square) and the ribbon border is a percentage of the ribbon width.

When drawing curved knots, the corners are drawn using cubic bezier curves as that is what cairo supports. When setting control points, I take the start, end and the point (where the knot enters and leaves the cell) and calculate where the ribbon lines would intersect for a "mid point"; the middle two control points are then set to be two-thirds of the way from one of the ends to the mid point. This is done both for the outer and inner edges of the knot.

Known Issues

These are as of the time of this writing. Time permitting, some of these may be addressed, but that seems unlikely.

Knot edges: because of line-capping, there are some "dents" along ribbon borders which is not too noticable with thin borders, but becomes more noticable with thicker borders. Experimenting with line-cap settings may alleviate this or drawing lines a little past their actual end points so that the overlap.
Cells: disabled cells are not saved when writing knot description files, also the editor allows cells to be toggled individually but really should be only toggled in 2x2 blocks (to match Cromwell's grids). These are fairly minor, striaghtforward issues to resolve, but as is it gets the idea across.
PDFs: there are some rendering artefacts in the PDF files that I have not had the opportunity to look into; basically, faint gaps are visible where the cell lines would be.

Extensions

As extensions, I implemented a user interface for interactively placing breakmarkers and modifying rendering parameters, I assign different colours to each unique strand in a knotwork, allow for individual cells to be disabled and allow for cells to be forced to draw squared corners.

The extensions are discussed in more detail on the extensions page.

Results

Some images are viewable on the results page.