
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00002056/00001
Material Information
 Title:
 Automating Escher tiling and coloring an implementation
 Creator:
 Ogden, Stephen C
 Place of Publication:
 Denver, Colo.
 Publisher:
 University of Colorado Denver
 Publication Date:
 2004
 Language:
 English
 Physical Description:
 xi, 86 leaves : illustrations ; 28 cm
Thesis/Dissertation Information
 Degree:
 Master's ( Master of Science)
 Degree Grantor:
 University of Colorado Denver
 Degree Divisions:
 Department of Computer Science and Engineering, CU Denver
 Degree Disciplines:
 Computer Science
 Committee Chair:
 Gethner, Ellen
 Committee Members:
 Alaghband, Gita
Choi, MinHyung Clark, John
Subjects
 Subjects / Keywords:
 Tiles  Computeraided design ( lcsh )
Decoration and ornament, Architectural ( lcsh )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 8586).
 Thesis:
 Computer science
 General Note:
 Department of Computer Science and Engineering
 Statement of Responsibility:
 by Stephen C. Ogden.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 60409677 ( OCLC )
ocm60409677
 Classification:
 LD1190.E52 2004m O43 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
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
MinHyung 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 MinHyung 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 IlKyun 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 CollisionFree 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
MinHyung 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 collisionfree 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 collisionfree 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
4tuple [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,01]
[6.7.1.0]
[8,9,1,0]
Table 2.1: Connections
This set of 4tuple 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 4tuples, an adjacency matrix could
have been used to record the same information. The set of 4tuples 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 4tuples 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 5tuples are used instead of 4tuples to account
for connections that involve the z coordinate. The 5tuple 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 ntuples (vectors) that are used to contain information about
the Escher tile were implemented as a set, or list, of ntuples.
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 depthfirst
search [WeOl]. The next steps following this one in the main algorithm
are performed for each connected component. Running a depthfirst
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 depthfirst 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 3tuples 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,22]
[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 depthfirst 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=Vv..
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 (eGE) II removed edge
E=E~(eij+eji)
This is a recursive procedure. If a selfconnection 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 4tuples instead of 3tuples. 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,91,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 (eEE) II removed edge
15 E=E(eij+eji)
16 Rh=Rh+eii
2.8 Identify Ghost Nodes
During the depthfirst 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 collisionfree 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 collisionfree 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 collisionfree
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 collisionfree vectors. If
we are dealing with a two dimensional tile, it turns out that we can choose
a collisionfree 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 collisionfree vectors. A
collisionfree 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
collisionfree. 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)
cTja^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 (1AT = 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=fqn
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 an13le, and
b=n23le, then, substituting into equation 2.2 then,
foz=f3e\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 nonzero
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 CollisionFree 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
collisionfree 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 collisionfree 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 collisionfree 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 collisionfree 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=vfi
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 collisionfree 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(lATl=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=vfi
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 collisionfree. 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, collisionfree 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 Kn12n23n13n22)
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 =
(n13n21nun23)
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)
(n12n31nun32)
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 n32n22 n31), (n12 /i31 /iu n32), {nn n22nl2 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 collisionfree 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 collisionfree 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 xaxis.
n3 is anywhere in 3space 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=cp
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=xmaxxmin, 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 =qe
(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' pjzcosfe)
cos(y)= ,=, 
1Jpl+P'l V(Pi2COs(0))2+(p2zsin(0))2
n11+n21p1zcos(0)
cos(y )= ,
yj{nn+n21p1zcos{e))2+{n22p2zsin(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 n331)
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
AT1 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(P2ki2)ni2(Pikil)
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 HKJI).
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 Al)
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 {Pxka)A {p2ka)D {p3ka)G
s' (Pi~ka)B (P2~ki2)E (P3ka)H
t' (Pi~ka)C (p2~ki2)F {Psk^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 HKJI).
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 Al)
2 for (6=0 to B 1)
3 for (c=0 to Cl)
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 clientserver 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 nonnegative 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., SpringerVerlag, 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) 3852.
[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.,
WellesleyCambridge Press, Wellesley, Maryland, 2003.
Douglas B. West, Introduction to Graph Theory, 2nd ed.,
PrenticeHall, Inc., Upper Saddle River, New Jersey, 2001.
86

Full Text 
PAGE 1
AUTOMATING ESCHER TILING AND COLORING: AN IMPLEMENTATION by Stephen C. Ogden B.S., University
PAGE 2
2004 by Stephen C. Ogden All rights reserved.
PAGE 3
This thesis for the Master of Science degree by Stephen C. Ogden has been approved by Ellen Gethner Gita Alaghband MinHyung Choi J 20 3 S? co y Date
PAGE 4
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 lV
PAGE 5
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. Ellen Gethner v
PAGE 6
DEDICATION This thesis is dedicated to every art and math lover who has come to appreciate the work ofM. C. Escher.
PAGE 7
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 MinHyung 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 IlKyun 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.
PAGE 8
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 Vlll
PAGE 9
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 CollisionFree 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 ......................................................................................... 7 4 3.1 Design Tool. ....................................................................................... 7 4 3.2 Future Considerations ...................................................................... 75 Appendix Appendix A. Algorithms ................................................................................ 76 Appendix B. Escher Tile Examples .............................................................. 81 References ....................................................................................................... 85 lX
PAGE 10
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 ofMotifPieces .................................................. 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.1: 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
PAGE 11
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 Xl
PAGE 12
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
PAGE 13
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
PAGE 14
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. 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
PAGE 15
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 MinHyung 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
PAGE 16
,. Escher Tile Des1gn Tool (20) X Figure 1.4: Escher Design Tool The main body of the discussion in this thesis will deal with tiling a 5
PAGE 17
wallpaper in R2 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 R3 This extension into 3 dimensions should be an aid in not only studying 3D Escher tiles, but also in defming just what a 3D Escher tile really is. 6
PAGE 18
, f;r.hPr Olnrl< rw .. lflll Tnol (10) X F igu r e 1.5: 3D E sc h e r D e s ign 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
PAGE 19
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. Figure 1.6: Highlighted Unit Tile / /::: 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. 8
PAGE 20
Figure 1. 7: Wallpaper Compon ent 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
PAGE 21
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 [Ma WaSc96]. 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
PAGE 22
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
PAGE 23
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 "collisionfree vectors" will become clearer as they are presented and defined in the sections that follow. 12
PAGE 24
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 collisionfree vectors 13 Compute Big Tile size 14 Locate color vectors 15 A 13
PAGE 25
2.2 Label Motif Pieces Figure 2.1 : Labeled Escher T ile 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
PAGE 26
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 m6 and m7, a vertical connection between motif pieces m3 and m2, and a diagonal connection between motif pieces m1 and ms. ( i a: horizontal connection b : vertical connection c: diagonal connection Figure 2.2: Horizontal, Vertical, and Diagonal Connections 15
PAGE 27
After all the connections have been discovered, the directions of the connections must be recorded. This associates each connection with a direction vector. In R2 the direction vector signifies connection in the x or y directions. For example, in Figure 2.2a, m5 has a horizontal connection to m7 with a direction vector of [1,0]. This means that, if we were able to stand on m5 and travel to m7, we would have to travel one unit in the x direction. Of course, to get back to m5 from m7, 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 m5 to motif piece m 7 in the direction of [1,0]. It is just as easy to use the complementary 4tuple [7,6,1,0] to describe the same connection. In Figure 2.2b, ms has a vertical connection to m 2 with a direction vector [1,0] resulting in [3,2,1,0] and its complement [2,3,1,0]. In Figure 2.2c, m1 has a diagonal connection toms 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
PAGE 28
[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,01] [6,7,1,0] [8,9,1,0] Table 2.1 : Connections This set of 4tuple 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 [mi,mi ,XS ], where m i 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
PAGE 29
[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
PAGE 30
Figure 2.4 : Agglomerated Period Graph 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 4tuples, an adjacency matrix could have been used to record the same information. The set of 4tuples 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 4tuples 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
PAGE 31
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 they 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 5tuples are used instead of 4tuples to account for connections that involve the z coordinate The 5tuple is described as [mi,m1,x,y,z]. 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, m1 overlaps m 3 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
PAGE 32
2.4.1 Implementation [1,3] [1,6] [2,3] [2,5] [2,6] [4,6] Table 2 2 : Overlaps 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 ntuples (vectors) that are used to contain information about the Escher tile were implemented as a set, or list, of ntuples. 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
PAGE 33
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 depthfirst search [WeOl]. The next steps following this one in the main algorithm are performed for each connected component. Running a depthfirst 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 ofmotifpieces on the wallpaper. Figure 2 5 : Spanning Tree 2.5.1 Implementation It will soon become apparent that the spanning tree is not an important 22
PAGE 34
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 depthfirst 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 m1. If there is more than one connected component, then each component will have its own origin piece other than m1. The generating set is a set of 3tuples that represent the motif piece and its relative position vector, [mi,XS ]. Another notation for this is [mi, aJ where mi is the motif piece and is its position vector [xs ]. 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
PAGE 35
positions of all motif pieces relative to the origin piece for a set of connected pieces. For example, m1 is automatically assigned position [0,0]. This is the origin piece [1,0,0]. Checking the period graph, we see that to get from m1 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
PAGE 36
Figure 2.6: Embedded Spanning Tree 2.6.1 Implementation Figure 2. 7 : Generating Set of Motif Pieces 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 m1. 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 depthfirst 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
PAGE 37
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 M k = the generating set of motif pieces for component k CreateGeneratingSet(P, Mk) 1 Add all vertices to V={1,2,3, ... n} 2 Copy period graph P E 3 k=1 4 C=Z 5 6 while (V *Z) 7 Mk=Z 8 Create Ck={Mk} 9 Get first available vertex in V and remove (V = V v0 ) 10 Create origin motif piece m0=[v0.0,0] 11 Mk=Mk+m0 12 Search ( v0 0, 0) II adds motif M k 13 C=C+Ck 14 k=k+1 The efficiency of this algorithm, not including the search, is proportional to the number of connected components in the tile, O(k). 26
PAGE 38
Algorithm: depth first search Inputs: E = the set of edges from the period graph V= the set of vertices from the period graph M k = the generating set of motif pieces for component k Search(i, xi, yJ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 for (each edge eij=[i,j,xi1,yij]) if(i=j) //selfconnection E=E(e .. +e .. ) IJ }! else if (v 1EV) II generating motif piece V=Vv. J E=E(eij+e1J x0=x.+x .. IJ Yo=yi+yij m=[j' Xo,Yo] Mk=Mk+m Search(}, x0 y0 ) else if ( e ij E E) I I removed edge E=E(e .. +e . ) IJ }! This is a recursive procedure. If a selfconnection 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 O(E), 27
PAGE 39
where E is the number of edges in the period graph. The performance may be enhanced by only checking edges where i on line 1. 2.6.2 3D Extension The generating motif pieces will be 4tuples instead of 3tuples. 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. 2. 7.1 Implementation [1,6,0,1] [1,8,1,1] [1,9,0,1] [2,9,1,1] Table 2.4: Removed Edges 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
PAGE 40
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 R k = the removed edges for component k Inputs: P = the period graph M k = the generating set of motif pieces for component k CreateGeneratingSet ( P M k ) 1 Add all vertices to V = { 1 2,3 ... n } 2 Copy period graph P E 3 k=1 4 C=JJ 5 6 while (V *XJ) 7 M k=XJ 8 Rk=XJ 9 Create Ck= {Mk, Rk } 10 Get first available vertex in V and remove (V=V v0 ) 11 Create origin motif piece m0=[v0. 0 0 ] 12 Mk=Mk+m0 13 Search( v0. 0 ,0) 14 C=C+C k 15 k=k+1 29
PAGE 41
Algorithm: depth first search Inputs: E = the set of edges from the period graph V = the set of vertices from the period graph M k = the generating set of motif pieces for component k Rk= the set of removed edges for component k Search(i, xi, yJ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2.8 for (each edge eij=[i,j,xij,yij]) if ( i = j) II selfconnection E=E(eij+e1J Rk=Rk +ei; else if (v 1EV) II generating motif piece V=Vv. J E=E(eij+e1J x0=xi+xij Yo=yi+yij m=[j' Xo Yo] Mk=Mk+m Search(}, x0, y0 ) else if (eijEE) II removed edge E=E(e .. +e .. ) IJ Jl Rk=Rk +eu Identify Ghost Nodes During the depthfirst 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
PAGE 42
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 m1, [0,0] to get [0,1]. Then we compare the sum to the position vector for m6 which is [1,2]. [0,1] is not equal to [1,2] so we get the ghost of m6 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. Figure 2.8: Ghost Node To define a natural period, recall the definition of a wallpaper component. 31
PAGE 43
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 m6 and the head on the very next m 6 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 R2 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 x n 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 collisionfree 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 collisionfree vectors. In the 32
PAGE 44
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 [ij ,x,y ], ( 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 fmd their difference That difference is a natural period so add it to the set of natural periods N. The efficiency is O (IIRkll). Algorithm: calculate natural periods Definitions: a i = the position vector of generating motif piece m i =[ i, li;] r iJ = [ i, j, hv] = a removed edge from the period graph Inputs: N k = the set of natural periods for component k R k = the set of removed edges for component k CalculateNatural( Nk, Rk) 1 N k=If 2 for (each removed edge riJERk) 3 i'"v=li;+hv II potential ghost 4 if s 6 N k=Nk+n 7 8 N k=HNF(Nk) 33
PAGE 45
2.8.2 3D Extension Item related to the 3D extension have been pretty simple up to this point concerning extending the algorithm into 1R3 The most complicated item has been to carry the hidden z coordinate along i n our calculations. But the procedure gets a little trickier here. In R2 we know that when we have a trivially or singly periodic tile, we must compute forbidden vectors and choose one or two colli s ionfree 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 collisionfree vectors. If we are dealing with a two dimensional tile, it turns out that we can choose a collisionfree vector that will fit for IR3 and allow the correct computations for R2 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 define s 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
PAGE 46
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. sum . .... ...... .... .. . . ... . 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
PAGE 47
.. : Figure 2.11: Lattice Pattern 2.10 C ompute 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 collisionfree vectors. A collisionfree 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 collisionfree. The method for finding forbidden vectors requires some analysis ofthe 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
PAGE 48
(2.1) 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 ii = 0 in equation 2.1. Figure 2.12: Overlap Graph Now we can calculate forbidden vectors. Each motif piece on the overlap graph is connected to an m1. The difference between the m1 motif pieces connected to some mi and mi is a forbidden vector. For example, the position of the m1 connected to m4 is a: and the m1 connected to m6 is The difference is Therefore, [1,1] is a forbidden vector. For m4 and m 9 the difference is so [0,1] is also forbidden. Note that m4 and m9 do not overlap each other. However, since m6 is equivalent to m9, 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
PAGE 49
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 m4 and m9. The overlap between m4 and m 6 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 6' 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 6, 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 6. 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(IIOII), where 0 is the set of overlaps. Normalization of the forbidden vector is a simple calculation that does not affect the efficiency. 38
PAGE 50
Algorithm: calculate forbidden vectors Definition: o v = 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=.RJ 2 if (IINII=O) m=O 3 if (IINII=l) m=n 4 5 for (each oiiEO) 6 fo=CijCi;. II possible forbidden 7 if (fo=O or fo*rm, rEZ) 8 f = NormalizeForbidden ( fo) II linear combo + 9 F=F+f 2.10.2 3D Extension The 3D extension is very simple. In R2 the tile may either have zero or one natural periods. In R3 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
PAGE 51
Algorithm: calculate forbidden vectors Definition: o iJ= 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=H 2 if (IINII=O) 3 if (IINII=1) m =m =0 1 2 m;=o 4 if (IINII=2) =n; iii;=li; 5 6 for (each oiJEO) 7 II possible forbidden 8 if (fo=O or r,sEZ) 1/linearcombo 9 f = NormalizeForbidden ( fo) 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 =[f 1 / 2 ] and a natural period n=[n1 n2 ] (there is only one), then we use greatest common divisor GCD) reduction to normalize {2 with respect to n2. If f2 =n2 =0, then we normalize {1 with respect to n1. In the trivially periodic case, normalization does not affect the forbidden vector. Assume we have a forbidden vector f =[f 1 / 2], and a natural period 40
PAGE 52
n =[ nl, n2]. All forbidden vectors equivalent to l are expressed as G={ f We want to find some foEG that minimizes fo2 Minimizing means finding the least residual {02={2mod(n2). Or, equivalently {2={02+qn12. Then we choose q=lf/n12J The normalized forbidden vector fo = fq 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 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 (IINII=O) 2 q=O 3 else !!IINII=1 4 if ({2+n2==0) 5 q=lf i2/n2 J 6 else 7 q=lfi/n1J 8 9 l=fqn 41
PAGE 53
2.11.2 3D Extension For R3 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 1 =[f 1 / 2 / 3], natural periods 1i';_ =[ n11, n12, n13], and ii';=[n21, n22 n23], all forbidden vectors equivalent to 1 are expressed as G={ 1 +s1i';_ +tii';:s, tEZ}. We want to find some foEG that minimizes {o3 subject to (2.2) Let e=gcd (n13, n23). Then, e=gn13+hn23 g, hEZ, where e, g, and hare the result of the extended Euclidean algorithm. Ifwe let a=n1afe, and b = n231 e, then, substituting into equation 2.2 then, f 03= f 3 e[s(n1af e )+t(n2af e)] = f 3e(sa+tb ). Next, we let q =lf / e J Note that ga+hb=l. (2.3) (2.4) Therefore, we can multiply both sides of equation 2.4 by q to get qga+qhb=q. Let s=qg, and t=qh, sothat q=sa+tb. Theresult is that we find fo3=f3qe ={3lfafej(e). (2.5) 42
PAGE 54
Equation 2.5 minimizes {o3 because Note that equations 2.5, and 2.6 are just the division algorithm (2.6) a=bq+r, with {3=a,e=b,lfafeJ=q, and {03=r. [RoOO]. Wecannow find values for s and t and calculate the minimized vector by using equation 2. 7. f01 f 1(snu+tn21) f o = fo2 = f 2(sn12+tn22) (2.7) f o3 f 3 ( sn1 3 +tn23) The procedure is much the same as in IR2 We find some nonzero 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
PAGE 55
Algorithm: normalize forbidden vectors Inputs: N = the set of natural periods f = a forbidden vector NormalizeForbidden (f) 1 if (IINII=O) 2 q=O 3 else 4 if (IINII=1) m;=o 5 if (IINII=2) ni;=ii; 7 if (m13+m23:#:0) 8 ( e, g h)= Extended.Euclid ( m13, m23 ) 9 q=lfi3/ej 10 s=qg 11 t=qh 12 if (m1 2+m2 2:#:0) 13 (e, g h)=Extended.Euclid(m12 m22 ) 1 if ({3 <0) 1=1 14 q=lfi2/ej 15 s=qg 16 t=qh 17 else 18 ( e, g, h)= Extended.Euclid ( m11, m21 ) 19 q=lfillej 20 s=qg 21 t=qh 22 23 44
PAGE 56
2.12 Choose CollisionFree 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 collisionfree 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 collisionfree 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. Figure 2.13: Lattice 45
PAGE 57
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,b]. 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 collisionfree 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, andy are reached. Therefore, the efficiency for this operation is @(Xmax Yma.J 46
PAGE 58
Algorithm: choose collisionfree vectors Inputs: N = the set of natural periods F = {T;, T;,. .. f nl = the set of forbidden vectors ChooseColllisionFree(N, F) 1 if (IINII=O) m=O 2 if (IINII=1) 3 4 OUTER_LOOP: 5 while (IINII<2) 6 for (a=O to maxa) 7 for (b=O to maxb) 8 v=[a,b] 9 for (i=1 to IIFII) 10 11 12 13 14 15 if (c:;t=sm, sEZ) II linear combo N=N+v if (m=O) m=v 1 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 @(Xmax Ymax ZmaxJ 47
PAGE 59
Algorithm: choose collisionfree vectors Inputs: N = the set of natural periods F={ f: f; ... ,fJ = the set offorbidden vectors ChooseCollisionFree ( N, F) 1 if (IINII=O) 2 if (IINII=l) iii;=O 3 if (IINII=O) 4 5 OUTER_LOOP: 6 while (IINII<2) 7 for (a=O to maxJ 8 for (b=O to maxb ) 9 for (c=O to max ) 10 V=[a,b,c] 11 for (i=1 to IIFII) 12 13 14 15 16 17 18 19 if s,tEZ) II linearcombo N=N+v if (ni;=O) iii=v 2 if .. m1=v continue OUTER_LOOP 2.13 Compute Big Tile Size We have arrived at this step with the necessary number of period vectors either natural or collisionfree. In IR2 that number is two. Before we can continue, we must first normalize the periods We perform the HNF 48
PAGE 60
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. N =([ 1, 3], [1,0])=[l (2.8) (2.9) .  Figur e 2.14 : Normali ze d 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, collisionfree vectors 49
PAGE 61
or both. The object is to find values that minimize the width and height. We will begin by finding the width. Given N ={ii;., n;}= n11 n21], let L\= determinant of N. Find a minimal n12 n22 x value that is a linear combination of periods xi=rii;.+sn; r,sEZ, i=[1,0]. (2.10) Then, equation 2.10 may be expressed as n21], therefore, nn 1 1 n22 Recall that the mverse of N 1s N = L\ n12 [r] = _!_ n22 s L\ n 12 (2.11) Solving for r and s in equation 2.12 gives us r=(n: )x, and (2.12) (n21 ) s= x. L\ (2.13) The smallest xEZ+ that satisfies equations 2.12 and 2.13 is L\ x= gcd (n12, n22) (2.14) Next, we will find the height. We use the same reasoning for they value as for the x value. Find a minimal y value that is a linear combination of the periods y]=rii;.+sn; r,sEZ, ]=[0,1]. (2.15) Then, equation 2.15 may be expressed as 50
PAGE 62
(2.16) Substituting the inverse, (2.17) Again, solving for r and s in equation 2.17 gives r=(:'1 k and (2.18) k (2.19) The smallest yEZ+ that satisfies equations 2.18 and 2.19 is f} y= gcd (n11, n2 1 ) (2.20) The width is the x value and the height is they 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= Ll x Ll gcd (n12 n22 ) gcd (n11 n21 ) (2.21) Using equation 2.21 in our example, we find that and BTS=lx3. We also know is the total number of colors necessary for coloring. The uncolored Big Tile is shown in Figure 2.15. 51
PAGE 63
2.13.1 Implementation Figure 2.15 : Uncolored Big Tile 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 IR3 The reasoning is almost exactly the same. The difference is that now we use 52
PAGE 64
the z coordinate to express the depth. Again, we start by finding the width. Given nu n21 n31 Find a N n;, li';}= n12 n22 n31 let .1 = determinant of N. n13 n23 n33 minimal x value that is a linear combination of periods r,s,tEZ, i=[I,O,O]. Then, equation 2.22 may be expressed as x nu n21 n31 0 = n12 n22 n31 0 n13 n23 n33 r x s N= 0 t 0 Let the transpose of the cofactor matrix of N, A D G NCT= B E G C F I r x s =N1 0 t 0 ( n22 n33n23 n32) ( n23 n31n21 n33) ( n21 n32n22 n31) = (n13n32n12n33) (nun33n13n31) (n12n3Inun32) (n12n23n13n22) (n13n2Inu n23) (nu n22n12n21) Therefore, r s t 1 A D G X B E H 0 .1 C F I 0 IxA xB .1 xC Solving for r, sand tin equation 2.26 gives us )x, 53 (2.22) (2.23) (2.24) (2.25) (2.26) (2.27)
PAGE 65
(C) ((n12n23n1an22)) tXX .1 .1 The smallest xEZ+ that satisfies equations 2.27, 2.28, and 2.29 is .1 X gcd(A,B,C) gcd ( ( n22 naan2a na2)' ( n1a na2n12 na a), ( n12 n2an1a n22)) (2.28) (2.29) (2.30) Next, we will find the height. Find a minimal y value that is a linear combination of the periods y]=rli';.+sii';+tn; r,s,tEZ, ]=[0,1,0]. Then, equation 2.31 may be expressed as 0 nu n21 na1 y = n12 n22 na1 ::::) 0 n1a n2a naa Substituting the inverse, r s t 1 A B .1 c D G 0 E H y F I 0 r s t 0 N= y 0 1 yD yE. .1 yF r ::::) s =N1 t Again, solving for r, sand tin equation 2.32 gives us )x, )x, and 54 (2.31) 0 Y 0 (2.32) (2.33) (2.34)
PAGE 66
t=( )x =( (nl, n, n,) )x. The smallest yEZ+ that satisfies equations 2.33, 2.34, and 2.35 is .1 y=l1 gcd(D, E ,F) gcd ( ( n2a na1n21 naa)' ( nu naan1a nal)' ( n1 a n21nu n23)) Next, we will find the depth. Find a minimal z value that is a linear combination of the periods r,s,tEZ, k=[0,0,1]. Then, equation 2.44 may be expressed as 0 nu n21 na1 0 = nl2 n22 na1 z n1a n2a naa Substituting the inverse, r 1 A D G s B E H .1 t c F I ::::) 0 0 z r 0 s N= 0 t z 1 zG .1 zH. zl r 0 => s =N1 0 t z Again, solving for r, sand tin equation 2.40 gives us )z=((n,l )z, )z, and t=U )z The smallest yEZ+ that satisfies equations 2.41, 2.42, and 2.43 is 55 (2.35) (2.36) (2.37) (2.38) (2.39) (2.40) (2.41) (2.42) (2.43)
PAGE 67
.1 z=l1 gcd(G,H, I) gcd ( ( nzl n3znzz n 31)' ( n1z n 31n u n3z), ( n u nzzn1z n zl)) The width is the x value, the height is y value, and the depth is the z value for the Big Tile Size. Big Tile Size BTS= width X height X depth BTS= .1 gcd(A,B,C) .1 .1 X X gcd(D,E,F) gcd(G,H, I ) .1 (2.44) X gcd ( (nzz n33nz3 n3z) (n13 n3z nlz n33)' (nlz nz3n13 nzz)) .1 gcd ( (nz3 n31nz1 n33)' ( nu n33n13 n31)' ( n13 nzlnu nz3)) X .1 (2.45) We use linear algebra and the Euclidean algorithm to implement equation 2.45 in the 3D extension. Notice that if we let n 1 3=n23=0 and n31 =n3 2=n33=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
PAGE 68
2.14.1 Implementation [0,0] [0,1] [0,2] Table 2. 6: Color Vectors At this point, we have found the natural periods and collisionfree 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 R2 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
PAGE 69
p Figure 2.16: Open Parallelogram c We start by defining the problem domain. The set of vectors is the set of natural periods and/or collisionfree vectors: vn v21 v31 V={U7D;Va} = vl2 v22 v32 (2.46) vl3 v23 v33 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)= 0 0 0 This gives us a set of vectors with the properties shown in Table 2.7 58 (2.47)
PAGE 70
n;_ coincides with the x axis. "ii; is anywhere in the XY plane except the x axis. 'iia is anywhere in 3space except the XY plane. Table 2. 7 : HNF Lattice Properties Note that we let 'iia=[O,O, 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 n;_ and "ii; c =Ti;_ +"ii; p = a point inside R and on n;_ and "ii; (not including points at the ends of n;_ and "ii;) q=c"P i =[ 1, 0, 0] (unit vector) ex= the angle between i and n;_ f3 = the angle between i and "ii; ex I= the angle between i and n;_ f3 I = the angle between i and "ii; ;y = the angle between i and p ;y I= the angle between i and q Table 2.8: Open Parallelogram Definitions Note that the and Ware equal. This is not necessarily the case with 'Y and "(1 Additionally, ex =ex I =0. Upon analyzing the aforementioned angles we can see that the relationships shown in Table 2.9 are true. 59
PAGE 71
a=a'=O (because ofHNF) {3' = {3 cos ((X) =cos ((X ') = 1 cos ( {3 ) =cos ( {3 ') 0 < {3 < TT 1
PAGE 72
X min :5; X :5; X max Y m i n :5; Y :5; Y max where X m in= min ( 0, n21) xmax =max ( n11, c1 ) Ymin =min (0, n 2 2 ) y max =max ( 0, n22) Table 2.10 : Iteration Ranges As we iterate over these x andy 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 d X= X maxX min' and d y = y max y min' then the efficiency of this operation is O(dx dy). Algorithm: locate color vectors Inputs: N = the set of period vectors LocateColors ( N) 1 for (x=xmin to xmax) 2 for (y=ymin to Ymax) 3 p=[x,y,O] 4 5 calculate cos ( y) 6 calculate cos (y ') 7 if (cos(/3) :s; cos(y) :s; 1 and cos(/3') < cos(y') < 1) 8 add p to the set of color vectors 61
PAGE 73
2.14.2 3D Extension J'n3 R' ................................ p F igure 2 .17: Ope n Paralle l e pipe d Up to now, we have not discussed the third vector, n3 For IR2 it is implied that n';= [ O O,l ] 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 n; onto the XY plane labeled n;' We need the definitions in Table 2 11. 62
PAGE 74
Tt; '= the projection of Tt; onto the XY plane e = the angle between i and 7t;' Table 2.11: Parallelepiped Definitions The three vectors inN describe an open parallelepiped where we must search for color vectors. We now know how to search for points when z=O. In R3 this is a matter of searching for the x andy 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 andy directions in relation to the original. The amount of shift is defined by the angle e and the value of z. 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. = [ z cos (e) z sin (e) p 3 ] (2.53) Note that if 7t;=[O,O,n33], then =[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 andy, 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 from them. This causes p' and q' to point to integer coordinates if does not have integer coordinates. This is the case if R' is between integer coordinates in either the x or y direction. q'=qp '=pWe also adjust the range for x andy by adding the corresponding coordinates to the minimum and maximum values of the ranges. lzcOS ( 8)j C 1 +ZCOS (8)j 63 (2.54) (2.55) (2.56)
PAGE 75
l z sin ( ()) J y l c 2 + z sin ( ()) J (2.57) Therefore, as the parallelogram shifts for each new value of z, we may have a new set of x andy points to test. This also keeps us from pointing too far away with our test points whenever R' is between x andy integer coordinates. We calculate the sine and cosine of the projection vector as shown in equations 2.58 and 2.59. n '31 cos(e) 2 2 n 31 +n 32 (2.58) (2.59) We evaluate the angles (a, {3, 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 ( p 1 z cos ( ()) )2 + ( p 2 z sin ( ()) )2 (2.60) (2.61) The efficiency of the operation is augmented by the magnitude to the projection of 'is Therefore, in R3 the efficiency is O(dx d y n3:J where dx and dy are as defined in section 2.14.1. 64
PAGE 76
Algorithm: locate color vectors Inputs: N = the set of period vectors LocateColors ( N) 1 for (z=O to n331) 2 = [ z sin (e) z cos (e) z] 3 X lower= l X min+ z sin ( 8) J 4 X upper= l X max+ Z sin ( 8) j 5 y lower= t y min+ z cos (e) J 6 y upper= l y max+ z cos (e) J 7 8 9 10 for (x=xlower to xupper) for ( Y = Y lower to Y uppeJ p=[x,y,z] p'=pq'=q11 12 13 14 15 16 calculate cos ( y) at P' calculate cos (y ') at Q' 2.15 if (cos(fi) cos(y) 1 and cos(fi') < cos(y') < 1) add p to the set of color vectors 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 N ii";}=[nu n21 color vectors K ... k,.} n12 n22 65
PAGE 77
and r, s E Z a Big Tile position of a motif piece is defined as It follows that [:]=N1 (2.62) Recall that the inverse of N is N 1=.l_[n22 n21 L\ n12 n n Therefore, (2.63) Let [ r :]=[n22(p 1kil)n21 (p2ki2) s nu (p2 ki2)n12(p1kil) (2.64) Then test O=r '(modL1N) and O=s '(mod L\N). (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
PAGE 78
BTloc Sum Linear combo [a,b] [mi,x,y] = p r' r' r' s' s' s' choose 1 2 3 1 2 3 6 7
PAGE 79
Figure 2.18: Color ed Big Til e 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 motifpiece, 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
PAGE 80
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. 2.15.1 Implementation 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
PAGE 81
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 O(A B I!Mkll IIKkll). Algorithm: assign colors Inputs: BTS=AxB .:::1 = the determinant of n (the set of periods) K k ={ k; k;, ... = the set of color vectors Mk={m1. m2 ... mnJ= a generating set of motif pieces (Recall mi=[i, x, y ]=[i, a";]) AssignColors(A, B, .:::1, M, K) 1 for (a=O to A1) 2 for (b=O to B1) 3 for (i=1 to IIMkll) 4 for (}=1 to IIKkll) 5 p=[a,b]a"; 6 calculate s and t 7 if (s' and t'=O(mod.1)) 8 assign to mi in position [a, b] 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 )). nu n21 n31 Given periods N ={n;, n;, ll;}= n12 n22 n33 n13 n23 n 33 colorvectors ... and r,s,tEZ, apositionofamotif 70
PAGE 82
piece is defined as +sn';+t n;. Therefore r plki l N1 s = p 2ki2 (2.66) t P aki3 Using the transpose of the cofactor matrix of N from equations 2.24, and 2.25 r 1 A D G p lkil s=.1 B E H p 2ki2 (2.67) t c F I P aki3 Let r (plkil) A (p2ki2)D ( p3ki3)G s' = (plkil)B (p2ki2)E (p3ki3)H (2.68) t (plkil)C (p2ki2)F (p3 ki3)I Then test O=r (mod.1 N ) O=s'(mod.1N ), and O=t'(mod.1N). (2.69) The algorithm is similar to the case in IR2 and highlighted below. In this case, the revised efficiency is O(A B C IIMkll IIKk ll). 71
PAGE 83
Algorithm: assign colors Inputs: BTS=AxBxC = the determinant of n (the set of periods) K k = { k;, k;, ... = the set of color vectors M k ={m1. m2 mJ= a generating set of motif pieces (Recall m .=[i, X, y, Z )=[i, aJ) AssignColors(A, B, C, M, K) 1 for (a=O to A1) 2 for (b=O to B1) 3 for (c=O to C1) 4 for (i=1 to IIMkll) 5 for (}=1 to IIKkll) 6 7 8 9 2.16 Color the Tile calculate r ', s' and t 1 if (r 1 s' and t '=O(mod .1)) assign k to m. in position [a, b, c ] 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 clientserver 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
PAGE 84
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 B1 X C1 and BTS2=A2 x B2 x C2 then the big Big Tile Size (2.70) Recall that lcm(a,b)=ab/gcd(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
PAGE 85
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 R3 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 fmish 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 ofM. C. Escher's tiles were formulated on a basic pattern within a 5 x 5 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
PAGE 86
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
PAGE 87
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.l Extended Euclidean Given a, b, c E 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 f, gEZ, then c =fa+ gb [RoOO]. The extended Euclidean algorithm computes c as well as providing the two factors f, and g [CoLeRiOl]. The algorithm depends on the fact that gcd (a, b)= gcd ( b, a mod b) [CoLeRiOl]. If b=O, then a is the GCD. Otherwise, find the remainder, r =a mod b, and recurse with b and r. As the algorithm ascends out of the recursions, the quotient q =l a/ b J is used to calculate valid factor values at each step as the algorithm ascends out of the recursion. When the method completes, f and g are valid factors for c =fa+ gb. The efficiency of this algorithm is proportional to O(log b) for a>b>O. 76
PAGE 88
Algorithm: extended Euclid Inputs: a,bEZ ExtendedEuclid (a, b) 1 if b=O 2 (c,f,g)=(a,1,0) 3 else 4 r=amodb 5 ( d, x, y) = ExtendedEuclid ( b, r) 6 q=lalb J 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=au, satisfies 1. a .. =O for i> j, IJ 2. aii>O for all i, and 3. .. i, IJ n or, as an mxn matrix with with the last m columns in HNF. 0 0 0 * 0 0 0 0 * A= 0 0 0 0 0 77
PAGE 89
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 nonnegative 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
PAGE 90
Algorithm: Hermite normal form (HNF) Definitions: A= an mXn matrix i, j, k, l, d EZ= matrix indices A i = 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=l 2 if 3 b=m 4 if (m>n) 5 b=n 79
PAGE 91
HermiteNormalForm (A) 1 while (k 1 7 if (aii#O and (min=O or min>iaiij)) 8 min =Ia ii i d = j 9 if (d:;e1) II foundai1
PAGE 92
APPENDIXB 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
PAGE 93
B.l Trivially Periodic Figure B.l: Trivially P eriodic Tile 82
PAGE 94
B.2 Singly Periodic Figure B. 3 : Singly P eriodic Tile 83
PAGE 95
B.3 Doubly Periodic Figure B.5: Doubly Periodic Tile 84
PAGE 96
REFERENCES [Co95] Henri Cohen, A Course in Computational Algebraic Number Theory, 2nd ed., SpringerVerlag, New York, 1995. [CoLeRi01] 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 FromM. C. Escher, The Electronic Journal ofCombinatorics, v. 4, no. 2, (1997) #R23. [Ge01] 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) 3852. [Pa01] [RoOO] [Sc04] Steve Passiouras, Escher Tiles, http://www.eschertiles.com, 2001. Kenneth H. Rosen, Elementary Number Theory, 4th ed., Addison Wesley Longman, Inc., Reading, Massachusetts, 2000. Doris Schattschneider, M.C. Escher: Visions of Symmetry, 2nd ed., Harry N. Abrams, Inc., New York, 2004. 85
PAGE 97
[Sc97] [St03] [WeOl] Doris Schattschneider, Escher's Combinatorial Patterns, The Electronic Journal ofCombinatorics, v. 4, no. 2, (1997) #R17. Gilbert Strang, Introduction to Linear Algebra, 3rd ed., WellesleyCambridge Press, Wellesley, Maryland, 2003. Douglas B. West, Introduction to Graph Theory, 2nd ed., PrenticeHall, Inc., Upper Saddle River, New Jersey, 2001. 86

