1 Einleitung 15
1.1 Ein kleiner Überblick 15
1.1.1 Bildverarbeitung 18
1.1.2 Die Interaktion von Mensch und Computer 19
1.2 Unser Programm 19

2 Bilddarstellung 21
2.1 Das RGB-Farbmodell 21
2.2 Direkte Kodierung 23
2.3 Nachschlagetabellen 24
2.4 Der Monitor 25
2.4.1 Farbanzeige 26
2.5 Drucker 27
2.5.1 Halbtöne 27
2.5.2 Näherungslösungen für Halbtöne 27
2.5.3 Dithering 29
2.5.4 Fehlerdiffusion 29
2.6 Bilddateien 30
2.7 Setzen des Farbattributs eines Pixels 31
2.8 Beispiel: Bildliche Darstellung der Mandelbrot-Menge 32
2.8.1 Julia-Mengen 34
2.9 Aufgaben mit Lösungen 35
2.10 Weitere Aufgaben 40

3 Scan Conversion 43
3.1 Scan Conversion eines Punkts 43
3.2 Scan Conversion einer Linie 44
3.2.1 Unmittelbare Anwendung der Geradengleichung 45
3.2.2 Der DDA-Algorithmus 45
3.2.3 Der Linienalgorithmus von Bresenham 45
3.3 Scan Conversion eines Kreises 48
3.3.1 Die Definition eines Kreises 48
3.3.2 Der Kreisalgorithmus von Bresenham 50
3.3.3 Der Mittenpunktsalgorithmus für Kreise 52
3.3.4 Kreise mit willkürlichen Mittelpunkten 54
3.4 Scan Conversion einer Ellipse 54
3.4.1 Die Polynomdefinition einer Ellipse 54
3.4.2 Die trigonometrische Definition einer Ellipse 55
3.4.3 Achsrotation einer Ellipse 56
3.4.4 Der Mittenpunktsalgorithmus für Ellipsen 57
3.5 Scan Conversion von Bögen und Sektoren 60
3.5.1 Bögen 60
3.5.2 Sektoren 61
3.6 Scan Conversion eines Rechtecks 62
3.7 Füllen von Bereichen 62
3.7.1 Vier oder acht Verbindungspunkte? 62
3.7.2 Der Boundary-Fill-Algorithmus 64
3.7.3 Der Flood-Fill-Algorithmus 64
3.7.4 Der Abtastzeilenalgorithmus 64
3.8 Scan Conversion eines Zeichens 66
3.8.1 Bitmap-Fonts 66
3.8.2 Outline-Fonts 67
3.9 Anti-Aliasing 68
3.9.1 Treppenstufen 68
3.9.2 Ungleichmäßige Helligkeit 68
3.9.3 Das Gartenzaun-Problem 68
3.9.4 Anti-Aliasing 69
3.9.5 Vor- und Nach-Filterung 70
3.9.6 Flächenabtastung 70
3.9.7 Überabtastung 71
3.9.8 Lowpass-Filter 72
3.9.9 Pixel Phasing 72
3.10 Beispiel: Rekursiv definierte Zeichnungen 72
3.10.1 DieC-Kurve 73
3.10.2 Die Koch-Kurve 74
3.10.3 Das Sierpinski-Dreieck 74
3.11 Aufgaben mit Lösungen 75
3.12 Weitere Aufgaben 89

4 Zweidimensionale Transformationen 91
4.1 Geometrische Transformationen 91
4.1.1 Translation 92
4.1.2 Rotation um den Ursprung 92
4.1.3 Skalierung relativ zum Ursprung 93
4.1.4 Spiegelung an einer Achse 93
4.1.5 Inverse geometrische Transformationen 94
4.2 Koordinatentransformationen 94
4.2.1 Translation 94
4.2.2 Rotation um den Ursprung 95
4.2.3 Skalierung relativ zum Ursprung 95
4.2.4 Spiegelung an einer Achse 96
4.2.5 Inverse Koordinatentransformationen 96
4.3 Verkettete Transformationen 96
4.3.1 Matrixbeschreibung der Grundtransformationen 97
4.3.2 Verkettung von Matrizen 98
4.3.3 Unterschiedliche Matrizenschreibweisen 99
4.4 Instanztransformationen 100
4.4.1 Verschachtelte Instanzen und Strukturen mit mehreren Ebenen 100
4.5 Aufgaben mit Lösungen 103
4.6 Weitere Aufgaben 115

5. Ansichten und Clipping im zweidimensionalen Raum 117
5.1 Abbildung des Fensters auf den Viewport 118
5.2 Zuschneiden von Punkten 119
5.3 Zuschneiden von Linien 119
5.3.1 Der Cohen-Sutherland-Algorithmus 120
5.3.2 Mittelpunktunterteilung 122
5.3.3 Der Liang-Barsky-Algorithmus 123
5.4 Zuschneiden von Polygonen 124
5.4.1 Clippingfenster für konvexe Polygone 125
5.4.2 Der Sutherland-Hodgman-Algorithmus 126
5.4.3 DerWeiler-Atherton-Algorithmus 127
5.5 Beispiel: Eine 2D-Grafikpipeline 128
5.5.1 Schwenks und Zoom 130
5.5.2 Doppelte Pufferung 130
5.5.3 Animation in der Nachschlagetabelle 130
5.6 Aufgaben mit Lösungen 131
5.7 Weitere Aufgaben 145

6 Dreidimensionale Transformationen 147
6.1 Geometrische Transformationen 147
6.1.1 Translation 147
6.1.2 Skalierung 148
6.1.3 Rotation 148
6.2 Koordinatentransformationen 150
6.3 Verkettete Transformationen 151
6.4 Instanztransformationen 152
6.5 Aufgaben mit Lösungen 152
6.6 Weitere Aufgaben 162

7 Mathematische Grundlagen der Projektion 163
7.1 Einteilung der Projektionsarten 163
7.2 Perspektivische Projektion 164
7.2.1 Grundprinzipien 164
7.2.2 Mathematische Beschreibung einer perspektivischen Projektion 164
7.2.3 Perspektivische Verzerrung 166
7.3 Parallelprojektion 168
7.3.1 Grundprinzipien 168
7.3.2 Mathematische Beschreibung einer Parallelprojektion 169
7.4 Aufgaben mit Lösungen 170
7.5 Weitere Aufgaben 192

8 Ansichten und Clipping im dreidimensionalen Raum 193
8.1 Dreidimensionale Ansichten 193
8.1.1 Festlegen der Ansichtsebene 193
8.1.2 Ansichtskoordinaten 193
8.1.3 Festlegen des Ansichtsvolumens 196
8.2 Clipping 197
8.2.1 Zuschneiden auf ein endliches Ansichtsvolumen 197
8.2.2 Clippingverfahren 198
8.2.3 Clippingalgorithmen 200
8.3 Ansichtstransformationen 201
8.3.1 Normalisierte Ansichtskoordinaten 201
8.3.2 Die Bildschirm-Projektionsebene 201
8.3.3 Konstruieren einer dreidimensionalen Ansicht 202
8.4 Beispiel: Eine 3D-Grafikpipeline 202
8.5 Aufgaben mit Lösungen 204
8.6 Weitere Aufgaben 220

9 Geometrische Darstellung 221
9.1 Einfache geometrische Formen 221
9.1.1 Punkte und Strecken 221
9.1.2 Polygonzüge 221
9.1.3 Polygone 221
9.2 Drahtmodelle 222
9.2.1 Darstellen eines Polygonnetz-Modells 222
9.2.2 Der Polyeder 223
9.2.3 Vor-und Nachteile von Drahtmodellen 223
9.3 Gekrümmte Oberflächen 223
9.4 Kurvenentwurf 223
9.5 Polynomiale Basisfunktionen 224
9.5.1 Lagrange'sche Polynome vom Grad n 225
9.5.2 Hermite'sche Polynome 3. Ordnung 225
9.5.3 B-Splines 225
9.5.4 Bernstein'sche Polynome 226
9.6 Das Problem der Interpolation 227
9.6.1 Die Interpolationslösung für Lagrange'sche Polynome 227
9.6.2 Die Interpolationslösung für Hermite'sche Polynome 3. Ordnung 227
9.6.3 Interpolation von Splines 227
9.7 Das Problem der Näherung 229
9.7.1 Die Bezier-Bernstein-Näherung 229
9.7.2 Eigenschaften der Bezier-Bernstein-Näherung 230
9.7.3 Die Bezier-Näherung mit B-Splines 230
9.7.4 Geschlossene Kurven 231
9.7.5 Eigenschaften der Bezier-Näherung mit B-Splines 231
9.8 Entwurf von gekrümmten Oberflächen 232
9.8.1 Hilfsnetze 232
9.8.2 Interpolieren von Teilflächen 233
9.9 Transformieren von Kurven und Oberflächen 235
9.10 Oberflächen zweiter Ordnung 235
9.10.1 Kugel 235
9.10.2 Ellipsoid 236
9.10.3 Einschaliges Hyperboloid 236
9.10.4 Zweischaliges Hyperboloid 236
9.10.5 Elliptischer Zylinder 237
9.10.6 Elliptisches Paraboloid 237
9.10.7 Hyperbolisches Paraboloid 238
9.10.8 Elliptischer Konus 239
9.11 Beispiel: Geländesimulation 239
9.11.1 Mittelpunktsverschiebung 239
9.11.2 Brown'sche Verteilung von Scheiben 240
9.12 Aufgaben mit Lösungen 242
9.13 Weitere Aufgaben 247

10 Verdeckte Oberflächen 249
10.1 Tiefenvergleich 249
10.2 Der Z-Puffer-Algorithmus 251
10.3 Entfernen von Rückseiten 252
10.4 Der Maler-Algorithmus 253
10.4.1 Zuweisen von Prioritäten 253
10.4.2 Verdeckt Polygon P das Polygon Q? 254
10.4.3 Der Algorithmus 256
10.5 Der Abtastzeilenalgorithmus (Scan Line-Algorithmus) 256
10.5.1 y-Abtastung 257
10.5.2 x-Abtastung 257
10.5.3 Arten der Kohärenz 258
10.5.4 Ein Abtastzeilenalgorithmus 259
10.6 Der Unterteilungsalgorithmus 260
10.6.1 Entfernen von verdeckten Polygonen 262
10.6.2 Der Unterteilungsalgorithmus 262
10.7 Entfernen von verdeckten Linien 263
10.8 Rendern von mathematischen Oberflächen 263
10.8.1 Die Umfangsmethode zum Rendern von Oberflächen 264
10.8.2 Die Sichtbarkeitsprüfung 265
10.8.3 Der Wright-Algorithmus zum Rendern von mathematischen Oberflächen 266
10.9 Aufgaben mit Lösungen 266
10.10 Weitere Aufgaben 286

11 Färb- und Schattierungsmodelle 289
11. Licht und Farbe 289
11.1.1 Grundeigenschaften des Lichts 289
11.1.2 Die Drei-Farben-Theorie 291
11.1.3 Das ClE-XYZ-Farbmodell 292
11.1.4 Das ClE-Farbwertdiagramm 292
11.1.5 Abbildung von Farbpaletten 293
11.1.6 Das NTSC-YIQ-Farbmodell 294
11.2 Das Phong-Modell 295
11.3 Interpolierende Schattierungsmethoden 297
11.3.1 Konstante Schattierung 298
11.3.2 Gouraud-Schattierung 298
11.3.3 Phong-Schattierung 300
11.4 Textur 300
11.4.l Projektion von Texturen 300
11.4.2 Textur-Mapping 301
11.4.3 Festkörpertexturen 302
11.5 Aufgaben mit Lösungen 305
11.6 Weitere Aufgaben 314

12 RayTracing 315
12.1 Die Lochkamera 315
12.2 Ein rekursiver Ray Tracer 316
12.3 Parametrische Vektordarstellung eines Strahls 319
12.4 Schnittpunkte von Strahlen und Oberflächen 320
12.4.1 Schnittpunkte mit der Ebene des Koordinatensystems 320
12.4.2 Schnittpunkte mit beliebigen Ebenen 321
12.4.3 Schnittpunkte mit Kugeln 322
12.4.4 Schnittpunkte mit allgemeinen impliziten Oberflächen 323
12.5 Effiziente Ausführung 323
12.5.1 Adaptive Tiefensteuerung 323
12.5.2 Die Ausdehnung von Hüllkörpern 324
12.5.3 Die Hierarchie der Hüllkörper 324
12.5.4 Räumliche Kohärenz und Unterteilung 325
12.6 Anti-Aliasing 325
12.6.1 Überabtastung 326
12.6.2 Adaptive Uberabtastung 326
12.6.3 Stochastische Überabtastung 326
12.7 Weitere visuelle Effekte 326
12.7.1 Umgebungs-Mapping 326
12.7.2 Weiche Schatten 327
12.7.3 Unscharfe Reflexionen 327
12.7.4 Durchscheinende Oberflächen 328
12.7.5 Bewegungsunschärfe 328
12.8 Aufgaben mit Lösungen 328
12.9 Weitere Aufgaben 339

A1 Mathematische Grundlagen für zweidimensionale Computergrafik 341
A1.1 Das zweidimensionale kartesische Koordinatensystem 341
A1.1.1 Abstandsmessung im kartesischen System 342
A1.1.2 Winkelmessung im kartesischen System 342
A1.1.3 Geradenbeschreibung im kartesischen System 343
A1.1.4 Kurven und parametrische Gleichungen 344
A1.2 Das Polarkoordinatensystem 345
A1.2.1 Wechseln des Koordinatensystems 346
A1.3 Vektoren 347
A1.3.1 Eigenschaften von Vektoren 347
A1.3.2 Koordinatenvektoren und Komponent 348
A1.3.3 Das Punktprodukt 349
A1.4 Matrizen 350
A1.4.1 Arithmetische Eigenschaften von Matrizen 350
A1.4.2 Matrixinversion und Einheitsmatrix 351
A1.5 Funktionen und Transformationen 352
A1.5.1 Funktionsgraphen 353
A1.5.2 Zusammensetzen von Funktionen 353
A1.5.3 Inverse einer Funktion 354
A1.6 Aufgaben mit Lösungen 354

A2 Mathematische Grundlagen für dreidimensionale Computergrafik 371
A2.1 Dreidimensionale kartesische Koordinaten 371
A2.1.1 Orientierung 371
A2.1.2 Die Rechte-Hand-Regel 371
A2.1.3 Kartesische Koordinaten von Punkten im dreidimensionalen Raum 372
A2.1.4 Die Abstandsformel 373
A2.2 Kurven und Oberflächen in drei Dimensionen 373
A2.2.1 Kurven 373
A2.2.2 Oberflächen 374
A2.3 Dreidimensionale Vektoren 377
A2.3.1 Das Punkt- und das Kreuzprodukt 378
A2.3.2 Die Vektorgleichung einer Geraden 379
A2.3.3 Die Vektorgleichung einer Ebene 380
A2.4 Homogene Koordinaten 382
A2.4.1 Die zweidimensionale projektive Ebene 382
A2.4.2 Homogene Koordinaten von Punkten und Geraden der projektiven Ebene 382
A2.4.3 Das Verhältnis von homogenen und kartesischen Koordinaten 383
A2.4.4 Homogene Koordinaten in der dreidimensionalen projektiven Ebene 384
A2.5 Aufgaben mit Lösungen 384

L Lösungen zu den Aufgaben 399

Index 429