1
Hier wird Wissen Wirklichkeit
Modul: B-CG Grundlagen der Computergraphik
V 02 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 – V-02- Geometrierepräsentationen
Rückblick: Bildrepräsentationen
• Merkmalsebene
• Abtastebene
• Reiz- & Aktionsebene
Grafik- undMerkmals-Primitive
Digitales Bild
optisch
beliebige Datenstruktur
1
2
3
4
Bildfunktion
Prof. Dr. Detlef KrömkerInstitut für Informatik
3 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
BeispielePolygonale Modellierung
Freiformflächen =(Tensorflächen,Polynomflächen, Parametrische Flächen)
Prozedurale Modellierung
( )
2
Prof. Dr. Detlef KrömkerInstitut für Informatik
4 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Ü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
Prof. Dr. Detlef KrömkerInstitut für Informatik
5 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
6 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
3
Prof. Dr. Detlef KrömkerInstitut für Informatik
7 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
8 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Geschichte der Geometrie (1)
Erste Ansätze schon in in den frühen Hochkulturen entwickelt, insbesondere zur Landvermessung, für astronomische Beobachtungen und in der Architektur: Winkel messen, Flächen- und Rauminhalte sowie Raumpunkte bestimmen.
Die Griechen machten die Geometrie zu einer Wissenschaft und benutzten sie 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
Prof. Dr. Detlef KrömkerInstitut für Informatik
9 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
4
Prof. Dr. Detlef KrömkerInstitut für Informatik
10 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
Prof. Dr. Detlef KrömkerInstitut für Informatik
11 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
Prof. Dr. Detlef KrömkerInstitut für Informatik
12 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
5
Prof. Dr. Detlef KrömkerInstitut für Informatik
13 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
14 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Weitere gebräuchliche Koordinatensysteme
‣ krummlinige orthogonale Koordinatensysteme: ‣ ebene Polarkoordinaten und Zylinderkoordinaten‣ räumliche und sphärische Polarkoordinaten (Kugelkoordinaten) ‣ Toruskoordinaten‣ ...
‣ Baryzentrische Koordinaten
Prof. Dr. Detlef KrömkerInstitut für Informatik
15 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 x1, ..., xn haben die baryzentrischen Koordinaten (1, 0, 0, ..., 0), (0, 1, 0, ..., 0), ..., (0, 0, 0, ..., 1).
xa ... xa p · )a ... (a nn11n1 ++=++
6
Prof. Dr. Detlef KrömkerInstitut für Informatik
16 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Baryzentrische Koordinaten – 2 Sätze
1. Baryzentrische Koordinaten sind nicht eindeutig: Für jedes von Null verschiedene b sind (b a1, ..., b an) ebenfalls baryzentrischeKoordinaten von p.
2. Falls die Koordinaten a1, ..., an alle positiv sind und sich zu 1 aufsummieren, d.h. a1 +...+ an = 1, 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.
Zusammengenommen: Die Bedingung in 2.: a1 +...+ an = 1 kann bei positiven Koordinaten durch eine geeignete Skalierung mit
immer erreicht werden.naab++=∑ ...1 1
Prof. Dr. Detlef KrömkerInstitut für Informatik
17 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Baryzentrische Koordinaten - Nutzung
Baryzentrische Koordinaten erscheinen auf den ersten Blick abstrakt und wenig intuitiv, aber sie können sehr nützlich sein:
In der Physik: 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.
In der CG: Zur Interpolation innerhalb von Dreiecken
Prof. Dr. Detlef KrömkerInstitut für Informatik
18 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Nutzung in der CG
)( a)( a a a )aa1(
oder a a agilt so 3,n und 1a ... a Wählen wir
a ... a a ... a
folgt a ... a · )a ... (a
3322
332232
33221
n1
n1
n1
n1n1
111
1
1
n1
n1
xxxxxpxxxp
xxxp
xxp
xxp
−+−+=++−−=
++===++
++++
=
++=++
x1
x2
x3
x 2- x
1
x3- x1
a 2=
0
a 2=
0,5
a 2=1
a 2=
-0,5
a3= 0,5
a3= 0
a3= -0,5
a3= 1
7
Prof. Dr. Detlef KrömkerInstitut für Informatik
19 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Spezielle Koordinatensysteme in der CG (1)
ObjektkoordinatenIntrinsisches Koordinatensystem eines ObjektsHierarchische ModellierungModellierungs -Transformation zu Weltkoordinaten
Weltkoordinaten (Koordinatensystem der Szene)Wurzel für die hierarchische ModellierungBezugspunkt für die KameraSicht-(Viewing-)Transformation zu Kamerakoordinaten
Kamerakoordinaten (Viewing-Koordinaten)Bezugssystem für die BeleuchtungsberechnungPerspektivische Transformation zu normalisierten
Projektionskoordinaten
Prof. Dr. Detlef KrömkerInstitut für Informatik
20 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 Window‣ Ursprung? RenderMan, X11: Oben links
OpenGL: Unten links‣ (Window-)Viewport-Transformation
‣ Anpassung der Seitenverhältnisse‣ Position innerhalb der Rasterkoordinaten
Raster - Koordinaten (Viewport)‣ 2D: Einheit in Pixel [0 .. xres-1, 0 .. yres-1]
Prof. Dr. Detlef KrömkerInstitut für Informatik
21 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 Modell (2D): = Zeichnungen)‣ Drahtgitter-Modell (3D)‣ Polygonale Modelle (Polyhedron-Modelle)‣ Freiformflächen-Modelle‣ CSG, Volumenmodelle, …‣ Softobjects, Prozedurale Modelle, ...
8
Prof. Dr. Detlef KrömkerInstitut für Informatik
22 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
ZeichnungenProblem 1: keine Körperbeschreibungen
unmögliche Objekte repräsentierbar
?
Prof. Dr. Detlef KrömkerInstitut für Informatik
23 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Zeichnungen und DrahtgittermodelleProblem 2: Mehrdeutigkeiten
Prof. Dr. Detlef KrömkerInstitut für Informatik
24 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
9
Prof. Dr. Detlef KrömkerInstitut für Informatik
25 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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?
Prof. Dr. Detlef KrömkerInstitut für Informatik
26 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 rrxxrrrr μλ ++=
Prof. Dr. Detlef KrömkerInstitut für Informatik
27 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Repräsentationsschemata für Körper
‣ Primitive Instancing
‣ Decomposition Models
‣ Constructive Models
‣ Boundary Models (Flächenmodelle)
‣ Sweeping
‣ u. v. a. m.
10
Prof. Dr. Detlef KrömkerInstitut für Informatik
28 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
29 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
30 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
11
Prof. Dr. Detlef KrömkerInstitut für Informatik
31 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
Prof. Dr. Detlef KrömkerInstitut für Informatik
32 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
33 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
12
Prof. Dr. Detlef KrömkerInstitut für Informatik
34 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
CSG Modellieren
Prof. Dr. Detlef KrömkerInstitut für Informatik
35 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Boundary Modelsdie wichtigste Repräsentation
‣ Flächenmodell‣ „verbessertes graphisches Modell“‣ Ursprung:
polyhedrales Modell‣ Boundary Datenstruktur
Drei Basisobjekttypen:‣ Face (Fläche),‣ Edge (Kante), ‣ Vertex (Ecke)
Prof. Dr. Detlef KrömkerInstitut für Informatik
36 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Boundary Models
‣ Schemata‣ Polygon-based‣ Vertex-based‣ Edge-based
13
Prof. Dr. Detlef KrömkerInstitut für Informatik
37 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
38 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
Prof. Dr. Detlef KrömkerInstitut für Informatik
39 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
SweepingBeispiele
14
Prof. Dr. Detlef KrömkerInstitut für Informatik
40 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
41 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
42 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Hybride Modelle
15
Prof. Dr. Detlef KrömkerInstitut für Informatik
43 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
44 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
45 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
16
Prof. Dr. Detlef KrömkerInstitut für Informatik
46 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
ModellierbeispielEinfacher Character mit Polygonen
Subdivide & bevel scale top down
Move vertices up scale down vertices extrude faces
Prof. Dr. Detlef KrömkerInstitut für Informatik
47 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Einfacher Character mit Polygonen
Extrude more & scale extrude down scale inner vertices
Extrude & scale smooth for test
Prof. Dr. Detlef KrömkerInstitut für Informatik
48 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Einfacher Character mit Polygonen
17
Prof. Dr. Detlef KrömkerInstitut für Informatik
49 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Einfacher Character mit Polygonen
Prof. Dr. Detlef KrömkerInstitut für Informatik
50 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
51 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Subdivision Techniken
Man modeliert und animiert in Low-Res
Vor dem Rendern Subdibvisions
18
Prof. Dr. Detlef KrömkerInstitut für Informatik
52 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Probleme
‣ Creases: Grobstruktur bleibt sichtbar erhalten! Besonders sichtbar in animierten Sequenzen
‣ Wenn Subdivison dynamisch beim Rendering durchgeführt wird: bubbling: Frage Abbruchkriterium?
Prof. Dr. Detlef KrömkerInstitut für Informatik
53 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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!
Prof. Dr. Detlef KrömkerInstitut für Informatik
54 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
LODs
19
Prof. Dr. Detlef KrömkerInstitut für Informatik
55 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Level of Detail Umschalten während des Renderns; Entfernung Objekt – Kamera d:
‣ 0 < d
20
Prof. Dr. Detlef KrömkerInstitut für Informatik
58 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Erzeugen der LODsdurch Simplification
Bad collapse:
Prof. Dr. Detlef KrömkerInstitut für Informatik
59 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Ü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!
Prof. Dr. Detlef KrömkerInstitut für Informatik
60 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Andere zur Beschleunigung des Rendering häufig genutzte Primitive
Weniger Punkte ‣ Weniger Transformationen‣ Weniger Normalen‣ Weniger Klippen‣ Weniger Beleuchtungsrechnungen
Triangle Strips Triangle Fans
21
Prof. Dr. Detlef KrömkerInstitut für Informatik
61 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
62 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Zwischen-Zusammenfassung
Koordinatensysteme Geometrisches Modellieren in 3D: Eine Übersicht Die Basistechnik: Polygonale RepräsentationenSpezielle Erweiterungen:
Polygonnetze, LODs, Subdivision, …5. Parametrische Kurven und Flächen
(eine erste Einführung, die Ideen!)6. Zusammenfassung7. Spezielle Literatur8. Ausblick
Prof. Dr. Detlef KrömkerInstitut für Informatik
63 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Probleme mit Polygonalen Modellen
‣ Für „glatte“ kurvige Flächen benötigt man sehr viele Polygone
sehr große Datenmengen
‣ Konturen bleiben trotzdem „kantig“
22
Prof. Dr. Detlef KrömkerInstitut für Informatik
64 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
65 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
66 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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.
23
Prof. Dr. Detlef KrömkerInstitut für Informatik
67 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 ++++= ...)(
2210Q
Prof. Dr. Detlef KrömkerInstitut für Informatik
68 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
69 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
24
Prof. Dr. Detlef KrömkerInstitut für Informatik
70 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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 K
∑=
⋅=n
jjj ktntP
0)()(
Prof. Dr. Detlef KrömkerInstitut für Informatik
71 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
‣ 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)
Prof. Dr. Detlef KrömkerInstitut für Informatik
72 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Oszillationsproblem bei Interpolation
‣ Beispiel:
Interpolationspolynom
“Erwarteter” Verlauf
25
Prof. Dr. Detlef KrömkerInstitut für Informatik
73 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
74 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Approximation mit Polynomenallgemeine Festlegungen
nkteKontrollpuionenBasisfunktubmit
ub
i
i
::)(
)((u)k
0i
i
i
p
pQ ∑=
=
Prof. Dr. Detlef KrömkerInstitut für Informatik
75 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
26
Prof. Dr. Detlef KrömkerInstitut für Informatik
76 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
77 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
78 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
27
Prof. Dr. Detlef KrömkerInstitut für Informatik
79 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
80 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
81 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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) globalanderen 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.
28
Prof. Dr. Detlef KrömkerInstitut für Informatik
82 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
83 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
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
Prof. Dr. Detlef KrömkerInstitut für Informatik
84 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Fragen und (hoffentlich) Antworten
29
Prof. Dr. Detlef KrömkerInstitut für Informatik
85 Hier wird Wissen WirklichkeitB-CG – V-02- Geometrierepräsentationen
Ausblick ... am nächsten Donnerstag
Geometrische Transformationen
... und, danke für Ihre Aufmerksamkeit!