Escherization
Craig S. Kaplan
David H. Salesin
Präsentation von Matthias Kaufmann
Fachseminar Aktuelle Themen der graphischen
Datenverarbeitung
Institut für wissenschaftliches Rechnen, ETH Zürich
6. Juni 2001
Motivation
 M. C. Escher
- holländischer
Grafiker
- 1898-1972
 inspiriert durch
orientalische
Verzierungen
 entwickelte seine
Bilder durch
„Ausprobieren“
Motivation
 Ziel:
Input
automatische
Erzeugung von
Pseudo-Escherbildern
 Algorithmus
 benötigt Vorlage
 EscherisierungsAlgorithmus
Output
Übersicht
 Tile
 Ähnlichkeit von Polygonen
 Optimierung
 Generierung
 Resultate
Tile - Definitionen
 Tiling
 Tilingeigenschaft eines
Polygons
 Tile: Grundbaustein
eines Tilings
 Vorlage normalerweise
kein Tile
 Hauptproblem: wie
Vorlage abändern, dass
sie nur leicht vom
Original abweicht und
Tilingeigenschaft erlangt
Escherisierungsproblem
Gegeben ein Polygon S,
finde zweites Polygon
T, so dass:
•
T und S sind
„möglichst ähnlich“
•
Kopien von T
passen zusammen
und füllen Ebene
Tile - Polygone
 Beschränkung auf
Polygone
 einfache
Manipulierbarkeit
 nur wesentliche
Ecken/Kanten
betrachten
Tile - Isoeder
 Beschränkung auf Klasse der Isoeder
 93 Isoedertypen
 Eigenschaften eines Isoeders:
– Tilingeigenschaft
– Verschiebungseinheit erzeugt Tiling nur durch
Translation
– alle Elemente einer Verschiebungseinheit haben
verschiedene Orientierungen und Farben
– Abbildung eines beliebigen Isoeders auf anderes
bildet gesamtes Tiling auf sich selber ab
– jede Ecke hat dieselbe Wertigkeit
Tile - Isoeder
Isoeder
Isoeder
Tile - Isoeder
 jeder Isoedertyp definiert,
– welche Bedingungen für die Tilingeigenschaft
eingehalten werden müssen
– wie einzelne Isoeder zu einem Tiling
zusammengefügt werden müssen
– Abhängigkeiten bei Kantendeformationen
– Anzahl Farben für Escherbild
 formale Beschreibung nötig
 Parametrisierung
 Inzidenzsymbol
Tile - Isoederparametrisierung
 Bedingungen für
Tilingeigenschaft
 Parametrisierung
notwendig für
Manipulation
 0 bis 6 Freiheitsgrade
 Parameter
Tile – Inzidenzsymbol

Konstruktion:
1. Bezeichnung / Richtung für
jede Kante
2. bei symmetrischen Kanten
Bezeichnung entsprechend
kopieren
3. Bezeichnungen im Gegenuhrzeigersinn aufschreiben
(+/-)
4. Symbole kopieren
5. für jede Bezeichnung die
Symbole der entsprechenden Nachbarskante
aufschreiben (mit umgekehrtem Vorzeichen)

nicht eindeutig
c
b
b
c
b
c
a
a
a
a
b
c
[a+ b+ c+ c- b- a- ; a- c+ b+]
Tile - Kantensymmetrien
 bis jetzt nur einfache
Isoeder mit geraden
Kanten
 weiterer Freiheitsgrad: Kanten
 Bedingungen
 aus Inzidenzsymbol
ableitbar
 4 Kantentypen:
S,U,I,J
[...a+...;...a+...]
Tile - Kantensymmetrien
[...a...; ...bx...]
[...a+...; ...a-...]
[...a...; ...a...]
[...a+/-...; ...b+/-...]
Ähnlichkeit von Polygonen
 vollständige Beschreibung von Isoedern mittels
Parametrisierung (inklusive Kanten)
 Metrik, um Polygone zu vergleichen:
–
–
–
–
Input: zwei Polygone
0 bei kongruenten Polygonen
je grösser Unähnlichkeit, desto grösser Wert
unabhängig von Rotation, Skalierung, Translation
 Idee:
– Repräsentation als Drehfunktion
– Normierung
Optimierung
 Ziel: in Parameterraum aller Isoeder dasjenige
mit grösstmöglicher Ähnlichkeit finden
 Tilingeigenschaft automatisch erfüllt
 Optimierungsproblem
 optimale Lösung schwierig zu finden
 Approximationsalgorithmus
 Simulated Annealing
Optimierung
 Input: Vorlagenpolygon
 Output: ähnliches Polygon mit
Tilingeigenschaft (Isoeder)
 Idee: Aufwand nur bei Isoedern mit Chance
 Algorithmus:
1. kreiere eine Instanz jedes Isoedertyps
2.
1. verbessere jede Instanz, so dass sie Vorlage ähnlicher wird
2. entferne sehr „schlechte“ Instanzen
3. iteriere 2., bis noch eine einzige Instanz übrig bleibt
Optimierung
 Verbesserung eines Tile:
for i := 1..n do
while „Temperatur noch zu hoch“ do
verbessere Tile mittels Parameter und Metrik
reduziere Temperatur
od
glätte, wo sinnvoll, Ecken
füge neue Ecken ein
reduziere Minimaltemperatur
od
Optimierung
Generierung
 Polygon mit Tilingeigenschaft
 Textur
 Markierungen zum Übertragen der
Originaltextur
 Automatisierung möglich
 eventuell manuelle Nachbearbeitung nötig
Generierung
 Füllen der Ebene
– Tile mittels Inzidenzsymbol und
Isoederinformation kopieren
– Verschiebungseinheit
 „bleichen“
 Farbtöne einbringen
 Maleffekte
Resultate
Resultate
Resultate
Resultate
 je komplizierter Form, desto
länger Optimierungsdauer
 schlecht approximierbare
Figuren
 Verbesserung:
Kantengewichte
 weniger comic-mässig als
Escherbilder
 manuelle Nachbearbeitung
kann Lösung verbessern
Zusammenfassung
 Input: Polygon der Vorlage
 die Parameter eines Isoeders so wählen,
dass Ähnlichkeit zum Vorlagenpolygon
maximal wird (Optimierung)
 Isoeder texturieren und Escherbild
generieren
Meinung
 Resultate überzeugend
 Aufwand riesig:
– Parametrisierung Isoeder
– Kantenparametrisierung
– Simulated Annealing
– Simplex
– Grafiktools für einfache Manipulation
 Verwendbarkeit?
 Grafiker, Verschnittminimierung
 andere Verfahren?
Literatur, Links
 http://www.cs.washington.edu/homes/csk/tile/
papers/kaplan_siggraph2000.pdf
 Grünbaum und Shephard: Tilings and
Patterns, W. H. Freeman, 1987
 Arkin et al., An efficiently computable metric
for comparing polygonal shapes, PAMI(13),
Nr. 3, März 1991, S. 209-216
 www.mcescher.com, www.worldofescher.com

Tilings and Patterns