25
Polynome im Einsatz: ezier-Kurven im CAD Dipl.-Inform. Wolfgang Globke Institut f¨ ur Algebra und Geometrie Arbeitsgruppe Differentialgeometrie Universit¨ at Karlsruhe 1 / 25

Polynome im Einsatz: Bézier-Kurven im CAD - math.kit.eduglobke/media/bezier.pdf · Polynome im Einsatz: B ezier-Kurven im CAD Dipl.-Inform. Wolfgang Globke Institut f ur Algebra

  • Upload
    others

  • View
    21

  • Download
    0

Embed Size (px)

Citation preview

Polynome im Einsatz:Bezier-Kurven im CAD

Dipl.-Inform. Wolfgang Globke

Institut fur Algebra und GeometrieArbeitsgruppe Differentialgeometrie

Universitat Karlsruhe

1 / 25

Kurven im Raum

Eine Kurve im R3 ist durch eine Abbildung

c : [a, b]→ R3, t 7→

x(t)y(t)z(t)

gegeben.Dabei kann man sich t als Zeitparameter vorstellen, so dass dieKurve c im Zeitraum von t = a bis t = b abgelaufen wird.

2 / 25

Kurven im Raum

c(a)

c(b)

c(t)x

y

z

3 / 25

Tangenten

Die Tangente einer Raumkurve c im Punkt c(t0) ist die Gerade, diedurch den Punkt c(t0) in Richtung der Ableitung c′ nach demZeitparameter t zum Zeitpunkt t0 verlauft:

c′(t0) =

x ′(t0)y ′(t0)z ′(t0)

Die Ableitung c′(t0) selbst ist ein Richtungsvektor, den man sicham Punkt c(t0) befestigt vorstellen kann, und die Kurve

”entlanggleitet“, wenn t0 variiert.

Die Lange ‖c′(t0)‖ der Ableitung kann als Geschwindigkeitaufgefasst werden.

4 / 25

Tangenten

c(t0)

c!(t0)

5 / 25

Kurven im CAD

Gewunscht:Eine glatte Kurve b(t), deren Verlauf durch Angabe vonKontrollpunkten vorgegeben wird.

b3

b2

b1

b0

6 / 25

Kurven im CAD

Forderungen:

1 Zum Zeitpunkt t = a soll die Kurve im Startpunkt liegen:b(a) = b0.

2 Zum Zeitpunkt t = b soll die Kurve im Endpunkt liegen:b(b) = b3.

3 In der ersten Halfte des Kurvenverlaufs soll die Kurve stark zub1 hingezogen werden.

4 In der zweiten Halfte des Kurvenverlaufs soll die Kurve starkzu b2 hingezogen werden.

7 / 25

Kurven im CAD

Ansatz:Zu jedem Zeitpunkt t ∈ [a, b] soll b(t) eine

”gewichtete Summe“

der Kontrollpunkte sein:

b(t) = B0(t)b0 + B1(t)b1 + B2(t)b2 + B3(t)b3

mit

B0(t) + B1(t) + B2(t) + B3(t) = 1 fur alle t ∈ [a, b],

Bi (t) ≥ 0 fur t ∈ [a, b], i = 0, 1, 2, 3.

8 / 25

Bernstein-Polynome

Als”Gewichtsfunktionen“ bieten sich die kubischen

Bernstein-Polynome B30 , B3

1 , B32 , B3

4 an:

B3k =

(3

k

)X k(1− X )3−k

1 = b0 = a

B30

B31 B3

2

B33

1

9 / 25

Bernstein-Polynome

Die Bernstein-Polynome sind geeignete Gewichtsfunktionen:

Sie sind eine Partition der 1, d.h.

1 = (X + (1− X ))3 =3∑

k=0

(3

k

)X k(1− X )3−k =

3∑k=0

B3k .

Auf dem Intervall [0, 1] gilt stets

B3k (t) ≥ 0.

(Fur beliebige Intervalle [a, b]: Umparametrisieren.)

10 / 25

Bezier-Kurven

Eine kubische Bezier-Kurve b(t) hat die Bernstein-Polynome alsGewichtsfunktionen:

b(t) = B30 (t)b0 + B3

1 (t)b1 + B32 (t)b2 + B3

3 (t)b3

Somit hat die Kurve die gewunschten Eigenschaften:

1 Bei t = 0 ist B30 (0) = 1 und B3

1 (0) = B32 (0) = B3

3 (0) = 0,also b(0) = b0.

2 Bei t = 1 ist B33 (0) = 1 und B3

0 (0) = B31 (0) = B3

2 (0) = 0,also b(1) = b3.

3 In der ersten Halfte des Kurvenverlaufs ist der Wert von B31 (t)

am großten, die Kurve wird also zu b1 hingezogen.

4 In der zweiten Halfte des Kurvenverlaufs ist der Wert vonB3

2 (t) am großten, die Kurve wird also zu b2 hingezogen.

11 / 25

Bezier-Kurven

Die beiden franzosischen Ingenieure Pierre Bezier (1910-1999) undPaul Faget de Casteljau (1930- ) entwickelten in den 1960erJahren unabhangig voneinander die Bezier-Kurven in derAutomobilindustrie (der eine fur Renault, der andere fur Citroen).

12 / 25

Bezier-Kurven

Die kubischen Bernstein-Polynome bilden eine Basis desRaums der Polynome vom Grad 3.

Somit konnen alle Kurven, die auf einem Segment mit einerpolynomialen kubischen Kurve ubereinstimmen, alsBezier-Kurven dargestellt werden.

Fur polynomiale Kurvensegmente von beliebigem Grad n kannman die Bernstein-Polynome vom Grad n verwenden:

Bnk =

(n

k

)X k(1− X )n−k .

13 / 25

de Casteljau-Algorithmus

Bernstein-Polynome haben einige verbluffende algebraischeEigenschaften.Daraus lasst sich der de Casteljau-Algorithmus ableiten, mit demeine Bezier-Kurve an der Stelle t sehr effizient ausgewertet werdenkann:

b0

t

��???

????

?

b11−t //

t

��>>>

>>>>

> b10

t

��>>>

>>>>

b2

t

��>>>

>>>>

>1−t // b1

11−t //

t

��>>>

>>>>

b20

t

AAA

AAAA

A

b31−t // b1

2t // b2

11−t // b(t)

14 / 25

de Casteljau-Algorithmus

Mit dem de Casteljau-Algorithmus kann man auch

Ableitungen der Kurve berechnen.

Unterteilung des Kontrollpolygons zur Approximation derKurve berechnen:

b3

b2

b1

b0

15 / 25

Splines

Eine Spline-Kurve ist eine Kurve s, die

sich stuckweise aus polynomialen Kurvensegmentenzusammensetzt,

aber nicht global eine polynomiale Kurve sein muss.

16 / 25

Splines

Statt stuckweise durch Bezier-Kurven, kann man Splines auch alsLinearkombination von B-Splines (

”B“ fur Basis) darstellen.

B-Splines sind keine Polynome, aber stimmen uber gewissenIntervallen mit Polynomen uberein.

Vorteil: Kontrollpunkte beeinflussen den Kurvenverlauf nurlokal.

In der Industrie bekannt als”Non-Uniform Rational B-Splines“

(NURBS).

17 / 25

Klassisches Problem: Interpolation

Bei einem Interpolationsproblem werden Punkte p1, . . . ,pk ∈ Rn

vorgegeben, durch die eine Kurve gelegt werden soll.

-5 -2,5 0 2,5 5

-3

-2

-1

1

2

3

In der Regel sind noch Nebenbedingungen an die Kurve gegeben.

18 / 25

Klassisches Problem: Interpolation

Interpolation leicht durch Polynome zu losen(es ist nur ein LGS zu losen).Aber: Fur k Punkte Polynom vom Grad k notwendig - dieskann zu schlechten Losungen fuhren:

-5 -2,5 0 2,5 5

-3

-2

-1

1

2

3

Besser: Kurve stuckweise aus Polynomen zusammensetzen.19 / 25

Klassisches Problem: Interpolation

Hermite-Interpolation: Ableitungen der Kurve in denInterpolationspunkten werden zusatzlich vorgegeben.

Durch Bezier-Kurven ohne Aufwand losbar.

Ableitungen der Bezier-Kurve sind durch das Kontrollpolygonvorzugeben.

20 / 25

Klassisches Problem: Interpolation

Spline-Interpolation: Beliebig viele Interpolationspunkte, aberKurve nur stuckweise polynomial vom Grad 3.

Kurve ist Linearkombination von B-Splines.

Linearkombination wird durch Losen eines LGS bestimmt:4 11 4 1

. . .

1 4 11 4

c>0c>1...

c>k−1

c>k

=

p>0p>1...

p>k−1

p>k

21 / 25

Anwendungen

Freiformkurven (und -flachen) in der Computergraphik.

Laufwege fur Roboter und Maschinen.

Schriftsatze als Vektorgraphiken.

Modellierung von 3D-Daten.

Numerische Simulation physikalischer Prozesse.

22 / 25

Weitere Grundlagen

Die Theorie der Bezier- und Spline-Kurven beruhrt auch folgendeBereiche der Mathematik:

Differentialgeometrie.

Numerische Mathematik.

Projektive Geometrie.

23 / 25

CAD in Karlsruhe

IBDS Prautzsch

Institut fur angewandte Geometrie und Computergraphik

Vorlesung: Kurven und Flachen im CAD

Vorlesung: Unterteilungsalgorithmen

Vorlesung: Rationale Splines

Vorlesung: Netze und Punktwolken

Praktikum: Geometrisches Modellieren

24 / 25

G. Farin:Curves and Surfaces for CAGD (Morgan Kaufmann)

H. Prautzsch, W. Boehm, M. Paluszny:Bezier and B-Spline Techniques (Springer)

25 / 25