1 Bézier-Bernstein Methoden für Bivariate Polynome Mathias Grieser Murat Deniz 29.09.2011 Lehrstuhl für Mathematik IVApproximationstheorie G. Nürnberger,

1

Bézier-Bernstein Methoden für Bivariate Polynome

Mathias Grieser

Murat Deniz

29.09.2011

Lehrstuhl für Mathematik IV Approximationstheorie G. Nürnberger, M. Matt, G. Schneider Seminar HWS 2011

2

Bézier-Bernstein Methoden für Bivariate Polynome

Inhaltsverzeichnis

1. Baryzentrische Koordinaten

2. Bernstein Basis Polynome

3. Die Bézier-Bernstein Darstellung

4. Stabilität der BB-Darstellung

5. Der deCasteljau Algorithmus

6. Richtungsableitung

7. Ableitung an einem Eckpunkt

8. Kreuzableitung auf einer Kante

9. Stetigkeit und stetige Differenzierbarkeit

10. Unterteilung/Basiswechsel

3


Seien

vi := (xi; yi), i = 1, 2, 3 Punkte in ℝ² und sei

T := <v1, v2, v3>

ein Dreieck mit den Ecken v1, v2, v3

Lemma 1.1:Jeder Punkt v := (x, y) є ℝ² lässt sich in der Form

v = b1v1 + b2v2 + b3v3

mit

1 = b1 + b2 + b3

darstellen.

b1, b2, b3 werden als baryzentrische Koordinaten des Punkts v bzgl. des Dreiecks T bezeichnet.

4


=: M

Dies ist gleichbedeutend mit folgender Matrix

1 1 1 b1 1

x1 x2 x3 b2 = x

y1 y2 y3 b3 y

Durch lösen dieses LGS oder durch die Formel (b2, b3 analog)

1 1 1

det x x2 x3

y y2 y3

b1 =

det (M)

erhält man die baryzentrischen Koordinaten.

5


Sei T ein Dreieck mit Eckpunkten v1, v2 und v3.Dann besitzen die baryzentrischen Koordinaten an den Eckpunkten folgende Werte:

am Punkt v1 am Punkt v2 am Punkt v3

b1 = 1 b1 = 0 b1 = 0b2 = 0 b2 = 1 b2 = 0b3 = 0 b3 = 0 b3 = 1

Abb. 1: baryzentrische Koordinaten an den Punkten v1 , v2 , v3

6


Definition 2.1Die Bernstein Basis Polynome sind

Bdijk :=

wobei i,j,k є ℕ0

Rekursionsformel:

Bdijk := b1 Bd-1

i-1,j,k + b2 Bd-1i,j-1,k + b3 Bd-1

i,j,k-1 i+j+k=d > 0

wobei B0000 = 1 gilt und die Bernstein Polynome gleich 0 sind, falls

mindestens eines der Indizes negativ ist.

Beispiel:

Bdd00 := b1 Bd-1

d-1,0,0 + b2 Bd-1d,-1,k + b3 Bd-1

d,0,-1 = b1 Bd-1d-1,0,0

d!i! j! k! bi

1bj2bk

3 , i+j+k = d

7


Eigenschaften:

„Partition der Eins“:

∑ Bdijk (v) = 1 für alle v є ℝ²

„Nicht-Negativität“:

Bdijk (v) ≥ 0 für alle i+j+k = d v є T

Basis:

Bd := {Bd

ijk }i+j+k=d

Dimension:

dim Bd =

d+2 2

i+j+k = d

8


Bézier - Bernstein Darstellung (BB-Darstellung):

p = ∑ cijkBdijk

wobei Bdijk die Bernstein Basis Polynome sind und cijk

als Bézier-Bernstein-Koeffizienten (BB-Koeffizienten) bezeichnet werden.

Notation:

Sei T := <v1, v2, v3> ein Dreieck, wobei v1, v2, v3 die Eckpunkten sind und d sei der Grad des Polynoms p auf diesem Dreieck.

Dann korrespondiert der Eckpunkt v1 mit dem Koeffizient cd00, der Eckpunkt v2 mit dem Koeffizient c0d0 und der Eckpunkt v3 mit dem Koeffizient c00d

i+j+k = d

9

Bézier-Bernstein-Punkte (BB-Punkte):

Die BB-Punkte ξijk є ℝ² lassen sich folgendermaßen bestimmen:

Dd,T := { ξijk := (iv1 + jv2 + kv3)/ d}i+j+k=d

Zusammen mit den Bézier-Bernstein-Koeffizienten cijk є ℝ bilden sie die Kontrollpunkte von p.

Wichtig:

Die BB-Punkte bilden eine Interpolationslage für das Polynom p


10

Beispiel für d = 3:

Abb. 3: BB-Koeffizienten

Abb. 2: BB-Punkte

dim B³ = = = 10

Im weiteren Verlauf werden

die Koeffizienten aus Abb. 3

so wie in Abb. 4 dargestelltAbb. 4: BB-Koeffizienten(vereinfacht)

d+2 2

3+2 2

3. Die Bernstein - Bézier Form

11

Der Graph eines Polynoms p verläuft innerhalb der konvexen Hülle dieser Kontrollpunkte

Abb. 5: konvexe Hülle der Kontrollpunkte im univariaten Fall


12

Sei

║c║∞ := max |cijk|

dann gilt folgender Satz:

Satz 4.1:

Sei p ein Polynom in BB-Darstellung mit Koeffizientenvektor c. Dann gilt:

║p║T ≤ ║c║∞

Dies bedeutet, dass die Werte des Polynoms p nie größer sein können, als der größte Koeffizient der BB-Darstellung


i+j+k = d

13


Satz 5.1:

Sei p ein Polynom in BB-Darstellung mit Koeffizienten

c(0)ijk := cijk i+j+k = d

v besitzt die baryzentrischen Koordinaten b := (b1.b2, b3) und für

ℓ = 1,...,d gilt

c(ℓ)ijk := b1 c(ℓ-1)

i+1,j,k + b2 c(ℓ-1)i,j+1,k + b3 c(ℓ-1)

i,j,k+1 für i+j+k = d - ℓ

Dann gilt

p(v) = ∑ c(ℓ)ijk Bd- ℓ

ijk(v)

für alle 0 ≤ ℓ ≤ d und

p(v) = c(d)000

i+j+k = d - ℓ

14

Abb. 6: de Casteljau Algorithmus

Abbildung 6 zeigt den Algorithmus für d = 2

Beispiel für ℓ = 1:

c(1)100:= b1 c(0)

2,0,0 + b2 c(0)1,1,0 + b3 c(0)

1,0,1

wobei c(0)ijk := cijk


ℓ = 0 ℓ = 1 ℓ = 2

15


Wichtige Notationen:

Ring RTm(v1):

Sei 0 ≤ m ≤ d. Dann ist der Ring RTm(v1) wie folgt definiert:

RTm(v1) := { ξd-m,j,m-j }m

j=0

wobei die ξ die BB-Punkte sind. Der Ring beinhaltet alle Punkte, die auf dem Rand des Radius m um den Punkt v1 liegen. (RT

m(v2), RTm(v3) analog)

Scheibe DTm(v1):

Sei 0 ≤ m ≤ d. Dann ist die Scheibe DTm(v) wie folgt definiert:

DTm(v1) := ∪m

n=0 RTm(v)

Sie beinhaltet alle Punkte die auf dem Rand und innerhalb des Radius m um den Punkt v1 liegen. (DT

m(v2), DTm(v3) analog)

Achtung: Verwechsel die Notation der Scheibe DTm nicht mit der

Notation der Ableitung Du , die auf den folgenden Folien definiert wird!

16

Veranschaulichung:

Gegeben sei eine Triangulierung der

Dreiecke T1, T2, T3, T4, T5 mit

gemeinsamen Punkt v.

RT1(v) ist der Ring, der alle Punkte

auf dem Radius 1 um v enthält.





Die Scheibe DT3(v) enthält alle

Punkte von RT1(v) , RT

2(v) und RT3(v)


T1

T2

T3

T4

T5

v

Abb. 7: Triangulierung von T1, T2, T3, T4, T5

17


In diesem Abschnitt sei v ein Punkt in ℝ² und u ein Vektor. Jeder Punkt v ist eindeutig bestimmt durch seine baryzentrische Koordinaten b1, b2

und b3. Außerdem wird jeder Vektor u := w - ŵ durch ein Tripel (a1, a2, a3) bestimmt. Dabei ist

ai := αi – βi, i = 1, 2, 3,

wobei (α1, α2, α3) und (β1, β2, β3) die baryzentrischen Koordinaten der zwei Punkte w und ŵ sind.

Beachte, dass die Summe des Tripels (a1, a2, a3) sich zu 0 summieren.

(a1, a2, a3) werden als Richtungskoordinaten von u bezeichnet.

18

Lemma 6.1:

Sei u ein Vektor mit Richtungskoordinaten (a1, a2, a3). Dann ist für jedes i+j+k = d

DuBdijk := d [a1 Bd-1

i-1,j,k + a2 Bd-1i,j-1,k + a3 Bd-1

i,j,k-1]

die Richtungsableitung der Bernstein-Polynome. Diese hängt nicht nur von der Richtung ab, sondern auch von der Länge des Vektors u.


19

Satz 6.2:

Sei p ein Polynom in BB-Darstellung bzgl. eines Dreiecks T und sei u ein Richtungsvektor, der durch das Tripel (a1, a2, a3) beschrieben wird. Dann ist die Richtungsableitung an einem Punkt v von p in Richtung u gegeben durch:

Dup(v) = d ∑ c(1)ijk(a)Bd-1

ijk(v)

wobei c(1)ijk(a) die Koeffizienten aus dem 1. Schritt des deCasteljau

Algorithmus, basierend auf dem Tripel a, sind.

Abb. 8: Richtungsableitung

am Punkt v


i+j+k=d-1

20

Satz 6.3:

Sei p ein Polynom in BB-Darstellung bzgl. eines Dreiecks T und sei u ein Richtungsvektor, der durch das Tripel (a1, a2, a3) beschrieben wird.

Dann gilt für 1 ≤ m ≤ d

Dmup(v) = ∑ c(m)

ijk(a)Bd-mijk(v)

wobei c(m)ijk(a) die Koeffizienten aus dem m. Schritt des deCasteljau


Der Vorteil der BB-Polynome ist, dass wir für die Richtungsableitung mit m < d nicht alle Koeffizienten des deCasteljau-Algorithmus benötigen!


i+j+k=d-m

d!(d-m)!

21


Sei T wieder ein Dreieck mit den Eckpunkten v1, v2, v3. Die Ableitung an dem Eckpunkt v1 Richtung Eckpunkt v2 und Richtung Eckpunkt v3 ist beispielhaft wie folgt definiert:

Dmv2-v1Dn

v3-v1p(v1) = ∑ ∑ (-1)i+j cd-i-j,i,j

für beliebige 0 ≤ m+n ≤ d. Dabei liegen alle dieser Koeffizienten in der Scheibe DT

m+n(v1)

Die Ableitungen an den Eckpunkten v2 und v3 oder die Ableitung in eine Richtung erfolgt analog.

(-1)m+nd!(d-m-n)!

m i

n ji=0 j=0

m n

22

Dmv2-v1Dn

v3-v1p(v1) = ∑ ∑ (-1)i+j cd-i-j,i,j

Veranschaulichung für d = 3 und m, n = 1:

D1v2-v1D1

v3-v1p(v1) = ∑ ∑ (-1)i+j c3-i-j,i,j

= 6 (c3,0,0 – c2,0,1 – c2,1,0 + c1,1,1 )

Die benötigten Koeffizienten liegen alle auf der Scheibe DT1+1(v1) =

DT2(v1).

Der Vorteil der BB-Polynome ist, dass wir für eine Ableitung an einem Eckpunkt nicht alle Koeffizienten cijk benötigen!


(-1)m+nd!(d-m-n)!

m n

j=0i=0

m i

n j

(-1)2 3! 1!

1 1

i=0 j=0

1 i

1 j

i=0, j=0 i=0, j=1 i=1, j=0 i=1, j=1

23


Abb. 9: Ableitung am

Eckpunkt v1 Richtung

v2 und Richtung

v3

i = 0, j = 0 i = 0, j = 1

i = 1, j = 0 i = 1, j = 1 DT2(v1)

24


Sei T wieder ein Dreieck mit den Eckpunkten v1, v2, v3 und u sei ein Richtungsvektor, der nicht parallel zur Kante e := < v2, v3> ist. Das Tripel a := (a1, a2, a3) sind die Richtungskoordinaten von u. Dann ist die Kreuzableitung auf der Kante e definiert durch:

Dmup(v) = ∑ c(m)

0jk(a)Bd-m0jk(v)

wobei c(m)0jk(a) die Koeffizienten aus dem m. Schritt des deCasteljau


Bei der Kreuzableitung muss mind. eine Komponente des Richtungsvektors parallel zur jeweiligen Kante, auf der abgeleitet wird, sein.

j+k=d-m

d!(d-m)!

25

Veranschaulichung für d = 3:

Abb. 10: Kreuzableitung auf Kante <v2, v3> für m = 0, 1, 2, 3

Wenn wir den Algorithmus betrachten, erkennen wir, dass wir nur die Koeffizienten cijk mit 0 ≤ i ≤ m benötigen. Diese Koeffizienten korrespondieren mit den BB-Punkten, die auf e oder auf den nächsten m Reihen parallel zu e liegen.


c300

c201

c102

c003

c012c021c030

c120

c210

c111

c[1]200

c[1]101

c[1]002

c[1]011c[1]

020

c[1]110

c[2]100

c[2]001

c[2]010

c[3]000

m = 0 m = 1 m = 2 m = 3

26


Satz 9.1:

Seien T := <v1, v2, v3> und T := <v4, v3, v2> Dreiecke mit gleicher Kante e := < v2, v3>. Die Polynome auf den Dreiecken T und T seien

p(v) = ∑ cijkBdijk (v)

und

p (v) = ∑ cijkBdijk(v)

wobei Bdijk und Bd

ijk die Bernstein Basispolynome bzgl. T und T sind. Sei u eine beliebige Richtung, die nicht parallel zu e ist. Dann gilt

Dnup(v) = Dn

up(v) für alle v є e und n = 0, …, r

nur wenn folgendes gilt

cnjk = ∑ cv,k+µ,j+KBnvµK(v4), j+k = d-n

n = 0, …, r.

~ ~~

~

~

~ ~

~

~

i+j+k=d

i+j+k=d

v+µ+K=n

27

Dies bedeutet, dass für Stetigkeit, also für n = 0, folgendes gilt:

c0jk = c0,k,j , j+k = d

Für stetige Differenzierbarkeit, also für n = 1, muss folgendes gelten:

c1jk = b1c1,k,j + b2c1,k+1,j + b3c1,k,j+1 , j+k = d-1


Für n = 0 stimmen die Koeffizienten

von T mit den Koeffizienten von T

auf der gemeinsamen Kante e

überein


~

~

c300

c201

c102

c003

c030 c021 c012

c111c120

c210

c300

c210

c120

c111

c102

c201

~c003 c030~

~~

~

~

~~

~c021c012

~

~

Abb. 11:Stetigkeit vonT und T auf e

~

T

T~

28

Für n = 1 (Abb. 12) stehen die c1jk

von T in einer linearen Beziehung

zu jeweils 3 Koeffizienten von T,

d.h. sie liegen in einer Ebene


c201

c102

c003

c030 c021 c012

c111c120

c210

c300

c210

c120

c111

c102

c201~

c003 c030~

~~

~

~

~~

~c021c012

~

~

~

c300Abb. 12:stetige Differenzier-barkeit von T und Tauf e

~

c300

c201

c102

c003

c030 c021 c012

c111c120

c210

c300

c210

c120

c111

c102

c201

~c003 c030~

~~

~

~

~~

~c021c012

~

T

~T

T~

TAbb. 13:2-fache stetige Differenzierbar-keit von T und T auf e~

Für n = 2 (Abb. 13) stehen die c2jk von T in einer quadratischen Beziehung zujeweils 6 Koeffizienten von T

~ ~

29


T1

T2

T3

T4

T5

v

Gegeben sei eine Triangulierung der Dreiecke

T1, T2, T3, T4, T5 mit Polynomen p1, p2,

p3, p4, p5 und einem gemeinsamen

Punkt v. Nur die Koeffizienten von T1

mit den schwarzen Punkten seien

bekannt und die restlichen

Koeffizienten (weiße Punkte) seien

unbekannt. Außerdem seien die

Polynome am Punkt v 2-mal stetig

Differenzierbar.

Dann lassen sich die Koeffizienten, die

sich auf und innerhalb der Scheibe DT2(v)

befinden, anhand der bekannten

Koeffizienten bestimmen.

Abb. 14: Triangulierung von T1, T2, T3, T4, T5

30

Lemma 9.2:Seien p und p Polynome auf den Dreiecken T und T mit Cr (r-fache stetige Differenzierbarkeit) auf einer gemeinsamen Kante e := <v2, v3> und sei 0 ≤ ℓ+1 ≤ q, q sowie q+q-ℓ≤ m ≤ d. Außerdem seien die Knoten v1, v2 und v4 nicht kollinear und die Koeffizienten cijk und cijk der Polynome p und p korrespondieren mit den BB-Punkten in DT

m-1(v2) ∪ DT

m-1(v2). Zusätzlich seien die Koeffizienten von p und p auf dem Ring Rm(v2) innerhalb des Abstands q+q-ℓ von e, außer den Koeffzienten

cv = cv,d-m,m-v, v = ℓ+1, …, q

cv = cv,m-v,d-m, v = ℓ+1, …, q

bekannt. Dann sind diese Koeffizienten eindeutig bestimmt durch die Cr

–Bedingungen

cn,m-n,d-m = ∑ ci,j+d-m,k+m-nBnijk(v4), ℓ+1 ≤ n ≤ q+q-ℓ


i+j+k=n

~ ~

~~

~ ~

~ ~~

~ ~ ~

~

31

Beispiel:

Sei d = 10, m = r = 8, q = 2, q = 4,

ℓ = 0

Abbildung 13 zeigt die Koeffizienten

der zwei zusammengefügten

Dreiecke. Wir nehmen an, dass

wir alle mit einem Kreis

markierten Koeffizienten kennen

und nur die 6 Koeffizienten, die

mit einem blauen Viereck markiert

sind, unbekannt sind.


v2

v1

v3

v4

Abb. 15: Anwendung des Lemma 9.2

~

32

Um die 6 unbekannten Koeffizienten

zu bestimmen, benötigen wir 6

Gleichungen. Da p und p am Punkt

v2 8-mal stetig differenzierbar ist

und diese 6 Koeffizienten

auf dem Ring R8(v2) liegen, lassen

sich diese durch die 6 Bedingungen

C1, …, C6 bestimmen.

Beachte, dass nicht alle Koeffizienten

zur Berechnung benötigt werden,

sondern nur diejenigen, die in den

6 Bedingungen vorkommen (schwarz

markierte Punkte)


v2

v1

v3

v4


~

33

Die 6 stetige Differenzierbarkeits-

Bedingungen:

1. C1

2. C2

3. C3

4. C4

5. C5

6. C6


v1

v3v2

v4


34


Sei p ein Polynom in BB-Darstellung bzgl. eines Dreiecks T mit den Eckpunkten v1, v2, v3. Dann unterteilt ein beliebiger Punkt w im inneren von T das Dreieck T in die drei Teildreiecke

T1 := <w, v2, v3>, T2 := <w, v3, v1>, T3 := <w, v1, v2>,

Der folgende Satz sagt unter anderem aus, dass die Basen der Teildreiecke T1, T2, T3 ebenfalls Basen des Polynomraums Pd sind. Dadurch lässt sich ein Basiswechsel durchführen

35

Satz 10.1:

Gegeben sei das Dreieck T mit den Teildreiecken T1, T2, T3, wie oben beschrieben. Der Punkt w hat die baryzentrischen Koordinaten a := (a1, a2, a3) und für ℓ = 1, 2, 3 seien BTℓ,d

ijk die Bernstein Basis Polynome bzgl. Tℓ := <w, vℓ+1, vℓ+2>. Dann gilt für beliebige Polynome p mit BB-Koeffizienten

∑ c(i)0jk BT1,d

ijk(v), v є T1

p(v) = ∑ c(j)i0k BT2,d

ijk(v), v є T2

∑ c(k)iij0 BT3,d

ijk(v), v є T3

wobei c(v)ijk := c(v)

ijk(a) die Koeffizienten aus dem v-ten Schritt des deCasteljau Algorithmus, basierend auf dem Tripel a, sind und der Startwert c(0)

ijk := cijk ist.


i+j+k = d

i+j+k = d

i+j+k = d

36


Der Koeffizient c(2)000 korrespondiert hierbei mit dem Punkt w. Man

erkennt durch abzählen der Koeffizienten, dass die Dimension der Teildreiecken (= 6) mit der Dimension von T (= 6) übereinstimmt.


Abb. 16: Koeffizienten der Teildreiecke

T1

T3

T2

37

Literaturverzeichnis

Lai, M. J.; Schumaker, L.L. (2007): Spline functions on triangulations, 18-61. Cambridge Univ. Press.

38

Vielen Dank für Eure Aufmerksamkeit!

Documents

1 Bézier-Bernstein Methoden für Bivariate Polynome Mathias Grieser Murat Deniz 29.09.2011 Lehrstuhl für Mathematik IVApproximationstheorie G. Nürnberger,