Vorwort 13

1 Mathematische Grundlagen 19
1.1 Punkte im dreidimensionalen Raum 19
1.2 Vektoren 21
1.2.1 Die Länge eines Vektors 23
1.2.2 Operationen mit Vektoren 25
1.2.3 Der Ortsvektor eines Punktes 31
1.3 Geraden 32
1.4 Ebenen 35
1.4.1 Die Punktrichtungsgleichung der Ebene 36
1.4.2 Die Normalenform der Ebene 39
1.4.3 Die Parameterform der Ebene 40
1.5 Trigonometrische Funktionen 41
1.5.1 Inverse trigonometrische Funktionen 43
1.6 Zuordnungen 44
1.6.1 Proportionale Zuordnungen 44
1.6.2 Antiproportionale Zuordnungen 46
1.6.3 Beliebige lineare Zuordnungen 47
1.6.4 Sinus- und Kosinuswerte am beliebigen rechtwinkligen Dreieck 50
1.6.5 Die Einteilung in Bogenmaß 53
1.7 Rotation im dreidimensionalen Raum 55

2 Einführung in die Grafikprogrammierung 59
2.1 Grundarchitektur der Grafikkarte 60
2.1.1 Auflösung und Farbtiefe 60
2.1.2 Speicherplatzanspruch eines Pixels 61
2.2 Der Videospeicher 62
2.3 Die Position eines Pixels 63
2.3.1 Der Anfangsoffset einer Pixelzeile 65
2.3.2 Der Offset eines beliebigen Pixels 67
2.4 Die 8 Bit Palette 68
2.5 Praktische Darstellung der Farbpalette 69
2.6 Aufbau eigener Algorithmen 72
2.7 Zufallszahlen 73
2.7.1 Die Obergrenze von Zufallszahlen 74
2.7.2 Praktischer Einsatz von Zufallszahlen 74
2.7.3 Die Untergrenze von Zufallszahlen 77
2.7.4 Praktische Einstellung der Untergrenze von Zufallszahlen 78
2.8 Passive Wiederholungsanweisungen 83
2.8.1 Praktischer Einsatz passiver Wiederholungsanweisungen 84
2.9 Horizontale und vertikale Geraden 86
2.9.1 Darstellung horizontaler Geraden 86
2.9.2 Darstellung vertikaler Geraden 88
2.9.3 Gemeinsame Visualisierung horizontal und vertikal verlaufender Geraden 89
2.9.4 Praktische Darstellung horizontal und vertikal verlaufender Linien 92
2.10 Initialisierung des Zufallszahlengenerators 95
2.11 Bresenhams Algorithmus zur Darstellung beliebig verlaufender Geraden 96
2.11.1 Langsam steigende Geraden 97
2.11.2 Automatische Darstellung langsam steigender Geraden 100
2.11.3 Schnell steigende Geraden 105
2.11.4 Praktische Implementierung von Bresenhams Linienalgorithmus 106
2.11.5 Ausnahmebehandlung 108
2.11.6 Praktische Darstellung beliebig verlaufender Linien 109

3 Einführung in die 3D-Programmierung 113
3.1 Zweidimensionale Figuren 113
3.1.1 Definition zweidimensionaler Figuren 114
3.1.2 Verwaltung zweidimensionaler Figuren 117
3.1.3 Praktische Darstellung zweidimensionaler Figuren 119
3.2 Die Projektion 123
3.2.1 Die Inversion der y-Koordinaten 126
3.2.2 Verlagerung des Ursprungs in die Mitte des Bildschirms 127
3.2.3 Der Viewport 128
3.2.4 Verwaltung dreidimensionaler Polygone 130
3.2.5 Praktische Darstellung von Polygonen mit dreidimensionalen Koordinaten 134
3.2.6 Die Variation der Projektionskonstanten 138
3.3 Matrizen 140
3.3.1 Transformation 141
3.3.2 Die Rotationsmatrix 144
3.3.3 Die Skaliermatrix 147
3.3.4 Matrizenmultiplikation 150
3.3.5 Verwaltung von Matrizen 154
3.3.6 Praktischer Einsatz von Matrizen 163
3.3.7 Fehlerbehandlung 168
3.4 Double Buffering 170
3.4.1 Das Problem der direkten Beschriftung des Videospeichers 174
3.4.2 Flimmerfreie Animation 178
3.4.3 Das Problem der hohen Unterscheidbarkeit aufeinanderfolgender Frames 182
3.5 Die Rotation 184
3.5.1 Rotation um die Koordinatenachsen der dreidimensionalen Welt 187
3.5.2 Die eigenen Achsen eines Gegenstands 192
3.5.3 Rotation eines Gegenstands um seine eigenen Achsen 194
3.5.4 Rotation um einen beliebigen Punkt 201
3.6 Der Einsatz variabler Matrizen 207
3.6.1 Aufbau variabler Matrizen 213
3.6.2 Praktischer Einsatz variabler Matrizen 214
3.6.3 Vor- und Nachteile beider Matrixtypen 217
3.7 Skalierung 219
3.7.1 Die Versetzung in Richtung des Ursprungs 223
3.7.2 Praktische Unterbindung der skalierungsbedingten Translation 224
3.7.3 Ungleichmäßige Skalierung 226
3.7.4 Iteration Counting 227
3.7.5 Praktische Umsetzung der ungleichmäßigen Skalierung 228
3.7.6 Fehlerbehandlung 232
3.7.7 Die Illusion der Tiefenverschiebung 233
3.7.8 Praktische Erzeugung der Illusion der Tiefenverschiebung 235

4 Polygonbasierende dreidimensionale Figuren 241
4.1 Rasterization 244
4.1.1 Die Kategorie einer Polygonseite 245
4.1.2 Anfang und Ende der Rasterzeilen 248
4.1.3 Lineare Interpolation – Der Zuordnungsansatz 249
4.1.4 Geschwindigkeit vs. Genauigkeit der Darstellung 251
4.1.5 Möglichkeiten der linearen Interpolation 252
4.1.6 Praktische Ermittlung der Endpunkte der Rasterzeilen 253
4.1.7 Bestimmung der Kategorie einer Polygonseite 254
4.1.8 Der Rasterizationsalgorithmus 255
4.1.9 Ausnahmebehandlung 259
4.1.10 Darstellung konkaver Polygone 260
4.1.11 Praktische Darstellung gefüllter Polygone 262
4.1.12 Das Problem der Nummerierung entgegen dem Urzeigersinn 267
4.1.13 Darstellung entgegen dem Uhrzeigersinn nummerierter Polygone 269
4.1.14 Praktische Visualisierung beliebig nummerierter, konvexer Polygone 272
4.2 Polygonbasierende dreidimensionale Figuren 275
4.2.1 Definition dreidimensionaler Figuren 275
4.2.2 Benutzerdefinierte Definition von Polygonen 276
4.2.3 Der Mittelpunkt eines Polyeders 277
4.2.4 Speicherung dreidimensionaler Figuren 278
4.2.5 Verwaltung dreidimensionaler Figuren 280
4.2.6 Der Einsatz von Polygonen als Bestandteil von Polyeder 285
4.2.7 Das ASCII-Format 288
4.2.8 Praktische Darstellung von Polyeder 291
4.3 Visual Surface Determination 299
4.3.1 Die Vorder- und Rückseite von Polygonen 300
4.3.2 Automatische Erkennung nicht sichtbarer Polygone 302
4.3.3 Fehlerbehandlung 304
4.4 Das Z-Buffer Algorithmus 305
4.4.1 Komplexe dreidimensionale Figuren 305
4.4.2 Grundidee des Z–Buffer-Algorithmus 308
4.4.3 Speichergarstellung der dreidimensionalen z-Koordinaten 309
4.4.4 Funktionsweise des Z-Buffer-Algorithmus 311
4.4.5 Mathematische Grundlage des Z-Buffer-Algorithmus 313
4.4.6 Der Einsatz des Z-Buffers während der Rasterization 317
4.4.7 Bestimmung der z-Koordinaten entlang der Rasterzeilen 321
4.4.8 Das Löschen des Z-Buffers 324
4.4.9 Praktische Implementierung des Z-Buffer-Algorithmus 325
4.4.10 Darstellung offener Körper 333
4.4.11 Z-Buffer vs. Visual-Surface-Determination-Algorithmus 335
4.4.12 Grundidee des Clear-Reduction-Algorithmus 337
4.4.13 Funktionsweise des Clear-Reduction-Algorithmus 338
4.4.14 Einordnung des Clear-Reduction-Algorithmus innerhalb des Visualisierungsprozesses 339
4.4.15 Clear-Reduction-Algorithmus und das Zurücksetzen des Z-Buffers 342
4.4.16 Praktischer Einsatz des Clear-Reduction-Algorithmus 344
4.5 Polygon-Clipping 348
4.5.1 Grundlagen des Polygon-Clippings 350
4.5.2 Mathematische Grundlagen des Pre-Projection-Clippings 351
4.5.3 Mathematische Grundlagen des Post-Projection-Clipping 355
4.5.4 Der Sutherland-and-Hodgman-Polygon-Clipping-Algorithmus 360
4.5.5 Praktische Darstellung beliebiger, mathematisch definierter Polygone 373
4.5.6 Benutzerdefinierte Rotationsebene für die Drehung um einen beliebigen Punkt 384

5 Unterstützung von Eingabegeräten 395
5.1 Verwaltung der Tastatur 395
5.1.1 Steuerung von Anwendungen in Multitasking-Betriebssystemen 395
5.1.2 Indirekte Verarbeitung von Benutzereingaben 399
5.1.3 Zusammenhang zwischen Auflösung und Projektionskonstante 404
5.1.4 Das Problem der flachen Objektkopien 406
5.1.5 Vor- und Nachteile der Verwendung eventbasierender Benutzereingaben 408
5.1.6 Direkte Verarbeitung von Benutzereingaben 409
5.2 Verwaltung der Maus 414
5.2.1 Die Position des Mauszeigers 415
5.2.2 Abfrage der Cursorposition 416
5.2.3 Abfrage des Zustands der Maustasten 418
5.2.4 Praktische Verwaltung der Maus 420
5.2.5 Praktische Verarbeitung von Mauseingaben 424

6 Einfache Polygonschattierung 429
6.1 Mathematische Ansätze zur Simulation natürlicher Farbwahrnehmung 430
6.1.1 Das RGB-Farbmodell 430
6.1.2 Das CMY-Farbmodell 438
6.1.3 Das HSV-Farbmodell 440
6.1.4 Beleuchtungsmodelle 444
6.2 Flat Shading 448
6.2.1 Intensität der Polygonfarbe 449
6.2.2 Mathematische Grundlagen des Flat-Shading-Algorithmus 451
6.2.3 Das Umgebungslicht 456
6.2.4 Implementierung des Flat-Shading-Algorithmus 458
6.3 Gouraud Shading 479
6.3.1 Der Normalenvektor eines Punkts 480
6.3.2 Farbinterpolation 485
6.3.3 Polygon Clipping unter Berücksichtigung von Farbinformationen 491
6.3.4 Rotation der Vektornormalen dreidimensionaler Vertices 494
6.3.5 Praktischer Einsatz des Gouraud-Shading-Algorithmus 495
6.3.6 Unterstützung mehrerer Primärfarben 510
6.3.7 Möglichkeiten des Einsatzes mehrerer Farbpaletten 524
6.4 Phong Shading 526
6.4.1 Die Vektornormale eines Pixels 528
6.4.2 Anpassung der Vektornormalen im Laufe des Polygon Clipping 534
6.4.3 Praktischer Einsatz des Phong-Shading-Algorithmus 537
6.5 Metal Shading 539
6.5.1 Exponentialinterpolation 540
6.5.2 Praktischer Einsatz des Metal-Shading-Algorithmus 549
6.5.3 Implementierung in die Hardware 550
6.5.4 Metal Shading unter Verwendung einer alternativen Farbgebung 554
6.6 Farbverläufe n-ten Grades 555
6.6.1 Anwendungsgebiete für Farbverläufe höheren Grades 556
6.6.2 Praktischer Einsatz von Farbverläufen n-ten Grades 557
6.732-Bit-Farbmodi 562
6.7.1 Verwaltung von Pixel in den 32-Bit-Farbmodi 565
6.7.232-Bit-Darstellung von Drahtgittermodellen 566
6.7.332-Bit-Gouraud-Shading 573
6.816-Bit-Farbmodi 584
6.8.116-Bit-Metal-Shading 587
6.8.28-Bit- vs. 16-Bit-Farbmodus 590

7 Bitmaps 593
7.1 Verwaltung von Bitmaps 594
7.1.1 Der Umgang mit 8-Bit-Bitmaps 595
7.2 Das 8-Bit-BMP-Dateiformat 598
7.2.1 Das Binärformat 598
7.2.2 Die Struktur von 8-Bit-BMP-Dateien 601
7.2.3 Praktische Darstellung von 8-Bit-Bitmaps 608
7.3 Externe Manipulation von Bitmaps 613
7.3.1 Grundlagen der externen Manipulation von Bitmaps 614
7.3.2 Praktische Darstellung von Linien innerhalb von Bitmaps 616
7.3.3 Background Buffering 621
7.3.4 Elementare Bitmaprotation 623
7.4 Verwaltung von 32-Bit-Bitmaps 629
7.4.1 Die Struktur von 24-Bit-BMP-Dateien 630
7.4.2 Praktische Darstellung von 32-Bit-Bitmaps 632
7.5 Partielle Darstellung von Bitmaps 633
7.5.1 Visualisierung rechteckiger Teilbereiche von Bitmaps 634
7.5.2 Einfache Transparenzeffekte 640
7.5.3 Zweidimensionale Umgebungen 643
7.5.4 Bitmap Clipping 646
7.5.5 Verwaltung zweidimensionaler Gegenstände 654
7.5.6 Praktische Visualisierung zweidimensionaler Gegenstände 657
7.6 Semitransparenzeffekte 666
7.6.1 Grundidee der Generierung semitransparenter Darstellungen 666
7.6.2 Mathematische Grundlagen der Generierung semitransparenter Darstellungen 668
7.6.3 Praktische Generierung semitransparenter Darstellungen 669

8 Texture Mapping 675
8.1 Linear Texture Mapping 676
8.1.1 Mathematische Grundlage des Linear-Texture-Mapping-Algorithmus 679
8.1.2 Implementierung des Linear-Texture-Mapping-Algorithmus 682
8.1.3 Praktischer Einsatz des Texture-Mapping-Algorithmus 697
8.1.4 Texturauswahl 700
8.1.5 Fehlerbehebung nach dem High-Level-, Low-Level-Prinzip 704
8.2 Perspective Texture Mapping 708
8.2.1 Grundlagen des Perspective-Texture-Mapping-Algorithmus 709
8.2.2 Das Problem der inversen z-Koordinaten 710
8.2.3 Praktischer Einsatz des Perspective-Texture-Mapping-Algorithmus 714
8.3 Höhere Genauigkeit durch den Einsatz des inversen Z-Buffer-Algorithmus 717
8.3.1 Simple Depth Shading 717
8.3.2 Praktischer Einsatz des Depth-Shading-Algorithmus 719
8.3.3Z-Buffer-Algorithmus unter Verwendung inverser z-Koordinaten 721
8.4 Multitextureffekte 729
8.4.1 Statische Multitextureffekte 730
8.4.2 Dynamische Multitextureffekte 737
8.4.3 MIP Mapping 739
8.4.4 Der Einsatz polymorpher Texturkoordinaten 741
8.4.5 Implementierung des Pixel-Based-MIP-Mapping-Algorithmus 744
8.4.6 Effiziente Verwaltung von Texturen 750
8.5 Erweiterte Polygonschattierung 756
8.5.1 Textured Flat Shading 756
8.5.2 Textured Gouraud Shading 777
8.5.3 Textured Phong / Metal Shading 782
8.5.4 Textured Depth Shading 784
8.5.5 Der Einsatz benutzerdefinierter Sekundärintensitäten 787
8.5.6 Bitmap Morphing 792

9 Landscape Generation 793
9.1 Grundlagen der Landscape Generation 794
9.1.1 Grundidee der Generierung dreidimensionaler Landschaften 794
9.1.2 Aufbau dreidimensionaler Umgebungen 796
9.1.3 Verwaltung dreidimensionaler Landschaften 806
9.1.4 Drahtgittermodell einer dreidimensionalen Landschaft 811
9.1.5 Polygonbasierende dreidimensionale Umgebungen 813
9.2 Navigation innerhalb einer dreidimensionalen Welt 819
9.2.1 Praktischer Aufbau eines einfachen Bewegungsmodells 823
9.3 Der Visible-Terrain-Visualisation-Algorithmus 825
9.3.1 Grundlagen des Visible-Terrain-Visualisation-Algorithmus 826
9.3.2 Implementierung des VTV-Algorithmus 830
9.3.3 Erweiterte Vektorrotation 849
9.3.4 Der Einsatz komplexer lokaler Koordinatensysteme 855
9.4 Erweiterte Visualisierungsalgorithmen 870
9.4.1 Texturauswahl bei der Generierung dreidimensionaler Landschaften 871
9.4.2 Uneingeschränkte Bewegung innerhalb dreidimensionaler Umgebungen 882
9.4.3 Der Einsatz mehrerer Darstellungskameras 890

A Grundlagen der Programmierung von Multitasking-Betriebssystemen 893
A.1 Erstellung eines Programmfensters 893
A.2 Kommunikation zwischen Programm und Betriebssystem 898
A.3 Grundlagen der Verwendung von High-Level-APIs 900
A.3.1 Einstellung der Auflösung 901
A.3.2 Die Anfangsadresse des Videospeichers 902
A.3.3 Die Einstellung der 8-Bit-Palette 904
A.4 Praktische Verwaltung von Programmfenstern 907
A.5 Abbruch der Programmausführung 907

Stichwortverzeichnis 909