Skript zum VortragGrundlagen der Computergrafik

Hanna PeetersCarsten Pauck

VR-GruppeRechen- und Kommunikationszentrum

RWTH Aachen

Betreuer: Jakob T. Valvoda

Dieses Dokument entstand im Rahmen der Seminarvortrage der Auszubil-denden zum Mathematisch-technischen Assistenten im dritten Lehrjahr desJahrganges 2002 am Rechen- und Kommunikationszentrum der Rheinisch-Westfalischen Technischen Hochschule Aachen. Es gibt einen Uberblick uberdie Grundlagen der Computergrafik.

1

Inhaltsverzeichnis

1 Einleitung 31.1 Anwendungsbereiche der Computergrafik . . . . . . . . . . . . 3

1.1.1 Architektur, Bauingenieurwesen . . . . . . . . . . . . . 41.1.2 Medizin . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.3 Wissenschaft und Technik . . . . . . . . . . . . . . . . 41.1.4 Filmindustrie . . . . . . . . . . . . . . . . . . . . . . . 51.1.5 Spieleindustrie . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Entstehung einer Grafik . . . . . . . . . . . . . . . . . . . . . 7

2 3D - Modellierung einer Grafik 82.1 Modellierungssoftware . . . . . . . . . . . . . . . . . . . . . . 82.2 Modellierungsprozess . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Virtuelle Welt und Weltkoordinatensystem . . . . . . . 112.2.2 Betrachterposition und Sichtvolumen . . . . . . . . . . 112.2.3 Modellierung von Korpern . . . . . . . . . . . . . . . . 112.2.4 Anmerkungen zum Licht . . . . . . . . . . . . . . . . . 192.2.5 Speicherung der Modelle in einem fur 3D Daten geeig-

neten Format . . . . . . . . . . . . . . . . . . . . . . . 20

3 Rendering 213.1 Transformationen, Ansichtsystem, Sichtvolumen . . . . . . . . 213.2 Clipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.3 Projektion auf 2D, Sichtbarkeit und Licht/Farben . . . . . . . 23

4 Geometrische Transformationen 244.1 Zweidimensionale Transformationen . . . . . . . . . . . . . . . 24

4.1.1 Elementare Transformationen . . . . . . . . . . . . . . 244.1.2 Homogene Koordinaten . . . . . . . . . . . . . . . . . . 264.1.3 Inverse zweidimensionale Transformationen . . . . . . 284.1.4 Eigenschaften affiner Transformationen . . . . . . . . . 28

4.2 Dreidimensionale Transformationen . . . . . . . . . . . . . . . 294.2.1 Translation . . . . . . . . . . . . . . . . . . . . . . . . 294.2.2 Skalierung . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2.4 Anwendung der Transformationen in Szene-Graphen . 31

5 Zusammenfassung 34

2

1 Einleitung

Im Rahmen unserer Seminararbeit wollen wir die Anwendungsgebiete furComputergrafiken beschreiben. Ferner erlautern wir, wie Computergrafikenentstehen. Schließlich erklaren wir Transformationen mit bekannten Metho-den der linearen Algebra.

Die Computergrafik ist ein Teilgebiet der grafischen Datenverarbeitung undbeschaftigt sich mit der Erzeugung, Beschreibung und Manipulation von Bil-dern mittels Computern.

Zur Eingrenzung des Themas soll eine Definition des Begriffes Computer-grafik vorangestellt werden. Nach einer ISO - Definition von 1982 umfasstdie Computergrafik:

”Methods and techniques for converting data to and from graphics displays

via computer“.

Diese Definition schließt sowohl die generative Computergrafik1 (Bilderzeu-gung) als auch die Bildanalyse2 (Mustererkennung) ein. Haufig werden bei-de Bereiche auch noch von der Bildverarbeitung abgegrenzt, die sich mitder Modifikation vorhandener Bilder (z. B. digitaler Fotografien) befasst. DieMustererkennung beschaftigt sich mit der Analyse von Bilddaten durch Zer-legung in bekannte grafische Objekte. Sie klart Fragen wie z. B. : Wo verlauftdie Straße? oder: Um welchen Buchstaben handelt es sich auf dem Bild?In unserer Ausarbeitung wollen wir uns ausschließlich mit generativer Com-putergrafik beschaftigen, d. h. wir wollen erlautern, wie eine Grafik entsteht.In Kapitel 2 erlautern wir die Grundlagen der Modellierung, Kapitel 3 gibteinen Uberblick uber den Renderingprozess. In Kapitel 4 werden Transfor-mationen an Grafiken mathematisch erklart.Weitere Informationen zu Bildverarbeitung und Bildanalyse finden sich in[Schurr 2000] bzw. [Soille 1998].

1.1 Anwendungsbereiche der Computergrafik

Die Anwendungsgebiete der Computergrafik sind vielfaltig.

1converting data to graphics displays2converting data from graphics displays

3

Abbildung 1: Therapieplanung [Mag 2004]

1.1.1 Architektur, Bauingenieurwesen

Heutzutage werden Zeichnungen meist nicht mehr am Zeichentisch, sondernam Computer erstellt. Mit Hilfe von CAD-Programmen (Computer AidedDesign) erstellen Architekten und Bauingenieure nicht nur Zeichnungen, son-dern auch virtuelle Modelle von Bauwerken.

1.1.2 Medizin

Anatomieausbildung wird mit Hilfe von Computergrafik gemacht. Chirurgi-sche Eingriffe werden zuerst mit einem Simulator trainiert. In der Diagno-se und Therapieplanung (siehe Abbildung 1.1.2) wird die Computergrafikbenotigt, z. B. um die Ergebnisse einer Computer-Tomographie dreidimen-sional darzustellen.

1.1.3 Wissenschaft und Technik

In der Wissenschaft wird die Computergrafik zur Darstellung von Funktio-nen, aber auch Molekulen, Kristallen oder Gensequenzen genutzt. Komple-xe Objekte werden interaktiv simuliert: Bei einem Viertaktmotor konnenz. B. Stromungen graphisch analysiert werden (siehe Abbildung 1.1.3). Einweitere wichtige Anwendung gibt es bei der Crash-Simulation, im KFZ- undFlugzeugbau. Bei der Produktion neuer Produkte spielt die Computergrafikauch eine wichtige Rolle, so kann anhand von virtuellen Prasentationen dasDesign und die Funktionalitat eines neuen Produktes uberpruft werden, wasbei der Realisierung Kosten spart.

4

Abbildung 2: Graphische Analyse von Stromungen [Mag 2004] [Vr2 2004]

Abbildung 3: ”The Matrix“, der Film wurde mit Hilfe von Softimage 3Dhergestellt.[Sof 2004]

1.1.4 Filmindustrie

In der Filmindustrie spielt die Computergrafik eine große Rolle. Der erstekomplett am Computer entstandene Kinofilm ist der Film Toy Story der Fir-ma PIXAR. Seitdem entstanden viele vollstandig am Computer produzierteFilme. Aber auch in Filmen wie Titanic oder Matrix (siehe Abbildung 1.1.4)wurden viele Spezialeffekte mit Hilfe der Computergrafik geschaffen.

1.1.5 Spieleindustrie

In Abbildung 1.1.5 ist ein Screenshot der Software 3D Studio Max zu sehen.Mit dieser Software wurden die Objekte fur das Spiel Tomb Raider 2 model-liert. Auf diese Software und die Modellierung wird in Kapitel 2 eingegangen.

5

Abbildung 4: Tomb Raider 2 wurde mit Hilfe von 3D Studio Maxproduziert.[RAI 2004]

6

1.2 Entstehung einer Grafik

Das Erzeugen einer Computergrafik vollzieht sich in mehreren voneinanderabgrenzbaren Teilschritten. Der erste Teilschritt ist die Modellierung, dannfolgt das Rendering. Die Gesamtheit der zum Rendering einer Grafik erfor-derlichen Teilschritte nennt man ublicherweise Renderingpipeline. Im drittenSchritt werden die Bilddaten auf ein Ausgabegerat ausgegeben. Die nach-folgende Abbildung 5 soll einen Uberblick uber die fur die Bilderzeugungerforderlichen Teilschritte geben. In unserer Ausarbeitung werden wir in Ka-pitel 2 einen Uberblick uber den Modellierungsprozess und in Kapitel 3 einenUberblick uber das Rendering geben. Auf die Ausgabe werden wir nicht ein-gehen.

Abbildung 5: Die Erzeugung einer Computergrafik wird in drei Teilschritte un-tergliedert. Zuerst muss ein Objekt modelliert werden, im zweiten Schritt wird esgerendert und zum Schluss ausgegeben.[Rechenberg und Pomberger 1997]

7

2 3D - Modellierung einer Grafik

Der erste Schritt bei der Bilderzeugung besteht darin, die Objekte, die inder Computergrafik erscheinen sollen, zu modellieren. Bei der Modellierungkonstruiert der Nutzer die darzustellenden Objekte. Diese Modellierung ge-schieht mit einer geeigneten Software.

2.1 Modellierungssoftware

Modellierungsprogramme ermoglichen dem Nutzer, auf verschiedene Arteneigene Modelle, aus denen eine Grafik erzeugt werden soll, zu erstellen.

Gegenwartig werden nachstehende Modellierungsprogramme eingesetzt. In-teressierte mogen prufen, ob eine kostenlose Demoversion oder eine Studie-rendenversion zum Herunterladen angeboten wird. Nachstehend findet maneine Liste einiger Modellierungsprogramme:

• Softimage 3D

– Modellierung, Animation, Rendering und Produktion im profes-sionellen Bereich

– Hersteller: Avid Technology Inc.

– Homepage: www.softimage.com

– Einsatz in Filmen: The Lost World: Jurassic Park, The Matrix,Star Wars: The Phantom Menace, Godzilla, Gladiator

– Plattform: SGI, Windows

• 3D Studio Max

– Modellierung, Animation, Rendering und Produktion im profes-sionellen Bereich

– Hersteller: Discreet (Autodesk)

– Homepage: www.discreet.com

– Einsatz in Filmen: Driven, Dungeons & Dragons, The Lost World:Jurassic Park

– Einsatz in Spielen: Tomb Raider 2, Myst, Age of Empires II, Sim-City 3000

8

– Plattform: Windows

– Screenshot : vgl. Abbildung 6 auf Seite 10

• Maya

– Modellierung, Animation, Rendering und Produktion im profes-sionellen Bereich

– Hersteller: Alias—Wavefront, division of Silicon Graphics Lt.

– Homepage: www.alias.com

– Einsatz in Filmen: Lord of the Rings Trilogy, Enemy at the Gates

– Einsatz in Spielen: Gran Turismo 3, Madden NFL 2001

– Plattform: Windows

• Blender3d

– Modellierung, Animation, Rendering

– Open Source, GNU GPL

– Homepage: www.blender3.com

– Kostenlos!

– Plattform: Windows, Linux

2.2 Modellierungsprozess

Mit Hilfe eines Modellierungsprogrammes lassen sich beliebige Objekte (z.B.Apfel, Auto, Comicfigur, etc.) als Grafik erzeugen. Diese konnen in verschie-denen Formaten (z. B. jpg, bmp, vrml) gespeichert werden.

Bei der Modellierung eines solchen Objektes ist seine Form (Volumen) undseine Oberflachenbeschaffenheit (Farbe, Material) festzulegen. Ferner defi-niert man die Position (Kameraposition) und Blickrichtung des Betrachtersauf die erzeugten Modelle. Desweiteren wird eine Lichtquelle definiert.

Diese Arbeitsschritte veranschaulichen wir an einem Beispiel in Abbildung6. Dort wird die Modellierung eines Gesichtes mit 3D StudioMax gezeigt.

9

Abbildung 6: Modellierung eines Gesichtes. Ansichtsfenster Vorn , Links , Obenzeigen Parallelprojektionen der Szene. Das Ansichtsfenster Kamera01 zeigt diePerspektive.

10

2.2.1 Virtuelle Welt und Weltkoordinatensystem

In dem unteren rechten Fenster (Kamera01) des Screenshots in Abbildung6 ist ein perspektivisches Gesicht zu sehen. Dieses Bild ist eine Projektioneiner dreidimensionalen virtuellen Welt auf eine zweidimensionale Flache.Das Koordinatensystem (Weltkoordinatensystem) ist in der linken unterenEcke angedeutet. Es wird benotigt, um jeder Geometrie (z. B. dem Gesicht)eine eindeutige Position zuweisen zu konnen.

2.2.2 Betrachterposition und Sichtvolumen

Es wird eine Betrachterposition und ein Sichtvolumen definiert. Aufgrunddieser Angaben wird der Inhalt des Bildes berechnet. Ferner ist seine Blick-richtung und sein Sichtvolumen zu bestimmen.

Im 3D Studio Max werden Betrachterposition und Sichtvolumen wie folgtdefiniert: Im Ansichtsfenster in Abbildung 6 unten links erkennt man eine(blau abgebildete) Kamera und eine Pyramide. Die Kamera legt die Positiondes Betrachters fest. Es wird zudem ein pyramidenformiges vom Betrach-ter ausgehendes Sichtvolumen (engl. viewing frustum) definiert. Wird eineComputergrafik erstellt, wird die Szene aus der Perspektive des Betrachtersabgebildet. Es werden nur die sich im Sichtvolumen befindlichen Gegenstandeabgebildet. Im Ansichtsfenster untern rechts - Kamera01 - sieht man die Sze-ne aus dieser Position und mit genau diesem Sichtvolumen.

Man kann eine fertige Computergrafik erzeugen. Das Erzeugen einer Gra-fik bezeichnet man auch als Rendern. Wird eine Grafik des aus der Kame-raperspektive betrachteten Modells gerendert, entsteht das in Abbildung 7abgedruckt Bild. Die Grafik liegt jetzt auch in einem geeigneten Dateiformat(jpg, gif, vrml usw.) vor.

2.2.3 Modellierung von Korpern

Wir wollen die Modellierung eines beliebigen Objektes (z. B. eines Gesichts)mit Hilfe von 3D Studio Max beschreiben.

Bei der Modellierung wird die Form des Objektes (also das Volumen) be-stimmt. Dann muss die Beschaffenheit der Oberflache (Farbe, Material) fest-gelegt werden. Wichtig ist auch die Bestimmung der Lichtverhaltnisse.

11

Abbildung 7: Computergrafik nach dem Rendering. Aufgrund der Schattierungim Gesicht erkennt man, dass eine (nicht sichtbare) Lichtquelle das Gesicht vonrechts beleuchtet. Ferner werden Schatten geworfen.

12

2.2.3.1 Modellierung der Form eines Korpers Fur die Bestimmungder außeren Form eines Objektes gibt es verschiedene Verfahren.

2.2.3.1.1 Constructive Solid Geometry Zur Volumenmodellie-rung konnen aus (von der Modellierungssoftware) bereitgestellten Primiti-ven (Quader, Kugel, Torus, usw.) komplexere Modelle erstellen werden. Soentstehen neue Modelle dadurch, dass man Primitive geeignet transformiertund sie dann mit anderen Primitiven schneidet oder vereinigt. Ferner ist dieBildung einer Differenz von zwei Objekten moglich.

Dieses Verfahren, aus einfachen Primitiven komplexere zu erstellen, nenntman Constructive Solid Geometry. Folgendes Beispiel soll dieses Verfahrenverdeutlichen. Es soll folgendes Objekt entstehen:

Abbildung 8: Ein aus vorgegebenen Primitiven erzeugtes Modell

Dazu war es erforderlich:

1. drei Zylinder (nach geeigneter Rotation) zu vereinigen (Abbildung 9)

2. einen Wurfel mit runden Kanten zu konstruieren, (Abbildung 10)

3. die Differenz aus den erzeugten Objekten zu bilden (Abbildung 11)

Bildet man die (richtige) Differenz der Objekte, entsteht das bereits in Ab-bildung 8 gezeigt Objekt.

2.2.3.1.2 Oberflachendarstellung Die Oberflachendarstellung istein weiteres Verfahren, Korper zu modellieren. Bei der Oberflachendar-stellung erfolgt die Beschreibung des Korpers uber die Beschreibung der

13

Abbildung 9: Es wurden Zyliner erzeugt, rotiert und verschoben. Dann wurdedie Vereinigungsmenge gebildet.

Abbildung 10: Es wurde eine Kugel und ein Quader erzeugt. Beide wurden ge-eignet inneinander verschoben. Dann wurde die Kugel herausgeschnitten (Bildungder Differenz). Es entsteht ein Wurfel mit runden Kanten.

Abbildung 11: Die erzeugten Objekte wurden verschoben, und die Differenzwurde gebildet.

14

Korperoberflache. Die Korperoberflache wird durch eine Vielzahl von Flachen(Dreiecke, Quadrate) naherungsweise beschrieben. Zur Veranschaulichungbeachte man die Abbildung 12 und Abbildung 6 zu sehen. Die Einteilung

Abbildung 12: Ein Saxofon wird durch Dreiecke naherungsweise beschrieben.

in Flachen (Dreiecke) erfolgt durch ein Drahtgitternetz. Dieses besteht ausden Scheitelpunkten (Vertices), Kanten und (folglich) Flachen. In Abbildung12 sind die Vertices blau eingezeichnet. Die Kanten sind weiss.

Bei der Konstruktion der Oberflachen ist Folgendes zu beachten:

• Die Oberflache muss geschlossen sein.An jede Kante mussen also zwei Flachen angrenzen.

15

• Die Flachen durfen sich nicht schneiden.

• Jede Flache muss orientierbar sein, d. h. sie muss zwei unterscheidbareSeiten haben.

Missachtet man diese Regeln, entstehen fehlerhafte Geometrien. Zur Ver-deutlichung haben wir eine Abbildung einer fehlerhaften Geometrie eingefugt(Abbildung 13).

Abbildung 13: Man erkennt, dass eine nicht abgeschlossene Geometrie fehlerhaftist. Loscht man eine beliebige Flache, ist nicht das Innere eines Korpers zu sehen- stattdessen wird die Geometrie fehlerhaft.

2.2.3.2 Datenstruktur Wir wollen die Datenstrukturen fur Geometrienerklaren. Korper werden dadurch beschreiben, dass ihre Oberflache durch ei-ne Polygonflache (z. B. eine Menge von Dreiecken ) naherungsweise beschrie-ben wird.

Eine solche Polygonflache kann durch drei sequentielle Listen, namlich ei-ne Flachen, Kanten- und Punktliste reprasentiert werden. Jede Flachenlistehat Zeigerverweise auf die begrenzenden Kanten in der Kantenliste. JedeKante wiederum verweist mittels Zeiger auf die entsprechenden Punkte inder Punkteliste.

Folgende Skizze mag die Datenstruktur erlautern. Soll die Position einer Geo-metrie in der virtuellen Welt verandert werden, mussen samtliche Punkte in

16

Abbildung 14: Beispiel fur die Speicherung einer Polygonflache.[Rechenberg und Pomberger 1997]

der Punktliste transformiert werden. Die Berechnungen werden mit Hilfe derMatrizenmultiplikation durchgefuhrt (vgl. Kapitel 4).

2.2.3.3 Der Begriff”Szene “ Eine virtuelle Welt, in der sich mehrere

Geometrien, Lichtquellen und ein Betrachter befinden, bezeichnet man alsSzene. Diese virtuelle Welt hat ein Koordinatensystem - das Weltkoordina-tensystem. Dieses Weltkoordinatensystem bezeichnet man auch als globalesKoordinatensystem. Zu jeder Geometrie gehort ein eigenes, lokales Koordi-natensystem. Abbildung 15 zeigt eine einfache Szene mit zwei Geometrien.Es gibt drei Koordinatensysteme: Das Weltkoordinatensystem, welches imGitternetz angedeutet ist und je ein Koordinatensystem fur jede Geometrie.Erfolgen Transformationen (vgl. Kapitel 4), muss definiert werden bezuglichwelchem Koordinatensystem die Transformationen erfolgen sollen.

2.2.3.4 Der hierarchische Aufbau einer Szene Ein nutzlichen Hilfs-mittel beim Erstellen von Grafiken ist die Fahigkeit, Objekte hierarchisch zuordnen. Indem man Objekt hierarchisch ordnet, stellt man eine Beziehungzwischen unter- und ubergeordnetem Objekt her. Transformationen, die aufdas ubergeordnete Objekt angewendet werden, werden an das untergeordne-te Objekt weitergegeben.

Beispiel: Angenommen, wir konstruieren ein Flugzeug, das aus einem Rumpf,Flugeln und Motoren besteht. Wenn wir den Rumpf verschieden, sollen sichFlugel und Motor automatisch mitbewegen. Somit bietet sich ein hierachi-scher Aufbau der Szene an. Der Rumpf ist ubergeordnet, Flugel und Motorsind nachgeordnet. Weitere Anmerkungen zum Scenegraphen findet man in

17

Abbildung 15: Jede Geometrie hat ihr eigenes Koordinatensystem. Zusatzlichgibt es das Weltkoordinatensystem (unten links).

18

Kapitel 4.2.4.

2.2.4 Anmerkungen zum Licht

Wir mochten Anmerkungen zur Ausleuchtung der Szene machen. Die Aus-leuchtung der Szene wird durch die Definition einer Lichtquelle bestimmt.Das Licht reagiert mit den in der Szene befindlichen Objekten. So wird z.B.die Farbe der Oberflache eines Objektes auch durch die Farbe des das Objektanstrahlenden Lichts bestimmt. Ausserdem bewirkt eine geeignete, von derLichtquelle abhangige Schattierung des Objektes, das perspektivische Aus-sehen. Die genannten Effekte werden an Beispielen veranschaulicht:

Abbildung 16: Erst nachdem eine Lichtquelle definiert und die Kugel geeignetschattiert wird, wirkt die Kugel perspektivisch.

Abbildung 17: Die vom Betrachter wahrgenommene Farbe wird von der Farbedes Objektes und der Farbe des das Objekt anstrahlenden Lichts bestimmt: Deswe-gen erscheint ein gelber Farbton auf der Oberflache der schwarze Kugel, nachdemsie mit gelbem Licht bestrahlt wurde (links). Eine hellblaue Kugel (rechts) wirdmit weissem Licht bestrahlt. Durch eine Schattierung entsteht der perspektivischeEffekt.

19

Zusammenfassend gilt :

• Ein Gegenstand, z.B. eine Kugel, wirkt erst durch eine geeignete Schat-tierung perspektivisch.

• Die Farbdarstellung der Kugel hangt von der Farbe der Kugel und vonder Farbe des ausgestrahlten Lichts ab.

2.2.5 Speicherung der Modelle in einem fur 3D Daten geeignetenFormat

Ein Modell kann in einer VRML Datei abgespeichert werden. VRML bedeu-tet Virtual Reality Modeling Language und ist eine Beschreibungssprachefur 3D-Szenen und Geometrien, Ausleuchtungen, Animationen und Interak-tionsmoglichkeiten. Es kommen aber auch andere Dateiformate in Betracht.

20

3 Rendering

Eine komplexere Computergrafik wird aus einzelnen Modellen (Geometri-en) zusammengesetzt. Diese werden mit einem Modellierungsprogramm er-stellt. Die (verschiedenen) Geometrien werden zu einem fertigen Gesamtbildzusammengefugt. Die Erzeugung des Bildes bezeichnet man als Rendering.Das Rendering des Bildes vollzieht sich in den in Abbildung 5 dargestelltenTeilschritten.

3.1 Transformationen, Ansichtsystem, Sichtvolumen

Der erste Teilschritt bei der Bilderzeugung besteht darin, die einzelnen Geo-metrien an den gewunschten Stellen zu plazieren. Dazu wird ein dreidimen-sionaler Raum (virtuelle Welt) mit einem kartesischen Koordinatensystem(Weltkoordinatensystem) definiert. Durch Transformationen (Translation,Rotation, Skalierung) werden die modellierten Objekte an die gewunschtePosition gesetzt. Die Skizze a) aus Abbildung 18 veranschaulicht, was einevirtuelle Welt oder ein Weltkoordinatensystem ist. Eine perspektivische Sichteiner virtuellen Welt zeigt auch Abbildung 6.

Desweiterern wird im Weltkoordinatensystem die Position des Betrachters(Blickpunkt) und seine Blickrichtung festgelegt. Ausgehend von dem Blick-punkt und der Blickrichtung des Betrachters legt man ein Sichtvolumen fest- vgl. Abbildung 18 d). Fur die Modellierung mit 3D Studio Max ist dieDefinition eines Betrachters und des Sichtvolumens bereits in Abbildung 6gezeigt worden.

3.2 Clipping

Es werden nur die Objekte aus der virtuellen Welt angezeigt, die im Sichtvo-lumen liegen. Die uber dieses Sichtvolumen herausragenden Objekte werdenentfernt. Diesen Vorgang nennt man Clipping. Es gibt verschiedenen Ver-fahren, um Linien und Polygone zu clippen. Zwei interessante Algorithmensind:

• Clippen von Linien mit Hilfe des Cohen-Sutherland Algorithmus

• Clippen von Polygonen mit Hilfe des Sutherland-Hodgman Algorith-mus

21

Abbildung 18: Es ist ein dreidimensionaler Raum durch ein Koordinatensystemangedeutet. Ferner ist die Betrachterposition, das Auge, eingezeichnet (a). Ausge-hend von der Betrachterposition wird ein Sichtvolumen erzeugt(d). [Watt 2002]

22

3.3 Projektion auf 2D, Sichtbarkeit und Licht/Farben

Da die Ausgabegerate (z. B.Monitor) in der Regel nur ein zweidimensionalesBild erzeugen, ist eine Abbildung zu definieren, die die Objekte aus der vir-tuellen Welt (3D) auf eine (2D) Ebene (Ansichtsebene) projiziert, die dann(nach Rasterisierung) auf dem Bildschrirm angezeigt werden kann.

Diese Ansichtsebene ist in Abbildung 18 Bild d) eingezeichnet. Die Objekteaus dem dreidimensionalen Raum, die im Sichtvolumen liegen, werden aufdie Ansichtsebene projiziert. Aus dieser Projektion entsteht nach Rasterisie-rung die fertige Computergrafik.

Moglicherweise verdecken sich auch die Objekte. So kann ein Objekt sichhinter einem anderen Objekt befinden. Es wird dann berechnet, welches die-ser Objekte in der Grafik sichtbar ist. Desweiteren sind die Helligkeits- undFarbwerte fur die Objekte zu berechnen. Sofern Schatten fallen, sind auchdiese zu berechnen. Nach diesem Schritt ist der Renderingprozess beendet.

23

4 Geometrische Transformationen

Bei Grafiken sind neben der Modellierung der darzustellenden Objekte, die inKapitel 2 vorgestellt wurde, und ihrer Erstellung (vgl. Kapitel 3) auch Mani-pulationsmoglichkeiten von großer Bedeutung. Das Thema Transformationenwird mit Hilfe der linearen Algebra behandelt.

4.1 Zweidimensionale Transformationen

In diesem Kapitel werden grundlegende geometrische Transformationen, diein der Computergrafik verwendet werden, vorgestellt. Mit Hilfe der Trans-formationen ist es moglich, Position, Orientierung, Form und Große von Ob-jekten zu manipulieren. Es werden die Fragen geklart, wie man Bewegungenbeschreiben kann und wie man die Positionen von Objekten nach einer Be-wegung berechnet. Man unterscheidet zwischen folgenden Transformationen:

- Translation (Verschiebung)- Skalierung (Großenveranderung)- Rotation (Drehung)- Scherung- Spiegelung

In diesem Kapitel gehen wir nur auf die Translation, die Skalierung unddie Rotation ein. Die Anderung grafischer Objekte wird allgemein durchmathematische Operationen auf den Definitionspunkten der Objekte (densogenannten Vertices vgl. Kapitel 2, Abschnitt 2.2.3.1.2) beschrieben. DieDefinitionspunkte sind in einer Punktliste gespeichert (vgl. Abbildung 14).Die meisten wichtigen Transformationen sind lineare Abbildungen, das be-deutet, dass sie folgende Eigenschaft haben: f(cx + y) = cf(x) + f(y). Einewichtige Transformation die nicht zu den linearen Abbildungen gehort ist dieTranslation. Durch Berechnung der Translation mit homogenen Koordinaten(vgl. Abschnitt 4.1.2) wird die Translation linear.

4.1.1 Elementare Transformationen

4.1.1.1 Translation Die Translation kann durch einen Vektor (dx, dy)T,der die Verschiebungsweite in x- und y-Richtung angibt, beschrieben werden.Der Punkt (x’,y’)T wird durch Addition des Verschiebungsvektors berechnet.

24

(x′

y′

)=

(xy

)+

(dxdy

)(1)

4.1.1.2 Skalierung Bei der Skalierung wird zwischen uniformer undnichtuniformer Skalierung unterschieden.

Uniforme Skalierung Das Zentrum der Skalierung ist der Nullpunkt, dieSkalierung erfolgt in alle Richtungen uniform mit dem skalaren Faktor α. DerOrtsvektor zum Punkt (x,y)T wird auf das α -fache verlangert um (x’,y’)T

zu erhalten.

(x′

y′

)= α ·

(xy

)(2)

Nichtuniforme Skalierung Das Zentrum der Skalierung ist der Nullpunkt,die Skalierung erfolgt in x-Richtung mit dem Faktor α , in y-Richtung mitdem Faktor β. Der Ortsvektor zum Punkt (x,y)T wird auf das α -fache inx-Richtung und das β -fache in y-Richtung verlangert.

(x′

y′

)=

(αxβy

)(3)

4.1.1.3 Rotation Der Punkt (x,y)T wird um den Winkel α um den Null-punkt gedreht, so dass sich der Punkt (x’,y’)T ergibt. Positive Werte von αergeben eine Drehung entgegen dem Uhrzeigersinn.

Herleitung der Berechnungsvorschrift:

Wir schreiben den Vektor (x,y)T in radialen Koordinaten (siehe Abbildung19).

x = r · cos(φ) (4)

y = r · sin(φ) (5)

x′ = r · cos(α + φ) = r · cos(φ) · cos(α)− r · sin(φ) · sin(α) (6)

y′ = r · sin(α + φ) = r · cos(φ) · sin(α) + r · sin(φ) · cos(α) (7)

25

Abbildung 19: Herleitung der Berechnungsvorschrift fur die Rotation mit Hilferadialer Koordinaten. [Mag 2004]

(4) in (6) und (5) in (7) eingesetzt, ergibt:

x′ = x · cos(α)− y · sin(α) (8)

y′ = x · sin(α) + y · cos(α) (9)

Diese Berechnungsvorschrift kann als Matrixmultiplikation ausgedruckt wer-den:

(x′

y′

)=

(cos(α) − sin(α)sin(α) cos(α)

)·(

xy

)(10)

Die vorgestellten Berechnungsvorschriften fur Transformationen sind nichteinheitlich. Zum einen gibt es die Vektoraddition fur die Translation, zumanderen wird bei der Skalierung ein Faktor multipliziert. Schließlich gibt esnoch die Matrixmultiplikation fur die Rotation. Dadurch wird es schwieriger,Transformationen zusammenzusetzen. Gesucht wird nun eine einheitliche Re-prasentation der Transformationen. Mit Hilfe von homogenen Koordinatenkonnen alle Transformationen durch Matrixmultiplikation realisiert werden.

4.1.2 Homogene Koordinaten

Die bisher behandelten Berechnungsvorschriften fur Transformationen habennoch den Nachteil, dass sie einen Fixpunkt, den Nullpunkt, besitzen. Man

26

muss erreichen, dass der Fixpunkt außerhalb der Bildebene liegt. Dazu fuhrtman eine dritte Dimension ein und nimmt als Bildflache die Ebene z=1.Der Fixpunkt liegt außerhalb der Bildebene. Ein Punkt (x,y)T wird in ei-nem homogenen Koordinatensystem durch das Tripel (x,y,1)T reprasentiert.Homogene Koordinaten von zweidimensionalen Punkten durfen nicht mitdreidimensionalen Punkten verwechselt werden. Der Vorteil ist nun, dass diePositionen nach den Transformationen einheitlich berechnet werden konnen,namlich mit Hilfe der Matrixmultiplikation. Die Transformationen werdennun durch 3x3-Matrizen beschrieben.

x′

y′

1

= T ·

xy1

(11)

4.1.2.1 Translation Bis jetzt wurde eine Translation durch Additioneines Verschiebungsvektors beschrieben. Nun wird die Verschiebung durchMultiplikation mit einer Translationsmatrix berechnet (siehe Gleichung (12)).

x′

y′

1

=

1 0 dx0 1 dy0 0 1

·

xy1

(12)

4.1.2.2 Skalierung Die Skalierung wird nicht mehr durch komponenten-weise Multiplikation berechnet, sondern indem man eine Skalierungsmatrixder Form wie in Gleichung (13) multipliziert.

x′

y′

1

=

α 0 00 β 00 0 1

·

xy1

(13)

4.1.2.3 Rotation Die Berechnung der Rotation (siehe Gleichung (14))wird ebenfalls durch Multiplikation mit einer Rotationsmatrix durchgefuhrt.

x′

y′

1

=

cos(α) − sin(α) 0sin(α) cos(α) 0

0 0 1

·

xy1

(14)

27

4.1.3 Inverse zweidimensionale Transformationen

Ein weiterer Vorteil der Darstellung der Transformationen in Matrizenformwird deutlich, wenn man eine Transformation ruckgangig machen will. Durcheinfaches Invertieren der Transformationsmatrix erhalt man die Matrix, umdie Transformation ruckgangig zu machen.

4.1.3.1 Translation Die Inverse der Translationsmatrix ist in Gleichung(15) zu sehen. Die Translation wird ruckgangig gemacht, indem man den ne-gativen Verschiebungsvektor (-dx,-dy)T addiert.

xy1

=

1 0 −dx0 1 −dy0 0 1

·

x′

y′

1

(15)

4.1.3.2 Skalierung Die Skalierung wird ruckgangig gemacht, indem manmit dem reziproken Skalierungsfaktor multipliziert. Die Matrix in Gleichung(16) entspricht der Inversen der Skalierungsmatrix.

xy1

=

1/α 0 00 1/β 00 0 1

·

x′

y′

1

(16)

4.1.3.3 Rotation Eine Rotation kann ruckgangig gemacht werden, in-dem man den Punkt mit dem Winkel -α um den Nullpunkt rotiert. Da Ro-tationsmatrizen orthogonal sind, folgt daraus: R-1 = RT

xy1

=

cos(α) sin(α) 0− sin(α) cos(α) 0

0 0 1

·

x′

y′

1

(17)

4.1.4 Eigenschaften affiner Transformationen

Homogene Koordinaten ermoglichen Vereinheitlichung und Kombination al-ler geometrischen Transformationen. Matrixmultiplikationen sind im Allge-meinfall nicht kommutativ. Das bedeutet, dass die Reihenfolge der Trans-

28

formationen ausschlaggebend fur das Ergebnis ist. In einigen Fallen bestehtKommutativitat:- Nacheinanderausfuhrung von Translationen- Nacheinanderausfuhrung von Skalierungen- Nacheinanderausfuhrung von Rotationen

Jede Sequenz von Rotationen, Translationen und Skalierungen erhalt dieParallelitat von Linien, aber nicht Langen und Winkel. Solche Transforma-tionen heißen affine Transformationen. Affine Abbildungen sind geradentreu,parallelentreu, teilverhaltnistreu. Sie sind nicht verhaltnistreu in Bezug aufTeilflachen, nicht langentreu, nicht winkeltreu und nicht flachentreu.

4.2 Dreidimensionale Transformationen

Die Vorgehensweise bei dreidimensionalen Transformationen ist gleich derVorgehensweise bei zweidimensionalen Transformationen. Sie lassen sichdurch Hinzunehmen einer dritten Koordinate relativ einfach aus den zweidi-mensionalen Transformationen (siehe Abschnitt 4.1) herleiten. Wie im Zwei-dimensionalen werden die Transformationen wieder durch Matrizen darge-stellt. Im Raum handelt es sich um 4x4 Matrizen.

4.2.1 Translation

Die Translation im Raum entspricht einer Addition des Verschiebungsvek-tors (dx,dy,dz)T. Sie lasst sich mit Hilfe von homogenen Koordinaten wie inGleichung (18) darstellen.

T =

1 0 0 dx0 1 0 dy0 0 1 dz0 0 0 1

(18)

4.2.2 Skalierung

Eine Skalierung erhalt man, indem man um das α-fache in x-Richtung ska-liert, um das β-fache in y-Richtung und um das γ-fache in z-Richtung. Hier-bei muss gelten α 6= 0, β 6= 0, γ 6= 0. Das Zentrum der Skalierung liegt im

29

Nullpunkt. Es handelt sich um eine uniforme Skalierung, wenn gilt: α=β=γ.

S =

α 0 0 00 β 0 00 0 γ 00 0 0 1

(19)

4.2.3 Rotation

Die Rotation im Raum ist komplexer als in der Ebene, da man statt einemDrehzentrum eine Drehachse benotigt. Handelt es sich bei der Drehachse umeine der positiven x-, y-, z-Achsen, so spricht man von einer kanonischenRotation. Wie im zweidimensionalen Fall werden auch die dreidimensionalenTransformationen durch Verknupfung homogener Koordinaten mit Transfor-mationsmatrizen beschrieben.

4.2.3.1 Kanonische Rotation Gleichung (20) zeigt die Transformati-onsmatrix fur die Rotation um die positive x-Achse.

Rx =

1 0 0 00 cos(α) −sin(α) 00 sin(α) cos(α) 00 0 0 1

(20)

Gleichung (21) zeigt die Transformationsmatrix fur die Rotation um die po-sitive y-Achse.

Ry =

cos(α) 0 sin(α) 00 1 0 0

−sin(α) 0 cos(α) 00 0 0 1

(21)

Gleichung (22) zeigt die Transformationsmatrix fur die Rotation um die po-sitive z-Achse.

30

Rz =

cos(α) −sin(α) 0 0sin(α) cos(α) 0 0

0 0 1 00 0 0 1

(22)

4.2.3.2 Rotation um eine beliebige Achse Die Rotation um eine be-liebige Achse lasst sich durch eine Folge von elementaren Transformationenbeschreiben. Die kompakte Darstellung erfolgt durch Zusammenfassung dereinzelnen Transformationsmatrizen zu einer einzigen Matrix. Folgende Schrit-te mussen fur eine Rotation um eine gegebene Drehachse mit einen Winkelα durchgefuhrt werden:

1. Translation der Rotationsachse und des zu drehenden Objekts, so dassdie Achse durch den Ursprung verlauft

2. Rotation der Drehachse um die x-Achse in die xz-Ebene

3. Rotation der Drehachse um die y-Achse in die z -Achse

4. Rotation des Objektes um die z-Achse mit dem Winkel α

5. Rucktransformation der Drehachse sowie des gedrehten Objektes in ih-re ursprungliche Lage durch Anwendung der inversen Transformationender Schritte (3), (2) und (1)

Selbstverstandlich kann statt der z-Achse auch jede andere Koordinatenachseverwendet werden.

4.2.4 Anwendung der Transformationen in Szene-Graphen

Dreidimensionale Modelle werden mit Hilfe von Szene-Graphen verwaltet.Unter einem Szene-Graphen versteht man eine gewohnliche Baumstrukturmit Knoten und Kanten. In Abbildung 21 sieht man am Beispiel eines Flug-zeuges einen schematisch dargestellten Szene-Graphen. Abbildung 20 zeigtdie einzelnen Teile eines Flugzeugmodells und wie sie zusammen gesetzt wer-den. Die Transformationen werden auf die einzelnen Knoten bzw. Aste an-gewandt. Jeder Ast des Szene-Graphen speichert eine lokale Transformation,diese werden miteinander multipliziert, um die Gesamttransformation zu er-halten. Ein typisches Szene-Graph-Format (es gibt zahlreiche Varianten)ist Folgendes: Graphische Primitive (grundlegende Objekte, wie z. B.Wurfel,

31

Abbildung 20: Zusammensetzung des Modells eines Flugzeuges [Viz 2004]

Abbildung 21: Scene-Graph des Flugzeug-Modells [Viz 2004]

32

Abbildung 22: Scene-Graph des Flugzeug-Modells

Kugel, Kegel etc. vgl. Kapitel 2) bilden die Blattknoten des Graphen. Trans-formationen sind ebenfalls Knoten des Graphen und werden auf Objekt-knoten je nach deren Lage im Graphen angewandt. In den Transformati-onsknoten sind die Transformationsmatrizen gespeichert. Die Gesamttrans-formation, die auf einen Objektknoten angewandt wird, erhalt man, indemman die Matrizen aus den Transformationsknoten bei top-down-Durchlaufdes Baumes miteinander multipliziert. Weitere Details sind abhangig vomGrafikpaket (z. B.VRML, Java3D etc.)

33

5 Zusammenfassung

In dieser Seminararbeit haben wir beschrieben, in welchen Bereichen Compu-tergrafik genutzt wird. Desweiteren haben wir einen Eindruck vermittelt, wieComputergrafiken modelliert werden. Zudem haben wir die Arbeitsschrittebeim Rendern einer Grafik beschrieben. Schließich haben wir mathematischeGrundlagen erortert, denen man bei der Beschaftigung mit Computergrafikbegegnet.

Diejenigen, die sich vertieft mit der Erzeugung von Grafiken beschafti-gen wollen, konnen die Modellierungssoftware blender3d (vgl. Kapitel2.1.)herunterladen. Ferner ist der unter der URL www.webreference.com/3dveroffentlichte Lehrgang interessant. Zur Vertiefung empfehlen wir das Stan-dardwerk von Foley [Foley et al. 1990].

34

Literatur

[Mag 2004] (2004). http://isgwww.cs.uni-magdeburg.de/graphik/lehre/cg1/ .Vorlesung Computergrafik I, Otto-von-Guericke-Universitat Magdeburg,Institut fur Simulation und Graphik. letzter Besuch Oktober 2004.

[Viz 2004] (2004). http://viz.aset.psu.edu/jack/java3d/slides/mt0026.htm.Penn State’s Visualization Group. letzter Besuch September 2004.

[Vr2 2004] (2004). http://www.rz.rwth-aachen.de/vr/ . RWTH Aachen. letz-ter Besuch September 2004.

[Sof 2004] (2004). http://www.softimage.com/ . Avid Technology Inc. letzterBesuch September 2004.

[RAI 2004] (2004). http://www.traider.pl . Fanclub Tomb Raider. letzterBesuch September 2004.

[Foley et al. 1990] Foley, J, A. van Dam, S. Feiner und J. Hughes(1990). Computer Graphics - Principles and Practice. Addison-Wesley.

[Rechenberg und Pomberger 1997] Rechenberg, Peter undG. Pomberger (1997). Informatik-Handbuch. Carl Hanser Ver-lag, Munchen, Wien.

[Schurr 2000] Schurr, Ulrich (2000). Handbuch digitale Bildverarbei-tung . dpunkt-Verlag, Heidelberg.

[Soille 1998] Soille, Pierre (1998). Morphologische Bildverarbeitung .u.a.: Springer, Berlin.

[Watt 2002] Watt, Alan (2002). 3D-Computergrafik . Addison-Wesley.

35