Subdivisionsalgorithmen –

Ein Oscar für die Mathematik

Ulrich Reif

Lange Nacht der Mathematik

Darmstadt, 9. Februar 2024
Geometrie

Punkte

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel
Dreiecke, n-Ecke

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel
Dreiecke, n-Ecke
Kreise

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel
Dreiecke, n-Ecke
Kreise
Zylinder, Quader

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel
Dreiecke, n-Ecke
Kreise
Zylinder, Quader
Pyramiden, Kegel

Ulrich Reif 09.02.24 2 / 34

Geometrie

Punkte
Geraden
Winkel
Dreiecke, n-Ecke
Kreise
Zylinder, Quader
Pyramiden, Kegel
Kugeln

Ulrich Reif 09.02.24 2 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

Thales von Milet

Pythagoras von Samos
Euklid von Alexandria
Archimedes von Syrakus

Ulrich Reif 09.02.24 2 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie

sin, arcsin
cos, arccos
tan, arctan

Ulrich Reif 09.02.24 3 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie
um 1600: Geometrie + Koordinaten → analytische Geometrie

~x + ~y , ~x − ~y
h~x , ~y i
~x × ~y (erst um 1880)

Ulrich Reif 09.02.24 3 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer Geometrie in

bis 1000: Trigonometrie der Schule
um 1600: Geometrie + Koordinaten → analytische Geometrie

~x + ~y , ~x − ~y
h~x , ~y i
~x × ~y (erst um 1880)

Ulrich Reif 09.02.24 3 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie
um 1600: Geometrie + Koordinaten → analytische Geometrie
seit 1700: Geometrie + Analysis → Differenzialgeometrie

Z b q
L= x 0 (t)2 + y 0 (t)2 dt
a

Ulrich Reif 09.02.24 4 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie
um 1600: Geometrie + Koordinaten → analytische Geometrie
seit 1700: Geometrie + Analysis → Differenzialgeometrie
seit 1850: Geometrie − Anschauung → Nichteuklidische Geometrie

Ulrich Reif 09.02.24 4 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie
um 1600: Geometrie + Koordinaten → analytische Geometrie
seit 1700: Geometrie + Analysis → Differenzialgeometrie
seit 1850: Geometrie − Anschauung → Nichteuklidische Geometrie
seit 1920: Geometrie + Algebra → Algebraische Geometrie

Ulrich Reif 09.02.24 4 / 34

Geometrie

bis -200: Hellenistische Geometrie und Vorläufer

bis 1000: Trigonometrie
um 1600: Geometrie + Koordinaten → analytische Geometrie
seit 1700: Geometrie + Analysis → Differenzialgeometrie
seit 1850: Geometrie − Anschauung → Nichteuklidische Geometrie
seit 1920: Geometrie + Algebra → Algebraische Geometrie
seit 1970: Geometrie + Computer → Digitale Geometrie

Ulrich Reif 09.02.24 4 / 34

Digitale Geometrie

Digitale Geometrie ist heute allgegenwärtig:

Computerspiele

Ulrich Reif 09.02.24 5 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 6 / 34

Digitale Geometrie

Digitale Geometrie ist heute allgegenwärtig:

Computerspiele
Animierte Filme

Ulrich Reif 09.02.24 7 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 8 / 34

Digitale Geometrie

Digitale Geometrie ist heute allgegenwärtig:

Computerspiele
Animierte Filme
Computerschriften

Ulrich Reif 09.02.24 9 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 10 / 34

 a
Digitale Geometrie

Ulrich Reif 09.02.24 10 / 34

Digitale Geometrie

Digitale Geometrie ist heute allgegenwärtig:

Computerspiele
Animierte Filme
Computerschriften
Simulation

Ulrich Reif 09.02.24 11 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 12 / 34

Digitale Geometrie

Digitale Geometrie ist heute allgegenwärtig:

Computerspiele
Animierte Filme
Computerschriften
Simulation
Computer-Aided Design

Ulrich Reif 09.02.24 13 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 14 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 14 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 14 / 34

Digitale Geometrie

Wie kommt die Geometrie in den Computer?

Ulrich Reif 09.02.24 15 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 15 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 15 / 34

Digitale Geometrie

Ulrich Reif 09.02.24 15 / 34

Die Geschichte beginnt . . .

. . . mit einem Hammer in Lausanne . . .

Ulrich Reif 09.02.24 16 / 34

Die Geschichte beginnt . . .

. . . mit einem Hammer in Lausanne . . .

. . . und endet mit einem Oscar in Hollywood.

Ulrich Reif 09.02.24 16 / 34

Der Trisektionsalgorithmus (1947)

Georges de Rham (1903 – 1990)

Ulrich Reif 09.02.24 17 / 34

Der Trisektionsalgorithmus (1947)

Ulrich Reif 09.02.24 18 / 34

Der Trisektionsalgorithmus (1947)

Ulrich Reif 09.02.24 18 / 34

Der Trisektionsalgorithmus (1947)

de Rham zeigt: Die Grenzkurve besitzt eine wohldefinierte Tangente und diese variiert
stetig im Kurvenverlauf.

Ulrich Reif 09.02.24 19 / 34

Der verallgemeinerte Trisektionsalgorithmus (1953)

de Rham betrachtet variable Teilverhältnisse 1:w:1 und erkennt die in gewisser Hinsicht
optimale Wahl

1 : 2 : 1

Ulrich Reif 09.02.24 20 / 34

Der verallgemeinerte Trisektionsalgorithmus (1953)

de Rham betrachtet variable Teilverhältnisse 1:w:1 und erkennt die in gewisser Hinsicht
optimale Wahl

1 : 2 : 1

Ulrich Reif 09.02.24 20 / 34

Der verallgemeinerte Trisektionsalgorithmus (1953)

. . . und dann geriet die Sache in Vergessenheit . . .

Ulrich Reif 09.02.24 21 / 34

Chaikins Algorithmus (1974)

Riesenfelds Aufgabe:
Erzeuge auf dem Computer möglichst effizient zu einem gegebenen Polygon eine
glatte Kurve ähnlicher Gestalt.

Ulrich Reif 09.02.24 22 / 34

Chaikins Algorithmus (1974)

Riesenfelds Aufgabe:
Erzeuge auf dem Computer möglichst effizient zu einem gegebenen Polygon eine
glatte Kurve ähnlicher Gestalt.

Chaikins Lösung:
Er glättet das Polygon durch corner cutting“.
”
Er findet, ohne von de Rham zu wissen, das günstige Teilverhältnis 1 : 2 : 1.
Nach drei bis vier Wiederholungen dieses Schrittes ist das Ergebnis visuell glatt.
Er erkennt, dass die Grenzkurve stückweise aus Parabelbögen besteht, die stetig
differenzierbar zusammengesetzt sind.
Er bezeichnet sein Verfahren als subdivision“.
”

Ulrich Reif 09.02.24 22 / 34

Chaikins Algorithmus (1974)

Effizienz: Zur Berechnung der Mitte M(P, Q) = (P + Q)/2 zwischen zwei Punkten
P und Q benötigt man nur eine Addition und einen Bitshift.
Die Unterteilungspunkte C und D zwischen A und B berechnet man wie folgt:

H = M(A, B) Hilfspunkt
C = M(A, H) = (3A + B)/4 linker Unterteilungspunkt
D = M(B, H) = (A + 3B)/4 rechter Unterteilungspunkt

Ulrich Reif 09.02.24 23 / 34

Vom Polygon zum Polynom

Wir betrachten das Polygon P mit den Ecken

P := p0 , p1 , p2 , . . .

Ulrich Reif 09.02.24 24 / 34

Vom Polygon zum Polynom

Wir betrachten das Polygon P mit den Ecken

P := p0 , p1 , p2 , . . .

Nun verwenden wir diese Ecken als Koeffizienten eines Polynoms,

X
p(x) := p0 + p1 x + p2 x 2 + · · · = pj x j
j

Ulrich Reif 09.02.24 24 / 34

Vom Polygon zum Polynom

Wir betrachten das Polygon P mit den Ecken

P := p0 , p1 , p2 , . . .

Nun verwenden wir diese Ecken als Koeffizienten eines Polynoms,

X
p(x) := p0 + p1 x + p2 x 2 + · · · = pj x j
j

Dadurch kann man Polynome und Polygone miteinander identifizieren,

P ←→ p(x).

Ulrich Reif 09.02.24 24 / 34

Vom Polygon zum Polynom

Ein Subdivisionsschritt

Palt −→ Pneu

hat, wie man zeigen kann, in der Welt der Polynome die Form

palt (x) −→ pneu (x) = s(x) · palt (x 2 ).

Dabei ist

s(x) = (1 + 3x + 3x 2 + 1x 3 )/4

das Symbol des Verfahrens.

Ulrich Reif 09.02.24 25 / 34

Vom Polygon zum Polynom

Die Koeffizienten des Symbols enthalten die Gewichte für die Berechnung der
Unterteilungspunkte:

s(x) = (1 + 3x + 3x 2 + 1x 3 )/4
C =( 3A + 1B )/4
D = (1A + 3B )/4

Man kann nun unterschiedliche Symbole s(x) verwenden, um neue Subdivisions-

algorithmen zu definieren

palt (x) → pneu (x) = s(x) · palt (x) ⇐⇒ Palt → Pneu .

Die Koeffizienten der geraden und ungeraden Monome in s(x) definieren die Regeln
für die neuen Punkte mit geradem und ungeradem Index.

Ulrich Reif 09.02.24 26 / 34

Vom Polygon zum Polynom

Die geometrischen Eigenschaften der erzeugten Kurven hängen mit algebraischen

Eigenschaften des Symbols s zusammen.
Eine notwendige Bedingung für k-malige stetige Differenzierbarkeit ist beispiels-
weise, dass s an der Stelle x = −1 eine (k + 2)-fache Nullstelle hat.
Hinreichende Bedingungen sind auch bekannt, aber u.U. gut in den Polynomen

s(x), s(x) · s(x 2 ), s(x) · s(x 2 ) · s(x 4 ), s(x) · s(x 2 ) · s(x 4 ) · s(x 8 ), . . .

versteckt.
Es gibt heute eine Fülle von Subdivisionsalgorithmen für verschiedene Zwecke.
Die analytischen Eigenschaften sind weitestgehend verstanden.

Ulrich Reif 09.02.24 27 / 34

Von Kurven zu Flächen

Chaikin für Kurven:

große Segmente −→ kleine Segmente −→ Nachbarn verbinden

Ulrich Reif 09.02.24 28 / 34

Von Kurven zu Flächen

Chaikin für Kurven:

große Segmente −→ kleine Segmente −→ Nachbarn verbinden

Chaikin für Flächen:

große Vierecke −→ kleine Vierecke −→ Nachbarn verbinden

Ulrich Reif 09.02.24 28 / 34

Der Eulersche Polyedersatz (1752)
Für jedes geschlossene Polyeder in R3 gilt

#Ecken + #Fl ächen − #Kanten = 2 − 2g ,

wobei das Geschlecht g die Anzahl der Löcher“ angibt .

”

g =0 g =1

Ulrich Reif 09.02.24 29 / 34

Der Eulersche Polyedersatz (1752)
Für jedes geschlossene Polyeder in R3 gilt

#Ecken + #Fl ächen − #Kanten = 2 − 2g ,

wobei das Geschlecht g die Anzahl der Löcher“ angibt .

”

g =0 g =1 g =3

Für eine schachbrettartige Struktur gilt stets g = 1.

Ulrich Reif 09.02.24 29 / 34
Jenseits des Schachbretts

Ulrich Reif 09.02.24 30 / 34

Jenseits des Schachbretts

Ulrich Reif 09.02.24 30 / 34

Der Doo-Sabin Algorithmus (1979)

Chaikin:
großes 4-Eck −→ kleines 4-Eck −→ verbinden

Ulrich Reif 09.02.24 31 / 34

Der Doo-Sabin Algorithmus (1979)

Chaikin:
großes 4-Eck −→ kleines 4-Eck −→ verbinden

Ulrich Reif 09.02.24 31 / 34

Der Doo-Sabin Algorithmus (1979)

Chaikin:
großes 4-Eck −→ kleines 4-Eck −→ verbinden

Doo-Sabin:
großes n-Eck −→ kleines n-Eck −→ verbinden
Ulrich Reif 09.02.24 31 / 34
Der Doo-Sabin Algorithmus (1979)

Ulrich Reif 09.02.24 32 / 34

Der Doo-Sabin Algorithmus (1979)

Subdivisionsalgorithmen für Flächen

sind einfach zu implementieren und hocheffizient

sind schwierig zu analysieren

Ulrich Reif 09.02.24 33 / 34

Der Doo-Sabin Algorithmus (1979)

Subdivisionsalgorithmen für Flächen

sind einfach zu implementieren und hocheffizient

sind schwierig zu analysieren

erzeugen stetig differenzierbare Flächen

sind Standard in der Computergrafik

Ulrich Reif 09.02.24 33 / 34

Der Doo-Sabin Algorithmus (1979)

Subdivisionsalgorithmen für Flächen

sind einfach zu implementieren und hocheffizient

sind schwierig zu analysieren

erzeugen stetig differenzierbare Flächen

sind Standard in der Computergrafik

erzeugen (derzeit) keine zweimal stetig differenzierbaren Flächen

sind (derzeit) nicht gut genug für das Design von Autokarosserien

Ulrich Reif 09.02.24 33 / 34

Der Durchbruch . . .

gelingt im Jahr 1998 mit der oscar-reifen Darbietung eines älteren Herrn namens Geri“.
”

Ulrich Reif 09.02.24 34 / 34

Der Durchbruch . . .

gelingt im Jahr 1998 mit der oscar-reifen Darbietung eines älteren Herrn namens Geri“.
”

Ulrich Reif 09.02.24 34 / 34