Publications

Disparity maps are integral to the fields of computer vision and computer graphics, with many applications in robotics, path planning, computerized drawing, 3D viewing, and more. Stereo algorithms can be used to synthesize disparity maps from stereo image pairs. Unfortunately, most methods to assess disparity map quality rely on a ground-truth disparity map, which is not always available. This paper introduces a method to evaluate disparity map generation algorithms that does not require ground truth, and is instead based on the quality of the disparity maps themselves. This novel scoring metric assesses each pixel in a given disparity map and then provides an overall score for the disparity map. The score is both a visual representation—where each color encodes an error or potential error—and a numerical score. This novel scoring metric is used to compare two top-ranking disparity map generators in different scenarios. Our scoring method yields results consistent with intuition and also uncovers, and helps in resolving, an issue with one generator. Finally, RANSAC plane-fitting is used to automatically inpaint unknown regions and thereby improve the usability of disparity maps in applications such as non-photorealistic rendering, layer-based stereo methods, and warping.

A periodic strip is a finite-width strip of tiles that repeats in one direction with frieze symmetry. They have many potential applications in art and design, particularly because of the ability to construct a finite portion of a periodic strip and wrap it seamlessly around a cylinder. I show that under very mild conditions, shapes that tile the plane also admit periodic strips of any desired width. This fact is true even for aperiodic tile sets. I explain why periodic strips exist, give simple methods for constructing them, and show examples for a variety of well known tilings.

Many traditional Islamic geometric patterns feature a single large rosette surrounded by a ring of eight satellite rosettes. We present a technique for constructing patterns in this style, which scales to rosettes larger than those executed historically. We decompose the regions between these rosettes into different characteristic regions called basic shapes, and show how to fill each basic shape with polygons that are close to regular, suitable for motif construction using the polygons-in-contact method.

I show how to express the question of whether a polyform tiles the plane isohedrally as a Boolean formula that can be tested using a SAT solver. This approach is adaptable to a wide range of poly-forms, requires no special-case code for different isohedral tiling types, and integrates seamlessly with existing software for computing Heesch numbers of polyforms.

We design and evaluate Mindful Scroll, a mobile application for mindfulness that encourages a slow and deliberate approach to colouring. The app renders an infinite scroll of generated geometric tilings that reveal pseudo-random colour palettes and fill effects when coloured using a finger or pen. A five-day study (N=28) evaluated the efficacy of the app in reducing anxiety and enhancing mindfulness. The results indicate that the app is capable of promoting a greater sense of mindfulness over time and produced similar results across several measures compared to traditional structured colouring and existing mindfulness-based mobile applications. All participants expressed a desire to use the app again, with a majority stating they felt more mindful after the study.

The quest for the einstein tile—a shape never seen before in mathematics—turned up even more discoveries than mathematicians counted on

The diffraction pattern from the recently reported aperiodic `einstein', or `hat', monohedral tiling [Smith et al. (2023). arXiv:2303.10798v1] has been analyzed. The structure is the hexagonal mta net, a kite tiling, with aperiodic vertex deletions. A large model's diffraction pattern displays a robust sixfold periodicity in plane group p6. A repeating, roughly triangular motif of `diffused intensity' arises between the strongest Bragg peaks. The motif contains high-density regions of discrete `satellite' peaks, rather than continuous `diffuse scattering', breaking mirror symmetry, consistent with the chiral hat tiling.

The recently discovered "hat" aperiodic monotile mixes unreflected and reflected tiles in every tiling it admits, leaving open the question of whether a single shape can tile aperiodically using translations and rotations alone. We show that a close relative of the hat -- the equilateral member of the continuum to which it belongs -- is a weakly chiral aperiodic monotile: it admits only non-periodic tilings if we forbid reflections by fiat. Furthermore, by modifying this polygon's edges we obtain a family of shapes called Spectres that are strictly chiral aperiodic monotiles: they admit only chiral non-periodic tilings based on a hierarchical substitution system.

A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical--and hence aperiodic--tilings.

To a person with colour vision deficiency (colour blindness), some pairs of colours that other people can easily tell apart will be perceived as similar or identical. In the right context, this deficiency can be harnessed as an unusual ability. In particular, some combinations of colours can serve as camouflage, allowing a design to conceal information that is nearly invisible to a viewer with normal colour vision, but comprehensible by someone with the right form of colour vision deficiency. I explore the possibility of using dichromatic vision as a vehicle for a subtle form of steganography, present tools for processing digital images to achieve this effect, and discuss the possibilities of this rather specialized aesthetic domain.

A common text layout style is a "packed rectilinear layout", in which non-overlapping word bounding boxes are packed so that their union forms a rectangle with no holes other than word and line spacing. Designing variations of these layouts while preserving word emphasis is a difficult and time-consuming process. We present a display text layout algorithm in which designers specify parameters that control the visual emphasis of words in these layouts. The number of possible layouts for a phrase follows the sequence of Big Schröder numbers as our algorithm involves the recursive subdivision of a rectangular bounding box. We conducted semi-structured interviews with graphic design experts to better understand their design decisions in creative typesetting. They rated the best-fitting layouts generated by our system to be very similar to designs that they would have created themselves.

Cooperative play, or “co-play”, is the act of playing with others in a co-located setting, including co-location of avatars in virtual reality (VR). Customizability is the degree to which play artifacts like props can be changed to suit different needs, a factor of co-play which is easier to support in VR than in the real world. We present the results of a preliminary user study that explores how different levels of customization affect creativity in a two-person VR co-play setting. Using the Creativity Support Index, system logs, and observations, we found that increasing customizability of props used to improvise a story trended toward higher levels of perceived creativity. Our work introduces a new topic of investigation for social VR together with a study methodology and initial results to motivate further investigation.

A shape's Heesch number is the number of layers of copies of the shape that can be placed around it without gaps or overlaps. Experimentation and exhaustive searching have turned up examples of shapes with finite Heesch numbers up to six, but nothing higher. The computational problem of classifying simple families of shapes by Heesch number can provide more experimental data to fuel our understanding of this topic. I present a technique for computing Heesch numbers of nontiling polyforms using a SAT solver, and the results of exhaustive computation of Heesch numbers up to 19-ominoes, 17-hexes, and 24-iamonds.

In this paper, we present a simple method to produce a colour palette for film trailers. Our method uses k-means clustering with a saturation-based weighting to extract the dominant colours from the frames of the trailer. We use our method to generate the palettes of 29 thousand film trailers from 1960 to 2019. We aggregate these palettes by era, genre, and director by re-applying our clustering method, and we note various trends in the use of colour over time and between genres. We also show that our generated palettes reflect changes in mood and theme across films in a series, and we demonstrate the palettes of notable directors.

Background Gesture drawing is a type of fluid, fast sketch with loose and roughly drawn lines that captures the motion and feeling of a subject. Although style transfer methods, which are able to learn a style from an input image and apply it to a secondary image, can reproduce many styles, they are currently unable to produce the flowing strokes of gesture drawings. Method In this paper, we present a method for producing gesture drawings that roughly depict objects or scenes with loose dancing contours and frantic textures. By following a gradient field, our method adapts stroke-based painterly rendering algorithms to produce long curved strokes. A rough, overdrawn appearance is created through a progressive refinement. In addition, we produce rough hatch strokes by altering the stroke direction. These add optional shading to gesture drawings. Results A wealth of parameters provide users the ability to adjust the output style, from short and rapid strokes to long and fluid strokes, and from swirling to straight lines. Potential stylistic outputs include pen-and-ink and colored pencil. We present several generated gesture drawings and discuss the application of our method to video. Conclusion Our stroke-based rendering algorithm produces convincing gesture drawings with numerous controllable parameters, permitting the creation of a variety of styles

I present a technique for generating random self-contained compositions in the style of zellij patterns, a type of Islamic geometric pattern found in Morocco and southern Spain. I use a multigrid dualization method to generate a random arrangement of polygons, and fill each polygon with a precomputed patch of zellij tile shapes.

In art, hatching means drawing patterns of roughly parallel lines. Even with skill and time, an artist can find these patterns difficult to create and edit. Our new artistic primitive—the hatching shape—facilitates hatching for an artist drawing from imagination. A hatching shape comprises a mask and three fields: width, spacing, and direction. Streamline advection uses these fields to create hatching marks. A hatching shape also contains barrier curves: deliberate discontinuities useful for drawing complex forms. We explain several operations on hatching shapes, such as the multi-dir operation, an easy way to depict 3D form using a hatching shape’s direction field. We also explain the modifications to streamline advection necessary to produce hatching marks from a hatching shape.

Islamic geometric patterns often feature symmetric motifs like stars or rosettes. Historical designs include motifs with up to 96 points, but traditional construction techniques make it difficult to go higher. We present a simple polygons-in-contact method for constructing designs around a large central motif with any number of points. The method surrounds a large central polygon with conformally mapped layers of smaller tiles. The fidelity of the final design improves as the central motif grows.

The regular tiling by squares can be unfolded by placing hinges at the vertices of tiles, connecting squares to their neighbours. The hinges open continuously to reveal rhombs, which grow into squares and then close up again. The intermediate square tiling offers an opportunity to create an animated loop, but colouring the tiles in that loop so that adjacent tiles never share a colour offers some interesting mathematical challenges. I discuss how many colours are required to permit a looping animation of unfolding squares, and demonstrate a few such loops.

We present a method to produce stylized drawings from stereoscopic 3D (S3D) images. Taking advantage of the information provided by the disparity map, we extract object contours and determine their visibility. The discovered contours are stylized and warped to produce an S3D line drawing. Since the produced line drawing can be ambiguous in shape, we add stylized shading to provide monocular depth cues. We investigate using both consistently rendered shading and inconsistently rendered shading in order to determine the importance of lines and shading to depth perception.

A picture frame in two dimensions is a rectangular array of symbols, with at least two rows and columns, where the first and last rows are identical, and the first and last columns are identical. If a coloring of the plane lattice has no picture frames, we call it frameless. In this note, we show how to create a simple 2-coloring of the plane lattice that is frameless.

We present AnimationPak, a technique to create animated packings by arranging animated two-dimensional elements inside a static container. We represent animated elements in a three-dimensional spacetime domain, and view the animated packing problem as a three-dimensional packing in that domain. Every element is represented as a discretized spacetime mesh. In a physical simulation, meshes grow and repel each other, consuming the negative space in the container. The final animation frames are cross sections of the three-dimensional packing at a sequence of time values. The simulation trades off between the evenness of the negative space in the container, the temporal coherence of the animation, and the deformations of the elements. Elements can be guided around the container and the entire animation can be closed into a loop.

Bobbin lace is a fibre art form in which threads are braided together to form a fabric, often with a very detailed and complex design. In traditional practice, each region of the fabric is filled with a periodic texture. We establish the groundwork for non-periodic lace patterns and present three new quasiperiodic families based on Sturmian words, the Penrose tiling by thick and thin rhombs and the Ammann-bar decoration of the Penrose tiling.

Image vectorization is one of the primary means of creating vector graphics. The quality of a vectorized image depends crucially on extracting accurate features from input raster images. However, correct object edges can be difficult to detect when color gradients are weak. We present an image vectorization technique that operates on a color image augmented with a depth map and uses both color and depth edges to define vectorized paths. We output a vectorized result as a diffusion curve image. The information extracted from the depth map allows us more flexibility in the manipulation of the diffusion curves, in particular permitting high-level object segmentation. Our experimental results demonstrate that this method achieves high reconstruction quality and provides greater control in the organization and editing of vectorized images than existing work based on diffusion curves.

We present a method to fill a container shape with deformable instances of geometric elements selected from a library, creating a 2D artistic composition called an element packing. Each element is represented as a mass-spring system, allowing it to deform to achieve a better fit with its neighbours and the container. We start with an initial placement of small elements and gradually transform them using a physics simulation that trades off between the evenness of the packing and the deformations of the individual elements. Unlike previous work, elements can be given preferred orientations, and we can use shape matching to control the initial placement of elements in tight convex corners. We also explore the creation of tileable packings, and validate our approach using statistical measurements of the distributions of positive and negative space in packings. Our method produces compositions in which the negative space between elements is approximately uniform in width, similar to real-world examples created by artists.

We define hatching-a drawing technique-as rigorously as possible. A pure mathematical formulation or even a binary this-or-that definition is unreachable, but useful insights come from driving as close as we can. First we explain hatching's purposes. Then we define hatching as the use of patches: groups of roughly parallel curves that form flexible, simple patterns. After elaborating on this definition's parts, we briefly treat considerations for research in expressive rendering.

Inspired by abstract mathematical animated loops like those created by David Whyte (@beesandbombs), I explore animations based on isohedral tilings. I present a complete interactive tool for designing tiling animations, and show a few results that I have obtained using this tool.

Symmetrical protein cages have evolved to fulfil diverse roles in nature, including compartmentalization and cargo delivery1, and have inspired synthetic biologists to create novel protein assemblies via the precise manipulation of protein–protein interfaces. Despite the impressive array of protein cages produced in the laboratory, the design of inducible assemblies remains challenging2,3. Here we demonstrate an ultra-stable artificial protein cage, the assembly and disassembly of which can be controlled by metal coordination at the protein–protein interfaces. The addition of a gold (i)-triphenylphosphine compound to a cysteine-substituted, 11-mer protein ring triggers supramolecular self-assembly, which generates monodisperse cage structures with masses greater than 2 MDa. The geometry of these structures is based on the Archimedean snub cube and is, to our knowledge, unprecedented. Cryo-electron microscopy confirms that the assemblies are held together by 120 S–Aui–S staples between the protein oligomers, and exist in two chiral forms. The cage shows extreme chemical and thermal stability, yet it readily disassembles upon exposure to reducing agents. As well as gold, mercury(ii) is also found to enable formation of the protein cage. This work establishes an approach for linking protein components into robust, higher-order structures, and expands the design space available for supramolecular assemblies to include previously unexplored geometries.

We present a method to fill a container shape with deformable instances of geometric elements selected from a library, creating a 2D artistic composition called an element packing. Each element is represented as a mass-spring system, allowing them to deform to achieve a better fit with their neighbours and the container. We start with an initial random placement of small elements and gradually transform them using repulsion forces that trade off between the evenness of the packing and the deformations of the individual elements. Our method produces compositions in which the negative space between elements is approximately uniform in width, similar to real-world examples created by artists. We validate our approach by performing a quantitative study using spatial statistics.

Most mathematical marbling simulations generate patterns for texture mapping and surface decoration. We explore the application of three-dimensional deformations inspired by mathematical marbling as a suite of tools to enable creative shape design. Our tools are expressed as analytical functions of space and are volume-preserving vector fields, meaning that the modelling process preserves volumes and avoids self-intersections. Complicated deformations are easily combined to create complex objects from simple ones. To achieve smooth and high-quality shapes, we also present a mesh refinement and simplification algorithm adapted to our deformations. We show a number of examples of shapes created with our technique in order to demonstrate its power and expressiveness.

Rinus Roelofs has exhibited numerous planar and polyhedral sculptures made up of two layers that weave over and under each other to form a single connected surface. I present a technique for creating sculptures in this style that are inspired by the geometric structure of Islamic star patterns. I first present a general approach for constructing interwoven two- layer sculptures, and then specialize it to Islamic patterns in the plane and on polyhedra. Finally, I describe a projection operation that bulges the elements of these designs into undulating dome shapes.

We present a technique for drawing ornamental designs consisting of placed instances of simple shapes. These shapes, which we call elements, are selected from a small library of templates. The elements are deformed to flow along a direction field interpolated from user-supplied strokes, giving a sense of visual flow to the final composition, and constrained to lie within a container region. Our implementation computes a vector field based on user strokes, constructs streamlines that conform to the vector field, and places an element over each streamline. An iterative refinement process then shifts and stretches the elements to improve the composition.

In this paper, we consider orthogonal closed paths that dwell on the edges of square grids. A certain subset of these paths are called “poppies.” We derive a formula for the number of asymmetrical poppies on an n by n grid, and we explore the aesthetics of the poppies.

When points are distributed evenly on a hypocycloid path and animated along that path, they can be seen as clustering together into “wheels”, groups of points that lie at the vertices of regular polygons and that rotate in synchrony. In some cases the points can group into two different sets of wheels, rotating in opposite directions. I derive formulas that predict the number of such wheels and the number of points on each one. The resulting animations are visually compelling and reminiscent of the motion of balls or clubs in multi-person juggling patterns

We introduce Modular Origami Halftoning, a set of techniques for representing continuous-tone greyscale images using a fixed set of origami modules folded from two-coloured paper. By arranging the modules to reveal different amounts of the paper's coloured side, each module can approximate the brightness of a single pixel from an image. We present two variations based on affixing a grid of disconnected modules to a backing, and one variation in which the modules interlock into a carpet, requiring no tape or glue.

The assembly of the chiral pentagonal-star-shaped 1,3,5,7,9-pentaphenylcorannulene on a Cu(111) surface has been studied with scanning tunneling microscopy. Two different long-range ordered phases coexist at 60 K, most likely racemic and homochiral phases. The principal motifs emulate a network of meshed gears. One of the observed structures resembles the densest packing of five-fold symmetric stars.

A reconfigurable maze is a small set of modular components, called tiles, that can be assembled into a variety of distinct mazes. Although the idea of a reconfigurable maze is simple enough to articulate, there are some difficult mathematical challenges to overcome in order to make them a reality. I introduce the concept of a reconfigurable maze, and work through the design of a first prototype based on a 2 x 2 grid of square tiles. The prototype is a partial solution to the original problem, leaving open many opportunities for future innovation.

We describe the conception and construction of E Pluribus Unum, a large-scale artwork that combines text and geometry to depict over a million names of global organizations dedicated to social and environmental causes. The names are rendered in small type along lines arranged symmetrically in a disc. We examine the aesthetic choices involved in designing the artwork, and the technical challenges we faced in laying out and rendering a monumental amount of text.

We present a method for stylizing stereoscopic 3D images that guarantees consistency between the left and right views. Our method decomposes the left and right views of an input image into discretized disparity layers and merges the corresponding layers from the left and right views into a single layer where stylization takes place. We then construct new stylized left and right views by compositing portions of the stylized layers. Because the new left and right views come from the same stylized source layers, our method eliminates common stylization artifacts that cause viewer discomfort. We also present a stereoscopic 3D painterly rendering algorithm tailored to our layer-based approach. This method uses disparity information to assist in stroke creation so that strokes follow surface geometry without ignoring painted surface patterns. Finally, we conduct a user study that demonstrates that our approach to stereoscopic 3D image stylization leads to images that are more comfortable to view than those created using other techniques.

Inspired by the results of recent studies on the perception of geometric textures, we present a patch-based geometric synthesis algorithm that mimics observed synthesis strategies. Our synthesis process first constructs an overlapping grid of copies of the exemplar, and then culls individual motifs based on overlaps and the enforcement of minimum distances.

In recent years, an increasing number of example-based Geometric Texture Synthesis (GTS) algorithms have been proposed. However, there have been few attempts to evaluate these algorithms rigorously. We are driven by this lack of validation and the simplicity of the GTS problem to look closer at perceptual similarity between geometric arrangements. Using samples from a geological database, our research first establishes a dataset of geometric arrangements gathered from multiple synthesis sources. We then employ the dataset in two evaluation studies. Collectively these empirical methods provide formal foundations for perceptual studies in GTS, insight into the robustness of GTS algorithms and a better understanding of similarity in the context of geometric texture arrangements.

Pixel artists rasterize vector shapes by hand to minimize artifacts at low resolutions and emphasize the aesthetics of visible pixels. We describe Superpixelator, an algorithm that automates this process by rasterizing vector line art at a low resolution pixel art style. Our technique successfully eliminates most rasterization artifacts and draws smoother curves. To draw shapes more effectively, we use optimization techniques to preserve shape properties such as symmetry, aspect ratio, and sharp angles. Our algorithm also supports "manual antialiasing," the style of antialiasing used in pixel art. Professional pixel artists report that Superpixelator's results are as good, or better, than hand-rasterized drawings by artists.

I explore a space of geometric, decorative corner designs based on paths through a square grid. I discuss the problems of enumerating corners of a given size efficiently, and exploring them interactively in software. I then impose a higher-level connectivity constraint on corners and discuss the effect of this constraint on the mathematical and aesthetic properties of corner designs.

We describe a tiling approach to animating line-based Op Art. The tiling must be seamless along the tile edges, and we seek to minimize the number of bidirectional tiles because they interfere with the Op Art illusion. We introduce several algorithms for creating these tilings, and demonstrate that an optimal tiling can be found in polynomial time. Examples of animated Op Art can be found on our website https://sites.google.com/site/tiffanycinglis/research/animating-line-based-op-art.

Hand made and computer generated drawings usually place marks with regard only for the role they play in communicating the overall content of the drawing. However, novel drawing styles emerge when extra constraints are applied to force the marks themselves to behave in an eye-catching way. I explore three drawing styles based on complex geometric relationships between paths: continuous line drawing with a closed loop, drawings from tree structures, and mazes that depict images.

A common technique in Op Art is the use of densely packed line segments to depict simple shapes such as circles and squares. Some artists have attempted to create more complex images using this technique but are faced with the difficulty of avoiding undesirable artifacts such as line breaks and T-junctions within their artworks. We introduce an algorithm that takes an arbitrary image and automatically generates the corresponding Op Art composition in this style. For 2-colour images, the algorithm produces artworks without any unwanted artifacts; for images with more colours, the basic algorithm cannot guarantee the removal of all artifacts, but we use a global optimisation technique to minimise their number. We also examine the use of curves in creating the illusion of 3D forms and present a corresponding algorithm based on a physical simulation of heat flow. The algorithms for generating Op Art with straight lines and with curves can be combined to create an interesting new style of art. The results have applications in graphic design, puzzle creation and non-photorealistic rendering.

Inspired by Gothic-influenced architectural styles, we analyze some of the circle patterns found in rose windows and semi-circular arches. We introduce a recursive circular ring structure that can be represented using a set-like notation, and determine which structures satisfy a set of tangency requirements. To fill in the gaps between tangent circles, we add Appollonian circles to each triplet of pairwise tangent circles. These ring structures provide the underlying structure for many designs, including rose windows, Celtic knots and spirals, and Islamic star patterns.

Inspired by Gothic-influenced architectural styles, we analyze some of the circle patterns found in rose windows and semi-circular arches. We introduce a recursive circular ring structure that can be represented using a set-like notation, and determine which structures satisfy a set of tangency requirements. To fill in the gaps between tangent circles, we add Appollonian circles to each triplet of pairwise tangent circles. These ring structures provide the underlying structure for many designs, including rose windows, Celtic knots and spirals, and Islamic star patterns.

We present a method for stylizing stereoscopic 3D images that guarantees consistency between the left and right views. Our method decomposes the left and right views of an input image into discretized disparity layers and merges the corresponding layers from the left and right views into a single layer where stylization takes place. We then construct new stylized left and right views by compositing portions of the stylized layers. Because the left and right views come from the same source layers, our method eliminates common artifacts that cause viewer discomfort. We also present a stereoscopic 3D painterly rendering algorithm tailored to our layer-based approach. This method uses disparity information to assist in stroke creation so that strokes follow surface geometry without ignoring painted surface patterns. Finally, we conduct a user study that demonstrates that our approach to stereoscopic 3D image stylization leads to images that are more comfortable to view than those created using other techniques.

I present a technique for constructing self-similar curves from smooth base curves. The technique is similar to that used in Iterated Function Systems like the Koch curve, except that it does not require a piecewise linear path in order to induce a set of similarities. I explain the mathematical machinery behind the technique, describe a practical numerical approximation that can be implemented in software, and show some results.

Sudoku, the popular logic puzzle, would have a greater artistic appeal if the final completed puzzle could be transformed into an image similar to nonogram outputs. To do this, we solve a mixed-integer nonlinear programming problem (MINLP) to find the Sudoku configuration that most closely represents a target image via an integer-colour mapping. This alone produces inadequate results, so we relax the problem by adding transparent regions to the target image and removing certain MINLP constraints. To produce puzzles that are feasible and interesting to players, additional components are added to avoid tedious recounting and unnecessary colouring.

A common technique in Op Art is the use of parallel lines to depict simple shapes such as circles and squares. Some artists have attempted to create more complex images using this technique but faced the problem of producing undesirable artifacts such as line breaks and T-junctions within their artworks. To this end, we developed a novel algorithm that takes an arbitrary image and automatically generates the corresponding Op Art composition of this style. For 2-colour images, the algorithm produces artworks without any unwanted artifacts; for images with more colours, the basic algorithm cannot guarantee the removal of all artifacts, but we use a global optimization technique to minimize the number of artifacts. The results have applications in graphics design, data visualization, puzzle creation and line drawings.

Two-dimensional geometric texture synthesis is the geometric analogue of raster-based texture synthesis. An absence of conventional evaluation procedures in recent synthesis attempts demands an inquiry into the visual significance of synthesized results. In this paper, we report on two psychophysical experiments that explore how people understand notions of similarity in geometric textures. We present perceptual metrics and human texture generation features that are crucial for future researchers when developing and assessing the success of their algorithms.

This paper discusses on-set previsualization with distributed motion capture, virtual camera and asset control, and real-time rendering using a video game engine. Our test harness, RTFX, demonstrates the feasibility and usefulness of a system that couples Epic Games’ UnrealEngine3 with the Houdini 3D animation kit by Side Effects Software and a passive motion capture system by Vicon.

This article explores applications of optimization algorithms to the computer‐based synthesis of art. The presentation covers title‐based methods, freeform arrangement of elements, and line art.

In the arts and sciences, as well as in our daily lives, symmetry has made a profound and lasting impact. Likewise, a computational treatment of symmetry and group theory (the ultimate mathematical formalization of symmetry) has the potential to play an important role in computational sciences. Though the term computational symmetry was formally defined a decade ago by the first author, referring to algorithmic treatment of symmetries, seeking symmetry from digital data has been attempted for over four decades. Computational symmetry on real world data turns out to be challenging enough that, after decades of effort, a fully automated symmetry–savvy system remains elusive for real world applications. The recent resurging interests in computational symmetry for computer vision and computer graphics applications have shown promising results. Recognizing the fundamental relevance and potential power that computational symmetry affords, we offer this survey to the computer vision and computer graphics communities. This survey provides a succinct summary of the relevant mathematical theory, a historic perspective of some important symmetry-related ideas, a partial yet timely report on the state of the arts symmetry detection algorithms along with its first quantitative benchmark, a diverse set of real world applications, suggestions for future directions and a comprehensive reference list.

The term “gotcha” is used to describe an unforeseen exception or complexity in a programming assignment given to students. All too often, the students' discovering gotchas in a programming assignment embarrasses the instructor into revising the assignment. This paper argues that students' discovery of gotchas should be encouraged to promote experiential learning of the value and necessity of requirements engineering. Rather than viewing the discovery experience as a misfortune, an instructor should welcome the experience and even plan assignments with an abundance of gotchas to be discovered by students.

In this paper, I consider the question of how to carry out aesthetically pleasing evolution of the curves that make up the edges in a parquet deformation. Within the framework of simple arrangements of square tiles, I explore curve evolution models based on grids, iterated function systems, and organic labyrinthine paths.

Procedural modelling can be used to generate digital content such as 3D digital models programmatically. In computer graphics, Procedural modelling has focused primarily on natural scenery and cityscapes. This paper considers the use of procedural modelling in a new domain: science fiction spaceships. We examine aesthetic principles as they relate to the beauty and visual interest of spaceships, especially surface details, and determine how these principles can be applied in a practical procedural modelling algorithm.We describe a prototype system that synthesizes and distributes surface details on large-scale spaceships. Given a surface representing the frame of a spaceship, we distribute geometry automatically in a coherent manner to achieve a characteristic science fiction aesthetic.

Painterly rendering algorithms often mimic classical hand-painting techniques to automatically generate stylized paintings from input images. These algorithms use a combination of techniques to express a variety of styles and artistic properties (e.g., contrast, mood), but often restrict the user from controlling the rendering order of overlapping brush strokes. This paper illustrates the importance of brush stroke ordering in creating stylistic effects and presents a layer-based painterly rendering algorithm that allows the user to specify a brush stroke ordering. Several of the presented orderings enable the renderer to reduce detail obstruction, simulate handpainting techniques and enhance artistic styles.

Inspired by recent advances in high-quality mesh parameterization, I present a technique for decorating surfaces with seamless ornamental patterns. The patterns are transferred from planar drawings with wallpaper symmetry. I show that when the original drawing belongs to one of a few specific symmetry groups, then it can easily be rendered with low distortion on a suitably parameterized mesh. The result is not symmetric, but retains most of the structure of the original drawing.

We present a system that can generate convincing synthetic landscape paintings with no user intervention whatsoever, nor any information about 3D geometry or lighting. The system is based on a direct implementation of the "wet-on-wet" oil painting technique taught by Bob Ross for many years on his show The Joy of Painting. We implement a canvas model and a set of brushes that correspond to the canvas and brushes that Bob Ross used on his show. We then compose brush strokes into landscape features that replicate his approach stroke by stroke. Finally, we develop an engine for automatic layout of these features in a painting. We demonstrate this automated system in the context of the Bob Ross painting Forest Hills.

An image mosaic is a rendering of a large target image by arranging a collection of small source images, often in an array, each chosen specifically to fit a particular block of the target image. Most mosaicking methods are simplistic in the sense that they break the target image into regular tiles (e.g., squares or hexagons) and take extreme shortcuts when evaluating the similarity between target tiles and source images. In this paper, we propose an efficient method to obtain higher quality mosaics that incorporate a number of process improvements. The Fast Fourier Transform (FFT) is used to compute a more fine-grained image similarity metric, allowing for optimal colour correction and arbitrarily shaped target tiles. In addition, the framework can find the optimal sub-image within a source image, further improving the quality of the matching. The similarity scores generated by these high-order cost computations are fed into a matching algorithm to find the globally-optimal assignment of source images to target tiles. Experiments show that each improvement, by itself, yields a more accurate mosaic. Combined, the innovations produce very high quality image mosaics, even with only a few hundred source images.

We consider the problem of depicting continuous-tone images using only black and white. Traditional solutions to this problem include halftoning, which approximates tones, and line drawing, which approximates edges. We introduce “artistic thresholding” as a technique that attempts to depict forms in an image. We apply segmentation to a source image and construct a planar subdivision that captures segment connectivity. Our artistic thresholding algorithm is a combinatorial optimization over this graph. The optimization is controlled by parameters that can be tuned to achieve different artistic styles.

Vector graphics representations of images are resolution independent. Direct use of vector images for real-time texture mapping would be desirable to avoid sampling artifacts such as blurring common with raster images. Scalable Vector Graphics (SVG) files are typical of vector graphics image representations. Such representations composite images from layers of paths and strokes defined with lines, elliptical arcs, and quadratic and cubic parametric splines.

High-quality texture mapping requires both random access and anisotropic antialiasing. For vector images, these goals can be achieved by computing the distance to the closest primitives from a sample point and then mapping this distance through a soft threshold function. Representing transparency masks in this way is especially useful, since vector mattes can be used to render complex curvilinear geometry as textures on simple geometric primitives.

Unfortunately, computing the exact minimum distance to the parametric curves used in vector images is difficult. Previous work has used approximations, but an accurate minimum distance is desirable in order to enable wide strokes and special effects such as embossing. In this paper, a simple algorithm is presented that can efficiently and accurately compute the minimum distance to a parametric curve when the sample point is within its radius of curvature and the curve can be segmented into monotonic regions. This technique can be used in a GPU shader to render antialiased vector images exactly as defined by SVG files.

M.C. Escher returned often to the themes of metamorphosis and deformation in his art, using a small set of pictorial devices to express this theme. I classify Escher's various approaches to metamorphosis, and relate them to the works in which they appear. I also discuss the mathematical challenges that arise in attempting to formalize one of these devices so that it can be applied reliably.

We present a set of graphical and combinatorial algorithms for designing mazes based on images. The designer traces regions of interest in an image and annotates the regions with style parameters. They can optionally specify a solution path, which provides a rough guide for laying out the maze's actual solution. The system uses novel extensions to well-known maze construction algorithms to build mazes that approximate the tone of the source image, express the desired style in each region, and conform to the user's solution path.

The creation of engaging mazes requires both mathematical and aesthetic considerations. We present an algorithm for producing mazes that we feel are difficult to solve. This algorithm is based on constructing and connecting obfuscating maze devices called vortices. A vortex is a collection of passages that wind around each other in a spiral and converge on a central junction. We explore variations on vortex construction that enable a range of aesthetic opportunities in the design of mazes, and demonstrate our technique with several of our own examples.

The craft of papercutting is part of the folk art traditions of cultures all over the world. From the point of view of computer graphics, papercutting can be seen as a method of composing bi-level images under a set of geometric connectivity constraints. In this paper, we present a technique for composing digital paper-cut designs. The elements of a design may be images, which are processed via a multilayer thresholding operation, or they may be procedurallygenerated arrangements of shapes. Elements are composed using a set of boolean operators that preserve connectivity. The resulting designs are well suited to being cut by a new generation of inexpensive computer peripherals.

There are many algorithms in non-photorealistic rendering for representing an image as a composition of small objects. In this paper, we focus on the specific case where the objects to be assembled into a composition are letters rather than images or abstract geometric forms. We develop a solution to the “calligraphic packing” problem based on dividing up a target region into pieces and warping a letter into each piece. We define an energy function that chooses a warp that best represents the original letter. We discuss variations in rendering style and show results produced by our system.

Labyrinths and mazes have existed in our world for thousands of years. Spirals and vortices are important elements in maze generation. In this paper, we describe an algorithm for constructing spiral and vortex mazes using concentric offset curves. We join vortices into networks, leading to mazes that are difficult to solve. We also show some results generated with our techniques.

We present symTone, a dual-mouse, symmetric image manipulation application. symTone includes a symmetric method for manipulating a tone reproduction curve using two standard USB mice. The symTone technique is an important contribution because the two mice are manipulating a geometric object as a tool to improve the underlying digital image, thus a spatial object (the curve) is being used to manipulate non-spatial data (the image tones). Our empirical evaluation of the technique shows that symmetric interaction can be effective for manipulating non-spatial data. This novel technique offers a significant improvement in ease of use and is a precursor to more advanced symmetric tone-mapping applications.

Kepler's Harmonice Mundi includes a mysterious arrangement of polygons labeled Aa, in which many of the polygons have fivefold symmetry. In the twentieth century, solutions were proposed for how Aa might be continued in a natural way to tile the whole plane. I present a collection of variations on Aa, and show how it forms one step in a sequence of derivations starting from a simpler tiling. I present alternate arrangements of the tilings based on spirals and substitution systems. Finally, I show some Islamic star patterns that can be derived from Kepler-like tilings.

We introduce symSpline: a symmetric, dual-mouse technique for the manipulation of spline curves. In symSpline, two cursors control the positions of the ends of the tangent to an edit point. By moving the tangent with both mice, the tangent and the edit point can be translated while the curvature of the spline is adjusted simultaneously, according to the length and angle of the tangent. We compare the symSpline technique to two asymmetric dual-mouse spline manipulation techniques and to a standard single-mouse technique. In a spline matching experiment, symSpline outperformed the two asymmetric dual-mouse techniques and all three dual-mouse techniques proved to be faster than the single-mouse technique. Additionally, symSpline was the technique most preferred by test participants.

We present a vector graphics representation suitable for real-time rendering on GPUs. Our representation can be used in place of a texture map, and renders precise antialiased edges at any magnification. A combination of texture data and procedural computation is used to evaluate an exact signed distance to a contour and its gradient. An optimized uniform grid accelerator is created using Voronoi analysis and redundancy elimination, so only the distances to a small constant number of features need be computed at every access. Contours and sharp features can be exactly reconstructed using a constant amount of computation per pixel. Our representation supports inexpensive high-quality anisotropic antialiasing as well as special effects such as outlining (with both rounded and sharp miters) and embossing.

We have applied our representation to the important application of glyph rendering. Variations in glyph complexity are handled by storing different glyphs at different grid resolutions. Large blocks of glyphs can be rendered efficiently with a single indirection through an index texture.

We present an evaluation of three mouse-based techniques for aligning digital images. We investigate the physical image alignment task and discuss the implications for interacting with virtual images. In a formal evaluation we show that a symmetric bimanual technique outperforms an asymmetric bimanual technique which in turn outperforms a unimanual technique. We show that even after mode switching times are removed, the symmetric technique outperforms the single mouse technique. Subjects also exhibited more parallel interaction using the symmetric technique than when using the asymmetric technique.

Bosch and Herman recently described how to use the traveling salesman problem (TSP) to construct a continuous line drawing based on a user-supplied image. They create a distribution of “cities” hat approximates the darkness of the source image, and pass the cities to a heuristic TSP solver. We discuss their method and present alternative algorithms for city distribution that yield more attractive line drawings.

While developing a program to render Voronoi diagrams, I accidentally produced a strange and surprising image. The unexpected behaviour turned out to be caused by a combination of reasons from signal processing and computer architecture. I describe the process that led to the pattern, explain its structure, and display many of the wonderful designs that can be produced from this and related techniques.

We present a simple method for rendering Islamic star patterns based on Hankin's “polygons-in-contact” technique. The method builds star patterns from a tiling of the plane and a small number of intuitive parameters. We show how this method can be adapted to construct Islamic designs reminiscent of Huff's parquet deformations. Finally, we introduce a geometric transformation on tilings that expands the range of patterns accessible using our method. This transformation simplifies construction techniques given in previous work, and clarifies previously unexplained relationships between certain classes of star patterns.

We present a paradigm that makes the flexibility of NC machining available to the non-technical woodworker. In this context, general-purpose CAD software and manufacturing systems are not appropriate due to prohibitive complexity and cost. We propose a machine architecture and suite of software tools that together offer a cost-effective and simple way of realizing art in wood. Designs can be tested in a 3D simulation before being realized. As a proof-of-concept of the new paradigm, we show a prototype NC milling lathe, a design tool for the special case of Islamic star patterns, and a decorative piece designed and cut using the system.

We present Najm, a set of tools built on the axioms of absolute geometry for exploring the design space of Islamic star patterns. Our approach makes use of a novel family of tilings, called “inflation tilings,” which are particularly well-suited as guides for creating star patterns. We describe a method for creating a parameterized set of motifs that can be used to fill the many regular polygons that comprise these tilings, as well as an algorithm to infer geometry for any irregular polygons that remain. Erasing the underlying tiling and joining together the inferred motifs produces the star patterns. Because Najm is built using only the axioms of absolute geometry, which makes no assumption about the behaviour of parallel lines, star patterns created by Najm can be designed equally well to fit the Euclidean plane, the hyperbolic plane, or the surface of a sphere.

“Escherization” is a process that finds an Escher-like tiling of the plane from tiles that resemble a user-supplied goal shape. We show how the original Escherization algorithm can be adapted to the dihedral case, producing tilings with two distinct shapes. We also use a form of the adapted algorithm to create drawings in the style of Escher's print Sky and Water. Finally, we develop an Escherization algorithm for the very different case of Penrose's aperiodic tilings.

Throughout history, geometric patterns have formed an important part of art and ornamental design. Today we have unprecedented ability to understand ornamental styles of the past, to recreate traditional designs, and to innovate with new interpretations of old styles and with new styles altogether.

The power to further the study and practice of ornament stems from three sources. We have new mathematical tools: a modern conception of geometry that enables us to describe with precision what designers of the past could only hint at. We have new algorithmic tools: computers and the abstract mathematical processing they enable allow us to perform calculations that were intractable in previous generations. Finally, we have technological tools: manufacturing devices that can turn a synthetic description provided by a computer into a real-world artifact. Taken together, these three sets of tools provide new opportunities for the application of computers to the analysis and creation of ornament.

In this dissertation, I present my research in the area of computer-generated geometric art and ornament. I focus on two projects in particular. First I develop a collection of tools and methods for producing traditional Islamic star patterns. Then I examine the tesselations of M. C. Escher, developing an “Escherization” algorithm that can derive novel Escher-like tesselations of the plane from arbitrary user-supplied shapes. Throughout, I show how modern mathematics, algorithms, and technology can be applied to the study of these ornamental styles.

We introduce and characterize a new class of polygons that models wood, stone, glass and ceramic shapes that can be cut with a table saw, lapidary trim saw, or other circular saw. In this model, a circular saw is a line segment (in projection) that can move freely in empty space, but can only cut straight into a portion of material. Once a region of material is separated from the rest, it can be picked up and removed to allow the saw to move more freely. A polygon is called cuttable by a circular saw if it can be cut out of a convex shape of material by a sufficiently small circular saw. We prove that a polygon has this property precisely if it does not have two adjacent reflex vertices. As a consequence, every polygon can be modified slightly to make it cuttable by a circular saw. We give a linear-time algorithm to cut out such a polygon using a number of cuts and total length of cuts that are at most 2.5 times the optimal. We also study polygons cuttable by an arbitrarily large circular saw, which is equivalent to a ray, and give two linear-time recognition algorithms.

In the quest for new visually interesting polyhedra with regular faces, we define and present an infinite class of solids, constructed by placing regular polygons at the rotational axes of a polyhedral symmetry group. This new technique can be used to generate many existing polyhedra, including most of the Archimedean solids. It also yields novel families of attractive symmetric polyhedra.

Boggle is a fast-paced word search game played on a five-by-five grid of letters. To remove any trace of fun from the game, I have conducted an extensive analysis of Boggle, using a newly-constructed software tool. I present the tool and the Boggle insights it provides.

This paper introduces and presents a solution to the “Escherization” problem: given a closed figure in the plane, find a new closed figure that is similar to the original and tiles the plane. Our solution works by using a simulated annealer to optimize over a parameterization of the “isohedral” tilings, a class of tilings that is flexible enough to encompass nearly all of Escher's own tilings, and yet simple enough to be encoded and explored by a computer. We also describe a representation for isohedral tilings that allows for highly interactive viewing and rendering. We demonstrate the use of these tools – along with several additional techniques for adding decorations to tilings – with a variety of original ornamental designs.

Islamic star patterns are a beautiful and highly geometric art form whose original design techniques are lost in history. We describe one procedure for constructing them based on placing radially-symmetric motifs in a formation dictated by a tiling of the plane, and show some styles in which they can be rendered. We also show some results generated with a software implementation of the technique.

A set of points in the plane induces a Voronoi diagram, a division of the plane based on proximity to points in the set. Voronoi diagrams have been used extensively in engineering and scientific disciplines, but the possibility of using them for creating abstract ornamental designs is largely unexplored. I present some techniques for creating attractive ornamental designs using Voronoi diagrams. I focus on two features of Voronoi diagrams that make them particularly useful artistic tools: their conservation of symmetry, which be used to construct interesting tilings of tne plane, and their continuity with respect to changes in the generators, which makes possible smooth, organic animations of tilings.

Predicate dispatching generalizes previous method dispatch mechanisms by permitting arbitrary predicates to control method applicability and by using logical implication between predicates as the overriding relationship. The method selected to handle a message send can depend not just on the classes of the arguments, as in ordinary ob ject-oriented dispatch, but also on the classes of subcomponents, on an argument's state, and on relationships between ob jects. This simple mechanism subsumes and extends ob ject-oriented single and multiple dispatch, ML-style pattern matching, predicate classes, and classiers, which can all be regarded as syntactic sugar for predicate dispatching. This paper introduces predicate dispatching, gives motivating examples, and presents its static and dynamic semantics. An implementation of predicate dispatching is available