Modul: B-CG Grundlagen der Computergraphik · 1 Hier wird Wissen Wirklichkeit Modul: B-CG Grundlagen der Computergraphik Geometrie-Repräsentationen Prof. Dr. Detlef Krömker Professur

1

Hier wird Wissen Wirklichkeit

Modul: B-CG Grundlagen der Computergraphik

Geometrie-Repräsentationen

Prof. Dr. Detlef KrömkerProfessur für Graphische DatenverarbeitungInstitut für InformatikFachbereich Informatik und Mathematik (12)

Prof. Dr. Detlef KrömkerInstitut für Informatik

2 Hier wird Wissen WirklichkeitB-CG – V01 Geometrie-Repräsentationen

Rückblick: Bildrepräsentationen

• Merkmalsebene

• Abtastebene

• Reiz- & Aktionsebene

Grafik- undMerkmals-Primitive

Digitales Bild

optisch

beliebige Datenstruktur

1

2

3

4

Bildfunktion

2



BeispielePolygonale Modellierung

Freiformflächen =(Tensorflächen,Polynomflächen, Parametrische Flächen)

Prozedurale Modellierung

�

(�)



Übersicht

1. Einführung: Ziele und Anforderungen2. Koordinatensysteme 3. Geometrisches Modellieren in 2D4. Geometrisches Modellieren in 3D: Eine Übersicht 5. Die Basistechnik: Polygonale Repräsentationen6. Spezielle Erweiterungen:

Polygonnetze, LODs, Subdivision, …7. Parametrische Kurven und Flächen (eine erste Einführung, die Ideen!)8. Zusammenfassung9. Spezielle Literatur10. Ausblick

3



Einführung: Ziele und Anforderungen

Begriffbildung

Wir beschreiben reale und gedankliche (imaginäre) Objekte insbesondere durch ihre

� Geometrische Eigenschaften: die Form und die Lage in einem Bezugssystem und durch ihre

� Topologische Eigenschaften: Die Zusammenhangsinformationen

René Descartes, La Geometrie (Erstausgabe 1637)



Geometrie

Die Geometrie (griech. „Landmessung“) ist ein Teilgebiet der Mathematik.Wir unterscheiden:

Die Euklidische Geometrie ist die klassische, uns vertraute Geometrie der Ebene oder des Raums, die schon Euklid in „Den Elementen“ dargelegt hat: Elementare Konstrukte sind: Punkt, Linie, Gerade, Ebene, Winkel, Parallelen u.a.

Die Euklidische Geometrie ist essentiell für die CG. Als Spezialgebiet gilt insbesondere die Algorithmische Geometrie (computationalgeometry).

„Wer die Geometrie versteht, der versteht alles in der Welt.“Galileo Galilei (1564-1642)

4



Erweiterungen der euklidischen Geometrie

� Affine Geometrie: Es gilt zwar das euklidische Parallelenaxiom, aber Abstand und Winkel haben keine Bedeutung. Inbegriff der unter affinen Abbildungen invarianten geometrischen Eigenschaften

� Projektive Geometrie: Zu jeder Klasse paralleler Geraden kommt ein so genannter unendlich ferner Punkt hinzu; alle diese Punkte bilden die unendlich ferne Gerade. Zwei Geraden schneiden sich stets in einem Punkt: Zwei parallele Geraden schneiden sich in ihrem gemeinsamen Fernpunkt, eine gewöhnliche Gerade und die Ferngerade schneiden sich im Fernpunkt der Geraden.

� Nichteuklidische Geometrie: hier gilt das Parallelenaxiom nicht Man unterscheidet elliptische und hyperbolische Geometrien.

V



Geschichte der Geometrie (1)

Erste Ansätze schon in in den frühen Hochkulturen entwickelt, insbesondere zur Landvermessung, für astronomische Beobachtungenund in der Architektur: Winkel messen, Flächen- und Rauminhalte sowie Raumpunkte bestimmen.

Die Griechen machten die Geometrie zu einer Wissenschaft und benutzten vielfältig. Euklid fasste die damals bekannten Kenntnisse in der Geometrie in seinem Buch "Die Elemente" zusammen.

Erst im 17. Jh. entsteht die analytische Geometrie (Descartes):Benutzt algebraische Hilfsmittel (vor allem aus der linearen Algebra) zur Lösung geometrischer Probleme. Entscheidendes Hilfsmittel der analytischen Geometrie ist ein Koordinatensystem. In der Praxis verwendet man meist ein kartesisches Koordinatensystem.

V

5



Geschichte der Geometrie (2)

Im 18. Jhd..entsteht die Differentialgeometrie als Bindeglied zur Analysis.

Ab dem 19. Jahrhundert: entscheidende Fortschritte zur „Exaktifizierung“ mathematischer Begriffe wie Axiom und Beweis und darauf basierend die Entdeckung der nichteuklidischen Geometrie.

Spätestens ab hier wird es wirklich schwierig, aber dieses brauchen wir in der CG eigentlich nicht!

V



Topologie

ist ein Teilgebiet der Mathematik: Die Topologie untersucht u.a. die Eigenschaften geometrischer Körper (d. h. topologischer Räume), die durch Verformungen mit Homöomorphismen (≠ Homomorphismen!) nicht verändert werden.

Dazu gehört das Dehnen, Stauchen, Verbiegen, Verzerren, Verdrillen eines Gegenstands; Zum Beispiel haben eine Kugel und ein Glas dieselbe Topologie; sie sind homöomorph. Ebenso sind ein Torus und eine einhenkelige Tasse homöomorph.

� Der axiomatische Aufbau der modernen Topologie beruht auf dem grundlegenen Konzept der "Nachbarschaft", formalisiert als offene Umgebung.

6



Kordinatensysteme = BezugssystemeMit Hilfe eines Koordinatensystems lassen sich die Positionen von Punkten im

Raum angeben. Die Position im Raum wird im gewählten Koordinatensystem durch Angabe von Zahlenwerten, Koordinaten genannt, eindeutig bestimmt. Mittels einzelner Punkte lassen sich dann durch Angabe mehrerer Punkte bestimmte Objekte (Linien, Abstände, Flächen, Körper) angeben.

Die Anzahl der zur Beschreibung notwendigen Werte entspricht der Dimension des Raumes Man fasst die Koordinaten eines n-dimensionalen Raumes dann als ein n-Tupel von Koordinaten auf.

Der Punkt, bei dem alle Koordinaten den Wert 0 annehmen, nennt man den Koordinatenursprung.

Das am häufigsten verwendete Koordinatensystem ist das Kartesische Koordinatensystem.



Kartesisches Koordinatensystem (1)� orthogonales Koordinatensystem,

dessen Koordinatenlinien parallele Geraden in konstantem Abstand sind.

� nach dem latinisierten Namen Cartesius seines Erfinders René Descartes.

� Die horizontale Achse wird als x-Achse, Abszisse oder Rechtsachse bezeichnet.

� Die vertikale Achse heißt entsprechend y-Achse, Ordinate oder Hochachse.

7



Kartesisches Koordinatensystem (2)

� Die räumliche Achse z wird Applikate (in der Geographie: Kote) genannt. Wichtig Unterscheidung: rechts- und links (-händige) Systeme

� höherdimensionaler Räume (4D, ...) sind möglich, die Achse für die Ausdehnung in der vierten Raumdimension wird häufig als w-Achse bezeichnet. linkshändig rechtshändig



Weitere gebräuchliche Koordinatensysteme

� krummlinige orthogonale Koordinatensysteme: � ebene Polarkoordinaten und Zylinderkoordinaten� räumliche und sphärische Polarkoordinaten (Kugelkoordinaten) � Toruskoordinaten� ...

� Baryzentrische Koordinaten

8



Baryzentrische Koordinaten (1)

Seien x1, ..., xn die Eckpunkte eines Simplex (1D: Strecke, 2D Dreieck, 3D Tetraeder) im Vektorraum A. Wenn für einen Punkt p aus A folgende Gleichung erfüllt ist,

so nennen wir die Koeffizienten (a1, ..., an) baryzentrische Koordinatenvon p zu x1, ..., xn.

Die Eckpunkte haben die Koordinaten (1, 0, 0, ..., 0), (0, 1, 0, ..., 0), ..., (0, 0, 0, ..., 1).

xa ... xa p · )a ... (a nn11n1 ++=++



Baryzentrische Koordinaten (2)

Baryzentrische Koordinaten sind nicht eindeutig: Für jedes von Null verschiedene b sind (b a1, ..., b an) ebenfalls baryzentrischeKoordinaten von p.

Falls die Koordinaten positiv und kleiner als 1 sind, so liegt der Punkt p in der konvexen Hülle von x1, ..., xn, also dem Simplex mit diesen Eckpunkten � sehr gut für Interpolationen geeignet.

Stellen wir uns Massen im Verhältnis a1, ..., an an den Eckpunkten des Simplex vor, so liegt der Massenschwerpunkt (das Baryzentrum) in p. Dies ist der Ursprung des Begriffs "baryzentrisch", eingeführt 1827 von August Ferdinand Möbius.

9



Spezielle Koordinatensysteme in der CG (1)

� Objektkoordinaten� Intrinsisches Koordinatensystem eines Objekts� Hierarchische Modellierung� Modellierungs -Transformation zu Weltkoordinaten

� Weltkoordinaten (KS der Szene!)� Wurzel für die hierarchische Modellierung� Bezugspunkt für die Kamera� Sicht-(Viewing-)Transformation zu Kamerakoordinaten

� Kamerakoordinaten (Viewing-Koordinaten)� Bezugssystem für die Beleuchtungsberechnung� Perspektivische Transformation zu normalisierten

Projektionskoordinaten



Spezielle Koordinatensysteme in der CG (2)

� Normalisierte Projektionskoordinaten� 3D: Normalisiert [-1 .. 1]3 oder [-1 .. 1]2 x [0 .. 1]� Clipping

� Normalisierte Bildschirmkoordinaten� 2D: [0 .. 1] 2� Ursprung?� RenderMan, X11: Oben links� OpenGL: Unten links� Viewport-Transformation

� Anpassung der Seitenverhältnisse� Position innerhalb der Rasterkoordinaten

� Raster-(Window-)Koordinaten� 2D: Einheit in Pixel [0 .. xres-1, 0 .. yres-1]

10



Geometrisches Modellieren in 3D� Gesamtziel:

Beschreibung von (physikalisch realen und imaginären) Objekten in einem Modell, welche mathematisch betrachtet eine Punktmenge bzw. Mengen aus Unterräumen des R3 sind

� Historische Entwicklung

� (Graphisches Modelle (2D): = Zeichnungen)� Drahtgitter-Modell (3D)� Polygonale Modelle (Polyhedron-Modelle)� Freiformflächen-Modelle� CSG, Volumenmodelle, …� Softobjects, Prozedurale Modelle, ...



ZeichnungenProblem 1: keine Körperbeschreibungen �� unmögliche Objekte repräsentierbar

?

11



Zeichnungen und DrahtgittermodelleProblem 2: Mehrdeutigkeiten



Geometrisches Modellieren

� Formale Anforderungen an Modell� Vollständigkeit (Geometrie und Topologie) � Integrität (keine „unmöglichen“ Objekte erzeugbar)� Balance bezüglich der Komplexität der Beschreibung und der

geometrischen Übereinstimmung zwischen Modell und Objekt

� Übliche Modellklassifizierungen� Dimension der Erzeugenden� Art der mathematischen Beschreibung� Bezug zum „realen“ Objekt

12



ModellklassifikationDimension der Erzeugenden

� Volumenmodell� 3D-Erzeugende

� Flächenmodell� 2D-Erzeugende� Rand des Volumens� Oberfläche� Manchmal nicht

ausreichend

� Linienmodell (Wire Frame)� 1D-Erzeugende� Rand einer Fläche� Rand des Randes eines

Volumens� Nicht ausreichend

� Punktmodell� 0D-Erzeugende� Element einer Linie� Element des Randes einer

Fläche� Nicht ausreichend, aber

aktuelles Forschungsthema„Point“ Rendering

� Modeerscheinung?



Weitere Klassifizierungen� Modellklassifizierung nach der

Art der mathematischen Beschreibung� Implizite Darstellung � Explizite Darstellung � Parametrische Darstellung

� Modellklassifizierung nach Bezug zum „realen oder mentalen“ Modell

� Analytisch exakt

� Interpolation

� Approximation

0),,( =zyxf),( yxgz =

210 rrxx �� µλ ++=

13



Repräsentationsschemata für Körper

� Primitive Instancing

� Decomposition Models

� Constructive Models

� Boundary Models (Flächenmodelle)

� Sweeping

� u. v. a. m.



Primitive Instancing

� Sammlung von vordefinierten Primitiven (Kugel, Zylinder, ...)� Instanzieren durch beschreibende Parameter� Einfachste Art zur Beschreibung von geometrischen Objekten� Nachteil: begrenzte Menge von Primitiven� Beispiele: (tbrick, l, h1, h2, w1, w2)

14



Quadrikensind häufig genutzte Primitive

Können auch parametrisch definiert werden, z.B. als:

� Sweep-Körper um die z-Achse � Viele elementare Körper

repräsentierbar: Kegel, Zylinder (Scheibe), Kugel (Ellipsoid), Paraboloid, Hyperboloid, Torus, …

[ ] 0

1

1,,,

0222222222

=

��

�

�

��

�

�

��

�

�

��

�

�

=+++++++++

zyx

JIGDIHFCGFEBDCBA

zyx

JIzGyDxCxzFyzBxyHzEyAx



Decomposition Models

� Auch spatial-partioning representation genannt� Basiselemente: Würfel, Quader, Halbräume

ggf. mit Parametrisierung� Nur eine Grund-Operation nötig: Glue („Verkleben“)� Varianten:

� exhaustive enumeration� space subdivision� cell decomposition

15



Exhaustive Enumeration

� Spatial-occupancy enumeration� Primitive: Block (3D), Rechteck (2D)� Glue-Operation: 3D-array, 2D-array

� 2D: Repräsentations-schema im digitalenBildprozess (digitalimage processing)= Digitale Bild

Torus represented by spatial-occupancy enumeration.



Constructive ModelsConstructive Solid Geometrie

� Mächtigere Operationen als „Glue“� Mengentheroetisch bzw. Boolean Set Operationen

� ∪ Vereinigung (union)∩ Durchschnitt (intersection)\ Differenz (hier A\B)

� Varianten� (Halbraum-Modell)� Constructive Solid Geometrie CSG

A

B

16



Constructive Solid Geometrie

� Primitive sind begrenzte Elemente z.B. Würfel, Zylinder, Kugel� Für Benutzer einfacher handhabbar� Transformationsoperationen – Rotation, Translation, Skalierung� Mengentheoretische Glue-Operationen� Schema:

� Hierarchische Strukturierung� Blatt: Primitiv + Transformierung� Knoten: Operation



CSG Modellieren

17



Boundary Modelsdie wichtigste Repräsentation

� Flächenmodell� „verbessertes graphisches Modell“� Ursprung:

polyhedrales Modell� Boundary Datenstruktur

Drei Basisobjekttypen:� Face (Fläche),� Edge (Kante), � Vertex (Ecke)



Boundary Models

� Schemata� Polygon-based� Vertex-based� Edge-based

18



Breps für Solid models (Körper)

� Invarianztheorem: Euler Charakteristik� v – e + f = 2 (für polyhedrons)

� Erweiterte Euler-Poincaré-Formel für Flächen mit Löchern� v – e + f = 2 (s – h) –l

s: Schale (shell) -> Körperh: Höhle (hole) -> Körperl: Loch (loop) -> Flächen

� Prinzipiell sind wir nicht auf ebene Primitive (Polygonmodelle) beschränkt � Freiformflächen (Polygonal definierte Objekte)



Sweeping

� Modell: i. a. Volumenmodell

� Primitive: Profil (Cross Section) und Pfad (Trajektorie)

� Definition: Ein Swept-Objekt beschreibt die Punktmenge im R3, die durch Bewegen eines 2D-Profils entlang eines Pfades überstrichen wird.

19



SweepingBeispiele



Sweeping

� Spezielle Ausprägungen� Extrusion (Pfad=Strecke)� Translational (Profile ändert Normalenrichtung nicht)� Rotational (revolving) (Pfad ist ein Kreis, Erweiterung:

Kreissegment)� Allgemein (general) (Profil ändert Normalenrichtung)

� Anwendungen� 3D-Objekte aus 2D-Objekten erzeugen� 2 1/2D-CAD-Konstruktion

20



Hybride Modelle

� Verschiedene Repräsentationen in einem übergeordneten Modell� Bzgl. Methoden� Bzgl. Realisierung

� Theoretischer Vorteil� Mächtigere Funktionalitätsmenge� Optimale Dualität zwischen Repräsentation und Modellierungsmethode

� Praktische Probleme� Konvertierung zwischen den Modellen� Konsistenzerhaltung: Modifizierung in einer Repräsentation müssen in

anderen Repräsentationen nachgezogen werden



Hybride Modelle

21



Wichtige interaktive Technikenbeim Polygon Modelling

� Parametrisieren und Instanzieren von Objekten: Würfel, Kugel, ... , Quadriken

� Duplizieren, Spiegeln, Facetten unterteilen� Direct Point Manipulation: „Verschieben“

� Basis: Polygonales (oder Freiform-) Modell� Virtual Sculping: “Modellieren mit Ton”

� Direct Edge / Face Manipulation: � Translieren – Rotieren – Skalieren (– Scheren)

� Auch Sweeping� Extrusion (Extrudieren, Lofting) einer Fläche entlang eines Pfades

(z.B. Polyline) Default oft: in Richtung der Normalen� Rotation (lathe, revolve, surface oft revolution)

V



Spezielle Modellierungsfunktionenbeim Polygon Modelling

� Beveling: Anphasen “harter” Kanten oder Punkte

� Rounding: “Abrunden”

� Fillets (wie Bevels, oft durch “sweeping” eines 2D-Outlines entlang einer Innenkante)

V

22



Spezielle Modellierungsfunktionenbeim Polygon Modelling

� Purging (Simplification): Eliminierung “zu kleiner” Polygone, “zu vieler” Eckpunkte

� Aligning: “Verbinden zweier Flächen”� Fitting: Eliminieren kleiner Zwischenräume� Blending: Erzeugung einer Zwischenfläche beim verbinden zweier

Flächen

V



ModellierbeispielEinfacher Character mit Polygonen

Subdivide & bevel scale top down

Move vertices up scale down vertices extrude faces

23



Einfacher Character mit Polygonen

Extrude more & scale extrude down scale inner vertices

Extrude & scale smooth for test




24






Spezielle Technik; Subdivision

� Heute in vielen 3D Systemen (insbesondere Animationssystemen) enthalten; verschiedene Bezeichnungen:� 3D-MAX Mesh Smooth� Maya Smoothing� Softimage Rounding

� Idee ist einfach: Durch fortgesetzte Unterteilung eines polygonalen Modells

� B-spline patch (P. de Casteljau)

25



Subdivision Techniken

Man modeliert und animiert in Low-Res

Vor dem Rendern � Subdibvisions



Probleme

� Creases: Grobstruktur bleibt sichtbar erhalten! Besonders sichtbar in animierten Sequenzen

� Wenn Subdivison dynamisch beim Rendering durchgeführt wird: bubbling: Frage Abbruchkriterium?

26



Level of Detail und andere Speedup-Techniken

Je weiter ein Objekt von de virtuellen Kamera entfernt ist (vielleicht wird es nur noch auf 5x10 Pixel abgebildet), um so geringer darf auch sein geometrischer Detailreichtum sein.

Man kann verschiedene Abstraktionsgrade nutzen!



LODs

27



Level of Detail Umschalten während des Renderns; Entfernung Objekt – Kamera d:

� 0 < d <= r1� r1 < d <= r2� r2 < d

range-based LOD

Problembereiche:1. Erzeugen der LODs (Modellieren oder Simplification)2. Überblenden zwischen LODs3. LOD Management



Erzeugen der LODsdurch Modellieren

� Parametrische Flächen werden unterschiedlich stark zerlegt muss nicht statisch sein � Parametrische Fläche als RenderingPrimitiv

� Subdivision� Von Hand modelliert (anders abstrahiert!)

28



Erzeugen der LODsdurch Simplification (data reduction, decimation)

Häufigste Methode: edge collapse

Subset placement oder optimal placement (z.B. neuen Punkt („Mittelpunkt“) suchen)



Erzeugen der LODsdurch Simplification

Bad collapse:

29



Überblenden zwischen LODs

� Sprunghaftes Umschalten (popping) wirkt störend:

� Alpha Channel: Transparenz verändern

� Wenn Subdivision oder Simplification genutzt wurde, kann man auch (Geo-) Morphing nutzen

� Immer: Entfernungshysterese nutzen!



Andere zur Beschleunigung des Rendering häufig genutzte Primitive

Weniger Punkte �� Weniger Transformationen� Weniger Normalen� Weniger Klippen� Weniger Beleuchtungsrechnungen

Triangle Strips Triangle Fans

30



Pro und ConsModelling mit Polygonen

Pro Unterschiedliche Netzdichte möglich:hohe Polygonzahl nur dort, wo viele geometrische Details vorliegen

Pro einfach zu verstehen und zu kontrollierenCon Glatte Kurven + Flächen können praktisch nur mit sehr

viel Aufwand erstellt werden; insbesondere polygonale Konturlinien bleiben sichtbar!

Con Kurven sind nicht akkurat (CAD; Karosseriebau)Con Hoher Speicheraufwand Con kein „natürlicher“ Parameter fürs

Textur-Mapping und die Animation



Zwischen-Zusammenfassung

� Koordinatensysteme � Geometrisches Modellieren in 3D: Eine Übersicht � Die Basistechnik: Polygonale Repräsentationen� Spezielle Erweiterungen:

� Polygonnetze, LODs, Subdivision, …5. Parametrische Kurven und Flächen

(eine erste Einführung, die Ideen!)6. Zusammenfassung7. Spezielle Literatur8. Ausblick

31



Probleme mit Polygonalen Modellen

� Für „glatte“ kurvige Flächen benötigt man sehr viele Polygone� sehr große Datenmengen

� Konturen bleiben trotzdem „kantig“



Ein klein wenig Geschichte

Anwendungsursprung: Ab ca. 1958 Anwendungen im Automobil-Karosseriebau:

Freiformflächen, allgemein CAD

Auch wenn vieles in der Differentialgeometrie vorab entwickelt war.Zwei große Namen:

Pierre Bézier (Renault): parametrische Repräsentation auf der Basis der Bernstein-Polynome: System UNISURF

P. de Casteljau (Citroen) (nur als interne Berichte veröffentlicht)

32



Biparametrische Patches (1)

Grundlegende Idee: uraltes Verfahren aus der Gießereitechnik / Formenbau

In der Sandbox ist das bewegliche Formteil noch unveränderlich. Im digitalen Modell kann auch dieses während der Bewegung verändert werden

� Biparametrisches Patch



Biparametrische Patches (2)a) Gegeben: drei Randkurven AB,

BC, CD (hier als kubische Bezier-Kurven mit ihren Kontrollpolygonen)

b) Die Kurve BC wird entlang BA und CD verschoben. Die Form kann sich dabei ändern!

c) Während des Verschiebens verändern sich die Punkte p1 und p2 und erzeugen neue Linien EFGH und IJKL

d) Es entstehen die 16 Kontrollpunkte (A, B, ..., P) und damit 9 Vierecke, die ein bikubisches parametrisches Bezier-Patch definieren.

33



Parametrische KurvenBasen und Kontrollpunkte

Parametrische Kurven sind i.d.R. � (ganz rationale) Polynome� gebrochen rationale Polynome Nurbs

n-ten Grades (n: höchster auftretender Exponent), z.B.

In der CG werden ganz überwiegend kubische (also k=3) Repräsentationen genutzt:

kkupupuppu ++++= ...)( 2

210Q



Typen der Darstellung von Kurven (und Flächen)

� Exakte Darstellung� Jeder Punkt ist durch eine Formel definiert� Problem: Formel ist meist nicht bekannt oder zu komplex

� Interpolatorische Darstellung� Kurve ist durch Stützstellenbedingungen beschrieben � Kurve ist an den Stützstellen determiniert

� Approximative Darstellung� Kurve ist durch Stützstellenbedingungen beschrieben� Kurve ist an den Stützstellen nicht determiniert

34



Interpolation

� Interpolation mit Monomen� Gesucht sind die Koeffizienten eines Polynoms P(t) derart, daß

P(ti) = Pi für alle Stützpunkte Pi gilt� Für n+1 paarweise verschiedene Stützpunkte gibt es genau ein

Polynom vom Grad n, das die obige Bedingung erfüllt� Nachteil: Berechnung der Koeffizienten ist aufwendig� Nachteil: Änderung eines Stützpunktes bedingt Neuberechnung

aller Koeffizienten



Beispiel für Interpolation

� Interpolation mit Newton-Polynomen

� Rekursive Berechnung der Koeffizienten kj mittels der dividierten Differenzen

� Vorteil: Neu hinzugefügter Punkt bedeutet nur eine weitere Stufe in dem Differenzschema

)()()()( 110 −−⋅⋅−⋅−= ii tttttttn �

�=

⋅=n

jjj ktntP

0

)()(

35



� Eine Reihe weiterer Interpolationsschemata sind üblich (z.B. Lagrange Polynome, Tschebyscheff Polynome oder rationale Funktionen als Basisfunktionen)

� Unabhängig von der Methode hat Interpolation immer das Problem der Oszillation, insbesondere bei hohem Polynomgrad n

� Interpolation liefert schlechte Qualität in praktischen Anwendungen (Kurven sind nicht „glatt“ genug)



Oszillationsproblem bei Interpolation

� Beispiel:

Interpolationspolynom

“Erwarteter” Verlauf

36



Approximation

� Ziel: Vermeidung von Oszillationsproblemen� Abschwächung der geometrischen Bedingungen: Nicht alle

Stützpunkte liegen notwendigerweise auf der Kurve, also nicht allePunkte werden interpoliert

� Einführung anderer Bedingungen als Stützpunkte (z.B. Betrag und Richtung von Tangentenvektoren)

� Problem: Aussehen der Kurve ist allgemein aus den Randbedingungen schwieriger vorhersagbar, aber spezielle Polynome haben interessante Eigenschaften



Approximation mit Polynomenallgemeine Festlegungen

nkteKontrollpuionenBasisfunktubmit

ub

i

i

::)(

)((u)k

0i

i

i

p

pQ �=

=

37



Approximation mit Polynomen

� Grad n = 1: Polygonzug, unstetige Steigungen an den Eckpunkten� Grad n = 2:In 3D können nur planare Kurven erhalten werden (d.h.

Kurve liegt immer in einer Ebene)� Grad n = 3 (übliche Wahl)

Die vier Koeffizienten können z.B. durch Startpunkt, Endpunkt, Tangente am Startpunkt, Tangente am Endpunkt gegeben werden

� Grad n > 3:Rechenaufwendig, nur in speziellen Anwendungen benutzt

�=

=k

0i)((u) ubiipQ

pi Kontrollpunktebi(u) Basisfunktionen

Polynome vom Grad n



Approximation Matrixschreibweise

� Der dritte Faktor heißt Geometrievektor G, die pi sind geometrische Nebenbedingungen (z.B. Kontrollpunkte oder definieren Tangentenvektoren, etc.)

� Das Produkt aus U und M ergibt die Blendingfunktionen (diese gewichten die den Geometrievektor (die geometrischen Nebenbedingungen pi)

��

�

�

��

�

�

⋅⋅==

4

3

2

1

23 1] u u [u z(u)] y(u)[x(u)(u)

pppp

MQ

Parametervektor Basismatrix Geometrievektork=3 � 4x4 (Kontrollpunkte)

Basisfunktionen oder Blending Functions

V

38



Kubische Bézier Kurve n=3

33,3

23,2

23,1

33,0

3

0i3,

)(

)1(3)(

)1(3)(

)1()(

)((u)

uuB

uuuB

uuuB

uuB

mituBi

=

−=

−=

−=

=�=

ipQ

Bezier Basisfunktionen

•Beobachtungen: p0 hat dominierenden Einfluss für u < 0,1•Mit wachsendem u haben nimmt der Einfluss der andere Kontrollpunkte zu

•Mann nennt die Basis Funktionen auch Blending Functions



Beispiele für Kubische Bézier Kurven

Eine erste interessante Eigenschaft:Steigung der Kurve in P1 ist gegeben durch den Vektor P1-P2Entsprechendes gilt für P3, P4

39



Eine weitere übliche NotationMatrix Notation der Bezier Kurve

��

�

�

��

�

�

⋅

��

�

�

��

�

�

−−

−−

⋅===

4

3

2

1

23

0001003303631331

1] u u [u z(u)] y(u)[x(u)(u)

pppp

PUMQ CB

Multipliziert man die Basismatrix MB mit dem Parametervektor U so errechnen sich die Basisfunktionen (Blending Functions):

BUM=),,,( 3,33,23,13,0 BBBB

V



Zusammenfassung der Eigenschaften von Bézier Kurven und Flächen

� Der Polynomgrad eines Kurvensegmentes ist um Eins kleiner als die Anzahl der Punkte des Kontrollpolygons

� Der erste und letzte Punkt des Kontrollpolygons werden interpoliert

� Der Tangentenvektor am Anfang und Ende der Kurve haben die gleiche Richtung wie die erste resp. letzte Kante des Kontrollpolygons

� Die Kurve verläuft innerhalb der konvexen Hülle des Kontrollpolygons

� Die Kurve ist invariant gegenüber affinen Transformationen

40



Zusammenfassung Bézier Kurven und Flächen

� Zwei entscheidende Nachteile beschränken die Flexibilität:� Feste Kopplung zwischen Polygongrad und der Anzahl der

Kontrollpunkte� Änderungen der Kontrollpunkte wirken innerhalb des Bezier-Spans

(des Patches) global� anderen Basisfunktionen (Splines) und rationalen Darstellungen NURBs

� Historisch bedeutende Repräsentation aber: Bézier Kurven noch oft genutzt, insbesondere in 2D Anwendungen: Kontrolle der Endpunkteund der Tangenten

� Bézier Flächen durch Verlust der Freiheitsgrade beim Modellieren beschränkt einsetzbar

� Häufig als Render-Primitiv genutzt.



Spezielle Literatur

Joe Warren, Henrik Weimer:Subdivision Methods for Geometric Design –A Constructive Approach, Morgan Kaufmann, 2002

Jules Bloomenthal (Ed.):Introduction to Implicit SurfacesMorgan Kaufmann, 1997

Donald H. House, Dacvid E. Breen:Cloth Modeling and Animation, A K Peters, 2000

41



Spezielle Literatur (2)

� Foley, vanDam, Feiner, Hughes:Computer Graphics – Principles and Practice Kapitel 112nd Edition, Addison-Wesley, 1992

� Hoschek, Lasser:Grundlagen der geometrischen DatenverarbeitungTeubner Verlag, 1992

� David F. RogersAn Introduction to NurbsMorgan Kaufmann, 2001

� Watt, Watt:Advanced Animation and Rendering Techniques insb. Kapitel 3Addison-Wesley, 1992

� Aus Anwendersicht: George Maestridigital Character Animation 2, volume 1 – essential techniquesNew Rivers, 1999



Fragen und (hoffentlich) Antworten

42



Ausblick ... am nächsten Donnerstag

Geometrische Transformationen

... und, danke für Ihre Aufmerksamkeit!

Documents

Modul: B-CG Grundlagen der Computergraphik · 1 Hier wird Wissen Wirklichkeit Modul: B-CG Grundlagen der Computergraphik Geometrie-Repräsentationen Prof. Dr. Detlef Krömker Professur