Taprats: Computer-Generated Islamic Star Patterns Architecture

This document points you at some of the highlights of the structure of Taprats, with references to classes in the source code.

Computational Geometry

Underneath the hood, Taprats relies heavily on some data structures from computational geometry. The most important abstraction in the system is the planar map (csk.taprats.geometry.Map). A planar map is a graph data structure: it maintains a collection of vertices (csk.taprats.geometry.Vertex), and a collection of edges (csk.taprats.geometry.Edge), where each edge joins two vertices. A planar map is a special kind of map where the vertices have positions in the two-dimensional plane and the graph is guaranteed to be planar -- when drawn, no two edges intersect.

The most important thing you can do with maps is merge them (Map.mergeMap and others). This involves combining the two maps, eliminating duplicate vertices, and splitting edges that cross over vertices or cross other edges. It's a challenging algorithm to write correctly and efficiently. My version is definitely not as efficient as is possible, but not too complicated either.


Taprats has a very limited understanding of tilings (unlike some of my other work). A tile (csk.taprats.tile.Feature) is a polygon. Taprats keeps track of regular polygons so it can put symmetric motifs in them later. A tiling (csk.taprats.tile.Tiling) is a collection of transformed tiles (csk.taprats.tile.PlacedFeature) together with two vectors. The tiles together define a translational unit, a set of tiles that can cover the whole plane through just translations. The two vectors are the translation vectors that make this happen. To fill a region, Taprats uses a modified polygon filling algorithm (csk.taprats.geometry.FillRegion) that transforms the viewing region into the coordinate system of the translation vectors. The unit squares inside the transformed region are the translational units to draw.


The package csk.taprats.app contains the code specific to the mathematics of Islamic ornament. A figure (csk.taprats.app.Figure) is an abstract base class for all objects that can be placed inside features. Basically, a figure represents the abstraction of a function producing Maps. Subclasses of Figure implement some of the common radially-symmetric Islamic motifs (csk.taprats.app.Star, csk.taprats.app.Rosette, and others) and a catch-all when the map is computed explicitly (csk.taprats.app.ExplicitFigure).

Features are paired up with figures in Design Elements (csk.taprats.app.DesignElement), which are then combined with tilings to yield all the information necessary to build a finished map (csk.taprats.app.Prototype).


Squares and features which aren't regular polygons don't have any default geometry associated with them. To obtain plausible geometry for these filler polygons, Taprats uses a big inference engine (csk.taprats.app.Infer). Infer encodes an algorithm for examining the figures bound to the featues that surround an empty feature. It finds edges that terminate at the boundary of the feature to fill, and tries to extend those edges until they meet up with each other. There's some black magic involed in deciding which intersections are better than others. The bottom line is that such algorithm simply cannot always work, no matter how many special cases are added. But for most common Islamic-like designs, the inference engine produces the "correct" inferred geometry.

Building the Design

Once the user has decided on geometry for all the features, the final design is built (Prototype.construct). Taprats tiles the region of interest using FillRegion. For each tile in the tiling, it looks up the figure associated with that tile and merges it into a growing map. The merging is optimized a bit for speed, which helps a lot over a previous version of the code. The resulting map is the final design.


The rendering algorithms are designed to work on the kinds of Maps produced by Taprats (i.e., every vertex has degree two or four and degree four vertices have edges that meet in a perfect "X"). They try to be as robust as possible against non-conforming maps -- the rest of the system might botch the build process. And some styles (like plain) can of course handle any map.

The styles involving thick lines (csk.taprats.ui.RenderOutline, csk.taprats.ui.RenderEmboss and csk.taprats.ui.RenderInterlace) rely on a little trig to figure out how to thicken the map edges. It's not unlike what postscript does to draw thick lines.


One "highlight" of the user interface (which doesn't need much explanation -- a large fraction of the code is used up setting parameters in GridBagConstraints) is the Signal class (csk.taprats.general.Signal). Rather than rely on the AWT for some event propagations, I tried to borrow the idea of signals from Gtk--, more specifically libsigc++. In this system, signals are public data members of objects that generate them. The upshot is that binding to them is more natural and straightforward, especially with C++ templates and operator overloading. In Java, it doesn't work so well. See the comments in Signal.java for more discussion.

Last modified: