Bernstein-Polynome fur die Computer-Typographie

C. Reinsch

0. Werbung

Die Welt ist heutzutage voller Mathematik — aber nicht alle konnen das erkennen. EinBeispiel dafur ist die Typographie, also die Gestaltung einer Schrift mit ihren Anspruchenan Lesbarkeit und Schonheit. Im Zeitalter des Bleisatzes (noch garnicht so lange her) warenes hochgradig spezialisierte Kunstler, die sich um den Entwurf eines Schriftsatzes (Font)kummerten und diesen modellierten wie eine Vase, Gotterfigur oder Autokarosserie. In un-serer Zeit mit Textverarbeitung am PC und dem ”Desktop Publishing” ist der Jahrhun-derte alte Bleisatz abgelost worden durch die digitalen Fonts, welche vom Betriebssystemeines Rechners fur die Auswahl in einem Anwendungsprogramm bereitgehalten werden. DieAnspruche sind dabei gestiegen, insbesondere verlangt man heute die stufenlose Skalierbarkeitaller Schriftzeichen nach Breite und Hohe und die Orientierung in allen Schreibrichtungen.

Merkwurdig, dass auch Leute, die personlich ”Desktop Publishing” taglich und routinemaßigeinsetzen, in der Regel vollig ahnungslos sind uber das, was dabei ablauft, und in ihrerIgnoranz verkennen, wieviel praktische Mathematik in der Computer-Typographie steckt.”Ist doch alles absolut trivial” habe ich schon bei Ruckfragen als Meinung scheinbar sonstintelligenter Leute zu horen bekommen. Ja, wenn die Maschine nicht rattert und stinkt, dannnimmt man sie eben nicht wahr, und denkt an Heinzelmannchen oder wohl eher an garnichts.

Im Jahr der Mathematik sind alle Fachleute aufgerufen, dieser Ignoranz entgegen zu tretenund Aufmerksamkeit auf die Leistungen und die eminente Nutzlichkeit der Mathematik zulenken. Naturlich muss man dazu selber Bescheid wissen, und daran hapert es ein wenig,denn auch in Kursen uber Computer-Grafik und Computer-Aided-Design (CAD) wird ausZeitmangel meist nur wenig uber Computer-Typographie gesprochen. Im folgenden findetsich eine Zusammenstellung des mathematischen Hintergrundes und der Hilfsmittel, die mandabei einsetzt. Auch wer es im Augenblick nicht grundlich studieren will (oder kann), mochtevielleicht diese Formelsammlung ausdrucken und seinen Unterlagen uber Computer-Grafikbeifugen, um bei Bedarf darauf zuruckgreifen zu konnen.

1

1. Die geeignete Polynom-Basis

Definition 1 Bernstein-Basis fur IPn, n = 0, 1, 2, . . .

Bk,n(t) :=

(

nk

)

tk (1 − t)n−k, k = 0, . . . , n.

Hierbei ist t0 = 1 und (1 − t)0 = 1 fur alle t. Dazu also die Vereinbarung 00 := 1.

n = 1 n = 2 n = 3

0 1 0 1 0 10 0 0

1 1 1

Abb. 1 Die Bernstein-Basis für Grad 1, 2, 3

Die Umkehrung von {1, t, . . . , tn} 7→ {B0,n(t), . . . , Bn,n(t)} ist

Lemma 1(

ni

)

ti =n∑

k=i

(

ki

)

Bk,n(t), i = 0, . . . , n.

Beweis: Rechts Einsetzen der Definition von Bk,n(t) und Binomialsatz fur (t + 1−t)n−i,

1 =n∑

k=i

(

n − ik − i

)

tk−i (1 − t)n−k.

Korollar Auf [0, 1] sind B0,n(t), . . . , Bn,n(t) linear unabhangig:n∑

k=0

fk Bk,n(t) = 0 auf [0, 1] =⇒ f0 = · · · = fn = 0.

Wir werden die Bernstein-Basis anstelle der ublichen Taylor-Basis {1, t, t2, . . . , tn} undFreiform-Kurven anstelle der verbreiteten Polynom-Interpolation (Newtonsche Formel, divi-dierte Differenzen usw.) verwenden. Das ist der entscheidende Wechsel, der vom anfanglichenMisserfolg zum heutigen Erfolg gefuhrt hat.

2

Elementare Eigenschaften der Basis-Polynome

(1) Bk,n(t) ist positiv fur 0 < t < 1 .

(2) Bk,n hat eine k-fache Nullstelle bei t = 0 und eine (n−k)-fache Nullstelle bei t = 1.

(3)n∑

k=0

Bk,n(t) = 1,

(4)n∑

k=0

k

nBk,n(t) = t,

(5)n∑

k=0

k2

n2Bk,n(t) = t2 + (t − t2)/n,

(6) Bk,n hat sein Maximum im Intervall [0, 1] bei t = k/n.

(7) Rekursion:Bk,n(t) = t Bk−1,n−1(t) + (1 − t) Bk,n−1(t),

(8) Ableitung:dBk,n

dt= n (Bk−1,n−1 − Bk,n−1).

Beweis:

(1) und (2) sind klar.

(3), (4), (5) folgen aus Lemma 1 fur i = 0, 1, 2. Bei (4) und (5) ist der Fall n = 0auszuschließen, nur um eine etwas augenfalligere Formulierung mit n im Nenner zu erlauben.

Bei (6) sind die drei Falle k=0, 0<k<n, k=n zu unterscheiden.

(7) und (8) sind unmittelbar nachzuprufen, dabei gilt die Vereinbarung B−1,n−1 =Bn,n−1=0.

3

2. Bernstein-Operator und Folge der Bernstein-Polynome

Definition 2 Bernstein-Polynome (Serge Bernstein, 1912)

Zu jeder stetigen Funktion f : [0, 1] → IR definiert man die Folge reeller Polynome

Bnf :=n∑

k=0

Bk,n f(k/n), Grad n = 0, 1, 2, . . .

Bn : C[0, 1] → IPn wird als Bernstein-Operator bezeichnet. Er ist linear.

(Die Bk,n(t) selbst sind also nicht die Bernstein-Polynome sondern die Bernstein-Basis.)

Wegen (1),(3) laßt sich der Wert des Polynoms Bnf(t) fur jedes t ∈ [0, 1] ansehen als eineMittelung der Funktionswerte f(k/n), k = 0, . . . , n mit von t abhangigen GewichtenBk,n(t) ≥ 0. Mit dieser Schreibweise kann (3),(4) in die Form gebracht werden Bng = g furalle Geraden g(t) = At + B und n = 1, 2, . . .

Bernstein hat mit Hilfe von (3),(4),(5) gezeigt, dass die Folge der Bnf fur n → ∞ auf demIntervall [0, 1] gleichmaßig gegen f konvergiert, und hat damit einen besonders eleganten Be-weis des Weierstraßschen Approximationssatz geliefert. Im CAD-Bereich ist man an solchenFragen nicht interessiert und begnugt sich mit einem festen n. Dann braucht man naturlichanstelle von f ∈ C[0, 1] nur einen diskreten Vektor f von n+1 Funktionswerten f0, . . . , fn.Bei festem n verstehen wir im Folgenden Bnf immer in diesem Sinn. Zum Beispiel steht B3ffur das kubische Polynom (1 − t)3f0 + 3 t (1 − t)2f1 + 3 t2 (1 − t)f2 + t3f3.

Vorteilhafte Eigenschaften der Bernstein-Polynome

(9) Bnf (0) = f0 und Bnf (1) = fn.

(10) (Bnf)′ = n Bn−1∆f = Bn−1(∆f/∆t),

m-fache Wiederholung:

(10)m (Bnf)(m) = n (n − 1) · · · (n − m + 1) Bn−m∆mf .

Hier ist ∆f := (f1 − f0, . . . , fn − fn−1) und ∆t = 1/n. ∆f/∆t sind die dividierten

Differenzen der Funktionswerte, wenn diese aquidistant im Intervall [0, 1] positioniert werden(stuckweise Ableitung des interpolierenden Polygons).

Kombiniert mit (9):

(Bnf)(m) (0) = n (n − 1) · · · (n − m + 1) ∆m(f0, . . . , fm),

(11)(Bnf)

(m) (1) = n (n − 1) · · · (n − m + 1) ∆m(fn − m, . . . , fn),

mit der m-ten Differenz von f0, . . . , fm und von fn−m, . . . , fn. Fur m < n/2 kann man alsoleicht ein Polynom vom Grad ≤ n erzeugen mit vorgeschriebenen Werten fur f, f ′, . . . , f (m)

an den beiden Endpunkten t = 0 und t = 1. Das macht es leicht, Polynomstucke an einanderzu hangen mit stetigen Ableitungen bis zur Ordnung m an den Nahtstellen (”Knoten”).

4

Weiter gilt:

(12)

t = 0 ist eine m-fache Nullstelle genau dann wenn f0 = . . . = fm−1 = 0 und fm 6= 0.t = 1 ist eine m-fache Nullstelle genau dann wenn fn = . . . = fn−m+1 = 0 und fn−m 6= 0.

Die oben besprochene Interpretation von Bnf als gewichtete Mittelung der Funktionswertef0, . . . , fn zeigt zusammen mit (10) die Form-Erhaltung des Operators Bn:

(13) f > 0 =⇒ Bnf > 0 auf [0, 1],

(14) ∆f > 0 =⇒ (Bnf)′ > 0 auf [0, 1],

(15) ∆2f > 0 =⇒ (Bnf)′′ > 0 auf [0, 1],

usw.

(13), (14), (15) gelten genauso auch mit <, ≥, ≤ anstelle von >. Zum Beispiel

a ≤ f ≤ b =⇒ a ≤ Bnf(t) ≤ b ∀ t ∈ [0, 1],

c ≤ ∆f/∆t ≤ d =⇒ c ≤ (Bnf)′(t) ≤ d ∀ t ∈ [0, 1].

Wegen Bng = g fur alle Geraden g kann man (13) auch auf f − g anwenden und so zeigen,dass das Polynom Bnf fur 0 ≤ t ≤ 1 innerhalb der konvexen Hulle der n + 1 Punkte(k/n, fk), k = 0, . . . , n liegt (straffes Lasso um alle Polygon-Ecken).

Eine weitere Eigenschaft ist die Variations-Verminderung: Das Bernstein-Polynom hatnie mehr Oszillationen als das Polygon mit den Ecken (k/n, fk), k = 0, . . . , n. Und auch dasgilt aus dem gleichen Grunde fur eine beliebige Gerade g(t) = At+B anstelle der t-Achse alsReferenz. Die Aussage wirft zusatzliches Licht auf den Unterschied zwischen Kontrollpunktenund Stutzpunkten bei der Interpolation und hat mehr theoretische Bedeutung. Fur n ≤ 3(wie in der Computer-Typographie) bringt die Aussage allerdings kaum Neues. Der Beweisist ein wenig anspruchsvoller als das Bisherige und deshalb in den Anhang 1 verlegt.

5

3. Kurven in der Ebene und im Raum

Im CAD-Bereich wird vor allem der Spezialfall n = 3 verwendet und zwar dort unter demNamen Bezier-Polynom und Bezier-Kurve. Letzteres, wenn man eine Parameter-Darstellungfur x-, y- und eventuell auch z-Komponente hat:

X = Bnx ⇐⇒ X(t) = B0,n(t) x0 + . . . + Bn,n(t) xn,

Y = Bny ⇐⇒ Y (t) = B0,n(t) y0 + . . . + Bn,n(t) yn,

Z = Bnz ⇐⇒ Z(t) = B0,n(t) z0 + . . . + Bn,n(t) zn.

Die Punkte (xk, yk) bzw. (xk, yk, zk), k = 0, . . . , n heißen Kontrollpunkte und das mitihnen gebildete Polygon heißt Kontrollpolygon. Die Bezeichnung Bezier -Kurve wird ver-wendet, weil Bezier auf die hervorragende Eignung dieser Formeln fur graphische Zweckeaufmerksam gemacht hat, insbesondere fur sogenannte Freiform-Kurven bei der Gestaltungvon Auto-Karosserien, im Bootsbau und dergleichen.

Wichtig:Die Bezier-Kurven, ihre Kontrollpunkte und das Kontrollpolygon liegen also in der x-y-Ebenebzw. im x-y-z-Raum und sind sichtbar fur den Anwender. Die unabhangige Variable t bleibtdagegen fur ihn unsichtbar bzw. verborgen.

Bei Kurven in der x-y-Ebene bzw. im x-y-z-Raum gelten (13) - (15) und ihr Beweis nichtnur fur jede Komponente, sondern wegen der Linearitat des Operators Bn auch fur jede be-liebige Kombination der Komponenten, also auch in jeder beliebigen Richtung. Auch diesesind ja Mittelwerte mit Gewichten Bk,n(t) ≥ 0. Wenn zum Beispiel alle Kontrollpunkteauf einer Seite einer beliebigen x-y-Geraden bzw. x-y-z-Ebene liegen, dann tut es auchdie zugehorige Bernstein-Kurve. Diese wird also wieder von der konvexen Hulle der Kon-trollpunkte eingeschlossen. Bei Bernstein-Polynomen ist deshalb eine Randuberwachung ingraphischen Anwendungen uberflussig, solange alle Kontrollpunkte innerhalb des zugelasse-nen Gebietes liegen und dieses konvex ist.

Die Anderung des k-ten Kontrollpunktes um δf andert Bnf um Bn,k(t) δf an jeder Stellet ∈ [0, 1]. Bei Bezier-Kurven in der Ebene oder im Raum ist Bn,k(t) ein skalarer Faktorzwischen 0 und 1 und δf ein Vektor. Das Verschieben eines Kontrollpunktes verschiebt alsoalle Punkte der Kurve in die gleiche Richtung, aber in schwacherem Maße. Diese Vorher-sehbarkeit macht Bezier-Kurven zu einem folgsamen und gefugigen Hilfsmittel beim Ent-werfen. Bei der Polynom-Interpolation von Stutzstellen ist das bekanntlich ganz anders undmacht dort Schwierigkeiten.

Die Kurvenstucke sind strikt kovariant, das heißt, jegliche Verschiebung, Drehung oderSpiegelung der Kontrollpunkte in der x-y-Ebene ubertragt sich in exakt gleicher Weise aufdas Kurvenstuck. Dessen Gestalt bleibt dabei also vollig unverandert. Skalierungen mitbeliebigen Faktoren in x- oder y-Richtung machen die Kurvenstucke genauso mit. EinSchrift-Gestalter merkt deshalb nichts von dem unterliegenden Koordinatensystem und derSkalierung seiner Achsen: allein die sichtbare Lage der Kontrollpunkte (von ihm gesetzt) be-stimmt den sichtbaren Umriss der Schriftzeichen. Auch aus diesem Grund sind die Freiform-Kurven mit Bernstein-Polynomen unter heutigen Schriftgestaltern sehr beliebt.

6

4. Der Algorithmus von de Casteljau

Vor Pierre Bezier (1970) hatte schon Paul de Casteljau (1959) Bernstein-Polynome furPolynom-Kurven in x und y verwendet. Er benutzte die Rekursion (7), um Bnf an einerbeliebigen Stelle λ zu berechnen. Dazu sei pj,m :=

∑mk=0 Bk,m(λ) fj+k.

Der Algorithmus von de Casteljau

Start: pj,0 := fj, (j = 0, . . . , n);

fur m = 1, . . . , n : pj,m := (1 − λ) pj,m−1 + λ pj+1,m−1, (j = 0, . . . , n − m);

Schluss: (Bnf)(λ) := p0,n.

Fur λ ∈ [0, 1] ist das eine wiederholte Mittelbildung mit festen, nicht-negativen Gewichtenund deshalb besonders robust gegenuber Rundungsfehlern. x-, y-, z-Komponente kann manin diesem Schema parallel berechnen. Dieses Rechenschema ist so einfach, dass man es auchgeometrisch mit einem Lineal ausfuhren kann:

p p p pp p p

p pp

00 10 20 30

01 11 21

02 12

03

f

f

f

f

0

1

2

3

Abb. 2 Das Schema von de Casteljau in der x-y-Ebene fur n = 3 und λ = 5/8

7

Sei gm := p0,m und hm := pm,n−m fur m = 0, . . . , n.

Im dreieckigen Schema von de Casteljau sind das die Elemente in der vorderen bzw. hinterenSchragzeile (grun und blau in Abb. 3). Setzt man fur diese gm = p0,m und hm = pm,n−m

die obigen Definitionen ein, dann erhalt man (endliche) Doppelsummen fur (Bng)(t) und(Bnh)(t). Nach Vertauschen der Summationsfolge, ergibt sich die Aussage

P (λt) = (Bng)(t), P (λ + (1 − λ)t) = (Bnh)(t), 0 ≤ t ≤ 1.

Ein etwas eleganterer Beweis zeigt zunachst durch Schluss von m − 1 auf m fur die m-tenDifferenzen, dass

∆m(g0, . . . , gm) = λm∆m(f0, . . . , fm), ∆m(hn−m, . . . , hn) = (1 − λ)m∆m(fn−m, . . . , fn)

fur m = 0, . . . , n. Dies kombiniert man mit (11) zur Aussage

(DmBng)(0) = λm(DmBnf)(0), (DmBnh)(1) = (1 − λ)m(DmBnf)(1).

Dm steht hier fur die m-te Ableitung nach t. Daraus folgt die Behauptung.

Der Algorithmus von de Casteljau berechnet also nicht nur den Wert des Bernstein-Polynomsan einer beliebigen Stelle λ, sondern liefert gleichzeitig die Zerlegung des Einheits-Intervalls[0, 1] in [0, λ] und [λ, 1] mit anschließender Skalierung beider Teile auf Einheitslange. DasResultat des Algorithmus von de Casteljau ist also nicht nur der unterste Eintrag im drei-eckigen Schema, sondern alle Eintrage in der vorderen und hinteren Schragzeile.

Von diesem Resultat wird spater Gebrauch gemacht bei der Zerlegung von B3f in seinezwei Anteile fur [0, 1/2] und [1/2, 1]. Dabei ist dann f = (a, b, c, d). Als Ubung und zurVorbereitung kann man das Schema fur λ = 1/2 aufstellen und obige Aussagen verifizieren.

de Casteljau−Algorithmus

· · · ·

· · ·

· ·

·

Eingabe

Ausgabe

P(t)

0 1λ

Abb. 3 Die erweiterte Ausgabe des Algorithmus von de Casteljau:Kontrollpunkte fur den linken und rechten Zweig des Polynoms

8

Ubrigens:

In der Computer-Grafik spielen Bernstein-Polynome auch in zwei unabhangigen Variableneine große Rolle, die dann auf dem Einheits-Dreieck in der Ebene definiert werden. Das sindSummen uber i, j, k mit i + j + k = n:

∑

i,j,k

n!

i! j! k!ui vj wk.

u, v, w sind Dreiecks-Koordinaten (baryzentrische Koordinaten), wobei immer u+ v +w = 1.1,0,0 und 0,1,0 und 0,0,1 sind die drei Ecken im Einheitsdreieck. Durch

x = A1u + B1v + C1w, y = A2u + B2v + C2w

kann man das Einheitsdreieck auf ein beliebiges Dreieck mit den Ecken A,B,C abbilden. DerAlgorithmus von de Casteljau ist dann ein Tetraeder-formiges Schema und seine wesentlichenEigenschaften bleiben gultig. Spielt aber keine Rolle fur die ubliche Computer-Typographie.Wichtig wird das erst, wenn man es mit drei-dimensionalen Schriftzeichen in einem Volumen-Modell zu tun hat (Plakatschrift).

9

5. Bernstein-Kurven vom Grad 1 bis 3 fur Computer-Fonts

Lineare, quadratische und kubische Bernstein-Kurven werden bei Computer-Fonts benutzt,um die Umrisse (engl. ”outline”) der einzelnen Schriftzeichen (engl. ”glyph”) in der Zeichen-ebene festzulegen. Also fur jeweils 0 ≤ t ≤ 1:

Lineares Kurvenstuck (Gerade):

X = B1x ⇐⇒ X(t) = (1 − t) x0 + t x1,

Y = B1y ⇐⇒ Y (t) = (1 − t) y0 + t y1.

Quadratisches Kurvenstuck (Parabelbogen):

X = B2x ⇐⇒ X(t) = (1 − t)2 x0 + 2 t (1 − t) x1 + t2 x2,

Y = B2y ⇐⇒ Y (t) = (1 − t)2 y0 + 2 t (1 − t) y1 + t2 y2.

Kubisches Kurvenstuck:

X = B3x ⇐⇒ X(t) = (1 − t)3 x0 + 3 t (1 − t)2 x1 + 3 t2 (1 − t) x2 + t3 x3,

Y = B3y ⇐⇒ Y (t) = (1 − t)3 y0 + 3 t (1 − t)2 y1 + 3 t2 (1 − t) y2 + t3 y3.

Ein quadratisches Kurvenstuck ist immer ein Parabelbogen mit beliebig orientierter Achse,moglicherweise degeneriert zu einer Geraden oder zu einem Punkt in Abhangigkeit vom Rangder 2 ×2 Matrix aus Start- und End-Tangente. Es gibt deshalb keinen Wendepunkt.

Bei einem kubischen Kurvenstuck wahlt man muhelos

• Startpunkt: x0, y0, • Endpunkt: x3, y3,• Startrichtung: x1 − x0, y1 − y0, • Endrichtung: x3 − x2, y3 − y2.

Die Lange der beiden Richtungsvektoren bestimmt, wie schnell sich entlang des Kurvenstuckesdie Startrichtung in die Endrichtung wendet. Je langer einer der Vektoren, desto langer bleibtdie Kurve in seiner Richtung. Bei Lange → 0 kommt man zur Geraden (Sekante). BeimVerbinden zweier Kurvenstucke kann man den Knickwinkel dazwischen wahlen, insbeson-dere ist der Ubergang glatt (ohne Knick), wenn man die beiden letzten Kontrollpunkte desvorderen Kurvenstuckes und die beiden ersten Kontrollpunkte des hinteren Kurvenstuckesauf einer Geraden wahlt (”kollinear”). Ein kubisches Kurvenstuck kann bis zu zwei Wen-depunkte haben, weil XY −Y X vom zweiten Grad ist, und es kann bis zu zwei Umkehrpunktehaben, weil X2 + Y 2 ≥ 0 vom Grad 4 ist und nur doppelte Nullstellen haben kann.

Wenn man Kurvenstucke an einander hangt (konkateniert), dann gehort selbstverstandlichzu dem entstandenen Kurvenzug auch ein Gesamt-Kontrollpolygon.

1985 fuhrte die Firma Adobe (auszusprechen ”a-dou-bi”) PostScript (Level 1) ein, welchesdie Definition von Pfaden erlaubt. Ein Pfad (engl. ”path”) besteht bei PostScript auseinem Startpunkt und einer beliebigen Anzahl von an einander gehangten linearen oder kubi-schen Kurvenstucken wie in der obigen Ubersicht aufgefuhrt. Dabei ist der Endpunkt einesKurvenstucks zugleich der Startpunkt des nachsten Kurvenstucks, sodass die Nahtstellen(”Knoten”) immer nur einmal in der Liste angegeben werden. Dieser Liste entspricht einKontrollpolygon mit Kontrollpunkten, namlich ausser dem Startpunkt jeweils einem fur ein

10

lineares Kurvenstuck und jeweils dreien fur ein kubisches Kurvenstuck. Ein oder mehreresolche Pfade bilden zusammen in PostScript Type 1 den Umriss eines Schriftzeichens. ZumBeispiel benotigt der Buchstabe O vier Pfade. Eine Konvention ist, Aussen-Umrisse im

Uhrzeigersinn und Innen-Umrisse gegen den Uhrzeigersinn zu durchlaufen: also links vomPfad ”hell” und rechts ”dunkel”. Dafur zwei Beispiele in Abb. 4 und 5.

Kontrollpunkte:

x = (0, h,1,1, 1,h,0, -h,-1,-1, -1,-h,0)

y = (1, 1,h,0, -h,-1,-1, -1,-h, 0, h,1,1)

Abb. 4 Vier 90°-Bögen als Kreis-Approximation

Der so erhaltene ”Kreis” ist nicht exakt, sondern nur eine sehr gute Approximation:mit der Wahl h = 4

3(√

2 − 1) liegt√

X(t)2 + Y (t)2 zwischen 1 und 1.0003 (Anhang 2).

Lineares Segment:

Kubisches Segment:

Glatter Übergang:

Abb. 5 Umriss eines Type1-Buchstabens

11

Die Firma Apple folgte Adobe Anfang 1991 mit ihren Computer-Fonts TrueType. Hier wer-den keine kubischen sondern quadratische Kurvenstucke aus obiger Liste verwendet mit einerBesonderheit: Bei n Parabelbogen hinter einander mit den Kontrollpunkten P2k−2, P2k−1, P2k,k = 1, . . . , n werden auf Wunsch die Knoten P2k nicht spezifiziert, sondern intern berechnetaus P2k = (P2k−1 + P2k+1)/2, k = 1, . . . , n − 1. Dadurch hat man glatte Ubergange (stetigeerste Ableitung) an den Knoten, d.h. quadratische Splinefunktionen X(t), Y (t). DerAnwender spezifiziert also nur P0, P2n und alle ungeraden Kontrollpunkte dazwischen. (Werwill, kann diese wieder luckenfrei durchnummerieren.) P0 und P2n sind on-curve und P1 bisP2n−1 sind off-curve. Letztere liegen nicht auf der Kurve. Mit P0 und P2n spezifiziert manStart- und Endpunkt. Mit P1 −P0 und P2n −P2n−1 spezifiziert man Start- und Endrichtung.Ein solcher Teilpfad hat also 2 on-curve Kontrollpunkte und dazwischen n ≥ 1 off-curveKontrollpunkte.

Bei n = 2 hat das Parabelpaar dieselbe Funktionalitat und Handhabung wie ein kubischesKurvenstuck, denn in beiden Fallen hat man dafur ein Kontrollpolygon mit vier Eckena, b, c, d. Den Unterschied von Parabelpaaren gegenuber kubischen Kurvenstucken sieht manam besten bei X(t) und Y (t). BeiType 1 sind das Polygonzuge (stuckweise linear) und beiTrueType Treppenfunktionen (stuckweise konstant). Bei quadratischen Splines gibt es wieschon erwahnt Wendepunkte ausschließlich an den Knoten x2k, y2k, denn entlang einesParabelbogens ist X Y − Y X konstant und die Krummung hat dort einheitliches Vorzeichen.Das ist keine große Einschrankung, weil man auch bei den kubischen Umrissen von Type 1 inder Regel Kontrollpunkte an den vorgesehenen Wendepunkten setzt. Im Gegenteil, nur beiden quadratischen Umrissen von TrueType kann man sicher sein, dass es zwischen den Knotenkeine unbeabsichtigten Wendepunkte gibt. Sprunge von X, Y an den Knoten haben im allge-meinen beide, doch nur die kubischen Kurvenstucke haben das Potential, solche Sprunge zuvermeiden und kubische Splinefunktionen zu bilden. Das Aussehen eines Parabelpaars unter-scheidet sich von dem eines kubischen Kurvenstucks so geringfugig, dass eine automatischeErsetzung in fast allen Fallen zu vollig befriedigenden Ergebnissen fuhrt, weil die Unterschiedekaum sichtbar sind.

Dabei wird man die beiden on-curve-Kontrollpunkte a und d unverandert lassen und nurdie beiden off-curve-Kontrollpunkte b und c zweckmassig verschieben: Wenn man ein kubi-sches Kurvenstuck ersetzt durch ein quadratisches Kurvenpaar, dann ist die Differenzfunktion(Fehler, Abweichung) stuckweise kubisch im Intervall 0 ≤ t ≤ 1/2 und 1/2 ≤ t ≤ 1. Da-her kann man bis zu drei Nullstellen wahlen in jeder der beiden Intervall-Halften. ZweiMoglichkeiten dazu bieten sich an: (I) Nullstellen bei t = 0, 0, 1/2, 1, 1 und (II) Nullstellenbei t = 0, 1/4, 1/2, 3/4, 1 . An diesen Stellen im Intervall [0, 1] interpoliert also das Parabel-paar das kubische Kurvenstuck. Fur die Durchfuhrung empfiehlt es sich, das t-Intervall [0, 1]zu zerlegen in [0, 1/2], [1/2, 1] und in beiden Teilen t wieder von 0 bis 1 laufen zu lassen, wieausfuhrlich diskutiert im Abschnitt zum Algorithmus von de Casteljau. Dann ist es leicht, diekubische Fehlerfunktion explizit anzugegeben und sie so einzurichten, dass ihre Nullstellenim Fall (I) links bei 0, 0, 1 , rechts bei 0, 1, 1 liegen oder im Fall (II) links und rechts bei0, 1/2, 1. So ergibt sich:

Die Naherung (I) verschiebt die Kontrollpunkte b, c zu b′ = (a + 3b)/4, c′ = (3c + d)/4.Nicht nur Start- und Endpunkt sondern auch Start- und Endrichtung bleiben erhalten undder maximale Fehler ist dann |f |/54 mit f := a−3b+3c−d. Zum Beispiel wird in der Kreis-approximation von Abb. 4 mit der dort empfohlenen Wahl h = 3

4(√

2−1) das Kontrollpolygonbei dieser Verschiebung zu einem regelmaßigen Achteck mit der idealen 8-zahligen Symmetrie.

12

Die Naherung (II) fuhrt zu verschobenen Kontrollpunkten b′′ = b′ + f/32, c′′ = c′ − f/32.Dies erhalt nur den Start- und Endpunkt. Start- und Endrichtung sind dagegen leichtverandert. Dafur wird der maximale Fehler um mehr als den Faktor 3 reduziert auf |f |/96

√3.

Diese Naherung laßt sich auch leicht iterieren wie im Anhang 3 ausgefuhrt.

Oft wird gesagt, dass Apple’s TrueType mehr Kontrollpunkte benotige als Adobe’s Type 1.Das ist sicherlich richtig, wenn es um die Approximation einer gegebenen zweimal stetigdifferenzierbaren Kurve geht, wie bei der Kreis-Approximation (Abb. 4). n Kurvenstuckegeben bei Type 1 einen Fehler O(1/n6) gegenuber nur O(1/n4) bei TrueType. (Details dazuim Anhang 2). Dem steht ein gewisses Einspar-Potential gegenuber bei konsekutiven Kurven-stucken: n konsekutive kubische Segmente in Type 1 haben 3n+1 Kontrollpunkten, wahrendeine Splinekurve mit 2n Parabelbogen in TrueType nur 2n+2 Kontrollpunkte hat, weil n−1”on-curve” Knoten vom System eingefullt werden. Im Beispiel von Abb. 5 mit zweimal je 4konsekutiven kubischen Segmenten kann man also bis zu 6 Kontrollpunkte einsparen.

13

6. Rasterisierung und Schraffuren

Der Umriss eines Schriftzeichens (Glyph) wird also spezifiziert durch einen Satz von Kurven-stucken {Xi(t), Yi(t) : t ∈ [0, 1]} vom Grad 1, 2 oder 3, die zusammen einen oder mehreregeschlossene Pfade bilden. Um diesen Umriss mit Farbe auszufullen, braucht man beiden heute ublichen, Raster-orientierten Ausgabe-Geraten die Schnittpunkte einer gegebe-nen horizontalen Geraden y = const mit allen Kurvenstucken Xi(t), Yi(t) : t ∈ [0, 1]. Jedergeschlossene Pfad hat eine gerade Anzahl solcher Schnittpunkte. Alle zusammen werdenaufsteigend sortiert und dann paarweise mit einander verbunden. Diese Aufgabe nennt manRasterisierung. Bei Schraffuren sind die Schnittgeraden im allgemeinen nicht horizontal son-dern im Winkel α geneigt. Dann werden zunachst alle Kontrollpunkte um den Winkel −αgedreht und die so berechneten Schnittpunkte anschließend zuruckgedreht.

Abb. 6 Zur Rasterisierung Abb. 7 Schraffur

Auf zwei Punkte kommt es dabei an. Erstens soll es schnell gehen. Man darf also nicht mehroder wenig umstandlich die quadratischen oder kubischen Gleichungen Yi(t) = h auflosenund ihre Wurzeln wegwerfen, wenn sie komplex sind oder nicht in [0, 1] liegen. Vor allemmuss man diesen trivialen Fall moglichst schnell erkennen und erledigen.

Zum zweiten ist Konsistenz unabdingbar. Das heißt, dass die Anzahl der berechnetenLosungen von Yi(t) − h = 0 im Intervall [0, 1] gerade oder ungerade sein muss, je nachdem Vorzeichen von Yi(0) − h und Yi(1) − h. Sind beide Werte ≥ 0 oder < 0, dann mussdie Zahl der Losungen auch unter dem Einfluss von Rundungsfehlern immer gerade sein. Istdagegen einer der Werte ≥ 0 und der andere < 0, dann muss die Zahl der Losungen unbedingtungerade sein. Diese Forderung muss auch erfullt sein, wenn die Losung bei 0 oder 1 liegt,und daher beim Kurvenstuck i und i + 1 auftritt und auch dann mit der richtigen Paritatgefunden werden muss, zum Beispiel 1-mal aber nicht 0- oder 2-mal. Im Gegensatz dazu sind

14

Rundungsfehler bei der Berechnung des zugehorigen Xi(t) unproblematisch und belanglos.

Die anzuwendende Technik kann studiert werden am einfachsten Fall, Grad = 1, alsoXi(t) = (1 − t)xi + t xi+1 und Yi(t) = (1 − t) yi + t yi+1 fur i = 0, . . . , n − 1,wobei x0 = xn und y0 = yn bei einem geschlossenen Pfad. Man setzt

b := yn − h;fur i = 1, . . . , n:

a := b; b := yi − h;falls a ≥ 0 und b < 0 : x := (xi − xi−1) a/(a − b) + xi−1;falls a < 0 und b ≥ 0 : x := (xi − xi−1) b/(b − a) + xi;

Quotient a/(a − b) bzw. b/(b − a) ist immer zwischen 0 und 1, niemals Division durch null !Damit erhalt man im Fall von yi = . . . = yj = h• genau eine Nullstelle bei xi, wenn yi−1 < h und yj+1 > h,• genau eine Nullstelle bei xj, wenn yi−1 > h und yj+1 < h,• keine Nullstelle, wenn yi−1 und yj+1 beide > h,• je eine Nullstelle bei xi und xj, wenn yi−1 und yj+1 beide < h.

Quadratische Kurvenstucke lassen sich in der Bernstein-Form genauso robust und geschlossenbehandeln wie diskutiert im Anhang 4. Bei kubischen Kurvenstucken berechnet man zunachstdie Nullstellen von dy/dt und die Werte von y(t) dort. Dann hat man bis zu drei Teil-Intervallen, in denen y(t) streng monoton ist, dort also hochstens eine Nullstelle haben kann,die man gegebenenfalls iterativ berechnet. Die Rasterisierung ist also bei den hochstensquadratischen Kurvenstucken von Apple’s TrueType weniger aufwandig und kompliziert alsbei Adobe’s Type 1 Fonts. Dort ist es sehr attraktiv, ein kubisches Kurvenstuck mit demAlgorithmus von de Casteljau und einem ”stack” so lange zu bisektionieren bis die Teilstuckein Zeichengenauigkeit quadratisch sind. (Details dazu im Anhang 3).

15

Anhang 1: Variations-Verminderung

Bernstein-Polynome werden auf Grund ihrer guten Eigenschaften immer im Intervall [0, 1]eingesetzt. Wie steht es dort mit den Nullstellen? (12) hat gezeigt, was fur die beidenRandpunkte gilt. Fur das Innere gilt folgende Abschatzung, wobei man den trivialen Fallf = 0 zunachst ausschließt.

Satz 1

f 6= 0 habe ν Vorzeichenwechsel.Dann hat das Bernstein-Polynom Bnf hochstens ν Nullstellen im offenen Intervall ]0, 1[.

Dabei gilt:

Definition 3 Vorzeichenwechsel bei Folgen

Aus f := (f0, f1, . . . , fn) streiche man alle Nullen und zahle dann die Ubergange von +nach − und von − nach + . Das ergibt die Zahl von Vorzeichenwechsel der Folge f .

f ≥ 0 oder f ≤ 0 und insbesondere f = 0 haben somit keinen Vorzeichenwechsel.

Beweis von Satz 1

Fur f 6= 0 ist auch Bnf 6= 0 und hat nur diskrete Nullstellen. Das offene Intervall 0 < t < 1wird mittels x := t/(1 − t) auf das Intervall 0 < x < ∞ abgebildet und dort das PolynomBnf/(1 − t)n =

∑nk=0 Fk xk angesehen, wobei Fk := fk n!/(k!(n − k)!). Es wird gezeigt,

dass∑n

k=0 Fk xk hochstens ν positive Nullstellen hat. Das ist ein Spezialfall von

Satz 2

Sei α1 < · · · < αm und alle γ1, . . . , γm 6= 0 .Die Anzahl µ der positiven Nullstellen von f(x) := γ1 xα1 + . . . + γm xαm istnicht großer als die Anzahl ν von Vorzeichenwechseln in der Folge γ1, . . . , γm.

Beweis

Der Fall m = 1 ist klar. Der Fall m = 2 ist leicht: betrachte die beiden Falle γ1 γ2 < 0 undγ1 γ2 > 0. Fur m > 2 Schluss von m − 1 auf m mittels eines Widerspruchsbeweises. Dazudie Annahme:

f(x) habe mindestens ν + 1 positive Nullstellen: 0 < ζ1 ≤ . . . ≤ ζν+1 ≤ . . .

Die Funktion g(x) = d/dx (f(x)/xα1) hat die gleiche Form wie f(x), jedoch ohne den Termmit γ1. Dieses g(x) hat nach dem Satz von Rolle mindestens ν Nullstellen in ζ1 ≤ x < ∞.

Falls γ1 γ2 < 0:

γ2, . . . , γm hatte ν − 1 Vorzeichenwechsel und g(x) mindestens ν Nullstellen. Widerspruch

16

zur Induktions-Voraussetzung.

Falls γ1 γ2 > 0 (und o.B.d.A. γ1 und γ2 > 0):

γ2, . . . , γm hatte ν Vorzeichenwechsel und g(x) mindestens ν + 1 Nullstellen, namlich ν Null-stellen in [ζ1, ∞] und noch mindestens eine in ] 0, ζ1 [ , denn f(x)/xα1 = γ1 + γ2 xα2−α1 + · · ·steigt rechts von 0 zunachst an bevor es zu seiner ersten Nullstelle ζ1 abfallt. Es hat alsodazwischen ein Maximum und dort ist seine Ableitung g(x) null. (Sinngemaß fur negativeγ1, γ2.) Auch hier also ein Widerspruch zur Induktions-Voraussetzung.

Etwas lax kann man sagen, dass das Bernstein-Polynom Bnf nie mehr Nullstellen in ]0, 1[hat als sein Kontrollpolygon, wobei die Nullstellen bei letzterem nicht diskret sein mussenund deshalb durch den Begriff der Vorzeichenwechsel prazisiert wurden.

Diese Aussage von Satz 1 fur die t-Achse laßt sich sofort verallgemeinern bezuglich einerbeliebigen Geraden g(t) = At + B, weil man diese von den Funktionswerten f und derFunktion Bnf abziehen kann. Eine beliebige Gerade schneidet also im Streifen 0 < t < 1das Polynom Bnf nie ofters als sein Kontrollpolygon.

Definition 4 Nulldurchgang bei Funktionen

Die stetige Funktion F : [a, b] → IR hat an der Stelle t einen Nulldurchgang,wenn F (t − ǫ)F (t + ǫ) < 0 fur ǫ → 0.

Ein Nulldurchgang ist also eine isolierte Nullstelle mit ungerader Multiplizitat im Innerendes Intervalls [a, b]. Die Anzahl der Nulldurchgange in [a, b] ist nie großer als die Anzahl vonNullstellen im offenen Intervall ] a, b [. Die Funktion F (t) ≡ 0 hat keinen Nulldurchgang.Damit bringen wir Satz 1 in seine endgultige Form:

Satz 3 Variations-Verminderung

f habe ν Vorzeichenwechsel.Dann hat das Bernstein-Polynom Bnf hochstens ν Nulldurchgange in [0, 1].

Die Einschrankung f 6= 0 von Satz 1 ist jetzt aufgehoben.

Bei Bernstein-Kurven Bnx, Bny, Bnz gilt Satz 3 auch fur die z-Komponente der Kurve, dasKontrollpolygon mit den Kontrollpunkten xk, yk, zk im Raum und eine beliebige Schnittebenez = const, weil der Verlauf von Bnx,Bny fur die Nulldurchgange in z-Richtung keine Rollespielt. Gleiches gilt fur die x- und die y-Richtung. Dann gilt es aber auch fur jede beliebigeRichtung und die dazu senkrechten Ebenen αx + βy + γz = λ im Raum:

Die Zahl der Nulldurchgange von α Bnx + β Bny + γ Bnz− λ ist nie großer als die Zahl vonVorzeichenwechsel in der Folge α x + β y + γ z − λ.

Man kann also im x-y-z-Raum eine beliebige Ebene als Referenz wahlen. Und in der x-y-Ebene kann man eine beliebige Gerade als Referenz wahlen. Immer hat das Kontroll-Polygonmindestens so viele Wechsel von Daruber und Darunter wie die Kurve.

17

Anhang 2: Kreisbogen-Approximation

Der Kreisbogen um den Ursprung mit Radius 1 reiche von −α bis +α, c := cos α, s := sin α.Start- und Endpunkt sind also (c,−s) und (c, s). Bei einem regularen n-Eck ist α = π/n.Welche Konvergenz-Ordnung ist erreichbar bei α → 0 bzw. n → ∞?

a) Mit quadratischem Kurvensegment

Es gibt nur ein quadratisches Kurvensegment tangential am Start- und Endpunkt, seine dreiKontrollpunkte (x, y) sind (c,−s), (1/c, 0), (c, s).Bei −1 ≤ t ≤ +1 ist die Bernstein-Basis (1 − t)2/4, (1 − t2)/2, (1 + t)2/4, sodass

x(t) = c + (1/c − c) (1 − t2)/2, y(t) = s t,

x(t)2 + y(t)2 − 1 = (1/c − c)2 (1 − t2)2/4 ∈ [0, s4/(4c2)].

Das regulare n-Eck hat also n Ausbuchtungen O(n−4) des Einheitskreises.Beispiele: 1 ≤ r(t) < 1.0607 fur n = 4 und 1 ≤ r(t) < 1.0032 fur n = 8.

b) Mit kubischem Kurvensegment

Hier ist λ ein positiver, frei wahlbarer Parameter und die vier Kontrollpunkte sind (c,−s),(c,−s) + λ(s, c), (c, s) + λ(s,−c), (c, s). Bei −1 ≤ t ≤ +1 ist die kubische Bernstein-Basis(1− 3t + 3t2 − t3)/8, (1− t− t2 + t3) 3/8, (1 + t− t2 − t3) 3/8, (1 + 3t + 3t2 + t3)/8 sodass

x(t) = c +3

4λ s (1 − t2), y(t) =

(

s + (s

2− 3

4λ c) (1 − t2)

)

t.

Eine kurze Rechnung gibt

x(t)2 + y(t)2 − 1 = (1 − t2)2 (a2t2 + b2 − 1), a :=s

2− 3

4λc, b := c +

3

4λs.

Die Wahl von λ wird dadurch zur Wahl von b und umgekehrt. (b ist x(0).)Sinnvoll bei b2 ist offensichtlich der Bereich von 1 bis 1 − a2.

b = 1 =⇒ 34λ = s/(1 + c), 2a = s3/(1 + c)2 = O(n−3) und

x(t)2 + y(t)2 − 1 = a2 (t − t3)2 ∈ [0, 4a2/27].

Zum Maximum bei t = ±1/√

3 gehoren die Winkel ± arctan ((s/√

3) 2/(1 + c)).Beim regularen n-Eck hat man also 2n nicht genau aquidistante Ausbuchtungen O(n−6) desEinheitskreises. Beispiel n = 4: 1 ≤ r(t) < 1.0003 mit Maximum bei ±260.

a2 + b2 = 1 =⇒ λ = 2s/(√

3 + c2 + c), 2a = s3/(1 + c√

3 + c2 + c2) und

x(t)2 + y(t)2 − 1 = − a2 (1 − t2)3 ∈ [−a2, 0].

Das Minimum ist beim Winkel 0. Diese Approximation des regularen n-Ecks hat also naquidistante Einbuchtungen, jetzt zwar 6.75mal großer aber immer noch O(n−6).

18

Diskussion

In den beiden Fallen a) und b) der Kreisbogen-Approximation ist die Konvergenz-Ordnungbesser als es bei Funktionen ublich ist. Wieso?

Bei der Approximation von Funktionen ist man gewohnt, dass quadratische Polynome dieKonvergenz-Ordnung O(h3) haben und kubische Polynome die Konvergenz-Ordnung O(h4),wie es das Restglied-Theorem von Peano verlangt. Zum Beispiel gibt die Interpolation einesregelmassigen n-Ecks (c+ i s)2k−1, k = 0, . . . , n mit periodischen kubischen SplinefunktionenX(t) + i Y (t) den Fehler (c − 1)2(2 − c)/(2 + 4c2), also O(n−4) wie zu erwarten. HohereKonvergenz-Ordnung als im Regelfall ist moglich, wenn aus Zufall oder wegen einer Symme-trie der Approximant vom Grade n ubereinstimmt mit dem Approximant vom Grad n+1 odernoch hoher, denn dann muss er dessen (hohere) Konvergenz-Ordnung erben. Zum Beispielgibt die quadratische Interpolation von f(t) = t4 an den Stutzstellen t = −h, 0, +h dasPolynom P (t) = h2t2 mit Fehler f(t) − P (t) = t2(t2 − h2) = O(h4), weil dieses gleichzeitigauch der Interpolant zu den Stutzstellen t = −h, 0, 0, +h ist.

Bei der Approximation glatter Kurven sind die Verhaltnisse etwas anders. Weil es dann aufdie Parametrisierung nicht ankommt, genugen die Interpolation von x, y und der Tangenten-Richtung, also drei Angaben, um im Fehler dort eine doppelte Nullstelle zu erzeugen. Mit den3+3 Koeffizienten zu quadratischem X(t), Y (t) kann man das genau an zwei Stellen machen(hier −1 und +1 genannt) und zwei doppelte Nullstellen geben Konvergenz-Ordnung 4. Daserklart Abschnitt a). Bei kubischen Kurven gibt es 4+4 Koeffizienten und das reicht nichtaus, um je 3 Vorgaben an 3 Stellen zu erfullen. Dass es im Abschnitt b) doch gelingt undman deshalb Konvergenz-Ordnung O(h6) erhalt, beruht wie soeben diskutiert auf Zufall bzw.Symmetrie der speziellen Situation.

19

Anhang 3: Rekursive Bisektion

Bei der Rasterisierung und Schraffur muss man Lage und Anzahl der Nullstellen von Y (t)−hschnell ermitteln. Wenn Y (t) quadratisch ist, geht das bekanntlich mit geschlossenen Formeln,(siehe Anhang 4) wahrend man bei einem kubischen Y (t) auf Iteration zur Nullstellen-Berechnung angewiesen ist. Als Alternative kommt eine Approximation des kubischen Kur-venstucks P (t) = X(t), Y (t) durch quadratische Kurvenstucke in Betracht, bei der die er-forderliche Intervall-Zerlegung automatisch ermittelt wird.

Sei P (t) = (1 − t)3a + 3 t (1 − t)2b + t2(1 − t)c + t3d, sodass P ′′′/6 = −a + 3b − 3c + d =: f ,P (t), a, b, c, d, f ∈ IR2. Sein quadratischer Interpolant zu den Stutzstellen t=0, t=1/2, t=1ist Q(t) = (1 − t)2a + 2 t (1 − t)q + t2d, q = (−a + 3b + 3c − d)/4 damit P (1/2) = Q(1/2) .Der exakte Interpolations-Fehler (nicht eine mehr oder weniger realistische Schranke dafur)ist P (t) − Q(t) = (P ′′′/6) t (t − 1/2) (t − 1), t ∈ [0, 1]. Die Richtung ist uberall gleich unddie Amplitude ist zweimal extrem im Intervall, namlich ±||f ||/

√432 bei t = 1/2 ± 1/

√12.

Wenn das kleiner ist als eine frei wahlbare, positive Toleranz, so wird Q(t) als Ersatz fur P (t)akzeptiert. Andernfalls wird das Intervall mit dem Algorithmus von de Casteljau halbiert:a, b, c, d, f =⇒ aL, bL, cL, dL, fL und aR, bR, cR, dR, fR fur linke und rechte Halfte, wobeifL = fR = f/8. Die rechte Intervall-Halfte kommt mit ihren Daten in den Keller, dielinke Halfte mit ihrer achtmal kleineren Fehlerschranke wird wie zuvor behandelt. Wenn dasaktuelle Teil-Intervall erledigt ist, wird aus dem Keller das nachste Teil-Intervall zuruckgeholtbzw. abgebrochen, wenn nichts mehr im Keller ist.

Alle akzeptierten Teil-Intervalle haben die gleiche Lange 2−m und die gleiche Fehlerschranke||f ||/(8m

√432), sodass das kubische Kurvenstuck an 1 + 2m+1 aquidistanten Stutzpunkten

in [0, 1] interpoliert wird. Diese gleichmaßige Unterteilung beruht eben darauf, dass P ′′′

konstant ist. Wenn man wie hier ein kubisches Kurvenstuck an aquidistanten Stellen stuck-weise quadratischen interpoliert, dann erhalt man immer eine stetige erste Ableitung, alsoeine quadratische Spline. Zum Beweis kann man sich auf das kubische Polynom P (t) = t3

und die Stutzstellen −2, −1, 0, 1, 2 beschranken; dann sind die beiden interpolierendenParabeln Q1(t) = −2t − 3t2 und Q2(t) = −2t + 3t2 mit Q′

1(0) = Q′2(0) = −2. (Im IR2 fur

jede Komponente.) Deshalb kann man wie zuvor besprochen alle on-curve Kontrollpunkteimplizit machen, sodass aus einem kubischen Kurvenstuck ganz automatisch eine quadratischeSplinekurve mit 2m Parabelbogen, 2 on-curve und 2m off-curve Kontrollpunkten wird, (m ≥ 0die notige Bisektions-Tiefe).

Die erwahnte positive Toleranz kann man relativ wahlen, zum Beispiel ein Tausendstel derSchrifthohe. Dann kann man grundsatzlich jeden Type 1 Font automatisch in einen gleich-wertigen TrueType Font wandeln. Alternativ kann man bei schon bekannter Schrifthohe diepositive Toleranz auch absolut wahlen, typisch den halben Pixelabstand im Raster. Daslaßt sich dann am besten vor der Font-Benutzung zusammen mit der vom Anwender ak-tuell gewahlten Skalierung und Schriftrichtung erledigen (”Font-Initialisierung”). Wenn miteinem sogenannten Font-Cache gearbeitet wird, macht man die Wandlung zusamen mit derSkalierung und Drehung nicht zu Beginn fur den gesamten Zeichenvorrat im Font, sondernfur jedes Zeichen unmittelbar vor dem ersten Zugriff. In den Font-Cache kommen dann diegewandelten Kontrollpunkte.

20

Kubisches Kurvenstück (verdeckt)Sein Kontroll−PolygonQuadratischer Spline−Interpolant

mit expliziten Kontrollpunkten (off-curve)

und impliziten Kontrollpunkten (on-curve)

Abb. 8 Wildes Kontrollpolygon fur ein kubisches Kurvenstuck

Abb. 9 Ausschnitt in 5-facher Vergroßerung

21

Anhang 4: Robuste Formeln fur die Nullstellen einer Parabel

Y (t) − h sei eine Parabel Q(t) mit Kontrollpunkten a, q, b:

Q(t) = (1 − t)2 a + 2 t (1 − t) q + t2b = a + 2(q − a)t + (a − 2q + b)t2.

Mit d := a − 2q + b und w := +√

q2 − ab ist also

Q(t) d = (t d + q − a)2 − (q − a)2 + a (a − 2q + b) = (t d + q − a)2 − w2.

Fur die beiden Nullstellen gilt t± · d + q − a = ± w. Mathematisch sind also die folgendendrei Formeln gleichwertig:

t± =a − q ± w

a − 2q + b=

a

a − q ∓ w=

q ∓ w

q ∓ w − b.

In Abhangigkeit von den Vorzeichen bei a, q, b wahlen wir aus diesen drei Alternativen diejeweils numerisch stabile, bei der alle Terme im Zahler und Nenner ≥ 0 sind.Es ist t− < t+ bei positivem d und t+ < t− bei negativem d.

Fur das Extremum gilt t d + q − a = 0 und Q(t) = −w2/d = (ab − q2)/d.Es ist ein Minimum bei positivem d und ein Maximum bei negativem d.

Vier Falle gibt es auf Grund der Fallunterscheidung ≥ 0 oder < 0 fur a = Q(0) und b = Q(1).

Fall 1: a ≥ 0 und b ≥ 0

Ist auch q ≥ 0 dann ist Q(t) ≥ 0 auf [0, 1], sodass m = 0.Bei q < 0 ist d = a − 2q + b > 0 und Q(t) hat das Minimum (ab − q2)/d, sodass m = 0 auchbei q2 ≤ ab. Nur bei q2 > ab ist das Minimum negativ und m = 2. In diesem Fall verwendenwir die Formeln t− = a/((w − q) + a), t+ = (w− q)/((w − q) + b) mit w,−q > 0, a, b ≥ 0.t+ − t− = 2w/(a − 2q + b) > 0, sodass fur die berechneten Werte t+ ≤ t− nur gelten kannauf Grund von Rundungsfehlern. In diesem Fall wird eine doppelte Nullstelle unterstellt undm = 0 gesetzt.

Fall 2: a ≥ 0 und b < 0

Hier ist m = 1. Ferner ist ab ≤ 0, w reell und ≥ |q|. Daher ist t− = a/((w − q) + a) =(w+ q)/((w+ q)− b) aus [0, 1] die richtige Nullstelle. Die erste Formel wird bei q < 0 benutztund die zweite Formel bei q ≥ 0. Beachte −b > 0.

Fall 3: a < 0 und b ≥ 0

Wieder ist m = 1 und w ≥ |q|. Jedoch ist jetzt t+ = (w− q)/((w− q)+ b) = −a/((w+ q)−a)aus [0, 1] die richtige Nullstelle. Die erste Formel wird bei q < 0 benutzt und die zweiteFormel bei q ≥ 0. Beachte −a > 0.

Fall 4: a < 0 und b < 0

22

Ist auch q ≤ 0 dann ist Q(t) < 0 auf [0, 1], sodass m = 0.Bei q > 0 ist −d = −a + 2q − b > 0 und Q(t) hat das Maximum (q2 − ab)/(−d), sodassm = 0 auch bei q2 ≤ ab. Nur bei q2 > ab ist das Maximum positiv und m = 2. In diesemFall verwenden wir die Formeln t+ = −a/((w + q) − a), t− = (w + q)/((w + q) − b) mitw, q,−a,−b > 0. Hier ist t−− t+ = 2w/(−a+2q − b) > 0. Wieder wird m = 0 gesetzt, wennunter dem Einfluß von Rundungsfehlern fur die berechneten Werte t− ≤ t+ gilt.

Insgesamt erhalt man m = 0 oder 1 oder 2 als Anzahl der Nullstellen im Intervall [0, 1].

Der Fall m = 0 erfordert nur die Vorzeichen-Abfragen von a, b, q und eventuell q× q− a× b.

Bei m = 1 wird die berechnete Nullstelle t1 ausgeliefert:auch unter dem Einfluß von Rundungsfehlern gilt dafur 0 ≤ t1 ≤ 1.

Bei m = 2 wird das berechnete Nullstellenpaar t1, t2 ausgeliefert:auch unter dem Einfluß von Rundungsfehlern gilt dafur 0 ≤ t1 ≤ t2 ≤ 1.

23

Anhang 5: Ein Blick in die Vergangenheit

Donald E. Knuth hat ein beeindruckendes Beispiel fur die Vorgehensweise in fruheren Zeitengegeben [The Letter S, The Mathematical Intelligencer 2.3 (1980) p.114-122]. Auch damalsmusste der Umriss eines Schriftzeichens festgelegt werden und auch damals hat man ihnzusammengestuckelt. Doch gab es als Hilfsmittel nur Zirkel und Lineal und das folgende Bildzeigt, wie muhsam das bei Kreisbogen ist. Wegen der stuckweise konstanten Krummung fehltauch den Ubergange die Eleganz.

Abb. 10 Der Buchstabe S bei Francesco Torniello (1517),Kreissektoren zartgrun markiert

24

Mathematisch sind Kreisbogen eine Untermenge von Ellipsen-Segmenten, exakt darstellbarals X(t) = (a0 + a1t + a2t

2)/(1 + t2), Y (t) = (b0 + b1t + b2t2)/(1 + t2) mit −1 ≤ t ≤ 1

fur 1800-Bogen bzw. −∞ < t < ∞ fur 3600-Bogen. Alle anderen Bereiche sind auch moglich.Diese Verallgemeinerung von Kreis- auf Ellipsen-Bogen ist unvermeidlich, wenn man beliebigeSkalierung in x- und y-Richtung wunscht. Man sieht die nahe Verwandtschaft dieses Kurven-vorrats mit den quadratischen Bezier-Kurven, die ebenfalls Wendepunkte nur an den Knotenhaben konnen.

25