Effiziente Oberflächenberechnung von komplexen CSG-Bäumencg/Studienarbeiten/SA-Woessner.pdf ·...

EffizienteOberflächenberechnung vonkomplexen CSG-Bäumen

Studienarbeit

Vorgelegt von

Ralph Wössner

Institut für ComputervisualistikArbeitsgruppe Computergraphik

Betreuer: Dipl.-Inform. Jan OhlenburgPrüfer: Prof. Dr.-Ing. Stefan Müller

Dezember 2005

Inhaltsverzeichnis

1 Einführung 1

2 Grundlagen 1

2.1 Constructive Solid Geometry . . . . . . . . . . . . . . . . . . 12.2 Boundary Representation . . . . . . . . . . . . . . . . . . . . 22.3 CSG und B-Rep . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Realisation 5

3.1 Prototyp-Entwicklung . . . . . . . . . . . . . . . . . . . . . . 53.1.1 Schnitt der Dreiecke und Unterteilung . . . . . . . . . 63.1.2 Punkt-in-Polyeder-Tests . . . . . . . . . . . . . . . . . 83.1.3 Mengenzugehörigkeitsklassifizierung . . . . . . . . . . 113.1.4 Zwischenbilanz . . . . . . . . . . . . . . . . . . . . . . 12

3.2 Weiterentwicklungen . . . . . . . . . . . . . . . . . . . . . . . 133.2.1 Koplanarität . . . . . . . . . . . . . . . . . . . . . . . 133.2.2 Gleitkomma-Ungenauigkeiten . . . . . . . . . . . . . . 183.2.3 Optimierung . . . . . . . . . . . . . . . . . . . . . . . 19

4 Ergebnisse und Tests 24

4.1 Experimente . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.2 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Fazit und Ausblick 29

i

Abbildungsverzeichnis

1 CSG-Baum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Inkorrektes R-Set . . . . . . . . . . . . . . . . . . . . . . . . . 33 CSG-Operatorenvergleich . . . . . . . . . . . . . . . . . . . . 44 Schnitt zwischen zwei Dreiecken . . . . . . . . . . . . . . . . . 75 Singularitäten beim Crossings Test . . . . . . . . . . . . . . . 86 Kantenkollision in 3D . . . . . . . . . . . . . . . . . . . . . . 97 Zwischenergebnis . . . . . . . . . . . . . . . . . . . . . . . . . 128 Vergrößerung: Loch in der Oberfläche . . . . . . . . . . . . . 139 Koplanarität: Ausgangszustand . . . . . . . . . . . . . . . . . 1410 Koplanarität: Ergebnis einfacher Operator . . . . . . . . . . . 1411 Koplanarität: Ergebnis als Wireframe . . . . . . . . . . . . . 1512 Koplanarität: Verbessertes Ergebnis . . . . . . . . . . . . . . 1513 Koplanarität: Verbessertes Ergebnis, Wireframe . . . . . . . . 1614 Koplanarität: Fertiges Ergebnis . . . . . . . . . . . . . . . . . 1615 Koplanarität: Fertiges Ergebnis, Wireframe . . . . . . . . . . 1716 Vergleich von Octree und Loose Octree . . . . . . . . . . . . . 2217 Polygonaufteilung im Octree . . . . . . . . . . . . . . . . . . 2418 Polygonaufteilung im Loose Octree, 10% . . . . . . . . . . . . 2519 Polygonaufteilung im Loose Octree, 30% . . . . . . . . . . . . 2520 Diagramm: Polygonverteilung im Loose Octree . . . . . . . . 2521 Diagramm: Mittlere Hierarchietiefe . . . . . . . . . . . . . . . 2622 Diagramm: Berechnungszeiten 0–100% . . . . . . . . . . . . . 2723 Diagramm: Berechnungszeiten 10–55% . . . . . . . . . . . . . 2724 Logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2825 Logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2926 Tori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3027 Kuh-Kugel-Differenz . . . . . . . . . . . . . . . . . . . . . . . 3028 Kuh-Kugel-Differenz . . . . . . . . . . . . . . . . . . . . . . . 31

ii

1 Einführung

Constructive Solid Geometry (CSG) ist eine Technik, die beim Modellie-ren von Körpern verwendet wird. Hierbei werden Körper, meist geometri-sche Primitive, durch boolesche Operatoren verknüpft. Durch die geschickteKombination von mehreren Körpern können dabei komplexe Körper model-liert werden. CSG findet Verwendung bei der Modellierung von Körpern,beim CAD sowie in der Simulation von Fertigungstechniken.

2 Grundlagen

2.1 Constructive Solid Geometry

Für CSG [FvDFH96] beschränkt man sich auf die Operationen Schnittmen-ge, Vereinigungsmenge und Differenz, da sich alle anderen booleschen Ope-rationen von ihnen ableiten lassen. Die drei Operationen lassen sich intuitivbenutzen, da sie Techniken aus dem realen Leben und aus der industriellenFertigung entsprechen.

So steht die Schnittmenge für das Ausschneiden oder Ausstanzen dergewünschten Form, die Vereinigungsmenge entspricht dem Auftragen vonMaterial oder dem Anfügen eines weiteren Körpers und die Differenz ent-spricht dem Entfernen oder Abtragen des Werkstoffes, z. B. durch Bohrenoder Fräsen. Ein solcher Operator wird auf zwei Körper angewendet, das Er-gebnis kann beliebig für weitere CSG-Operationen weiterverwendet werden.Komplexere Körper können durch die Kombination beliebig vieler Körperund Operatoren entstehen. Diese Körper und Operatoren bilden einen bi-nären CSG-Baum. Jeder Knoten des Baumes besitzt zwei Kinder, bei denenes sich um Blätter oder wiederum um Knoten handeln kann. Die Blätterdes Baumes bestehen aus den verwendeten Körpern, die Knoten stellen dieCSG-Operatoren bzw. aus vorhergehenden Operationen entstandene Körperdar. Einen binären Baum für CSG zu verwenden stellt keine Einschränkungdar, da jeder beliebige boolesche Ausdruck auch in eine binäre Schreibweisegebracht werden kann und damit auch in einem binären Baum ausgedrücktwerden kann, wie z. B. A ∩ B ∩ C, das (A ∩ B) ∩ C entspricht, siehedazu auch [SLJ98].

Zur Darstellung von CSG-Bäumen gibt es verschiedene Verfahren. Sollder Baum (oder der resultierende Körper) gerendert werden, gibt es einenAnsatz über einen erweiterten Z-Buffer, siehe [SLJ98] [OM05]. Dieser Ansatzbenötigt einen permanenten, höheren Aufwand zur Darstellung als die An-zeige eines einfachen Körpers und erzeugt selbst keine neue Geometrie. Die-ses Verfahren ermöglicht, dynamische CSG-Bäume, liefert bei komplexeren

1

Bäumen aber keine zufriedenstellenden Frameraten und ist daher nur be-schränkt für Interaktion geeignet.

Wird der aus einem CSG-Baum resultierende Körper berechnet, kanndieser flüssig dargestellt werden, da dies von gängiger Grafikhardware bes-ser unterstützt wird und eignet sich dadurch sowohl für interaktive Anwen-dungen also auch für andere rechenintensive Simulationen, wie z.B. der Be-rechnung von Schatten oder Kollisionsdetektionen. Der Körper kann zudembeliebig weiterbearbeitet und weiterverwendet werden, z. B. zur Modellie-rung.

Abbildung 1: CSG-Baum, Bildquelle: Stewart et a. [SLJ98]

2.2 Boundary Representation

Boundary Representation (B-Rep) [FvDFH96] bedeutet, dass Körper nurdurch ihre Oberfläche repräsentiert werden, d. h. durch eine Menge vonPunkten, Kanten und Polygonen. Bei nicht-planaren Oberflächen stellt dieB-Rep immer ein Approximierung der Oberfläche dar, die mit steigenderPolygonzahl zwar an Genauigkeit gewinnt, aber sich der wirklichen Formdes Körpers nur annähern und sie nur stellenweise erreichen kann.Welche Seite der Polygone der B-Rep nach außen, also vom dargestelltenKörper weg zeigt, wird durch die Angabe von Normalen bestimmt.

Im Gegensatz zu B-Rep steht die parametrische Darstellung, wie sie oftbeim Raytracing Verwendung findet. Dabei werden von einem Körper alle

2

nötigen Parameter gespeichert, bei einer Kugel zum Beispiel Position undRadius. Boundary Representations finden in der Computergrafik dort Ver-wendung, wo Objekte durch Rendern visualisiert werden, da gängige Gra-fikhardware für diese Darstellung optimiert ist. Auch bei Grafikformaten,die von außen auf Parametern zu basieren scheinen, wird intern oft mit B-Reps gearbeitet. So werden z. B. die Primitive in VRML in Parameterformbeschrieben, intern werden sie aber trianguliert und als B-Rep dargestellt.

2.3 CSG und B-Rep

Die ersten umfassenden Studien zu CSG und B-Rep stammen von Requi-cha und Voelcker [RV85]. Darin wird festgestellt, dass für CSG spezielleEinschränkungen bezüglich der verwendeten Körper und Operatoren nötigsind.

Ist ein Körper zum Beispiel nicht komplett geschlossen, so ist es nichtmöglich, eindeutig zu ermitteln, ob ein beliebiger Punkt innerhalb oder au-ßerhalb des Körpers liegt, da es keine abgeschlossene Grenze zwischen

”in-

nen“ und”außen“ gibt. Requicha hat daher [Req80] regularized sets (R-Sets)

definiert.R-Sets nehmen eine endliche Menge Raum ein, sind geschlossen und von

jedem beliebigen Punkt kann eindeutig bestimmt werden, ob sich dieserinnerhalb, außerhalb oder auf der Oberfläche der R-Sets befindet. Als Nega-tivbeispiel wird ein Würfel genannt, der zwar über eine geschlossene B-Repverfügt, allerdings eine im Raum stehende Fläche (dangling face) und eineebenso allein stehende Kante (dangling edge) besitzt, siehe Abb. 2.

Abbildung 2: Inkorrektes R-Set, Bildquelle: Requicha [Req80]

Werden normale boolesche Operatoren auf diese R-Sets angewendet,kann es – vor allem, wenn die beiden Körper überlappende, zueinander ko-planare Flächen haben – zu Artefakten kommen. Requicha et al. haben

3

deswegen die regularisierten Operatoren ∩*, ∪* und −* definiert, die, wennsie auf R-Sets angewendet werden, wieder R-Sets liefern. Der Unterschiedder Operatoren wird in am Beispiel der Vereinigung in Abb. 3 veranschau-licht. Der Einfachheit halber wird im Weiteren ∩, ∪ und − synonym für dieregularisierten Operatoren verwendet.

Abbildung 3: Die theoretische Vereinigungsmenge der Körper A und B (a) ergibtkeinen korrekten Körper, da das Resultat eine Fläche zu viel enthält (b). Rechtsdas Ergebnis eines regularisierten Operators (c). Bildquelle: Requicha et al. [RV85]

Sollen B-Reps der R-Set-Definition entsprechen, müssen sie geschlossensein, d. h. zu jeder Kante des Körpers müssen mindestens zwei Flächengehören. Außerdem muss für jedes der Polygone gelten, dass Vorder- undRückseite nicht gleichzeitig innerhalb oder außerhalb des Körpers liegen.Dies ist der Fall, wenn einer Kante mehr als zwei Polygone zugeordnet wer-den. Im Folgenden wird daher von Körpern ausgegangen, deren Kanten zugenau zwei Polygonen gehören (im Englischen 2-manifolds).

4

3 Realisation

Die Grundidee hinter CSG ist einfach. Will man z. B. die Differenz zweierKörper A − B bilden, so wird von A alles subtrahiert, was Teil von B ist.Arbeitet man mit den Oberflächen von Körpern kommt hinzu, dass man füreine Differenz A − B auch einen Teil der Oberfläche von B braucht, fallssich die beiden Körper überschneiden, sonst würde man einen Körper miteiner nicht geschlossenen Oberfläche erhalten. D. h. von A werden alle Teilesubtrahiert, die sich innerhalb von B befinden und zusätzlich werden zuA alle Teile von B addiert, die innerhalb von A sind. Für Schnittmengenwerden alle Teile von A, die sich in B und alle Teile von B, die Teil vonA sind zu einem neuen Körper kombiniert. Vereinigungsmengen werden ausdem Komplement der Schnittmenge gebildet.

Da die Oberflächen aus Polygonen bestehen und sie sich mit den Ober-flächen beliebiger Körper schneiden, ist nicht davon auszugehen, dass allebeteiligten Polygone komplett innerhalb oder außerhalb des anderen Kör-pers liegen. Um dies zu ändern, müssen die Polygone der beiden Körpermit den Polygonen des jeweils anderen Körpers geschnitten und unterteiltwerden.

Sind die Oberflächen unterteilt, kann getestet werden, zu welcher Mengeein Polygon gehört und je nach Operator können die Polygone zu einemneuen Körper zusammengefügt werden.

3.1 Prototyp-Entwicklung

Zur Realisierung wird ein Prototyp implementiert, da sich dabei Lösungs-ansätze schnell evaluieren lassen.Damit der Prototyp einen kompletten CSG-Baum in eine fertige B-Rep um-wandeln kann, genügt es, die einzelnen Operatoren jeweils für zwei beliebigeKörper zu implementieren, da dies ausreicht, um den kompletten Baum ab-arbeiten zu können.

Der Ablauf zur Erzeugung eines neuen Körpers ist folgender: Zuerst wer-den alle Dreiecke der beiden Körper miteinander geschnitten. Danach wirdüberprüft, welche der Dreiecke für die Oberfläche des neuen Körpers benö-tigt werden.

Ziel der Unterteilung ist es, die Polygone der beiden B-Reps soweit zuunterteilen, dass es zu keiner Kollision zweier Dreiecke mehr kommen kann.Die Polygone der beiden Körper dürfen sich danach nicht nur nicht mehrdurchdringen, sondern sich nur noch an ihren Kanten gegenseitig berühren.Dazu werden die Dreiecke beider Körper auf Überschneidung getestet undgegebenfalls in mehrere Dreiecke unterteilt. Ist dies gewährleistet, werdenalle Dreiecke dahin gehend überprüft, ob sie ein Teil der Oberfläche des

5

gewünschten Körpers darstellen. Dazu muss festgestellt werden, zu welcherMenge jedes einzelne Polygon gehört. Flächen, die nicht Teil der gewünschtenErgebnismenge sind, können gelöscht werden. Um diesen Test durchführenzu können, wird eine Funktion benötigt, die ermitteln kann, ob ein beliebigerPunkt innerhalb oder außerhalb eines Körpers liegt.

Für ein minimales System sind dabei folgende Funktionen nötig:

• Schnitt der Dreiecke und Unterteilung: subdivideCollidingFaces()

• Punkt-in-Polyeder-Tests: isInside()

• Mengenzugehörigkeitsklassifizierung: classifyAndDelete()

Diese Funktionen werden im Folgenden besprochen, ab Abschnitt 3.2 wirdauf Verbesserungen, Optimierung und Weiterentwicklungen eingegangen.

Die Umsetzung ist auf triangulierte Körper beschränkt, die die Anfor-derung an R-Sets erfüllen. Die Einschränkung auf triangulierte Körper be-gründet sich dadurch, dass Polygone spätestens in Dreiecke unterteilt werdenmüssen, wenn sie gerendert werden sollen, außerdem erleichtert dies die Im-plementierung. Die Anforderungen an R-Sets müssen die Körper erfüllen, daeine CSG-B-Rep-Implementierung laut Requicha nur so korrekte Ergebnisseliefern kann.

Die Realisierung erfolgt in C++ mit dem Visual Studio .NET 7.1 vonMicrosoft und soll in das AR/VR-Framework Morgan [OHL+04] der Ar-beitsgruppe CVAE des Fraunhofer Institutes für Angewandte Informations-technik FIT eingebaut werden. Zur Visualisierung der Ergebnisse wird derMorgan-Viewer verwendet.

3.1.1 Schnitt der Dreiecke und Unterteilung

Für den Schnitt der Dreiecke wurde eine modifizierte Version des Algorith-mus von Tomas Möller [Mol97] verwendet.

Der Algorithmus berechnet die Ebenen, die von den beiden Dreieckenaufgespannt werden und die Distanzen der Eckpunkte zur jeweils anderenEbene. Sind alle Distanzen gleich Null, so sind die beiden Polygone koplanar.Für diesen Fall werden die Dreiecke auf eine achsenparallele Ebene projiziertund in 2D auf Überschneidung überprüft.

Für den nicht-koplanaren Fall werden die Distanzen einem weiteren Testunterzogen. Verfügen alle Werte eines Polygons über dasselbe Vorzeichenund sind ungleich Null, so kann ausgeschlossen werden, dass es zu einemSchnitt kommt.

Andernfalls wird die Schnittgerade der beiden Ebenen und die Schnitt-punkte der Geraden mit den beiden Dreiecken berechnet. Aufgrund der Tests

6

ist zu diesem Zeitpunkt klar, dass die Dreiecke sich mit einer Geraden schnei-den. Ob wiederum die beiden Dreiecke sich miteinander schneiden, hängtnun davon ab, ob die Intervalle sich überlappen (sh. Abb. 4). Ist dies derFall, so werden die beiden mittleren der vier Punkte auf der Geraden alsAnfangs- und Endpunkt der Überschneidung zurückgegeben, diese beschrei-ben die Schnittgerade der Dreiecke.

Abbildung 4: Jeweils zwei Dreiecke mit den durch sie aufgespannten Ebenen undder Schnittgerade der beiden Ebenen. Die Schnitt-Intervalle zwischen Dreieckenund Ebenen sind grau markiert. die beiden Dreiecke links überschneiden sich imGegensatz zu den beiden Dreiecken rechts, da die beiden Intervalle sich überlappen.Bildquelle: [Mol97]

Der Algorithmus von Möller wurde dahingehend verändert, dass ein Teilder Schnittpunktberechnungen eingespart wurde und statt der Koordina-ten der beiden Ergebnispunkte die Eckpunkt-Ebenen-Distanzen sowie zweiSchnitt-Flags zurückgegeben werden. Die Distanzen sind nötig, da sich mitihrer Hilfe bei einer nötigen Unterteilung die Vertex-Informationen leich-ter interpolieren lassen. Aus den reinen Koordinaten der Eckpunkte ist diesaufwändiger und anfälliger für Fehler. Um Fehler bei den Gleitkommabe-rechnungen der Distanzen zu minimieren, wurde hier ein Schwellwert ver-wendet. Für Eckpunkte mit einem kleineren Abstand zur Ebene als Epsilon,wird eine Distanz von Null zurückgegeben. Die Wahl dieses Schwellwerts istallerdings nicht unproblematisch, dazu mehr in Abschnitt 3.2.2.

Die beiden Schnitt-Flags geben an, welche der beiden Polygone unterteiltwerden müssen. Sie sind nicht nur im Falle einer gegenseitigen Durchdrin-gung

”true“, sondern auch wenn eines der Polygone mit mehr als einem

Eckpunkt auf dem anderen”steht“. Dies ist wichtig, um jedes Dreieck mit

einem einzigen Test klassifizieren zu können und später nicht mehr unter-teilen zu müssen. Nicht gesetzt werden die Flags, wenn die beiden Dreieckezueinander koplanar sind. Koplanare Flächen müssen sich nicht gegenseitig

7

unterteilen, da sie bereits von den nicht-koplanaren Nachbarn der koplanarenFläche gegenseitig unterteilt werden können.

Ist eines der Schnitt-Flags gesetzt, dann werden die entsprechenden Di-stanzen übergeben und die Produkte von je zwei der Distanzwerte werdenausgewertet, um die nötige Unterteilung festzustellen. Im Normalfall wirdhier ein Dreieck (das

”Vater“-Dreieck) in drei Dreiecke (

”Kind“-Dreiecke)

unterteilt. Kommt es allerdings zu einem”Vertex-Treffer“, so wird das be-

stehende in zwei Kind-Dreiecke gespalten.Andere Vertex-Informationen der Dreiecke wie Normalen, Texturkoordi-

naten oder andere Materialeigenschaften können an dieser Stelle ebenfallsinterpoliert werden. Die neu entstandenen Dreiecke werden auch auf Über-schneidung getestet und gegebenenfalls unterteilt.

In der Implementierung werden alle Dreiecke in einem Vector-Objektder Standard Template Library gespeichert. Auf Kollision getestet wird inzwei verschachtelten Schleifen, die jeweils durch die Flächen der beiden Kör-per iterieren. Im Falle einer nötigen Unterteilung bleibt das

”Vater-“Dreieck

erhalten, wird aber verkleinert und bekommt mindestens einen neuen Eck-punkt zugewiesen. Die neu erzeugten

”Kind-“Dreiecke werden am Ende das

Vector-Objekts eingefügt. Um sicherzustellen, dass alle Kollisionen festge-stellt werden, muss jedes Dreieck (oder dessen Vater) mit jeder Fläche desanderen Körpers getestet werden.

Geht man von zwei Körpern mit m und n Polygonen aus, sind also m×nTests nötig, falls es zu keiner Unterteilung kommt. Im Falle von Kollisionensteigt der Aufwand durch die steigende Anzahl von Flächen entsprechendan.

3.1.2 Punkt-in-Polyeder-Tests

Nach der Unterteilung der Polygone der beiden Körper muss festgestelltwerden, welche der Dreiecke noch Teil der Oberfläche sind. Dafür reicht esaus, einen Punkt des Dreiecks, wie z. B. den Schwerpunkt, zu untersuchen.Im Gegensatz zur parametrischen Repräsentationen von Körpern ist dies beiB-Reps aber nicht ganz trivial, da hier alle Polygone des Körpers berück-sichtigt werden müssen.

Abbildung 5: Drei Strahlen mit jeweils zwei Kollisionen (siehe Text)

8

Die Problematik wird in diversen Aufsätzen sowohl in 2D als auch in3D behandelt. Von den verschiedenen Ansätzen ist laut [Hai94] der Cros-sings Test eine gute Möglichkeit: Um einen Punkt zu testen, wird ein Strahlvon diesem Punkt in eine beliebige Richtung geschickt und die Anzahl derKollisionen mit dem Körper gezählt, wobei zum Strahl parallele Flächenignoriert werden. Kommt es zu einer geraden Anzahl von Kollisionen, sobefindet sich der Punkt außerhalb des Körpers, andernfalls befindet sich derPunkt innerhalb. Meistens wird der Strahl parallel zur X-Achse ausgesendet.

Dieser Test funktioniert sehr gut, so lange keine Kanten oder Eckpunktegetroffen werden, da es sonst zu Singularitäten kommen kann. Im Falle voneinem Kantentreffer trifft der Strahl die Kanten von zwei Dreiecken, waszwei Kollisionen ergibt. Nach zwei Kantentreffern kann sich der Status desStrahls (innen oder außen) ändern, muss er aber nicht. Bei einem solchenFall lässt sich also nicht aus der Anzahl der Kollisionen auf ein Ergebnisschließen. Geht man also von einem Punkt innerhalb des Körpers aus, so istnicht sicher, ob der Strahl nach der Kollisionen mit zwei Kanten den Kör-per verlassen hat, oder nicht. Drei Strahlen mit jeweils zwei Treffern aberunterschiedlichem gewünschten Ergebnis sind in Abb. 5 zu sehen. Die dreiStrahlen testen einen Körper, der aufgeschnitten dargestellt ist. Der obereund der unter Strahl kollidieren zweimal mit dem Körper, da sie die Kantenzweier Polygone treffen. Im Falle von Vertex-Treffern verhält sich die Sacheähnlich, mit dem Unterschied, dass es hier zu einer beliebigen Anzahl vonTreffern pro Problemstelle kommen kann, da jedes an den Vertex angren-zende Dreieck getroffen wird.

Abbildung 6: Kantenkollision in 3D, Bildquelle: Requicha et al. [RV85]

Haines schlägt zur Vermeidung von Singularitäten vor, bei einer Kollisi-on mit einer Kante oder einem Vertex den Strahl um ein klein zu wählendes

9

Epsilon zu verschieben. Das Ziel dabei ist, dass aus mehreren nicht aussage-kräftigen Treffern an einer Problemstelle eine möglichst geringere Zahl vonaussagekräftigen Treffern entsteht.

Dies wäre ohne Weiteres möglich, solange gewährleistet ist, dass dieFunktion den Strahl bei allen zusammengehörenden Kollisionen um die glei-che Distanz in die gleiche Richtung verschiebt, da es nur so zu einem aussage-kräftigen Ergebnis kommen. Dies funktioniert für Point-in-Polygon-Problemein zwei Dimensionen recht gut, in 3D wird dies komplizierter.

Würde der Strahl z. B. an einer Stelle, an der er den Körper verlassensoll, die Kanten zweier benachbarter Polygone treffen und der Strahl würdein den beiden Fällen auf verschiedene Ersatzkoordinaten abgebildet werden,so kann die Anzahl der resultierenden Kollisionen zwischen Null und Zweiliegen. Null für den Fall, dass der Strahl aus Versehen neben die Polygonegeschoben wird, eine Kollision mit dem Inneren eines der Dreiecke im erhoff-ten Fall und zwei Treffer, falls der Strahl wieder auf die Kanten der beidenPolygone abgebildet wird. Um den ersten Fall zu verhindern, sind Informa-tionen über die benachbarten Polygone nötig oder ein erneuter Test über allePolygone, was den Berechnungsaufwand erhöht. Dass der Strahl wieder aufandere Kanten abgebildet wird, lässt sich nicht ohne Weites allgemeingültigverhindern, da es recht viele Möglichkeiten gibt, wie die Polygone im Raumangeordnet sein können und es zum Großteil der Lösungsansätze Fälle gibt,für die das Verfahren versagt.

Linhart beschäftigt sich in [Lin90] mit der gleichen Problematik undschlägt vor, die Kollisionen des Strahls gewichtet zu zählen. Tritt der Strahlbei einer Kollision in einen Körper ein, berechnet er −1 und +1, falls dieserihn verlässt. Für Kantentreffer berechnet er entsprechend ± 1

2.

Für den Fall eines Vertex-Treffers arbeitet Linhart mit einer Normalenpro-jektion in Richtung des Strahls und den Winkeln zwischen den beteiligtenPolygonen. Die Werte werden dabei nach den inneren Winkeln der projizier-ten Dreiecke gewichtet.Aus der Summe dieser Werte kann am Schluss auf den Punkt geschlossenwerden. Sie kann nur Null sein, wenn der Punkt außerhalb des Körpers liegt.

Für die Berechnung der Strahl-Dreieck-Kollisionen wird [MT97] verwen-det und leicht modifiziert. Er berechnet die vom Dreieck aufgespannte Ebeneund ermittelt den Schnittpunkt einer Geraden mit dieser Ebene. Über ba-ryzentrische Koordinaten wird daraufhin überprüft, ob der Punkt innerhalbdes Dreiecks liegt.Der Algorithmus wird um einige Tests erweitert, um direkt überprüfen zukönnen, ob eine Kante oder ein Eckpunkt getroffen wird, außerdem wird dieImplementierung abgeändert, um nur den Schnitt mit einem Strahl (stattdes Schnitts mit einer Geraden) zu berechnen.

10

In einigen Versuchen stellt sich heraus, dass der Ansatz von Linhart gutgeeignet ist, allerdings kann es zu Fehlern kommen, weil durch Ungenauig-keiten bei Gleitkommaberechnungen nicht garantiert werden kann, dass imFalle eines Vertex-Treffers wirklich alle Polygone als Vertex-Kollisionen er-kannt wurden. Der Algorithmus kann allerdings nur in diesem Fall zu einemkorrekten Ergebnis kommen.

Eine gute und stabile Lösung stellt die Kombination beider Ansätze dar.Für normale Treffer und Kantenkollisionen wird so verfahren, wie von Lin-hart vorgeschlagen, bei Vertex-Treffern wird der Strahl wie bei Haines leichtverschoben. Bei erneuten Treffern wird dem Strahl spiralförmig eine neuePositionen zugewiesen bis keine Eckpunkte mehr getroffen werden.

Die Probleme mit dem Verschieben des Strahls machen sich hier nur nochtheoretisch bemerkbar, da der Algorithmus mit Kantentreffern adäquat um-zugehen vermag. Der Fall, hier nicht nach wenigen Verschiebungsschritten zueinem Ergebnis ohne Eckpunkttreffer zu kommen, dürfte wohl nur in Test-szenarien auftreten, die unter Kenntnis des Algorithmus konstruiert wurden.Im Gegensatz zu Linhart kann hier jetzt mit Integer-Werten gearbeitet wer-den, in dem man die Werte verdoppelt.

3.1.3 Mengenzugehörigkeitsklassifizierung

Um den fertigen Körper zu erhalten, muss nun überprüft werden, welche Po-lygone für die Boundary des neuen Körpers benötigt werden. Wendet mandie Operatoren auf die beiden Körper A und B an, so gilt:

• Für die Schnittmenge A ∩ Bwerden alle Flächen beider Körper benötigt, die jeweils im anderenKörper liegen.

• Für die Vereinigungsmenge A ∪ Bwerden die Flächen beider Körper verwendet, die sich außerhalb desanderen Körpers befinden.

• Für die Differenzmenge A - Bwerden von A alle außerhalb von B liegenden und von B alle in Aliegenden Polygone verwendet.Die Polygone von B müssen anschließend noch invertiert werden, dasheißt die Normale muss gespiegelt werden.

11

Alle anderen Flächen können gelöscht und die verbleibenden unter Be-rücksichtigung der verschiedenen Materialeigenschaften in einem neuen Kör-per zusammengefasst werden.

Realisiert werden die Tests und das Löschen der Flächen in einer Me-thode, die zwei Modi unterscheidet: Modus 0 löscht alle Polygone, die sichaußerhalb des anderen Körpers befinden, Modus 1 löscht alle Polygone in-nerhalb.Bei einer CSG-Operation wird die Methode für jeden der beiden Körper miteiner Kopie des anderen Körpers einmal aufgerufen, je nach Operator mitverschiedenen Modi. Für die Schnittmenge wird zweimal Modus 0 verwen-det, für die Vereinigungsmenge zweimal Modus 1, für die Differenz jeweilseinmal Modus 0 und 1.

3.1.4 Zwischenbilanz

Abbildung 7: Zwischenergebnis

Nach der Implementierung der bisher genannten Funktionen ist der Al-gorithmus prinzipiell funktionsfähig (sh. Abb. 7), allerdings kommt es zuFehlern, wenn sich koplanare Flächen überschneiden. Außerdem treten zumTeil aufgrund von Ungenauigkeiten bei Gleitkommaberechnungen kleine Lö-cher an den Schnittstellen der beiden Körper auf, siehe Abb. 8. Ein weiteresProblem sind die bei größeren Körpern benötigten Berechnungszeiten. Aufdie Gründe für die Fehler und mögliche Verbesserungen soll im Folgendeneingegangen werden.

12

Abbildung 8: Unter starker Vergrößerung: Ein Loch in der Oberfläche am Über-gang zwischen zwei Körpern

3.2 Weiterentwicklungen

3.2.1 Koplanarität

Die bis zu diesem Punkt implementierten Funktionen entsprechen den Nega-tivbeispielen aus [RV85] und stellen normale boolesche Operatoren dar, diebei auftretenden Koplanaritäten zu den beschriebenen Artefakten führen.Durch Ungenauigkeiten bei Gleitkommaoperationen sind diese Ergebnissezudem instabil und reagieren auf kleinste Änderungen mit dem Verschwin-den oder Wiederauftauchen von Polygonen.Die bisherigen Ergebnisse sind in Abb. 9 bis 11 zu sehen. Die Abbildungenzeigen dieselben vier Körper, aus je zweien von ihnen soll die Vereinigungs-menge gebildet werden.Bei koplanaren Flächen können nur zwei Fälle auftreten: Die beiden Ebenenhaben die gleiche Orientierung, das heißt sie haben identische Flächennor-malen oder die Flächennormalen zeigen in entgegengesetzte Richtungen.

Diese beiden Fälle sind dargestellt: Die beiden linken Körper liegen auf-einander und berühren sich gegenseitig mit ihren zueinander koplanarenFlächen, die Flächennormalen der beiden Flächen zeigen in die entgegen-gesetzte Richtung. Die beiden Körper rechts überschneiden sich gegenseitigund die Flächennormalen ihrer koplanaren Flächen sind identisch. In Bild 9wird der Ausgangszustand gezeigt, in Abb. 10 ist das Ergebnis der Ope-ration dargestellt, in Abb. 11 als Wireframe. Im zweiten Fall ist der Fehleroffensichtlich: Der neue Körper ist nicht geschlossen. Im ersten Fall hingegenwird der Fehler erst im Wireframe sichtbar: Eine Fläche bleibt zwischen denbeiden Körpern stehen, das Resultat ist damit kein R-Set mehr.

13

Abbildung 9: Koplanarität: Ausgangszustand

Abbildung 10: Zwei Vereinigungsmengen gebildet mit dem einfachen Test

Requicha et al. berücksichtigen für ihre regularisierten Operatoren Nach-barschaftsinformationen. Soll ein Punkt getestet werden, untersucht er, wiees in einem kugelförmigen Umfeld um den Punkt aussieht. Falls diese Kugelkomplett innerhalb oder komplett außerhalb des gewünschten Körpers liegt,so ist Punkt ebenfalls innerhalb oder außerhalb. Andernfalls ist der getestetePunkt ein Teil der Boundary und darf nicht gelöscht werden.

Umgesetzt wird dieser Ansatz, indem zwei von den Mittelpunkten ausleicht verschobene Punkte getestet werden. Die Richtung der Verschiebungs-richtung ist dabei die jeweils einmal die positive oder negative Flächennor-male des Dreiecks. Da jeweils in der Nähe der Mittelpunkte getestet wird,sind zwei mögliche Testpunkte zur Auswertung der Nachbarschaft ausrei-

14

Abbildung 11: Koplanarität: Ergebnis als Wireframe

chend. Die beiden neuen Tests können mit isInsideIn() und isInsideOut()durchgeführt werden.

Um die bisherigen Ergebnisse zu verbessern, werden die beide Modi wiefolgt verändert und ein zusätzlicher Modus hinzugefügt:

• Modus 0 löscht Polygone, wenn isInsideIn() == false

• Modus 1 löscht Polygone, wenn isInsideOut() == true

• Modus 2 löscht Polygone, wenn isInsideOut() == false

Der neue Modus 2 ist fast identisch mit Modus 0 und wird nur für dieDifferenzbildung verwendet. Er ließe sich zu diesem Zweck auch durch Mo-dus 0 ersetzen, dazu müsste aber der Körper vor der Operation invertiertwerden. Effizienter ist es, dies nach nach der Operation zu tun.

Abbildung 12: Verbesserter Test: Je zwei Vereinigungsmengen, Schnittmengenund Differenzen (eine Schnittmenge ist nicht sichtbar)

15

Abbildung 13: Wireframe

Abbildung 14: Fertiger Test: Je zwei Vereinigungsmengen, Schnittmengen undDifferenzen (eine Schnittmenge ist nicht sichtbar)

Durch die Anpassung der Tests kommt es zwar zu stabilen Ergebnissen,aber, wie in Abb. 12 und 13 zu sehen, immer noch zu Artefakten. Dieserühren daher, dass überlappende koplanaren Flächen beim Crossings Testdasselbe Ergebnis liefern, das heißt sie werden beide gelöscht oder bleibenbeide erhalten. In beide Fälle ist das Ergebnis fehlerhaft.

Eine gute Lösung stellt hier die Aufspaltung der bisherigen Modi miteiner kombinierten Auswertung der beiden zusätzlichen Testpunkte dar. Dieneuen Modi (11 und 12) testen die Umgebung der Polygone genauer undentsprechen in den Standardfällen Modi 0 und 1, bei Koplanarität weichtihr Verhalten jedoch ab, was dazu führt, dass z. B. beim Bilden der Ver-einigungsmenge verschiedene Ergebnisse für die koplanaren Flächen liefertwerden, wodurch nur noch eine der beiden Flächen gelöscht wird.Die CSG-Methoden verwenden nun

• Schnittmenge: 0 und 10,

• Vereinigungsmenge: 1 und 11,

• Differenzmenge: 2 und 11.

Das Verhalten der Methode in Abhängigkeit vom gewählten Modus undden Ergebnissen der Tests ist in Tabelle 1 dargestellt. Wie die Abbildun-gen 15 und 14 zeigen, entsprechen die Resultate dem zu erwartenden Ergebnis.

16

Modus isInsideIn() isInsideOut() Resultat

0 True -0 False Löschen

1 True Löschen1 False -

2 True -2 False Löschen

10 True True -10 True False Löschen10 False Löschen

11 True Löschen11 True False Löschen11 False False -

Tabelle 1: Verhalten der Methode classifyAndDelete()

Abbildung 15: Wireframe

17

3.2.2 Gleitkomma-Ungenauigkeiten

Bei der Berechnung der Oberflächen kommt es regelmäßig zu kleineren Lö-chern, wie in Abb. 8. Bei einer genaueren Betrachtung ist dies darauf zu-rückzuführen, dass nicht alle Dreiecke in jedem nötigen Fall unterteilt wer-den. Die Folge ist, dass im nächsten Schritt getestet wird, ob das Dreieckzur Oberfläche gehört. Ist jedoch nur ein kleiner Teil des Dreiecks ein Teilder Oberfläche und der Rest innerhalb oder außerhalb, so wird das Dreieckkomplett gelöscht. Dies führt zu Löchern im Triangle Mesh. Eine Evaluati-on ergibt, dass das Problem durch Gleitkomma-Ungenauigkeiten verursachtwird.

Bei Gleitkommaoperationen kann es zu kleineren Ungenauigkeiten kom-men, weswegen ein einfacher Test wie if (value == 0.0) nicht viel Sinn hatund stattdessen durch einen Test wie if (fabs(value) < epsilon) ersetzt wird.Meistens wird das Epsilon im Bereich von 1 × 10−10 bis 1 × 10−6 gewählt.

In der Implementierung werden Epsilon-Vergleiche in erster Linie in denGleitkommavergleichen bei Schnitt-Tests wie Strahl-Dreieck oder Dreieck-Dreieck und bei der Unterteilung der Dreiecke verwendet. Dabei kommtjeweils pro Klasse ein einziger Wert für alle Vergleiche zum Einsatz.

Um die Menge der Fehler zu reduzieren wird versucht, die Anzahl derEpsilon-Tests möglichst klein zu halten und gute Werte für die Epsilons zuwählen.

Als besonders problematisch stellen sich dabei alle Tests heraus, die mitdem Dreieck-Dreieck-Schnitt zu tun haben. Versuche ergeben, dass kein all-gemeingültig akzeptabler Wert gefunden werden kann. Rein intuitiv würdeman dazu tendieren, einen möglichst großen Toleranzbereich zu setzen, diesfunktioniert aber in vielen Fällen nicht.

Ein Beispiel: Zwei Dreiecke U und V werden auf ihre Überschneidungüberprüft. Ein Punkt von Dreieck V hat zu U den Abstand von 0.0, einerden Abstand 1 × 10−6 und einer den Abstand 1 × 10−4. Der Absolutwertder drei Distanzen wird im Algorithmus mit Epsilon verglichen und jeweilsauf 0.0 gesetzt, falls der Wert kleiner ist. In diesem Fall kommt es nur dannzu einer Unterteilung, wenn für Epsilon ein Wert zwischen 1 × 10−7 und1 × 10−5 gewählt wird, da bei einem zu kleinen Wert nur ein Punkt dieEbene des Dreiecks U überhaupt berührt. Wird der Wert zu groß gewählt,wird die Distanz aller drei Punkte auf 0.0 gesetzt, was zur Folge hat, dassbeide Dreiecke als koplanar betrachtet werden und keine Schnittgerade mehrbesitzen.

Wählt man nun den Wert passend für dieses Bespiel, kann es passieren,dass andere Dreiecke durch den Schnitt-Test fallen. Welche Lösung für diesesProblem in Frage kommt, kann im Moment nicht klar gesagt werden, eswürde wohl den Rahmen dieser Arbeit sprengen, die Frage komplett zuklären. Das Ziel muss es aber sein, im Zweifel an jeder Stelle zu unterteilen,

18

wo eventuell eine Kollsion stattfinden könnte, unter anderem auch im Fallvon koplanaren Flächen.

3.2.3 Optimierung

Der bisher zur Berechnung benötigte Aufwand ist bei n Polygonen pro Kör-per O(n2). Bisher wird jedes Dreieck aus Körper A mit jedem Dreieck ausKörper B auf Kollision getestet und beim Crossings Test werden ebenfallsalle Dreiecke eines Körpers auf eine Überschneidung mit dem Strahl über-prüft. Eine Berechnung mit zwei Triangle-Meshes mit m und n Polygonenzeigt, wie hoch der Aufwand ist: Für den Kollisionstest sind für den Fall,dass keine Kollisionen auftreten, m×n Tests nötig, die Anzahl der Polygonesteigt aber mit jeder Kollision weiter an. Der Aufwand für die Punkt-in-Polyeder-Tests ist ebenfalls quadratisch, konkret werden 2 × m × n Testsbenötigt. Bei einem Beispiel mit m = 6000 und n = 6000 sind dies imbesten Fall 2 × m × n = 108 × 106 Tests.

In einem realen Fall wurde der Algorithmus auf zwei sich überschneiden-de Meshes mit anfangs je 5800 Dreiecken angewandt. Im Lauf der Berech-nung stieg die Polygonzahl auf ca. 8500 an, die benötigte Zeit1 lag etwasmehr als 36 Minuten.

Besonders Beispiele, in denen keine einzige Kollision auftritt, legen na-he, dass Optimierungsverfahren, die auf der räumlichen Nähe der Objektebasieren, sich gut eignen, um den immensen Berechnungsaufwand zu re-duzieren. Bei den meisten dieser Verfahren wird ein Volumen schrittweiseunterteilt und in einer Hierarchie dargestellt, wodurch es möglich ist, Ob-jekte zu finden, die in unmittelbarer Nähe zueinander liegen. Vorgeschlagenwerden BSP Trees [TN87] [SBGS69] [FKN80] [Nay81] [FAG83] oder Octrees[Mea82] [Mea84] sowie Hyperplane Arrangements [Taw91] [EOS86] und Ac-tive Zones in [RV89].

Für die Implementierung wird eine Optimierung über Octrees gewählt.Dieses Verfahren ist einfach zu implementieren und leicht zu debuggen, au-ßerdem lassen sich die Überschneidungen der Octree-Elemente leicht berech-nen.

Octree-Hierarchien ähneln einer Optimierung durch achsenparallele BSP-Trees. Ein Quader wird dabei mittig parallel zur X-, Y- und Z-Achse un-terteilt. Dadurch entstehen 8 neue Quader, die in einer Baumstruktur an-geordnet werden und die zu Kindknoten des vorherigen Quaders werden.Diese Quader können beliebig lange oder bis zu einem gewünschten Grenz-wert weiter unterteilt werden. Wird der Octree-Hierarchie ein neues Objekthinzugefügt, wird rekursiv entschieden, ob das Objekt im aktuellen Knoten

1Verwendetes System: Athlon 2100+ (1733 MHz) mit 1024 MB Arbeitsspeicher undWindows XP als Betriebssystem

19

gespeichert oder an welches Kind es weitergegeben wird. Die Weiteruntertei-lung und das Anlegen von neuen Knoten wird meist nur bei Bedarf durch-geführt, wodurch der Octree sich an das Vorkommen der Elemente anpasstund Speicherplatz gespart wird.

Beim Hinzufügen eines Polygons wird die Axis-Aligned Bounding Box(AABB) ermittelt, was jeweils einem Minimal- und einem Maximalwert derKoordinaten der Eckpunkte für jede der drei Achsen entspricht. Falls fürdie AABB ein sie komplett umschließender Kindknoten gefunden werdenkann, so wird der Kindknoten gegebenenfalls neu angelegt und das Polygoninklusiver der AABB an ihn weitergegeben. Falls keiner der Kindknoten dieAABB komplett fassen kann oder die maximale Rekursionstiefe erreicht ist,wird das Dreieck im aktuellen Knoten in einem STL-Vector gespeichert.

Der Einbau der Octree-Hierarchien in den Crossings Test bereitet kaumProbleme, da diese Methode im Gegensatz zur Unterteilung der Polygonenichts mehr am Körper ändert.

Für den zur X-Achse parallelen Strahl wird ebenfalls ein achsenparallelesBounding Volume berechnet, das den Strahl inklusive eines Epsilon-Wertesumschließt. Dieses Bounding Volume wird im Octree rekursiv auf Über-schneidung mit den jeweiligen Kindknoten überprüft und die Pointer aufdie Knoten in einer STL-Queue gespeichert und zurückgegeben. Der Epsilon-Wert wird verwendet, um mit Sicherheit alle beteiligten Octree-Knoten zuschneiden. Anschließend wird der Strahl mit allen in den Knoten der Queueenthaltenen Polygone getestet. Dies ist eine Mischung aus Breiten- und Tie-fensuche, die Reihenfolge der Tests spielte hier aber keine Rolle.

Bei den Tests auf Kollision ist eine ähnlich geradlinige Implementierungnicht möglich, da sich während der Bearbeitung die Polygone selbst nochändern. Hier ist es wichtig, eine geeignete Strategie zu finden, um alle Kol-lisionen festzustellen und trotzdem nur alle nötigen Tests nur einmal zudurchlaufen. Das Hauptproblem ist, dass sich die Baumstruktur währendder Unterteilung der Dreiecke weiter verändert. Kindknoten, die bisher nichtexistieren, weil keine ausreichend kleinen Objekte vorhanden sind, könnenneu hinzukommen, und neu hinzukommende Polygone müssen so im Octreeuntergebracht werden, dass sie weder zu selten noch zu oft getestet werden.Daher muss während der Bearbeitung noch auf eine veränderte Struktureingegangen werden können.

Eine gute Lösung für das Problem ist es, auch hier eine Queue zu ver-wenden, um eine Breitensuche auf dem Baum durchzuführen. Die Queuewird dazu schrittweise erstellt und während der Bearbeitung aktualisiert.

Man beginnt beim Wurzelknoten von Körper A, hängt diesen an queue Aan und fügt den Wurzelknoten von Körper B in queue B. Dann werden inverschachtelten Schleifen alle Polygone der Knoten aus den Queues auf Kol-lision getestet. Dabei wird jeweils ein Knoten aus A mit allen Knoten aus B

20

getestet, wenn deren Bounding Boxes sich überschneiden. Sind alle Dreie-cke aus einem Knoten aus B abgearbeitet, werden queue B alle Kinder desaktuellen B-Knotens hinzugefügt, die mit der Bounding Box des aktuellenA-Knotens kollidieren. Sind alle Polygone des A-Knotens behandelt, wer-den queue A alle Kinder des aktuellen A-Knotens angehängt.

Dieser Vorgang läuft, bis die beiden Queues leer sind. Kommt es zu ei-ner Kollision, wird eines oder beide Polygone unterteilt. Dabei wird dasursprüngliche Polygon verkleinert, und neu entstehende Flächen werden di-rekt an den Knoten des Vater-Polygons übergeben, der sie dann je nachBounding Box in der Hierarchie meist nach weiter unten durchreicht.Der Octree des Körpers A wird also bei diesem Ansatz in einer Breitensu-che traversiert und jeweils mit den sich schneidenden Octree-Elementen ausKörper B getestet.

Einige Probeläufe zeigen die Funktionsfähigkeit des Ansatzes und ne-ben seinen Stärken auch gleichzeitig seine Schwächen. Es bleiben bei derZuordnung auf die Octree-Knoten relativ viele Polygone weit oben in derHierarchie, zum Teil sogar in der ersten Ebene, das Ziel ist aber, die Poly-gone möglichst tief in der Hierarchie und in möglichst kleinen Knoten miteiner jeweils geringen Anzahl von Objekten zu speichern, da so die An-zahl der überlappenden Knoten aus dem anderen Körper und damit dieAnzahl der unnötigen Tests klein bleibt. Experimente zu guten Werten fürdie Überlappung sind in Abschnitt 4.1 angeführt. Die Tiefe der Zuordnungin der Hierarchie hängt dabei von der Größe der Polygone ab, bei nähe-rer Betrachtung fällt aber auf, dass die Polygone auf der ersten Stufe zumTeil sehr klein sind, aber auf der Schnittstelle zwischen zwei Bounding Bo-xes von Octree-Knoten liegen und daher keinem der Kindknoten zugeordnetwerden können. Dies bremst den Algorithmus stark aus, wie man im z. B. imWorst-Case-Szenario sieht. In diesem Szenario sind die Bounding Volumesder beiden Körper deckungsgleich, d. h. der Octree-Knoten aus der erstenEbene überlappt mit allen Knoten aus dem anderen Körper, die Polygoneaus diesem Knoten müssen daher mit jedem Polygon des zweiten Körpersgetestet werden.

In [MHAM02] wird dieses Problem bereits beschrieben und der verbesser-te Ansatz Loose Octrees von Thatcher [Tha00] genannt. Die Loose Octreesunterscheiden sich von normalen Octrees nur dadurch, dass sich die Kinderjedes Knotens gegenseitig um einen beliebigen Faktor überschneiden, sieheAbb. 16. Dadurch ist es möglich, kleinere aber mittig positionierte Objektetiefer in der Hierarchie zu speichern. Der Faktor ist dabei nicht zu groß zuwählen, da durch eine große Überlappung die Größe der Knoten mit steigen-der Hierarchietiefe langsamer abnimmt. Bei einem zu kleinen Faktor wirdhingegen der Vorteil der Loose Octrees zunichte gemacht, da sie sich mitsinkender Überlappung einem normalen Octree annähern.

21

Abbildung 16: Ein Vergleich von Octree und Loose Octree: Ein Objekt wird einemKnoten zugewiesen und dieser hat zu testen, wo das Objekt gespeichert werdenkann. Der Octree kann das Objekt nicht tiefer in der Hierarchie speichern, da dasObjekt nicht in die Bounding Volumes der Kinder passt. Beim Loose Octree gelingtdies, da sich die Bounding Boxes überschneiden. Bildquelle: [MHAM02]

In einer Evaluation (sh. Abschnitt 4.1) zeigen sich deutliche Verbesserun-gen der Verteilung der Polygone auf den Octree mit einer höheren durch-schnittlichen Hierarchietiefe, dieser Ansatz wird daher im Weiteren für denAlgorithmus verwendet.

Durch die Überlappung ist eine eindeutige Zuordnung der Objekte nichtmehr gegeben. Ein kleines, mittig positioniertes Objekt kann z. B. jedemder acht Kindknoten zugeordnet werden. In der Implementierung wird einObjekt einfach dem ersten passenden Knoten übergeben, der genaue Spei-cherort ist nicht weiter von Belang, solange er möglichst tief in der Hierarchieist.

Für die beiden Anwendungsgebiete bei der CSG-Konvertierung hat derEinsatz der Loose Octrees keine größeren Folgen, zu beachten ist lediglich,dass bei beiden Tests die Anzahl der kollidierenden Octree-Knoten mit stei-gender Überlappung ebenfalls ansteigt und daher nicht zu groß gewählt wer-den sollte.

Für die Kollionstests zwischen den Polygonen gilt dasselbe, hier ist außer-dem darauf zu achten, dass bei der Unterteilung von Polygonen gewährleistetsein muss, dass neu entstehende Polygone wieder in ihrem ursprünglichenKnoten oder in einem seiner Nachfolger gespeichert werden. Ist dies nichtgewährleistet, so kann es durch die Überlappung passieren, dass neue Polygo-ne in bereits bearbeiteten Knoten gespeichert werden und notwendige Testsübersprungen werden. Die fertige Implementierung in Pseudocode ist aufSeite 23 zu finden, visualisierte Ergebnisse der Loose-Octree-Zuordnungenund einige Auswertungen finden sich in Abschnitt 4.1.

22

1

2 BoundaryRep body_A;

3 BoundaryRep body_B;

4

5 Queue queue_A;

6 Queue queue_B;

7 octreeChildPointer pointer_A ;

8 octreeChildPointer pointer_B ;

9

10 queue_A.push (body_A. octreeRoot );

11 while (! queue_A.empty())

12 {

13 pointer_A = queue_A;

14 queue_A.pop ();

15

16 queue_B.push(body_B. octreeRoot );

17 while (! queue_B.empty ())

18 {

19 pointer_B = queue_B ;

20 queue_B.pop ();

21

22 for each Polygons from pointer_A

23 {

24 for each Polygons from pointer_B

25 {

26

27 testForCollision (Polygon from pointer_A ,

28 Polygon from pointer_B );

29 if ( divisionNeeded (Polygon from pointer_A )

30 {

31 divideAndSaveChildrenIn(pointer_A );

32 }

33

34 if ( divisionNeeded (Polygon from pointer_B )

35 {

36 divideAndSaveChildrenIn(pointer_B );

37 }

38

39 } // for each Polygons from pointer_B

40

41 } // for each Polygons from pointer_A

42

43 pointer_B -> addCollidingChildrenToQueue(

44 queue_B , pointer_A );

45 } // while (! queue_B .empty ())

46

47 pointer_A -> addCollidingChildrenToQueue(queue_A );

48

49 } // while (! queue_A.empty ())

Listing 1: Optimierter Polygonkollisionstest und -unterteilung

23

Abbildung 17: Polygonaufteilung im Octree. Die Polygone sind je nach Tiefe inder Hierarchie eingefärbt. 682 von 5802 Polygonen befinden sich im Wurzelknoten,die Durchschnittstiefe liegt bei 3,354.

4 Ergebnisse und Tests

Eines der wichtigsten Maße für die Verwendbarkeit eines Algorithmus ist diebenötigte Rechenzeit. Um diese zu reduzieren, ist eine geeignete Optimie-rung von Nöten. Die gewählte Ansatz Loose Octrees liefert gute Ergebnisse,inwieweit diese durch geschickte Auswahl der Parameter, vor allem durchden Faktor der Überlappung, verbessert werden können, soll hier getestetwerden.

4.1 Experimente

In Abb. 17 ist die Verteilung der Polygone auf die verschiedenen Ebenendes Octrees visualisiert. Hier ist gut zu erkennen, wie Dreiecke, die sich mitden Grenzflächen der Octree-Knoten schneiden nicht tiefer in die Hierarchiegelangen können. Im Vergleich mit Abb. 18 werden die Vorteile des Loose-Octree-Ansatzes deutlich, es sind kaum noch Flächen auf der ersten Ebene.Bei einer stärkeren Überschneidung der Elemente nimmt der Effekt weiterzu, wie in Abb. 19 zu erkennen ist2.

Die Verteilung der Polygone in der Octree-Struktur in Abhängigkeit vomÜberschneidungsfaktor sind in Abb. 20 zu sehen, der Effekt der tieferen Plat-zierung der Objekte durch Loose Octrees ist mehr als deutlich. Vor allembei hohen Überlappungsfaktoren (ab ca. 80%)

”stauen“ sich die Polygone bei

der maximal eingestellten Hierarchietiefe von 30. Bei einem Wert von 80%sind schon mehr als 60% der Polygone auf dem 30. Level, bei 90% werdenalle Polygone auf dieser Stufe gespeichert.

2Die maximale Hierarchietiefe ist hier auf 8 Stufen beschränkt.

24

Abbildung 18: Dasselbe Modell im Loose Octree mit einer Überschneidung von10 %. Nur noch 2 Polygone sind im Wurzelknoten gespeichert, die mittlere Tiefeerreicht hier 4,925.

Abbildung 19: Überschneidung von 30 %, die mittlere Tiefe ist 7,441

Abbildung 20: Polygonverteilung im Loose Octree abhängig vom Überschnei-dungsfaktor. Die Gesamtzahl der Polygone ist 5802.

25

0

5

10

15

20

25

30

0 10 20 30 40 50 60 70 80 90 100

Dur

schn

ittlic

he H

iera

rchi

etie

fe

Ueberschneidungsfaktor [%]

’data-level.dat’ using 1:2

Abbildung 21: Die mittlere Speichertiefe der Polygone in Abhängigkeit vom Über-schneidungsfaktor

Wie schon erwähnt ist es nicht damit getan, die Überschneidung der Bo-xes zu maximieren und dadurch die mittlere Hierarchietiefe der Polygonezu vergrößern, um den Algorithmus zu verschnellern. Falls die Größe derOctree-Elemente zu groß gewählt wird, kommt es zur Verlangsamung desAlgorithmus durch eine größere Zahl von zu testenden Octree-Elementenund zu längeren Bearbeitungszeiten durch eine größere Hierarchietiefe. Ineinem Geschwindigkeitstest soll daher ein gut geeigneter Wert für den Fak-tor bestimmt werden. Hierfür werden 2 Körper mit jeweils ca. 5800 Dreieckengeschnitten und ihre Schnittmenge gebildet. Die Berechnungszeiten sind inAbb. 22 und 23 zu finden, die aus der Überschneidung resultierende durch-schnittliche Hierarchietiefe der Polygone ist in Abb. 21 dargestellt.Der normale Octree benötigt 435906 ms und ist damit ca. um den Fak-tor 4,98 schneller als die unoptmierte Version, die 2171703 ms oder 36:11min benötigt. Der beste Wert liegt mit 20015 ms bei einer Überschneidungvon 23%, dies ist ca. um den Faktor 108,5 schneller als die Berechnung desErgebnisses mit dem unoptimierten Algorithmus und um den Faktor 21,77schneller als der normale Octree. Welcher Wert wann ideal ist, schwanktvon Fall zu Fall, eine Überschneidung zwischen 20 und 40% scheint aber einakzeptabler Bereich zu sein.

Auffällig ist, dass der Loose-Octree-Ansatz ab einer Überschneidung von70 bis 75% langsamer wird als der Octree und ab 80 bis 85 % sogar langsamerals die unoptimierte Version. Der extreme Anstieg gegen Ende erklärt sichdadurch, dass die maximale Tiefe des Baumes die Platzierung der Polygoneab 80% zu stark beschränkt. In diesem Fall sammeln sich viele Polygone inden Knoten mit der höchsten zugelassenen Tiefe, womit sich die Anzahl derPolygone pro Knoten erhöht, was zu massiven Geschwindigkeitsverlustenführt. Dies ist auf jeden Fall zu vermeiden.

26

0

500000

1e+006

1.5e+006

2e+006

2.5e+006

3e+006

3.5e+006

4e+006

4.5e+006

0 10 20 30 40 50 60 70 80 90 100

Ber

echn

ungs

zeit

[ms]


’data3times.dat’ using 1:2

Abbildung 22: Berechnungszeiten des Algorithmus in Abhängigkeit vom Über-schneidungsfaktor

20000

25000

30000

35000

40000

45000

50000

55000

60000

10 15 20 25 30 35 40 45 50 55

Ber

echn

ungs

zeit

[ms]


’data3times10-55.dat’ using 1:2

Abbildung 23: Berechnungszeiten für Überschneidungsfaktoren zwischen 10% und55%

27

4.2 Ergebnisse

Im Folgenden werden einige Ergebnisse gezeigt.

Abbildung 24: Logo

28

Abbildung 25: Logo

5 Fazit und Ausblick

Die für die Studienarbeit gesetzten Ziele wurden alle erreicht, der Algorith-mus liefert zufriendenstellende Körper aus CSG-Bäumen, die flüssig darge-stellt werden können und sich gut in interaktiven Anwendungen einsetzenlassen. Für die Hauptprobleme bei der Oberflächenberechnung von komple-xen CSG-Bäumen wurde eine gute Lösung gefunden, vor allem die Optimie-rung über Loose Octrees bringt einen deutlichen Geschwindigkeitszuwachs.An einigen Stellen könnte allerdings noch nachgebessert werden, vor allemder Schnitt der Dreiecke ist noch nicht optimal gelöst. Der nächste Schrittwäre hier, mit koplanaren Flächen zu experimentieren und die Problema-tik mit kleinen Grenzwerten in den Griff zu bekommen. Außerdem solltenMaterialeigenschaften und Texturen in die Berechnung miteinbezogen wer-den.

29

Abbildung 26: Kombination aus mehreren Tori

Abbildung 27: Kuh-Kugel-Differenz mit abwechselnd eingefärbten Polygonen

30

Abbildung 28: Kuh-Kugel-Differenz

31

Literatur

[EOS86] Edelsbrunner, O’Rourke, and Seidel. Constructing arrange-ments of lines and hyperplanes with applications. SICOMP:SIAM Journal on Computing, 15, 1986.

[FAG83] H. Fuchs, G. D. Abram, and E. D. Grant. Near-real-time shadeddisplay of rigid objects. ACM Computer Graphics, 10(3):65–72,July 1983.

[FKN80] H. Fuchs, Z. M. Kedem, and B. F. Naylor. On visible surface ge-neration by A priori tree structures. Conf. Proc. of SIGGRAPH’80, 14(3):124–133, July 1980.

[FvDFH96] J. D. Foley, A. van Dam, S. K. Feiner, and J.F. Hughes. Com-puter Graphics. Pearson, 1996.

[Hai94] Eric Haines. Point in polygon strategies. In Paul Heckbert,editor, Graphics Gems IV, pages 24–46. Academic Press, SanDiego, 1994.

[Lin90] Johann Linhart. A quick point-in-polyhedron test. Computers& Graphics, 14(3-4):445–447, 1990.

[Mea82] D. Meagher. Geometric modeling using octree encoding. Com-puter Graphics and Image Processing, 19:129–147, June 1982.

[Mea84] D. J. Meagher. A new mathematics for solids processing (oc-trees...). cgw, October 1984.

[MHAM02] Tomas Moller, Eric Haines, and Tomas Akenine-Moller. Real-Time Rendering. A K Peters, 2002.

[Mol97] Moller. A fast triangle-triangle intersection test. JGTOOLS:Journal of Graphics Tools, 2, 1997.

[MT97] Moller and Trumbore. Fast, minimum storage ray-triangle in-tersection. JGTOOLS: Journal of Graphics Tools, 2, 1997.

[Nay81] B. F. Naylor. A Priori Based Techniques for Determining Visi-bility Priority for 3-D Scenes. PhD thesis, University of Texasat Dallas, May 1981.

[OHL+04] J. Ohlenburg, I. Herbst, I. Lindt, T. Fröhlich, and W. Broll.The MORGAN Framework: Enabling Dynamic Multi–User ARand VR Projects. In Proceedings of VRST 2004, pages 166–169,2004.

32

[OM05] Jan Ohlenburg and Jan Müller. Interactive csg trees inside com-plex scenes. In Proc. of IEEE Visualization, pages 106–107,2005.

[Req80] A. A. G. Requicha. Representations for rigid solids: Theory,methods, and systems. ACM Computing Surveys, 12(4):437–464, December 1980.

[RV85] A. A. G. Requicha and H. B. Voelcker. Boolean operations insolid modeling: Boundary evaluation and merging algorithms.In Proc. IEEE, volume 73, pages 30–44, January 1985.

[RV89] Jarek Rossignac and Herbert B. Voelcker. Active zones in CSGfor accelerating boundary evaluation, redundancy elimination,interference detection, and shading algorithms. ACM Trans.Graph, 8(1):51–87, 1989.

[SBGS69] R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp. Studyfor applying computer-generated images to visual simulation.Technical Report AFHRL–TR–69–14, U.S. Air Force HumanResources Laboratory, 1969.

[SLJ98] N. Stewart, G. Leach, and S. John. An improved Z-Buffer CSGrendering algorithm. In Stephen N. Spencer, editor, Proceedingsof the 1998 EUROGRAPHICS/SIGGRAPH Workshop on Gra-phics Hardware (EGGH-98), pages 25–30, New York, August31– September 1 1998. ACM Press.

[Taw91] Maged S. Tawfik. An efficient algorithm for CSG to b-rep con-version. In Symposium on Solid Modeling and Applications,pages 99–108, 1991.

[Tha00] Ulrich Thatcher. Game Programming Gems 1, chapter LooseOctrees, pages 444–453. Mark DeLoura, 2000.

[TN87] W. C. Thibault and B. F. Naylor. Set operations on polyhedrausing binary space partitioning trees. ACM Computer GraphicsSIGGRAPH ’87, 21(4):153–162, July 1987.

33

EinführungGrundlagenConstructive Solid GeometryBoundary RepresentationCSG und B-Rep

RealisationPrototyp-EntwicklungSchnitt der Dreiecke und UnterteilungPunkt-in-Polyeder-TestsMengenzugehörigkeitsklassifizierungZwischenbilanz

WeiterentwicklungenKoplanaritätGleitkomma-UngenauigkeitenOptimierung

Ergebnisse und TestsExperimenteErgebnisse

Fazit und Ausblick

Date post:	19-Oct-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Effiziente Oberflächenberechnung von komplexen CSG-Bäumencg/Studienarbeiten/SA-Woessner.pdf ·...

Documents