AUTOMATING ESCHER TILING AND COLORING:
AN IMPLEMENTATION
by
Stephen C. Ogden
B. S., University of Colorado at Denver, 1997
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
2004
2004 by Stephen C. Ogden
All rights reserved.
This thesis for the Master of Science
degree by
Stephen C. Ogden
has been approved
by
Ellen Gethner
Gita Alaghband
Min-Hyung Choi
\X 0 3 3 CC L)
Date
Ogden, Stephen C. (M. S., Computer Science)
Automating Escher Tiling and Coloring: An Implementation
Thesis directed by Assistant Professor Ellen Gethner
ABSTRACT
An Escher tile is a creation most notably attributed to the famous artist
M. C. Escher. The tile is a square that contains a unique design. It is
used to cover a surface much as tiles cover a wall, for instance. The
design in the tile may seem to be unremarkable because it appears to
contain only a group of random polygons. But, when the tiles are placed
adjacent to one another to cover a surface, patterns appear on the surface.
These patterns are repeated in cycles, or periods, to create wallpaper
patterns on the surface. In addition, the patterns may or may not be
overlapping. The patterns may not be apparent just by looking at the
designs, or motifs, in the square tile.
The patterns are interesting but even more interesting when colored. A
question that begs an answer is: How can the patterns be colored so as to
receive unique colors? Unique coloring, in this case, means that each
wallpaper pattern receives a color that is different from patterns it may
overlap. There must also be a discrete number of colors used on the
wallpaper. This allows the color patterns are repeated as well.
Fortunately, Ellen Gethner, has discovered a method for the solution to
this problem.
Another question is: How can this method be automated on a computer?
That is the question that this thesis seeks to answer. Each step in the
IV
process of coloring Escher tiles in a wallpaper is mathematically sound
and serves a purpose in the solution. However, for an implementation,
there are issues of data structures, algorithms, and procedures that are
necessary for engineering a solution. There is also the problem of simply
defining the problem in concrete terms so that a solution may be
implemented. The theoretical solution many times does not account for
the practical solution. There must be some translation from the realm of
theory to the realm of practice. These are the issues that are discussed in
this thesis.
This abstract accurately represents the content of the candidate's thesis.
I recommend its publication.
Signed
Ellen Gethner
v
DEDICATION
This thesis is dedicated to every art and math lover who has come to
appreciate the work of M. C. Escher.
ACKNOWLEDGEMENT
I wish to thank my advisor and mentor Ellen Gethner who spent many
evenings with me explaining linear algebra, number theory, and those
pesky forbidden vectors. Thanks to Min-Hyung Choi for his help in
implementing a graphical interface for Escher tile visualizations. Also
thanks to the talented professors in the Computer Science department,
including John Clark, Bill Wolfe, Gita Alaghband, and Il-Kyun Ra, for
expanding my world once again. I especially wish to thank my fiance,
Ann Gonzalez, for all her love, support, and devotion that made it possible
for me to complete this project and earn a degree.
CONTENTS
Figures..........................................................x
Tables...........................................................xi
Chapter
1. Introduction...............................................1
1.1 Motivation.................................................1
1.2 Problem Definition.........................................7
1.3 Related Work and Resources................................10
1.4 Discussion Format.........................................10
2. Method....................................................12
2.1 Main Algorithm............................................13
2.2 Label Motif Pieces........................................14
2.2.1 Implementation............................................14
2.3 Identify Connections......................................15
2.3.1 Implementation............................................19
2.3.2 3D Extension..............................................20
2.4 Identify Overlaps.........................................20
2.4.1 Implementation............................................21
2.4.2 3D Extension..............................................21
2.5 Derive the Spanning Trees.................................22
2.5.1 Implementation............................................22
2.5.2 3D Extension..............................................23
2.6 Create the Generating Set of Motif Pieces.................23
2.6.1 Implementation............................................25
2.6.2 3D Extension..............................................28
2.7 Record Removed Edges......................................28
2.7.1 Implementation............................................28
2.8 Identify Ghost Nodes......................................30
2.8.1 Implementation............................................33
2.8.2 3D Extension..............................................34
2.9 Lattice...................................................34
2.10 Compute Forbidden Vectors.................................36
viii
2.10.1 Implementation............................................38
2.10.2 3D Extension..............................................39
2.11 Normalize Forbidden Vectors...............................40
2.11.1 Implementation............................................41
2.11.2 3D Extension..............................................42
2.12 Choose Collision-Free Vectors.............................45
2.12.1 Implementation............................................46
2.12.2 3D Extension..............................................47
2.13 Compute Big Tile Size.....................................48
2.13.1 Implementation............................................52
2.13.2 3D Extension..............................................52
2.14 Locate Color Vectors......................................56
2.14.1 Implementation............................................57
2.14.2 3D Extension..............................................62
2.15 Assign Colors to Lattice Points...........................65
2.15.1 Implementation............................................69
2.15.2 3D Extension..............................................70
2.16 Color the Tile............................................72
3. Conclusion................................................74
3.1 Design Tool...............................................74
3.2 Future Considerations.....................................75
Appendix
Appendix A. Algorithms...........................................76
Appendix B. Escher Tile Examples.................................81
References.......................................................85
IX
FIGURES
Figure 1.1: An Escher Tile.........................................1
Figure 1.2: An Escher Wallpaper....................................2
Figure 1.3: A Colored Escher Wallpaper.............................3
Figure 1.4: Escher Design Tool.....................................5
Figure 1.5: 3D Escher Design Tool..................................7
Figure 1.6: Highlighted Unit Tile..................................8
Figure 1.7: Wallpaper Component....................................9
Figure 2.1: Labeled Escher Tile...................................14
Figure 2.2: Horizontal, Vertical, and Diagonal Connections........15
Figure 2.3: Period Graph..........................................18
Figure 2.4: Agglomerated Period Graph.............................19
Figure 2.5: Spanning Tree.........................................22
Figure 2.6: Embedded Spanning Tree................................25
Figure 2.7: Generating Set of Motif Pieces........................25
Figure 2.8: Ghost Node............................................31
Figure 2.9: Natural Period........................................31
Figure 2.10: Lattice Basis........................................35
Figure 2.11: Lattice Pattern......................................36
Figure 2.12: Overlap Graph........................................37
Figure 2.13: Lattice..............................................45
Figure 2.14: Normalized Lattice...................................49
Figure 2.15: Uncolored Big Tile...................................52
Figure 2.16: Open Parallelogram...................................58
Figure 2.17: Open Parallelepiped..................................62
Figure 2.18: Colored Big Tile.....................................68
Figure 2.19: Numbered Big Tile....................................69
Figure B.l: Trivially Periodic Tile...............................82
Figure B.2: Trivially Periodic Wallpaper..........................82
Figure B.3: Singly Periodic Tile..................................83
Figure B.4: Singly Periodic Wallpaper.............................83
Figure B.5: Doubly Periodic Tile..................................84
Figure B.6: Doubly Periodic Wallpaper.............................84
x
TABLES
Table 2.1: Connections.............................................17
Table 2.2: Overlaps................................................21
Table 2.3: Generating Set of Motif Pieces..........................24
Table 2.4: Removed Edges...........................................28
Table 2.5: Forbidden Vectors.......................................38
Table 2.6: Color Vectors...........................................57
Table 2.7: HNF Lattice Properties..................................59
Table 2.8: Open Parallelogram Definitions..........................59
Table 2.9: Lattice Angle Properties................................60
Table 2.10: Iteration Ranges.......................................61
Table 2.11: Parallelepiped Definitions.............................63
Table 2.12: Color Assignments......................................67
xi
1. Introduction
Working with Escher tiles is fun. It involves the study of their
mathematical properties that span the areas of Number Theory, Graph
Theory, Linear Algebra, and Geometry. The added benefit is that this
study involves studying the art of the great master artist M. C. Escher. It
seems incongruous that the study of mathematics would lead to a deeper
appreciation of art. This artist's work is awe inspiring from the
standpoint of beauty and form. It seems that most people are familiar
with and love his art. As if esthetics are not enough, it is also awe
inspiring to consider the beauty of the mathematics present in his work.
It is incredible how art and math were brought together so seamlessly by
this man.
1.1 Motivation
Figure 1.1: An Escher Tile
Figure 1.1 shows an example of an Escher tile. This is the basic building
1
block for creating patterns on a plane. By placing multiple copies of this
tile adjacent to one another a wallpaper is created. Figure 1.2 is an
example of tiling a wallpaper with the tile shown in Figure 1.1. The
patterns that emerge in the wallpaper are not readily apparent just by
looking at the tile alone. We can see patterns in the ribbons, or strands,
that are created by the tile. The preferred term for these strands is
wallpaper component. Each polygon in the tile is joined with another on
the wallpaper to create regular patterns.
Figure 1.2: An Escher Wallpaper
The patterns that show up in the wallpaper, almost as if by magic, are
interesting in their own right. They weave in and out amongst
themselves as if to create some exotic fabric. The individual wallpaper
2
components create a repeated, rhythmic, design that guides our eye across
the canvas. They interlace and overlap to create a structure that makes it
seem as if they cannot be unraveled. And if they were unraveled, they
could all be part of the same wallpaper component. It would be much
more interesting if we could color the patterns so that we could better see
the rhythms and dependencies. Figure 1.3 is an example of one possible
coloring.
Figure 1.3: A Colored Escher Wallpaper
The coloring is definitely an improvement over the monotone scheme in
its predecessor. The coloring in Figure 1.3 is the result of using
Ellen Gethner's coloring algorithm for Escher tiles [Ge02]. The coloring
uses enough colors so that overlapping patterns do not use the same color
3
while allowing the color pattern to repeat. In Figure 1.3, for example, no
red wallpaper component overlaps another red wallpaper component.
Ellen's algorithm guarantees that no same colored wallpaper components
will overlap another.
Now we know we can take an Escher tile, cover a wallpaper with it, and
color it as defined. It would be nice if we could stretch the possibilities.
There are a number of Escher tiles using an arrangement of motif pieces
such as seen in Figure 1.1. It would be nice if we could automate the
process for different tiles. Automation holds the promise of being able to
explore many new possibilities of creating Escher tiles. Software could be
implemented to allow a user to create new tiles and see the patterns
emerge, both geometrically and chromatically.
As part of a related project, software has been created to test the
feasibility of the following scenario. A tile designer sits down at a
computer and begins to add polygons, or motif pieces, to a design pane. As
each motif piece is added, a wallpaper pattern emerges in a separate
pane. A screen shot of a prototype for this software is shown in Figure
1.4.
This tool was created by the author as part of a project supervised by
Min-Hyung Choi. The aim of the project was to provide a graphical
interface as an aid in the visualization of Escher tiles. This tool is
planned to be used as a teaching aid for students of Combinatorics and
Geometry. A major use for the design tool is simply to test the
functionality of the implementation described here.
4
X
Figure 1.4: Escher Design Tool
The main body of the discussion in this thesis will deal with tiling a
5
wallpaper in IR2. It turns out that the algorithm is easily extended to IR3.
As part of the same project mentioned above, a design tool for 3D
visualization was created. A screen shot of that prototype is shown in
Figure 1.5. The purpose of the software was intended to help in
visualizing motif pieces in IR3. This extension into 3 dimensions should be
an aid in not only studying 3D Escher tiles, but also in defining just what
a 3D Escher tile really is.
6
Figure 1.5:3D Escher Design Tool
1.2 Problem Definition
Now that we have some idea of the problem domain, it is time to define
the problem to be solved and implemented. First, we need to define some
terms.
7
The Escher tile (Figure 1.1) is called a unit tile. It is a unit tile because it
is the basis for all measurements on the wallpaper. All positions and
directions on the wallpaper are expressed in units of one tile. Since we do
not deal with fractions of unit tiles, only the set of integers will be needed
for calculations.
The polygons within the unit tile are called motif pieces. Motif pieces may
or may not overlap one another. Also, they may or may not touch the edge
of the unit tile. Figure 1.6 shows the motif pieces seen in Figure 1.1
highlighted with different patterns. There are nine motif pieces for this
particular example.
An area tiled with unit tiles is called a wallpaper. The motif pieces then
join with one another to form patterns. These patterns are called
wallpaper components. Figure 1.7 highlights one wallpaper component in
our example. We could have chosen any of an infinite number of identical
wallpaper components. Notice that all of the wallpaper components in
this example overlap each other. However, with other Escher tiles, some
wallpaper components may not overlap each other.
Figure 1.6: Highlighted Unit Tile
8
>V^\5^ \ XxxW / \ /v4\\ / \ /X\\\ /
\ /x\\\ / >Y\^J \ / \r% \ /x\\\ /
\ /VC\\\ / \ \ /
\ /x\\\ / \ /a\\\ / \ /
Figure 1.7: Wallpaper Component
Now that we have these basic definitions, the problem can be stated. The
problem is to color all wallpaper components in such a manner such that
no two overlapping components have the same color and using a finite
number of colors. The solution is attainable and may be solved using an
efficient algorithm [Ge02]. It would be nice to say that the number of
color is minimal. But the number of colors is only guaranteed to be finite.
9
The first part of the problem, that no two wallpaper components that
overlap may have the same color, could be solved by simply using a
different color each time a new component is found. This would require
an infinite number of colors. That does not satisfy the second part of the
solution that a finite number of colors be used. The second part implies
that, in addition to seeing geometric repetition in a colored wallpaper, we
would see a chromatic repetition as well. The solution gives us a palette
of colors that is finite, but is not minimal.
1.3 Related Work and Resources
The primary motivation for this project is Ellen Gethner's work with
Escher tiles. However, there are a few other resources available for
further investigation.
Doris Schattschneider explored the subject by investigating the counting
problem posed and answered by M. C. Escher[Sc97]. This problem was
alluded to in work by Rick Mabry, Stan Wagon, and Doris Shattschneider
earlier in [MaWaSc96]. In the same article she also posed a problem in
three dimensions. Dan Davis showed the exact counting of different
Escher tiles using a base motif [Da97]. Ellen Gethner later generalized
the problem that Doris Schattschneider posed [GeOl]. An interactive web
site by Steve Passiouras lets the user experiment with the motifs to see
what patterns emerge [PaOl].
Finally, for actual drawings of tiles by M. C. Escher see Visions of
Symmetry, by Doris Schattschneider [Sc04]. This book shows many works
beside the tiles and gives insight into many of the patterns that Escher
was pursuing. Additionally, the work of Ellen Gethner is mentioned in
this book relation to Escher tiles.
1.4 Discussion Format
As you can see, there is plenty of motivation for the study of Escher tiles.
This is an area of study that combines the disciplines of art, mathematics,
computer science, and engineering. The primary focus of this thesis is the
implementation of Ellen Gethner's algorithm. However, one aspect of the
implementation is how to transfer tile information into a f the computer
10
can use. This process is commonly called digitizing. Another area of
discussion is how to extend the algorithm so that it can be used in three
dimensions.
The discussion of digitizing is discussed during the primary steps of the
algorithm. It is also discussed at the last step, the point where colors may
be assigned to motif pieces.
The 3D extension could be a case of carrying along a third coordinate, or it
may require some extra work to be conform to the theory. The discussion
of extending the algorithm into 3D is handled at nearly every step in the
algorithm. The 3D extensions are very important because that is where
the real implementation lies. Since 2D is a special case of 3D, the
implementation will be in 3D and then applied to scenarios in 2D.
Another note on format is the use of an example tile. We have seen the
tile in Figure 1.1. To help provide some continuity, this tile will be used
as we work our way through the steps in the algorithm. At each step, the
results of calculations will be shown to help illustrate the expected
results. These are the same results that must be used when performing
unit tests on the software.
Lastly, there is no discussion of actual programming languages here. All
the procedures are shown in pseudo code. This document is meant more
as a blueprint for implementation. The concepts and procedures could be
implemented just as readily in C, C++, Java, Perl, or Assembly if one
would like. The major consideration is that it becomes possible to create a
bridge from the theoretical realm to the practical realm.
11
2. Method
The main algorithm, as summarized from Ellen Gethner's doctoral thesis
[Ge02], is presented below. The method described here, and the theory
behind the method is described in her thesis. It is included only to
illustrate the overall program flow. Terms such as motif piece,
forbidden vectors, natural periods, and collision-free vectors will
become clearer as they are presented and defined in the sections that
follow.
12
2.1 Main Algorithm
The main algorithm may be summarized by the following steps.
Algorithm: color an Escher wallpaper
Inputs:
An Escher tile in a wallpaper
Main
1 Label the motif pieces
2 Identify motif piece connections
3 Identify overlapping motif pieces
4 Derive spanning forest for all connected components
5 for (each connected component)
6 Create the generating set of motif pieces
7 Record removed edges
8 Identify ghost nodes and compute natural periods
9 if (the number of natural periods <2)
10 Compute forbidden vectors
11 Normalize forbidden vectors
12 Choose collision-free vectors
13 Compute Big Tile size
14 Locate color vectors
15 A
13
2.2
Label Motif Pieces
Figure 2.1: Labeled Escher Tile
Figure 2.1 shows an example of a labeled Escher tile. For convenience,
this particular tile will be used in all of the examples that follow. The tile
is a square that is one unit by one unit in dimension. It is used to tile the
Euclidean plane to create a wallpaper. This type of Escher tile will
sometimes be referred to as a unit tile. Figure 2.1 also illustrates one
possible numbering of motif pieces for this particular Escher tile. As
discussed earlier, a motif piece is a unique polygon within the unit tile.
Motif pieces may or may not intersect the edge of the unit tile. Motif
pieces may or may not overlap each other. It is not important which order
the motif pieces are numbered. It is only important that each distinct
motif piece gets a unique number.
2.2.1 Implementation
This has been included as part of the algorithm because this may also be
14
automated. The design tool mentioned in the introduction allows a user
to enter various polygons, such as we see in Figure 2.1. This user
interface recognizes each polygon as it is created and assigns it a unique
index. This step, and the next two, require transferring visual
information into digital information. Therefore, the first three steps are
considered digitizing steps.
2.3 Identify Connections
When a wallpaper is tiled with the Escher tiles, they are placed adjacent
to other tiles. Two tiles are adjacent if they touch on their horizontal
edges, vertical edges or if they touch each other at their corners. There
are two adjacencies in the x direction, two in they direction and one for
each of the four corners. Therefore, one tile is adjacent to eight other tiles
for a total of nine tiles in all.
A connection occurs when a motif piece shares at least one point with
another motif piece in an adjacent tile. This means there are three types
of connections. Figure 2.2 shows a horizontal connection between motif
pieces ms and m,7, a vertical connection between motif pieces m3 and m2,
and a diagonal connection between motif pieces mi and ms.
a: horizontal connection
Y
b: vertical connection
c: diagonal connection
Figure 2.2: Horizontal, Vertical, and Diagonal Connections
15
After all the connections have been discovered, the directions of the
connections must be recorded. This associates each connection with a
direction vector. In IR2, the direction vector signifies connection in the x or
y directions.
For example, in Figure 2.2a, me has a horizontal connection to m7 with a
direction vector of [1,0]. This means that, if we were able to stand on me
and travel to m7, we would have to travel one unit in the x direction. Of
course, to get back to me from mz, the direction vector would be [-1,0].
This highlights one property of connections: there is always a direction
vector [-x,-y] or a complementary connection, for every direction vector
[xj] for each connection. The notation we will use for this connection is
[6.7.1.0] which signifies a connection from motif piece me to motif piece m7
in the direction of [1,0]. It is just as easy to use the complementary
4-tuple [7,6,-1,0] to describe the same connection.
In Figure 2.2b, m3 has a vertical connection to m2 with a direction vector
[1.0] resulting in [3,2,1,0] and its complement [2,3,-1,0]. In Figure 2.2c,
mi has a diagonal connection to mg with a direction vector of [1,1]
resulting in [1,8,1,1] and its complement [8,1,-1,-1].
The complete set of connections for Figure 2.1 is listed below in Table 2.1.
Since the complementary connections may be derived from this set, they
have been omitted.
16
[1,2,1,0]
[1,6,0,1]
[1,8,1,1]
[1,9,0,1]
[2,3,0,-1]
[2,8,0,1]
[2,9,-1,1]
[3,4,-1,0]
[4.5.1.0]
[5,6,0-1]
[6.7.1.0]
[8,9,-1,0]
Table 2.1: Connections
This set of 4-tuple vectors describes the relationship between any tile in
the plane and its eight adjacent tiles. This information will be used to
build the period graph. Each entry in the list has the form [m^rrijjcy],
where m; is represents a motif piece with label i. Figure 2.3 shows the
period graph for the connections listed in Table 2.1 including the
complementary connections.
17
[0,-1]
[1^0].
[0,-1]
Figure 2.3: Period Graph
It is useful to consider the underlying structure of the period graph by
combining all the edges (connections) between vertices (motif pieces) and
removing the directions. Figure 2.4 shows the agglomerated period graph
derived from the the period graph. It will tell us the exact nature of the
wallpaper components that are created by the connected motif pieces.
Please see Ellen Gethner's doctoral thesis [Ge02] for a more complete
discussion of the period graph. The usage of the period graph and the
agglomerated period graph will become clear in subsequent sections.
18
The period graph represents one connected component. It is possible to
have multiple connected components for an Escher tile, each with their
own period graph. Separate components are discovered during creation of
the spanning tree.
2.3.1 Implementation
Note that, instead of using as set of 4-tuples, an adjacency matrix could
have been used to record the same information. The set of 4-tuples was
chosen because it makes more efficient use of memory. The difference in
efficiency when referencing matrix entries as opposed to set (or list) of
entries is acceptable [CoLeRiOl]. Additionally, the set of 4-tuples makes
locating entries easier to implement.
The design tool is able to recognize when polygons intersect an edge or a
corner. This is accomplished by constraining the endpoints of the line
segments that create the polygon to a regular grid. By testing each of the
grid points on the edges, the tool can determine which polygons (motif
pieces) intersect the edge, and where they intersect. When two polygons
19
share opposite edge points, either horizontally, vertically, or diagonally, a
connection is recorded.
2.3.2 3D Extension
One difference between 2D and 3D is the definition of edges. Instead of
connections existing only on line segments or corner points, connections
can occur at the faces of a unit cube as well. The unit cube could be called
an Escher cube, but a preferable term is a 3D Escher tile.
Another difference is the definition of a connection. There is still a
horizontal connection in the x direction, and a vertical connection in the y
direction. There is an additional depth wise connection in the z direction.
A diagonal connection is a connection between any two opposing edges in
the cube or any two opposing corners. One cube may be adjacent to 26
other cubes for a total of 27 cubes.
The last difference is that 5-tuples are used instead of 4-tuples to account
for connections that involve the z coordinate. The 5-tuple is described as
2.4 Identify Overlaps
Finding overlaps is very straightforward. Simply record the fact that any
pair of motif pieces have overlapped each other. This produces a set of
ordered pairs. Each pair represents the indices of the two motif pieces
that overlap one another. For instance, in Figure 2.1, mi overlaps m3.
This produces an overlap of [1,3] and the complement [3,1]. One might
consider this an undirected graph where motif pieces are the vertices and
overlaps are the edges. Table 2.2 shows the overlaps for Figure 2.1.
20
[1.3]
[1,6]
[2.3]
[2.5]
[2.6]
[4,6]
Table 2.2: Overlaps
2.4.1 Implementation
Again, a set of pairs is used instead of an adjacency matrix. This is more
a matter of consistency throughout the implementation at this point.
Therefore, all n-tuples (vectors) that are used to contain information about
the Escher tile were implemented as a set, or list, of n-tuples.
The design tool uses a method similar to finding intersections with the
edges. A minimum set of points, not necessarily grid points, is used to
detect whether a motif piece intersects each test point. If two or more
motif pieces intersect with a test point, then an overlap is recorded.
This step may or may not be necessary depending on the Escher tile. It
will not be necessary if two natural periods are found in line 9 of the
main algorithm (section 2.1). This bit of inefficiency must be tolerated in
the design tool because we can never know in advance what the finished
product will be. Calculations are processed dynamically as the tile is
created. Given a fixed tile, however, we would skip this step until we
know that overlaps are needed.
2.4.2 3D Extension
Whether we are considering IR2 or IR3, only the fact that two motif pieces
overlap is important. An overlap is defined as when two motif pieces
contact each other in at least one point. Since overlaps do not record
direction or position, the fact that they occur in either IR2 or IR3 is
21
inconsequential.
2.5 Derive the Spanning Trees
The next step is to find a spanning tree, or spanning forest, of the period
graph. The period graph may have multiple connected components.
Therefore, it is necessary to find a spanning tree for each connected
component. This is easily accomplished by performing a depth-first
search [WeOl]. The next steps following this one in the main algorithm
are performed for each connected component. Running a depth-first
search on the agglomerated period graph in Figure 2.4 reveals that there
is only one connected component. This produces the spanning tree found
in Figure 2.5. This spanning tree will be used to plot the relative
locations of motif pieces on the wallpaper.
2.5.1 Implementation
It will soon become apparent that the spanning tree is not an important
22
artifact. It is only the exercise of performing the depth first search that is
important. Therefore, no attempt is made to save any graph information
concerning the spanning tree. It is useful for human eyes to see the
spanning tree because it helps us to visualize what is happening. For
instance, we can see which motif pieces are connected to each other.
Recursive method calls were chosen to implement the depth-first search.
There is a danger of stack overflow when using recursive method calls.
But, since most period graphs (Escher tiles) are simple enough, that
danger is relatively low. If there is a problem with method call stack
overflow, the search may be implemented iteratively.
2.5.2 3D Extension
The 3D extension has no effect on the spanning tree except that there is
an additional direction of connection to consider when parsing the period
graph.
2.6 Create the Generating Set of Motif Pieces
In this step, we will use the direction vectors of the period graph to
produce a position vector for each one of the motif pieces. The position
vector is the position of a motif piece in relation to an origin piece to which
it is connected. The origin piece is an arbitrary piece that is chosen to
occupy position [0,0]. The initial origin piece is always mi. If there is
more than one connected component, then each component will have its
own origin piece other than mi.
The generating set is a set of 3-tuples that represent the motif piece and
its relative position vector, [mtpc y]. Another notation for this is [m^ aj
where mi is the motif piece and a; is its position vector [rc^y]. The set is
called a generating set because it can be used to determine the
relationship between a motif piece and any other motif piece in the
wallpaper.
The generating set is produced during traversal down the spanning tree.
The direction vectors for the vertices on an edge are summed to produce a
position vector. The position vector is then assigned to the latest vertex to
create a generating motif piece. The generating set represents the
23
positions of all motif pieces relative to the origin piece for a set of
connected pieces.
For example, mi is automatically assigned position [0,0]. This is the
origin piece [1,0,0]. Checking the period graph, we see that to get from mi
to m2 on the spanning tree we must travel in the direction of [1,0]. Adding
[0,0] and [1,0], we get the result [1,0]. This creates generating piece
[2,1,0]. To get from m2 to m3, we must travel in the direction of [0,-1].
Adding [1,0] to [0,-1], we get [1,-1]. This creates generating piece
[3,1,-1].
The complete set of generating motif pieces is shown in Table 2.3. The
graph of the generating set, or embedded spanning tree, is shown in
Figure 2.6. The embedded spanning tree represents the motif pieces in
their relative locations. This set of motif pieces, or wallpaper component,
is a base pattern for a repeating set of patterns in the wallpaper. To get a
good idea of what the graph actually represents, a partial tiling is shown
in Figure 2.7. This illustrates how the individual motif pieces are located
according to the spanning tree in our example.
[1,0,0]
[2,1,0]
[3,1,-1]
[4,0,1]
[5,1,-1]
[6,1,-2]
[7,2-2]
[8,1,1]
[9,0,1]
Table 2.3: Generating Set of Motif Pieces
24
Figure 2.7: Generating Set of Motif Pieces
2.6.1 Implementation
While the vertices have not been exhausted, first create a generating set
that contains an origin piece. The origin piece is the first available motif
piece. Its position vector set to [0,0]. For example, the very first piece is
always mi. Thus, we start out with the initial set containing the origin
piece [1,0,0]. This vertex (motif piece) is removed from the set of available
vertices. Then a depth-first search is done on the period graph starting
with the origin piece. It is during the search that position vectors are
calculated. Then, the resulting generating set is associated with the
connected component from which it was derived. If there are any vertices
left at this point, they are part of different components. The procedure is
repeated until all the vertices are depleted.
25
Algorithm: Create generating set of motif pieces
Definitions:
C = the set of connected components
E = the set of edges from the period graph
V = the set of vertices from the period graph
Inputs:
P = the period graph
Mk = the generating set of motif pieces for component k
CreateGeneratingSet (P, Mk)
1 Add all vertices to V={ 1,2,3
2 Copy period graph P>E
3 k = l
4 C=0
5
6 while (V*J0T)
7 Mk=0
8 Create Ck={Mk}
9 Get first available vertex in V and remove (V=Vv0)
10 Create origin motif piece m0=[v0 0,0]
11 Mk=Mk+m0
12 Search (i>0 0,0) // adds motif pieces > Mk
13 C=C+Ck
14 k = k + l
The efficiency of this algorithm, not including the search, is proportional
to the number of connected components in the tile, O(k).
26
Algorithm: depth first search
Inputs:
E = the set of edges from the period graph
V = the set of vertices from the period graph
Mk= the generating set of motif pieces for component k
Search.(i,xi,yi)
1 for ( each edge ei;/=[ i, j, , y^])
if (i=j) II self connection
E=E~(eti+eji)
else
if (VjE.V) IIgenerating motif piece
V=V-v..
2
3
4
5
6
7
8
9
10
11
12
13
14
E=E-(e..+eji)
x0=Xi+x..
y0=yi+yij
m=[j,x0
M k=M k+m
Search {j,x0y0)
else if (e-GE) II removed edge
E=E~(eij+eji)
This is a recursive procedure. If a self-connection is encountered, then
remove that edge. Otherwise, if a new vertex (motif piece) is encountered,
(1) remove the new vertex from the list of unvisited vertices, (2) add the
direction vectors of the parent vertex and the new vertex to create a
position vector, (3) assign the position vector to the new vertex, and (4)
add the new generating piece to the current generating set. Then, start a
new search using the newly created generating piece. If the vertex is not
new, simply remove the edge.
The algorithm must traverse each edge in the graph twice, once for each
vertex on the edge. Therefore, the efficiency of this procedure is 0(E),
27
where E is the number of edges in the period graph. The performance
may be enhanced by only checking edges where i < j on line 1.
2.6.2 3D Extension
The generating motif pieces will be 4-tuples instead of 3-tuples. The only
thing that changes in the algorithm is to use the z coordinate when
calculating the position vector for a generating motif piece.
2.7 Record Removed Edges
Removed edges are the edges that were removed to create the spanning
tree. They are used to determine the natural periods if any. Natural
periods and the use of removed edges will be explained in section 2.8. The
removed edges for our example are listed in Table 2.4.
11,6,0,1]
11,8,1,1]
11,9,0,1]
12,9-1,1]
Table 2.4: Removed Edges
2.7.1 Implementation
The procedure is simply an extension to the search that was described in
the section 2.6. The new behavior, in bold and underlined, is to record the
removed edges and link it with the generating set. The efficiency is not
affected.
28
Algorithm: Create generating set of motif pieces and record removed
edges
Definitions:
C = the set of connected components
E = the set of edges from the period graph
V = the set of vertices from the period graph
Rk = the removed edges for component k
Inputs:
P = the period graph
Mk= the generating set of motif pieces for component k
CreateGeneratingSet(P, Mk)
1 Add all vertices to V={ 1,2,3
2 Copy period graph P^E
3 k = l
4 C=J3
5
6 while (V*j0)
7 Mk=0
8 Rk=0
9 Create Ck={Mk,Rk]
10 Get first available vertex in V" and remove (V=Vv0)
11 Create origin motif piece m0=[v0 0,0]
12 Mk=Mk+m0
13 Search(v0 0,0)
14 C=C+Ck
15 k=k + l
29
Algorithm: depth first search
Inputs:
E = the set of edges from the period graph
V = the set of vertices from the period graph
Mk= the generating set of motif pieces for component k
Rk= the set of removed edges for component k
Search (i, y;)
1 for ( each edge e-=[i,j, xtj, y-])
2 if (i=j) II self connection
3 E=E-{eij+eji)
4 Rk=Rk+eu
5 else
6 if (Vj.V) II generating motif piece
7 < II <5 1
8 E=E-(eij+eji)
9 x0=xi+xij
10 yo=yi+yij
11 m=[j,x0y0]
12 M kM k+m
13 Search {j,x0y0)
14 else if (e-EE) II removed edge
15 E=E-(eij+eji)
16 Rh=Rh+eii
2.8 Identify Ghost Nodes
During the depth-first search, certain edges were removed to create the
spanning tree. The removed edges contain direction vectors that may
create a different position vector for a given motif piece. This leads to the
creation of ghost nodes. Ghost nodes are those that have a different
relative position than their counterparts in the generating set. A natural
30
period is the difference between these two positions.
For example, examine removed edge [1,6,0,1]. Its direction vector is [0,1].
We add this vector to the position vector for mi, [0,0] to get [0,1]. Then we
compare the sum to the position vector for me which is [1,-2]. [0,1] is not
equal to [1,-2] so we get the ghost of me at position [0,1]. The natural
period is the difference between the latter vectors. Therefore,
[0,1] [1,2]=[1,3] is a natural period. Figure 2.8 shows this ghost
node, the only ghost for our example.
>V\Ji A /x\\\ / \ /x\\\ /
>>W^ \ /x\\\ / \ 7 Awi" \ \ \ \ /x\\\ /
>Vv/ \ /x\\\ / \ / \ /x\\\ /
\ /x\\\ / \ M\\\ / \ \ \ '' \\ /A \ /x\\\ /
Figure 2.9: Natural Period
To define a natural period, recall the definition of a wallpaper component.
31
A wallpaper component is simply a connected set of motif pieces. Figure
2.9 shows a highlighted wallpaper component with a vector superimposed
on top of it. The vector represents the natural period. The tail has been
set on a motif piece me and the head on the very next me. We can see that,
if we count the tiles between them, we have traveled a distance of [-1,3].
The significance of the natural period vector is that the tiles at the head
and tail receive the exact same coloring. So, if the wallpaper component
was to be translated by a natural period, it would land right back on top of
itself and not some other wallpaper component. If the tile was doubly
periodic, the translation could occur in two distinct directions and a
wallpaper component would still land on top of itself and not another.
In IR2, there can never be more than two valid natural periods. However,
our algorithm so far could produce more than two results for natural
periods. If we find two natural periods, they must be linearly independent
as well. How do we solve the problem of finding more than two natural
periods and guarantee that they are linearly independent? We can use
Hermite Normal Form (HNF) to address this problem. (Please see
appendix A for an explanation of HNF). We place the vectors in a 2 xn
matrix where n is the number of potential natural periods. When this
matrix is run through the algorithm to create a HNF matrix, the result
will be one or two basis vectors [Co95].
It is necessary to run our results through HNF to get a basis or a partial
basis and to ensure that the vectors will be linearly independent. We will
see in section 2.14 that this will also aid in locating the colors for each
motif piece.
At this point, we will have either zero, one, or two natural periods. If we
have zero we call the tile trivially periodic. With one natural period, we
call the tile singly periodic and with two, doubly periodic. If the tile is
doubly periodic, we have a basis and are ready to start coloring.
Otherwise, we must choose one or two collision-free vectors to add to the
set of natural periods so that we may have a basis for a lattice. The
lattice will be discussed more fully in section 2.9. Therefore, in the
trivially or singly periodic case, we must continue to sections 2.10, 2.11,
and 2.12 to find forbidden vectors and choose collision-free vectors. In the
32
doubly periodic case, we can skip directly to selecting color vectors
starting at section 2.13. It might be instructive at this point to see the
examples of the different period types in appendix B.
2.8.1 Implementation
The procedure is to iterate over each removed edge. For each removed
edge [ijjcy], (1) find the position vector of generating piece i, (2) add that
position vector to the direction vector in the removed edge, (3) compare
the sum to the position vector of generating piece j. If the sum vector and
the position vector of piece j are different, find their difference. That
difference is a natural period, so add it to the set of natural periods N.
The efficiency is 0(||i?J|).
Algorithm: calculate natural periods
Definitions:
a-= the position vector of generating motif piece at]
rij=[i> J>by\ = a removed edge from the period graph
Inputs:
Nk= the set of natural periods for component k
Rk = the set of removed edges for component k
CalculateNatural(iVft, Rk)
1 Nk=0
2 for (each removed edge,/v ei2J
3 gl=&i+bij II potential ghost
4 if {Fy*aj)
5 n=g..-aj
6 Nk=Nk+n
7
8 Nk=HNF{Nk)
33
2.8.2 3D Extension
Item related to the 3D extension have been pretty simple up to this point
concerning extending the algorithm into IR3. The most complicated item
has been to carry the hidden z coordinate along in our calculations. But
the procedure gets a little trickier here.
In IR2, we know that when we have a trivially or singly periodic tile, we
must compute forbidden vectors and choose one or two collision-free
vectors. If the tile is doubly periodic, we skip those steps. In IR3, we need
to find a basis of three vectors. So if we have a doubly periodic tile, we
have a dilemma. How do we know if we are working in IR2 or IR3 given
only a period graph? To make matters worse, we will be using 3
dimensional vectors for the direction vectors and position vectors for both
IR2 and IR3.
The answer is that whenever the tile is less than triply periodic, we must
proceed to finding forbidden vectors and choosing collision-free vectors. If
we are dealing with a two dimensional tile, it turns out that we can choose
a collision-free vector that will fit for IR3 and allow the correct
computations for IR2. The main algorithm from section 2.1 then needs to
be adjusted at line 9 to say that if the number of natural periods is less
than 3, continue, otherwise skip to finding color vectors.
2.9 Lattice
The wallpaper components are a graphical representation of a lattice. We
saw in Figure 2.9 how a natural period defines the period of a wallpaper
component. Assume that we have a tile that is doubly periodic. Then
both natural periods would map an Escher tile from one position in the
wallpaper to two others. The tile in the original position and both of the
tiles in the translated positions receive the same coloring. The tiles
intervening tiles must receive different colorings.
For example, Figure 2.10 shows a wallpaper grid with tiles represented as
points on the grid. The vectors are the natural periods, or vectors, that
34
provide a basis for the lattice. The tile at the base of both vectors gets a
coloring scheme. The tiles at the tips of the vectors get the exact same
coloring scheme as the tile at the base. Additionally, the tile at the sum of
the vectors receives the same coloring as the previous three tiles.
Figure 2.10: Lattice Basis
The vectors form an open parallelogram in which lie a set of points, or
tiles. The set of points (tiles) defined by the parallelogram are those that
lie within it an those that coincide with the vectors except at the vector
tips. Each point in the set receives a unique coloring scheme from the
others in the set. It is this set of tiles that is repeated infinitely
throughout the wallpaper. Figure 2.11 illustrates how the patterns are
repeated. Later, we shall see how the lattice will be used to derive a Big
Tile that is used to assign colors in the wallpaper.
35
Figure 2.11: Lattice Pattern
2.10 Compute Forbidden Vectors
We are at this step because we don't have enough natural periods to
create a lattice. We have a tile that is either trivially or singly periodic.
Forbidden vectors are used when choosing collision-free vectors. A
collision-free vector is the distance between two wallpaper components
that do not overlap one another. Therefore, forbidden vectors are the
vectors between two wallpaper components that do overlap one another.
We have to know which vectors are forbidden so we can choose one that is
collision-free. The method for finding forbidden vectors requires some
analysis of the relationship between motif pieces and overlaps. The
method may then be distilled into a few simple steps that are still correct.
The first step in the analysis is to find the equivalent motif pieces.
Equivalent pieces are those that are a linear combination of the natural
period away from each other as expressed in equation 2.1.
36
(2.1)
cTj-a^kn, &eZ
Equivalent motif pieces are grouped together on vertices in the overlap
graph. Figure 2.12 shows the overlap graph for our example. An edge in
the overlap graph connects two vertices if any motif piece overlaps any
motif piece in another vertex. If the tile is trivially periodic (zero natural
periods), then any two motif pieces with the same position vector are
equivalent without regard as to whether they overlap. This is equivalent
to letting n=0 in equation 2.1.
Overlap Graph
Now we can calculate forbidden vectors. Each motif piece on the overlap
graph is connected to an mj. The difference between the mi motif pieces
connected to some mi and m, is a forbidden vector. For example, the
position of the mi connected to m^ is -a] and the mi connected to m& is
-cT6. The difference is a^-a^=[l,-2]-[0,-l]=[l,-l]. Therefore,
[1,-1] is a forbidden vector. For m4 and m9, the difference is
a^-a^=[0,1] [0, 1]=[0,2], so [0,1] is also forbidden. Note that m^
and mg do not overlap each other. However, since me is equivalent to mg,
we must calculate the difference just the same. The two forbidden
vectors, [1,-1] and [0,2], are equivalent because their difference is a linear
37
combination of the natural period [-1,3].
Since one overlap provides a representative for an entire class of vectors,
it is not necessary in the previous example to calculate the difference
between ni4 and mg. The overlap between and me provided the
necessary forbidden vector. In the next step of the main algorithm, the
forbidden vectors will be normalized, therefore, one representative is
enough. In fact, it is only necessary to check the set of overlaps (not to be
confused with the overlap graph) to find all the representative forbidden
vectors.
Thus, the procedure is simplified. We just iterate over each pair of
overlaps while calculating the difference in the position vectors. If the
difference is 0, or not a linear combination of n, then add the
difference to the set of forbidden vectors. The forbidden vectors (not
normalized) for the our example tile are listed in Table 2.5.
[1,-2]
[0,1]
[1,-1]
[0,2]
Table 2.5: Forbidden Vectors
2.10.1 Implementation
The method begins by iterating over every overlap that has been detected.
The difference between the position vectors of the pair of motif pieces is
calculated. If the difference is either 0, or it not a linear combination of
the natural period, then that vector is forbidden. Add it to the set of
forbidden vectors. The method is set up to account for the trivially, or
singly periodic cases by setting an appropriate vector to 0. This causes
the linear combination to be accurate by effectively removing a missing
natural period from the calculations. The efficiency of this operation is
O(IIOH), where O is the set of overlaps. Normalization of the forbidden
vector is a simple calculation that does not affect the efficiency.
38
Algorithm: calculate forbidden vectors
Definition:
oy = an overlap GO of motif pieces i and j
F = the set of forbidden vectors
Inputs:
N= the set of natural periods
0= the set of overlaps
CalculateForbidden
1 F=0
2 if (||iV||=0) m=0
3 if (||iV||=l) m=n
4
5 for (each o^gO)
6 fQ=ajai II possible forbidden
7 if (/0=6 or f0^rm, rGZ)
8 f=NormalizeForbidden (f0) II linear combo
9 F=F+f
2.10.2 3D Extension
The 3D extension is very simple. In IR2, the tile may either have zero or
one natural periods. In IR3, the tile may also have two natural periods.
This is accounted for in the initialization and also when determining if the
forbidden vector is a linear combination of the natural periods. The
changes are underlined in bold below. The efficiency is not affected in IR3.
39
Algorithm: calculate forbidden vectors
Definition:
oy = an overlap eO of motif pieces i and j
F = the set of forbidden vectors
Inputs:
N = the set of natural periods
0= the set of overlaps
CalculateForbidden
1 F=8
2 if(||iV||=0) m,=m2=0
3 if (1|AT|| = 1) m,=n, in2=6
4 if (||AT||=2) m,=n, m2=n2
5
6 for (each o- GO)
7 fQ=ajai II possible forbidden
8 if (/q=0 or f r,sGZ) II linear combo
9 jf=NormalizeForbidden (/'q)
10 F=F+f
2.11 Normalize Forbidden Vectors
We need to reduce every forbidden vector to a minimal range.
Normalization requires finding the least residual of some coordinate in
the forbidden vector. For example, given f=[f1f2\ and a natural period
n=[n1 n2] (there is only one), then we use greatest common divisor
GCD) reduction to normalize f2 with respect to n2. If f2=n2=0, then we
normalize fi with respect to ni. In the trivially periodic case,
normalization does not affect the forbidden vector.
Assume we have a forbidden vector f=[/*1 f2], and a natural period
40
n=[n1 n2]. All forbidden vectors equivalent to f are expressed as
G={f +qn1:qeZ). We want to find some f0^G that minimizes fo2.
Minimizing means finding the least residual f 02=f2mod (n2). Or,
equivalently f2=fo2+(lni2 Then we choose q=[f2ln12J- The
normalized forbidden vector f 0=f -qnx.
The forbidden vectors in Table 2.5 are exactly the set of normalized
forbidden vectors. We can verify this by noting that the second coordinate
for each forbidden vector is 0 < |/2| < |n2|=3.
2.11.1 Implementation
The procedure checks the number of natural periods. In IR2, the possible
number is zero or one natural periods. The forbidden vector does not get
normalized in the trivially periodic case. In the singly periodic case, we
find the least residual as applicable.
Algorithm: normalize forbidden vectors
Inputs:
N = the set of natural periods
f = a forbidden vector
NormalizeForbidden (f)
1 if (||AT||=0)
2 q=0
3 else //||AT||=1
4 if (f2+n2*0)
5 q=[fjn2\
6 else
7 Q=[ful^i\
8
9 f=f-qn
41
2.11.2 3D Extension
For IR3, there can be zero, one, or two natural periods. We will still employ
GCD reduction on the forbidden vector, but in a slightly different manner.
We need to find the least residual of some coordinate in the forbidden
vector with respect to a linear combination of the natural periods. As
before, if the number is zero, then normalization does not affect the
forbidden vector. If the number is one, then normalization occurs exactly
as before. However, if the number is two, then a linear combination of the
two natural periods must be taken into account. We can use the linear
combination of two vectors to handle the case of one natural period by
letting one vector be the zero vector.
Given forbidden vector /=[/\/"2 natural periods ^i=[nnn12ji13],
and n2=[n21n22n23\, all forbidden vectors equivalent to f are
expressed as G={f+sfT1+tn2:s,tEZ}. We want to find some f0eG
that minimizes fo3 subject to
f 03 f 3 (13 t^23) fo3~(2.2)
Let e=gcd(n13n23). Then, e=gn13+hn23 g,hÃ‚Â£.~Z., wheree,g, andh are
the result of the extended Euclidean algorithm. If we let a-n13le, and
b=n23le, then, substituting into equation 2.2 then,
foz=f3-e\s{n13le)+t{n23le)\
=f3e{sa+tb). (2.3)
Next, we let q=[f3le\ Note that
ga+hb=1. (2.4)
Therefore, we can multiply both sides of equation 2.4 by q to get
qga+qhb=q. Let s=qg, and tqh, so that q=sa+tb. The result
is that we find
f03=f3-
=fz~yfzle J(e)- (2.5)
42
(2.6)
Equation 2.5 minimizes fo3 because
|/,o3|
Note that equations 2.5, and 2.6 are just the division algorithm
a=bq+r, with f3a, e=b ,[f3le\=q, and f03=r. [RoOO]. We can now
find values for s, and t and calculate the minimized vector by using
equation 2.7.
>0i fi~(snn+tn21)
f 02 f 2(snl2+tn22)
f 03 f3-{snl3+tn23)
The procedure is much the same as in IR2. We find some non-zero
coordinates to work with and use them to calculate a quotient. Then we
subtract the quotient times the linear combination of the natural periods
from the forbidden vector. This gives us the least residual and normalizes
the forbidden vector. Finding the GCD is a matter of using the extended
Euclidean algorithm [CoLeRiOl]. (Please see appendix A for details of
this algorithm). The efficiency of this operation is that of the Euclidean
algorithm.
43
Algorithm: normalize forbidden vectors
Inputs:
N = the set of natural periods
f = a forbidden vector
NormalizeForbidden (f)
1 if (||AT||=0)
2 g=0
3 else
4 if (||AT|| = 1) m^=n^ rn2=6
5 if (||iV||=2) m^nl m2=n2
7 if (m13 + m23^0)
8 (e,g,h)=ExtendedEuclid(m 13 ra23)
9 9=l//eJ
10 s=qg
11 Ã‚Â£=<7/1
12 if (m12+m22^0)
13 (e,g,&)=ExtendedEuclid(m12 m22)
1 if (/*3<0) /=-/
14 ?=i/yeJ
15 s=<7g
16 t=qh
17 else
18 (e,g,h)=ExtendedEuclid(mn m21)
19 q=[fnle\
20
21 tqh
22
23
44
2.12 Choose Collision-Free Vectors
At this point, we know whether we are trivially or singly periodic, and we
have a set of normalized forbidden vectors. The correct choice of a
collision-free vector is one that is not a linear combination of the forbidden
vectors and the natural period. Note that the zero vector is always a
forbidden vector. It is at this point that we start adding vectors to the set
of natural periods. The set will continue to called N even though it may
not be solely comprised of natural periods. In our example, we can choose
[1,0] for the collision-free vector. This vector will be used to create the
lattice, shown in Figure 2.13, that is used for coloring motif pieces in the
wallpaper.
A
Figure 2.13: Lattice
45
2.12.1 Implementation
The task is to iterate over enough vector values until we have two valid
choices. If the number of natural periods is zero, the first choice is used as
if it were a natural period to ensure that both choices are linearly
independent.
There is a challenge as to how to set the limits for iteration. Vector
choices would iterate over values for [a,6]. If we let the limits be infinite,
then the b values will never go past zero. This situation invites the
possibility of an endless loop. The solution is to place a maximum on the
iteration for a and b values. If we set these limits high enough, we will
find a collision-free vector. If they are too low, we will not find a collision-
free vector. If they are too high, performance will be affected.
For simple Escher tiles, a small limit (16) seems to be more than
adequate. But this might not be high enough in some extreme cases and a
vector would not be chosen. One possible solution is to have rolling limits.
Rolling limits would be implemented as follows. Each time both a and b
limits are exhausted, and the number of periods is still less than two,
reset the upper and lower limits and start again. This solution is not part
of the implementation to date. With this in mind, the worst case is when
the maximum values for x, and y are reached. Therefore, the efficiency for
this operation is 0(xmax ymaJ.
46
Algorithm: choose collision-free vectors
Inputs:
N = the set of natural periods
F=[fx f2-",fn}= the set of forbidden vectors
ChooseColllisionFree {N ,F)
1 if (||AT||=0) m=0
2 if (||A/j| = l) m=nl
3
4 OUTER_LOOP:
5 while (||AT||<2)
6 for (a=0 to maxa)
7 for (6=0 to maxb)
8 v=[a,b]
9 for (i=l to \\F\\)
10 c=v-fi
11 if (c^sm, sGZ) // linear combo
12 N=N+v
13 if (m=0)
14 65=6^
15 continue OUTER_LOOP
2.12.2 3D Extension
In R3, the number of possible natural periods changes. Only minor
adjustments are needed for implementation in 3D. The changes are
highlighted below. Since there is one more coordinate to account for in
the iteration, efficiency is increased to 0(xmax 3W zmax).
47
Algorithm: choose collision-free vectors
Inputs:
N= the set of natural periods
F'={f1f2...,fn}= the set of forbidden vectors
ChooseCollisionFree (N, F)
1 if (||AT||=Q) rn,=Tn,2=0
2 if (||AT|| = 1) m^=iV1 fn2=0
3 if(|lAT|l=0) in=N~,
4
5 OUTER_LOOP:
6 while (||iV||<2)
7 for (a=0 to maxa)
8 for (6=0 to maxb)
9 for (c=0 to maxe)
10 v=[afbfc]
11 for (i = l to ||F||)
12 c=v-fi
13 if (c^smj+f
14 N=N+v
15 if (nf2=0)
16 m2=v
17 if (/rf, =6)
18 rn^v
19 continue
2.13 Compute Big Tile Size
//
linear combo
We have arrived at this step with the necessary number of period vectors,
either natural or collision-free. In IR2, that number is two. Before we can
continue, we must first normalize the periods. We perform the HNF
48
algorithm on the matrix to normalize the basis. This will be very useful
for the next step when we look for color vectors. Equation 2.9 is the result
of running the natural periods in equation 2.8 through the HNF
algorithm. The normalized lattice is illustrated in Figure 2.14.
tf={[-l,3],[l,0]}=
1
0
(2.8)
HNF{N) =
1
0
0
3
(2.9)
A
P
Figure 2.14: Normalized Lattice
The Big Tile Size is the width and height of a set of unit tiles which will
be used to assign colors to the motif pieces. Each tile in the Big Tile
represents a location that will receive a different coloring than other tiles
in the Big Tile. Finding the Big Tile size (BTS) depends on the set of
periods, which contains the either natural periods, collision-free vectors,
49
or both. The object is to find values that minimize the width and height.
We will begin by finding the width.
Given W={n1,n2} =
n n n21
n!2 n22
, let A = determinant of N. Find a minimal
x value that is a linear combination of periods
xi^rn^+sn^ r,seZ, i=[l,0].
Then, equation 2.10 may be expressed as
X = /in n2l r => r N = X => r =N~1 X
0 "12 U22 s s 0 s 0
___! 1
Recall that the inverse of N is N =
A
U22
n
-n,
21
12
n
n
therefore,
Solving for r and s in equation 2.12 gives us
r =
s =
n
22
\AI
X,
and
n
21
X.
The smallest xeZ+ that satisfies equations 2.12 and 2.13 is
4
x =
gcd{n12n22)
(2.10)
r 1 n22 -^21 X 1 xn22 (2.11)
s A 1 to nn 0 ~xn12
(2.12)
(2.13)
(2.14)
Next, we will find the height. We use the same reasoning for the y value
as for the x value. Find a minimal y value that is a linear combination of
the periods
y j=rn1+sn2 r,seX, y'=[0,l]. (2.15)
Then, equation 2.15 may be expressed as
50
(2.16)
0 nn n2i r => r N = 0 => r II i 0
y. 1112 n22 s s y_ s
Substituting the inverse,
r 1 n22 ~n2l 0 l -yn 2i
s A ~nU nn y_ A yn n
Again, solving for r and s in equation 2.17 gives
n
r =
21
y,
s =
nn
^A,
The smallest yG Z4
and
that satisfies equations 2.18 and 2.19 is
(2.17)
(2.18)
(2.19)
y=
gcd(nun21)
(2.20)
The width is the x value and the height is the y value. We use the results
from equations 2.14, and 2.20 to calculate the Big Tile Size.
Big Tile Size BTS = width X height
BTS =
A v A
gcd(n12n22) gcd{nnn21)
(2.21)
Using equation 2.21 in our example, we find that |a|=3, and
BTS = 1x3. We also know that A is the total number of colors necessary
for coloring. The uncolored Big Tile is shown in Figure 2.15.
51
Figure 2.15: Uncolored
Big Tile
2.13.1 Implementation
Implementation is matter of correctly implementing equation 2.21 using
linear algebra [St03] and the Euclidean algorithm [CoLeRiOl]. Linear
algebra is used to find the determinant. The Euclidean algorithm is used
to find the GCD of the vector values.
2.13.2 3D Extension
The Big Tile size in R2 is just a special case of the Big Tile size in R3. The
reasoning is almost exactly the same. The difference is that now we use
52
the z coordinate to express the depth. Again, we start by finding the
width.
Given
N={nltn2,fQ=
nn U21 U3l
ni2 n22 n3X
ni3 U23 n33
, let A = determinant of N.
Find a
minimal x value that is a linear combination of periods
xi=rfT1+sn2+tn3 r,s,t&~Z., i=[ 1,0,0].
(2.22)
Then, equation 2.22 may be expressed as
X /In n2\ n31 r X r X
0 = 12 U22 n3l => s N = 0 => s H 1 Ã‚Â£ II 0
0 "13 U23 3 CO CO t 0 t 0
Let the transpose of the cofactor matrix of N,
Nct
A D G
BEG
C F I
(n22n33
(ni3 U32
(n!2n23
~n23n3?) (^23^31
~ni2n33^ (niin33
~ni3n22^ (n\3n2l
n2in33)
~ni3n3l)
~nnn23)
(n2in32 n22n3l)
(n 12 ^31 ^11^32)
(^11^22-^12^2l)
Therefore,
r 1 A A D G X 1 xA
s t B E H C F I 0 0 -L A xB xC
Solving for r, s and t in equation 2.26 gives us
r =
A
A. x =
(n22n33 n23n32^
X,
(2.23)
(2.24)
(2.25)
(2.26)
(2.27)
53
s =
B
A
JC
~\a
II (ni3n32 nV2n33^
A
II Kn12n23-n13n22)
A
x, and
x.
(2.28)
(2.29)
The smallest xGZ.+ that satisfies equations 2.27, 2.28, and 2.29 is
A
x =
gcd(A,B ,C)
gcd{(n22n33 n23n3^), {n13n32 n12n33), (^12^23 ^13^22))
(2.30)
Next, we will find the height. Find a minimal y value that is a linear
combination of the periods
yj=rn1+sn2+tn3 r,s,te Z, j'=[0,l,0].
Then, equation 2.31 may be expressed as
(2.31)
0 nn n21 n31 r 0 r 0
y = nn U22 n31 => s N = y => s =N~' y
0 niz U23 U33 t 0 t 0
Substituting the inverse,
r 1 A D G 0 1 yD
s t A B E H C F I y 0 A yE yF
(2.32)
Again, solving for r, s and t in equation 2.32 gives us
x,
r=
s =
1
D
x =
IE
X
Al
(n23n31-^2in33)
x, and
(2.33)
(2.34)
54
t=
lp\
A
x =
(n13n21-nun23)
x.
(2.35)
The smallest yeZ+ that satisfies equations 2.33, 2.34, and 2.35 is
4
y=
gcd(D ,E ,F)
gcd((n23n31 n21n3g),(ujjUgg n13n3l),(nl3n21 n.un23))
Next, we will find the depth. Find a minimal z value that is a linear
combination of the periods
zk=rn1+sn2+tn3 r,s,t^7L, Ã‚Â£=[0,0,1].
Then, equation 2.44 may be expressed as
(2.36)
(2.37)
0 Tin n21 n31 r 0 r 0
0 = ni2 U22 n31 => s N = 0 => s =AT1 0
z nX3 n23 U33 t z t z
Substituting the inverse,
r 1 ~ A A D G 0 1 ~ A zG
s B E H 0 zH
t Zj C F I z lA zl
Again, solving for r, s and t in equation 2.40 gives us
s =
t =
yG'
\^/
*4,
z=\
z =
\(n2in32 n22n3l)
(n12n31-nun32)
z,
z, and
z =
(nnn22 ^12^21)
(2.38)
(2.39)
(2.40)
(2.41)
(2.42)
(2.43)
The smallest yeZ+ that satisfies equations 2.41, 2.42, and 2.43 is
55
4
gcd(G,H,I)
______________________________A___________________________
gcd{{n2l ^32 ^22 ^31) > (^12 ^"31_^"11 ^32) > (^11 ^22 _^12 ^2l))
The width is the x value, the height is y value, and the depth is the 2
value for the Big Tile Size.
Big Tile Size BTS = width X height X depth
(2.44)
BTS =
4 4
gcd(A, B, C) A gcd(D ,E ,F) A gcd(G,H ,1)
A
___________________________________________________ x
gcd ((n.22 ^33 ^23^32)> ( ^13 ^32 ^'12^33)^ (^12 ^23 ^13 ^22))
___________________________________________________ x
gcd((n23n31n21n33), (nnn33n13n31), (n13n21nnn23))
_________________________A_________________________
gcd {{n21 n32-n22 n31), (n12 /i31 -/iu n32), {nn n22-nl2 n21))
(2.45)
We use linear algebra and the Euclidean algorithm to implement equation
2.45 in the 3D extension. Notice that if we let n13=n23=0 and
^31=^32=^33 = 1, then equation 2.45 reduces to equation 2.21.
2.14 Locate Color Vectors
Now that we have found the lattice, or set of periods, we can begin to color
the motif pieces. But first we need to identify the colors. This procedure
involves choosing points (vectors) inside the open parallelogram created
by the period vectors. Valid points are points that are located on the
period vectors but not at their tips, and inside the parallelogram but not
on the open boundary. Remember that we will use the normalized lattice
as shown in Figure 2.14. The choices for color vectors are listed in Table
2.6.
56
[0,0]
[0,1]
[0,2]
Table 2.6: Color Vectors
2.14.1 Implementation
At this point, we have found the natural periods and collision-free vectors.
The next step is to identify the set of color vectors so that individual motif
pieces may be colored correctly. The color vectors are those points within
the half open parallelogram in IR2 (or the half open parallelepiped in IR3).
Figure 2.16 is a geometric representation of some general parallelogram
in IR2. An explanation of terms will follow. We begin the discussion by
examining the conditions in IR2 using vectors in IR3 After that, we will
extend the discussion to cover the conditions for IR3.
57
Figure 2.16: Open Parallelogram
We start by defining the problem domain. The set of vectors is the set of
natural periods and/or collision-free vectors:
V=Ky2/3) =
V2i v3i
V\2 V22 V32
V13 V23 V33
(2.46)
We apply the Hermite Normal Form algorithm to the matrix to derive, the
matrix N. N describes a vector space equivalent to V.
N=HNF{V) =
nn n21 "31
0 n22 "32
0 0 U33
(2.47)
This gives us a set of vectors with the properties shown in Table 2.7.
58
coincides with the x -axis.
n2 is anywhere in the XY plane except the x-axis.
n3 is anywhere in 3-space except the XY plane.
Table 2.7: HNF Lattice Properties
Note that we let n3=[0,0,1] when we want to consider only IR2. Table
2.8 defines the terms we saw in Figure 2.16.
R = the region inside parallelogram defined by and n2
c=rtl+n2
p = a point inside R and on n[ and n2
(not including points at the ends of and
q=c-p
i=[ 1,0,0] (unit vector)
a = the angle between i and
P = the angle between i and n2
a '= the angle between i and
*
P= the angle between i and n2
y= the angle between i and p
y'= the angle between -i and q
Table 2.8: Open Parallelogram Definitions
Note that the angles p and P' are equal. This is not necessarily the case
with y and y'. Additionally, a=a=0.
Upon analyzing the aforementioned angles we can see that the
relationships shown in Table 2.9 are true.
59
a='=0 (because of HNF)
r = ~P
cos(a)=cos(a') = l
cos(/J)=cos(/T)
0
cos(/J)
cos(f$ ')
Table 2.9: Lattice Angle Properties
From this we find the important inequalities in equations 2.48, and 2.49.
For a point to be inside the open parallelogram, both of these inequalities
must be true for any point we test.
cos(/$)
cos(0)
Since we know the values of the vectors, we can compute the cosines.
cos(/J) =
cos(y)=
cos(y') =
"21
+n
2
22
("ll + "21 Pi)
^(nn+n21p1f+(n22p2f
(2.50)
(2.51)
(2.52)
Now that we can compute the cosine values, we now need a range of
points to test. The maximum range is defined by the vectors
nx,n2, and c So, we let x and y range over the intervals in Table 2.10.
60
X
mm max
v < v < v
J mm J J max
where
xmin = min{0,n 21)
Xmox = maX(n 11, Cl)
ymin=min( 0^22)
ymax = maX(n 22)
Table 2.10: Iteration
Ranges
As we iterate over these x and y values, we let p=[x, y, 0] and evaluate
p against the angle intervals described earlier.
We are now ready to define an algorithm that will work in IR2. After a
discussion of the algorithm in IR2, we will extend the algorithm to work for
both IR2 and IR3. If we let dx=xmax-xmin, and d^y^-y^, then the
efficiency of this operation is 0(dx dy).
Algorithm: locate color vectors
Inputs:
N = the set of period vectors
LocateColors (N)
1 for (x=x to xm)
2 for {y=ymin to ymJ
3 p=[*,:y,o]
4 q^+r^-p
5 calculate cos(y)
6 calculate cos(y')
7 if (cos(^) < cos(y) < 1 and cos(/3') < cos(y') < 1)
8 add p to the set of color vectors
61
2.14.2
3D Extension
Figure 2.17: Open Parallelepiped
Up to now, we have not discussed the third vector, n3. For IR2, it is
implied that n^=[0,0,1] for reasons that will soon become clear. This
last vector is anywhere in IR3 except for the XY plane. Referring to Figure
2.17, we see the projection of n3 onto the XYplane labeled nz'. We
need the definitions in Table 2.11.
62
ti3'= the projection of nz onto the XY plane
Q= the angle between i and nz
Table 2.11: Parallelepiped Definitions
The three vectors in N describe an open parallelepiped where we must
search for color vectors. We now know how to search for points when
z=0. In IR3, this is a matter of searching for the x and y values of
points for all the other values of z. For example, imagine a plane parallel
to the XY plane and passing through z = 1. The intersection of this plane
and the parallelepiped creates an nearly exact duplicate of the original
parallelogram. The only difference is that this new parallelogram might
be shifted by some amount in the x and y directions in relation to the
original. The amount of shift is defined by the angle 6 and the value ofz.
Equation 2.53 defines a shift vector to tell us where the new
parallelogram is in relation to the one at z=0 for each new value of z.
e=[zcos(0), zsin(0), p3]
(2.53)
Note that if n3=[0,0,n33], then e=[0,0,p3]
We need the shift vector for two purposes. The first is to adjust the
vectors for each point p we test, and to shift the range of x and y, as we
iterate over z values. The shift vector tells us where the projection of the
parallelogram onto the XY plane, R', will be located.
We adjust the vectors p and q by subtracting e from them. This
causes p and q to point to integer coordinates if e does not have
integer coordinates. This is the case if R is between integer coordinates
in either the x or y direction.
(2.54)
q =q-e
(2.55)
P =P~e
We also adjust the range for x and y by adding the corresponding e
coordinates to the minimum and maximum values of the ranges.
[zcos(0)J
63
(2.57)
[zsin(0)J
Therefore, as the parallelogram shifts for each new value of z, we may
have a new set of x and y points to test. This also keeps us from pointing
too far away with our test points whenever R' is between x and y integer
coordinates.
We calculate the sine and cosine of the projection vector as shown in
equations 2.58 and 2.59.
cos(0)=
n
31
yfn'
31
+n
> 2
32
(2.58)
sin(0) =
|| [-7T31 0,0] |1 _ n'32
11*11 Ill'll Vrc'gi + tt'L
(2.59)
We evaluate the angles (a, 0, y, etc.) as before except we use the adjusted
points p' and q to calculate the angles. If p' or q are accepted as
valid within the angle ranges, then we add p and q, respectively, to
the set of color vectors. Equations 2.60 and 2.61 show the new
calculations for p and q.
Pj' pj-zcosfe)
cos(y)= ,=, ---
1Jpl+P'l V(Pi-2COs(0))2+(p2-zsin(0))2
n11+n21-p1-zcos(0)
cos(y )= ,
yj{nn+n21-p1-zcos{e))2+{n22-p2-zsin(e))
2
(2.60)
(2.61)
The efficiency of the operation is augmented by the magnitude to the
projection of ri3. Therefore, in IR3, the efficiency is 0(dx dy n33) where
dx and dy are as defined in section 2.14.1.
64
Algorithm: locate color vectors
Inputs:
N = the set of period vectors
LocateColors (N)
1 for (z =0 to n33-1)
2 e=[zsin(0), zcos(0), z]
3 *w=Km+2:sin(0)J
4 ^pper = t^mo, + 2:sin(0)J
5 :ywr=lymin+zcos(0)j
6 yupper = \.ymax~^^ COS (0)J
7 for {x=xlower to xupper)
8 for (v = v, to v )
\J Slower S upper /
9 P=[x,y,z]
10 q=n1+n2p
11 p'=P~e
12 P=q~e
13 calculate cos(y) at p'
14 calculate cos(y') at q
15 if (cos(fl) < cos(y) < 1 and cos(^') < cos(y') < 1)
16 add p to the set of color vectors
2.15 Assign Colors to Lattice Points
Returning to the uncolored Big Tile in Figure 2.15, we see every motif
piece that we need to color. We will color the Big Tile then use the Big
Tile to tile the wallpaper. Almost as if by magic (not really, though),
every wallpaper component will be colored so that a wallpaper component
will have a different color than another wallpaper component it happens
to overlap.
Given periods A{n x ,n2}
n ii n2i
*12 *22
, color vectors K={kl, k2,...kn}
65
and r,sE Z, a Big Tile position of a motif piece is defined as
p=ki+rnl+sn2.
It follows that
=at1
r
s
Pi~ku
P2~ki2
AT-1 J-
Recall that the inverse of AT is A/ =
A
Therefore,
n
22
n
21
-n12 nu
r _ 1 n22 n2\ Pi~ku
s -n12 nu P2~^i2
Let
^22^Pl ^n) ^21 (P2
nu(P2-ki2)-ni2(Pi-kil)
Then test
(2.62)
(2.63)
(2.64)
0=r'{modAN) and 0=s'{mod(2.65)
The worksheet in Table 2.12 shows all the assignments that need to be
made. Figure 2.18 shows a colored Big Tile. We know that there are
three unit tiles in our Big Tile. Each unit tile has nine motif pieces.
Therefore, there are 27 color assignments to make, nine for each Big Tile
location. The determinant tells us that three colors will be used, so each
color must be used a total of nine times in the Big Tile. In general, each
color must be used the exact number of times every other color is used.
This fact helps provide a method to double check the calculations.
66
BT loc Motif Sum Linear combo
[a,b] - [mi,x,y] = P r' i r' 2 s' 2 choose
[0, 0] [1, 0, 0] [0,0] 0 -3 -3 0 1 2 [0,0J
[0,0] [2, 1, 0] [-1,0] -3 -6 -6 0 1 2 [0,0]
[0,0] [3,1, -1] [-1,1] -3 -6 -3 1 2 3 to,2| '
[0,0] [4, 0, -1] [0,1] 0 -3 -3 1 2 3 ~to;2T
[0,0] [5, 1, -1] [-1,1] -3 -6 -3 1 2 3 to, 2]
[0,0] [6, 1, -2] [-1, 21 -3 -6 -6 2 3 4 [0, 1]
[0,0] [7, 2, -2] [-2, 2] -6 -3 -9 2 3 4 [0,1] '
[0,0] [8, 1, 1] [-1, -1] -3 -6 -6 -1 0 1 [0, lj
[0,0] [9, 0, 1] [0, -1] 0 -3 -3 -1 0 1 [0,1]
[0,1] [1, 0, 0] [0, 1] 0 -3 -3 1 2 3 to,2l
[0,1] [2, 1, 0] [-1, 1] -3 -6 -3 1 2 3 10, 2J
[0,1] [3, 1, -1] [-1, 2] -3 -6 -6 2 3 4
[0,1] [4, 0, -1] [0, 2] 0 -3 -3 2 3 4 iSjtr
[0,1] [5, 1, -1] [-1, 2] -3 -6 -6 2 3 4
[0,1] [6, 1, -2] [-1, 3] -3 -6 -6 3 4 5 (Ml
[0,1] [7, 2, -2] [-2, 3] -6 -9 -9 3 4 5 r WM~
[0,1] [8, 1, 1] [-1, 0] -3 -6 -6 0 1 2
[0,1] [9, 0, 1] [0, 0] 0 -3 -3 0 1 2 10,0;
[0, 2] [1, 0, 0] [0, 2] 0 -3 -3 2 3 4 10, 1]
[0, 2] [2, 1, 0] [-1, 2] -3 -6 -6 2 3 4 [0,1]
[0, 2] [3, 1, -1] [-1, 3] -3 -6 -6 3 4 5 TOT"
[0, 2] [4, 0, -1] [0, 3] 0 -3 -3 3 4 5 TCiol
[0, 2] [5, 1, -1] [-1, 3] -3 -6 -6 3 4 5
[0, 2] [6, 1, -2] Tl,4] -3 -6 -6 4 5 3 tOP
[0, 2] [7,2, -2] [-2, 4] -6 -9 -9 4 5 T FT2T
[0, 2] [8, 1, 1] [-1, 1] -3 -6 ne~ 1 2 |3| to sr
[0, 2] [9, 0, 1] [0, 1] 0 -3 ^- 1 2 [0,2]
Table 2.12: Color Assignments
i
67
Figure 2.18: Colored
Big Tile
This is almost the last step in the coloring algorithm. The information
that seeds this algorithm may come from the design tool that was
mentioned in the beginning of this thesis. It is now time to pass the
coloring information back to the coloring machinery of the design tool. In
effect, the coloring can happen in real time while a tile is being designed.
Recall that the coloring information at this point is for one connected
component. This has to be taken into account when choosing colors to fill
a palette. The strategy is to disallow the choice of a color for any other
motif piece, in any other component, once it has been assigned within
another component. For example, if red, blue, and green have been used
for component A, then they are not available for component B of the same
68
tile. This choice could be implemented here. But it seems better to let the
object actually in charge of coloring to make that decision. Thus the
design tool receives generic color vectors and decides which colors to take
from the palette.
Figure 2.19: Numbered
Big Tile
We begin by assigning each unit tile in the big tile a location vector. This
assignment is illustrated in Figure 2.19. For each Big Tile location, each
motif piece must get the correct color. A Big Tile location is the sum of a
color vector plus a linear combination of the periods. The procedure for
color assignment is to iterate over every motif piece at every Big Tile
69
location and plug in each color vector. If a linear combination is found for
a color during iteration, then assign that color to the current motif piece.
The efficiency for this procedure is 0(A B ||MJ| H-KJI).
Algorithm: assign colors
Inputs:
BTS=AxB
A = the determinant of ft (the set of periods)
Kk={k1 k2..., kn}= the set of color vectors
Mk=[mx m2..., mn}= a generating set of motif pieces
(Recall mi=[i,jc,y]=[i,a)])
AssignColors (A,B,A,M ,K)
1 for (a=0 to A-l)
2 for (6=0 to B 1)
3 for (i = l to ||MJ|)
4 for (j = l to \\Kk\\)
5 ~p=[a,b]ai
6 calculate s' and t'
7 if (s' and t '=0(mod A))
8 assign kj to mi in position [a, 6]
2.15.2 3D Extension
There is a little more work involved to carry out the calculations in IR3.
But, the algorithm is only slightly changed to account for the extra
coordinate. Note that, in both IR2 and IR3, it is necessary to check all sets of
modulus equations (r, s, and t (mod A )).
Given periods N={nx,Tr2>n^)
color vectors K=[kl,k2,...kn\, and r,s,tE Z, a position of a motif
nll n21 n31
= ni2 n22 n33
ni3 n23 3 CO CO
70
piece is defined as p=ki+rn1+sn2+tn3. Therefore,
r Pi~ka
s =N~l P2~ki2
t Pz~kj3
(2.66)
Using the transpose of the cofactor matrix of N from equations 2.24, and
2.25,
Let
r 1 A D G Pi~ku
s t X ~A B E H C F I P2~ki2 P3~ki3
(2.67)
r {Px-ka)A {p2-ka)D {p3-ka)G
s' (Pi~ka)B (P2~ki2)E (P3-ka)H
t' (Pi~ka)C (p2~ki2)F {Ps-k^I
(2.68)
Then test
0=r'(modAN),
0=s'{modAN), and 0=t(modAN).
(2.69)
The algorithm is similar to the case in IR2 and highlighted below. In this
case, the revised efficiency is 0(A B C ||AfJ| H-KJI).
71
Algorithm: assign colors
Inputs:
BTS=AxBxC
A = the determinant of ft (the set of periods)
Kk={k1k2 ...,kn}= the set of color vectors
Mk={m1 m2..., mn}= a generating set of motif pieces
(Recall mi=[i,a:,y>z]=[i,gi]) 1 2 3 4 5 6 7 8 9
AssignColors (A, B, Q, A, M, K)
1 for (a=0 to A-l)
2 for (6=0 to B 1)
3 for (c=0 to C-l)
4 for (i=l to ||MJ|)
5 for (j = l to ||tfj|)
6 p=[ a, 6, c 1 a;
7 calculate r . 8' and t'
8 if (r'fs and t=0(modA))
9 assign fe, to mi in position [q,6,c]
2.16 Color the Tile
This is the step where we complete the loop in relation to the design tool.
We finally get to transmit color information back to the design tool. The
design tool will receive and interpret the color assignments, and assign
colors to the polygons that have been built. A possible software design
might allow the user interface to be decoupled from the algorithm
implementation in a client-server relationship. In other words, the color
calculations could be kept separate from the graphical rendering in the
design tool. Thus, performance could be enhanced by allowing rendering
and computations to be performed in separate environments.
If there are multiple wallpaper components, they all have their own Big
Tile size. If all the Big Tile sizes are identical, then they will all fit into
72
the same Big Tile. However, the case may be that different wallpaper
components have different Big Tile sizes. In that case, a big Big Tile size
needs to be found so that all the Big Tiles will fit within it. To find the big
Big Tile size the least common multiple (LCM) of all the corresponding
dimensions for each Big Tile must be calculated. For example, in IR3,
given two Big Tile Sizes BTS1=A1 X B1xC1 and
BTS2=A2 X B2xC2, then the big Big Tile Size
bBTS=\cm(A1, A2) X lcm(B1,B2) X lcm(C1 C2). (2.70)
Recall that lcm(a, b)=ablgcd(a,b) [RoOO]. We can find the GCD, and
by extension, the LCM of two integers using the Euclidean algorithm.
This is a computation that should be added to the design tool so that
rendering may be adjusted as necessary.
73
3. Conclusion
Now that we see how to compute the coloring for an Escher tile, we can
wonder where it will lead. Looking back, we touched on implementing
algorithms for dealing with vectors and matrices utilizing principles found
in linear algebra. We saw how to manipulate the vectors using GCD
reduction and the Hermite Normal Form that draws on techniques from
number theory. We mentioned the design tool that uses graphics
programming to aid in visualization and creation of tiles in both IR2, and
IR3. We drew on techniques from basic geometry to help identify points in
a lattice.
An important aspect of the implementation is that all the steps involved
are efficient. This means that we can expect the overall run time to be in
a manageable range. While we are not looking for real time
computations, we will be happy that the algorithm will finish quickly.
Most Escher tiles are relatively simple. They have few motif pieces and
few connections. That means that the software implementation should be
fast enough so that a user of the design tool will not have to wait a
noticeable amount of time for coloring.
Looking forward, it is easy to imagine a wide range of possibilities. The
design tool may be used to create strange and wonderful new Escher tiles.
Many of M. C. Escher's tiles were formulated on a basic pattern within a
5x5 grid. This motif pattern may be used in several permutations to
create a lot of interesting patterns. We do not have to be limited to a grid
or even straight lines when creating a tile. Unit tile patterns, for
instance, do not have to be polygons. They can be a set of lines, or a
combination of lines and polygons. We are not even constrained to create
two dimensional tiles. When we look into three dimensional layouts, we
add three dimensional solids to the list of possible motif pieces. The
aesthetic possibilities abound.
3.1 Design Tool
The design tool holds much hope for possibilities. With this tool, a
74
designer or artist is free to create new tiles that have not been seen
before. The tool was developed as part of a related project. To be truly
automated, the coloring algorithm needs to have some sort of input. In
fact, the first steps down the road to coloring require that we label motif
pieces, and find their relationship to one another through connections and
overlaps. The last step implicit in the algorithm is that a person actually
colors a physical wallpaper. The design tool is intended to fulfill those
steps in the algorithm.
3.2 Future Considerations
As humans, we can sit down with a sketch pad, draw tiles, then
wallpapers based on that tile. A few talented souls, M. C. Escher being a
notable example, have the time, talent, and resources to produce such
creations. The hope for the design tool is to make this type of endeavor
accessible to a wider range of people and possibilities. It should make
creating tiles easier so that people can create pleasing wallpapers. New
wallpapers mean that students and scholars might gain new insight by
having a concrete example to manipulate.
Earlier we mentioned extending Escher tiles into three dimensions. This
holds promise for further exploration. Problems such as using tiles other
than square tiles could be explored. For instance, the Euclidean plane can
be tiled by squares, regular hexagons, and equilateral triangles. Motif
pieces could be drawn on hexagons or triangles and then used to tile an
area. The problem of how to define connections and boundaries could be
posed. With square tiles the Big Tile is and area outlined by straight
lines. It may be that Big Tiles using triangles, and certainly hexagons
would not have straight edges. Triangles should be problematic because
they must be translated so they can tile a plane. This could possibly make
connections harder to define. Escher also created work that explored the
hyperbolic plane. This is an interesting area of exploration as well.
There are many areas that beg to be explored when it comes to Escher
tiles as it is with the rest of M. C. Escher's work. He inspires us not only
with beauty and form but with the infinite possibilities that exist in his
patterns.
75
APPENDIX A
Algorithms
The following algorithms are listed in this appendix to provide an
illustration of their implementation. They have been used as part of
the implementation but not described in the text.
A.1 Extended Euclidean
Given a, b, c Z, the greatest common divisor (GCD) c is the
greatest integer that will divide both a, and b. Additionally, c may be
expressed as a linear combination of a, and b. Given /, ge Z, then
c=fa+gb [RoOO]. The extended Euclidean algorithm computes c as
well as providing the two factors f, andg [CoLeRiOl].
The algorithm depends on the fact that gcd (a,b)=gcd (b, a mod b)
[CoLeRiOl]. If b=0, then a is the GCD. Otherwise, find the
remainder, r=amodb, and recurse with b and r. As the algorithm
ascends out of the recursions, the quotient q=[alb\ is used to
calculate valid factor values at each step as the algorithm ascends out
of the recursion. When the method completes, / and g are valid factors
for c =fa +gb. The efficiency of this algorithm is proportional to
0(log b) for a>b>0.
76
Algorithm: extended Euclid
Inputs:
a,bG Z
ExtendedEuclid (a ,b)
1 if 6=0
2 (c,f ,g)={a, 1,0)
3 else
4 r=a mod b
5 (d, x, ;y)=ExtendedEuclid(6, r)
6 q=[a/b\
7 t=xqy
8 [c,f ,g)={d,y,t)
9
10 return {c,f,g)
A.2 Hermite Normal Form (HNF)
Hermite Normal Form is a form of matrix and also refers to the algorithm
for normalizing matrices [Co95], In general, the result is a matrix of the
that, given the matrix A=aij, satisfies
1. Uy=0 for i> j,
2. au>0 for all i, and
3. 0i,
or, as an mxn matrix with m
0 0 0 * * ... *
A = 0 0 0 0 * ... *
0 0 0 0 0 *
77
50
In our explicit case for the Escher coloring, m=n=3, so the result matrix
form is
* * *
A = 0 * *
0 0 *
The algorithm starts at the bottom right and works its way up the
diagonal. The zero values are the result of performing GCD reduction on
the columns to the left of the current diagonal element. The result is that
the diagonal entry contains the non-negative GCD of every element to the
left in the row or zero. After the every element to the left is zero, a final
reduction is performed on the columns to the right.
The initialization of the algorithm is just setting indices for iteration.
After initialization, the algorithm performs the reductions using column
operations.
Since the algorithm is computing a GCD the efficiency is related to that of
the Extended Euclidean algorithm. Assuming m
n 1 operations on the last row at each iteration until every value
except the last is zero. So efficiency for that row is 0 ((n -1) log *),
where x is the least value in that row. For the next row, efficiency is
0((n2)logx), and so on. Every column operation involves m
operations for each element in the column. Therefore, overall efficiency is
0(ra2nlogx).
78
Algorithm: Hermite normal form (HNF)
Definitions:
A= an mXn matrix
i,j,k,l,d GZ= matrix indices
A;= a column in A
min = temp variable for minimum value
allzero = boolean status of row
Inputs:
A= the matrix to be reduced
Initialize:
1 i=k=1
2 if (m
3 b=m
4 if (m>n)
5 b=n
79
HermiteNormalForm (A)
1 while (k
2 s=1
3 while (s^O)
4 min=0
5 d=-1
6 for (j=0 to k 1) // findleast^a^O, j>l
7 if (a^0 and (min=0 or mm>|aj))
8 mm=|a^| d=j
9 if (d^1) // foundajj
10 if ((0^=0 and a^ne0) or (a^O and |a^|
11 swap(Ad, Ak)
12 "o' & A o
13
14
15 s=0
16 for (j=n l to k 1) II column reductions
17
18 >> II > II
19 s=s+a V
20
21 if (att=0)
22 k=k l
23 else // final reductions
24 for (j=k l to 0)
25 q=Wijlaik\
26 > II > 1 Ã‚Â§>
27
28 i=i + l
29 k=k + l
l
80
APPENDIX B
Escher Tile Examples
The following are examples of Escher tiles representing each of the period
types in IR2. These examples are meant to aid in understanding what
natural periods actually describe geometrically and chromatically.
81
B.l Trivially Periodic
Periodic Tile
Figure B.2: Trivially Periodic Wallpaper
82
B.2 Singly Periodic
Figure B.3: Singly
Periodic Tile
83
B.3 Doubly Periodic
Figure B.5: Doubly
Periodic Tile
Figure B. 6: Doubly Periodic Wallpaper
84
REFERENCES
[Co95] Henri Cohen, A Course in Computational Algebraic
Number Theory, 2nd ed., Springer-Verlag, New York,
1995.
[CoLeRiOl] Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, Clifford Stein, Introduction to Algorithms, 2nd ed.,
The MIT Press, Cambridge, Massachusetts, 2001.
[Da97] Dan Davis, On a Tiling Scheme From M. C. Escher, The
Electronic Journal of Combinatorics, v. 4, no. 2, (1997)
#R23.
[GeOl] Ellen Gethner, On a Generalization of a Combinatorial
Problem Posed by M. C. Escher, Congressus
Numerantium, Baton Rouge, LA, 2001.
[Ge02] Ellen Gethner, Computational Aspects of Escher Tilings,
PhD thesis, University of British Columbia, 2002.
[MaWaSc96]Rick Mabry, Stan Wagon, Doris Schattschneider,
Automating Escher's Combinatorial Patterns,
Mathematica in Education and Research, v. 5, no. 4,
(1996) 38-52.
[PaOl] Steve Passiouras, Escher Tiles,
http://www.eschertiles.com, 2001.
[RoOO] Kenneth H. Rosen, Elementary Number Theory, 4th ed.,
Addison Wesley Longman, Inc., Reading, Massachusetts,
2000.
[Sc04] Doris Schattschneider, M.C. Escher: Visions of Symmetry,
2nd ed., Harry N. Abrams, Inc., New York, 2004.
85
[Sc97]
[St03]
[WeOl]
Doris Schattschneider, Escher's Combinatorial Patterns, The
Electronic Journal of Combinatorics, v. 4, no. 2, (1997) #R17.
Gilbert Strang, Introduction to Linear Algebra, 3rd ed.,
Wellesley-Cambridge Press, Wellesley, Maryland, 2003.
Douglas B. West, Introduction to Graph Theory, 2nd ed.,
Prentice-Hall, Inc., Upper Saddle River, New Jersey, 2001.
86