Grundlagen der 3D-Modellierung

Christian Fraß

July 17, 2009

Contents

1 Allgemeines 21.1 Einfuhrung und Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Mathematische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Szenen-Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Direkte Darstellungsschemata 52.1 Zerlegung in Zellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Konstruktive Festkorpergeometrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Indirekte Darstellungsschemata 83.1 Drahtgitter- und Oberflachen-Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2.1 Delaunay-Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.2 Minimal-Gewicht-Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Freiformkurven und -flachen 114.1 Interpolations-Techniken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.1.1 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.1.2 Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.2 Approximations-Techniken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2.1 Bezier-Kurven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.2.2 Nicht-uniforme rationale B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5 Sonstige Modellierungstechniken 185.1 Lindenmayer- und iterierte Funktionen-Systeme . . . . . . . . . . . . . . . . . . . . . . . . 185.2 Partikelsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6 Abschluss 206.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206.2 Verwendete Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206.3 Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1

Chapter 1

Allgemeines

1.1 Einfuhrung und Motivation

Die geometrische Modellierung beschaftigt sich mit der Beschreibung und Erfassung von Formen undAttributen geometrischer Objekte sowie der Bereitstellung geeigneter Datenstrukturen und Algorithmenzur Speicherung und Manipulation derselbigen. In der Regel ist dies mit einem hohen Maß an Abstrak-tion und Idealisierung verbunden, sodass man zwischen Exaktheit und Nutzen abwagen muss. Da dieUmsetzung der Techniken zur Modellierung meist rechnergestutzt erfolgt, spricht man auch von com-puter aided geometric design (kurz: CAGD). Auf welche Aspekte man sich konzentriert, hangt vomKontext ab, in welchem die zu beschreibenden Objekte erfasst werden sollen, sodass sich die Umsetzun-gen der Theorie je nach Fachgebiet und Verwendungszweck voneinander unterscheiden. Hauptsachlichfindet die geometrische Modellierung in der Computergrafik Anwendung, wird aber auch fur physikalis-che Simulationen und ahnliches eingesetzt. Im Bereich der Computergrafik legt man den Fokus auf jeneObjekt-Informationen, welche fur die Darstellungen von Belangen sind. Meist ist dabei unwichtig, wieein Korper im Inneren beschaffen ist, sondern nur, wie er optisch nach außen hin wirkt. Im Folgendenwerden die verschiedenen Methoden zur Beschreibung geoemtrischer Formen unter dem Gesichtspunktder Visualierung vorgestellt und gegeneinander abgewogen.

Ablaufschema: vom physikalischen Korper zur informatischen Beschreibung und Darstellung

2

1.2 Mathematische Grundlagen

Das wichtigste Theorie-Werkzeug fur die Modellierung ist zweifelsohne die Mathematik. Viele geometrischenGebilde lassen sich in Form einer einfachen Relation oder Funktion definieren. Hier ein paar Beispiel, wieman einfache Formen als bestimmte Relationen beschreiben kann:

ellipsoid(r1, r2, r3) =

(x, y, z) ∈ R3 |

(x

r1

)2

+(y

r2

)2

+(z

r3

)2

= 1

kugel(r) = ellipsoid(r, r, r)

torus(rH , rN ) =

(x, y, z) ∈ R3 |(x2 + y2 + z2 + r2H − r2N

)2= 4r2H

(x2 + y2

)

Die Kombination von Objekten zu komplexeren Strukturen kann dann einfach mit Hilfe von Mengen-Operatoren bzw. stuckweiser Definition realisiert werden. Dabei gilt es allerdings die Sinnhaftigkeit derentstehenden Objekte zu gewahrleisten und da kommt das Fachgebiet der Topologie ins Spiel. Diesesermoglicht die Untersuchung und Klassfikation von Objektformen und Beziehungen zwischen diesen. Fureinige Modellierungs-Techniken ist die Regularisierung von Teilmengen topologischer Raume ein wichtigesWerkzeug, welches es ermoglicht isolierte und ’baumelnde’ Segmente topologischer Raume zu elinieren:Sei X eine Untermenge des Gebietes Ω.

• x heißt Randpunkt von X, wenn jede Umgebung von x Elemente von X und von Ω \X enthalt

• x heißt innerer Punkt von X genau dann, wenn es eine Umgebung U von x gibt, mit U ⊆ X

• der Rand von X ist definiert als δ(X) := x ∈ Ω | x ist Randpunkt von X

• das Innere von X ist definiert als ι(X) := X \ δ(X)

• der Abschluss von X ist definiert als α(X) := X ∪ δ(X)

• die Regularisierung von X ist definiert als %(X) := α(ι(X))

• X heißt offen genau dann, wenn X = ι(X)

• X heißt abgeschlossen genau dann, wenn X = α(X)

• X heißt regular genau dann, wenn X = %(X)

Veranschaulichung der definierten Funktionen

3

Damit fuhrt man die regularisierten Mengen-Operationen ein (es gelte ∈ ∪,∩, \):

X ∗ Y := % (X Y )

1.3 Szenen-Graph

Haufig ist es sinnvoll, die Objekte, die man modellieren mochte in einer baumartigen Datenstrukturanzuordnen, welche die Szene hierarchich beschreibt. Das hat den Vorteil, das einzelne Teile der Szene,welche logisch zusammen gehoren, einerseits als atomare Objekte behandelt werden konnen und ander-seits diese selbst eine Szene darstellen, welche auf die gleiche Weise zerlegt werden kann, was in einerhoheren Kontrollierbarkeit und Dynamik der Szene resultiert. Die Blatter des Baumes sind einfacheFormen, welche die Grundbausteine der Szene darstellen, weshalb sie als Primitive bezeichnet werden.

Beispiel: Hierarchisch gestaffelte Transformationen

4

Chapter 2

Direkte Darstellungsschemata

2.1 Zerlegung in Zellen

Einen einfachen Ansatz zur Erfassung von Objekten, verfolgt das Normzellen-Aufzahlungs-Schema.Dabei wird der Raum in ein regelmaßiges Raster aufgeteilt, sodass eine (moglicherweise skalierte) regulareParkettierung des Raumes entsteht. Die gleichgeformten Zellen dieses Raumgitters nennt man Voxel,was eine Kurzwort fur volumetric pixel ist. Im einfachsten Fall, wird der Raum in Quader (vorzugsweiseWurfel) aufgeteilt, was eine besonders einfache Behandlung der Voxel erlaubt. Die Exaktheit der Mod-ellierung durch das Normzellen-Aufzahlungs-Schema ist direkt proportional zur Auflosung des Rasters;das heißt, je kleiner man die Zellengroße wahlt, desto genauer und umfangreicher kann man geometrischeObjekte beschreiben.

Durch Voxel modellierter Torus: links: 4 Voxel pro LE, rechts 16 Voxel pro LE

Einem jeden Voxel werden diverse Attribute zugeschrieben, welche dazu dienen sollen, die Eigen-schaften des von ihm umfassten Raumabschnittes zu beschreiben; das konnen Angaben wie Dichte, Masse,Material-Zusammensetzung, Farbe, Transparenz und ahnliches sein. Gut geeignet ist das Schema daherfur pyhsikalische Messungen und Simulationen, wahrend es fur Echtzeit-Computergrafik eher schwerfalligist - haufigste Anwendung ist die Modellierung von Terrains. Das hangt zum einen damit zusammen, dassder Speicherbedarf mit steigender Auflosung exponentiell wachst, womit auch die Verarbeitungszeit indie Hohe schießt, aber auch zum anderen damit, dass sich die Visualisierung einer durch Normzellenbeschriebenen Szene etwas schwieriger gestaltet. Dennoch ist das Voxel-Modell ein sehr machtigesBeschreibungs-Konzept.

5

links: Durch Voxel modellierter Berg, rechts: Screenshot aus dem auf einer Voxel-Engine basierendenSpiel ”Delta-Force”

Um den Nachteil des erhohten Speicherbedarfs und Rechenaufwands ein wenig zu reduzieren, verzichtetman meist auf gleiche Große der Zellen und verwendet statt dessen eine baumartige Datenstruktur fur sie.So werden Bereiche gleicher Beschaffenheit, die man sonst mit vielen einzelnen Voxeln modellieren musste,zusammengefasst und als einzelnens Voxel behandelt. Dazu wird zunachst ein ausreichend großer Bere-ich mit der Form eines Voxels gewahlt, welcher das zu beschreibende Objekt vollstandig enthalt. DieserBereich wird nun in kleinere Bereiche ahnlicher Form zerlegt. In den entstanden Zellen wird das gleichegetan, aber es wird nur dann unterteilt, wenn die betreffenden Wurfel in Kontakt mit dem Rand des zubeschreibenden Objektes liegt. Vollkommen innerhalb und vollkommen außerhalb liegende Zellen werdennicht weiter zerlegt. Je nach Dimension entsteht so ein Baum mit einer bestimmten Anzahl an Nachfol-gern an jedem Knoten. In der Ebene spricht man dann von einem quadtree und im Raum von einemoctree.

Veranschaulichung eines durch einen quadtree modellierten Bildes der Mandelbrotmenge

6

2.2 Konstruktive Festkorpergeometrie

lasst sich die Realitatsnahe dieses Modells schrittweise erhoehen, was ein entscheidenter Vorteil der Kan-tenmodelle ist. Besonders fur die Visualisierung mittels Bildsynthese ist die konstruktive Festkorpergeometrie(constructive solid geometry, kurz: CSG) interessant. Dabei werden Objekte durch regularisierte Mengen-Operationen kombiniert sowie durch affine Abbildungen transformiert und so zu immer komplexere Ob-jekten verbunden. CSG ist einerseits sehr nah an der mathematischen Beschreibung, aber andererseitseine recht intuitive Technik, denn haufig beschreibt der Mensch die Objekte seiner Umwelt auf ahnlicheWeise.

Einsatz von regularisierten Mengen-Operationen

Direkt nutzbar ist diese Modellierungs-Technik fur die Bildsynthese, wahrend sich die Visualisierungmittels Polygonen eher problematisch gestaltet. Meist wird dann auf die sogenannte boundary repre-sentation zuruck gegriffen (siehe nachster Abschnitt).

7

Chapter 3

Indirekte Darstellungsschemata

3.1 Drahtgitter- und Oberflachen-Modelle

Das grundlegende Prinzip der Kantenmodelle ist, die Form eines Korpers abstrakt als Menge von Punk-ten sowie Kanten und Flachen aus diesen zu behandeln. Aufgrund dieser sehr vereinfachten Sichtweise,ist eine schnellere Berechnung moglich, da man prinzipiell lediglich die Szenen-Punkte korrekt projizierenund daraus die Bild-Punkte ermitteln muss. Im einfachsten Fall werden nur die Punkte gespeichert unduber welche Kanten diese verbunden sind. Da die schlichte Visualisierung solcher Modelle grob den An-schein eines Gestells aus losem Draht erweckt, bezeichnet man diese Stufe als Drahtgittermodelle. DieEinfachheit dieser Modelle bedingt, dass viele Informationen uber die Objekte unter den Tisch fallen,was einige Probleme mit sich bringt:

Es ist allerhochstens durch die Perspektive zu erahnen, welche Flachen in diesem Bild sich auf derRuckseite des Objekts befinden. Selbst bei Bewegung um das Objekt herum, hat man Schwierigkeitenzu erkennen, was uberhaupt dargestellt werden soll. Das Ausblenden von nicht sichtbaren Kanten (unterder Annahme, dass geschlossene Kanten-Zuge nicht durchsichtige Flachen definieren) ware hier schonhilfreich:

8

Hier werden aber implizit schon Polygone mit einbezogen, allerdings werden immer wieder die sel-ben gebraucht und daher bietet es sich an, diese zu speichern. Geht die Visualisierung darauf ein, soist man auf der Stufe der Oberflachenmodelle (boundary represantations/b-reps) angelangt. DurchEinbeziehen zusatzlicher Informationen uber die Polygone in die Visualisierung, kann man recht schnellbessere Ergebnisse erzielen. Naheliegend ware zum Beispiel, die Helligkeit einer jeden Flache gemaß ihrerAusrichtung relativ zur Position einer Lichtquelle anzupassen, sodass ein einfaches diffuses Beleuchtungs-Modell entsteht:

Auf ahnliche Weise lasst sich das Oberfachenmodell weiter ausbauen, sodass die Realitatsnahe derdargestellten Objekte weiter wachst. Das ist ein entscheidender Vorteil der Kantenmodelle, denn jenach gewunschtem Detaill-Grad, lassen sich bestimmte Effekte bei der Visualisierung schnell aktivierenbeziehungsweise deaktivieren, sodass die Objekte einer Szene nicht unotig exakt dargestellt werden.

Die Organisation der verschiedenen Informationen ueber die Objekte durch geeignete Datenstrukturenist eine Herausforderung fur sich, denn es kann schnell passieren, dass Speicher- und Verwaltungs-Aufwandstark in die Hohe schießen. Dafur wird vorzugsweise ein vef-Graph (vertices, edges, faces) genutzt.

3.2 Triangulation

Das Beschranken auf Dreiecke als Flachen bringt viele Vorteile mit sich. So ist beispielsweise immergewahrleistet, dass die Eckpunkte in nur einer Ebene liegen, was fur die Darstellung eine wichtige Rolle

9

spielt. Dreiecke sind in jedem Fall konvex und Großen wie Winkel, Umkreismittelpunkt, Schwerpunkt,etc. lassen sich besonders leicht berechnen. Die Machtigkeit des Modells bleibt die gleiche, da sich jedesPolygon in Dreiecke zerlegen lasst. Diese und noch eine Reihe anderer Vorteile haben viele Hersteller vonGrafik-Karten veranlasst, ihre Gerate auf die Verarbeitung von Dreiecken zu spezialiseren.Hat man eine Punktmenge gegeben, welche eine bestimmte Oberflachenform beschreibt, so mochte mannicht jedes Polygon einzeln definieren, sondern hatte gerne ein Verfahren, welches selbststandig eingeeignetes Netz entsprechend ein paar weniger Rahmengroßen generiert, welche die jeweiligen Anforderun-gen an die Vermaschung wiederspiegeln. Aus genannten Grunden sind Dreiecke die favorisierten Polygoneund ein Vermaschungs-Verfahren zum Generieren eines Dreiecksnetzes aus einer gegegeben Punktmenge(und auch aus einer gegebenen Polygonmenge) wird Triangulation (oder auch Triangulierung) genannt.Prinzipiell konnte man jede Funktion des Typs P(I) → P(I3), welche aus einer Individuen-Menge Ieine Menge von Tripeln uber dieser erzeugt, als Triangulation bezeichnen, aber meist werden bestimmteAnforderungen an das Ergebnis gestellt, sodass nur einige wenige solcher Funktionen von Interesse sind.Zwei haben sich besonders etabliert: Die Delaunay- und die Minimum-Weight-Triangulation. Verfahrenzur Generierung von Vierecks-Netzen werden pavings genannt, kommen aber weitaus weniger zum Ein-satz als Triangulationen.Neben den Verfahren zur Generierung von Dreiecks-Netzes aus Punktmengen, existieren Algorithmenzur Erzeugung aus anderen Polygon-Netzen. Verschiedene Klassen von Polygonen lassen sich verschiedenschwer triangulieren. Am einfachsten ist es bei konvexen Polygonen; bei einfachen, aber nicht-konvexenkommt hauptsachlich der Ear-Cutting-Algorithmus zum Einsatz, der die Polygonecken vom Gesamtpoly-gon abtrennt, in welchen keine weiteren Knoten liegen (sogenannte Ohren). Auch einfache Polygone mitLochern lassen sich triangulieren; wirklich schwierig wird es bei nicht-einfachen Polygonen.

3.2.1 Delaunay-Triangulation

Hier wird an jedes Dreieck die Bedingung gestellt, dass sich kein anderer Punkt der gegebenen Punkt-menge innerhalb der kleinsten Umkugel dieses Dreiecks befindet. Das Auffinden der kleinsten Umkugel istziemlich rechenintensiv, weswegen man haufig andere Ansatze verfolgt, als das naive Filtern nach dieserBedingung, die aber das gleiche Dreiecksnetz erzeugen; die schnelleren Algorithmen weisen eine eine loga-rithmische Zeit-Komplexitat auf. Der duale Graph zum Dreiecksnetz einer Delaunay-Triangulation ist dasVoronoi-Diagramm. Die Delaunay-Triangulation erzeugt ein Dreiecksnetz mit minimalen Innenwinkelnder Dreiecke.

3.2.2 Minimal-Gewicht-Triangulation

Die Minimal-Gewicht-Triangulation (Minimum-Weight-Triangulation, kurz: MWT) erzeugt hingegen einDreiecksnetz mit minimaler Kantenlange der Dreiecke. Seit einigen Jahren weiß man, dass das Auffindender MWT aus einer gegebenen Punktmenge NP-hart ist, also in einer hoheren Komplexitatsklasse liegtals das Auffinden der Delaunay-Triangulation. Die MWT ist in manchen Situationen vorteilhafter, wirdaber aufgrund der hoheren Rechenzeit haufig gemieden.

10

Chapter 4

Freiformkurven und -flachen

Haufig ist es von Vorteil, eine bestimmte Form kontinuierlich durch eine Funktion oder ahnliches beschreibenzu konnen und dann je nach gewunschtem Detaill-Grad eine diskrete Annaherung dieser Form aus demkontinuierlichem Modell zu erstellen. Noch hilfreicher ist ein Zweiwege-Verfahren, mit welchem manauch aus einer diskreten Beschreibung einer Form eine kontinuierliche ermittlen kann, um eine fehler-freie Reproduzierbarkeit dieser Formen gewahrleisten zu konnen. Dafur unterscheidet man zwei Ansatze:Interpolation und Approximation.

4.1 Interpolations-Techniken

Das Ziel besteht darin, aus einer gegebenen Untermenge U = ((u0, v0), (u1, v1), . . . , (un, vn)) eines Vek-torraumes V eine Funktion zu finden, deren Graph alle Elemente U enthalt.

4.1.1 Polynominterpolation

Hier soll die interpolierende Funktion eine Polynom-Funktion sein, hat also die Form p : R → R, x 7→∑mk=0

(akx

k), wobei m der Grad des Polynoms ist. Die Interpolation-Bedingung erzeugt damit das fol-

gende lineare Gleichungs-System:

u0

0 u10 . . . um

0

u01 u1

1 . . . um1

......

. . ....

u0n u1

n . . . umn

·a0

a1

...am

=

v0v1...vn

Sofern (∀i, j ∈ 0, 1, . . . , n) ((ui = uj)→ (i = j)) gilt, also keine zwei ersten Komponenten der Ele-mente von U gleich sind, aber verschiedene Indizes haben, ist das Gleichungssystem eindeutig losbar,wenn n = m gilt.

Die Lagrange-Basis und die Newton’sche Polynomform erlauben effizienteres Finden einer Losung alsuber das Gleichungs-System.Zwar bieten Polynome eine einfache Variante zur Interpolation einer Punktmenge, aber sehr vorteilhaftsind sie nicht gerade. Mit steigendem Grad ist eine zunehmende Oszillation des Funktionsgraphen zuverzeichnen, was so viel heißt, wie dass er viele unerwunschte Auspragungen auweist.

11

4.1.2 Splines

Funktionen, welche sich stuckweise aus Polynomen zusammensetzen, werden als Splines bezeichnet. Auf-grund der Vielzahl an variablen Parametern, ergeben sich auch viele verschiedene Klassen von Splines.Gegeben sei zunachst eine Folge von Punkten ((u1, v1), (u2, v2), . . . , (un, vn)) mit der Bedingung u1 <u2 < . . . < un. Wenn sk(x) =

∑mk

i=0

(ak,ix

i)

das k-te Segment-Polynom des Splines S bezeichnet; danngilt:

S(x) =

(nicht definiert) x < u1

s1(x) u1 ≤ x ≤ u2

s2(x) u2 ≤ x ≤ u3

......

sn−1(x) un−1 ≤ x ≤ un

(nicht definiert) x > un

Nun lassen sich je nach Bedarf verschiedene Anforderung an den Spline stellen. Grundvoraussetzungist, dass der Graph der Spline-Funktion stetig ist und alle gegebenen Stutzpunkte enthalt (also inter-poliert); in der Regel mochte man auch, dass er differenzierbar ist, also keine Knicke aufweist und gutware noch, wenn sich die Krummung nicht sprungartig andert. Formal lauten diese Anforderungen wiefolgt:

(∀k ∈ 1, 2, . . . , n− 1) ((sk(uk) = vk) ∧ (sk(uk+1 = vk+1))

(∀k ∈ 1, 2, . . . , n− 2)((s′k(uk) = s′k+1(uk)

)∧(s′′k(uk) = s′′k+1(uk)

))Solche Bedingungen verlangen allerdings, dass der Grad der Segment-Polynome ausreichend groß ist;

fur die genannten Anforderungen benotigt man mindestens kubische Polynome. Wenn also mk = 3fur beliebige k aus 1, 2, . . . n − 1 gilt, so wurden die genannten Bedingungen genau 4n − 6 lineareGleichungen ergeben. Zur eindeutigen Losbarkeit des Systems werden aber 4n−4 benotigt; daher werdenoft zwei weitere Bedingungen formuliert. Beim naturlichen kubischen Spline beispielsweise gilt s′′1(u1) =s′′n−1(un) = 0 und beim periodischen kubischen Spline

(s′1(u1) = s′n−1(un)

)∧(s′′1(u1) = s′′n−1(un)

)Generell lassen sich verschiedenste Spline-Typen aufstellen, hauptsachlich aber kommen kubische Basis-Splines zum Einsatz. Dabei handelt es sich um kubische Splines, welche als Linear-Kombination vonbestimmten Splines dargestellt werden, die eine Basis des Vektorraums bilden und dafur sorgen, dassdie Spline-Funktion drei mal stetig differenzierbar ist. Voraussetzung dafur ist, dass je zwei benachbarteStutzstellen den gleichen Abstand h voneinander haben - man sagt, die Stutzstellen mussen aquidistantsein. Das Gleichungs-System wird aber stark vereinfacht.

12

ψ(x) =16

x3 + 6x2 + 12x+ 8 −2 ≤ x ≤ −1−3x3 − 6x2 + 4 −1 ≤ x ≤ 03x3 − 6x2 + 4 0 ≤ x ≤ 1−x3 + 6x2 − 12x+ 8 1 ≤ x ≤ 20 sonst

ϕk(x) = ψ

(x− uk

h

)S(x) =

n∑k=−1

(akϕk(x))

Die Aufgabe besteht also lediglich noch darin, die Koeffizienten ak der Basis-Polynome ϕk zu finden.

Die Vorteile von Splines gegenuber Polynominterpolation sind hohere Kontrollierbarkeit und Lokalitat,was heißt, dass sich Anderungen an einzelnen Kontrollpunkten direkter auswirken, aber keine umliegendenSegmente beeinflussen; außerdem oszillieren sie nicht. Allerdings ist der Verwaltungsaufwand, bedingtdurch meherere Fallunterscheidungen, hoher und sofern man keine Basis-Splines verwendet, wird auchmehr Speicher in Beschlag genommen.

4.2 Approximations-Techniken

Ist es nicht notig eine Funktion zu finden, welche alle gegeben Stutzpunkte enthalt, so kann man stattInterpolation auch auf Approximation zuruckgreifen. Wiederum gibt es eine Moglichkeit, dies direkt mitPolynomen zu realisieren: Die orthogonale Projektion eines Interpolations-Polynoms in einen Raumvon Polynomen geringeren Grades als fur die Interpolation erforderlich (Methode der kleinsten Quadrate).

Polynom 5. Grades (grun), welches die roten Punkte interpoliert und dessen orthogonale Projektion inden Raum der Polynome 3. Grades (blau)

Zufriedenstellend ist diese Variante aber in den seltensten Fallen, da einerseits die Nachteile derdirekten Nutzung von Polynomen nicht verschwinden und andererseits weil sie in der Praxis schlicht zuschlechte Ergebnisse erzielt.

13

4.2.1 Bezier-Kurven

Grundsatzlich anders verlauft die parametrische Beschreibung einer Form; ein bekannter Vetreter dieserTechnik ist die Bezier-Kurve. Zu deren Beschreibung ist zunachst die Definition des k. Bernstein-polynoms n. Grades notig:

Bn,k(t) =(n

k

)(1− t)n−k

tk

Bernstein-Polynome weisen eine Reihe vorteilhafter Eigenschaften auf, zum Beispiel folgt aus dembinomischen Lehrsatz, dass die Summe aller k-ten Bernstein-Polynome n-ten Grades stets 1 ist:

n∑k=0

(Bn,k(t)) =n∑

k=0

((n

k

)(1− t)n−k

tk)

= ((1− t) + t)n = 1n = 1

Die Bernstein-Polynome 5. Grades

Es sei nun V ein beliebiger R-Vektorraum. Die Bezier-Kurve wird durch die folgende Funktionbeschrieben:

C : Vn+1 × [0, 1]→ V

((x0, x1, . . . , xn) , t) 7→n∑

k=0

(Bn,k(t) · xk)

Mit dem DeCasteljau-Algorithmus lasst sich diese Funktion durch eine numerisch stabile Rekur-sion effizienter berechnen:

14

C ((x0, x1, . . . , xn) , t) =

x0 n = 0C (((1− t)x0 + tx1, (1− t)x1 + tx2, . . . , (1− t)xn−1 + txn) , t) n > 0

Bezier-Kurven haben die Eigenschaft der affinen Invarianz, was heißt, dass die Transformationeiner Bezier-Kurve gemaß einer affinen Abbildung gleich der Bezier-Kurve uber den transformiertenStutzpunkten ist. Beweis dafur: Es sei f : Vn+1 → Vn+1, x 7→ Ax + b eine affine Abbildung (A ∈R(n+1)×(n+1), b ∈ Vn+1):

C (AX + b, t)=C (Ax0 + b, Ax1 + b, . . . , Axn + b , t)

=n∑

k=0

(Bn,k(t) · (Axk + b))

=n∑

k=0

(Bn,k(t) ·Axk +Bn,k(t) · b)

=n∑

k=0

(Bn,k(t) ·Axk) +n∑

k=0

(Bn,k(t) · b)

=A ·n∑

k=0

(Bn,k(t) · xk) +n∑

k=0

(Bn,k(t)) · b

=A · C(X, t) + b

Fur die 3D-Modellierung sind hauptsachlich die Falle V = R2 und V = R3 interessant. Dannbeschreibt die Bezier-Kurve eine gekrummte Linie in der Ebene beziehungsweise im Raum.

Man kann allerdings auch komplexere Vektorraume betrachten, wie zum Beispiel den Raum allern2 + 1-Tupel von Bezier-Kurven uber n1 + 1 Stutzpunkten. Das scheint zunachst nicht allzu sinnvoll zusein, resultiert aber in der Verallgemeinerung der Bezier-Kurven auf hohere Dimensionen. So erhalt manunter anderem eine weitere wichtige Freiform: Die Bezier-Flache.

X(t2) =

(n2∑

k2=0

(Bn2,k2(t2) · x0,k2) ,n2∑

k2=0

(Bn2,k2(t2) · x1,k2) , . . . ,n2∑

k2=0

(Bn2,k2(t2) · xn1,k2)

)

C(X(t2), t1) =n1∑

k1=0

(Bn1,k1(t1) ·

n2∑k2=0

(Bn2,k2(t2) · xk1,k2)

)=

n1∑k1=0

(n2∑

k2=0

(Bn1,k1(t1) ·Bn2,k2(t2) · xk1,k2)

)

15

Kontrollnetz Punkte auf Flache ermitteln

Triangulation fertige Freiformflache

Tatsachlich ist die Theorie der Bezier-Kurven um einiges und umfangreicher und allgemeiner gehalten,als der hier vorgestellte Aspekt. So ware zum Beispiel ein anderer Spezialfall, die Approximation einesdurch Dreiecke beschriebenen Netzes.

4.2.2 Nicht-uniforme rationale B-Splines

Eine Verallgemeinerung von sowohl Splines, als auch Bezier-Kurven, sind die sogenannten Nicht-uniformenrationalen B-Splines (kurz: NURBS). Ein wichtiger Unterschied zu beiden Techniken ist, dass manPunkten eine Gewichtung zuschreiben, sodass die Kurve starker von diesen beeinflusst wird. Damitstellen sie ein Modellierungs-Spektrum von glatt gekrummten bis hin zu eckigen und kantigen Kur-ven/Flachen bereit. Dieses und eine Reihe anderer Moglichkeiten machen NURBS zu einer Art ”eier-legenden Wollmilchsau”, da sich quasi jede beliebige Kurve/Flache durch sie beschreiben lasst. Sie weisendie positiven Eigenschaften von simplen Splines und Bezier-Kurven auf und sind zusatzlich invariant unterprojektiven Transformationen.

Es sei ((x1, w1), (x2, w2), . . . , (xm, wm)) ∈ (V× R)m - eine Menge von Kontrollpunkten zusammenmit ihren Gewichtung - gegeben. Zum Kontrollieren der Kurve steht neben der Gewichtung noch dieAnpassung des Knoten-Tupels u zur Verfugung. Die Werte dessen fließen in die Definition der NURBS-Basis-Funktionen ein:

16

fn,k(t) :=t− uk

un+k − ukgn,k(t) :=

un+k − tun+k − uk

Nn,k(t) = fn,k(t)Nn−1,k(t) + gn−1,k+1(t)Nn−k,k+1(t)

Die NURBS-Kurve wird dann folgendermaßen berechnet:

C(t) =m∑

k=1

(Nn,k(t)wk∑m

j=1 (Nn,j(t)wj)· xk

)

17

Chapter 5

Sonstige Modellierungstechniken

5.1 Lindenmayer- und iterierte Funktionen-Systeme

Ein Lindenmayer-System (kurz: L-System) ist ein abstrakter Formalismus im Sinne einer Grammatik,wie sie Gegenstand der theoretischen Informatik ist. Der prinzipielle Aufbau ist der selbe:

L = (V,Σ, P, S)V ∩ Σ = ∅P ⊆ (V ∪ Σ)+ × (V ∪ Σ)∗

S ∈ V

Der Unterschied zur gewohnlichen Grammatik besteht nun in der Interpretation der Produktionenaus P und zwar wird eine Regel stets auf alle Vorkommen der Pramisse im aktuellen Wort angewendetund nicht nur auf ein einzelnes.

LKochkurve = (S, l, r, v, (S, SlSrrSlS), (S, v) , S)S

` SlSrrSlS` SlSrrSlSlSlSrrSlSrrSlSrrSlSlSlSrrSlS` vlvrrvlvlvlvrrvlvrrvlvrrvlvlvlvrrvlv

Ein iteriertes Funktionen-System (kurz: IFS) arbeitet nach einem vergleichbaren Schema, ist aberetwas flexibler zu handhaben, als schlichte L-Systeme. Beide eignen sich recht gut, um allerlei fraktaleObjekte zu erzeugen, da durch die besondere Anwendung der Produktionen und Funktionen gewahrleistetwird, dass stets ein selbstahnliches und quasi skaleninvariantes Wort entsteht. Diese etwas exotisch an-mutende Technik findet Anwendung zur Modellierung von Pflanzen, Kristallen und anderen Strukturen,deren Aufbau sich fraktal-ahnlich verhalt.

18

links: Ein durch ein L-System modellierter Baum, rechts: Der von Barnsley vorgestellte Farn, welcherdurch ein IFS beschrieben wird

5.2 Partikelsysteme

Obwohl das Partikelsystem vor nicht allzu langer Zeit noch als Exot unter den Modellierungstechnikengalt, ist es heute eine der bedeutendsten Techniken uberhaupt. Prinzipiell modelliert man durch einPartikelsystem nicht zusammenhangende, dynamische Objekt-Aggregationen. Die Grundbausteine dazubilden die Partikel, in welchen man Position, Geschwindigkeit, Richtung, Farbe, Transparenz, Große,Alter, Rotation und ahnliche Eigenschaften erfasst. Damit lassen sich Dinge wie Granulate, Flussigkeiten,Dampfe, Flammen und vergleichbare naturliche Phanomene gut simulieren, welche keine klar abgegrenzteOberflache besitzen. Aufgrund der Moglichkeit, das Verhalten eines jeden Partikels individuell festzule-gen, zeichnen sich Partikelsysteme durch eine sehr hohe Dynamik aus, wodurch auch eine Vielzahl vonAnimations-Effekten wie Explosionen oder Stromungen darstellbar werden. So fullen die Partikelsys-teme eine wichtige Lucke in der Modellierungs-Theorie, denn bei allen genannten Beispielen erweisen sichVoxel- oder Kantenmodelle als unbrauchbar. Der Fortschritt der Technik der letzten Jahrzehnte hat denEinsatz von Partikelsystemen uberhaupt erst ermoglicht.

links: verschiedene Darstellungen von Flammen/Plasma durch ein Partikel-System, rechts: Screenshotaus einer durch ein Partikel-Plugin modifizierten Version des Spiels ”The Elder Scrolls III -

Morrowind”

19

Chapter 6

Abschluss

6.1 Zusammenfassung

Je nach Zielsetzung und zur Verfugung stehenden Ressourcen ist eine andere Modellierungs-Technikvorteilhafter und in der Praxis kombiniert man haufig verschiedene Techniken und kommt so zu Hybrid-verfahren; ebenso ist es auch moglich sich auf eine Technik zu spezialiseren, welche beispielsweise fureine bestimmte Visualierungsmethode besonder geeignet ist. So ist die gute Modellierung einer SzeneGrundlage fur effektives Aufsgestalten und Interagieren in dieser.

6.2 Verwendete Software

Textsatzsystem LATEX

Persistance of Vision Raytracer

Java

6.3 Quellen

• Bungartz, Hans-Joachim (et al.): Einfuhrung in die Computergraphik, Braunschweig (vieweg) 20022.

• Klawonn, Frank: Grundkurs Computergrafik mit Java. Die Grundlagen verstehen und einfachumsetzen mit Java3D, Wiesbaden (vieweg) 2005.

• Skript ”Prof. Dr. S. Gumhold, Computergraphik I, WS 08/09”

• http://en.wikipedia.org/wiki/Nonuniform rational B-spline.html

• http://www.osnews.com/img/10607/Voxel world.jpg

• http://www.fraktalwelt.de/myhome/images/farn.gif

20

• http://upload.wikimedia.org/wikipedia/commons/4/41/Fractal tree %28Plate b - 2%29.jpg

• http://acidmonk.ac.funpic.de/modbilder/partikel waffen.jpg

• http://unigine.com/products/unigine v0.33/particles.jpg

21