145 107 129MB
German Pages 319
Frank Klawonn Grundkurs Computergraf ik mit Java
Frank Klawo nn
Grundkurs Computergrafik mit Java Die Grundlagen verste hen und einfac h umsetzen mit Java 3D 3., erwe iterte Auflage Mit 139 Abbi ldungen und 6 Tabellen STU DIUM
11 VIEWEG+ TEUBNER
Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Natlonalbibfiogratie: detaillierte bibliografische Daten sind im Internet über abrufbar.
Das in diesem Werk enthaltene Programm-Material ist mit keiner Verpflichtung oder Garantie irgendeiner Art verbunden. Der Autor übernimmt infolgedessen keine Verantwortung und wird keine daraus fo lgende oder sonstige Haftung übernehmen, die auf irgendeine Art aus der Benutzung dieses Programm- Materials oder Teilen davon entsteht. Höchste inhaltliche und technische Qualität unserer Produkte ist unser Ziel. Bei der Produktion und Auslieferung unserer Bücher wollen wir die Umwelt schonen: Dieses Buch ist auf säurefreiem und besteht aus Polyäthylen und damit aus chlorfrei gebleichtem Papier gedruckt. Die organischen Grundstoffen, die weder bei der Herstellung noch bei der Verbrennung SChadstoffe freise tzen.
ansenwemreue
1. Auflage 2005 2. Aufl age 2008 3., erweiterte Auflage 2010 Alle Rechte vorbehalten
© Vieweg+Teubner Verlag I Springer Fachmedien Wiesbaden GmbH 20 10 Lektorat: Chnstet Roß I Maren Mithöfer viaweg- Teubner Verlag ist eine Marke von Springer Fachmedien. Springer Fachmedien ist Teil der Fachverlagsgruppe Springer Seience-Business Media. www.viewegteubner.de Das Werk einschli eßlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mihoverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen . Die Wiedergabe von Gebrauchsnamen, Handelsnamen. Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften.
Urnschlaggestaltung: Künkell.opka Medienentwicklung, Heidelberg Druck und buchbindensehe Verarbeitung: MercedesDruck, Berlin Gedruckt auf säurefreiem und Chlorfrei gebleich tem Papier. Printed in Germany ISBN 978-3-8348-1223-0
v
Vorwort In der frühen Phase der Computergrafik oder der grafischen Datenverarbeitung beschäftigten sich primär Experten mit diesem Gebiet, etwa im Bereich des Computer Aided Design (CAD). Heutzutage kommt jeder Computer-Nutzer mit Computergrafik in Berührung. Dies beginnt bei grafischen Betriebssystemen und grafischen Oberflächen, schließt Visualisierungen von einfachen Balkendiagrammen bis hin zu dynamischen dreidimensionalen Darstellungen zeitlicher Abläufe, wie Strömungen oder Winde, ein und umfasst ebenso den populären Bereich der Computerspiele. Auch wenn man selbst keinen Computer nutzt, begegnet man der Computergrafik im Kino oder im Fernsehen, wo Teile von Bildern, einzelne Szenen oder ganze Filme mittels grafischer Datenverarbeitung erstellt werden. Ermöglicht wurde all dies zum einen durch die heute verfügbare leistungsfähige Hardware in Form von schnellen Prozessoren, großzügigem Speicher und speziellen Grafikkarten. Zum anderen sind aber auch effiziente Algorithmen und einfach zu handhabende Programmmierwerkzeuge erforderlich. Standard-PC's reichen inzwischen aus, um eigene grafische Anwendungen und Animationen zu erstellen. Dazu gibt es frei verfügbare Programmierplattformen wie beispielsweise OpenGL oder Java 3D. Neben grundlegenden Programmierkenntnissen erfordert die Benutzung dieser Werkzeuge zumindest ein elementares Verständnis der Konzepte, Verfahren und Hintergründe der grafischen Datenverarbeitung. Die Vermittlung dieser notwendigen Grundlagen der Computergrafik im direkten Verbund mit der sofortigen praktischen Umsetzung an Beispielen ist das Ziel dieses Buches. Diese Kopplung von Theorie und Praxis soll es dem Leser ermöglichen , die konzeptionellen Grundlagen direkt in die Praxis umzusetzen und visuell zu begreifen. Für die praktische Umsetzung werden vom Leser nur elementarste Kenntnisse in der Programmiersprache Java erwartet. Das Buch verwendet für die Beispielprogramme Java 3D und zu Beginn Java 2D, um einen einfachen Einstieg in die Grundlagen der zweidimensionalen grafischen Datenverarbeitung zu geben. Die erforderlichen Grundlagen von Java 2D und Java 3D werden im Rahmen dieses Buches vermittelt. Auch wenn gerade die Verbindung der Theorie mit der Praxis bei der Erstellung des Buches im Vordergrund stand, so kann dieses Buch ebenso allein für das Erlernen der Grundlagen der Computergrafik verwendet werden, ohne Java 2D oder Java 3D zu erlernen. Das Buch bleibt in sich geschlossen, wenn man alle Abschnitte weglässt , in deren Uberschrift das Wort Java auftaucht. Für das Verständnis der Techniken und Algorithmen in der Computergrafik werden elementare Kenntnisse im Rechnen mit Vektoren
VI
Vorwort
und Matrizen vorausgesetzt sowie Grundlagen der Analysis. Dieses Buch kann nicht den Anspruch erheben, den vollen Umfang von Java 2D oder Java 3D auch nur annähernd abzudecken. Dies würde jeweils allein ein mehrbändiges Werk füllen, ohne auf die Grundlagen der Computergrafik einzugehen. Vielmehr werden hier nur die jeweils für die praktische Umsetzung relevanten Teile von Java 3D bzw. 2D möglichst ohne Ballast erklärt. Es wird daher nicht immer die allgemeinste Form einer Realisierung mit allen Optionen diskutiert, sondern die für die Standardanwendung erforderliche. Es wurde ebenfalls versucht, die Programmbeispiele in diesem Buch - so weit wie möglich einfach zu halten und auf das Wesentliche zu konzentrieren. Diese Art der Vermittlung und das gesamte Konzept des Buches basiert neben den Erfahrungen aus Industrieprojekten auf Vorlesungen und Laboren, die an der Fachhochschule Braunschweig /Wolfenbüttel seit mehreren Jahren gehalten werden. Die Entscheidung für die Plattformen Java 2D und Java 3D fiel aus mehreren Gründen. Die Programmiersprache Java setzt sich in vielen Bereichen immer mehr durch und damit ebenso Erweiterungen wie Java 2D/3D. An vielen Hochschulen wird Java inzwischen als erste Programmiersprache gelehrt , sowohl in Informatikstudiengängen als auch in anderen Fächern, so dass den Studierenden mit Java 2D13D ein direkter und einfacher Einstieg in die Computergrafik ermöglicht wird. Insbesondere im Bereich der Medientechnik und -informatik gewinnt Java 2D13D zunehmende Beliebtheit. Das Buch wäre unnötig umfangreich , wäre der Quellcode aller Beispielprogramme vollständig abgedruckt. Außerdem möchte sich niemand der Mühe und der fehleranfälligen Tätigkeit unterziehen, die Programme abzutippen. Deswegen werden im Buch nur die jeweils relevanten Auszüge der Programme dargestellt. Der Quellcode aller Beispielprogramme sowie weitere Programme können im Internet über den Online-Service zum Buch unter http: / /public.ostfalia .del r-v klawonnlcomputergrafik herunter geladen werden. Der Online-Service bietet außerdem weitere Übungsaufgaben zu Theorie und Praxis, Lösungshinweise, Folien zur Unterstützung von Lehrveranstaltungen sowie Dateien mit Beschreibungen dreidimensionaler Objekte, die in Java 3D eingebunden werden können. Auch die im Anhang A angegebenen Links finden sich dort noch einmal. Viele meiner Studenten haben über die Jahre durch Anregungen, Verbesserungsvorschläge und Fragen in meinen Lehrveranstaltungen dazu beigetragen, dass das vorliegende Buch in dieser Form entstehen konnte. Mein besonderer Dank gilt Daniel Beier, Thomas Weber und Jana Volkmer, die mit zahlreichen konstrukti-
VII ven Anmerkungen zur wesentlichen Verbesserung des Manuskripts beigetragen haben. Ferner möchte ich meiner Mitarbeiterin Katharina Tschumitschew und Gerry Gehrmann für die Unterstützung beim Aufbau des Online-Service zum Buch sowie für die Erstellung einiger 3D-Modelle danken. Schließlich gilt mein ganz persönlicher Dank meinen Eltern und Keiko, ohne deren Unterstützung dieses Buch nie zustande gekommen wäre.
Wolfenbüttel, im September 2005
Frank Klawonn
Vorwort zur zweiten Auflage
Die positive Resonanz der Leserschaft auf das Konzept, Computergrafik in Kombination mit Java 2D/ 3D zu lernen, hat zum einen dazu geführt, dass inzwischen beim Springer-Verlag eine englische Übersetzung des deutschen Buches in Lizenz erschienen ist [25], und zum anderen, dass eine Neuauflage der deutschen Version erforderlich wurde. Ich bedanke mich für die Hinweise auf die von mir verursachten und von mir zu verantwortenden Tippfehler, die in der zweiten Auflage entsprechend korrigiert wurden. Ich habe außerdem zahlreiche Anregungen und Wünsche bzgl. Erweiterungen bereits zumindest rudimentär behandelter Aspekte der Computergrafik sowie Vorschläge für weiterführende Themen erhalten. Leider ist es unmöglich, alle Wünsche zu berücksichtigen, da das Buch ansonsten den Charakter einer elementaren Einführung verlieren würde. Neben kleinen Modifikationen, die an einzelnen TextsteIlen vorgenommen wurden, sind in der zweiten Auflage folgende Ergänzungen bzw. Erweiterungen enthalten: • Im Rahmen der OberflächenmodelIierung wird auf die Darstellung von Funktionen in zwei Variablen eingegangen, die auch dazu verwendet werden kann, um z.B. hügelige Landschaften zu modellieren. • In diesem Zusammenhang wird auch kurz das Thema Text in dreidimensionalen Darstellungen behandelt.
• Partikelsysteme werden ausführlicher erläutert und ein einfaches Partikelsystem mit diversen Parametern wurde implementiert.
VIII
Vorwort
• Dynamische Oberflächen werden ebenfalls detaillierter behandelt. Natürlich werden auch zu diesen Themen die Implementierungen anhand von Beispielprogrammen in Java 3D erklärt. Bei der Realisierung der Partikelsysteme wird außerdem erklärt, wie Szenengrafen dynamisch während der Animation verändert werden können, was für einige Anwendungen erforderlich ist. Ich hoffe, dass so auch die zweite Auflage die gleiche positive Resonanz der Leserschaft erfährt wie bereits die erste.
Wolfenbüttel, im September 2008
Frank Klawonn
Vorwort zur dritten Auflage
In der dritten Auflage wurden gegenüber der Zweiten neben kleinen Korrekturen ein Abschnitt und Beispiel zur Realisierung der Technik Level of Detail (LOD) im Kapitel 9 aufgenommen.
Wolfenbüttel, im Februar 2010
Frank Klawonn
IX
In haltsverzeichn is Vorwort
V
1
Einleitung
1
1.1
Anwendungsfelder . . . . . . .
1
1.2
Von der realen Szene zum Bild
3
1.3
Aufbau dieses Buches . . . . .
4
2
Grundlagen zweidimensionaler Darstellungen
6
2.1
Rastergrafik versus Vektorgrafik
6
2.2
Das erste Java 2D Programm
9
2.3
Geometrische Grundobjekte ..
12
2.4
Geometrische Grundobjekte in Java 2D
16
2.5
Geometrische Transformationen
22
2.6
Homogene Koordinaten . . . . .
27
2.7
Anwendungen von Transformationen
31
2.8
Geometrische Transformationen in Java 2D
33
2.9
Animation und Bewegungen mittels Transformationen
36
2.10
Bewegungen mittels Transformationen in Java 2D .
39
2.11
Interpolatoren für kontinuierliche Veränderungen
40
2.12
Realisierung von Interpolatoren mit Java 2D .
44
2.13
Einfache oder doppelte Genauigkeit
45
2.14
Übungsaufgaben . . . . . . . . . . .
47
3 Zeichnen von Kurven
48
3.1
Geraden und Rastergrafik . . . . . . . .
48
3.2
Der Mittelpunktalgorithmus für Geraden
50
x
4
5
In haItsverzeichnis 3.3
Strukturelle Algorithmen ..
60
3.4
Pixeldichten und Linienstile .
63
3.5
Geradenclipping
68
3.6
Der Mittelpunktalgorithmus für Kreise
76
3.7
Zeichnen beliebiger Kurven
80
3.8
Antialiasing
81
3.9
Zeichnen breiter Linien
84
3.10
Übungsaufgaben .
88
.
.
Flächen, Text und Farbe
89
4.1
Füllen von Flächen
89
4.2
Bufferedimages in Java 2D
93
4.3
Darstellung von Text
98
4.4
Text in Java 2D . . .
99
4.5
Grauwertdarstellung und Intensitäten .
101
4.6
Farbmodelle . . .
104
4.7
Farbinterpolation
109
4.8
Farbinterpolation mit Java 2D
112
4.9
Übungsaufgaben
.
115
Grundlagen dreidimensionaler Darstellungen
116
5.1
Von der 3D-Welt zum Modell
116
5.2
Geometrische Transformationen
118
5.3
Szenengraphen
5.4
Elementare geometrische Objekte in Java 3D
126
5.5
Der Szenengraph in Java 3D
127
5.6
Animation und Bewegung.
133
5.7
Animation in Java 3D .
135
5.8
Projektionen . . .
142
5.9
Übungsaufgaben .
151
.
123
XI 6
Modellierung dreidimensionaler Körper
152
6.1
Dreidimensionale Körper und deren Oberflächen.
152
6.2
Topologische Begriffe .
155
6.3
Modeliierungstechniken
157
6.4
OberflächenmodelIierung mit Polygonen in Java 3D .
162
6.5
Flächen als Funktionen in zwei Variablen.
167
6.6
Text in dreidimensionalen Darstellungen
173
6.7
Para metrische Kurven und Freiformflächen .
175
6.8
Normalenvektoren an Oberflächen
185
6.9
Übungsaufgaben . . . . . . . . . .
190
7 Visibilitätsbetrachtungen
8
191
7.1
Das C1ippingvolumen . . . . . . . .
191
7.2
Grundlagen der Visibilitätsverfahren
195
7.3
Bildraumverfahren ..
199
7.4
Prioritätsa Igorithmen
207
7.5
Übungsaufgaben . . .
210
Beleuchtungsmodelle und Schattierung
211
8.1
Lichtquellen . . . . . . .
212
8.2
Lichtquellen in Java 3D .
214
8.3
Reflexion . . . . . .
217
8.4
Shading in Java 3D
226
8.5
Shading
227
8.6
Schatten.
232
8.7
Transparenz
234
8.8
Texturen ..
237
8.9
Texturen in Java 3D
240
8.10
Das Radiosity-Modell
242
8.11
Ray-Tracing .....
247
XII
In haItsverzeichnis 8.12
9
Übungsaufgaben .
249
Spezialeffekte und virtuelle Realität
250
9.1
Nebel. . . . . .
250
9.2
Nebel in Java 3D
251
9.3
Partikelsysteme
253
9.4
Eine einfache Realisierung eines Partikelsystems in Java 3D. 255
9.5
Dynamische Oberflächen . . . . . .
258
9.6
Dynamische Oberflächen in Java 3D
262
9.7
Interaktion. . . . . . .
264
9.8
Interaktion in Java 3D
265
9.9
Kollisionsdetektion. .
268
9.10
Kollisionsdetektion in Java 3D
270
9.11
Level of Detail (LOD) in Java 3D
276
9.12
Akustische Effekte. . . . . . .
278
9.13
Akustische Effekte in Java 3D
279
9.14
Stereoskopie. . .
281
9.15
Übungsaufgaben .
286
A Anhang: Hilfreiche Adressen im Internet
287
BAnhang: Beispielprogramme
289
C Anhang: Hinweise zu Java 20 Klassen und Methoden
297
o
298
Anhang: Hinweise zu Java 30 Klassen und Methoden
Literatu rverzeichnis
300
Index
304
1
1
Einleitung
Computergrafik beschäftigt sich mit der Erzeugung von Bildern mittels eines Rechners. Aus diesem Grund wird auch häufig der Begriff grafische Datenverarbeitung verwendet. Das Wort" Bild" sollte hier in einem abstrakten Sinn verstanden werden. Ein Bild kann eine realistische Szene aus der Alltagswelt darstellen, aber ebenso Grafiken wie Histogramme oder Tortendiagramme wiedergeben oder die grafische Benutzungsoberfläche einer Software sein. Im folgenden Abschnitt sollen exemplarisch einige Anwendungsfelder der Computergrafik dargestellt werden, um einen Eindruck über das Aufgabenspektrum der grafischen Datenverarbeitu ng zu vermittel n.
1.1
Anwendungsfelder
Obwohl grafische Betriebssysteme und Benutzungsoberflächen grundsätzlich auch ein Anwendungsfeld der Computergrafik repräsentieren, spielen sie eher eine untergeordnete Rolle. Zum einen gibt es zur Programmierung für grafische Schnittstellen standardisierte Werkzeuge und zum anderen liegt der Schwerpunkt dort vor allem auf der Benutzerfreundlichkeit und damit im Bereich der Softwareergonomie. In der Werbung und in bestimmten Kunstrichtungen werden viele Bilder inzwischen vollständig mit dem Computer erzeugt oder Fotografien mittels Techniken der Computergrafik überarbeitet oder sogar verfremdet. Für die riesigen Datenmengen, die überall in Industrie, Wirtschaft, Wissenschaft und Forschung aufgezeichnet werden, sind nicht nur geeignete Verfahren zur automatischen Analyse und Auswertung der Daten erforderlich, sondern auch Techniken zur Visualisierung und grafischen Präsentation. Diese Visualisierung geht weit über einfache Darstellungen von Funktionsgraphen, Histogrammen oder Tortendiagramme hinaus , was heute schon Tabellenkalkulationsprogramme können. Zwei- oder dreidimensionale Visualisierung von hochdimensionalen Daten , problemangepasste Darstellungen der Daten [24, 41, 45, 48] oder auch spezielle Animationen, die zeitliche Verläufe z.B. von Strömungen oder Wetterphänomenen zeigen, zählen dazu.
2
1 Einleitung
Neben der Erzeugung und Darstellung dieser eher abstrakten Grafiken liegen die Hauptanwendungsfelder der Computergrafik natürlich im Bereich der Darstellung realistischer - nicht notwendigerweise realer - Bilder und Bildfolgen. Klassische Anwendungen kommen aus dem Bereich CADjCAM (Computer Aided DesignjManufacturing), wo es um den Entwurf und die Konstruktion von Objekten wie Autos oder Gehäusen geht. Die darzustellenden Objekte werden dabei im Rechner entworfen, genau wie auch in Computerspielen oder Architektenplanungsprogrammen zur Visualisierung von realen oder geplanten Gebäuden und Landschaften. In diesen Fällen werden im Rechner zu entwerfende Objekte, z.B. ein Anbau an ein Haus, kombiniert mit bereits existierenden Objekten, die ebenfalls erst im Rechner modelliert werden müssen. Die gleiche Problematik ergibt sich z. B. auch bei Fahr- oder Flugsimulatoren, in denen reale Städte oder Landschaften im Computer zu modellieren sind. Nicht nur die Möglichkeit, Objekte zu modellieren und zu visualisieren, spielt in der Computergrafik eine wichtige Rolle, sondern auch die Erzeugung von realistischen Darstellungen aus gemessenen Daten. Zur Erzeugung solcher Daten werden Scanner verwendet, die die Tiefeninformationen von Oberflächen von Objekten messen, oder mehrere kalibrierte Kameras, aus denen sich 3D-Informationen rekonstruieren lassen. Ein sehr bedeutendes Anwendungsfeld stellt dabei auch die medizinische Informatik [38] dar. Dort wird aus zum Teil mit verschiedenen Verfahren wie Röntgenaufnahmen, Ultraschallbildern oder Computertomografie gewonnenen Daten eine dreidimensionale Visualisierung von Organen oder Knochenstru ktu ren erzeugt. Die Kopplung von realen Daten und Bildern mit Techniken der Computergrafik wird sich in der Zukunft wahrscheinlich noch weiter verstärken. Computerspiele erlauben das Navigieren durch Szenen und das Betrachten einer Szene aus verschiedenen Blickwinkeln. Bei Filmen, wie sie im Fernsehen gezeigt werden, ist es bisher nicht möglich, dass der Betrachter sich eine Szene aus einem selbst gewählten Blickwinkel ansieht. Die grundsätzlichen Techniken dafür sind aber bereits vorhanden [29]. Dazu ist es allerdings erforderlich, dass neben "intelligenteren" Fernsehern Szenen gleichzeitig aus mehreren Perspektiven aufgenom men werden. Der Betrachter muss nicht an die Positionen der Kameras gebunden sein, sondern kann einen beliebigen Standpunkt einnehmen. Die entsprechende Darstellung der Szene wird dann aus den Informationen berechnet , die die einzelnen Kameras liefern. Hierzu müssen Techniken der Computergrafik, die der Synthese von Bildern dienen, mit Verfahren aus der Bildverarbeitung, die sich mit der Analyse von Bildern beschäftigen, kombiniert werden [31].
3
1.2 Von de r realen Szene zum Bild
Ein weiteres wicht iges Anwendu ngsfe ld der Computergrafik bilden Virt ua l Reality, wo es um die Vermitt lung eines nah ezu ec hten dreidi mens iona len Eindrucks geh t , und Augmented Reality, bei de r die rea le Wahrne hmung durch Zusatz informa t ionen angereichert wird.
1.2
Von der realen Szene zum Bild
An de n im vorher ge hend en Absc hnitt erwähnten Beispielanwendu ngen erke nnt man bereits , dass eine Vielzahl unterschiedlicher Aufgaben in der Compute rgrafik zu lösen ist . Abb ildung 1.1 zeigt die groben Schritte , die nöti g sind , um von einer realen oder virtuellen Sze ne zu einem Bild zu ge lange n.
I
/'
r-,
-,
~
./
(a)
(b)
(c)
\\
1
/'
(d)
Abbild ung 1.1 Von der realen Szene zum Bild
Zunäc hst müsse n d ie Objekte der Szene in Abbildung 1.1(a ) mit den zur Verfüg ung stehende n Mögli chkeiten eines Model iierungswerkze ugs nachgebildet werden. Diese Nachbildung ist im Allgemeinen nur eine Annä hrung an die Objekte de r Szene. Je nac h Aufwand , den ma n bet reibt , und den zur Verfügung stehende n Mode lIieru ngsa rte n können die Objekte mehr ode r weniger gut approximiert werden . Dieser Sachver ha lt wird in Abb ildung 1.1(b) etwas übe rdeutl ich da rgestellt , indem die Form der realen Schüsse l hier nur se hr grob du rch eine Ha lbkugel angenä hert wird . Die modellierten Objekte decken in der Rege l einen viel größe ren als den für den Betrachte r sichtbaren Bereich ab. Es könnten z.B . mehrere Gebäudekomp lexe mit umliegenden Gärten mode lliert sein, d urch die sich der Bet rac hter bewegen kan n. We nn de r Bet rach ter in einem best immten Ra um steht und in eine konkrete Richt ung blickt , so befinde n sich die meisten modell ierten Objekte überhaupt nicht in se inem Blickfeld und können be i der Darst ellung der Szene vernac hlässigt werden. Es muss also ein dreidime nsiona ler
4
1 Einleitung
Bereich definiert werden, der vom Betrachter wahrgenommen wird (siehe Abbildung 1.1(c)). Die Ermittlung, welche Objekte überhaupt in diesem Bereich liegen und welche nicht, bezeichnet man als (dreidimensionales) Clipping. Ein Objekt, das im Wahrnehmungsbereich liegt, ist nicht notwendigerweise auch für den Betrachter sichtbar, da es durch andere Objekte im Wahrnehmungsbereich verdeckt werden kann. Die Objekte, die in diesem Bereich liegen, müssen dann auf eine zweidimensionale Fläche projiziert werden, so dass man schließlich ein auf dem Monitor oder dem Drucker darstellbares Pixelbild wie in Abbildung 1.1(d) erhält. Bei dieser Projektion müssen Visibilitätsbetrachtungen durchgeführt werden, welche Objekte oder welche Teile von Objekten sichtbar sind bzw. durch andere Objekte verdeckt werden. Außerdem spielen Beleuchtung und Lichteffekte eine wesentliche Rolle für die Darstellung der sichtbaren Objekte. Auch zweidimensionales Clipping muss hier angewendet werden um festzustellen, welche Teile eines dreidimensionalen Objektes im Wahrnehmungsbereich gezeichnet werden müssen oder vernachlässigt werden sollten, da sie außerhalb der Projektionsfläche liegen. Der gesamte Prozess der Erzeugung eines zweidimensionalen Bildes aus einer dreidimensionalen Szene wird auch als Rendering bezeichnet. Die Hintereinanderausführung der einzelnen Techniken, die im Detail in der groben Beschreibung in Abbildung 1.1 ausgeführt werden müssen, nennt man auch Rendering Pipeline. Die Rendering Pipeline hängt von den ausgewählten Techniken und Algorithmen ab. In [16] werden exemplarisch allein fünf Rendering Pipelines unter Berücksichtigu ng verschiedener Beleuchtu ngsverfahren vorgestellt.
1.3
Aufbau dieses Buches
Der Aufbau dieses Buches orientiert sich an der Rendering Pipeline. In den Kapiteln 2, 3 und 4 werden die wesentlichen Aspekte für den letzten Abschnitt der Rendering Pipeline dargestellt. Es geht dabei ausschließlich um Verfahren zur Darstellung zweidimensionaler Bilder, zum einen als Teilaufgabe beim Rendering dreidimensionaler Szenen, zum anderen aber auch als eigenständiges Werkzeug. Zunächst werden die Grundlagen für Vektor- und Pixelgrafik sowie die einfache ModelIierung planarer Objekte und deren Bewegungen anhand von Java 2D eingeführt und veranschaulicht.
1.3 Aufbau dieses Buches
5
Das 3. Kapitel widmet sich vor allem algorithmischen Aspekten der Rasterdarstellung, die beim Zeichnen von Kurven von großer Bedeutung sind, während das vierte Kapitel FlächendarsteIlung behandelt sowie auf die Verwendung von Schriftzeichen und Farbe eingeht. Die darauf folgenden Kapitel sind der ModelIierung und Darstellung dreidimensionaler Szenen gewidmet und geben gleichzeitig eine Einführung in Java 3D, um die vorgestellten Konzepte praktisch umzusetzen. Kapitel 5 und 6 legen die Grundlagen für die Handhabung und ModelIierung dreidimensionaler Objekte und Szenen. Verschiedene Techniken zur Berechnung, welche Objekte in einer dreidimensionalen Szene sichtbar bzw. verdeckt sind, werden in Kapitel 7 diskutiert. Für fotorealistische Darstellungen ist es erforderlich, Effekte wie Schattierungen, Schatten und Reflexion zu berücksichtigen. Kapitel 8 beschäftigt sich mit diesen Fragestellungen. Schließlich bietet das letzte Kapitel 9 einen Überblick zu weiter führenden Themen wie Spezialeffekten, Interaktionsmechanismen oder dem stereoskopischen Sehen, das für das Verständnis der Grundlagen der Virtual-Reality-Anwendungen unabdingbar ist. Im Anhang finden sich Hinweise auf hilfreiche Internetadressen sowie eine Auflistung, welche Beispielprogramme an welcher Stelle im Buch erläutert werden.
6
2
Grundlagen zweidimensionaler Darstellungen
In diesem Kapitel werden elementare Konzepte für zweidimensionale Grafiken eingeführt. Die üblichen Ausgabemedien für Grafiken wie Monitore oder Drucker sind fast ausschließlich Pixel-orientiert. Deswegen muss zwischen der Darstellung auf diesen Medien und der eigentlichen ModelIierung der Grafiken, die im Allgemeinen nicht Pixel-orientiert ist, unterscheiden werden.
2.1
Rastergrafik versus Vektorgrafik
\\, ~
D (a) Abbildung 2.1
10 (b)
(c)
Originalbild , Vektor- und Rastergrafik
Ein zu zeichnendes Objekt , sofern es nicht schon als fertiges Bild vorliegt, muss zunächst beschrieben oder modelliert werden. Dies geschieht üblicherweise mittels vektororientierter Grafik oder Vektorgrafik. Das zu modellierende Objekt wird dabei durch die Kombination von Grundobjekten wie z.B. Linien, Rechtecken, Kreis- oder Ellipsenbögen beschrieben. Jedes dieser Grundobjekte lässt sich durch die Angabe weniger Koordinaten, die die Lage bestimmen, und einiger Parameter, wie z.B. der Radius bei einem Kreis, eindeutig definieren. Eine sehr einfache Beschreibung des Hauses aus Abbildung 2.1(a) als Vektorgrafik zeigt Abbildung 2.1(b). Das Haus kann als Folge von Punktkoordinaten oder Vektoren beschrieben werden. Dabei muss zusätzlich noch angegeben werden, ob zwei aufeinander folgende Punkte miteinander durch eine Linie verbunden
2.1 Rastergrafik versus Vektorgrafik
7
werden sollen oder nicht. In der Abbildung ist dies dadurch angedeutet, dass eine Verbindung zweier Punkte, die nicht gezeichnet werden soll, gestrichelt dargestellt ist. Diese Form der Objektbeschreibung eignet sich jedoch nicht direkt für die Darstellung auf einem rein Pixel-orientierten Ausgabegerät wie etwa einem Flachbildschirm oder einem Drucker. Bei einem Kathodenstrahlmonitor ließe sich theoretisch eine vektororientierte Grafik direkt umsetzen, indem man den Kathodenstrahl - bzw. drei Kathodenstrahlen bei Farbdarstellung - entlang der zu zeichnenden Linien führt und, je nachdem, ob eine Linie zu zeichnen ist oder nicht, den Kathodenstrahl ein- oder ausblendet. Hierbei kann sich aber das Problem eines flackernden Bildschirms ergeben, da die Fluoreszens der Bildschirmpunkte nachlässt, wenn sie nicht erneut von dem Kathodenstrahl getroffen werden. Flackerfreiheit erfordert eine Bildwiederholrate von ca. 60Hz. Wenn der Kathodenstrahl die einzelnen Linien der Vektorgrafik immer wieder ablaufen muss, hängt die Bildwiederholrate davon ab , wie viele Linien das Bild enthält. Daher kann bei komplexeren Bildern eine genügend hohe Bildwiederholrate für Flackerfreiheit nicht garantiert werden. Der Kathodenstrahl durchläuft den Bildschirm daher zeilenweise, so dass die Bildwiederholrate unabhängig von der darzustellenden Grafik ist. Auf dem Monitor, dem Drucker, aber auch bei verschiedenen Bildspeicherungsformaten wie JPEG wird daher eine Rastergrafik oder rasterorientierte Grafik verwendet. Einer Rastergrafik liegt eine feste Pixelmatrix zugrunde. Jedem einzelnen Pixel des Rasters kann ein Farbwert zugeordnet werden. Im einfachsten Fall eines Schwarz/Weiß-Bildes wird das Pixel entweder gefärbt oder nicht gefärbt. Soll eine vektororientierte Grafik als Rastergrafik dargestellt werden, müssen alle Linien in Pixelform konvertiert werden. Man spricht dabei von Scan Conversion. Das bedeutet zum einen hohen Rechenaufwand. Ein üblicher Monitor hat ca. eine Million Pixel, für die jeweils entschieden werden muss, wie sie zu färben sind. Zum anderen treten unerwünschte Aliasing-Effekte in Form ausgefranster oder stufenförmige Linien auf. Der Begriff Aliasing-Effekt stammt aus der Signalverarbeitung und bezeichnet Artefakte, d.h. künstliche, unerwünschte Effekte, die auftreten, wenn man ein kontinuierliches Signal mit einer diskreten Abtastung erfasst. Auch wenn ein Bild letztendlich als Rastergrafik dargestellt werden muss, ist es dennoch vorteilhaft, es in vektororientierter Form zu modellieren und abzuspeichern. Eine Rastergrafik ist an eine spezifische Auflösung gebunden. Legt man sich auf ein Raster fest, ergeben sich erhebliche Nachteile bei der Darstellung, wenn ein Ausgabegerät mit einer anderen Auflösung arbeitet. Abbildung 2.2 zeigt die Spitze eines Pfeils und die Darstellung als Rastergrafik unter
2 Grundlagen zweidimensionaler Darstellungen
8
zwei verschiedenen Auflösungen. Kennt man nur die Darstellung in der groben Auflösung in der Mitte, kann die gewünschte feinere Rasterung rechts nicht mehr ohne weitere Informationen rekonstruiert werden. Bestenfalls könnte man hier die identische grobe Darstellung in der Mitte für die feinere Auflösung übernehmen, indem man ein grobes Pixel auf vier feinere Pixel abbildet. Wenn das Verhältnis der Auflösungen der beiden Rasterungen nicht ganzzahlig ist, wird die Umrechnung von einer Auflösung in eine andere aufwendiger und birgt die Gefahr neuer Aliasing-Effekte, selbst wenn die Auflösung verfeinert wird.
••
Abbildung 2.2
-
-• ••
••
Eine Pfeilspitze in zwei Auflösungen dargestellt
Zur Veranschaulichung von Rasterungen wird in diesem Buch teilweise die Darstellung wie in Abbildung 2.2 verwendet, wo ein Pixel durch ein Einheitsquadrat zwischen den Gitterlinien repräsentiert wird. In anderen Fällen ist die Darstellung wie in Abbildung 2.3 günstiger, bei der die Pixel Kreise auf den Gitterpunkten entsprechen. In Abbildung 2.3 ist das Pixel mit den Koordinaten (5,3) zu sehen. 8 7 6 5 4 3 2 1
-
00 1 2 3 4 5 6 7 8 9 Abbildung 2.3
Eine alternative Pixelrepräsentation
2.2 Das erste Java 2D Programm 2.2
9
Das erste Java 2D Programm
Bevor näher auf die ModelIierung zweidimensionaler Objekte eingegegangen wird, soll an dieser Stelle gezeigt werden, wie man Java 2D grundsätzlich verwenden kann, um Grafiken zu erstellen. Java 2D wird die ersten Kapitel des Buches begleiten, bei denen es allein um zweidimensionale Probleme geht. Ab dem 5. Kapitel wird Java 3D für dreidimensionale ModelIierung verwendet. Das Ziel dieses Buches besteht nicht in einer möglichst vollständigen Einführung in Java 2D oder Java 3D. Vielmehr sollen auch interessierte Leser, die nur über geringe Java-Kenntnisse verfügen, in die Lage versetzt werden, die für die Computergrafik erforderlichen Methoden zu nutzen und anzuwenden. Aus diesem Grund wird versucht, die Programme möglichst einfach und übersichtlich zu halten, und es werden nicht alle zur Verfügung stehenden Optionen im Detail erläutert, um sich besser auf die wesentlichen Aspekte konzentrieren zu können. Für diejenigen, die bereits über vertiefte Java-Kenntnisse verfügen, sollte die in diesem Buch gegebene Einführung in Java 2D bzw. Java 3D ausreichen, um sich eigenständig weitere Möglichkeiten dieser beiden Application Programming Interfaces (API's) anhand der Literatur oder der Dokumentation zu erarbeiten. Zu Java 2D findet man umfangreiche Informationen in den Büchern [21, 26]. sowie in der API und dem Java Tutorial, die im Internet zu finden sind (s. Anhang
A). Java 20 ist ein API, das ab der Java 2 Plattform (früher JDK 1.2) zu den Kernklassen von Java gehört, so dass, sofern eine entsprechende Java-Plattform zur Verfügung steht, keine zusätzlichen Installationen vorgenommen werden müssen.
~ ~IU I Abbildung 2.4
Java2D API
Die Java 2D API erweitert AWT
I
2 Grundlagen zweidimensionaler Darstellungen
10
Java 2D ergänzt einige AWT1-Pakete von Java um neue Klassen und führt außerdem noch neue Pakete innerhalb von AWT ein. Java 2D ist unterhalb der Grafik-Komponenten AWT und Swing von Java angesiedelt (vgl. Abbildung 2.4). AWT-Komponenten, die auf dem Bildschirm dargestellt werden, haben eine paint-Methode, die ein Graphics-Objekt als Argument erhält. Um die Möglichkeiten von Java 2D für die entsprechende Komponente zu nutzen, muss dieses Graphics-Objekt nur in ein Graphics2D-Objekt gecastet werden. Die Klasse Graphics2D innerhalb von Java 2D erweitert die Klasse Graphics. Die folgende einfache Java-Klasse SimpleJava2DExample. java demonstriert diese Vorgehensweise. Kommentare sind zur besseren Übersicht nicht mit abgedruckt. import java.awt.*; public class SimpleJava2DExample extends Frame {
SimpleJava2DExample() {
addWindowListener(new MyFinishWindow()); }
public void paint(Graphics g) {
Graphics2D g2d = (Graphics2D) g; g2d.drawString("Hello worldl",30,50); }
public static void main(String[] argv) {
SimpleJava2DExample f = new SimpleJava2DExample(); f .setTitle("Das erste Java 2D Programm"); f.setSize(250,80); f.setVisible(true); } }
1
Abstract Windowing Toolkit
2.2 Das erste J ava 20 Programm
11
Hello worldl
Abbild ung 2.5 Das Ergebnis des ersten Java 2D Programms
Abbildung 2.5 zeigt das Ergebnis, wenn man das Programm a usfü hrt. Im Konstruktor wird mit addv dndovl .i s t ene r ermög licht. dass sich das erzeugte Fenster schließen lässt . Dazu wird d ie eigene, sehr einfac he Klasse MyFinishWindo\l'. java verwendet . Die main-Methode konst ruiert das entspreche nde Fenst er , definiert die Fensterbesch riftung. legt die Größe mit 250 P ixeln Breite und 80 Pixeln Höhe fest und öffnet es sc hließlich. Dieser Aufba u de r mat n-Met hode wird bei allen J ava 20 Beispielprogram men in diesem Buch beibehalten. Es muss bei späteren Program men jewei ls nu r SimpleJava2DExample durch den entsprechende n Klassen na men ersetzt werden und event uell eine a ndere Fenste rbesch rift ung und eine neue Fenstergröße gewä hlt werden . Die zu zeichne nde Grafik wird in der paint- Meth ode definiert. Auch die erste Zeile dieser Met hode, in der das Casting des Gr aphi c s-O bjekt es zu eine m Gr a phi c s 2D-Objekt gesc hieht , wird sich nicht ä nde rn. Der da rauffo lgende Teil wird dan n für jedes P rog ra mm individue ll sein. In unsere m erste n Beispielprogram m wird nur der Text .H ello world " a n die Fensterkoord inaten (30,50) geschrieben . Bei de r Angabe de r Fensterkoord inat en sind allgeme in zwei Dinge zu beachten. • Der linken o beren Ecke des Fensters sind d ie Koord inaten (0,0) zugeordne t . Das Fenst er de hnt sich nach rechts (in unserem Beispiel um 250 Pixel) und nach unten (in unserem Beispiel um 80 Pixe l) aus. Das bedeutet. dass die y- Achse nicht wie gewohnt nac h oben, sondern nach unten zeigt . Wie dieses P roblem umga nge n werde n kann , wird an späterer Ste lle noch erklärt . • Das Fenster besitzt an allen vier Seiten einen Rand . Insb esondere der obere Rand, de r a uch die Fensterbeschriftung ent hält, ist relat iv breit. Auf d iese Ränder ka nn mit de r p aint-Methode nicht geze ich net werde n. Es wird zwar kein Fehler erzeugt. se lbst dan n nicht . wenn man versucht . außerha lb des Fensters zu zeichne n. Allerdings werden derartige Zeichenanweisunge n auf dem Rand ode r gar außerha lb des Fenste rs nicht durchge fü hrt . Wenn ma n also wie in dem einfac hen Beispielprogra mm ein Fenste r der Größe 250 x
12
2 Grundlagen zweidimensionaler Darstellungen 80 öffnet , steht ein etwas kleinerer Bereich zum Zeichnen zur Verfügung. Die Breite der Ränder ist plattformabhängig. In den Beispielprogrammen wird dieses Problem der Ränder umgangen, indem immer ein genügend großes Fenster geöffnet wird und es vermeiden wird, zu nahe am Rand zu zeichnen. Man kann die genaue Breite der Ränder aber auch in der entsprechenden Klasse, z.B. in der paint-Methode mittels Insets ins = this. getInsets 0; feststellen. ins . l ef t , ins . right, ins. top und ins . bottomgeben dann die Breite des linken, rechten, oberen bzw. unteren Randes in Pixeln an.
Das erste Java 2D Programmbeispiel erforderte noch keine weiteren Berechnungen vor dem eigentlichen Zeichenvorgang. In der Regel müssen jedoch mehr oder weniger aufwendige Berechnungen durchgeführt werden, um komplexer darzustellende Objekte zu definieren und korrekt zu positionieren. Java 2D trennt zwischen der Definition der Objekte und deren Darstellung. Ein Objekt , das man definiert hat, wird erst dann gezeichnet, wenn eine draw- oder fill-Methode mit dem Objekt als Argument aufgerufen wird. Java 2D unterscheidet daher ebenfalls zwischen der ModelIierung der Objekte, die in vektororientierter Grafik, d.h. in Fließkommaarithmetik erfolgt, und der Darstellung auf dem Bildschirm in Form einer Rastergrafik. Um die Beispielprogramme in diesem Buch möglichst einfach und übersichtlich zu halten , werden die Berechnungen der Objekte direkt in der paint-Methode durchgeführt. Dies kann bei komplexeren animierten Grafiken, d.h. Grafiken mit sich bewegenden oder verändernden Objekten, dazu führen, dass das Fenster nur sehr langsam reagiert , wenn man versucht, es zu schließen. Java ordnet der paint-Methode eine relativ hohe Priorität zu, so dass Ereignisse wie das Schließen des Fensters erst sehr spät registriert werden. Um diesen Effekt zu vermeiden, sollte man, wenn dies erforderlich ist, alle Berechnungen aus der paint-Methode auslagern und die paint- bzw. repaint-Methode jeweils nur dann aufrufen, wenn Objekte zu zeichnen sind. Eine elegantere Lösung liefert die Technik des Double-Buffering, auf die später genauer eingegangen wird.
2.3
Geometrische Grundobjekte
In der zweidimensionalen Computergrafik lassen sich im Wesentlichen drei Typen von Grundobjekten unterscheiden. Punkte, die durch ihre x - und y-Koordinate eindeutig spezifiziert sind. Punkte
werden vor allem dazu verwendet, um andere Grundobjekte zu definieren,
2.3 Geome t rische Grundobjekte
13
be ispielsweise ein Geradensegment d urc h die Festlegurig des Anfa ngs- und des Endpunktes. Kur ven oder Kur venzüge können durch zwei P unkte definierte Geradensegmen te se in, aber a uch komplexere, unt er Umständen a us mehreren Teilkurven zusa mmengesetzte Liniensegmente da rste llen. Flächen werden üblicherweise d urch geschlossene Kurvenzüge begrenzt . Ein gesc hlossener Kurvenzu g kann mit einer Farbe ode r eine m Muste r gefüllt werde n.
Die einfachste Kurve ist ein Gerade nsegmen t, das durch Anfangs- und Endpun kt chara kterisiert wird . We rden mehrere Gerade nsege mente a neina nder gefügt, er hält ma n einen Polygonzug. Ein geschlossener Polygonzug, dessen letztes Gerad ensegment dort endet , wo das erste begin nt . heißt Polygon . Je nac h Grafikprogram m werden nur bestimmte Arte n von Polygonen zugelasse n. Wic htige Eigenschafte n sind d abei d ie Überschneid ungsfreiheit de r Kanten oder die Konvexität . Ein Polygon , ode r allgemeiner eine beliebige Fläche oder ein Körper, heißt konvex , wenn mit je zwei Punkten auc h die Verb indungsstrec ke zwischen diese n beide n P unkt en vollständ ig innerh alb de r Fläche bzw. des Körpe rs verläu ft . Abbi ldung 2.6 zeigt ein nicht- überschn eid ungsfreies. ein nicht-konvexes und ein konvexes Polygon. Bei dem nicht-ko nvexen Polygon in de r Mitte ist eine Verb indu ngs linie zwischen zwei Pu nkten des Polygons gestrichelt angedeutet, die nicht vollstä ndig innerh alb des Polygons verläuft. Nicht- überschneidungsfreie Polygone sind niemals Konvex.
Abbildung 2.6
Polygon
Ein nicht-überschneidungsfreies, ein nicht-konvexes und ein konvexes
Neben den linearen Geradensegme nte n bzw. den stückweise linearen Po lygonzügen werden auch gekrüm mte Kurven verwendet. In den meisten Fä llen werde n gek rümmte l inien durch parametrische Polynome besch rieben , die - wie bei den Gerade nsegmenten - auch stückweise zusam mengesetzt werden können . Wie diese Kurven genau definiert und be rechnet werden, wird im Ka pitel 6 im Det ail besprochen. An dieser Stelle so ll es genüge n, das P rinzip zu er läutern, wie derartige Kurven beschriebe n werden. Nebe n einem Anfangs- und einem Endpun kt
14
2 Grundlagen zweidimensionaler Darste llungen
werden zusätzlich Kont rollpunkt e definiert . In der Regel verwendet man einen Kont rollpunkt und erhä lt eine q uadrat isch e Kurve bzw. zwei Kontrollpunkte.
um eine kubische Kurve zu definieren. Die Kurve beginnt im Anfa ngspunkt und end et im Endpun kt . Sie verläuft im Allgemeine n jedoch nicht d urch die Kont rollpun kte. Die Kontrollpu nkt e die ne n daz u, die Richt ung zu beschreib en , a us
der die Kurve in den Anfangs- bzw. Endpunkt hinein lä uft .
... ~
,,/\ ' .\
, ...-- --...'.\. .
•:
Abbildun g 2.7 Definiti on quadratischer und kubischer Kurven
Im Falle einer quadr at ischen Kurve mit einem Kontrollpunkt stellt man sich die beiden Ver bindun gs linien vom Kont rollpunkt zu m Anfan gs- und zu m Endp unkt vor. Diese gedachten Linien bilden die Ta nge nten an d ie Kurve im Anfa ngsbzw . End punkt . Ab bildung 2.7 zeigt links eine quadr at ische Kur ve. die nebe n Anfangs- und Endpu nkt durch einen Kontrollpunkt definiert wird. Die Ta ngent en im Anfan gs- und Endpun kt sind gestri chelt gezeic hnet . Bei einer kub ische n Kurve , wie sie im rechten Teil de r Abbi ldung zu se hen ist , könne n d ie beiden Ta ngen ten durch zwei Kontrollpunkt e unabhä ngig voneina nde r festge legt werden . Füg t man Kurven ähn lich wie Gerade nsegmente zu einem Polygo nzug ane ina nder . so genügt es im Allgeme inen nicht , d ass der Endp unkt jeder Vorgängerkurve mit dem Anfa ngs pun kt der jewei ligen Folgekurve zusa mme nfä llt. Die zusam mengesetzte Kurve wäre zwar stetig, abe r nicht g latt . d. h.. sie könn te Knicke ent halten. Zu r Verme idu ng von Knicken muss d ie Tan gent e im Endpun kt de r Vorgängerkurve zum indest kollinear mit der Tangente im Anfa ngs pun kt der Folgekurve sein, da s heißt , die beiden Ta ngenten müssen a uf einer Gera de n liegen . Dies err eich t man , indem man d ie Kontrollpu nkte gee ignet set zt . Z ur Verme idung von Knicken muss de r erste Kont rollpunkt de r Folgeku rve auf de r Verbindu ngsgerad en des Endpu nktes der Vorgängerkurve mit ihrem letzt en Kon tr ollpunkt liegen. Ga nz a na log kann ma n auc h eine Kurve an eine Gerade an füge n. oh ne eine n Knick zu erzeugen, indem ma n den erste n Kontrollpu nkt so wäh lt , da ss er au f der Verlänger ung der Geraden liegt. Abbild ung 2.8 veranschau licht diesen Sachverhalt .
15
2.3 Geomet rische Gru ndobjekte
• ,
.....•
A bbildung 2 .8 Glattes Anfügen einer kubischen Kurve an eine Gerade
Weitere, in de r Computergrafik hä ufig verwendete Kurven sind Kreise und Ellipsen oder Teile davon in Form von Kreis- bzw. Ellipsenb ögen. Kreise und Ellipsen def iniere n ebenso wie Po lygone Flächen. Fläc hen werde n durch gesc hlossene Kurven begrenzt . So ll nu r der Rand einer Fläche gezeichnet werde n, besteht kein Unterschied zu m Zeichne n von Kurve nzüge n a llgeme in. Flächen können aber im Gegensatz zu einfachen Linien mit Farben oder Muste rn a usgefü llt werde n. Algorithm isch bet rac htet bedeutet das Ausfüllen einer Fläche etwas a nde res als das Zeichnen von Linien. Eine wichtige Rolle spie len in der Compute rgrafik achsenpara llele Rechtecke, deren Se iten para llel zu den Koordi nat enachsen ve rlaufen. Sie sind zwa r Spezi alfälle von Polygone n, lassen sich aber einfache r d urch d ie Angabe zweier diago nal gege nüber liegen der Ecken , d. h. durch zwei Pu nkte spezifizie ren.
• A bbildung 2.9 Vereinigung, Durchschnitt , Differenz und symmet rische Differenz eines
Kreises und eines Rechtecks
Es ka nn se hr a ufwendig sein, komplexere Fläc hen durc h die d irekte Angabe de r Randkurve zu def inieren. Eine Mög lichkeit , aus bereits konst ruiert en Flächen komplexere aufzubauen , beste ht darin, me nge nt heoretische O perat ionen auf die Flächen anzuwe nden . Die wichtigsten diese r Operati onen sind Vereinigung, Dur chsch nitt, Differenz und sym met rische Differen z. Bei de r Vereinigung werde n zwei Flächen zusammengefügt, wä hre nd de r Durchschnitt aus dem gemeinsamen Teil beide r Flächen besteht . Die Differenz ergibt sic h, indem man von de r ersten
16
2 Grundlagen zweidimensionaler Darstellungen
Fläche alle Teile entfernt, die auch zur zweiten Fläche gehören. Die symmetrische Differenz entspricht der punktweisen exklusiven Oder-Verknüpfung der beiden Flächen. Die symmetrische Differenz besteht aus der Vereinigung der beiden Flächen ohne deren Durchschnitt. Abbildung 2.9 zeigt, was sich ergibt, wenn man diese Operationen auf einen Kreis und ein Rechteck anwendet. Geometrische Transformationen wie z.B. Skalierung, auf die später genauer eingegangen wird, bieten eine weitere Möglichkeit, aus bereits konstruierten Flächen neue zu erzeugen.
2.4
Geometrische Grundobjekte in Java 2D
Java 2D stellt alle im vorhergehenden Abschnitt beschriebenen Möglichkeiten zur Erzeugung von geometrischen Objekten zur Verfügung. Im Mittelpunkt steht dabei die abstrakte Klasse Shape , die mit ihren Unterklassen eine Reihe von zweidimensionalen geometrischen Grundobjekten ermöglicht. Shape-Objekte werden in vektororientierter Grafik definiert und können in reellen Koordinaten (float oder double) angegeben werden. Shapes werden erst gezeichnet, wenn in der paintMethode die draw- oder die fill-Methode mit dem entsprechenden Shape in der Form graphics2d .drawCshape) bzw. graphics2d .fillCshape) aufgerufen wird. Die Methode draw zeichnet nur den Rand des entsprechenden Shape-Objektes, während fill die gesamte durch das Shape-Objekt definierte Fläche ausfüllt. Die abstrakte Klasse Point2D für Punkte ist keine Unterklasse der Klasse Shape. Punkte können nicht direkt gezeichnet werden. Sollen tatsächlich einzelne Punkte dargestellt werden, kann dies über Geraden der Länge Eins realisiert werden. Objekte vom Typ Point2D dienen im Wesentlichen zur Spezifikation von Koordinaten , die in den meisten Fällen auch in Form zweier einzelner Werte direkt angegeben werden können. Aus diesem Grund wird die Klasse Point2D nur seIten in den Beispielprogrammen auftauchen. Die abstrakte Klasse Point2D wird von den Klassen Point2D . Float und Point2D . Double erweitert. Arbeitet man mit der abstrakten Klasse Point2D muss nicht vorher festgelegt werden, weIche Art der Fließkommaarithmetik - float oder die genauere Form double - verwendet werden soll. Dieses Konzept wird auch bei den meisten anderen geometrischen Objekten beibehalten. Alle folgenden geometrischen Grundobjekte in Java 2D erweitern die Klasse Shape und können daher mit Hilfe der Methoden draw und fill gezeichnet werden.
2.4 Geometrische Grundobjekte in Java 2D
17
Die abstrakte Klasse Line2D definiert Geradensegmente. Eine Möglichkeit, ein Geradensegment vom Punkt (x l ,yd zum Punkt (X2,Y2) anzugeben, ist die folgende: Line2D .Double line
=
new Line2D .Double(xl,yl,x2,y2);
Die Parameter xl, yl, x2 und y2 sind dabei vom Typ double. Entsprechend verwendet Line2D. Float Parameter vom Typ float. Es sei noch einmal darauf hingewiesen, dass dieses Geradensegment damit noch nicht gezeichnet wird. Dies erfolgt erst durch g2d . draw (Li.ne) . Analog zu Geraden werden quadratische Kurven mit der abstrakten Klasse QuadCurve2D modelliert. Die Definition einer quadratischen Kurve erfordert einen Anfangs-, einen End- und einen Kontrollpunkt. Es wird eine quadratische Kurve so durch den Anfangspunkt (x l ,yd und den Endpunkt (X2,Y2) gelegt, dass sich die Tangenten im Anfangs- und Endpunkt im Kontrollpunkt (crtl x ,crtly) schneiden, wie es durch die linke Kurve in Abbildung 2.7 veranschaulicht wird. Quadratische Kurven können z. B. auf die folgende Weise in Java 2D definiert werden. QuadCurve2D .Double qc
new QuadCurve2D.Double(xl,yl, ctrlx,ctrly, x2,y2);
Kubische Kurven verwenden statt eines Kontrollpunktes zwei, um die Tangenten im Anfangs- und Endpunkt festzulegen wie in der rechten Kurve in Abbildung 2.7 dargestellt. Java 2D stellt für kubische Kurven die abstrakte Klasse CubicCurve2D zur Verfügung, mit deren Unterklasse CubicCurve2D. Double folgendermaßen eine Kurve definiert werden könnte: CubicCurve2D .Double ce = new CubicCurve2D .Double(xl,yl, ctrlxl,ctrlyl, ctrlx2,ctrly2, x2,y2); Die Verwendung von Line2D, QuadCurve2D und CubicCurve2D wird in dem Programm CurveDemo. java exemplarisch gezeigt. Mit der Klasse GeneralPath können Kurvenzüge in Java 2D erzeugt werden, die aus Geradensegmenten, quadratischen und kubischen Kurven zusammengesetzt sind. Ein GeneralPath beginnt im Koordinatenursprung, d.h. im Punkt
2 Grundlagen zweidimensionaler Darstellungen
18
(0,0) . In der Klasse General Path werde n vier Met hode n zur stückweisen Definiti on eines Kurvenzuges zur Verfügung gestellt. Mit diesen Met hoden wird ein ent sprech end es Kurven stü ck an den Endp unkt des zuletzt defin ierten Kurvensegments des Gene ralPa t h angehä ngt . Mit H ne'ro. qu adTo oder cur veTo wird ein Geradensegment, eine qua dr atisch e bzw . eine kub ische Kurve als näc hstes Kurvensegment angefügt. Diese d rei Meth oden werden im Ge ne ral Pat h ana log z u Line 2D, QuadCurve 2D un d Cub icCur ve2D verwendet mit de m Unterschied, dass beim GeneralPath jeweils ein Param eter weniger s pezifiziert wird . Der fehlende Paramet er ist der Anfangspunkt, de r durch den Endpunkt des vorherge hende n Kurvensegments im entsprechende n GeneralPath bereits festgeleg t ist . Die Koordinaten der Punkte müssen als fl oat-Werte angeg eben werden. Neben den drei Kurvenformen gibt es beim GeneralPath noch die Möglichkeit, mit der Met hode move To ohne jegliche Verbindungskurve zu einem Punk t zu spnngen. 50 70 90 110 1]0 150 170 190 60 SO 100
no 140
~-)
Abbildung 2.10 Beispiel für einen GeneralPath Abbildung 2.10 zeigt de n Umriss eines Aut os, der mit Hilfe des folgenden Gen eralPath erzeugt wurde: GeneralPath gp
=
new Ge ne ral Pat h( ) ;
//Beg i nn e an de r vorder en unteren Ecke des Autos gp . move To (6 0 , 120); gp .lineTo( 80,12 0) ; / / vorderer Unt e r bo de n gp. quadTo (90 , 140 , 100 , 120);//Vor de r r e i f en gp .line To ( 160 , 120) ;//mit tlerer Unt er boden gp. quadTo ( 170 , 140 , 180 , 120) ;//Hint e r r ei f en gp .lineTo( 200 ,1 20) ; / /hint erer Unt erboden gp . curveTo(195,100,200, 80,160 , 80) ; / /He ck gp. line To ( 110 ,80);//Dac h
2.4 Geometrische Grundobjekte in Java 2D
19
gp .lineTo(90,100);//Frontscheibe gp .lineTo(60,100);//Motorhaube gp.lineTo(60,120);//Front g2d .draw(gp);//Zeichne das Auto Das eingeblendete Koordinatensystem bezieht sich auf die Fensterkoordinaten. Die vollständige Klasse, in der das Auto gezeichnet wird, ist die Datei GeneralPathCar . java. Eine Fläche, bzw. deren Rand, lässt sich durch geschlossene Kurvenzüge in Form eines GeneralPath-Objektes definieren. Java 2D stellt außerdem achsen parallele Rechtecke und Ellipsen als geometrische Grundobjekte bereit. Mit der Klasse Rectangle2D .Double, die die abstrakte Klasse Rectangle2D erweitert, kann folgendermaßen ein Rechteck definiert werden: Rectangle2D.Double r2d = new Rectangle2D .Double(x,y,width,height) ; Das Rechteck wird durch die beiden diagonal gegenüber liegenden Eckpunkte (x ,y) und (x + w idt h ,y + height) aufgespannt. Berücksichtigt man, dass die y-Achse im Darstellungsfenster nach unten zeigt, wird ein Rechteck definiert, dessen obere linke Ecke sich an der Position (x ,y) und dessen untere rechte Ecke sich an der Position (x + widt h,y + height) befindet. Abbildung 2.11 zeigt links ein Rechteck das mittels Rectangle2D .Double r2d = new Rectangle2D .Double(50,60,150,100); erzeugt wurde. Es sei noch einmal darauf hingewiesen, dass dieses Rechteck damit nur generiert wird, genauso wie bei allen anderen Shape-Objekten, die schon besprochen wurden. Gezeichnet wird das Rechteck erst beim Aufruf der Methode g2d . draw (r2d). Analog zu Rechtecken lassen sich achsenparallele Ellipsen mit Java 2D definieren. Eine Ellipse wird durch das sie umschreibende Rechteck festgelegt, das über dieselben Parameter wie bei Rectangle2D spezifiziert wird. Die in Abbildung 2.11 dargestellte Ellipse wurde mittels Ellipse2D.Double elli = new Ellipse2D .Double(250,60,150,100);
20
2 Grundlagen zweidimensionaler Darste llungen
60
so 100
IlO HO 160
ISO Abbildun g 2.11
Beispiel für ein Rechteck und eine Ellipse
ge neriert. Zur Vera nscha ulichung ist das umschreibende. d .h. das definierende Rech teck de r Ellipse in Abbi ldung 2.11 mit eingeze ichnet . Zur Erzeugung de r Abb ildung wurde die Klasse Rect angleEllipseExample . j a va verwendet . Ein Kreis ist ein Spezialfall einer Ellipse . be i der das umsch reibende Rechteck ein Quad rat ist . Ein Kreis mit dem Mit telpunkt (x, y ) und de m Radius r lässt sich mittels
Ell i ps e2D .Doubl e ci rc l e = nev El l ipse2D.Double (x -r ,y-r,2*r.2*r) ; erzeugen.
Mit der Klasse Ar c2D lassen sich Ell ipsenbögen und damit auch Kreisbögen def inieren.
Arc2D.Do uble are
= new
Arc2D. Double(rect2D,st art,extend ,type) ; • re ct 2D spe zifiziert Rec tangle2D.
das
umschreiben de
Rechteck
de r
Ellipse
als
• start ist der W inkel bezogen auf das umschreibende Rechteck, be i dem de r Bogen beginnen soll. Der W inkel wird als fl oat -Wert in Grad angegeben" . Der W inkel entspricht nur im Falle eines Kreises dem Winkel zur x-Achse. Ansonsten wird de r W inkel relat iv zum Rechteck bestimmt . Ein Winkel 2 Ar c 2D ist die einzige Ausna hme, bei der Winkel in Grad angegeben werden. Ansonsten
werden Winkel immer im Bogenma ß spezifiziert .
2.4 Geome t rische Grundobjekte in J ava 2D
21
von 45 0 bedeutet beispie lsweise, dass der Startpu nkt des Bogens auf der Verbindu ngslinie des Rechteckmittelp unktes mit de r rechten oberen Ecke liegt . • e xtend ist der Öffnungswinkel. d. h., der Bogen wird von star t bis start + e xtend gezeichnet (bezogen a uf das umschr eibende Rechteck). Auch dieser Winkel wird als fl oat-Wert in Grad angegeben. • type kan n einen de r d rei We rte Ar c 2D.OPEN. Arc2D.PIE und Arc2D. CHORD a nnehmen und gibt an. ob nur der Ellipsen bogen , de r EIlipsenausschnitt bzw. de r Ellipsena bschnitt konst ruiert werden soll. Abbildung 2.12 zeigt vo n links nac h rechts einen Ellipsenbogen, einen Ellipsenau sschnitt und einen Ellipsenabschnitt . In alte n Fällen wurde a ls Sta rtwinkel 450 und a ls Öffnungswinkel 90 0 gewählt. Die umsc hreibenden Rechtecke der zug runde liegenden Elli psen wurden zur besse ren Vera nscha ulichung mit eingezeichnet . Ma n sieht hier deutlich, dass der Startw inkel mit 45 0 bewirkt , dass de r Bogen auf der Verbind ungslinie des Rechteckmittelpunktes mit der recht en oberen Ecke begin nt . Der Winkel dieser Verbindu ngslinie mit der x-Achse ist jedoch kleiner als 450 , da ein breites , aber niedriges umschreibend es Rechteck verwendet wurde. Das Gleiche gilt für den Öffnungswinkel. Auch dieser W inkel beträgt nicht 90 0 , so ndern entspricht dem W inkel zwischen den be iden Verbin dungsstrecken vom Rechteckmittelpunkt zur rechte n bzw. linken oberen Ecke. Ein Beispiel für d ie Verwend ung von Arc2D findet sich in der Dat ei ArcExampl e . j a va. mit der a uch Abb ildung 2.12 erzeugt wurde .
Abbildun g 2.12 Ein Ellipsenbogen. ein Ell ipsenausschnitt und ein Ellipsenabschnitt Neben de r Möglichkeit, Flächen mittels gesc hlossener Kurvenzüge in Form eines Ge ne r a lPa th zu definieren, wurde am Ende des Abschnitts 2.3 ein Verfa hren erk lärt, das auf den mengen t heoret ischen Operat ione n Vereinigung. Durchsc hnitt , Differenz und symmetrische Differenz beruht . Aus bereits erzeugten Flächen kö nnen mit diesen Operationen neue Flächen definiert werden. In J ava 2D dient d ie Klasse Area d iesem Zweck. Aus einem Shape-Objekt s , z.B . einem Rec tangle2D , einer El lips e2D, einem gesch lossenen Gene ralPath oder einem Arc2D, der einen Ellipse naus- oder -a bschnitt darstellt . kann mittels
22
2 Grundlagen zweidimensionaler Darstellungen
Area a
=
new Area(Shape s);
ein Area-Objekt der entsprechenden Form erzeugt werden. Für derartige AreaObjekte stehen die oben erwähnten Mengenoperation zur Kombination zur Verfügung. Sind areaA und areaB zwei Area-Objekte, können die folgenden Methoden verwendet werden. • areaA . add Careaß) vereinigt areaA mit areaB. • areaA . intersect (areaB) schneidet areaA mit areaB. • areaA . subtract (areaB) liefert areaA ohne areaB, d.h. die Differenz. • areaA . exclusiveOr(areaB) liefert die Vereinigung von areaA mit areaB ohne den Durchschnitt, d.h. die symmetrische Differenz. Das Area-Objekt areaA enthält jeweils das Ergebnis der Mengenoperation. Ein Area-Objekt kann genau wie ein Shape-Objekt mit den Methoden draw, die nur den Rand zeichnet, und fill, die die gesamte Fläche ausfüllt, gezeichnet werden. Die Datei AreaExample .java, mit der auch Abbildung 2.9 auf Seite 15 erzeugt wurde, verdeutlicht die Verwendung von Area-Objekten.
2.5
Geometrische Transformationen
Neben den geometrischen Objekten spielen geometrische Transformationen eine wesentliche Rolle in der Computergrafik. Geometrische Transformationen werden dazu verwendet, Objekte zu positionieren, d.h. zu verschieben oder zu drehen, sie zu verformen, z.B. in einer Richtung zu strecken oder zu stauchen , oder um Bewegungen oder Veränderungen von Objekten in animierten Grafiken zu realisieren. Bevor näher auf die geometrischen Transformationen eingegangen wird, sollen noch einige Konventionen vereinbart werden. In der Computergrafik verwendet man sowohl Punkte als auch Vektoren, die beide formal als Elemente des IRn repräsentiert werden. Insbesondere in der Physik ist eine saubere Unterscheidung dieser beiden Konzepte erforderlich. Im Rahmen dieses Buches und aus der Sicht der Computergrafik wird häufig zwischen beiden Interpretation als Punkt und als Vektor gewechselt, so dass hier mit diesen Begriffen zum Teil sehr flexibel umgegangen wird. Ein Tupel (Xl, ... ,X n ) E IRn kann in einer Gleichung als Punkt und in der nächsten als Vektor interpretiert werden. Die Physiker mögen uns
23
2.5 Geometrische Transformationen
diese Nachlässigkeit verzeihen. In Gleichungen werden in diesem Buch generell Spaltenvektoren verwendet. Im Text werden Punkte manchmal als Zeilenvektoren notiert, um nicht unnötig hohe Zeilen zu verursachen. In den Fällen, wo ein Punkt explizit im Sinne eines Spaltenvektors verwendet wird, wird in der Regel das Symbol für das Transponieren an den Punkt geschrieben, d.h., er wird in der Form (x ,y) T E IR2 bzw. (x ,y,z) T E IR3 dargestellt. Das Skalarprodukt zweier Vektoren u und v wird hier folgendermaßen notiert: n UT .
v =
(Ul " "
,u n )
Vnl
. (
)
L
Ui ' Vi
i= l
V
Die wichtigsten geometrischen Transformationen sind Skalierung, Rotation, Scherung und Translation. Skalierungen bewirken Streckungen oder Stauchungen in x - und y-Richt ung. Der Punkt (x ,y) wird bei einer Skalierung S (sx,Sy ) auf den folgenden Punkt (x' ,y' ) abgebildet: (
X' )
y'
x) =
Sx' ( "v :Y
(
sx
0
0) ( Yx)
Sy
.
ist der Skalierungsfaktor in x-Richt ung. Es liegt genau dann eine Streckung in x-Richt ung vor, wenn Isxl > 1 gilt. Bei Isxl < 1 handelt es sich um eine Stauchung. Ist der Wert Sx negativ, wird zusätzlich zur Streckung oder Stauchung in x-Richt ung noch eine Spiegelung an der y-Achse vorgenommen. Entsprechend bewirkt Sy eine Streckung oder Stauchung in Richtung der y-Achse und bei einem negativen Wert zusätzlich eine Spiegelung an der x-Achse. Sx
Eine Skalierung ist - wie alle anderen geometrischen Transformationen auch immer punktweise zu verstehen, auch wenn sie auf Objekte angewendet wird. Als Beispiel wird hier die Skalierung mit Sx = 2 und Sy = 0.5 betrachtet, die in Richtung der x-Achse auf das Doppelte streckt und Richtung der y-Achse auf die Hälfte staucht. Wendet man diese Skalierung auf das Rechteck an, dessen linke untere Ecke sich im Punkt (80,120) und dessen obere rechte Ecke sich im Punkt (180,180) befindet , so ist das resultierende Rechteck nicht nur doppelt so breit und halb so hoch wie das ursprüngliche, sondern auch nach rechts und nach unten verschoben. Abbildung' 2.13 zeigt das Ausgangsrechteck und gestrichelt das skalierte Rechteck. Die Skalierung bezieht sich immer auf den Koordinatenursprung. Sofern ein Objekt nicht im Ursprung zentriert ist, bewirkt eine Skalierung daher immer eine zusätzliche Verschiebung des Objekts. 3
Die Abbildung ist in der übli chen Repräsentation dargestellt und nicht in der Java 2D t ypischen Koordinatenrepräsentation mit der nach unten gerichteten y-Achse.
24
2 Grundlagen zweidimensionaler Darstellungen 200 180 160 140
120 100
D
80
60 40
20
Abbi ldung 2.13
Skalierung am Beispiel eines Rechtecks
Eine weitere wicht ige geometrische T ransformati on ist die Rotation, die durch die Angabe eines Winkels definiert wird. Die Rot ation erfolgt um den Koordinaten ursprung entgegen dem Uhrzeigersinn bzw. mit de m Uhrzeigersi nn , wenn der Wi nkel negat iv ist . Die Rotation R(O ) um den Winkel () bildet den P unkt (x ,y) auf den folgenden Pu nkt (xl, y' ) a b:
('0, (0) u , m(O) ) ( .y'r' ) _ ( xx.. sin(B) +y . r
co~ (8 )
~ ( (,0,(0)
sin(O)
x)
- , in(O) ) . ( cos(8) y
Da sich die Rotation immer auf den Koordinat enursprung bezieht, bewirkt eine Rotation eines nicht im Koordi natenu rspr ung zentrierten Objektes, genau wie bei de r Skalie rung, eine zusätzl iche Verschiebung des Objekts . In Abb ildung 2.14 wurde eine Rotation um 45° ausgeführt, die das Ausgangsrechteck auf das gestrichelte Rechteck abbildet . Als vorletzte , elementa re geometrische Tra nsformation bet rachten so ll die Scherung eingeführt werden , die eine Verzerrung eines Objektes bewirkt . Eine Scherun g wird wie eine Skalierung d urch zwei Para meter defi niert mit dem Unterschied, dass die beiden Para meter in der Nebend iagonalen und nicht in der Hau ptd iagona len der entsprechenden Matrix stehen. Lässt ma n eine Scherung Sh(:c;x,:C;y} auf den Pu nkt (x ,y) wirken, erhält man de n folgenden P unkt (Xl,yl):
Ana log zu Ska lieru ng und Rotation bezie ht sich die Scherung a uf de n Koord inat enurs prung, so dass ein nicht im Koordinaten urspr ung zentriertes Objekt bei
2.5 Geome t rische Tra nsformat ionen
25
"-
200 180
160 140
120 100 80 60 40 20
/
/ /
""/
"
/ /
)
D
20 40 60 80 100120140160180200
Ab bildung 2.14 Rotation am Beispiel eines Rechtecks
einer Sc herung zusätzlich zu der Verzer rung noc h versc hoben wird. In Abb ildu ng 2.15 ergibt sich das gestrichelte Rechteck, inde m man d ie Scherung mit den Parametern .~x = 1 und Sy = 0 auf das Ausgangsrechteck anwendet . 200
180 160 140 120 100 80 60 40 20
L/
---7
__ /
20 40 60 80 100120 140 160 180200 220 240 260 280 300 320
Abbildung 2.15 Scherung am Beispiel eines Rechtecks
26
2 Grundlagen zweidimensionaler Darstell ungen
Da hier Sy = 0 gilt, spricht ma n vo n einer Scherung in y· Richt ung. Bei einer Sc he rung in x - Richt ung muss S x = 0 ge lte n.
Die letzte noc h zu bet rachtende elementare geomet rische Transformation ist zwar relat iv einfac h, unterscheidet sich aber wesent lich von den dre i bishe r eingefü hrten T ransformati onen . Die Translation T (dx.dy) bew irkt eine Verschiebung um eine n gegebe nen Vektor d = (dx,dy)T, d.h., de r Pu nkt (x ,y ) wird a uf den Punkt
abgeb ildet. Abbildung 2.16 zeigt eine Tra nslat ion eines Rechtecks um den Vektor d (140,80)T .
180 160 14ll
120 100 80 60
I L
1
4ll
20 20 40 60 80 1001 201 40 160 180 200 220240260 280
Abb ildun g 2.16 Translation arn Beispiel eines Rechtecks
Im Gegensatz zu de n vorher besp rochenen T ransformationen. die a lle lineare Abbildunge n sind, lässt sich eine Translat ion nicht durch eine Matrixmultip likat ion repräsentieren. Bei einer Matrixmulti plikation wird der Nullvektor, d. h. de r Koordinatenursp rung, immer auf sich selbst a bgebildet . Eine T ranslat ion versc hiebt jedoch alle Pun ke, a uch den Koord inatenu rspru ng . Tra nslationen zäh len zu den affine n, aber nicht zu de n linearen Abbi ldunge n. In de r Computergraf ik werde n komplexere Tra nsformati onen hä ufig d urch d ie Hintereina nderschaltu ng elementarer geometrische r Tra nsformationen erzeugt. Eine Transform ation, d ie sich aus einer Hintereina ndersch altu ng ve rschiede ne r Ska lierungen, Rotatio nen und Sche runge n erg ibt, wird d urch die Mat rix besch riebe n, die ma n durc h Mult iplikat ion der zu den en tsprec hend en elemen taren
2.6 Homogene Koordinaten
27
Transformationen gehörenden Matrizen erhält. Werden auch Translationen verwendet, lässt sich die zusammengesetzte Transformation nicht mehr auf diese einfache Weise errechnen und repräsentieren. Es wäre sowohl vom Speicheraufwand als auch vom Rechenaufwand günstig, wenn sich alle mit geometrischen Transformationen zusammenhängenden Operationen auf Matrixmultiplikationen zurückführen ließen. Um dies zu ermöglichen, verwendet man eine andere Koordinatendarstellung der Punkte , bei der sich auch die Translation in Form einer Matrixmultiplikation beschreiben lässt. Diese alternative Koordinatendarstellung nennt man homogene Koordinaten, die im folgenden Abschnitt genauer erklärt werden.
2.6
Homogene Koordinaten
An dieser Stelle werden homogene Koordinaten für Punkte in der Ebene eingeführt. Dieselbe Technik wird später auch für den dreidimensionalen Raum verwendet. Homogene Koordinaten verwenden zur Darstellung von Punkten eine zusätzliche Dimension. Der Punkt (x ,y,z) in homogenen Koordinaten wird mit dem Punkt
( ; , ~)
in kartesischen Koordinaten identifiziert. Die z-Komponente
eines Punktes in homogenen Koordinaten darf niemals den Wert Null annehmen. Soll der Punkt (xo,Yo) in homogenen Koordinaten repräsentiert werden, kann die Darstellung (xo,Yo ,1) verwendet werden. Dies ist jedoch nicht die einzige Repräsentation. Jede Darstellung (z · Xo,Z ' Yo ,z) mit z i= 0 ist ebenfalls korrekt. Die Punkte {(x,y,z ) E IR3 I (x ,y,z) = (z · Xo,Z . Yo,z)} liegen alle auf der Geraden im IR3 , die durch das Gleichungssystem
x - Xo' z Y - Yo ' z
0 0
definiert wird und die durch den Koordinatenursprung verläuft. Jeder Punkt auf dieser Geraden, ausgenommen der Koordinatenursprung, repräsentiert den Punkt (x o,Yo) in homogenen Koordinaten. Wählt man für die Darstellung in homogenen Koordinaten einen festen z-Wert , z.B. z = 1, werden alle Punkte in der zur .7:/YEbene parallelen Ebene mit dem entsprechenden z-Wert repräsentiert.
28
2 Grundlagen zweidimensionaler Darstellungen
Abbildu ng 2.17 vera nschau licht d iese Zusammenh änge. Alle P unkte a uf der dargeste llten Gerade n repräsentieren de nselben Pun kt im rrt2 . Fixiert man einen
z-Wert , z.B. eine der eingezeichnete n Ebenen, so lassen sich die Punkte des IR2
in der ents preche nden Ebene repräse ntieren.
z
y
+ x
IL.-
Abbildun g 2.17
Homogene Koordinaten
Der Koordinat enur sprung in kartesischen Koordinaten entspricht in homogenen
Koordinaten einem Punkt der Form (O,O,z). Eine lin eare Abbildung bezogen auf homogene Koordinat en, d.h. eine lineare Abbildung im IR3 , muss diesen Punkt nicht mehr notwendigerweise als Fixpunkt besitzen. Die lineare Abbildung kann diesen Pu nkt auf einen a nde ren P unkt in homogenen Koordinaten abbilden . Eine Tra nslat ion lässt sich in homogenen Koordin at en a ls Matrixmu lt iplikatio n d arstellen:
o 1
o Die an deren eleme nt aren geo met rischen T ransformat ionen lassen sich proble mlos auf homogene Ko ordinaten erweite rn, so dass ma n folgend e T ransformationsmat rizen erhä lt:
29
2.6 Homogene Koordinaten
Transformation
Translation
Skalierung
Rotation
Scherung
Kurzform
Matrix
( (
1 0 dx 0 1 dy 0 0 1
T(dx ,dy)
Sx 0 0
S (sx ,Sy)
(
R(B)
0 Sy 0
0 0 1
) )
cos(B) sin( B)
- sin(B)
0
0
(
1 Sy 0
S( sx,Sy)
cos(B) Sx 1 0
0 0 1
0 0 1
)
)
Rotationen und Translationen erhalten Längen und Winkel. Skalierungen und Scherungen erhalten im Allgemeinen weder Längen noch Winkel, aber zumindest Parallelität von Linien. Die Hintereinanderausführung von geometrischen Transformationen lässt sich in homogenen Koordinaten daher mittels Matrixmultiplikation realisieren. Die eingeführten Matrizen für die elementaren Transformationen sind alle von der Form
cef ) .
d
o
(2.1)
1
Das Produkt zweier solcher Matrizen ergibt wiederum eine Matrix dieser Form, wie sich leicht nachrechnen lässt. Geometrische Transformationen werden in der Computergrafik daher üblicherweise in dieser Form repräsentiert und gespeichert. Dies gilt nicht nur für Transformationen, die in der Ebene operieren, sondern in ähnlicher Weise ebenso für räumliche Transformationen, die im Kapitel 5 behandelt werden. Eine Grafikkarte eines Rechners muss daher unter anderem Vektor- und Matrixoperationen schnell ausführen können. Bei der Hintereinanderschaltung von Transformationen ist zu berücksichtigen, dass die Reihenfolge, in der die Transformationen ausgeführt werden, eine Rolle spielt. Die Matrixmultiplikation ist eine nicht-kommutative Operation. Abbildung 2.18 zeigt im rechten Teil die unterschiedlichen Ergebnisse, die man erhält, wenn man im einen Fall zuerst eine Translation um den Vektor (40,20) T und
30
-80-60-
2 Grundlagen zweidimensionaler Darste llungen
so
ee
(I)
(I)
'"
20
-20
401 --
20
00 00
-30 .60 ·40
-::0
20
-
,
20 40 60 80
-80 _60 _40 _~
·40
-40
-40
. (1)
-60
-60
.80
-80
_80
Original
Tra nslation
20 40 60 80
1. Translat ion, 2. Rotat ion 80 (I)
40 20
-SO _60 .4:1 _20
-80 -60
.20
.40 . (1)
.(1)
.80
.80
Rotation
1. Rotat ion , 2. T ra nslat ion
Abb ildung 2.18 Unterschiedliche Ergebnisse bei Verta uschung der Reihenfolge von Tra nslat io n und Rot at ion
da nn eine Rota t ion um 45° und im a nderen Fall in der umgekehrten Reihenfolge au f das Rechteck im linken Teil de r Abb ildung an wendet . Dieser Effekt t ritt
nur auf, wenn man unt erschiedliche Tra nsformat ionen miteina nder verknüpft. Bei der Hintereina ndersch a ltu ng gleicha rt iger T ransformat ionen. d.h. nur Rotationen, nur Tran slat ionen, nur Ska lierungen oder nur Scheru nge n, spie lt die Reihenfolge keine Rolle. Man sol lte auße rde m beachten, dass bei de r Matrixnotat ion oder der Notation von T ransformationen a ls Abb ildungen die T ransformationen von rechts nach links ausgefü hrt werden. Die Transformation
(T (d",l,)
0
R(O))(v )
bzw. in Mat rixnotat ion
0
0 d, 1 d, 0 1
)(
eos (O) sin (O) 0
- sin(O) co, (O) 0
0 0 1
)v
31
2.7 Anwendungen von Transformationen
bedeutet, dass zuerst die Rotation R(B) und dann die Translation T(dx,dy ) auf den Punkt v angewendet wird.
2.7
Anwendungen von Transformationen
In diesem Abschnitt werden einige Beispielanwendungen und Probleme erläutert, die sich mit Hilfe von geometrischen Transformationen lösen lassen. In der Computergrafik ist es üblich, Objekte in beliebigen Koordinaten in Fließpunktarithmetik, den Weltkoordinaten, zu spezifizieren. Für die Erzeugung einer konkreten Grafik muss ein rechteckiges Fenster, der Viewp ort, angegeben werden , das den auf dem Bildschirm oder sonstigen Ausgabegerät sichtbaren Bereich der" Objektwelt" definiert. Es muss daher eine Abbildung von den WeItkoordinaten zu den Geräte- bzw. Bildschirmkoordinaten berechnet werden.
Fenster in Weltkoordinaten, im Weltkoordinatenursprung y
,....---e ax'Jnax ) I
I
I
I
y
x
' - - - - - + - - - - --0-- X
(Xmin 'Jnin )
v
v
(Umin ,Vrnin )
L...1...--L...
0 6. ist immer ganzzahlig, das heißt, die Entscheidungsvariable d ändert sich nur um ganzzahlige Werte.
6.
Um den Wert der Entscheidungsvariablen d in jedem Schritt berechnen zu können, wird zusätzlich zur Änderung von d noch der Ausgangswert von d benötigt. Dieser ergibt sich, indem man den ersten Mittelpunkt in die Gleichung (3.5) einsetzt. Das erste Pixel auf dem zu zeichnenden Geradensegment besitzt die Koordinaten (XO ,yo). Der erste zu betrachtende Mittelpunkt ist daher (xo + 1,yo + ~), so dass sich der erste Wert der Entscheidungsvariablen folgendermaßen berechnen lässt: dinit
F ( xo
+ 1,yo + ~)
dy · (xo
+ 1) -
dx . (YO
dy . Xo - dx . Yo F(xo ,yo) + dy -
+ ~) + C dx
+ C + dy - T dx
T
dx dY-T Der Wert F( xo ,yo) ist Null, da der Punkt (XO ,yo) nach Voraussetzung auf der zu zeichnenden Geraden liegt. Leider ist der Anfangswert dinit im Allgemeinen nicht ganzzahlig, außer wenn dx gerade ist. Da dx zumindest immer ganzzahlig ist, kann man dieses Problem umgehen, indem man statt der Entscheidungsvariablen d die Entscheidungsvariable D = 2· d betrachtet, d.h. für die Geradengleichung anstelle der impliziten Form (3.5) die ebenfalls implizite Darstellung
3 Zeichnen von Kurven
58
D = F(.'E,y) = 2· F(x ,y) = 2 · dy · x - 2 . dx . y + 2 . C = 0 verwendet. Für die Bestimmung des zu zeichnenden Pixels spielt es keine Rolle, welche der beiden Entscheidungsvariablen d und D = 2· d verwendet wird, da es jeweils nur auf das Vorzeichen der Entscheidungsvariablen ankommt. Für die Initialisierung und die Anderung von D erhält man: Dinit
2 · dy - dx
D neu
Dal t
+ ,6.
(3.7) mit
2· dy { 2· (dy - dx)
falls Dal t < 0 falls Dal t > 0
(3.8)
Die Entscheidungsvariable D nimmt nur ganzzahlige Werte an. Für die Initialisierung von D ist eine Multiplikation und eine Subtraktion erforderlich. Außerdem sollten die beiden Werte von ,6. ebenfalls im Anfang einmal vorausberechnet werden, wozu weitere zwei Multiplikationen und eine Subtraktion durchgeführt werden müssen. Bei der Aktualisierung von ,6. ist in jedem Schritt nur eine einzige Addition nötig.
dx dy
6-3
8 3 6
,6. NO
2 · dy 2· (dy - d.'E)
Dinit
2 · dy - dx
-2
Dinit+l
Dinit
Dinit+2
Dinit+l
4 (NO) -6 (0)
,6.0
Dinit+3 Dinit+4 Dinit+5 Dinit+6 Dinit+7 Dinit+8
Tabelle 3.1
10 - 2
+ ,6.0 + ,6. NO Dinit+ 2 + ,6.0 Dinit+ 3 + ,6.0 Dinit+4 + ,6. N O Dinit+7 + ,6.0 Dinit+ 6 + ,6. NO Dinit+7 + ,6.0
-10
0
(0)
(O ?)
6 (NO) - 4 (0) 2
(NO)
- 8 (0) -2
Rechenschritte des Mittelpunktalgorithmus am Beispiel des Geradensegments vom Punkt (2,3) bis zum Punkt (10,6)
3.2 Der Mittelpunktalgorithmus für Geraden
59
Ein Beispiel soll die Funktionsweise dieses Algorithmus, der auch Mittelpunktalgorithmus oder nach seinem Erfinder Bresenham-Algorithmus genannt wird, verdeutlichen. Es soll das Geradensegment vom Punkt (2,3) bis zum Punkt (10,6) gezeichnet werden. Damit ergeben sich die in Tabelle 3.1 angegebenen Werte. 7,....-.--...---.----.---.-----r-----.----.---,---,
61--+--t-+-+-+-+--t- _ _H 5 I--+--t-+-+--+-i 4
I--+--I-t_
3 2 1 2 3 4 5 6 7 8 9 10 11 Abbildung 3.5
Zeichnung eines Geradensegments mit dem Bresenham-Algorithmus
Nachdem das Startpixel (2,3) gesetzt wurde, ergibt sich der negative Wert -2 für Dinit, so dass als nächstes das östliche Pixel zu zeichnen ist und die Entscheidungsvariable sich um ßo = 6 ändert. Damit wird die Entscheidungsvariable positiv, das nordöstliche Pixel ist zu zeichnen und die Entscheidungsvariable wird um ß NO geändert. In diesem Schritt ergibt sich der Wert Null für die Entscheidungsvariable, das heißt, die Gerade verläuft genau in der Mitte zwischen den nächsten beiden Pixelkandidaten. Hier sei festgelegt, dass in diesem Fall immer das östliche Pixel gezeichnet werden soll. Die restlichen Werte lassen sich entsprechend berechnen. Abbildung 3.5 zeigt das gezeichnete Geradensegment. Die Voraussetzung für die Anwendung dieses Algorithmus war, dass die Steigung der zu zeichnenden Geraden zwischen Null und Eins liegt. Es wurde bereits erwähnt, dass bei einer Steigung, deren Betrag den Wert Eins überschreitet, die Rollen der .'C- und y-Achse bei den Berechnungen zu vertauschen sind, das heißt, es werden die y- anstelle der x-Koordinaten beim Zeichnen in Einerschritten durchlaufen. Auf diese Weise erhält man immer Geraden, deren Steigung zwischen -1 und 1 liegt. Für Geraden mit einer Steigung zwischen -1 und o lassen sich völlig analoge Überlegungen anstellen , wie für Geraden mit einer Steigung zwischen 0 und 1. Anstatt des "nordöstlichen" Pixels muss nur jeweils das" südöstl iche" betrachtet werden. Eine wesentliche Voraussetzung für den Mittelpunktalgorithmus besteht in der Annahme, dass das zu zeichnende Geradensegment von zwei Punkten begrenzt wird, die ganzzahlige Koordinaten besitzen, d.h. auf dem Raster liegen. Bei der ModelIierung des Geradenstücks in vektororientierter Grafik muss diese Voraus-
60
3 Zeichnen von Kurven
setzung keineswegs gegeben sein. In diesem Fall zeichnet man das Geradensegment, das sich aus der Verbindung des gerundeten Anfangs- und Endpunktes des Geradensegment ergibt. Dadurch werden beim Zeichnen des gesamten Geradensegments im Allgemeinen nicht dieselben Pixel gesetzt, die sich durch direktes Runden wie beim naiven Algorithmus vom Anfang dieses Kapitels ergeben würde. Die Abweichungen betragen jedoch höchstens ein Pixel und sind daher tolerierbar.
3.3
Strukturelle Algorithmen
Der Mittelpunktalgorithmus benötigt neben der einmaligen Initialisierung zu Beginn n ganzzahlige Rechenoperationen zum Zeichnen eines aus n Pixeln bestehenden Geradensegments, so dass der Rechenaufwand linear in der Anzahl der Pixel ist. Strukturelle Algorithmen zum Zeichnen von Geraden verringern diesen Rechenaufwand noch weiter, indem sie sich wiederholende Stufenmuster ausnutzen, die beim Zeichnen einer Geraden auf einer Rastergrafik auftreten. Abbildung 3.6 zeigt ein derartiges Stufenmuster, das eine Gesamtlänge von fünf Pixeln besitzt. Um das sich wiederholende Muster zu verdeutlichen, wurden die gezeichneten Pixel unterschiedlich markiert. Das Grundmuster in Abbildung 3.6 besteht aus einem Pixel (ausgefüllter Kreis), zwei nebeneinander liegenden Pixeln diagonal über dem ersten Pixel (nicht ausgefüllte Kreise), gefolgt von zwei weiteren nebeneinander liegenden Pixeln diagonal darüber liegend (nicht ausgefüllte Doppelkreise). Bezeichnet Deinen Diagonal- (Zeichnen des " nordöst lichen" Pixels) und H einen Horizontalschritt (Zeichnen des "östlichen" Pixels), so lässt sich die Gerade durch das Muster DHDHD beschreiben. Würde man das Geradensegment aus Abbildung 3.5 auf Seite 59 nicht beim Punkt (10,6) enden lassen, sondern weiterzeichnen, würde sich das dort zu erkennende Muster HDHHDHDHD wiederholen. Dies lässt sich auch aus den Berechnungen des Mittelpunktalgorithmus in Tabelle 3.1 auf Seite 58 ablesen. Der anfängliche Wert der Entscheidungsvariablen Dinit ist identisch mit dem letzen Wert Dinit+8 in der Tabelle , so dass sich dieselben Berechnungen ergäben, wenn man den Mittelpunktalgorithmus fortführen würde. Da bisher immer davon ausgegangen wurde, dass ein zu zeichnendes Geradensegment durch einen Startpunkt (x a,Ya) und einen Endpunkt (Xl ,Yl) auf der Rastergrafik definiert wird, sind die Werte Xa,Ya,XI ,YI ganzzahlig und mit ihnen auch die Werte dx = Xl - Xa und dy = YI - Ya. Die zu zeichnende Gerade besitzt daher eine rationale Steigung ~; . Beim Zeichnen der Geraden müssen die v-Werte
61
3.3 Strukturelle Algorithmen
. k\""
«
I' rv: ~
« F\'V r v: -K: ~ ~
....
'W; ~
~"
.//
~ f?'-. V
.... ~ ?\.. ./
~~~ rv; I' rK' ~ .// ... ~ f:?\. V
"
,..,
Abbildung 3.6
Ein sich wiederholendes Stufenmuster beim Zeichnen einer Geraden
dy (3.9) - .x +b dx mit ebenfalls rationaler Konstante bund ganzzahliger Laufvariable x gerundet werden, egal ob man dies explizit wie beim naiven Geradenalgorithmus oder implizit mit dem Mittelpunktalgorithmus durchführt. Es ist offensichtlich, dass sich dadurch bei der Berechnung der y-Werte (3.9) nur endlich viele verschiedene Reste ergeben können. Aus diesem Grund liegt jedem auf einer Rastergrafik zu zeichnenden Geradensegment ein sich wiederholendes Muster zugru nde, auch wenn es unter Umständen sehr lang sein kann. Strukturelle Algorithmen zum Zeichnen von Geradensegmenten nutzen diese Tatsache aus und bestimmen das jeweilige Grundmuster, das das Geradensegment beschreibt. Im Gegensatz zum linearen Rechenaufwand in der Anzahl der Pixel des Mittelpunktalgorithmus benötigen strukturelle Algorithmen nur einen logarithmischen Aufwand. Wie bereits beim Mittelpunktalgorithmus wird die Betrachtung struktureller Algorithmen auf den Fall einer Geraden mit einer Steigung zwischen Null und Eins eingeschränkt. Ein struktureller Algorithmus zum Zeichnen einer Geraden konstruiert die zum Setzen der Pixel benötigte Folge aus Horizontalschritten (H) und Diagonalschritten (D) und läuft nach folgendem Grundprinzip ab. Gegeben sind der Startpunkt (xo ,Yo) und Endpunkt (xl ,yd eines Geradensegments mit einer Steigung zwischen Null und Eins. Man berechnet zunächst die Werte dx = Xl - Xo und dy = Y l - Yo. Es müssen nach dem Startpixel insgesamt noch dx Pixel gezeichnet werden. Auf dieser Strecke muss die Gerade um dy Pixel nach oben steigen. Dafür sind dy Diagonalschritte erforderlich. Die übrigen (d.'r;-dy) Zeichenschritte müssen Horizontalschritte sein. Als erste, sehr
62
3 Zeichnen von Kurven
schlechte Approximation des Geradensegments, bzw. der das Geradensegment beschreibenden Sequenz wählt man die Folge H dx- dytr«. die zwar die richtige Anzahl von Horizontal- und Diagonalschritten enthält, jedoch nicht in der korrekten Reihenfolge. Durch geeignete Permutation dieser Ausgangssequenz erhält man schließlich die gewünschte Folge von Zeichenschritten. Der Algorithmus von Brons konstruiert die korrekte Permutation aus der Ausgangssequenz H dx-dyD dy folgendermaßen [6, 7]: • Sind dx und dy (und damit auch (dx - dy )) nicht teilerfremd, das heißt, es gilt für den größten gemeinsamen Teiler 9 = ggT(dx ,dy) > 1, lässt sich das Zeichnen der Geraden offenbar durch 9 sich wiederholende Sequenzen der Länge dx 19 realisieren. • Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass d» und dy teilerfremd sind. • Seien P und Q zwei beliebige Worte (Sequenzen) über dem Alphabet { D, H }. • Aus einer Ausgangsfolge P PQq mit teilerfremden Häufigkeiten p und q (sowie ohne Beschränkung der Allgemeinheit 1 < q < p) wird mittels ganzzahliger Division p
k . q + T,
°
1: Der Schnittpunkt liegt außerhalb des Geradenstücks und hinter Xmax' • 0 :::; t l :::; 1 und t2 > 1: Das Geradenstück schneidet die durch die untere Kante definierte Gerade hinter .'I:max• t l > 1 und t 2 > 1: Der Schnittpunkt liegt außerhalb des Geradenstücks und hinter .'I:maxEntsprechende Überlegungen können für die übrigen Rechteckkanten angestellt werden und daraus geschlossen werden, ob bzw. welcher Teil des Geradenstücks zu zeichnen ist. Beim Cohen-Sutherland-Clipping-Algorithmus (siehe z.B. [16]) wird versucht, die aufwendigen Berechnungen von Geradenschnittpunkten möglichst zu vermeiden. Dazu wird die Ebene in neun Teilbereiche aufgeteilt, die durch einen 4-Bit-Code beschrieben werden. Einem Punkt P = (x p ,yp) wird der vierstellige Binärcode blP ) b~P) b~P) b~P) E {0,1}4 nach dem folgenden Muster zugeordnet: P
= b~P) =
bl
)
< Xmin x p > Xmax YP < u-: Yp > Ymax
1 {:} x p 1 {:}
b~P)
= 1
b~P)
=
{:}
1 {:}
3.5 Geradenclipping
71
Abbildung 3.12 zeigt die neun Bereiche und die ihnen zugeordneten Binärcodes. I
1001
0001:
0101
:
(Xmax,Ymax)
I I
I
::~~~~:::::~:::::~~~~:: (Xmin,Ymin)
1010 Abbildung 3.12
0010
0110
Binärcode für die neun Bereiche beim Cohen-Sutherland-C1ipping
Es wird ein zu zeichnendes Geradensegment mit Startpunkt P und Endpunkt Q betrachtet. Der diesen beiden Punkten zugeordnete Binärcode b(P ) bzw. b(Q ) lässt sich durch einfache Zahlenvergleiche bestimmen. Man unterscheidet beim Zeichnen des Geradensegments drei Fälle. Das Zeichnen des Geradensegments erfolgt stückweise. Die beiden ersten Fälle repräsentieren dabei eine Abbruchbedingung. Im dritten Fall wird das Geradensegment in Teilstücke aufgeteilt. 1. Fall: Die bitweise Verknüpfung der den beiden Punkten zugeordneten Binärcodes durch den logischen Oder-Operator ergibt b(P ) V b(Q ) = 0000. Dann liegen offenbar beide Punkte innerhalb des C1ippingbereichs, die gesamte Strecke PQ wird gezeichnet und das Zeichnen des Geradensegments ist beendet. 2. Fall: Die bitweise Verknüpfung der den beiden Punkten zugeordneten Binärcodes durch den logischen Und-Operator ergibt b(P ) 1\ b(Q ) =1= 0000. Dies bedeutet, dass die beiden Binärcodes mindestens an einer Position eine gemeinsame Eins besitzten. Bei einer gemeinsamen Eins an der ersten Position liegt das gesamte Geradensegment auf der linken Seite des C1ippingbereichs und bei einer Eins an der zweiten Position rechts vom C1ippingbereich. Entsprechend bedeutet eine Eins an der dritten bzw. vierten Position, dass sich das Geradensegment unter- bzw. oberhalb des C1ippingbereichs befindet. In diesem Fall muss das Geradensegment nicht gezeichnet werden und das Zeichnen des Geradensegments ist beendet. 3. Fall: Weder der erste noch der zweite Fall treffen zu. Dann muss
b(P ) =1=
0000 und
b(Q ) =
0000 gelten.
3 Zeichnen von Kurven
72
Ohne Einschränkung der Allgemeinheit kann angenommen werden, dass :/= 0000, ansonsten werden die Punkte P und Q vertauscht. Man berechnet in diesem Fall den oder die Schnittpunkte des Geradensegments mit den Rechteckgeraden, zu denen die Eins bzw. die Einsen in b(P ) :/= 0000 gehören. Es sind entweder ein oder zwei Schnittpunkte vorhanden. Exemplarisch soll dies am Beispiel des Bereichs mit dem Binärcode 1000 gezeigt werden. Das Geradensegment kann nicht die untere und die obere begrenzende Gerade des C1ippingbereichs schneiden. Die untere Gerade kann nur geschnitten werden, wenn b(Q) an der dritten Stelle eine Eins besitzt, die obere nur, wenn b(Q) an der vierten Stelle eine Eins besitzt. Die dritte und vierte Stelle von b(Q) können aber niemals gleichzeitig den Wert Eins annehmen. b(P )
Gibt es nur einen Schnittpunkt des Geradensegments mit den Begrenzungsgeraden des C1ippingbereichs, ersetzt man den Punkt P durch diesen Schnittpunkt. Liegen zwei Schnittpunkte vor, wird einer von beiden Schnittpunkten bestimmt und P durch diesen Schnittpunkt ersetzt. Das auf diese Weise verkürzte Geradensegment wird entsprechend behandelt, bis einer der ersten beiden Fälle zutrifft.
1010 Abbildung 3.13
0010
0110
Cohen-Sutherland-C1ipping
Abbildung 3.13 veranschaulicht diese Vorgehensweise. Das Geradensegment PQ wird über die Zwischenschritte 8 1 Q, 8 2 Q , 8 283 zum Geradenstück 8 2 8 4 verkürzt , das schließlich vollständig gezeichnet wird. Der Cyrus-Beck-Clipping-Algorithmus [12] bestimmt das zu zeichnende Stück eines Geradensegments unter Verwendung von Normalenvektoren des C1ippingbereichs und einer para metrischen Darstellung des Geradensegments, das wie in
3.5 Geradenclipping
73
Gleichung (3.10) auf Seite 69 als Konvexkombination von Anfangs- und Endpunkt dargestellt wird. Ist Po der Anfangs- und P i der Endpunkt des Geradensegments, so entspricht das Geradensegment genau den Punkten g(t) = (1 - t) . Po + t· P i = Po + (P i - PO) . t
(t E [0,1]).
Für jede der vier, den C1ippingbereich begrenzenden Kanten wird der Normalenvektor bestimmt und zwar so, dass er jeweils nach außen zeigt. Für die linke Kante verwendet man daher den Normalenvektor (-1 ,0) T , für die untere (0, - 1) T , für die obere (0,1) T und für die rechte (1,0) T . Abbildung 3.14 zeigt die Vorgehensweise beim Cyrus-Beck-C1ipping exemplarisch an der linken Begrenzungskante des C1ippingbereichs. Neben dem jeweiligen Normalenvektor n wird außerdem ein Punkt auf der entsprechenden Kante des C1ippingbereichs gewählt. Für die linke Kante ist dieser Punkt mit P E (E für "Edge") in Abbildung 3.14 bezeichnet.
Abbildung 3.14
Cyrus-Beck-C1ipping
Der Verbindungsvektor des Punktes P E mit einem Punkt auf der durch die Punkte Po und P i definierten Geraden lässt sich in der Form PO+(Pi-P O)t-PE
schreiben. Für den Schnittpunkt der Geraden mit der Kante des C1ippingbereichs muss gelten:
Diese Gleichung besagt, dass der Verbindungsvektor von P E mit dem Schnittpunkt orthogonal zum Normalenvektor n E verlaufen muss, da er parallel zur linken Kante des C1ippingbereichs verläuft. Somit ergibt sich für t :
74
3 Zeichnen von Kurven t
=
nI · (po - PE) nI · (P i - PO)
(3.12)
Der Nenner kann nur dann 0 werden, wenn entweder Po = P i gilt , das heißt, das Geradenstück besteht nur aus einem Punkt, oder wenn die Gerade senkrecht zum Normalenvektor n E, d.h. parallel zur betrachteten Kante E verläuft. Dann kann es keinen Schnittpunkt geben. Der Wert t wird für alle vier Kanten des C1ippingrechtecks bestimmt, um festzustellen, ob Schnittpunkte des Geradenstückes mit den Rechteckkanten vorliegen. Liegt ein Wert t außerhalb des Intervalls [0,1], so existiert kein Schnittpunkt des Geradenstückes mit der entsprechenden Rechteckkante. Man beachte, dass die Berechnung der Skalarprodukte im Zähler und Nenner von Gleichung (3.12) durch die einfache Form der Normalenvektoren nur aus der Auswahl der x- bzw. y-Komponente des jeweils rechten Differenzvektors besteht, ggf. noch mit einer Änderung des Vorzeichens. Für die vier Kanten des C1ippingrechtecks betrachtet man jeweils den berechneten t-Wert für den Schnittpunkt der Geraden mit der Kante. Liegt ein Wert t außerhalb des Intervalls [0,1], so schneidet das Geradensegment die entsprechende Rechteckkante nicht. Die noch verbleibenden potenziellen Schnittpunkte mit den Rechteckkanten werden als "potenziell austretend" (PA) und "potenziell eintretend" (PE) charakterisiert. Diese Schnittpunkte liegen alle innerhalb des Geradensegments, sie müssen allerdings nicht eine Rechteckkante schneiden, sondern können auch deren Verlängerungen schneiden. Abbildung 3.15 veranschaulicht diesen Sachverhalt.
---------------+----------+
PA
+----------+---------------
Abbildung 3.15
Potenzielle Schnittpunkte mit dem C1ippingrechteck
3.5 Geradenclipping
75
Rechnerisch lässt sich die Entscheidung PA oder PE anhand des Winkels zwischen der Geraden P OPi und dem zur entsprechenden Rechteckkante gehörenden Normalenvektor n treffen: • Ist der Winkel größer als 90°, liegt der Fall PE vor. • Ist der Winkel kleiner als 90° , liegt der Fall PA vor. Für diese Entscheidung muss nur das Vorzeichen des Skalarprodukts
bestimmt werden. Ein negatives Vorzeichen impliziert den Fall PE, ein positives den Fall PA. Da jeweils eine Komponente der Normalenvektoren der Rechteckkanten Null ist, erhält man das Vorzeichen des Skalarprodukts schon durch Betrachtung des entsprechenden Vorzeichens des Vektors P i - P O. Um das im C1ippingrechteck liegende Geradenstück zu bestimmen, muss der größte Wert t E bestimmt werden, der zu einem PE-Punkt gehört und der kleinste Wert t ». der zu einem PA-Punkt gehört. Gilt tE ~ t A ist genau der Teil der Geraden zwischen den Punkten P o + (Pi - pO)t E und Po + (Pi - p O) t A in das Rechteck zu zeichnen. Im Fall t e > tA liegt das Geradenstück außerhalb des Rechtecks. left
1--+----+-- lower
lower - 0.5
-----±::o_::::r----+---+--+--+--+-----1f---+-- lower - 1
Abbildung 3.16
pingbereich
Bestimmung des exakten Eintrittspunktes einer Geraden in den Clip-
Ein weiteres Problem, das beim Geradenclipping zu berücksichtigen ist, besteht in der Bestimmung des ersten zu zeichnenden Pixels. Hierfür genügt es im Allgemeinen nicht, den gerundeten Eintrittspunkt der Geraden in das C1ippingrechteck zu wählen. In der Abbildung 3.16 - die linke Kante des C1ippingrechtecks ist mit .Jeft" , die untere mit" lower" bezeichnet - würde bei dieser Vorgehensweise das erste Pixel nicht gesetzt werden, obwohl es zur Geraden gehört. In diesem Fall wird der Schnittpunkt des zu zeichnenden Geradensegments mit dem um einen
76
3 Zeichnen von Kurven
halben Pixel nach unten verschobenen , unteren Rechteckrand berechnet. Der aufgerundete x-Wert ergibt dann die Stelle, bei der das Zeichnen des Geradensegments begonnen werden muss.
3.6
Der Mittelpunktalgorithmus für Kreise
Im Abschnitt 3.2 wurde ein effizienter Algorithmus zum Zeichnen von Geraden auf einem Pixelraster vorgestellt, dessen Berechnungen nur auf ganzzahliger Arithmetik beruhen. Dieser Mittelpunktalgorithmus kann unter gewissen Voraussetzungen für das Zeichnen von Kreisen verallgemeinert werden. Die wesentliche Voraussetzung besteht dabei darin, dass der Mittelpunkt (xrn ,Yrn) des zu zeichnenden Kreises auf einem Pixel liegt, d.h. ganzzahlige Koordinaten besitzt. In diesem Fall genügt es, ein Verfahren zum Zeichnen eines Kreises mit Mittelpunkt im Koordinatenursprung zu entwickeln. Für einen Kreis mit dem Mittelpunkt (x rn ,Yrn) muss dann nur der Algorithmus für einen Kreis mit Mittelpunkt (0,0) ausgeführt und die berechneten Pixel mit einem Offset von (xrn ,Yrn) gezeichnet werden. Um die Pixel zu bestimmen , die bei einem Kreis um den Koordinatenursprung zu setzen sind, werden die Berechnungen explizit nur für einen Achtelkreis ausgeführt. Die übrigen Pixel ergeben sich aus Symmetrieüberlegungen, wie sie in der Abbildung 3.17 zu sehen sind. Mit dem zu zeichnenden Pixel (x ,y) im schraffierten Achtelkreis müssen ebenso die entsprechenden Pixel (±x ,±y) und (±y, ± x ) in den anderen Achtelkreisen gezeichnet werden.
(-y,x) ---+-
(y,x) -
-
-
---j"------
-
-
-f-
(-y,-x)
(y,-x)
(-x,-y)
(x,-y)
Abbildung 3.17 Ausnutzung der Symmetrie des Kreises
3.6 Der Mittelpunktalgorithmus für Kreise
77
Um den Mittelpunkt- oder Bresenham-Algorithmus für Kreise [5] zu formulieren, soll zunächst davon ausgegangen werden, dass der Radius R des Kreises ganzzahlig ist. In dem Achtelkreis, der zu betrachten ist, liegt die Steigung der Kreislinie zwischen 0 und -1. Analog zu den Uberlegungen beim Mittelpunktalgorithmus für Geraden stehen nur zwei Pixel als Folgepixel eines gesetzten Pixels zur Auswahl. Wurde das Pixel (xp,yp) in einem Schritt gezeichnet, kommt - wie in Abbildung 3.18 zu sehen ist - als nächstes zu zeichnendes Pixel nur einer der beiden Punkte 0 und SO in Frage.
Abbildung 3.18
Mittelpunktalgorithmus für Kreise
Wie beim Mittelpunktalgorithmus für Geraden soll die Entscheidung, welches der beiden Pixel zu zeichnen ist, mit Hilfe einer Entscheidungsvariablen bestimmt werden. Dazu wird die Kreisgleichung x 2 + y 2 = R 2 in der Form
(3.13) umgeschrieben. Für diese implizite Gleichung und einen Punkt (x ,y) gilt offenbar:
• F (x, y ) = 0 {::} (x ,y) liegt auf dem Kreis. • F (x, y ) > 0 {::} (x ,y) liegt außerhalb des Kreises. • F (x,y ) < 0 {::} (x ,y) liegt innerhalb des Kreises. Um zu entscheiden, ob als nächstes das Pixel 0 oder SO zu zeichnen ist, setzt man den Mittelpunkt M ein und erhält:
78
3 Zeichnen von Kurven • Ist d
> 0, so
muss SO gezeichnet werden.
• Ist d < 0, so muss
° gezeichnet werden.
Wie schon beim Mittelpunktalgorithmus für Geraden wird nicht jedes Mal der Mittelpunkt explizit eingesetzt, sondern nur die Anderung der Entscheidungsvariablen in jedem Schritt berechnet. Dazu geht man vom Pixel (xp ,Yp) aus, das mit korrekter Rundung gezeichnet wurde, und bestimmt, wie sich d ändert, wenn man nach dem Zeichnen des Pixels (x p+t ,Yp+d den Mittelpunkt zur Bestimmung des Pixels (Xp+2,Yp+2) betrachtet. Dazu sind zwei Fälle zu unterscheiden. Fall 1: 0, d.h. (x p+t ,Yp+d
= (x p + 1,yp) war das nach (.'Cp,yp) zu zeichnende
Pixel. Dies entspricht dem in Abbildung 3.18 dargestellten Fall. Der zum Zeichnen des Pixels (Xp+2,Yp+2) zu betrachtende Mittelpunkt ME hat daher die Koordinaten ( x p + 2,yp - ~). Setzt man diesen Punkt in Gleichung (3.13) ein, ergibt sich der folgende Wert für die Entscheidungsvariable d: d neu = F
(x p + 2,yp -"21)
=
(x p + 2)
2+ (Yp - "21)2- R 2
Im vorhergehenden Schritt zur Bestimmung des Pixels (x p+l ,Yp+d musste der Mittelpunkt ( x p + 1,yp + ~ ) in die Gleichung (3.13) eingesetzt werden, so dass die Entscheidungsvariable den Wert da1t = F
( p + 1,yp -"21) X
=
(x p + 1)
2+ (YP - "21)2- R 2
hatte. Als Anderung der Entscheidungsvariablen ergibt sich damit in diesem Fall der Wert: ßo = d neu - dal t = 2x p + 3 Fall 2: SO, d.h. (Xp+l ,Yp+l ) = (x p + 1,yp - 1) war das nach (xp ,Yp) zu zeich-
nende Pixel. In diesem Fall ist der nächste zu betrachtende Mittelpunkt M so = ( x p + 2,yp - ~ ) (vgl. Abbildung 3.18). Für die Entscheidungsvariable ergibt sich somit der Wert: d neu =
F
(x p + 2,yp -"23)
=
(3)2 "2 - R 2
(x p + 2)2 + YP -
Der vorhergehende Wert der Entscheidungsvariablen d ist derselbe wie im ersten Fall des östlichen Pixels 0, so dass man als Änderung der Entscheidungsvariablen ß so erhält.
=
d neu - dal t =
2x p - 2yp + 5
79
3.6 Der Mittelpunktalgorithmus für Kreise Zusammengefasst ergibt sich die Änderung der Entscheidungsvariablen
+
2x p 3 2x p - 2yp
d.h.
+5
ß _ { 2x p + 3 -
2x p - 2yp
falls 0 gewählt wurde falls SO gewählt wurde falls dal t falls d a1t
+5
°
< > 0,
so dass ß immer ganzzahlig ist. Um die Entscheidungsvariable d in jedem Schritt berechnen zu können, fehlt noch der Anfangswert. Das erste zu zeichnende Pixel hat die Koordinaten (O ,R), so dass (1 ,R - ~ ) der erste zu betrachtende Mittelpunkt ist. Der Anfangswert von d ist damit: F R _~) = ~ - R (3.14) , 2 4
(1
Wie im Fall der Geraden ändert sich die Entscheidungsvariable zwar nur um ganzzahlige Werte, der Anfangswert ist aber nicht ganzzahlig. Man könnte daher ähnlich wie bei den Geraden die Entscheidungsvariable D = 4 · d verwenden, um eine Initialisierung mit einem ganzzahligen Wert zu erreichen. Einfacher ist es jedoch, den Nachkommaanteil des Initialisierungswertes (3.14) zu ignorieren. Dies ist aus folgendem Grund zulässig: Um zu entscheiden, welches Pixel jeweils zu zeichnen ist, muss in jedem Schritt nur bestimmt werden, ob die Entscheidungsvariable d einen positiven oder negativen Wert annimmt. Da sich d in jedem Schritt nur um ganzzahlige Werte ändert, kann der Nachkommaanteil des Initialisierungswertes das Vorzeichen von d nicht beeinflussen. Bei der Herleitung des Mittelpunktalgorithmus zum Zeichnen von Kreisen wurde angenommen, dass der Mittelpunkt des Kreises der Koordinatenursprung - oder zumindest ein Rasterpunkt - ist und dass der Radius ebenfalls ganzzahlig ist. Die Vorgehensweise lässt sich problemlos auf Kreise mit nichtganzzahligen Radien erweitern. Da der Radius keinen Einfluss auf die Änderung der Entscheidungsvariablen d hat, muss der nichtganzzahlige Radius nur bei der Initialisierung von d berücksichtigt werden. Bei einem nichtganzzahligen Radius Rist (O,round(R)) das erste zu zeichnende Pixel und somit (1 ,round(R) - ~) der erste zu betrachtende Mittelpunkt. Entsprechend muss d mit dem Wert
F (1 ,round(R)
-~)
=
~-
round(R)
initialisiert werden. Dabei kann der Nachkommaanteil wiederum ignoriert werden.
80
3.7
3 Zeichnen von Kurven
Zeichnen beliebiger Kurven
Der Mittelpunktalgorithmus lässt sich nicht nur auf Kreise, sondern auch auf andere Kurvenformen, z.B. Ellipsen [23, 36, 49], erweitern. Eine wesentliche, sehr einschränkende Voraussetzung für den Mittelpunktalgorithmus besteht darin, dass die Steigung der Kurve in dem zu zeichnenden Intervall zwischen 0 und 1 bzw. zwischen 0 und -1 bleibt. Zum Zeichnen beliebiger, zumindest stetiger Kurven oder zur Darstellung von Funktionsgraphen wird daher im Allgemeinen eine einfachere Annäherung durch Geradensegmente vorgenommen. Soll die stetige Funktion y = f (x ) gezeichnet werden, genügt es nicht, die Funktion pixelweise in x-Richt ung abzutasten und die zugehörigen Pixel mit den gerundeten v-Werten zu zeichnen. In Bereichen, wo die Funktion eine betragsmäßig größere Steigung als 1 aufweist , würden sich die gleichen Lücken beim Zeichnen des Funktionsgraphen ergeben, wie sie der naive Geradenalgorithmus in Abbildung 3.2 auf Seite 49 produziert. Geraden besitzen eine konstante Steigung, die sich leicht bestimmen lässt. Daher kann man dieses Problem bei den Geraden dadurch beheben, dass man beim Zeichnen einer Geraden mit einer betragsmäßigen Steigung von mehr als 1 die Rollen von x - und y-Achse vertauscht, d.h. die Umkehrfunktion entlang der y-Achse zeichnet. Beliebige Funktionen besitzen keine konstante Steigung und sowohl die Steigung als auch die Umkehrfunktion können häufig gar nicht oder nur schwer berechnet werden. Aus diesem Grund geht man beim Zeichnen einer beliebigen Kurve meistens so vor, dass man die Funktion in x-Richt ung pixelweise abtastet, die v-Werte bestimmt und nicht nur die Pixel mit den den entsprechenden gerundeten v-Werten zeichnet, sondern die zu zwei benachbarten x-Werten gehörigen Pixel durch ein Geradensegment verbindet, das mit dem Mittelpunktalgorithmus gezeichnet wird. Abbildung 3.19 veranschaulicht diese Vorgehensweise für das Zeichnen einer stetigen Funktion y = f( x) im Intervall [XÜ ,.' rl] mit .'rü ,Xl E IN. Die ausgefüllten Kreise sind die Pixel der Form (x ,round(f(x))) für ganzzahlige x-Werte. Die nichtausgefüllten Kreise entsprechen den Pixeln, die beim Zeichnen der Verbindungsgeraden von Pixeln mit benachbarten x-Koordinaten gesetzt werden. Wird eine Kurve auf diese Weise gezeichnet, werden im Allgemeinen nicht dieselben Pixel gesetzt wie in dem Fall, wenn man jeweils das zur Kurve am nächsten liegende Pixel wählt. Die Abweichung beträgt jedoch maximal ein Pixel in yRichtung.
3.8 Antialiasing
81
int yRoundl, yRound2; yRoundl = round(f(xO)) for (int x=xO; x 0, wird das Rechteck nicht weiter in Teilrechtecke unterteilt. Andernfalls wird das Rechteck in vier gleichgroße Teilrechtecke aufgeteilt. Mit jedem dieser Teilrechtecke wird dann genauso verfahren wie mit dem ursprünglichen Rechteck. Ist der Fehler der Annäherung der Funktion auf einem Teilrechteck durch zwei Dreiecke genügend klein, werden die entsprechenden Dreiecke auf dem Teilrechteck zur Approximation der Funktion verwendet, andernfalls wird das Teilrechteck weiter rekursiv in vier kleinere Teilrechtecke unterteilt. Man sollte zusätzlich eine maximale Rekursionstiefe oder eine minimale Größe der Teilrechtecke vorgeben, damit der
170
6 ModelIierung dreidimensionaler Körper
Teilungsalgorithmus auch bei unstetigen Funktionen oder Funktionen mit einem Pol terminiert. Für beliebige Funktionen ist die Berechnung des maximalen Fehlers auf einem Teilrechteck nicht unbedingt analytisch möglich. Es empfiehlt sich daher , ein genügend feines Gitter - beispielsweise das Gitter, das sich aus den kleinsten zulässigen Rechtecken ergeben würde - zu verwenden und den Fehler nur an den Gitterpunkten innerhalb des jeweiligen Teilrechtecks zu betrachten.
6.5.1
Darstellung von Landschaften
Gekrümmte Flächen werden in der Regel nicht durch beliebige Funtionen der Form z = f (x,y ) beschrieben , sondern aus Polynomen niedrigen Grades oder rationalen Funktionen zusammengesetzt, die eine intuitive und leichter verständliche ModelIierung ermöglichen als mit beliebigen Funktionen. Diese Art der ModelIierung wird in Abschnitt 6.7 genauer besprochen. Die Technik zur Darstellung von Funktionen der Form z = f( x ,y), wie sie hier eingeführt wurde, kann allerdings für die ModelIierung von Landschaften zum Beispiel bei Flugsimulatoren verwendet werden. Zum einen können künstliche Landschaften mit Hügeln, Bodenwellen und ähnlichen Eigenschaften durch geeignete Funktionen relativ einfach erzeugt werden. Zum anderen können reale Landschaften durch eine geeignete Modifikation der Darstellung für Funktionen zur Animation nachgebildet werden. Zunächst soll nur die reine Geometrie oder Topologie der Landschaft betrachtet werden und nicht das konkrete Aussehen im Detail wie etwa Grasfläche, Straße, Steinwüste oder ähnliches. Für reale Landschaften liegen in der Regel Höheninformationen über einem ausreichend feinem Raster oder Gitter vor. Das bedeutet , dass etwa in einer Datei für jeden Kreuzungspunkte eines Gitternetzes, das über die Landschaft gelegt wird, die geografische Höhe abgelegt ist. Anstatt die Funktion z = f (x ,y ) an den entsprechenden Gitterpunkten (Xi ,Yj) auszuwerten, wird der Wert Zij = f (xi,Yj ) durch den Höhenwert hij an der entsprechenden Stelle der zu modellierenden Landschaft ersetzt. Bei einer größeren Landschaft würde eine gleichmäßige Aufteilung in Dreiecke oder eine Aufteilung in Abhängigkeit von der Landschaftsstruktur dazu führen, dass bei einem weiten Blick in die Landschaft sehr viele Dreiecke bei der Darstellung berücksichtigt werden müssten, selbst für die Teile der Landschaft, die in weiter Ferne vom Betrachter liegen. Es ist daher günstiger, das Rendering der Landschaft bzw. ihre Aufteilung in Dreiecke abhängig von der Entfernung des Betrachters zu machen. Sehr nahe Teile der Landschaft werden sehr fein
6.5 Flächen als Funktionen in zwei Variablen
171
aufgeteilt und je weiter Teile die Landschaftsteile vom Betrachter entfernt sind, desto gröber wird die Unterteilung in Dreiecke vorgenommen (s. [34]. Kapitel 2). Abbildung 6.15 veranschaulicht dieses Prinzip der Clipmaps. Dabei wurde die Höheninformation in der Darstellung weggelassen.
y
Abbildung 6.15
LOD-Aufteilung einer Landschaft mittels C1ipmaps
Derartige Techniken, bei denen die Anzahl der Dreiecke zur Darstellung einer Fläche von der Entfernung des Betrachters abhängt, werden in der Computergrafik nicht nur bei Landschaften, sondern auch für andere Objekte bzw. Oberflächen eingesetzt, die aus vielen Dreiecken bestehen. Ist der Betrachter näher am Objekt , wird eine höhere Anzahl Dreiecke für die Darstellung der Oberfläche verwendet und bei größerer Entfernung begnügt man sich mit wenigen Dreiecken. Man bezeichnet dies auch als LOD (Level of Detail). Die Implementierung der LOD-Technik in Java 3D wird im Abschnitt 9.11 erläutert. Die in diesem Abschnitt beschriebenen Methoden ermöglichen die rein geometrische oder topologische ModelIierung von Landschaften. Anschließend müssen auf die Landschaft noch Texturen aufgebracht werden, um die unterschiedlichen Bodenbeschaffenheiten wie Gras oder Straßen wiedergeben zu können. Texturen werden allgemein im Abschnitt 8.8 behandelt.
172
6.5.2
6 ModelIierung dreidimensionaler Körper Darstellung von Funktionen in Java 3D
Die Darstellungen von Landschaften und Funktionen in zwei Variablen in Java 3D kann mit Hilfe der bereits im Abschnitt 6.4 vorgestellten Klasse GeometryArray direkt realisiert werden. Im einfachsten Fall eines zugrunde liegenden Rechteckrasters müssen nur die Gitterpunkte des Rasters mit den zugehörigen Höhenkoordinaten der Funktion bzw. der Landschaft als Punkte für das GeometryArray verwendet werden. Die einzelnen Rechtecke des Gitters werden jeweils in zwei Dreiecke aufgeteilt und liefern so die Dreiecke für das GeometryArray. Die Darstellung der Funktion z = x sin(7x) cos(4y) in Abbildung 6.13 auf Seite 168 wurde mit Hilfe der Klasse SurfaceExample . java erstellt. In dieser Klasse wurde die Methode createSurface implementiert, die ein GeometryArray für eine gegebene Funktion in zwei Variablen liefert. Aus dem GeometryArray lässt sich dann ein Shape erzeugen, der in einen Szenengraphen eingefügt werden kann. Die Methode createSurface benötigt eine Reihe von Parametern. • Die darzustellende Funktion wird in Form einer Implementierung des Interfaces! IFunctionlnTwoVariables realisiert. Das Interface muss in einer konkreten Klasse implementiert werden. Als Beispiel ist die Funktion z = x sin(7 x) cos(4y ) in der Klasse FunctionlnTwoVariablesExample realisiert. • Die folgenden vier Werte geben den Bereich [Xmin ,X max] x [Xmin ,X max] an, über dem die Funktion ausgwertet werden soll. Mit den darauf folgenden beiden Werten können die Funktionswerte, d.h. die z-Werte, begrenzt werden. Sollen die Funktionswerte auf diese Weise begrenzt werden, d.h. zu kleine bzw. zu große Werte werden abgeschnitten, muss der nächste boolesche Wert auf true gesetzt werden. Ansonsten wird der gesamte Wertebereich der Funktion über dem betrachteten Rechteck verwendet. • Die folgenden sechs Parameter definieren einen Quader, in dem die Funktion innerhalb der dreidimensionalen Darstellung bzw. der Transformationsgruppe dargestellt wird. Dieser Quader sollte in der Regel um den Koordinatenursprung gelegt werden, selbst wenn die Funktion beispielsweise im Bereich [1000,2000] x [1000,2000] ausgewertet werden soll. 1
Ein Interface in Java kann dazu benutzt werden, um Methoden festzulegen, die eine Klasse enthalten muss. Im Falle der reellen Funktion in zwei Variablen verlangt das Interface nur , dass eine Methode evaluateAt implementiert sein muss, die für ein Paar von Werten x und y den Funktionswert z = f( x ,y) zurückliefert. Das Interface muss dann von einer Klasse implementiert werden, in der die geforderten Methoden zu programmieren sind. Im Fall der Funktionsauswertung ist eine konkrete reelle Funktion in zwei Variablen zu berechnen.
6.6 Text in dreidimensionalen Darstellungen
173
• Die letzten beiden Parametern geben an , wie viele Gitterpunkte in x - bzw. y-Richtung bei der Annäherung durch Dreiecke verwendet werden sollen.
6.6
Text in dreidimensionalen Darstellungen
Text kann in einer dreidimensionalen Szene entweder zweidimensional, d.h. flach, oder dreidimensional sein. Zweidimensionale Buchstaben werden in der Regel auf Oberflächen in Form von Texturen, wie sie im Abschnitt 8.8 behandelt werden, aufgebracht. Sie können z.B. als Aufschriften von Plakaten in einer Szene dienen. Dreidimensionale Buchstaben sind eigene geometrische Objekte. Buchstaben, wie sie in der Leuchtreklame vorkommen, wären eine mögliche Anwendung. Eine andere Anwendung von Texten ist die Beschriftung von Grafiken, wie sie etwa bei der dreidimensionalen Darstellung einer Funktion in zwei Variablen vorgenommen wird. Hierbei treten zwei wesentliche Probleme auf , wenn der Betrachter die Möglichkeit hat , in der Szene zu navigieren, sich beispielsweise eine Funktion in zwei Variablen aus verschiedenen Blickwinkeln anzusehen. Zum einen können die Beschriftungen zu klein werden, um noch lesbar zu sein, wenn der Betrachter sehr weit aus der Szene herauszoomt. Zum anderen sind die Beschriftungen nicht mehr oder kaum lesbar, wenn der Betrachter sie von der Seite oder von hinten ansieht. Um dies zu vermeiden, kann man auf die Beschriftungen geeignete Transformationen anwenden, so dass sie immer zum Betrachter hin orientiert sind und ggf. auch in der richtigen Größe erscheinen.
6.6.1
Text in Java 3D
Java 3D bietet die Klassen Text2D und Text3D für die Darstellung von zweibzw. dreidimensionalen Texten in einer Szene. Text2D bringt den Text als Textur auf ein virtuelles Rechteck auf. Der Text ist nur von vorne zu sehen. Mit Text3D können dreidimensionale Buchstaben erzeugt werden, die zwar von allen Seiten sichtbar sind, aber nicht unter jedem Blickwinkel vernünftig lesbar sind. Exemplarisch soll hier nur die Klasse Text3D behandelt werden. Text2D wird ganz analog verwendet. Um einen dreidimensionalen Text darzustellen, muss zunächst eine Schriftart im Form eines Font f, wie in Abschnitt 4.4 beschrieben, definiert werden. Mit den folgenden Zeilen wird ein Text aus dreidimensionalen Zeichen erzeugt.
174
6 ModelIierung dreidimensionaler Körper
Font3D f3d = new Font3D(f, new FontExtrusion()); Text3D t3d = new Text3D(f3d,s,p); Shape3D textShape = new Shape3D(t3d,app); Zunächst wird aus dem gewöhnlichen Font f der dreidimensionale Font3D f3d erzeugt. Das Objekt FontExtrusion legt fest, wie der dreidimensionale Zeichensatz aus dem zweidimensionalen generiert wird. Anschließend wird ein Objekt Text3D t3d erzeugt, das den eigentlichen Text in Form eines Strings s enthält und außerdem eine Position zur Textpositionierung mittels eines Point3f p benötigt. Schließlich kann mit diesem Text3D-Objekt zusammen mit einer Appearance app ein Shape3D-Objekt generiert werden, das dann in einem Szenengraphen oder einer Transformationsgruppe verwendet werden kann. Wenn ein Text oder allgemeiner ein beliebiges Objekt oder eine Transformationsgruppe immer zum Betrachter hin ausgerichtet sein soll, kann man dies durch die Verwendung eines Billboard-Behaviours erreichen. Dazu muss zunächst eine Instanz der Klasse Billboard erzeugt werden, der im Konstruktor die Transformationsgruppe tgBBGroup zugeordnet wird, die immer zum Betrachter hin ausgerichtet sein soll. Außerdem muss in einer Konstanten angegeben werden, durch welche Art der Transformation - im folgenden Beispiel durch eine Punktrotation festgelegt durch die Konstante Billboard . ROTATE...ABOULPOINT - dies erreicht werden soll. Schließlich muss noch der Punkt in Form eines Point3f p definiert werden, um den rotiert werden soll: Billboard bb
=
new Billboard(tgBBGroup, Billboard .ROTATE_ABOUT_POINT, p) ;
bb.setSchedulingBounds(bounds) ; tgBBGroup.addChild(bb); tgBBGroup .setCapability(TransformGroup .ALLOW_TRANSFORM_WRITE); Dem Billboard-Behaviour muss ein Gültigkeitsbereich , z.B. in Form einer BoundingSphere bounds zugewiesen. Außerdem muss das Billboard-Behaviour der entsprechenden Transformationsgruppe tgBBGroup zugeordnet werden. Für diese Transformationsgruppe muss das Verändern der Transformation erlaubt werden, damit das Billboard-Behaviour die Transformationsgruppe zum Betrachter hin ausrichten kann. In dem Programm Text3DExample. java wurde die Funktionsdarstellung aus dem Programm SurfaceExample . java um ein Koordinatensystem mit Achsenbezeichnungen erweitert. Nur für die Beschriftung der y-Achse wurde ein Billboard-Behaviour verwendet. Abbildung 6.16 zeigt das Ergebnis, nachdem
6 .7 Para metrische Kurven und Freiformflächen
175
die Ansich t rotiert wurde. Die Besch riftungen der x- und der z-Achse sind nicht zum Betrachte r hin orient iert , während der Buchstabe Y durch das BillboardBehaviour genau auf den Bet rach te r ausgerichtet ist.
Abbildung 6 .16 Achsenbeschriftung: Nur für den Buchstaben Y Billboard-Behaviour verwendet
6 .7
wurde ein
Parametrische Kurven und Freiformflächen
Für die Darst ellung eine r Szene werden die Oberflächen der einze lnen Objekte zwar durch Dreiecke angenähert, für die Mode liierung von Objekten eignet sich diese ..R epräsentat ion jedoch nicht. Stattdessen werden Freiformffächen verwendet. Ahnlich wie bei der Besch reibung von Kurven in der Ebene aus Absch nitt 2.3 werden bei Freiformflächen P unkte im Ra um vorgegeben, die durc h eine gekrümm t e Fläche angenähert werden . Eine Spe icher ung diese r Kurven ermöglicht das Arbeiten mit unt erschied lichen Auflös ungen bei der Darstellung der Fläche. Die Anzah l der Dreiecke zu r Annäheru ng der Fläche kann je nach gewünschter Gena uigkeit der Da rstellung unterschiedlich gewählt werde n. Außerdem werde n
6 Modellierung dreidimensiona ler Körper
176
die für die Lichtreflexionseffekte benötigten Normalenvektoren nicht aus den Dreiecken berech net , sondern d irekt aus de r ursprüngli chen gek rümmten Fläche .
Abbildun g 6. 17 Zwei Kurven, die man erhält, wenn man eine gekrümmte Fläche entlang einer Achse abtastet .
Die ModeJlierung gekrümmter Oberflächen basiert auf paramet rischen Kurven. Tastet man entlang einer Achsenrichtung eine gekrümmte Fläche ab . erhä lt ma n eine Kurve im Rau m. Abbildung 6.17 veranschaulicht diese n Sachverha lt.
Die Grundlagen parametrischer Kurven im Raum sind da her wesent lich zum Verständnis gekrümmter Flächen, so dass hier zunächst die ModelIie rung von Kurven betrachtet werden soll.
6.7.1
Parametrische Kurven
Soll eine Kurve im Raum oder in der Ebene durch eine Reihe von Pun kten - so genannten Kontrolfpunkten - spezifiziert werden , sind folgende Eigenschaften wünschenswert, um eine leichte Ha ndha bung bei der Modeliierung einer Kurve zu ermög lichen :
Kontrollierbarke it: Der Einfluss der Para meter au f de n Kurvenverlauf ist fü r den Benutzer intuitiv verstä ndlich. Soll ein Kurvenverlauf geä ndert werde n, muss für den Benutzer einfach erken nbar sein, welche Parameter er wie ändern sollte. Lokalit ät sprinzip: Es muss die Mög lichkeit geben , die Kurve lokal zu verä ndern. Wi rd beispielsweise ein Kontrollpunkt der Kurve verändert, sollte dies nac h Mög lichkeit nur Auswirk ungen in der Nähe des Kont rollpunkt es haben. Glattheit : Die Kurve sollte gewisse Glattheitseigenschaften bes itze n. Das bedeutet, sie so llte nicht nur stetig sein , das heißt , keine Lücken oder Sprünge aufweisen, sondern au ch keine Knicke bes itzen . Letzteres bedeutet, dass die Kurve zumindest einma l stetig differenzierbar sein muss . In manchen Fä llen kann es auch erforderl ich se in, dass höhere Ableitungen existieren. Auße rdem sollte die Kurve in gewisser Weise von besch ränkter Variation sein.
6 .7 Para metrische Kurven und Freiformflächen
177
Da mit ist gemeint , dass sie nicht nu r nahe an den Kontrollpu nkt en vorbe iläuft , sondern sich a uch zw ische n de n Kontro llpunkten nicht beliebig weit von ihnen entfernt . We nn d ie Kurve exakt d urch d ie Kont rollpun kte verläuft, spricht man von Interpolation, wä hrend Approximation nur verlangt , dass d ie Kurve d ie P unkte möglichst gut annähert. Durc h (u + 1) Kont rollpunkt e lässt sich zwar imme r ein Interpolat ionspolynom höc hstens n- ten Grades legen. Trotzdem eignen sich lnte rpclaticns potynorne nicht für d ie Mode lIierung in de r Computergrafik . Neben de r P roblemati k, dass be i einer hohen Anza hl von Kontrollpu nkt en a uch der Grad des Polynoms und som it der Reche naufwa nd se hr groß wird, genügen Int erpolat ionsp olynome nicht dem Lokalit ät sprinzip. Wird ein Kont rollpunkt geä ndert, wirkt sich d ies in der Regel a uf alle Koeffi zienten des Polynoms und dam it auf die gesamte Kurve a us. Das Clipping wird wesentlich erleichtert , wenn der Bereich. in dem de Kurve verläuft , se hr leicht direkt aus de n Kont rollpunkten zu ermitte ln ist . Dies ist bei Po lynomen nicht gegeben. Außerdem neigen hochgrad ige Int erpolat ionsp olyno me zum Schwi ngen . Das bedeutet. dass sie tei lweise zwisc hen den Kontrollpun kt en stark schwanken. Abb ildung 6 .18 zeigt ein Interpo lat ionspolynom 5. Grades d urch sechs Kontrollpunkt e, die alle bis auf eine n auf der x -Achse liegen. Das Polynom schw ingt um die Kont rollpun kt e herum und sc hießt üb er den höchst en Kon trollpu nkt hinaus. Es bleibt nicht innerh alb de r konvexen Hülle der Kontrollpu nkt e.
15
1 CE
0
.a; -1 -15 0
1
2
3
4
5
Abbildung 6 .18 Interpolationspolynom 5. Grades durch die Kontrollpun kte (0,0). (1,0), (2,0), (3,0), (4,1), (5,0)
Wenn man darauf verzichtet, dass die Polynome die Kontrollp unkt e inter polieren müssen. und sich mit der Approximation der Kontrollpun kt e begnü gt , können die unangeneh men Eigensc hafte n der Interpolat ionspolynome ver miede n werde n.
178
6 ModelIierung dreidimensionaler Körper
Man kann dazu Bernstein-Polynome n-ten Grades verwenden, die folgendermaßen definiert sind. Das i-te Bernstein-Polynome n-ten Grades (i E {O , ... ,n } ) ist durch die Gleichung (t E [0,1])
gegeben. Die Bernstein-Polynome besitzen zwei wichtige Eigenschaften: für alle t E [0,1] Das heißt, im Bereich des Einheitsintervalls [0,1] nehmen sie nur Werte zwischen Null und Eins an. Diese und die zweite, folgende Eigenschaft werden später benötigt, um Kurven zu konstruieren, die innerhalb der konvexen Hülle der StützsteIlen verlaufen: n
LB~n)(t) = 1
für alle t E [0,1]
i =O
An jeder Stelle im Einheitsintervall addieren sich die Bernstein-Polynome zu Eins auf. Bezier-Kurven verwenden Bernstein-Polynome n-ten Grades zur Approximation von (n + 1) StützsteIlen b o, ... ,b ., E IRP. Für die Cornputergrafi k sind nur die Fälle der Ebene mit p = 2 und des dreidimensionalen Raums mit p = 3 von Bedeutung. Die Kontrollpunkte werden auch Bezler-Punkte genannt. Die durch diese Punkte definierte Kurve n
x(t)
=
L b , . B~n) (t)
(t E [0,1])
(6.3)
i= O
heißt Bezler-Kutve vom Grad n . Die Bezier-Kurve interpoliert den Anfangs- und den Endpunkt, das heißt, es gilt x(O) = b o und x(l) = b.,; Die anderen Kontrollpunkte liegen im Allgemeinen nicht auf der Kurve. Die Tangentialvektoren an die Bezier-Kurve im Anfangsund im Endpunkt lassen sich folgendermaßen berechnen:
*(0) *(1)
n · (b I - b o) n · (b., - b n -
I)
Das bedeutet, dass die Tangente im Anfangspunkt in Richtung des Punktes b l verläuft, die Tangente im Endpunkt kommt aus der Richtung des Punktes b n - I . Dieses Prinzip lag bereits der Definition kubischer Kurven in Abbildung 2.7 auf Seite 14 zugrunde.
6.7 Para metrische Kurven und Freiformflächen
179
Hält man in der Gleichung (6.3) den Wert t fest, erhält man aufgrund der Eigenschaften der Bernsteinpolynome x( t) als Konvexkombination der Kontrollpunkte b o, ... ,b n . Somit verläuft die Bezier-Kurve innerhalb der konvexen Hülle der Kontrollpunkte. Wendet man auf alle Kontrollpunkte eine affine Transformation an, stimmt die Bezier-Kurve aus den transformierten Punkten mit der Transformation der ursprünglichen Bezier-Kurve überein. Bezier-Kurven sind somit invariant unter affinen Abbildungen wie Rotation, Verschiebung oder Skalierung. Bezier-Kurven sind außerdem symmetrisch in den Kontrollpunkten , das heißt, die Kontrollpunkte b o, ... ,b n und b n , ... ,b o ergeben dieselbe Kurve, nur die Durchlaufrichtung ändert sich. Verwendet man als Kontrollpunkte eine Konvexkombination zweier Sätze von Kontrollpunkten, ergibt sich als Bezier-Kurve die Konvexkombination der entsprechenden Bezier-Kurven: • Definieren die Kontrollpunkte • die Kontrollpunkte
bo, ... ,bn
bo, ... ,bn die Bezier-Kurve x(t) und die Bezier-Kurve x(t),
• dann definieren die Kontrollpunkte abo + ßbo, ... ,abn + ßbn die BezierKurve x( t) = ax (t ) + ßx (t ), falls a + ß = 1, a ,ß ~ 0 gilt. Liegen alle Kontrollpunkte auf einer Geraden oder einer Parabel, ergibt sich als Bezier-Kurve ebenfalls die entsprechende Gerade bzw. Parabel. Bezier-Kurven erhalten außerdem gewisse Formeigenschaften wie Monotonie oder Konvexität der Kontrollpunkte. Trotz der vielen günstigen Eigenschaften der Bezier-Kurven sind sie für größere Anzahlen von Kontrollpunkten ungeeignet, da sich ein zu hoher Polynomgrad ergibt. Bei (n+1) Kontrollpunkten ist die Bezier-Kurve in der Regel ein Polynom n-t en Grades. Daher werden statt der Bezier-Kurven eher B-Splines verwendet, um eine Kurve zu einer gegebenen Menge von Kontrollpunkten zu definieren. B-Splines werden aus mehreren Bezier-Kurven niedrigeren Grades - üblicherweise dritten oder vierten Grades - zusammengesetzt. Dazu wird für jeweils n aufeinander folgende Punkte eine Bezier-Kurve berechnet und der letzte Kontrollpunkt der vorhergehenden Bezier-Kurve bildet den ersten Kontrollpunkt der nachfolgenden Bezier-Kurve. Dadurch interpolieren B-Splines die Kontrollpunkte, an denen die einzelnen Bezier-Kurven jeweils aneinander gefügt werden. Diese Nahtstellenpunkte werden als Knotenpunkte bezeichnet. Die anderen Kontrollpunkte heißen innere Bezier-Punkte. Abbildung 6.19 zeigt einen B-Spline, der aus zwei Bezier-Kurven dritten Grades zusammengefügt wird.
180
Abbildung 6.19 PZ,P3 ,PS ,P6
6 ModelIierung dreidimensionaler Körper
B-Spline mit Knotenpunkten P1'p4,P7 und inneren Bezier-Punkten
Damit keine Knicke an den Nahtstellen entstehen, was gleichbedeutend mit der Nicht-Differenzierbarkeit der Kurve ist, müssen der jeweilige Knotenpunkt, der direkt davor und der direkt dahinter liegende innere Bezier-Punkt kollinear sein. Diese Eigenschaft zur Vermeidung von Knicken wurde bereits in der Abbildung 2.8 auf Seite 15 dargestellt. Mit B-Splines n-ten Grades lassen sich durch geeignete Wahl der inneren Bezier-Punkte Kurven erzeugen, die (n-l)-mal stetig differenzierbar sind. Mit kubischen B-Splines, die Polynome dritten Grades verwenden, muss für die zweimalige Differenzierbarkeit neben der Kollinearitätsbedingung eine weitere Bedingung an die benachbarten inneren Bezier-Punkte gestellt werden. Der in Abbildung 6.20 dargestellte B-Spline setzt sich aus zwei BezierKurven dritten Grades zusammen und wird durch die Knotenpunkte Pl ,P4 ,P7 und die inneren Bezier-Punkte P2 ,P3 ,P5 ,P6 definiert. Um zweimalige Differenzierbarkeit sicherzustellen, müssen die eingezeichneten Tangentenabschnitte im gleichen Verhältnis zueinander stehen. B-Splines erben die positiven Eigenschaften der ßezier-Kurven. Sie verlaufen in der konvexen Hülle der Kontrollpunkte, sind invariant unter affinen Abbildungen, symmetrisch in den Kontrollpunkten, interpolieren Anfangs- und Endpunkt der Kontrollpunkte und genügen dem Lokalitätsprinzip. Ein B-Spline setzt sich stückweise aus Bezier-Kurven zusammen. Diese lassen sich in homogenen Koordinaten in der Form
Px(t) ) Py(t) ( Pz(t) 1
schreiben. Dabei sind Px(t) ,Py(t) ,Pz(t) Polynome in t. Wendet man auf diese Darstellung eine perspektivische Projektion in Form der Matrix aus Gleichung (5.6) an, erhält man:
6 .7 Para metrische Ku rven und Freiformflächen
18 1
I~
,
~\
----a:ß Abbildun g 6 .20 Bedingung an die inneren Bazier-Pu nkte für zweimal stetig differenzierbare kubische B-Splines
(~ ~ o o
0 0
~ ~ ) (~:m) ~
0 ...!.. Zn
0 1
P, (t ) 1
( ~:~:; ) 0
1', (1) Zn
+1
In kartesischen Koord inaten ergibt sich somit a ls Proje ktio n einer Bezier- Kurve eine para metrisch e Kurve, die in den einzel nen Koord inaten rationale Funkt ionen a ufweist :
IW L
~ -o P, (t )
3:III+J '0
o We nn sich bei de r perspe kt ivische n Pr ojekt ion von B-Sp lines bzw. Bazier-Kurven in der Regel sowieso rati onal e Funkti o nen ergeben, ka nn ma n im Grunde au ch sc hon bei der Mode liierung im Dreidimensional en mit ratio nalen Funkt ionen arbeiten. Die persp ekt ivisch e P roje kt ion einer rationa len Funkti on ist wiede ru m eine ration ale Fun kt ion . Statt B-Splines werde n dah er hä ufig die a llgemeineren NU RBS (non-un iform rati onal B-splines) verwendet , deren Grund lage auf rati onale Funkt ionen erwe iterte Baz ier-Kurve n de r Form
x ( t) =
c-» bj L.. j- OWi· c-u
L.. jo:=O 1lJ j '
'
I1(1l i )( t )
I1(n)( i t)
sind. Die frei wäh lbaren Gewichte W j beze ichnet ma n als Formpersmeter. Ein größeres Gewicht W j erhöht de n Einfluss des Kont rollpun ktes b , a uf die Kurve.
182
6 ModelIierung dreidimensionaler Körper
Im Sinne dieser Interpretation und um Singularitäten zu vermeiden, setzt man üblicherweise voraus, dass die Gewichte ui; positiv sein müssen.
6.7.2
Effiziente Polynomberechnung
Um eine parametrische Kurve darzustellen, müssen Polynome ausgewertet werden. Dies gilt ebenso für die Darstellung von Freiformflächen. In der Regel verwendet man Polynome dritten Grades. In diesem Abschnitt wird ein effizientes Auswertungsschema von Polynomen vorgestellt, das auf einem ähnlichen Prinzip beruht, wie die bereits im Rahmen des Bresenham-Algorithmus im Abschnitt 3.2 eingeführten inkrementelIen Berechnungen. Man kann auf diese Weise bei den Polynomen zwar nicht auf die Fließkommaarithmetik verzichten. Zumindest kann jedoch die wiederholte Berechnung von Multiplikationen vermieden werden. Um eine kubischen Kurve darzustellen, wird die parametrische Kurve in der Regel an äquidistanten Stellen des Parameters t ausgewertet, die entsprechenden Punkte berechnet und jeweils durch Geradenstücke verbunden. Das gilt ebenso, wenn eine Freiformfläche mit ebenen Polygonen angenähert werden soll. Um ein Polynom f(t) an den Stellen ta, tl = ta+S, t2 = ta+2S , ... mit der Schrittweite S > 0 auszuwerten, nutzt man Vorwärtsdifferenzen. Dazu entwickelt man ein Verfahren zur direkten Berechnung der Anderung
tlf(t)
=
f(t
+ S) -
f(t) ,
so dass das Polynom f(t) ausgewertet wird, indem man den Startwert f(ta) an der Stelle ta explizit berechnet und danach mit der Formel
f(t
+ S) =
f(t)
oder
fn+l = fn
+ tlf(t)
+ tlfn
fortfährt. Für ein Polynom dritten Grades f(t) = at 3 somit:
tlf(t)
=
= fa
+ bt2 + ci + d ergibt
3at 2S + t(3aS2 + 2M) + aS3 + M2
sich
+ eS
Auf diese Weise hat man die Auswertung eines Polynoms dritten Grades auf die Addition von tl-Werten zurückgeführt, die eine Auswertung eines Polynoms zweiten Grades erfordern. Auch für dieses Polynom zweiten Grades lassen sich Vorwärtsdifferenzen ausnutzen:
tl(tlf(t))
=
6aS2t + 6aS3
tlf(t + S) - tlf(t)
+ 2M2
6.7 Para metrische Kurven und Freiformflächen to
=
°
to + 25
to + 5
fl f o
.>
fl 2fo
.> ---+
+ + +
fl 3fo
/'
fl 3fo
fo
-+ ---+
---+
183
+ + +
-+
/'
---+
/'
---+
.>
fl 3f o
---+
to + 35
---+
+ + +
/'
fl 3f o
-+
.> ---+
.> ---+
Tabelle 6.1 Differenzenschema für Polynome dritten Grades
Die fl-Werte für das ursprüngliche Polynom dritten Grades werden somit durch die Formel fl f n = fl f n- l + fl 2fn -l bestimmt. Für die Berechnung der fl 2-Werte ist immer noch eine Multiplikation auszuführen. Wendet man das Schema der Vorwärtsdifferenzen noch ein letztes Mal an , erhält man: fl 3f(t) = fl 2f(t + 5) - fl 2f(t) = 6a5 3 Damit sind nur für die Berechnung der Initialisierungswerte für to = kationen erforderlich: fo fl f o fl 2fo fl 3fo
°
Multipli-
d
a5 3 + M2 + c5 6a5 3 + 2M2 6a5 3
Alle weiteren Werte lassen sich allein du rch Additionen ermitteln. Tabelle 6.1 verdeutlicht dieses Prinzip des Differenzenschemas. Tabelle 6.2 enthält die Auswertung des Differenzenschemas für das Beispielpolynom f(t) = t 3 + 2t + 3, d.h. a = 1, b = 0, C = 2, d = 3, mit der Schrittweite 5 = 1.
6.7.3
Freiformflächen
Wie bereits zu Beginn des Abschnitt 6.7 erwähnt, sind Freiformflächen eng mit para metrischen Kurven verwandt. Bei Kurven wird ein Parameter t durchlaufen, während bei Flächen zwei Parameter benötigt werden. Hält man einen dieser beiden Parameter fest , ergibt sich jeweils eine Kurve auf der Fläche wie in Abbildung 6.21 dargestellt. Bezier-Flschen setzen sich aus Bezier-Kurven zusammen , die jeweils in den Pa-
ra metern s und t durchlaufen werden:
184
6 ModelIierung dreidimensionaler Körper t=O 3
-+
t=l 6
3
.>
9
6
.>
12
6
--+
/'
6
--+ --+
t=2 15
-+ /'
21
--+
/'
18
.>
6
--+ --+
t=3 36
-+
t=4 75
39
.>
63
/'
24
.>
30
.>
--+
6
--+
/'
6
-+ /' --+ --+ --+
--+
Tabelle 6.2 Differenzenschema für das Polynom f( t ) = t 3 + 2t +3 mit der Schrittweite 6= 1
t=)
t=O.8 t=O.6
!
t=OA t=O.2 t=O
~ P2(t)
Abbildung 6.21 Parametrische Freiformfläche
x( s ,t)
=
n m L L bij i=O j=o
·
B}n) (s ). BJm) (t )
(s ,t E [0,1])
In der Regel beschränkt man sich auch hier auf Bezier-Kurven dritten Grades, das heißt, man wählt m = n = 3. Zur Festlegung einer derartigen Bezier-Flache müssen (m + 1) . (n + 1) Bezier-Punkte b i j , d.h. 16 im Falle kubischer BezierKurven, angegeben werden. Abbildung 6.22 veranschaulicht, wie dieses Netz von Bezier-Punkten die Bezier-Fläche definiert. Bezier-Flachen besitzen ähnlich günstige Eigenschaften wie Bezier-Kurven. Die vier Eckpunkte b oo,bom,bno,bnm liegen auf der Fläche, für die anderen Kont roll punkte gilt dies in der Regel nicht. Die Fläche bleibt innerhalb der konvexen Hülle der Kontrollpunkte. Die Kurven mit konstantem Wert s = So sind BezierKurven bezüglich der Kontrollpunkte bj
=
n
Lbij · B Jn)(so) i=O
6.8 Normalenvektoren an Oberflächen
185
Entsprechendes gilt für die Kurven mit konstantem Parameter t = to.
Abbildung 6.22
Netz von Bezier-Punkten zur Definition einer Bezier-Fläche
Da in der Computergrafik Oberflächen üblicherweise mit Dreiecken und nicht mit Vierecken approximiert werden, verwendet man teilweise Bezier-Flachen vom Grad n , meistens n = 3, über einem Dreiecksgitter, die folgendermaßen definiert sind: x(tlh ,t3) = b ijk ' Bi~2 (tl,t2h ) i,j,k?O:i+j+k=n
L
Die entsprechenden Bernsteinpolynome sind durch (n) (
B ij k tlh ,t3
) _
-
n!
~kl
Z.J . .
i
j
k
. t1 . t 2 . t3
gegeben mit t l + t2 + t3 = 1, t l,t2h ~ 0 und i + j + k = n (für i,j, k E lN). Das entsprechende Dreiecksnetz ist in Abbildung 6.23 dargestellt.
6.8
Normalenvektoren an Oberflächen
Zur realistischen Wiedergabe eine Szene müssen Beleuchtungseffekte wie Reflexionen berücksichtigt werden. Reflexionen hängen von den Winkeln ab , in denen Lichtstrahlen auf eine Oberfläche treffen. Zur Berechnung dieser Winkel werden Normalenvektoren der Oberfläche benötigt. Beleuchtungseffekte und Reflexionen werden im Detail im Kapitel 8 besprochen. An dieser Stelle soll es zunächst nur um die Bestimmung der Normalenvektoren an eine Oberfläche gehen. Bei einem Dreieck, das eine ebene Fläche repräsentiert, zeigen die Normalenvektoren alle in dieselbe Richtung, entsprechend dem Normalenvektor zur Ebene
186
6 ModelIierung dreidimensionaler Körper (0,0,4)
(3,1,0)
Abbildung 6.23
(2,2,0)
(1,3,0)
Dreiecksnetz, über dem eine Bezier-Fl äche definiert werden kann
Ax
+ By + C z + D
(6.4)
0,
=
die durch das Dreieck induziert wird. Der Vektor (A ,B ,C ) T ist der nicht-normierte Normalenvektor zu dieser Ebene. Dies sieht man leicht anhand folgende r Überlegung: Ist n = (n x ,ny,n z ) T ein nicht-normierter Normalenvektor an die Ebene und v = (vx,Vy,vz )T ein Punkt in der Ebene , so liegt der Punkt (x ,y ,z )T genau dann in der Ebene , wenn der Verbindungsvektor zwischen v und (x ,y ,z )T in der Ebene liegt, das heißt , wenn er senkrecht zum Normalenvektor steht. Es muss also Folgendes gelten:
0 = n T .((x ,y ,z )T
-v)
= n x · x +ny .y +nz · z - n T . v
Setzt man A = n x, B = n y , C = n z und D = n T Ebenengleichung (6.4).
.
v , erhält man genau die
Ist ein Dreieck durch die drei nicht-kollinearen Punkte P l ,P 2 ,P 3 gegeben , so lässt sich der Normalenvektor zu diesem Dreieck mittels des Kreuzproduktes berechnen: n
= (P 2
-
P j)
X
(P 3
-
Pd
Das Kreuzprodukt zweier Vektoren (xl ,Yl,zd T und (X2,Y2,Z2)T ist definiert du rch: Xl ) ( X2) Y2 Yl X ( Zl Z2
(
ui :z2 - Y2 . zl ) zl . x 2 - z2 . Xl Xl . Y2 - X2 . YI
Das Kreuzprodukt ist null, falls die beiden Vektoren kollinear sind. Auf diese Weise erhält man den nicht-normierten Normalenvektor der Ebene aus Gleichung (6.4). Der Wert D in dieser Gleichung kann dann durch Einsetzen eines der Punkte des Dreiecks, d.h . der Ebene , bestimmt werden:
187
6.8 Normalenvektoren an Oberflächen
D = nT
. PI
Wird eine Oberfläche durch eine Freiformfläche beschrieben , ermittelt man den Normalenvektor in einem Punkt x( so,to) der Fläche als Normalenvektor zur Tangentialebene in diesem Punkt. Die Tangentialebene wird durch die beiden Tangentenvektoren an die para metrischen Kurven p( s) = x( s,to) und q(t) x( so,t) an der Stelle x (so,to) bestimmt:
(%s x( s,tolL
o
(%s
toto
b ij . B!n)(sl Bjm) (tolL,"
rn
n
J- O
t- O
~ BJrn) (ta) . ~ bij .
(ÖÖt x( so,t)) t=to
8ss
(ÖB (n)( )) 8 =8 0
(%t to~ b 'j . B!n)(so) . Bjm)(t)) '~'o n
rn
~ BJn)(So) .~bij.
Crn ( ÖB )(t)) jöt
t=t o
Diese beiden Tangentenvektoren verlaufen parallel zur Oberfläche an der Stelle
(so,to) und spannen somit die Tangentialebene an die Fläche in diesem Punkt auf. Das Kreuzprodukt der beiden Tangentenvektoren ergibt damit den Normalenvektor an die Fläche im Punkt x( so,to). Wenn eine gekrümmte Fläche in Form einer Freiformfläche durch Dreiecke angenähert wird, sollten die Normalenvektoren für die Dreiecke nicht erst nach der Approximation durch die Dreiecke bestimmt werden, sondern direkt aus den Normalenvektoren der Oberfläche. Es ist natürlich nicht möglich, den Normalenvektoren in jedem Punkt der Oberfläche zu speichern. Wenigstens zu den Punkten, die zur Definition der Dreiecke verwendet werden, sollten die Normalenvektoren der gekrümmten Fläche berechnet und abgespeichert werden. Auf diese Weise können einem Dreieck drei verschiedene Normalenvektoren zugeordnet sein, die alle nicht mit dem Normalenvektor der durch das Dreieck definierten Ebene übereinstimmen , so wie es in Abbildung 6.24 zu sehen ist.
6.8.1
Normalenvektoren in Java 3D
Für die elementaren geometrischen Objekte Quader, Kugel, Zylinder und Kegel werden die Normalenvektoren automatisch berechnet. Bei Objekten, die aus ei-
188
6 ModelIierung dreidimensionaler Körper
Abbildung 6.24 Normalenvektoren der Originalfläche in den Eckpunkten eines approximierenden Dreiecks
ner Datei z.B. im Wavefront Object Format geladen werden, stehen die benötigten Normalenvektoren ebenfalls in der Datei. Werden Objekte direkt in Java 3D mittels Dreiecken definiert, können die Normalenvektoren auch direkt angegeben werden. Dies wird man in der Praxis jedoch kaum benötigen, da man selten komplexe Objekte direkt mit Dreiecken modellieren wird, sondern eher ein entsprechendes 3D-Modellierungswerkzeug zu Hilfe nehmen wird. Trotzdem soll an dieser Stelle eine Methode beschrieben werden, mit der sich die Berechnung der Normalenvektoren in der Klasse GeometryArray steuern lässt. Bei der Erstellung eines Objekts aus Dreiecken in Java 3D mittels der Klasse GeometryArray muss, wie auf Seite 164 beschrieben, eine Instanz ng der Klasse NormalGenerator erzeugt werden. Man kann vor der Erzeugung der Normalenvektoren mit der Methode ng. generateNormals (g i ) für das GeometrylnfoObjekt gi noch die Methode ng .setCreaseAngle(angle); aufrufen. Der Winkel angle gibt an, bis zu welchem Winkel die Normalenvektoren benachbarter Dreiecke interpoliert werden sollen. Man geht davon aus, dass benachbarte Dreiecke, die fast in einer Ebene liegen, das heißt, zwischen denen ein kleiner Winkel liegt, dazu dienen , eine gekrümmte Fläche ohne Kanten oder Knicke anzunähern. Der zwischen den Dreiecken entstehende Knick ist eigentlich nicht erwünscht und nur durch die Approximation erzwungen. Deswegen sollten die Normalenvektoren in den Ecken der Dreiecke nicht individuell für jedes Dreieck als Normalenvektoren der jeweilgen Dreiecksebene bestimmt werden. Statt dessen mittelt man in den Ecken die Normalenvektoren aller benachbarten Dreiecke, die einen entsprechend kleinen Winkel mit dem betrachteten Dreieck bilden. Diese Vorgehensweise ist in der Abbildung 6.25 links veranschaulicht. Der
6.8 Normalenvektoren an Oberflächen
189
Winkel zwischen den beiden Dreiecken ist relativ klein 2 , so dass für die Normalenvektoren an den beiden gemeinsamen Eckpunkten der Vektor verwendet wird, der sich durch Mittlung aus den beiden tatsächlichen Normalenvektoren an die Ebenen ergibt, die durch die Dreiecke induziert werden. Rechts in der Abbildung liegt eine echte Kante zwischen den Dreiecken vor, die nicht zufällig durch die ungenaue Approximation entstanden ist. Daher werden die Normalenvektoren nicht interpoliert.
Abbildung 6.25
Interpolierte und nicht interpolierte Normalenvektoren
Mit dem Standardkonstruktor new NormalGeneratorO wird der Winkel auf den Wert Null gesetzt, so dass keine Interpolation von Normalenvektoren stattfindet. Mit der Methode setCreaseAngle kann der Winkel auf einen anderen Wert gesetzt werden, so dass im Extremfall sogar bei Dreiecken die Normalenvektoren gemittelt werden, die eine sehr scharfe Kante bilden. Im Programm NormalsForGeomArrays. java wird der gleiche Tetraeder wie im Programm GeomArrayExample. java erzeugt mit dem Unterschied, dass der Winkel zur Interpolation der Normalenvektoren auf it, d.h. 1800 gesetzt wurde, so dass die Normalenvektoren benachbarter Dreiecke immer interpoliert werden. Die vorher deutlich sichtbaren, scharfen Kanten des Tetraeders werden auf diese Weise fast unsichtbar. 2
Ein kleiner Winkel meint hier einen flachen, d.h. stumpfen Winkel. Der Winkel bezieht sich nicht auf den Winkel zwischen den Dreiecken, sondern wie weit eines der beiden Dreiecke gedreht werden müsste, damit sie in einer Ebene liegen.
190
6.9
6 ModelIierung dreidimensionaler Körper
Übungsaufgaben
Aufgabe 6.1: Die Oberfläche des dargestellten Körpers soll mit Dreiecken modelliert werden. Geben Sie geeignete Koordinaten für die sechs Knotenpunkte an sowie entsprechende Dreiecke, die aus diesen Knotenpunkten zu bilden sind. Achten Sie darauf, dass die Dreiecke so orientiert sind, dass die entgegen dem Uhrzeigersinn orientierte Fläche nach außen zeigt. Der Körper ist 2 zwei Einheiten hoch, eine Einheit tief und fünf Einheiten breit. Schreiben Sie anschließend ein Programm, um den Körper darzustellen. Verwenden Sie dazu die in Abschnitt 6.4 vorgestellte Technik. Aufgabe 6.2: Zeichnen Sie den QuadTree für das nebenstehende Dreieck bis einschließlich zur Tiefe 2. Die Wurzel (Ebene 0) des QuadTrees entspricht dem gestrichelten Quadrat.
Aufgabe 6.3: Stellen Sie die Kugeln aus Abbildung 6.12, die mit dem Programm TesselationResolution .java erzeugt wurden, als Drahtgittermodell dar. Stellen Sie ebenfalls das Schiff, das im Programm Load3DExample. java geladen wird, als Drahtgittermodell dar. Aufgabe 6.4: Zeichnen Sie mit Java 2D eine zweimal stetig differenzierbare geschlossene Kurve, indem Sie die Bedingungen in Abbildung 6.20 ausnutzen.
191
7
Visibilitätsbetrachtungen
Für die Darstellung eines Ausschnitts einer dreidimensionalen Modellwelt muss ebenso wie im Zweidimensionalen bestimmt werden, welche Objekte überhaupt in dem darzustellenden Bereich liegen. Nur für diese Objekte muss das Rendering durchgeführt werden. Bei dreidimensionalen Szenen muss zusätzlich zu diesen C1ippingberechnungen das Problem der Verdeckung von Objekten oder Objektteilen durch andere Objekte der Szene gelöst werden. Dieses Kapitel gibt eine Einführung in das dreidimensionale C1ipping und Verfahren zur Bestimmung der in einer Szene sichtbaren Objekte.
7.1
Das Clippingvolumen
Die Darstellung des Ausschnitts einer dreidimensionalen Modellwelt, den ein Betrachter sehen kann, erfordert eine Reihe von Angaben darüber, wie der Betrachter in die Modellwelt blickt. Die Koordinaten des Punktes, in dem sich der Betrachter befindet , und die Richtung , in die er schaut, müssen spezifiziert werden. Diese Informationen reichen jedoch noch nicht aus. Die Projektionsebene muss festegelegt werden. Sie entspricht der Ebene des Darstellungsmediums, in der Regel die Ebene des Bildschirms, mit dem der Betrachter die Szene wie durch ein Fenster sieht. Der Bildschirm oder das Darstellungsfenster auf dem Bildschirm können nur einen endlichen Ausschnitt der Projektionsebene wiedergeben. Üblicherweise ist dieser Ausschnitt rechteckig. Anstatt ein korrespondierendes Rechteck auf der Projektionsebene zu spezifizieren, wird häufig ein Winkel angegeben, der das Sichtfeld des Betrachters festlegt. Dieser Winkel definiert , wie weit sich das Blickfeld des Betrachters nach links und rechts öffnet. Daraus ergibt sich eine Breite auf der Projektionsebene, die der Breite des Darstellungsfensters auf dem Bildschirm entspricht. Die Höhe des Bereichs auf der Projektionsebene wird proportional zur Höhe des Darstellungsfensters gewählt. Abbildung 7.1 zeigt eine Draufsicht auf das Sichtfeld des Betrachters. Prinzipiell reichen diese Angaben zur C1ippingberechnung aus. Der dreidimensionale C1ippingbereich - das Clippingvolumen - entspricht einer Pyramide unendlicher Höhe im Fall perspektivischer Projektion bzw. einem sich einer Richtung
192
7 Visibilitätsbetrachtungen Fensterbreite - - - + - - - - - - - - . ; - - - Projektionsebene
Betrachter
Abbildung 7.1 Der Sichtfeldwinkel der der Fensterbreite entspricht.
Cl:
bestimmt den Bereich auf der Projektionsebene,
unendlich ausdehnenden Quader bei einer Parallelprojektion. Folgende Betrachtungen schränken das C1ippingvolumen jedoch weiter ein. Die Sichtweite eines Menschen ist zwar theoretisch nahezu unbegrenzt. Man kann sowohl Lichtjahre entfernte Sterne als auch das Gestell einer Brille direkt vor den Augen sehen. Beim Sehen werden die Augen jedoch auf eine Entfernung fokussiert, so dass es nicht möglich ist, gleichzeitig ein ganz nahes und ein sehr weit entferntes Objekt scharf zu sehen. Fixiert man beispielsweise ein weit entferntes Objekt und hält dann einen Finger relativ nahe vor ein Auge, sieht man diesen Finger fast nicht. Umgekehrt nimmt man beim Lesen eines Buches nicht wahr, wie ein Vogel in der Ferne vorbeifliegt. Der in einem Augenblick scharf sichtbare Bereich erstreckt sich daher üblicherweise von einer bestimmten minimalen bis zu einer bestimmten maximalen Entfernung. Diese Eigenschaft modelliert man in der Computergrafik, indem man eine vordere und eine hintere Clippingebene definiert. Bei einer perspektivischen Projektion nimmt das C1ippingvolumen so die Form eines Pyramidenstumpfes an, während eine Parallelprojektion einen Quader als C1ippingvolumen liefert. Die Projektionsebene liegt in der Entfernung, auf die die Augen des Betrachters optimal fokussiert sind. Die vordere und hintere C1ippingebene entsprechen dem kleinsten bzw. größten Abstand, bei dem der Betrachter bei der Fokussierung auf die Projektionsebene Objekte noch scharf wahrnehmen kann. Die Projektionsebene liegt üblicherweise zwischen der vorderen und hinteren C1ippingebene. Bei Objekten, die vor der Projektionsebene liegen, sollte für den Betrachter der Eindruck entstehen, dass sie sich vor dem Bildschirm befinden. Dieser Effekt ist jedoch nur mit Techniken zu erzielen, die stereoskopisches Sehen unterstützen, die im Kapitel 9 behandelt werden. Der Zusammenhang zwischen C1ippingvolumen, vorderer und hinterer C1ippingebene , Projektionsebene und Projektionsart ist in Abbildung 7.2 dargestellt.
193
7.1 Das C1ippingvolumen
hintere Clippingebene vordere Clippingebene hintere Clippingebene
vordere
Projektionsebene
Clippingebene Abbildung 7.2 Das C1ippingvolumen bei Parallelprojektion (oben) und bei perspektivischer Projektion (unten)
Im Abschnitt 5.8 wurde bereits erläutert, wie sich jede Projektion in eine Transformation T und eine anschließende Parallelprojektion auf die x/v-Ebene zerlegen lässt. Das dreidimensionale C1ipping kann daher auf folgende Weise einfach und effizient durchgeführt werden. Zuerst wird auf alle Objekte die Transformation T angewendet. Da die so transformierten Objekte mittels Parallelprojektion auf die x/v-Ebene abgebildet werden, entspricht das transformierte C1ippingvolumen einem Quader, dessen Kanten parallel zur den Koordinatenachsen verlaufen. Dieser Quader kann durch zwei diagonal gegenüberliegende Ecken (Xmin ,Ymin ,Zmin) und (xmax,Ymax,zmax) definiert werden. Um festzustellen, ob ein Objekt innerhalb dieses C1ippingvolumens liegt, muss nur überprüft werden, ob mindestens ein Punkt (Px ,py,pz) des Objekts innerhalb des Quaders liegt. Dies ist genau dann der Fall, wenn Xmin ~ Px ~ Xmax
und
Ymin ~ Py ~ Ymax
und
Zmin ~ pz ~ Zmax
gilt. Für ein ebenes Polygon müssen diese Vergleiche daher nur für alle Ecken durchgeführt werden, um festzustellen, ob das Polygon im C1ippingvolumen liegt.
194
7.1.1
7 Visibilitätsbetrachtungen
Clipping in Java 3D
Durch die Verwendung der Klasse SimpleUniverse werden die zum C1ipping erforderlichen Parameter auf Standardwerte gesetzt. Wie man die Position des Betrachters verändert, wurde bereits im Abschnitt 5.8.1 vorgestellt. Um den Sichtfeldwinkel oder die C1ippingebenen zu modifizieren, muss man auf den View des SimpleUniverse zugreifen, den man folgendermaßen erhält. View v
=
simpUniv .getViewer() .getView() ;
Mit der Methode v.setFieldOfView(angle); wird der Sichtfeldwinkel auf den Wert angle (im Bogenmaß) gesetzt. Zur Festlegung des Abstands der vorderen und hinteren C1ippingbene zum Betrachter dienen die Methoden: v.setFrontClipDistance(fcdist); v.setBackClipDistance(bcdist); Durch v .getPhysicalBody() .setNominalEyeOffsetFromNominalScreen( distance); kann der Abstand der Projektionsebene zum Betrachter verändert werden. In der Klasse ClippingPlanes .java wird der Sichtfeldwinkel auf 30° Grad gegenüber dem Standardwert von 45° verengt. Außerdem wird die vordere C1ippingebene weiter nach hinten und die hintere weiter nach vorn verschoben, so dass sich ein kleineres C1ippingvolumen ergibt. Mit diesen veränderten Einstellungen wird die in Abbildung 5.3 auf Seite 124 gezeigte Hubschrauberszene aus dem ursprünglichen Programm StaticSceneExample . java noch einmal wiedergegeben. Durch die Einengung des C1ippingvolumens werden Teile der Szene nicht mehr dargestellt.
7.2 Grundlagen der Visibilitätsverfahren
7.2
195
Grundlagen der Visibilitätsverfahren
Durch das C1ipping wird bestimmt, welche Objekte einer im Computer modellierten dreidimensionalen Welt zumindest teilweise im C1ippingvolumen liegen. Diese Objekte sind Kandidaten für die in der Szene darzustellenden Objekte. In der Regel werden aber nicht all diese Objekte sichtbar sein, da weiter hinten liegende Objekte von weiter vorne liegenden eventuell verdeckt werden. Visibilitätsverfahren 1 bezeichnen Techniken zum Zeichnen der Objekte, die tatsächlich vom Betrachter gesehen werden, das heißt, die nicht durch andere Objekte verdeckt werden. Da sich Projektionen durch das vorherige Ausführen einer geeigneten Transformation immer auf eine Parallelprojektion auf die xjy-Ebene zurückführen lassen, werden die Visibilitätsbetrachtungen in diesem Kapitel - sofern nicht anders angegeben - auf diesen Spezialfall der Parallelprojektion eingeschränkt.
7.2.1
Bildraum- und Objektraumverfahren
Ein einfacher Algorithmus zum Zeichnen der tatsächlich sichtbaren Objekte einer Szene könnte folgendermaßen vorgehen. Man denkt sich das Pixelraster auf die Projektionsebene gezeichnet und legt durch jedes Pixel einen Strahl in der Projektionsrichtung, d.h. parallel zur z-Achse. Ein Pixel ist so einzufärben, wie das Objekt, auf das sein zugehöriger Strahl zuerst trifft. Diese Technik wird als Bildraumverfahren bezeichnet, da sie die Pixelstruktur des zu konstruierenden Abbildes benutzt. Ein Bildraumverfahren hat bei p Pixeln und n Objekten einen Rechenaufwand von ti - p Schritten. Bei einer üblichen Bildschirmauflösung kann man von ungefähr einer Millionen Pixeln ausgehen. Die Anzahl der Objekte kann je nach Szene sehr stark schwanken. Unter Objekten sind hier die Dreiecke zu verstehen, mit denen die Oberflächen der komplexeren Objekte angenähert werden. Aus diesem Grund sind vier- oder fünfstellige Anzahlen von Objekten , d.h. Dreiecken, bei aufwendigeren Szenen keine Seltenheit. Im Gegensatz zu den Bildraumverfahren gehen die Objektraumverfahren nicht von den Pixeln aus , sondern bestimmen direkt für die Objekte, d.h. die Dreiecke, welche Objekte andere zumindest teilweise verdecken. Nur die sichtbaren Teile eines Objektes werden dann projiziert. Objektraumverfahren müssen die Objekte paarweise auf gegenseitige Verdeckung testen, so dass bei n Objekten ein Rechenaufwand von ca. n 2 , d.h. ein quadratischer Aufwand entsteht. Es gilt zwar 1
Im Englischen spricht man von Hidd en Line und Hidden Surface Algo rithmen.
196
7 Visibilitätsbetrachtungen
im Allgeimeinen, dass die Anzahl der Objekte deutlich kleiner als die Anzahl der Pixel, so dass n 2 « ri - p folgt, das heißt, die Objektraumverfahren müssen eine weitaus geringere Anzahl von Schritten als die Bildraumverfahren durchführen. Dafür sind die Einzelschritte bei den Objektraumverfahren wesentlich aufwendiger. Ein Vorteil der Objektraumverfahren besteht darin, dass sie unabhängig von der Bildauflösung berechnet werden können, da sie für die Visibilitätsbetrachtungen nicht auf die Pixel zugreifen. Erst bei der anschließenden Projektion der sichtbaren Objekte spielt die Bildauflösung eine Rolle.
7.2.2
Rückseitenentfernung
Unabhängig davon, welches Visibilitätsverfahren bevorzugt wird, sollte man vor der Anwendung die Anzahl der Objekte , d.h. der Dreiecke oder allgemeiner der ebenen Polygone durch Riickseitenenttemung' verringern. Mit Rückseiten sind Flächen gemeint, die vom Betrachter wegzeigen und die er somit nicht sehen kann. Diese Flächen können bei den Visibilitätsbetrachtungen vernachlässigt werden. Durch die im Abschnitt 6.1 beschriebene Orientierung der Flächen können die Normalenvektoren zu den Flächen so ausgerichtet werden, dass sie immer zur Flächenaußenseite zeigen. Zeigt ein so orientierter Normalenvektor vom Betrachter weg, sieht der Betrachter auf die Rückseite der Fläche und sie muss bei den Visibilitätsbetrachtungen nicht berücksichtigt werden. Bei der hier betrachteten Parallelprojektion auf die .1:/ y-Ebene verläuft die Projektionsrichtung parallel zur z-Achse. Der Betrachter sieht in diesem Fall auf die Rückseite einer Fläche, wenn der Normalenvektor der Fläche mit der z-Achse einen stumpfen Winkel bildet, das heißt, wenn er ungefähr in die entgegengesetzte Richtung der z-Achse zeigt. Abbildung 7.3 verdeutlicht diesen Sachverhalt anhand zweier Seiten eines Tetraeders. Die beiden parallelen Vektoren entsprechen der Projektionsrichtung und zeigen somit in Richtung der z-Achse. Die anderen beiden Vektoren sind die Normalenvektoren an die Vorder- bzw. Rückseite des Tetraeders. Man sieht, dass der Normalenvektor der sichtbaren Vorderseite in einem spitzen Winkel zur Projektionsrichtung steht, während der Normalenvektor der unsichtbaren Rückseite einen stumpfen Winkel mit der Projektionsrichtung bildet. Wenn ein stumpfer Winkel zwischen dem Normalenvektor einer Fläche und der Projektionsrichtung vorliegt, bedeutet dies, dass der Winkel größer als 90° ist. Berechnet man das Skalarprodukt des Normalenvektors n = (n x,n y,n z ) T mit 2
Englisch: Back Face Culling
7.2 Grundlagen der Visibilitätsverfahren
197
Abbildung 7.3 Eine vordere Fläche, deren Normalenvektor einen spitzen Winkel mit der z-Achse bildet, und eine hintere, deren Normalenvektor eine stumpfen Winkel ergibt, so dass die Fläche bei der Darstellung vernachlässigbar ist.
dem Projektionsrichtungsvektor, d.h. mit dem Einheitsvektor e z = (0,O,1)T in z-Richt ung, ergibt sich:
e; . n = cos(