Boolsche Operationen fur triangulierte K orp ergermer/publications/studienarbeit.pdf · Constructive Solid Geometry (CSG) ist eine Technik der Computergraphik, die komplexe Objekte

Otto-von-Guericke-UniversitätMagdeburgFakultät für InformatikInstitut für Simulation und Graphik

Boolsche Operationenfür triangulierte Körper

Studienarbeit

Verfasser:

Tobias Germer

16. Juni 2003

Betreuer:

Henry König (Universität Magdeburg)Axel Hintze (Fraunhofer IFF)

Universität Magdeburg

Fakultät für Informatik

Postfach 4120, D–39016 Magdeburg

Germany

Germer, Tobias:

Boolsche Operationen für triangulierte KörperStudienarbeit, Otto-von-Guericke-Universität Magdeburg, 2003.

i

Vorwort

Die vorliegende Arbeit entstand im Rahmen eines Praktikums am FraunhoferInstitut für Fabrikbetrieb und Fabrikautomatisierung Magdeburg. Sie wurdeals Erweiterung zu einem Programm für das virtuelle Training entwickelt.Ziel war es, eine Grundlage für

”Ingenieur-typische“ Tätigkeiten im virtuellen

Raum zu schaffen.

Selbständigkeitserklärung

Hiermit erkläre ich, daß ich diese Studienarbeit selbständig angefertigt habe.

Magdeburg, den 16. Juni 2003

Tobias Germer

iii

Inhaltsverzeichnis

Abbildungsverzeichnis x

Tabellenverzeichnis xi

1 Einleitung 1

1.1 Motivation und Problemstellung . . . . . . . . . . . . . . . . . 1

1.2 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Gliederung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Grundlagen 5

2.1 Thematik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Regularisierte boolsche Operationen . . . . . . . . . . . 5

2.1.2 Anforderungen . . . . . . . . . . . . . . . . . . . . . . 7

2.1.3 Abgrenzung . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.4 Einschränkungen . . . . . . . . . . . . . . . . . . . . . 9

2.2 Thematisches Umfeld . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1 Constructive Solid Geometry . . . . . . . . . . . . . . . 11

2.2.2 Binary Space Partitioning . . . . . . . . . . . . . . . . 12

2.2.3 Die Stencil-Buffer Methode . . . . . . . . . . . . . . . 14

2.2.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . 15

2.3 Berechnung von Dreiecksnetzen . . . . . . . . . . . . . . . . . 16

2.3.1 Teilung der Oberfläche . . . . . . . . . . . . . . . . . . 17

v

vi INHALTSVERZEICHNIS

2.3.2 Spezialfälle . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.3 Klassifizierung der Oberfläche . . . . . . . . . . . . . . 20

2.3.4 Dreiecksnetze . . . . . . . . . . . . . . . . . . . . . . . 21


3 Entwurf 25

3.1 Berechnung der Schnittlinie . . . . . . . . . . . . . . . . . . . 25

3.1.1 Koordinatensysteme . . . . . . . . . . . . . . . . . . . 25

3.1.2 Dreieck-Dreieck Überschneidung . . . . . . . . . . . . . 26

3.2 Zusammenfassen planarer Dreiecke . . . . . . . . . . . . . . . 29

3.2.1 Besonderheiten von triangulierten Körpern . . . . . . . 29

3.2.2 Bildung von Facetten . . . . . . . . . . . . . . . . . . . 32

3.2.3 Spezialfälle . . . . . . . . . . . . . . . . . . . . . . . . 34

3.2.4 Beseitigung der inneren Merkmale . . . . . . . . . . . . 36


3.3 Triangulierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.3.1 Delaunay Triangulierung . . . . . . . . . . . . . . . . . 38

3.3.2 Algorithmen zur Triangulierung . . . . . . . . . . . . . 39

3.3.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.4 Triangulierung von Facetten . . . . . . . . . . . . . . . 47

3.3.5 Kollineare Randpunkte . . . . . . . . . . . . . . . . . . 49

3.4 Ausführung der boolschen Operation . . . . . . . . . . . . . . 50

3.4.1 Klassifizierung . . . . . . . . . . . . . . . . . . . . . . . 50

3.4.2 Konstruktion des Ergebniskörpers . . . . . . . . . . . . 52

4 Implementierung 55

4.1 Technische Umsetzung . . . . . . . . . . . . . . . . . . . . . . 55

4.1.1 Kontext . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1.2 Werkzeuge . . . . . . . . . . . . . . . . . . . . . . . . . 57

INHALTSVERZEICHNIS vii

4.2 Umsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2.1 Datenstrukturen . . . . . . . . . . . . . . . . . . . . . 57

4.2.2 Besonderheiten . . . . . . . . . . . . . . . . . . . . . . 58

4.3 Kollisionserkennung . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3.1 VCollide . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3.2 Erweiterungen . . . . . . . . . . . . . . . . . . . . . . . 60

4.3.3 Temporale Aspekte . . . . . . . . . . . . . . . . . . . . 61

5 Zusammenfassung 63

5.1 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Literaturverzeichnis 67

viii INHALTSVERZEICHNIS

Abbildungsverzeichnis

1.1 Boolsche Operationen zwischen Kugel und Quader . . . . . . . 2

1.2 Boolsche Operationen in einer interaktiven Testumgebung . . 3

2.1 Schritte bei regularisierten boolschen Operationen . . . . . . . 6

2.2 Beispiele zur Zwei–Mannigfaltigkeit . . . . . . . . . . . . . . . 9

2.3 Raytracing von CSG–Modellen . . . . . . . . . . . . . . . . . 11

2.4 Körperdefinition durch BSP-Bäume . . . . . . . . . . . . . . . 13

2.5 Zusammensetzen der Oberfläche aus den inneren und äußeren

Körperteilen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.6 Teilung der Oberfläche anhand der Schnittlinie . . . . . . . . . 18

2.7 Behandlung von koplanaren Oberflächen . . . . . . . . . . . . 19

2.8 Klassifizierung durch Raytracing . . . . . . . . . . . . . . . . . 20

2.9 Skizzierung des Algorithmus . . . . . . . . . . . . . . . . . . . 23

3.1 Berechnung von Schnittsegmenten . . . . . . . . . . . . . . . . 28

3.2 Möglichkeiten der Triangulierung . . . . . . . . . . . . . . . . 30

3.3 Schritte bei der Erzeugung von Facetten . . . . . . . . . . . . 33

3.4 Erzeugung von Löchern . . . . . . . . . . . . . . . . . . . . . . 34

3.5 Löschen eines Linienzuges . . . . . . . . . . . . . . . . . . . . 35

3.6 Löschen von inneren Punkten . . . . . . . . . . . . . . . . . . 36

3.7 Kollineare Segmente, die nicht vereinigt werden können . . . . 37

3.8 Qualität von Triangulierungen . . . . . . . . . . . . . . . . . . 38

ix

x ABBILDUNGSVERZEICHNIS

3.9 Beispiele zum Delaunay-Kriterium . . . . . . . . . . . . . . . . 39

3.10 Schrittweises Einfügen nach Lawson . . . . . . . . . . . . . . 40

3.11 Dualität von Voronoi-Diagramm und Delaunay-Triangulierung 42

3.12 Definition der Beachline . . . . . . . . . . . . . . . . . . . . . 43

3.13 Fortschreiten der Sweep-Line . . . . . . . . . . . . . . . . . . . 43

3.14 Einfügen von Constraints . . . . . . . . . . . . . . . . . . . . . 45

3.15 Einfügen von Constraints in mehreren Durchläufen . . . . . . 46

3.16 Triangulierung einer Facette . . . . . . . . . . . . . . . . . . . 47

3.17 Behandlung kollinearer Begrenzungskanten . . . . . . . . . . . 49

3.18 Klassifizierung an den Schnittkanten . . . . . . . . . . . . . . 51

3.19 Propagierung der Klassifikation . . . . . . . . . . . . . . . . . 51

3.20 Normalen und koplanare Flächen . . . . . . . . . . . . . . . . 53

4.1 Kontext der libSO . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2 Kollisionserkennung und kleine Objekte . . . . . . . . . . . . . 61

5.1 Konstruktion mit soliden Körpern im Hugo . . . . . . . . . . . 64

5.2 Teilung von Objekten im Hugo . . . . . . . . . . . . . . . . . 65

Tabellenverzeichnis

2.1 Eignung verwandter Algorithmen bezüglich der Anforderungen 16

3.1 Klassifizierung nach Lage und Operation . . . . . . . . . . . . 52

xi

xii TABELLENVERZEICHNIS

Kapitel 1

Einleitung

1.1 Motivation und Problemstellung

Constructive Solid Geometry (CSG) ist eine Technik der Computergraphik,die komplexe Objekte durch Kombination einfacher Körper erzeugen kann.Es handelt sich um eine Modellierungstechnik, bei der man von solidenKörpern ausgeht. Diese Körper können addiert, subtrahiert oder geschnit-ten werden. Dabei entsteht erneut ein solider Körper, der mit einem anderenKörper kombiniert werden kann. Durch diese Methode wird ein binärer Baumerzeugt, der die Entstehung des fertigen Körpers dokumentiert. Bei der Be-wertung1 des CSG-Modells wird der Baum traversiert und das Resultat dereinzelnen boolschen Operationen rekonstruiert.

Betrachtet man Constructive Solid Geometry im klassischen Sinne, sosind als Grundprimitive nur wenige geometrische Körper zugelassen. Dazugehören zum Beispiel Quader, Kugel, Zylinder und Kegel. Das Paradigmavon CSG ist gerade die Erzeugung von komplexen Objekten aus einfachen,soliden Körpern. Der Kern von CSG ist die Verwendung von boolschen Men-genoperationen, die auf den Volumina der Operanden arbeiten.

Mit CSG lassen sich schnell komplexe Objekte und speziell industriellgefertigte Körper modellieren. Für den Autor ist es intuitiv, einen Zylindervon einem Quader

”abzuziehen“, um z.B. ein Bohrloch zu erzeugen. So kann

eine Vielzahl realer Formen modelliert werden.

Obwohl die Klasse der mit CSG realisierbaren Objekte sehr groß ist,entstehen durch die geringe Anzahl der Primitiven auch Einschränkungen.Oft will der Modellierer bestehende Körper weiterverwenden. Dabei liegendie Daten in modernen Systemen meist als Dreiecksnetze vor. Solche Modellekönnen ohne weiteres nicht in bestehenden CSG-Systemen verwendet werden.

Ein weiteres Problem liegt in der Einsicht, daß es Objekte gibt, die miteinfachen Grundkörpern nicht oder sehr schwer modelliert werden können.

1z.B. die Erzeugung eines Bildes (rendern)

1

2 KAPITEL 1. EINLEITUNG

(C) Vereinigung(A) Differenz (B) Durchschnitt

Abbildung 1.1: Boolsche Operationen zwischen Kugel und Quader

Als Beispiel lassen sich Freiformflächen nennen. Obwohl eine Approximationmeist ausreichend ist, wäre diese mit einem CSG-Baum sehr aufwändig undineffizient.

In dieser Arbeit werden Methoden und Werkzeuge entwickelt, mit de-nen es möglich ist, dreidimensionale, triangulierte Objekte mit boolschenOperationen zu verarbeiten. Es werden Algorithmen vorgestellt, mit denenVereinigung, Differenz und Schnitt solcher Körper möglich sind. Diese Ope-rationen können neben einer Erweiterung von CSG-Systemen als Grundlagefür eine Reihe weiterer Anwendungen dienen.

1.2 Ergebnisse

Im Rahmen dieser Arbeit wurde eine Bibliothek entwickelt, mit der esmöglich ist, triangulierte solide Körper mit boolschen Operationen zu kom-binieren. Es wird ein neuer triangulierter solider Körper konstruiert, der dasErgebnis einer Vereinigung, Differenz oder Durchschnitt repräsentiert. Dasentstandene Objekt kann als erneute Eingabe für den Algorithmus dienen.

Abbildung 1.1 zeigt die Ergebnisse von boolschen Operationen zwischeneiner Kugel und einem Würfel. Abbildung 1.1 (A) zeigt die Differenz, (B) den

1.3. GLIEDERUNG 3

Abbildung 1.2: Boolsche Operationen in einer interaktiven Testumgebung

Durchschnitt und (C) die Vereinigung. Um die Struktur des Dreiecksnetzeszu verdeutlichen, ist zusätzlich jeweils das Drahtgittermodell dargestellt.

Die Berechnung erfolgt effizient und robust. Bei wiederholter Ausführungdes Algorithmus erfolgt die Berechnung mit einer Geschwindigkeit, die inter-aktive Anwendungen ermöglicht. Es wurde eine Prototyp-Anwendung ent-wickelt, mit der nicht-triviale Körper virtuell und interaktiv miteinanderkombiniert werden können. Abbildung 1.2 zeigt einen Screenshot, in dem derNutzer interaktiv eine Testszene manipuliert hat. Alle dargestellten Körpersind solide. Insbesondere sind die Kugeln oben links vereinigt.

Die Bibliothek und die Algorithmen wurden außerdem so entwurfen, daßsie leicht in bestehende Systeme integriert werden können. Sie wurden in einSystem zum virtuellen Training2 aufgenommen und erweitert dessen Funk-tionalität um boolsche Operationen.

1.3 Gliederung

Nachdem die Motivation kurz angerissen wurde, folgt im nächsten Kapitelein genauere Definition der Aufgabe. Außerdem werden die Grundlagen der

2des Fraunhofer IFF Magdeburg

4 KAPITEL 1. EINLEITUNG

Thematik erarbeitet. Dazu gehört ein Überblick über bestehende Ansätze,die Wahl des vorgestellten Ansatzes und eine Skizzierung der Vorgehensweise.

Kapitel 3 erläutert detailliert die gewählten Methoden. Es folgt dabeider Schrittfolge des Algorithmus und stellt das Vorgehen bei der Teilung derOberfläche, der Triangulierung und der Klassifizierung vor. Besonderheitender Entwicklung werden hervorgehoben und erklärt.

Das 4. Kapitel stellt ausgesuchte Aspekte der Implementierung vor. Esgeht dabei auch auf die Kollisionserkennung als Grundlage ein.

Eine Zusammenfassung der vorgestellten Konzepte und ein Ausblick aufweitere Aufgaben und Anwendungen beschließen die Arbeit mit Kapitel 5.

Kapitel 2

Grundlagen

Dieses Kapitel befaßt sich mit der theoretischen Vorbetrachtung der gewähl-ten Methoden. Zunächst wird die Thematik dieser Arbeit definiert. Danachwerden die Anforderungen erläutert, die sich an die zu entwickelnden Me-thoden stellen und Abgrenzungen sowie Einschränkungen genannt, die dieAufgabe eingrenzen. Um einen Überblick des Themengebietes und Einblickin weitere Hintergründe zu erlangen, beleuchtet Abschnitt 2.2 das themati-sche Umfeld. Schließlich wird der Algorithmus skizziert, der als Grundlagefür diese Arbeit dient.

Viele der folgenden Konzepte werden durch Abbildungen illustriert. Diemeisten davon sind zweidimensionale Schemata mit Punkten und Linien.Da die boolschen Operationen im dreidimensionalen Raum operieren, sinddie betreffenden Darstellungen als Draufsicht der Dreiecke bzw. Polygone zuinterpretieren. Eine Linie repräsentiert dabei ein Dreieck, welches senkrechtzur Bildebene steht.

2.1 Thematik

2.1.1 Regularisierte boolsche Operationen

Diese Arbeit befaßt sich mit der Entwicklung und Implementierung von Ver-fahren für die Berechnung der Schnittmenge (

⋂), Vereinigung (

⋃) und Diffe-

renz (–) auf dreidimensionalen Objektgeometrien. Um die Mengenoperatio-nen in diesem Kontext sinnvoll definieren zu können, werden die behandeltenKörper als

”solide“ angesehen.

In der Computergraphik sind aber durchaus andere Objekte möglich. Daseinfachste Beispiel ist ein einzelnes Dreieck. Dieses beschreibt nichts weiter,als eine begrenzte Fläche oder eine planare Menge von Punkten. Alle Körper,die uns umgeben, beinhalten jedoch ein gewisses Volumen und beschreibeneine Menge von Punkten, die einen (begrenzten) Rauminhalt ausfüllen. Die

5

6 KAPITEL 2. GRUNDLAGEN

(B) Durchschnitt (C) innerePunkte

(D) regularisierterDurchschnitt

(A) Ausgangssituation

Abbildung 2.1: Schritte bei regularisierten boolschen Operationen

Menge solcher Körper ist Objekt der folgenden Betrachtungen.

Die genannten Mengenoperationen werden als Operationen auf den Vo-lumina der Operanden definiert. Die Punktmengen der Volumina werdenvereinigt, voneinander abgezogen, oder es wird der Durchschnitt gebildet. InAnalogie zur Mengenalgebra wird die Gesamtheit der drei betrachteten Ope-rationen im folgenden als boolsche Operationen bezeichnet. In dieser Arbeitbezieht sich der Begriff immer auf die Kombination zweier Objektgeometrien.

Bei der boolschen Operation entsteht erneut ein gültiges Objekt. DerAusdruck

”gültig“ heißt in diesem Zusammenhang, daß das Resultat der

boolschen Operation wieder ein echtes Volumen beschreibt (> 0) und alsEingabe für eine weitere boolsche Operation dienen kann. Aus dieser Forde-rung folgt, daß die zu entwickelnden Operationen abgeschlossen bezüglich derMenge der Ein- und Ausgabeobjekte sein müssen. Das Resultat und die Aus-gangsobjekte müssen sich also gegenüber der boolschen Operation qualitativgleichwertig verhalten. Betrachtet man allerdings die einfachen boolschenOperationen genauer, so fällt auf, daß es

”degenerierte“ Fälle gibt, die die

Abgeschlossenheit der Operation verletzen. Als Beweis dient ein einfachesBeispiel: Gegeben seien zwei Quader, welche sich an einer Seite berühren,aber nicht durchdringen. Die Quader liegen also perfekt aneinander. Bildetman nun die Schnittmenge der Punkte, so ergibt sich eine Fläche, die keinVolumen beschreibt. Mit ähnlichen Fällen können Punkte oder Linien ent-stehen. Abbildung 2.1 (A) zeigt zwei Körper, die sich teilweise durchdringenund teilweise nur berühren. Wenn eine

”normale“ boolsche Operation aus-

geführt wird, so entsteht das Objekt aus Abbildung 2.1 (B). Während es imBereich der Durchdringung ein gültiges Volumen beschreibt, ist der untereTeil degeneriert.

Eine Lösung dieses Problems beschreibt das Kapitel 12.2 von Foley[FvDFH96]. Das bisher entwickelte Konzept der boolschen Operationen wirddurch regularisierte boolsche Operationen ersetzt, symbolisiert durch

⋂*

⋃*

und –*. Bei diesen wird ein Körper in innere und äußere Punkte aufgeteilt.Die äußeren Punkte sind solche, deren Distanz zum Komplement der Körper-

2.1. THEMATIK 7

menge 0 ist. Intuitiv kann man die äußeren Punkte als solche definieren, dieden Rand des Körpers bilden. Die inneren Punkte beschreiben den

”Rest“

des Körpers und damit sein Volumen. Innere Punkte sind nur von Punktenumgeben, die ebenfalls zum Objekt gehören. Die Hülle beschreibt die Vereini-gung aller inneren und äußeren Punkte. Regularisierte boolsche Operationensind nun wie folgt definiert:

A op∗B = closure(interior(A op B)), op ∈ {−,∩,∪} (2.1)

Es wird also die boolsche Operation”normal“ ausgeführt. Danach werden

die inneren Punkte des Ergebnisses extrahiert und von ihnen die Hülle ge-bildet. Das Ergebnis wird daher

”regularisiert“. Bei dem oben beschriebenen

Beispiel der zwei Quader ergibt sich als Ergebnis die leere Menge. Die Mengeder inneren Punkte einer Ebene ist leer. Daher können auch keine Hüllpunktegebildet werden. Im Beispiel von Abbildung 2.1 (C) sind die inneren Punktegrau dargestellt. Zu beachten ist, daß vom unteren Teil keine inneren Punkteexistieren, da alle Punkte dort am Rand liegen. Beim Ergebnis (D) werdenalso nur die oberen Punkte berücksichtigt.

Aufgrund der Abgeschlossenheit wird in den folgenden Betrachtungenvon regularisierten Operationen ausgegangen. Eine detaillierte Diskussionund weiterführende Informationen der Thematik bietet Foley [FvDFH96].

2.1.2 Anforderungen

Die erste und wichtigste Anforderung an die Entwicklung der erforderlichenVerfahren ist die Eignung für die

”Zielapplikation“: Es ist eine Bibliothek zu

entwickeln, die sich in eine bestehende Echtzeit-Applikation integrieren läßt.Daraus ergeben sich eine Reihe von Vorgaben.

In einem Großteil der modernen 3D-Graphik-Applikationen (wie auchin der Zielapplikation) werden Objekte als sogenannte B-Reps1 dargestellt.Dabei beschränkt sich die Beschreibung der Geometrie auf die Repräsentati-on der Oberfläche. Aus Sichtweise der regularisierten boolschen Operationenwerden also nur die äußeren Punkte dargestellt. Zusätzlich besteht die Ober-fläche (in der Zielapplikation) ausschließlich aus Polygonen. Zu den erforderli-chen Koordinaten der Polygonpunkte (im folgenden Vertex genannt) kommtnoch die Beschreibung von Materialeigenschaften, zu denen auch Normalenund Texturkoordinaten zählen.

Der Nutzer interagiert mit der Zielapplikation in Echtzeit. Daher müssendie boolschen Operationen für die gewünschten Anwendungen und Operan-den möglichst schnell berechenbar sein. Ein besonderes Augenmerk bei derEntwicklung von geeigneten Verfahren liegt also auf deren Effizienz. Auf-grund der Interaktivität müssen die Verfahren auch robust sein. Der Nutzer

1Boundary-Representation


hat völlige Freiheit bei der Manipulation der Operanden und erwartet injedem Fall das entsprechende Resultat.

Aus der Interaktivität ergibt sich auch die Forderung nach Robustheit.Die Eingabegeometrie kann sehr komplex sein. Es soll von einer allgemeinenLage der Geometrie ausgegangen werden. Alle Spezialfälle, die auftreten,sollen behandelt werden.

Schließlich sollen die boolschen Operationen auch wiederholt auf einemObjekt ausgeführt werden können. Das Resultat einer Operation soll selbstOperand für eine weitere Operation sein (Abgeschlossenheit). Besonderer Fo-kus liegt hierbei auf der Effizienz. Die Anzahl der Dreiecke darf sich nichtpotenzieren und soll auch bei wiederholter Ausführung so gering wie möglichbleiben.

Zusammenfassend sind also Funktionen zu entwickeln, die boolsche Ope-rationen für (bestehende) polygonale Objekte effizient und robust berechnenund dabei das Resultat einer weiteren Behandlung zur Verfügung stellen.

2.1.3 Abgrenzung

Der Fokus dieser Arbeit begrenzt sich auf die Entwicklung boolscher Opera-tionen als Blackbox: Zwei gültige Operanden dienen als Eingabe, die Ausgabeist ein Objekt als Resultat der gewählten Operation. Dieses erfüllt dieselbenForderungen, wie die Eingabe. Das Themengebiet ist beschränkt sich damitauf die boolschen Operationen im engeren Sinne. Die folgenden Erklärungenumgrenzen den Anspruch dieser Arbeit genauer.

Boolsche Operationen verleihen einer Applikation ein mächtiges Werk-zeug und ermöglichen eine ganze Reihe von Anwendungen. Auf die Möglich-keiten soll jedoch nur ein (exemplarischer) Blick geworfen werden, der keinenAnspruch auf Vollständigkeit erhebt.

Die Kollisionserkennung ist bei der Implementierung zwar eine Grundlageder boolschen Operationen, sie wird aber nur aus Sicht des Anwenders be-schrieben. Eine ausführliche und detaillierte Abhandlung ist nicht Teil dieserArbeit.

Wie bereits in Abschnitt 1.1 angerissen wurde, fällt das Thema derboolschen Operationen in den Kontext der

”Constructive Solid Geometry“

(CSG). Allerdings liegen das Augenmerk und die Hauptanwendung bei CSGauf der Konstruktion komplexer Körper durch einfache Primitive. Dabei wirdein Baum von Operationen aufgebaut, der die hierarchische Ausführung derOperationen beschreibt. Die Blätter dieses Baumes sind einfache Geometrie-Primitive. Jeder innere Knoten repräsentiert das Ergebnis einer Operationder beiden Kinder. Die Wurzel ist das Endergebnis. In dieser Arbeit wirdjedoch von einer Operation ausgegangen, die die Geometrie direkt verändertund auf polygonalen Objekten arbeitet. Obwohl dies für die Implementie-

2.1. THEMATIK 9

(D) richtig

��

��

��

��

��

��

��

��

��

��

��

a

(A) falsch (B) falsch (C) falsch

��

Abbildung 2.2: Beispiele zur Zwei–Mannigfaltigkeit

rung von CSG genutzt werden kann, ermöglicht der vorgestellte Ansatz auchandere Applikationen. Die Traversierung des Baumes und der Kontext vonmehr als zwei Objekten sind nicht Thema dieser Arbeit.

2.1.4 Einschränkungen

Die Anforderung an die Operanden besteht bisher darin, daß sie aus allgemei-nen polygonalen Oberflächenmodellen bestehen. Wie bereits erläutert, liegtein Hauptaugenmerk auf der Effizienz der boolschen Operationen. Durch dieBeschränkung der gültigen Operanden wird eine weitere Vereinfachung derBerechnung und damit eine Steigerung der Effizienz bewirkt.

Zum ersten sollen die Objekte aus Dreiecken bestehen. Dies verein-facht die Datenstrukturen und die Berechnung der Schnittlinien. Die For-derung kann leicht erfüllt werden, indem zunächst alle Polygone in Drei-ecke umgewandelt werden. Die Operanden werden also durch Dreiecksnetzerepräsentiert. Abschnitt 2.3.4 geht näher auf diese Entscheidung ein. DieBeschränkung auf Dreiecke bewirkt jedoch keine Einschränkung der darstell-baren Objekte.

Außerdem besteht die Forderung an die Objekte darin, daß sie solide sind.Das bedeutet, daß die Objekte ein nicht degeneriertes Volumen2 beschreiben.Da die Eingabegeometrie nur aus Dreiecken besteht, ist a priori keine Infor-mation über das Volumen vorhanden. Daher muß diese Eigenschaft nach-gebildet oder gefordert werden. In Zusammenhang mit der Forderung nacheiner Boundary-Repräsentation ergibt dies folgende Einschränkungen.

Die Objekte müssen topologisch geschlossen und streng flächig (zwei–mannigfaltig) sein. Per Definition bedeutet Zwei–Mannigfaltigkeit, daß jedenPunkt auf der Oberfläche eines Körpers in jeder beliebig kleinen Umgebungdieselbe Topologie umgibt, wie eine Kreisscheibe in der Ebene. Bei Dreiecks-netzen wird das dadurch erreicht, daß jede Kante genau zwei Nachbardrei-

2Volumen, welches größer als 0 ist


ecke hat. Würde sie mehr als zwei oder nur ein Nachbardreieck haben, hättendie Punkte auf der Kante keine flächige Topologie mehr. Daraus ergibt sichauch, daß sich die Oberfläche nicht selbst schneiden oder berühren darf, dadann die Zwei–Mannigfaltigkeit und damit die flächige Topologie ebenfallsverletzt wäre. Abbildung 2.2 (A), (B) und (C) skizzieren drei Beispiele, indenen die Zwei–Mannigfaltigkeit verletzt ist. Das Objekt aus (A) besitzt einLoch, bei (B) schneiden sich zwei Kanten und bei (C) besitzt Vertex a mehrals zwei Nachbarn. Abbildung 2.2 (D) skizziert hingegen ein Objekt, daßzwei–mannigfaltig ist.

Die Forderung nach Zwei–Mannigfaltigkeit stellt auch Konsistenz zwi-schen dem Thema der boolschen Operationen und den polygonalen Objekt-geometrien dar. Falls man

”offene Objekte“ zuläßt, wäre z.B. auch ein ein-

faches Dreieck oder Viereck bereits ein gültiger Operand. Die Frage, welchesObjekt die Schnittmenge von zwei dreidimensionalen, allgemeinen Viereckendarstellt, läßt sich jedoch nicht eindeutig beantworten. Die boolschen Ope-rationen lassen sich sinnvoll nur bei soliden Objekten definieren.

Aus Sicht der Regularisierung (Abschnitt 2.1.1) lassen sich die strengenForderungen an die Topologie auch begründen: Wie schon im Namen enthal-ten, beinhalten B-Reps nur Informationen über die Oberfläche eines Objek-tes. B-Reps beschränken sich also auf die Beschreibung der äußeren Punkte.Da regularisierte boolsche Operationen aber auf den inneren Punkten defi-niert sind, müssen Informationen über diese aus der B-Rep ermittelt werdenkönnen. Das aber setzt voraus, daß ein B-Rep implizit eine Menge von in-neren Punkten beschreibt. Die Forderungen an die Topologie der Dreieckestellt sicher, daß diese implizit die geforderten Informationen enthalten.

Die Reihenfolge der Dreieckspunkte wird gegen den Uhrzeigersinn fest-gelegt. Dadurch ergibt sich eindeutig eine

”Innen-“ und eine

”Außenseite“.

Die Objekte dürfen keine doppelten Punkte oder degenerierten Dreiecke ent-halten. Jeder Vertex muß also einen deutlichen3 Abstand von allen anderenVertices haben. Außerdem muß jedes Dreieck einen Mindestflächeninhalt be-schreiben, der größer als die numerische Toleranz ist.

2.2 Thematisches Umfeld

Dieser Abschnitt beleuchtet den Kontext, in dem das Thema der Arbeit zusehen ist. Er geht dabei auf CSG-Raytracing, BSP-Bäume und die Stencil-Buffer Methode ein. Diese Ansätze beschäftigen sich auch mit boolschen Ope-rationen auf dreidimensionalen Körpern und bilden somit verwandte Paradig-men der Arbeit. Die folgenden Betrachtungen geben dabei nur einen grobenÜberblick und gehen nicht auf die genaue Funktionsweise ein. Die Vor- undNachteile der verschiedenen Methoden werden hervorgehoben und mit den

3über der numerischen Toleranz

2.2. THEMATISCHES UMFELD 11

Durchschnitt

Vereinigung

Differenz

Abbildung 2.3: Raytracing von CSG–Modellen

gestellten Anforderungen verglichen.

2.2.1 Constructive Solid Geometry

In Abschnitt 2.1.3 wurde bereits der Zusammenhang von boolschen Opera-tionen mit Constructive Solid Geometry (CSG) erläutert. Die zentrale Rollespielt dabei das Konzept, aus einfachen Grundkörpern komplexe Objekte zuerstellen. Daraus kann man direkt eine Geometriebeschreibung ableiten. Eswird von einfachen Primitiven wie Quadern, Kugeln oder Zylindern ausgegan-gen. Komplexe Geometrie wird durch (hierarchische) boolsche Operationendieser Primitive definiert. Wenn man sich auf eine begrenzte Menge einfa-cher Primitive beschränken kann, besteht ein Ansatz darin, diese analytischzu definieren. Dann kann man CSG-Geometrie als Kombination von mathe-matisch definierten Körpern betrachten. Da bei dieser Vorgehensweise dieBoundary Representation (B-Rep) keine Rolle spielt, stellt sie einen eigenenAnsatz für boolsche Operationen dar.

Von den analytisch definierten Körpern kann man direkt ein Bild erzeugen(rendern). Hier bieten sich Raytracing-Algorithmen an. Foley [FvDFH96],beschreibt in Kapitel 15.10.3 einen solchen Algorithmus, der CSG-Bäumerendern kann. Dabei kommt ein Raytracing zum Einsatz, das die boolscheKombination der Primitive berücksichtigt. Jeder Körper, der einen Strahlschneidet, belegt eine Strecke darauf. Der Strahl besitzt also für jeden schnei-denden Körper einen Eintritts- und Austrittspunkt. Bei der Berechnung desCSG-Bildes werden die boolschen Operationen auf diesen Strahlsegmentenausgeführt. Für jeden Strahl wird der CSG-Baum traversiert und die Strahl-segmente der entsprechenden Objekte miteinander kombiniert. Abbildung 2.3zeigt die Kombination von einem Quader und einem Zylinder. Die linke Sei-te veranschaulicht die räumliche Situation und einen Strahl. Auf der rechtenSeite ist dieser Strahl in Schnittsegmente eingeteilt. Die dicken Segmentestellen das Ergebnis der CSG–Operation dar.


Der Vorteil bei dieser Methode besteht darin, daß die Operanden bei derboolschen Operation nicht direkt verknüpft werden müssen. Die Operationbeschreibt lediglich die Art, wie ein Körper beim Raytracing berücksichtigtwird. Bei genauerer Betrachtung wird hierbei die boolsche Operation aufeine Dimension reduziert. Differenz, Vereinigung oder Durchschnitt werdenauf der Punktmenge eines Strahls durchgeführt. Ein weiterer Vorteil ergibtsich aus der analytischen Beschreibung der Grundkörper. Durch die impliziteDefinition der Oberfläche kann diese exakt dargestellt werden und brauchtkeiner Approximation genügen.

Die Nachteile jedoch machen diesen Ansatz in diesem Kontext unbrauch-bar. Moderne Echtzeitsysteme (wie auch die Zielapplikation) rasterisierenDreiecke. Raytracing ist (noch) nicht in Echtzeit möglich bzw. nicht für dieZielapplikation einsetzbar.4 Daher müßte der CSG-Baum in ein Dreiecks-Netz umgewandelt werden, bevor es gerendert wird. Wenn aber ein Operandin der CSG-Repräsentation in seiner Lage verändert, gelöscht oder erzeugtwird, so muß die Umwandlung erneut vorgenommen werden. Da die Konver-tierung von CSG zu Dreiecken aufwändig und schwierig ist, die Umwandlungaber potentiell in jedem Frame erfolgen muß, kann dies nicht in Echtzeit er-folgen. Auf der anderen Seite ist es auch nötig, die Dreiecks-Modelle in dieCSG-Repräsentation zu konvertieren, da mit bestehenden Modellen gearbei-tet werden soll. Aufgrund dieser

”Inkompatibilität“ und der aufwändigen Be-

rechnung ist dieser Ansatz für die folgenden Betrachtungen ungeeignet. Deminteressierten Leser bietet Foley [FvDFH96] in Kapitel 12 weiterführendeInformationen und eine tiefere Diskussion dieses Themas.

2.2.2 Binary Space Partitioning

Eine sehr verbreitetes Verfahren zur Raumunterteilung ist das Binary SpacePartitioning (BSP). Dabei wird der gesamte Raum rekursiv durch Hyper-ebenen unterteilt. Bei der Speicherung der Hyperebenen entsteht ein binärerBaum. Die erste Hyperebene teilt den Raum in zwei Hälften und stellt dieWurzel dar. Das linke und das rechte Kind der Wurzel repräsentieren diebeiden Raumhälften. Diese werden jeweils durch weitere Hyperebenen un-terteilt. Dieser Prozess wird rekursiv fortgesetzt, bis der gewünschte Gradan Unterteilung erreicht ist. Eine anschauliche Beschreibung bietet Foley[FvDFH96] in Kapitel 12.6.4.

Durch diesen Prozess wird der Raum in konvexe Polyeder unterteilt. Ver-knüpft man mit den Hyperebenen Normalenvektoren und vereinbart man,daß die Normalen einer Objektoberfläche nach außen zeigen, so lassen sichmit BSP-Bäumen beliebige polygonale Objekte definieren. Abbildung 2.4 (A)zeigt ein Ausgangsobjekt. Dieses wird durch eine Raumunterteilung definiert,welche in Abbildung 2.4 (B) dargestellt ist. Den zugehörigen BSP-Baum zeigt

4dennoch gibt es Spezialhardware, die CSG-Modelle in Echtzeit rendern kann


(A) Objekt (C) BSP−Baum(B) Raumunterteilung

2

3

4

6f

d c5e

a

b

c

1

2

d 3

e4

5 f

6 7

a

b

1

Abbildung 2.4: Körperdefinition durch BSP-Bäume

Abbildung 2.4 (C).

Mit BSP-Bäumen lassen sich leicht Informationen über die räumlichenVerhältnisse ermitteln. Die Abfrage, ob ein Punkt innerhalb oder außerhalbeines Körpers liegt, kann sehr effizient berechnet werden. Neben vielen ande-ren Anwendungsgebieten, wie

”hidden surface removal“ oder Kollisionserken-

nung ist mit BSP-Bäumen auch die Berechnung von boolschen Operationenmöglich.

Naylor [Nay92] beschreibt dazu einen Algorithmus, der zwei BSP-Bäume so miteinander mischt, daß dabei die gewünschte Operation berechnetwird. Dabei werden die Elemente des einen Baumes in den anderen eingefügt,so daß der Ergebnisbaum das Resultat einer boolschen Operation repräsen-tiert. Bei Einfügeoperationen werden die Hyperebenen geteilt und genau dieTeile verworfen, die für das Ergebnis irrelevant sind. Die

”Binary Space Par-

titioning Trees FAQ“ [Wad95] bietet in Abschnitt 11 neben weiterführendenInformationen ein anschauliches Beispiel dazu.

Obwohl BSP-Bäume auch in der Praxis für boolsche Operationen einge-setzt werden, sprechen einige Aspekte doch gegen diesen Ansatz. Zunächstmuß wieder eine Konvertierung der B-Rep Darstellung in BSP-Bäume vorge-nommen werden. Nachdem die boolsche Operation als BSP-Baum ausgeführtwurde, muß dieser wieder in Dreiecke überführt werden. Neben dem Zeitauf-wand, der bei dieser Umwandlung investiert werden muß, entsteht noch einweiterer Nachteil. Wenn BSP-Bäume aus Dreiecks- oder Polygonnetzen auf-gebaut werden, müssen in der Praxis viele Flächen geteilt werden. Bei realenModellen wird sich kaum eine Ebene finden, die keine Polygone schneidet.Da eine Ebene aus dem BSP-Baum den Raum aber komplett teilt, muß einPolygon, was sich in beiden Raumhälften befindet, auch geteilt werden. Diesresultiert nicht nur in redundanten Informationen, sondern erhöht auch dieAnzahl der Polygone nach der Rückkonvertierung in das Dreiecksnetz.

Fatal wirkt sich in diesem Zusammenhang aus, daß laut Forderung zwei


(oder mehr) Körper vielfach miteinander in verschiedenen Positionen kombi-niert werden können. Bei jeder boolschen Operation würden nicht nur neueHyperebenen erzeugt werden, sondern auch eine Vielzahl bestehender Ebenengeteilt werden. Ohne zeitaufwändige Optimierungsschritte explodiert die An-zahl der Ebenen, was die Anwendung in einer Echtzeitapplikation unmöglichmacht.

2.2.3 Die Stencil-Buffer Methode

Ein sehr interessantes Verfahren zum rendern von CSG-Modellen5 benutztMerkmale moderner Graphik-Hardware. In Kombination mit dem Z-Bufferund dem Stencil-Buffer bietet OpenGL die Möglichkeit, das Ergebnis einerboolschen Operation zu rendern [McR96]. Die grundlegende Idee ist es, imStencil Buffer Paritäten zu akkumulieren, mit denen die Objekte maskiertwerden und das Bild zusammengesetzt wird. Der Algorithmus in der Fassungvon McReynolds [McR96] lautet:

deaktiviere "color buffer"

lösche "stencil buffer"

aktiviere "depth testing"

aktiviere "backface culling"

rendere Objekt A

// Der Z-Buffer enthält nun die z-Werte der Vorderseite von A

// inkrementiere den stencil buffer, wenn Z-Test erfolgreich

glStencilFunc(GL_ALWAYS, 0, 0)

glStencilOp(GL_KEEP, GL_KEEP, GL_INCR)

rendere Objekt B

// dekrementiere den stencil buffer, wenn Z-Test erfolgreich

glStencilOp(GL_KEEP, GL_KEEP, GL_DECR)

// aktiviere "frontface culling"

glCullFace(GL_FRONT)

rendere Objekt B //nochmals

Nach dieser Prozedur ist der der stencil buffer überall da ungleich 0, wodie Oberfläche von Objekt B im Inneren von Objekt A ist. Der Stencil Bufferkann nun dazu genutzt werden, die Darstellung der Objekte zu maskieren.Dabei werden die Objekte nur dort gerendert, wo der Stencil-Test erfolgreichist. Die Art des Stencil-Test gibt dabei die gewünschte Operation an. Umzum Beispiel den Teil von A darzustellen, dessen Vorderseite im Inneren vonB liegt, geht man so vor:

5und damit von boolschen Operationen


// Stencil-Test überall da wahr, wo stencil buffer != 0

glStencilTest(GL_NOTEQUAL, 0, 0)

// deaktiviere stencil buffer updates

glStencilMask()

// aktiviere "backface culling"

glCullFace(GL_BACK)

deaktiviere "depth testing"

rendere Objekt A

Die Vorderseite von Objekt A erscheint nun überall da, wo sie innerhalbvon Objekt B liegt — der Stencil Buffer ist genau an diesen Stellen ungleich0. Bei einer normalen Darstellung ohne CSG würden die Punkte von ObjektB im Z-Buffer weiter vorn liegen und gerendert werden. Wenn man hinge-gen den Teil von A rendern will, der außerhalb von B liegt, so setzt manden Stencil-Test auf GL_EQUAL. Eine detaillierte Diskussion dieses Verfahrensbieten Wiegand [Wie96] oder Steward [SLJ98].

Da diese Implementierung der boolschen Operationen auf allen Objektenfunktioniert, die bereits vom System dargestellt werden können, ist das Vor-gehen sehr einfach zu implementieren und verlangt nur minimale Eingriffe inein bestehendes System. Auch hier gilt die Einschränkung, daß die Objek-te geschlossen (solide) sein müssen und das Dreiecksnetz zwei–mannigfaltigist. Eine Verletzung dieser Forderungen würde die Stabilität nicht gefähr-den, dennoch würden Darstellungsfehler resultieren, die den Eindruck derboolschen Operation vernichten. Aufgrund der Hardwarebeschleunigung mo-derner Graphiksysteme kann die Operation sehr schnell ausgeführt werden.

Ein großer Nachteil macht diese einfache Methode jedoch unbrauchbarfür die Zielapplikation. Die Berechnung findet ausschließlich im Bildraumstatt. Dies erzeugt auf der einen Seite Stabilität und Schnelligkeit, jedochmacht es eine Weiterverarbeitung der Geometrie unmöglich. Es werden keineSchnittpunkte oder Schnittflächen berechnet und es wird keine Geometrieverändert. Für jede einzelne Operation muß eine neue Instanz eines Operan-den erzeugt werden. Da im Zielsystem aber potentiell in jedem Frame eineboolsche Operation ausgeführt wird, würde die Anzahl der Geometrien zuschnell ansteigen.

2.2.4 Zusammenfassung

Die vorgestellten Algorithmen haben jeweils ihre eigenen Vorteile, was siefür andere Anwendungen prädestiniert. Wenn man eine einzelne boolscheOperation zweier Körper rendern will, bietet sich die Stencil-Buffer Methodean. Wenn einfache Basisobjekte genügen und das Ziel ein (nicht interaktives)Bild mit hoher Qualität ist, so ist CSG-Raytracing das Mittel der Wahl. ImZusammenhang mit den gestellten Anforderungen hat jeder Ansatz jedochgravierende Nachteile, die in Tabelle 2.1 zusammengefaßt werden.


Eingabe Robustheit Effizienz Ausgabe

CSG – – + + – – –

BSP + + – – –

Stencil-Buffer + + + + + + – –

Tabelle 2.1: Eignung verwandter Algorithmen bezüglich der Anforderungen

(D) Vereinigung(A) Original (B) Differenz (C) Durchschnitt

Abbildung 2.5: Zusammensetzen der Oberfläche aus den inneren und äußerenKörperteilen

Ein großer Nachteil, den die drei Algorithmen gemeinsam haben, bestehtdarin, daß sie eine ungeeignete Ausgabe besitzen. Um das Resultat der bool-schen Operation für eine neue Operation zu verwenden, soll es erneut in poly-gonaler Darstellung vorliegen. Jedoch berechnet keiner der drei Algorithmendirekt einen Polyeder.

2.3 Berechnung von Dreiecksnetzen

Die Lösung des Problems bietet ein Algorithmus, der die boolsche Opera-tion direkt auf den vorhandenen Eingabedaten6 ausführt. Dadurch fällt dieUmwandlung der Daten in ein renderbares Format weg. Foley [FvDFH96]nennt solche Modelle beim Vergleich der Methoden in Kapitel 12.8

”eva-

luated models“. Das Resultat der Operation wird bei diesen Ansätzen also(endgültig) berechnet, während die

”unevaluated models“ bei der Darstel-

lung das eigentliche Resultat erst erzeugen müssen. Das Ziel ist es also, eine

”evaluated boundary representation“ zu erzeugen.

Den Ansatz gibt erneut Foley [FvDFH96] in Kapitel 12.5.3. Dort wirdein Algorithmus beschrieben, der von Laidlaw entwickelt wurde [LTH86].Die Idee besteht darin, zunächst die Operanden in zwei Teile zu zerlegen,die jeweils vollständig innerhalb oder außerhalb des Volumens des anderenKörpers sind. Danach werden nur die Teile in das Resultat aufgenommen,

6also Dreiecken

2.3. BERECHNUNG VON DREIECKSNETZEN 17

die für die betreffende boolsche Operation zutreffend sind.

Abbildung 2.5 illustriert die Konstruktion des Ergebniskörpers. Links sindeine Kugel und ein Quader zu sehen. Die Teile, die innerhalb des Volumensdes anderen Körpers liegen, sind gestrichelt dargestellt. Daneben sind diedrei boolschen Operationen zu sehen. Der Linienstil zeigt, welche Teile derOriginale in den Ergebniskörper einfließen. Berechnet man beispielsweise denDurchschnitt von A und B (A

⋂* B), so werden nur die Teile übernommen,

die jeweils innerhalb des Volumens des anderen Objektes liegen (siehe Ab-bildung 2.5 (C)).

Eine Verbesserung dieses Algorithmus mit Beschränkung auf die Berech-nung von Dreiecken beschreibt Hubbard [Hub90]. Die dort vorgestelltenVerfahren dienen als Leitfaden für diese Arbeit. Auf die Details wird in Ka-pitel 3 genauer eingegangen.

2.3.1 Teilung der Oberfläche

Als erstes wird davon ausgegangen, daß die Oberflächen der beiden Objek-te zusammenhängende Schnittlinien bilden. Jedes Segment einer Schnittliniewird durch zwei schneidende Polygone der beiden Körper gebildet. Um diePolygone eindeutig dem Ergebniskörper zuordnen zu können, besitzen siedas Attribut

”Klassifikation“. Dieses gibt an, ob sich das Polygon innerhalb

oder außerhalb des Volumens des anderen Körpers befindet. Um jedem Poly-gon eine eindeutige Klassifikation zuordnen zu können, werden die Polygonean der Schnittlinie so geteilt, daß die Polygonteile vollständig

”innen“ oder

”außen“ bezüglich des anderen Körpers sind. Es darf also keine Polygone ge-

ben, die teilweise innen und außen sind. Polygone, die vollständig innerhalboder außerhalb des anderen Körpers sind, werden nicht geteilt. Sie werdenals Ganzes klassifiziert und anschließend übernommen oder verworfen.

Zunächst müssen die Polygone gefunden werden, auf denen die Schnittli-nie liegt. Dazu müssen sie einzeln gegeneinander auf Schnitt getestet werden.Bei der entwickelten Anwendung dient dazu eine allgemein anwendbare, fle-xible und optimierte Kollisionserkennung (siehe Abschnitt 4.3). Diese berech-net auf der einen Seite, welche Objekte sich berühren bzw. durchschneidenund auf der anderen Seite, welche Dreiecke genau bei diesem Schnitt beteiligtsind. Die Kollisionserkennung ist in der Lage, diesen Schritt schnell und ef-fizient durchzuführen. Dadurch ist es für die boolsche Operation nicht mehrnötig, jedes Dreieck des ersten Operanden gegen alle Dreiecke des zweitenOperanden zu testen. Es werden nur noch die Dreiecke betrachtet, die beider Schnittlinie beteiligt sind.

Als nächstes muß die Schnittlinie der Polygone berechnet werden. Polygo-ne können nicht nur eine Schnittlinie besitzen, sondern im allgemeinen Fallmehrere. Sind die Polygone planar, so existiert nur eine Schnittgerade, je-doch bestehen die Schnittlinien aus mehreren Geradensegmenten. Laidlaw


(B) geteilte Oberfläche(A) Polygone mit Schnittlinie

Abbildung 2.6: Teilung der Oberfläche anhand der Schnittlinie

[LTH86] beschränkt sich daher bei der Eingabe seines Algorithmus auf plana-re, konvexe Polygone. Hier kann ein Schnittsegment berechnet werden, wel-ches Teil der Schnittlinie wird. Wie in Abschnitt 2.3.4 näher erläutert wird,ist es sogar sinnvoll, sich auf die Berechnung von Dreiecken zu beschränken.Eine detaillierte Diskussion zur Berechnung der Schnittlinie findet sich inAbschnitt 3.1.

Als letzter Schritt zur Teilung der Oberfläche werden die Polygone ander Schnittlinie geteilt. Die Schnittlinie beginnt an einer Kante im Polygonund endet an einer anderen Kante. Diese beiden Kanten werden geteilt undes werden zwei neue Polygone gebildet. Durch die Beschränkung auf planarekonvexe Polygone entstehen ebenfalls zwei planare konvexe Polygone. Ab-bildung 2.6 (A) zeigt ein Beispiel eines Polygonnetzes. Die Schnittlinie istgestrichelt eingezeichnet. In Abbildung 2.6 (B) ist das geteilte Polygonnetzdargestellt. Der

”herausgetrennte“ Teil ist grau dargestellt und kann einheit-

lich klassifiziert werden.

2.3.2 Spezialfälle

Besondere Beachtung verdienen die vielen Spezialfälle, die bei allgemeiner La-ge von Polygonen auftreten können. Zwei Polygone werden als

”nicht schnei-

dend“ betrachtet, wenn ihre Punktmengen vollkommen disjunkt sind, odersie genau einen Punkt teilen. Die beiden Polygone sind

”schneidend“, wenn

ihre Schnittmenge eine Gerade ist. Insbesondere sind auch zwei Polygoneschneidend, wenn sie nur eine Kante teilen, oder die Kante eines Polygonsauf der Fläche von dem anderen Polygon liegt. Sind die Polygone jedochkoplanar und überlagern sich, so werden sie als

”überlappend“ bezeichnet.

Wie Laidlaw [LTH86] in Kapitel 4 zeigt, genügt es, nur die”schneiden-

den“ Polygone zu teilen. Überlappende Polygone werden bei der Unterteilungalso nicht weiter beachtet. Diese Einsicht erspart die Behandlung einer Reihe


i

b c

f g h

f hb c

f g h

a d

e

Abbildung 2.7: Behandlung von koplanaren Oberflächen

von Spezialfällen, ist aber keineswegs offensichtlich. Das folgende Beispiel solldiese These bestätigen.

Abbildung 2.7 skizziert zwei Körper, A (a, b, c, d, Kreuze) und B(e, f, g, h, i, Kreise). Wenn die beiden Körper A und B eine koplanare Flächeteilen (f − h), so gilt es zunächst festzustellen, daß jedes Polygon an jederKante einen Nachbarn hat (Zwei–Mannigfaltigkeit). Wenn dieser Nachbarebenfalls koplanar ist, so erfolgt bei ihm die gleiche Berechnung. Interessantist die

”Kante“ dieses koplanaren Polygon-Clusters7, an der die Nachbarn

nicht mehr koplanar sind. In Abbildung 2.7 wird das Dreieck bei gh betrach-tet. Das Dreieck bei cd liegt zu ihm koplanar. Der Nachbar hi ist jedochnicht mehr koplanar. Daher erzeugt hi eine Schnittlinie auf cd. Die Schnitt-linie bildet genau die Kante zwischen gh und hi. Durch die Erzeugung derSchnittlinie im Körper A werden die entsprechenden koplanaren Dreieckevon A (ab, cd) geteilt. Bei den Kanten, die innerhalb der koplanaren Flächenliegen, brauchen keine Polygone geteilt werden (im Beispiel bei b, c und g).Letztlich werden Cluster von Polygonen, die koplanar mit Polygonen des an-deren Objektes sind, genau an den Kanten der gemeinsamen Fläche geteilt.Die rechte Seite von Abbildung 2.7 zeigt die geteilten Cluster der beidenKörper, die eine gemeinsame Fläche teilen.

Die Außenkanten der beiden Cluster sind identisch. Im Inneren der Clu-ster kann die Triangulierung der beiden Körper völlig unterschiedlich sein.Dies spielt aber keine Rolle bei der boolschen Operation, da es aus Sichtder Geometrie egal ist, welcher Verlauf der Kanten bei einer koplanarenFläche gewählt wird. Koplanare Flächen werden also paarweise behandeltund so

”beschnitten“, daß sie genau

”aufeinander passen“ und geometrisch

äquivalent sind. Wichtig ist nur, daß höchstens ein Cluster in das Resultatübernommen wird. Würden beide Cluster übernommen werden, so würde dieFläche doppelt definiert werden. Diese Forderung wird in der Klassifizierungsichergestellt. Hubbard [Hub90] erläutert diese Logik anschaulich in Kapitel4.1.

7Menge von zusammenhängenden Polygonen


des Strahls(A) Klassifizierung

"innen"(B) Klassifizierung

"außen"(C) Verschiebung

Abbildung 2.8: Klassifizierung durch Raytracing

Die Unterteilung der Polygone in vollständig”innen“ und

”außen“, die

im vorherigen Abschnitt eingeführt wurde, wird nun um die Klassifikation

”koplanar“ erweitert. Jedes Polygon von Operand A ist also genau einer der

folgenden Klassen zuzuordnen:

• vollständig innerhalb Operand B

• vollständig außerhalb Operand B

• vollständig koplanar zur Oberfläche von Operand B

Durch die Teilung der Oberfläche wird sichergestellt, daß die Punktmengeeines Polygons vollständig einer dieser Klassen zugeordnet werden kann.

2.3.3 Klassifizierung der Oberfläche

Nachdem es keine Polygone von A mehr gibt, die gleichzeitig innerhalb, au-ßerhalb oder koplanar bezüglich des Volumens von B sind, muß jedes Polygoneiner Klasse eindeutig zugeordnet werden. Dazu benutzt Laidlaw [LTH86]ein Raytracing. Der Ursprung des Strahls ist der Schwerpunkt des zu klas-sifizierenden Polygons PA aus A. Die Richtung des Strahls entspricht derNormalen des Polygons. Der Strahl zeigt also

”nach außen“. Der Strahl wird

mit allen Polygonen von Objekt B geschnitten und es wird der Abstand allerSchnittpunkte gegenüber dem Strahlursprung in Richtung des Strahls berech-net. Wenn der Abstand kleiner 0 ist, so wird der Schnittpunkt verworfen.8

Von allen geschnittenen Polygonen wird das ermittelt, dessen Schnittpunkt

8da der Strahl nur in die positive Richtung zeigt


den geringsten Abstand hat (PB). Ist der Abstand gleich 0, so sind PA undPB koplanar.

Wenn der kleinste Abstand größer 0 ist, wird aus der Normalen von PAund PB das Skalarprodukt berechnet. Wenn das Skalarprodukt größer als 0ist, so zeigt die Normale von PB weg von PA. Das zu klassifizierende Polygonist also

”unter“ dem nächsten Polygon aus B und damit innerhalb des Vo-

lumens von B (siehe Abbildung 2.8 (A)). Ist Das Skalarprodukt kleiner als0, so ist PA entsprechend außerhalb von B (Abbildung 2.8 (B)). Wenn dasSkalarprodukt 0 ist, so verläuft der Strahl parallel zu PB. Laidlaw löst dieseMehrdeutigkeit dadurch, daß er den Strahl leicht verschiebt.9 In der Praxiswird dadurch ein anderes Polygon geschnitten, welches ein Skalarproduktungleich 0 liefert. Abbildung 2.8 (C) zeigt die Verschiebung des Strahls.

Das beschriebene Raytracing ist aus der Sicht der Rechenzeit sehraufwändig. Um alle Polygone eines Objektes klassifizieren zu können, mußfür jedes Polygon aus Objekt A ein Strahl berechnet werden, der gegen je-des Polygon von Objekt B getestet wird. Um dieses Problem zu verringern,wird davon ausgegangen, daß alle Kanten, die zwei Polygone unterschiedli-cher Klassifikation trennen, auf der Schnittlinie der Körper A und B liegen.Ausgehend von einem klassifizierten Polygon kann man daher die Klassifizie-rung an alle Nachbarn propagieren, solange diese nicht auf der anderen Seiteder Schnittlinie liegen. Dadurch reicht es, für jeden gegenüber der Klassi-fizierung homogenen Teil des Objektes ein Raytracing zu machen und dasErgebnis zu propagieren.

Nachdem die Polygone von Operand A bezüglich Körper B klassifiziertwurden, muß der Algorithmus in umgekehrter Richtung erfolgen. Mit eineranalogen Berechnung werden die Polygone von Operand B bezüglich KörperA klassifiziert, so daß von jedem Polygon beider Körper bekannt ist, in wel-chem Verhältnis es zum anderen Körper steht.

2.3.4 Dreiecksnetze

Für alle bisherigen Betrachtungen dienten planare, konvexe Polygone alsGrundlage. Diese Einschränkung brachte eine Reihe von Vereinfachungen beider Berechnung. Wie Hubbard [Hub90] in Kapitel 2 erläutert, ist es jedochsinnvoll, sich bei der Berechnung von boolschen Operationen auf Dreiecke zubeschränken.

Wenn man Polygone mit mehr als drei Punkten zuläßt, entsteht eine po-tentielle Schwachstelle in der Forderung, daß diese planar und konvex sind.Wird dies nicht gefordert, werden die Algorithmen schnell unübersichtlichund ineffizient. Andererseits ist die Genauigkeit in der Darstellung von ge-brochenen Zahlen auf dem Computer begrenzt. So kann es zum Beispiel

9der genaue Mittelpunkt von PA als Ursprung des Strahls ist nicht kritisch für dasVerfahren


vorkommen, daß konvexe Polygone kollineare Punkte enthalten, die durchUngenauigkeiten in den internen Datenstrukturen tatsächlich konkav sind.Genauso ist es auch nur bis auf eine bestimmte Fehlergenauigkeit möglich,alle Punkte eines Polygons in einer Ebene zu halten. Bei Dreiecken hingegenliegt es in ihrer Natur, planar und konvex zu sein. Wenn man degenerierteDreiecke verbietet10, so können auch keine kollinearen Eckpunkte auftreten.Durch die Beschränkung auf Dreiecke und die Beseitigung der genannten po-tentiellen Fehlerquellen werden die Algorithmen also übersichtlicher und vorallem robuster.

Wie bereits erwähnt, bestimmt die Normale der Oberfläche, welche Seitenach innen und welche nach außen zeigt. Die Normalen beinhalten also wich-tige Informationen, die kritisch für den Algorithmus sind. Verwendet manDreiecke mit einem Mindestflächeninhalt über der numerischen Toleranz, soist die Berechnung der Normalen trivial. Sie besteht aus dem Kreuzproduktzweier Seitenvektoren. Sie ist garantiert orthogonal zu der Dreiecksfläche undbesitzt eine Länge größer 0, da das Dreieck einen Flächeninhalt größer überder numerischen Toleranz besitzt. Bei allgemeinen Polygonen ist die Berech-nung von Normalen schwieriger. Wenn die Punkte, die als Eingabe für dasKreuzprodukt dienen, (fast) kollinear sind, ist die Berechnung der Normalennumerisch ungenau oder die Länge der Normalen 0.

Ein weiterer Vorteil der Verwendung von Dreiecken sind die einfachere-ren Datenstrukturen, die verwendet werden können. Allgemeine Polygonehaben eine unbestimmte Anzahl von Punkten und Kanten. Bei Dreiecksnet-zen hingegen sind diese Informationen a priori bekannt. Somit lassen sicheinfachere und effizientere Datenstrukturen wie zum Beispiel Arrays stattListen verwenden. Die einzige variable Topologie-Information ist die Anzahlder Dreiecke, die einen Punkt teilen.

Schließlich fällt auch der Schritt von der Forderung nach konvexen, plana-re Polygonen hin zu Dreiecken nicht schwer, da man diese Polygone sehr leichtin Dreiecke umwandeln kann. Im einfachsten Fall legt man einen Startpunktfest und

”fächert“ das konvexe Polygon ausgehend davon auf. Zu beachten ist

allerdings, daß eine konsequente Verwendung von Dreiecken einen etwas dif-ferenzierten Ansatz bei der Teilung der Oberfläche (Abschnitt 3.1) und derTriangulierung (Abschnitt 3.3) erfordern. In den betreffenden Abschnittenerfolgt eine detailliertere Diskussion.

2.3.5 Zusammenfassung

Abbildung 2.9 faßt den Algorithmus in der Grobform zusammen. Die Metho-den, die in den weiteren Betrachtungen vertieft werden sollen, gliedern sichin zwei Grundschritte: die Teilung der Oberfläche und die Ausführung derboolschen Operation.

10diese können leicht in einer Vorverarbeitung entfernt werden


− Konstruktion des Ergebniskörpers

Eingabekörper A

Teilung der Oberfläche

− Berechnung der Schnittlinie

− Zusammenfassen von Dreiecksclustern

− Neu−Triangulierung

Eingabekörper B

Ergebnis der boolschen Operation

Ausführung der boolschen Operation

− Klassifizierung: "innen", "außen", "koplanar"

Abbildung 2.9: Skizzierung des Algorithmus

Die Teilung der Oberfläche beginnt mit der Berechnung der Schnittlinien,an denen sich die beiden Körper schneiden. Danach werden die Dreiecke derKörper zu planaren Polygonen zusammengefasst. Dieser Schritt wird in Ab-schnitt 3.2 erläutert und soll hier nicht weiter vertieft werden. Danach werdendie Oberflächen der beiden Körper an den Schnittlinien neu trianguliert, sodaß die Schnittlinien ausschließlich auf den Kanten der Dreiecke verlaufen.

Nach der Teilung kann die boolsche Operation ausgeführt werden.Zunächst wird jedes Dreieck der Körper klassifiziert, indem bestimmt wird,ob es innerhalb oder außerhalb des Volumens des anderen Körpers liegt, oderob es koplanar zur Oberfläche des anderen Körpers ist. Nun können die Drei-ecke ausgewählt werden, die für die jeweilige boolsche Operation zutreffendsind. Aus ihnen wird der Ergebniskörper konstruiert.

Eine gesonderte Betrachtung der einzelnen Schritte folgt im nächsten Ka-pitel.

Kapitel 3

Entwurf

Dieses Kapitel befaßt sich mit der konkreten Ausarbeitung des vorgestell-ten Ansatzes. Es werden Details, Teilprobleme und Lösungen vorgestellt, diewährend der Entwicklung entstanden sind. Die Reihenfolge der Abschnittefolgt dabei der Schrittfolge des Algorithmus. Es wird davon ausgegangen,daß die Kollisionsabfrage stattgefunden hat. Der Algorithmus bekommt alsEingabe die beiden Operanden (mit ihrer Geometrie), die gewählte boolscheOperation und von der Kollisionserkennung die Information darüber, welcheDreiecke sich schneiden.

3.1 Berechnung der Schnittlinie

3.1.1 Koordinatensysteme

Die zwei Operanden der boolschen Operation sind jeweils in ihrem eigenenlokalen Koordinatensystem definiert. Sie besitzen jeweils eine Transformati-onsmatrix, mit der sie in das Weltkoordinatensystem transformiert werden.Da die boolsche Operation in einem Koordinatensystem arbeitet, müssen diePunkte in das Koordinatensystem des Ergebniskörpers transformiert werden.Für die boolsche Operation wird festgelegt, daß sich das Ergebnis im Koor-dinatensystem von Operand A befinden soll.

Um die Punkte von Operand B (p) aus dem Koordinatensystem B indas Koordinatensystem A transformieren, werden die Punkte zuerst mit derTransformationsmatrix von MB in das Weltkoordinatensystem überführt:

p′ = MB p (3.1)

Als nächstes werden die Punkte p′ mit der inversen Transformationsmatrixvon A (M−1A ) in das Koordinatensystem von A transformiert:

p′′ = M−1A p′ (3.2)

25

26 KAPITEL 3. ENTWURF

Die Transformationsmatrix MBA, mit der die Punkte von B nach A trans-formiert werden, ergibt sich somit aus:

MBA = M−1

A MB (3.3)

Um MBA zu berechnen wird die Inversion von Matrix MA benötigt. Von MAist jedoch bekannt, daß sie ausschließlich aus einer Rotation RA und einerTranslation TA besteht:

MA = TA RA (3.4)

Mit dieser Voraussetzung läßt sich leicht eine Inversion formulieren:

M−1A = (TA RA)−1 = R−1A T

−1

A (3.5)

Da RA eine reine Rotationsmatrix und somit orthonormal ist, gilt R−1

A = RTA.

Die obere 3x3-Matrix muß also einfach transponiert werden. Das inverse einerTranslationsmatrix T (x) mit dem Vektor x ist T (−x), also die Translation indie entgegengesetzte Richtung. Die Matrix T−1A wird daher aus den negiertenWerten der Translation von A gebildet.

Nachdem die Transformationsmatrix MBA gebildet wurde, werden mitihr alle Punkte von Objekt B in das Koordinatensystem A überführt, wo siezur weiteren Berechnung genutzt werden können. Zusammengefasst lautetdie vollständige Transformationsreihenfolge also:

p′′ = MBA p = M−1

A MB p = R−1

A T−1

A MB p (3.6)

3.1.2 Dreieck-Dreieck Überschneidung

Nachdem alle Punkte in ein Koordinatensystem transformiert wurden, kannnun die Schnittlinie berechnet werden. Die Schnittlinie setzt sich aus einerReihe zusammenhängender Segmente zusammen, die durch den Schnitt dereinzelnen Dreiecke entstehen. Dieser Abschnitt erläutert die Berechnung dereinzelnen Segmente. Dazu wird der Ansatz aus [Hub90] bzw. [LTH86] benutztund weiter konkretisiert.

Der erste Schritt (1) bei der Berechnung der Schnittsegmente zweier Drei-ecke A und B bildet die Ermittlung der (vorzeichenbehafteten) Abstände derEckpunkte von A gegenüber der Ebene von B. Dazu werden die drei Eck-punkte von A in die Ebenengleichung von B eingesetzt. Abbildung 3.1 (A)zeigt zwei Dreiecke, von denen die Schnittlinie (gestrichelt) berechnet wer-den soll. Die Abstände des schrägen Dreiecks zu der Ebene des anderen sindgepunktet eingezeichnet. Im zweiten Schritt (2) werden alle Abstände, de-ren Betrag kleiner als eine Toleranz ist, auf 0 gesetzt. Eckpunkte, die sehrnahe an der Ebene von B sind, werden daher so betrachtet, als ob sie aufB liegen. Dieser Schritt trägt der fehlerbehafteten internen Darstellung vonGleitkommazahlen Rechnung und dient der Robustheit des Algorithmus. Imdritten Schritt (3) wird überprüft, welche Eckpunkte auf unterschiedlichen

3.1. BERECHNUNG DER SCHNITTLINIE 27

Seiten von B liegen. Dazu werden die Vorzeichen der Eckpunkt–Abständemiteinander verglichen und folgende Fälle unterschieden:

• Alle Vorzeichen haben positive Werte oder alle haben negative Werte.Dreieck A liegt vollständig auf einer Seite von B und schneidet B nicht.Die Schnittberechnung von A und B wird abgebrochen.

• Ein Abstand ist 0, die anderen Abstände haben gleiche Vorzeichen.Dreieck A berührt die Ebene von B mit nur einem Punkt1. Das Schnitt-segment besteht nur aus höchstens einem Punkt und braucht dahernicht beachtet zu werden: Entweder, dieser Punkt ist Teil der Schnitt-linie. Dann werden sich an diesem Punkt

”echte“ Schnittsegmente von

Nachbardreiecken von A treffen. Oder, die beiden Dreiecksnetze treffensich nur in diesem Punkt. Dann ist diese Stelle für die boolsche Opera-tion irrelevant. Die Schnittberechnung von A und B wird abgebrochen.

• Alle Abstände sind 0. Dreieck A und Dreieck B sind koplanar. Wie inAbschnitt 2.3.2 erläutert, ist der Schnitt von A und B irrelevant unddie Schnittberechnung für A und B wird abgebrochen.

• Zwei Abstände sind 0, der andere ungleich 0. Eine Kante von DreieckA liegt in der Ebene von Dreieck B. Diese Kante bildet die Gerade fürein mögliches Schnittsegment.

• Zwei Abstände haben verschieden Vorzeichen ungleich 0. Dreieck Aschneidet die Ebene von B und bildet eine Schnittgerade. Der drittePunkt kann auf dieser Schnittgeraden liegen.

Die Schritte (1) bis (3) werden ebenfalls für Dreieck B gegenüber A durch-geführt. Tritt bei beiden Berechnungen der letzte oder der vorletzte Fall ein,so schneiden sich A und B und die Berechnung wird fortgeführt.

Im nächsten Schritt werden die Schnittpunkte der schneidenden Kantenkl mit der Ebene berechnet. Dazu wird das Verhältnis vom Abstand derEbene von Punkt k zum Gesamtabstand beider Punkte berechnet (sieheAbbildung 3.1 (B)). Dieses Verhältnis gibt den Interpolationsparameter t an,mit dem der Schnittpunkt s berechnet werden kann:

s = t ∗ k + (1 − t) ∗ l (3.7)

Wenn ein Eckpunkt eines Dreiecks auf der geschnittenen Ebene liegt, so bildetdieser Punkt den Schnittpunkt.

Aus dieser Berechnung resultieren vier Schnittpunkte, jeweils zwei für denSchnitt eines Dreiecks mit der Ebene des Anderen. Die beiden Schnittpunkteeines Dreiecks werden als Intervall aufgefaßt. Der Durchschnitt beider Inter-valle bildet das Schnittsegment der beiden Dreiecke. Um zu ermitteln, welche

1der Eckpunkt, dessen Abstand 0 ist


t

(A) Ermittlung derschneidenden Kanten

(B) Berechnung derSchnittpunkte

(C) Projektion auf eineKoordinatenachse

k

l

k

l

s

Abbildung 3.1: Berechnung von Schnittsegmenten

der vier Schnittpunkte das Intervall bilden, werden diese geordnet. Dazu wirddie Dimension von drei auf eine reduziert, indem die Schnittpunkte auf ei-ne Koordinatenachse projiziert werden (siehe Abbildung 3.1 (C)). Um dienumerische Stabilität des Vergleichs zu gewährleisten und damit die Robust-heit zu erhöhen, wird die Koordinatenachse ausgewählt, in der die Richtungder Schnittgerade die größte Ausdehnung besitzt. Die Werte der vier Schnitt-punkte werden in dieser Dimension verglichen. Dazu werden die beiden Inter-valle so geordnet, daß der Startpunkt eines Intervalls beim Vergleich kleinerist, als der Endpunkt. Danach werden folgende Fälle unterschieden:

• Der Endpunkt von Segment A ist kleinergleich dem Startpunkt von Seg-ment B oder der Startpunkt von Segment A ist größergleich dem End-punkt von Segment B. Die beiden Segmente bzw. die beiden Dreieckeüberschneiden sich nicht. Die Schnittberechnung wird abgebrochen.

• Das Segment A liegt vollständig innerhalb Segment B. Das Schnittseg-ment ist Segment A.

• Das Segment B liegt vollständig innerhalb Segment A. Das Schnittseg-ment ist Segment B.

• Für alle anderen Fälle wird das Schnittsegment aus dem größeren Start-punkt und dem kleineren Endpunkt gebildet. Wenn beide Start- oderEndpunkte gleich sind, so schneiden sich die Kanten der beiden Drei-ecke.

Das berechnete Schnittsegment wird in die Datenstrukturen beider Drei-ecke eingefügt. Jedes Dreieck beinhaltet eine Liste von Linienzügen. Wennein Segment in ein Dreieck eingefügt wird, so wird geprüft, ob dieses Segmenteinen Linienzug auf einer Seite fortführt.2 In diesem Fall wird das Segment

2d.h., ob ein Endpunkt des Segments mit einem der Endpunkte des Linienzuges iden-tisch ist

3.2. ZUSAMMENFASSEN PLANARER DREIECKE 29

in die Datenstruktur des Linienzuges integriert. Paßt das Schnittsegment ankeinen Linienzug oder existiert für dieses Dreieck noch kein Linienzug, sowird das Segment als neuer Linienzug in die Datenstruktur eingefügt. Au-ßerdem ist der Fall zu beachten, daß ein Segment zwei Linienzüge vereinigtoder einen Linienzug schließt.

Die Entscheidung, daß beide Dreiecke eine Kopie des Schnittsegments be-kommen, liegt im lokalen Ansatz der Schnittlinienberechnung. Die Reihenfol-ge, in der die einzelnen Segmente berechnet werden, ist unbestimmt.3 Daherwerden die Schnittsegmente zunächst lokal für jedes Dreieck in begrenztenLinienzügen verwaltet. Wenn zwei Dreiecke sich schneiden, so teilen sie nurein Segment des Linienzuges. Bei den restlichen Segmenten des Linienzugessind andere Dreiecke involviert.

Bei allen Berechnungen, Vergleichen und Fallunterscheidungen gilt es zubeachten, daß keine Punkte doppelt erzeugt werden. Dies würde den topolo-gischen Zusammenhang zerstören oder zu degenerierten Fällen führen. Dazumuß bei der Berechnung des Schnittsegments und bei der Erzeugung neuerSchnittpunkte ermittelt werden, ob der Schnittpunkt einem Eckpunkt bei-der Dreiecke entspricht oder bereits in den Datenstrukturen von einem derDreiecke erzeugt und eingefügt wurde.

In diesem Zusammenhang spielen auch die Punkte der Linienzüge einegroße Rolle, die auf den Seitenkanten des Dreiecks liegen. Wenn ein Schnitt-segment ermittelt wird, dessen Endpunkt auf einer Seitenkante liegt, so ist esmöglich, daß das Nachbardreieck an dieser Kante den Punkt bereits erzeugthat. Um diese Situation aufzulösen, wird in solchen Fällen ein Linienzug miteinem Punkt4 in das Nachbardreieck eingefügt. Ist dieses Dreieck mit derBerechnung an der Reihe, so besitzt es diesen Punkt bereits und kann ihnnicht doppelt erzeugen.

Die Berechnung der Schnittsegmente wird für alle Dreiecke durchgeführt,bei denen die Kollisionserkennung einen Schnitt meldet. Als Ergebnis hatjedes Dreieck eine Liste von Linienzügen, welche die Schnittlinie in diesemDreieck beschreiben. Unter der Voraussetzung, daß die Eingabeobjekte solidesind, bildet die Gesamtheit der Linienzüge zusammenhängende, geschlosseneSchnittlinien auf der Oberfläche der Operanden.

3.2 Zusammenfassen planarer Dreiecke

3.2.1 Besonderheiten von triangulierten Körpern

Alle Methoden, die Laidlaw [LTH86] für polygonale Objekte entwickelthat, sind prinzipiell auch für Dreiecke zutreffend. Schließlich ist ein Dreieck

3in der Praxis entspricht sie der Ausgabe der Kollisionserkennung4welcher in diesem Zustand noch degeneriert ist


(A) Ausgangssituationder Dreiecke

(B) lokale Triangulierung (C) Triangulierungdes Polygons

Abbildung 3.2: Möglichkeiten der Triangulierung

”nur“ ein Spezialfall eines Polygons. So besteht die Teilung der Oberfläche im

einfachsten Fall darin, die Dreiecke mit den Algorithmen von Laidlaw an derSchnittkante zu teilen. Da die Ausgabegeometrie wieder nur aus Dreieckenbestehen soll, müssen die resultierenden Polygone noch trianguliert werden.

Dieses einfache Vorgehen stellt jedoch eine große Schwachstelle in derBehandlung triangulierter Objekte dar. Durch die ausschließlich lokale Be-trachtung und Teilung der einzelnen Dreiecke entstehen viele überflüssigeDreiecke. Überall da, wo Dreiecke eine planare Oberfläche bilden und diesegeteilt wird, entstehen Dreiecke, die nichts zu der Form der Oberfläche bei-tragen. Besser wäre es, diese in wenige, größere Dreiecke zusammenzufassen.

Diese Einsicht und deren Lösung bilden den Hauptaspekt von HubbardsArbeit [Hub90]. Die Problematik soll anhand eines Beispiels verdeutlichtwerden. Gegeben sei eine Gruppe zusammenhängender Dreiecke, die in ei-ner Ebene liegen. Abbildung 3.2 (A) zeigt ein solches Dreiecksnetz als Aus-schnitt der Oberfläche eines Körpers. Dieses wird von einem anderen Körpergeschnitten. Dabei symbolisiert die gestrichelte Linie die Schnittkanten derDreiecke. Abbildung 3.2 (B) zeigt eine mögliche Triangulierung, wenn jedesder Dreiecke einzeln (lokal) geteilt wird. Da die Dreiecke koplanar zueinandersind, beschreibt jedoch die Triangulierung aus Abbildung 3.2 (C) die gleicheOberfläche, wie die lokale Triangulierung. Außerdem ist sie wie die lokaleTriangulierung an der Schnittlinie geteilt. Es fällt sofort auf, daß hier vielweniger Dreiecke gebraucht werden. In diesem Beispiel ergibt sich aus derlokalen Triangulierung eine Anzahl von 26 Dreiecken. Bei der Triangulierungaus Abbildung 3.2 (C) ergeben sich dagegen nur 13 Dreiecke. Abgesehen vonder Ersparnis einer Vielzahl von Dreiecken neigt die letzte Variante auch we-niger dazu, kleine Dreiecke zu produzieren. Wenige Dreiecke sorgen für mehrEffizienz und größere Dreiecke für mehr Stabilität und Robustheit bei denboolschen Operationen.

Natürlich ist der Ansatz aus Abbildung 3.2 (C) auf zusammenhängendeGruppen von Dreiecken (Dreieckscluster) beschränkt, die planar zueinan-


der sind. In realen Objekte finden sich sehr viele ebene Flächen, die nichteine Dreiecksform haben. Das einfachste Beispiel ist ein Quader, dessen 6Flächen durch 12 Dreiecke gebildet werden. Ist ein Operand bereits Ergeb-nis einer (früheren) boolschen Operation, so wurden seine Flächen an derSchnittkante bereits geteilt. Daraus resultieren an diesen Stellen auch Clu-ster von planaren Dreiecken. In all diesen Fällen können Dreiecke auf dieseWeise gespart werden.

Die Brisanz dieser Einsicht wird deutlich, wenn man beachtet, daß dieboolschen Operationen wiederholt auf einen Körper angewendet werden.Wenn jedoch eine Operation immer wieder an benachbarten Positionen aus-geführt wird, so werden in jedem Schritt eine Reihe von überflüssigen Drei-ecken produziert. Diese dienen jedoch als Eingabe zum nächsten Schritt undproduzieren ihrerseits überflüssige Dreiecke. So werden immer kleinere Drei-ecke erzeugt und die Anzahl der Dreiecke wird sehr schnell zu groß. Im Kon-text von CSG mit triangulierten Körpern ergibt sich das gleiche Problem.Mit jedem inneren Knoten, der im CSG-Baum berechnet wird, steigt dieAnzahl der unnötigen Dreiecke.

Bei genauerer Betrachtung ist für die große Anzahl von Dreiecken bei derlokalen Triangulierung folgende Ursache verantwortlich. Die Schnittlinien die-nen bei der Triangulierung als Constraints5. Werden die Dreiecke anhand derSchnittlinien einzeln neu trianguliert, so agieren die Dreieckskanten ebenfallsals Constraints. Durch diese zusätzliche Einschränkung werden mehr Drei-ecke erzeugt.

Wird hingegen der Dreieckscluster als ganzes Polygon aufgefaßt und neutrianguliert, so fungieren nur die Schnittlinien sowie die Außenkanten desPolygons als Constraints. Ziel ist es also, planare Dreieckscluster zu Polygo-nen zusammenzufassen, welche als Gesamtes neu trianguliert werden. Da beider Triangulierung die Schnittlinien berücksichtigt werden, entstehen andereDreiecke als die des Original-Dreiecksnetzes.

Die beschriebenen Polygone können auch Löcher haben. Löcher in denplanaren Dreiecksclustern entstehen z.B. dann, wenn kleine Körperteile auseiner umschließenden, ebenen Körperfläche herausstehen.

Zur Berücksichtungung der Dreieckscluster definiert Hubbard [Hub90]innere Merkmale und äußere Merkmale. Die letzteren sind Kanten und Punk-te der Objektoberfläche, die zur Form beitragen. Innere Merkmale sind Punk-te und Kanten, die aufgrund der Triangulierung eingefügt wurden und vonDreiecken umgeben sind, die planar zueinander sind. Vor der Triangulie-rung markiert Hubbard alle inneren Merkmale und löscht sie. Dazu isteine separate (nicht triviale) Berechnung erforderlich, welche für alle Kantenund Punkte bestimmt, ob sie innere oder äußere Merkmale sind. In seinenAusführungen fehlt außerdem eine Beschreibung, auf welche Weise die Drei-ecke zusammengefaßt (geclustert) werden. Daher wird hier ein neuer Algo-

5Beschränkungen, Einschränkung im Freiheitsgrad, siehe Abschnitt 3.3


rithmus entwurfen, der diese Aufgabe bewältigt.

3.2.2 Bildung von Facetten

Als Eingabe für die Zusammenfassung zu Polygonen dienen Dreiecke mit Li-nienzügen (den Schnittkanten). Die Ausgabe bildet ein Polygon, welches imFolgenden als Facette bezeichnet wird. Eine Facette ist eine ebene Fläche,welche als Begrenzung eine Reihe von geschlossenen Linienzügen enthält. Dieäußere Begrenzung wird gegen den Urzeigersinn festgelegt. Um Löcher dar-stellen zu können, sind zusätzliche Begrenzungslinienzüge erlaubt, welche imUrzeigersinn laufen. Aufgrund der Zwei–mannigfaltigkeit können und dürfensich Begrenzungslinienzüge nicht schneiden. Zusätzlich enthält eine FacetteInformationen über die Schnittlinien, die in ihrem Bereich verlaufen. Da dieSchnittlinien bei der Triangulierung als Constraints dienen, werden sie ausden Dreiecken übernommen, aus denen die Facette aufgebaut wird. Währenddie Begrenzungslinienzüge die Form der Facette definieren, sind die Schnittli-nien eine zusätzliche Information, die bei der Triangulierung verwendet wird.

Eine Facette wird aus allen Dreiecken erzeugt, die koplanar zueinanderliegen. Die Facette beschreibt also die äußere Begrenzung bzw. das Polygoneines koplanaren Dreiecksclusters. Hat ein Dreieck keine koplanaren Nach-barn, so bildet es allein eine Facette. Die Facette selbst enthält keine Infor-mationen darüber, aus welchen Dreiecken sie aufgebaut wurde. Sie enthältnur die Informationen, die für eine neue Triangulierung unter Berücksichti-gung der Schnittlinien nötig sind.

Der Algorithmus zur Erzeugung einer Facette geht von einem bestehen-den Begrenzungslinienzug aus. Die grundlegende Idee besteht darin, diesenLinienzug schrittweise zu erweitern, so daß die Facette wächst. Der Algorith-mus startet an einem beliebigen Segment des Begrenzungslinienzuges undanalysiert nacheinander alle folgenden Segmente der Facette. Dabei wird fürjedes Segment ermittelt, ob sein rechtes Nachbardreieck in die Facette aufge-nommen werden kann. Dies ist der Fall, wenn das Nachbardreieck koplanarzu der Facette ist und noch nicht in eine andere Facette aufgenommen wur-de. Erfüllt das Nachbardreieck diese Bedingungen, so werden seine Kanten indie Facette aufgenommen und das aktuelle Segment wird gelöscht. Danachfährt der Algorithmus fort, indem er die neu aufgenommenen Kanten undalle Nachfolger analysiert.

Im folgenden wird der Algorithmus anhand Abbildung 3.3 erläutert. Inder Abbildung ist ein Dreiecksnetz zu sehen, welches zu einer Facette zu-sammengefaßt wird. Die Facette ist dabei grau dargestellt. Ihre Begrenzungbesteht aus den dicken Linien.

Der Algorithmus beginnt, indem ein Dreieck gewählt wird, welches nochnicht in eine Facette aufgenommen wurde. In Abbildung 3.3 (A) ist dies Drei-eck fea. Aus diesem Dreieck wird eine Facette erzeugt, deren Begrenzungsli-


e

b

c

d

f

e

a

b

c

d

f

e

a

b

c

d

a

de

a

b

c

de

(A) (B) (C)

(F)(E)(D)

a

b

c

de

a

b

c

f

f

Abbildung 3.3: Schritte bei der Erzeugung von Facetten

nienzug bisher nur das Dreieck beschreibt. Nun betrachtet der Algorithmusnacheinander alle Kanten des Begrenzungslinienzuges und vergrößert dortdas Polygon, wenn möglich. Die erste Kante sei fe. An dieser Kante wirddas koplanare Dreieck fde gefunden, welches noch nicht in einer Facette in-tegriert wurde. Daher wird die Kante fe gelöscht und an deren Stelle dieKanten fd und de eingefügt (siehe Abbildung 3.3 (B)). Die nächste Kan-te ist nun fd. Hier wird wieder ein passendes Dreieck gefunden (fbd) undintegriert (siehe Abbildung 3.3 (C)).

Beim nächsten Schritt wird an Kante fb das Dreieck fab gefunden. BeimIntegrieren des Dreiecks in die Facette entstehen jedoch zwei degenerierteKanten af und fa. Wie in Abbildung 3.3 (D) zu sehen ist, bilden sie einen

”Spalt“ in der Facette und können gelöscht werden. Um diesen Fall zu er-

fassen, werden alle Punkte markiert, die bereits Teil der Facette sind. BeimSchritt von (C) zu (D) wird nun erkannt, daß Punkt a markiert und derVorgänger von f ist. Daher werden die Segmente af und fb gelöscht unddas Segment ab eingefügt (Abbildung 3.3 (E)). Zu beachten ist, daß f nunnicht mehr in der Facette auftaucht. Das nächste Segment ist nach dieserOperation ab. Hier wird kein Nachbardreieck gefunden, welches koplanar istund noch nicht in einer Facette aufgenommen wurde. Daher schreitet derAlgorithmus weiter zu Segment bd. Hier wird wieder ein passender Nachbargefunden (bcd) und eingefügt (Abbildung 3.3 (F)). Der Algorithmus läuftjetzt durch alle weiteren Kanten (bc, cd, de, ea), bis er am Startpunkt der


c

d

b

a

c

d

e

f

(A) Ausgangssituation

b

(B) Geteilte Begrenzung

a

Abbildung 3.4: Erzeugung von Löchern

Facette wieder angekommen ist. Damit gibt es keine weiteren Dreiecke, dieintegriert werden können und der Algorithmus endet.

3.2.3 Spezialfälle

Das Beispiel aus Abbildung 3.3 beschreibt die generelle Funktionsweise desAlgorithmus und ist relativ simpel gehalten. Um die Entstehung von Löchernerklären zu können, ist die Betrachtung einiger Spezialfälle nötig. Diese tretenimmer dann ein, wenn ein Nachbardreieck gefunden wurde, bei dem der

”ge-

genüberliegende“ Punkte bereits markiert ist. Im Beispiel von Abbildung 3.3trat bei der Integration von Dreieck bfa (Schritt (C) nach (D)) ein solcherFall ein. Besondere Beachtung finden also alle Fälle, bei denen während desWachstums der Facette zwei Segmente eines Begrenzungslinienzuges aufein-ander treffen.

Es kann dabei vorkommen, daß ein Begrenzungslinienzug geteilt wird.Dies ist speziell bei der Erzeugung von Löchern wichtig. Abbildung 3.4 (A)zeigt eine Situation, bei der die Facette bereits gewachsen ist. Die aktuelleKante sei ab.6 Sie besitzt ein Nachbardreieck afb (durch die graue gestrichelteLinie begrenzt), welches integriert werden soll. Die Eckpunkte e und b liegendabei an der selben Stelle. Die Pfeile geben die Laufrichtung des Begren-zungslinienzuges an. Bei der Integration von afb wird sowohl Segment ab alsauch ef gelöscht. Dafür wird Segment af eingefügt. Außerdem wird ein neuerBegrenzungslinienzug bcd erzeugt. Das Resultat ist in Abbildung 3.4 (B) zusehen. Nachdem die Teilung vollzogen ist, werden die beiden Linienzüge vomAlgorithmus gesondert weiter betrachtet. Da der neue Begrenzungslinienzugein Loch beschreibt, ist seine Laufrichtung im Uhrzeigersinn.

Wenn ein Loch entsteht, das nur Dreiecke enthält, die ebenfalls koplanarsind, so

”wächst es zu“. Abbildung 3.5 verdeutlicht diesen Schritt. Hier ist

in (A) ein Loch zu sehen, welches aus dem Linienzug cba besteht. Betrachtetwird Kante ba. Durch die Integration von Dreieck abc in die Facette schließt

6d.h. alle Kanten vor ab bis zum Startpunkt wurden bereits behandelt


ab

c

(A) Polygon mit Loch (B) Resultat

Abbildung 3.5: Löschen eines Linienzuges

sich das Loch. Daher kann der Begrenzungslinienzug cba gelöscht werden.Das Resultat ist in Abbildung 3.5 (B) zu sehen.

Für die gewählten Methoden ist es wichtig zu erkennen, daß sich zweiLinienzüge nicht mehr treffen können, sobald sie getrennt sind. Ein Drei-eck wird markiert bzw. gelöscht, wenn es in die Facette aufgenommen wird.Da aber ein Linienzug immer nur über adjazente Dreiecke wächst und zweiLinienzüge nach der Trennung disjunkt sind, können sie nicht wieder aufein-ander stoßen. Diese Eigenschaft ist wichtig, da hierdurch die Vereinigung vonLinienzügen entfällt.

Durch den beschriebenen Algorithmus werden Dreiecksnetze schnell undeffizient analysiert und koplanare Cluster zu Facetten zusammengefaßt. Dieentstehenden Begrenzungslinienzüge sind überschneidungsfrei.

Bei der Erzeugung der Facetten ist es wichtig, die Schnittlinien zu beach-ten. Wenn ein Dreieck in eine Facette integriert wird, so werden auch sei-ne Schnittlinien in die Facette aufgenommen. Dabei werden die Linienzügeentsprechend vereinigt, geschlossen oder verbunden. Das Verfahren verläuftanalog dem Einfügen der Schnittsegmente (siehe Abschnitt 3.1.2). Nachdemdie Facette aufgebaut wurde, enthält sie also zusammenhängende Linienzüge,die die Schnittlinie im Bereich der Facette widerspiegeln.

Wie bei der Behandlung der Schnittlinien in den Dreiecken (siehe Ab-schnitt 3.1.2) ist auch hier die Verwaltung der Schnittlinien–Enden wichtig,die auf einer Kante eines Begrenzungslinienzuges liegen. Wenn bei der Fa-cettenerzeugung kein passendes Nachbardreieck gefunden wird, werden dieSchnittlinienenden der betreffenden Kante in den Begrenzungslinienzug ein-gefügt. Somit enthalten die Begrenzungslinienzüge neben ihren Eckpunktenzusätzlich auch Seitenpunkte. Das sind die Punkte, an denen eine Schnittli-nie die Facette verläßt. Im allgemeinen liegen die Seitenpunkte zwischen zweiEckpunkten, so daß diese drei Punkte kollinear sind. Wie in Abschnitt 3.3.4noch weiter erläutert wird, sind die Seitenpunkte wichtig für die Triangulie-rung der Facette.


(B) innere Punkte

��

��

��

��

��

a

b

c

d

e(A) Situation in 3D

ab

cd

e

��

Abbildung 3.6: Löschen von inneren Punkten

3.2.4 Beseitigung der inneren Merkmale

Durch die Vereinigung der Schnittlinien wurden Punkte in die Linienzügeaufgenommen, die für die Triangulierung nicht relevant sind und nach Hub-bards Terminologie zu den

”inneren“ Merkmalen gehören. Abbildung 3.6

(A) zeigt eine Situation, in der sich zwei Dreiecks-Netze schneiden. Das ei-ne Netz besteht aus zwei Dreiecken (dick) und wird von einem Netz mitdrei Dreiecken geschnitten. Von den beiden Netzen bilden jeweils zwei Drei-ecke koplanare Cluster. Die Schnittlinie ist gestrichelt angedeutet. In Abbil-dung 3.6 (B) ist die Facette dargestellt, die aus dem ersten Cluster entsteht.Der Schnittlinienabschnitt abc kommt aus dem einen Dreieck, während derAbschnitt cde aus dem anderen in die Facette aufgenommen wurde. Bei derErstellung der Facette wurden die beiden Abschnitte vereinigt. Da a, b, cund d kollinear sind, sind b und c innere Merkmale (siehe Abschnitt 3.2.1).Um diese zu beseitigen, werden nach der Facettenerstellung alle Schnittlini-ensegmente auf Kollinearität getestet und entsprechend gelöscht. Dabei mußbeachtet werden, daß die Punkte, die dabei gelöscht werden, nicht auf demBegrenzungslinienzug liegen. Abbildung 3.7 zeigt einen Fall, bei dem dies vonBedeutung ist. Hier bilden die Punkte a, b und c zwei Schnittsegmente, diekollinear sind und nicht vereinigt werden können, da Punkt b wichtig für dieForm des Körpers ist.

Überflüssige Punkte, die auf dem Begrenzungslinienzug liegen, könnendaher in dieser Phase der boolschen Operationen nicht beseitigt werden. Umdennoch ein kompaktes Ergebnis zu erzeugen, werden nach der Berechnungdes Ergebniskörpers alle Kanten überprüft, an denen Facetten enden. Wenndiese nicht zur Form des Körpers beitragen, wird hier ein

”Edge-Collapse“

vorgenommen. Dabei werden die Punkte der überflüssigen Kante vereinigtund die beiden adjazenten Dreiecke gelöscht.

3.3. TRIANGULIERUNG 37

��

��

Documents

Boolsche Operationen fur triangulierte K orp ergermer/publications/studienarbeit.pdf · Constructive Solid Geometry (CSG) ist eine Technik der Computergraphik, die komplexe Objekte