Eine Zusammenstellung der Blender-Quellfiles, welche zum UNIX-STammtisch "Character-Animation mit Blender" gezeigt wurden.

Active contours have been proven to be a powerful semiautomatic image segmentation approach, that seems to cope with many applications and different image modalities. However, they exhibit inherent drawbacks, including the sensibility to contour initialization due to the limited capture range of image edges and problems with concave boundary regions. The Gradient Vector Flow replaces the traditional image force and provides an enlarged capture range as well as enhanced concavity extraction capabilities, but it involves an expensive computational effort and considerably increased memory requirements at the time of computation. In this paper, we present an enhancement of the active contour model to facilitate semiautomatic contour detection in huge images. We propose a tile-based image decomposition accompanying an image force computation scheme on demand in order to minimize both computational and memory requirements. We show an efficient implementation of this approach on the basis of general purpose GPU processing providing for continuous active contour deformation without a considerable delay.

In dieser Dissertation wird erstmalig ein theoretisches Fundament zur Beschneiung virtueller Szenen entwickelt. Das theoretische Fundament wird als analytisches Modell in Form einer Diffusionsgleichung formuliert. Aus dem analytischen Modell lässt sich eine Gruppe von Algorithmen zur Beschneiung virtueller Szenen ableiten. Eingehende Voruntersuchungen zur allgemeinen Modellierung natürlicher Phänomene in der Computergraphik sowie eine Klassifikation der bestehenden Literatur über mathematische Schneemodellierung bilden den Anfang der Arbeit. Aus der umfassenden Darstellung der Eigenschaften von Schnee, wie er in der Natur vorkommt, ergeben sich die Grundlagen für die Modellbildung. Die Modellbildung fußt auf den grundlegenden Ansätzen der klassischen Mechanik und der statistischen Physik. Für die Beschneiung auf visueller Skala erweist sich der Diffusionsprozess als geeignete Beschreibung. Mit der Beschreibung lassen sich diffusiv Schneeoberflächen erzeugen. Der konkrete computergraphische Wert des theoretischen Fundaments wird anhand zweier Implementierungen exemplarisch dargestellt, und zwar in der Distanzfeldmethode und der Diffusionskernmethode. Die Ergebnisse werden mithilfe dreidimensionaler Rauschtexturen und Alpha-Masken an den Rändern fotorealistisch visualisiert.:1. Einleitung 7 2. Zentrale Beiträge dieser Arbeit 11 3. Natürliche Phänomenmodellierung in der Computergraphik 13 3.1. Die Rolle der computergraphisch modellierten Naturphänomene in der Informatik . . . . 14 3.2. Repräsentationsformen natürlicher Phänomene in der Computergraphik . . . . 16 3.3. Modellierungsmethoden im Überblick . . . . . . . . . . . . . . . . . . . . 20 3.3.1. Bildbasierte Methoden . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2. Diskretisierungsbasierte Methoden . . . . . . . . . . . . . . . . . . 21 3.3.3. Kontinuumsbasierte Methoden . . . . . . . . . . . . . . . . . . . . 22 3.3.4. Modellreduktionsmethoden . . . . . . . . . . . . . . . . . . . . . . 23 3.3.5. Interaktionsmethoden . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4. Klassifikation der natürlichen Phänomene in der Computergraphik . . . . 25 3.4.1. Statische Phänomene . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4.2. Dynamische Phänomene . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.3. Zusammengesetzte Phänomene . . . . . . . . . . . . . . . . . . . . 30 3.4.4. Sonstige natürliche Phänomene . . . . . . . . . . . . . . . . . . . . 32 3.5. Schlussfolgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4. Schnee in der Natur 35 4.1. Entstehung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2. Niederschlag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3. Akkumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4. Metamorphose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5. Computergraphisch modellierbare Aspekte . . . . . . . . . . . . . . . . . . 40 5. Vorarbeiten zur computergraphischen Schneemodellierung 45 5.1. Modellierung statischer Aspekte . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1.1. Optische Schneeeigenschaften . . . . . . . . . . . . . . . . . . . . . 45 5.1.2. Geometrische Form der Schneeoberflächen . . . . . . . . . . . . . . 46 5.1.3. Schnee als makroskopische Landschaftstextur . . . . . . . . . . . . 48 5.2. Modellierung dynamischer Aspekte . . . . . . . . . . . . . . . . . . . . . . 48 5.2.1. Schneefall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2.2. Schneeschmelze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.2.3. Lokale Schneeumlagerung und Kompaktifizierung . . . . . . . . . . 50 5.2.4. Bisher nicht modellierte Aspekte . . . . . . . . . . . . . . . . . . . 51 5.3. Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6. Physikalische Methoden zur Darstellung von Materialflüssen und Phasengrenzen 55 6.1. Mikroskopische Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.1.1. Formale Schneecharakterisierung mit einer Vielteilchen-Hamilton- Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.1.2. Statistische Formulierung der Vielteilchenbeschreibung . . . . . . . 57 6.2. Makroskopische Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2.1. Schneeverteilung als globales Strahlungsgleichgewicht . . . . . . . 59 6.2.2. Lokale stochastische Darstellung als getriebene Oberfläche . . . . . 61 6.2.3. Oberflächenentwicklung als Reaktionsdiffusion . . . . . . . . . . . 63 6.3. Zusammenfassung und Schlussfolgerung . . . . . . . . . . . . . . . . . . . 65 7. Eigenschaften und Lösungen von Diffusionsgleichungen 67 7.1. Das physikalische Prinzip der Diffusion . . . . . . . . . . . . . . . . . . . . 67 7.1.1. Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.1.2. Diffusion auf Höhenfeldern . . . . . . . . . . . . . . . . . . . . . . 68 7.2. Mathematische Behandlung linearer Diffusionsgleichungen . . . . . . . . . 70 7.2.1. Konstruktion von allgemeinen Lösungen mittels Fundamentallösung 70 7.3. Analytische Lösungsbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . 72 8. Computergraphische Erzeugung von Schneeoberflächengeometrien 75 8.1. Faltung als Grundprinzip der diffusiven Schneedeckenerzeugung . . . . . . 76 8.2. Datenstrukturen zur Darstellung von Schneedecken . . . . . . . . . . . . . 79 8.3. Darstellung mittels Distanzfeld . . . . . . . . . . . . . . . . . . . . . . . . 81 8.3.1. Details der Distanzfeldmethode . . . . . . . . . . . . . . . . . . . . 81 8.3.2. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.4. Darstellung als Diffusionsprozess . . . . . . . . . . . . . . . . . . . . . . . 86 8.4.1. Modelldetails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.4.2. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.5. Erweiterung für Überhänge und Schneebrücken . . . . . . . . . . . . . . . 96 8.5.1. Brückenerzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.5.2. Überhangsberechnung . . . . . . . . . . . . . . . . . . . . . . . . . 98 8.5.3. Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.5.4. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.6. Vergleich und Verallgemeinerbarkeit der Schneemodellierungsansätze . . . 101 9. Visualisierung virtueller Schneeoberflächen 103 9.1. Schneeoberfläche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2. Schneeränder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.3. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 10.Zusammenfassung und Schlussfolgerungen 107 10.1. Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.2. Schlussfolgerungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 A. Beobachtungssammlung natürlicher Schneeformen 109 A.1. Randprofile und Stützflächenabhängigkeit . . . . . . . . . . . . . . . . . . 109 A.2. Verdeckung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 A.3. Glättung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 A.4. Innenränder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 A.5. Brücken und Überhänge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 A.6. Nicht modellierte Aspekte . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 B. Sammlung virtuell beschneiter Szenen 125 B.1. Distanzfeldmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 B.2. Diffusionskernmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 B.3. Brückenbildung und Überhänge . . . . . . . . . . . . . . . . . . . . . . . . 130 Literaturverzeichnis 131 Abbildungsverzeichnis 143 Veröffentlichungen 151 / In this dissertation for the first time a theoretical foundation is developed for snow accumulation in virtual scenes. The theoretical foundation is formulated in an analytical model as diffusion equation. The analytical model leads to a group of algorithms for virtual snow accumulation. Comprehensive investigations for the modelling of natural phenomena in computer graphics in general are used to develop a method classification scheme. Another classification is given for an overview over the aspects of snow in the real world. This allows an efficient presentation of related literature on snow modelling. A new approach of snow modelling is then drawn from first principles of classical mechanics and statistical physics. Diffusion processes provide an efficient theoretical framework for snow accumulation. The mathematical structure of diffusion equations is discussed and demonstrated to be adequate to snow modelling in visual scales. The value of the theoretical foundation for computer graphics is demonstrated with two exemplary implementations, a distance field method and the diffusion kernel method. Results are visualized with 3D noise textures and alpha masks near borders delivering photorealistic snow pictures.:1. Einleitung 7 2. Zentrale Beiträge dieser Arbeit 11 3. Natürliche Phänomenmodellierung in der Computergraphik 13 3.1. Die Rolle der computergraphisch modellierten Naturphänomene in der Informatik . . . . 14 3.2. Repräsentationsformen natürlicher Phänomene in der Computergraphik . . . . 16 3.3. Modellierungsmethoden im Überblick . . . . . . . . . . . . . . . . . . . . 20 3.3.1. Bildbasierte Methoden . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2. Diskretisierungsbasierte Methoden . . . . . . . . . . . . . . . . . . 21 3.3.3. Kontinuumsbasierte Methoden . . . . . . . . . . . . . . . . . . . . 22 3.3.4. Modellreduktionsmethoden . . . . . . . . . . . . . . . . . . . . . . 23 3.3.5. Interaktionsmethoden . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4. Klassifikation der natürlichen Phänomene in der Computergraphik . . . . 25 3.4.1. Statische Phänomene . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4.2. Dynamische Phänomene . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.3. Zusammengesetzte Phänomene . . . . . . . . . . . . . . . . . . . . 30 3.4.4. Sonstige natürliche Phänomene . . . . . . . . . . . . . . . . . . . . 32 3.5. Schlussfolgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4. Schnee in der Natur 35 4.1. Entstehung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2. Niederschlag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3. Akkumulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4. Metamorphose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5. Computergraphisch modellierbare Aspekte . . . . . . . . . . . . . . . . . . 40 5. Vorarbeiten zur computergraphischen Schneemodellierung 45 5.1. Modellierung statischer Aspekte . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1.1. Optische Schneeeigenschaften . . . . . . . . . . . . . . . . . . . . . 45 5.1.2. Geometrische Form der Schneeoberflächen . . . . . . . . . . . . . . 46 5.1.3. Schnee als makroskopische Landschaftstextur . . . . . . . . . . . . 48 5.2. Modellierung dynamischer Aspekte . . . . . . . . . . . . . . . . . . . . . . 48 5.2.1. Schneefall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2.2. Schneeschmelze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.2.3. Lokale Schneeumlagerung und Kompaktifizierung . . . . . . . . . . 50 5.2.4. Bisher nicht modellierte Aspekte . . . . . . . . . . . . . . . . . . . 51 5.3. Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6. Physikalische Methoden zur Darstellung von Materialflüssen und Phasengrenzen 55 6.1. Mikroskopische Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.1.1. Formale Schneecharakterisierung mit einer Vielteilchen-Hamilton- Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.1.2. Statistische Formulierung der Vielteilchenbeschreibung . . . . . . . 57 6.2. Makroskopische Modelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2.1. Schneeverteilung als globales Strahlungsgleichgewicht . . . . . . . 59 6.2.2. Lokale stochastische Darstellung als getriebene Oberfläche . . . . . 61 6.2.3. Oberflächenentwicklung als Reaktionsdiffusion . . . . . . . . . . . 63 6.3. Zusammenfassung und Schlussfolgerung . . . . . . . . . . . . . . . . . . . 65 7. Eigenschaften und Lösungen von Diffusionsgleichungen 67 7.1. Das physikalische Prinzip der Diffusion . . . . . . . . . . . . . . . . . . . . 67 7.1.1. Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.1.2. Diffusion auf Höhenfeldern . . . . . . . . . . . . . . . . . . . . . . 68 7.2. Mathematische Behandlung linearer Diffusionsgleichungen . . . . . . . . . 70 7.2.1. Konstruktion von allgemeinen Lösungen mittels Fundamentallösung 70 7.3. Analytische Lösungsbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . 72 8. Computergraphische Erzeugung von Schneeoberflächengeometrien 75 8.1. Faltung als Grundprinzip der diffusiven Schneedeckenerzeugung . . . . . . 76 8.2. Datenstrukturen zur Darstellung von Schneedecken . . . . . . . . . . . . . 79 8.3. Darstellung mittels Distanzfeld . . . . . . . . . . . . . . . . . . . . . . . . 81 8.3.1. Details der Distanzfeldmethode . . . . . . . . . . . . . . . . . . . . 81 8.3.2. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.4. Darstellung als Diffusionsprozess . . . . . . . . . . . . . . . . . . . . . . . 86 8.4.1. Modelldetails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.4.2. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.5. Erweiterung für Überhänge und Schneebrücken . . . . . . . . . . . . . . . 96 8.5.1. Brückenerzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.5.2. Überhangsberechnung . . . . . . . . . . . . . . . . . . . . . . . . . 98 8.5.3. Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.5.4. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.6. Vergleich und Verallgemeinerbarkeit der Schneemodellierungsansätze . . . 101 9. Visualisierung virtueller Schneeoberflächen 103 9.1. Schneeoberfläche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2. Schneeränder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.3. Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 10.Zusammenfassung und Schlussfolgerungen 107 10.1. Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.2. Schlussfolgerungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 A. Beobachtungssammlung natürlicher Schneeformen 109 A.1. Randprofile und Stützflächenabhängigkeit . . . . . . . . . . . . . . . . . . 109 A.2. Verdeckung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 A.3. Glättung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 A.4. Innenränder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 A.5. Brücken und Überhänge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 A.6. Nicht modellierte Aspekte . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 B. Sammlung virtuell beschneiter Szenen 125 B.1. Distanzfeldmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 B.2. Diffusionskernmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 B.3. Brückenbildung und Überhänge . . . . . . . . . . . . . . . . . . . . . . . . 130 Literaturverzeichnis 131 Abbildungsverzeichnis 143 Veröffentlichungen 151

Thema dieser Arbeit sind echtzeitfähige 3D-Renderingverfahren, die 3D-Geometrie mit über der Standarddarstellung hinausgehenden Qualitäts- und Gestaltungsmerkmalen rendern können. Beispiele sind Verfahren zur Darstellung von Schatten, Reflexionen oder Transparenz. Mit heutigen computergraphischen Software-Basissystemen ist ihre Integration in 3D-Anwendungssysteme sehr aufwändig: Dies liegt einerseits an der technischen, algorithmischen Komplexität der Einzelverfahren, andererseits an Ressourcenkonflikten und Seiteneffekten bei der Kombination mehrerer Verfahren. Szenengraphsysteme, intendiert als computergraphische Softwareschicht zur Abstraktion von der Graphikhardware, stellen derzeit keine Mechanismen zur Nutzung dieser Renderingverfahren zur Verfügung.<br><br> Ziel dieser Arbeit ist es, eine Software-Architektur für ein Szenengraphsystem zu konzipieren und umzusetzen, die echtzeitfähige 3D-Renderingverfahren als Komponenten modelliert und es damit erlaubt, diese Verfahren innerhalb des Szenengraphsystems für die Anwendungsentwicklung effektiv zu nutzen. Ein Entwickler, der ein solches Szenengraphsystem nutzt, steuert diese Komponenten durch Elemente in der Szenenbeschreibung an, die die sichtbare Wirkung eines Renderingverfahrens auf die Geometrie in der Szene angeben, aber keine Hinweise auf die algorithmische Implementierung des Verfahrens enthalten. Damit werden Renderingverfahren in 3D-Anwendungssystemen nutzbar, ohne dass ein Entwickler detaillierte Kenntnisse über sie benötigt, so dass der Aufwand für ihre Entwicklung drastisch reduziert wird.<br><br> Ein besonderer Augenmerk der Arbeit liegt darauf, auf diese Weise auch verschiedene Renderingverfahren in einer Szene kombiniert einsetzen zu können. Hierzu ist eine Unterteilung der Renderingverfahren in mehrere Kategorien erforderlich, die mit Hilfe unterschiedlicher Ansätze ausgewertet werden. Dies erlaubt die Abstimmung verschiedener Komponenten für Renderingverfahren und ihrer verwendeten Ressourcen.<br><br> Die Zusammenarbeit mehrerer Renderingverfahren hat dort ihre Grenzen, wo die Kombination von Renderingverfahren graphisch nicht sinnvoll ist oder fundamentale technische Beschränkungen der Verfahren eine gleichzeitige Verwendung unmöglich machen. Die in dieser Arbeit vorgestellte Software-Architektur kann diese Grenzen nicht verschieben, aber sie ermöglicht den gleichzeitigen Einsatz vieler Verfahren, bei denen eine Kombination aufgrund der hohen Komplexität der Implementierung bislang nicht erreicht wurde. Das Vermögen zur Zusammenarbeit ist dabei allerdings von der Art eines Einzelverfahrens abhängig: Verfahren zur Darstellung transparenter Geometrie beispielsweise erfordern bei der Kombination mit anderen Verfahren in der Regel vollständig neuentwickelte Renderingverfahren; entsprechende Komponenten für das Szenengraphsystem können daher nur eingeschränkt mit Komponenten für andere Renderingverfahren verwendet werden.<br><br> Das in dieser Arbeit entwickelte System integriert und kombiniert Verfahren zur Darstellung von Bumpmapping, verschiedene Schatten- und Reflexionsverfahren sowie bildbasiertes CSG-Rendering. Damit stehen wesentliche Renderingverfahren in einem Szenengraphsystem erstmalig komponentenbasiert und auf einem hohen Abstraktionsniveau zur Verfügung. Das System ist trotz des zusätzlichen Verwaltungsaufwandes in der Lage, die Renderingverfahren einzeln und in Kombination grundsätzlich in Echtzeit auszuführen. / This thesis is about real-time rendering algorithms that can render 3D-geometry with quality and design features beyond standard display. Examples include algorithms to render shadows, reflections, or transparency. Integrating these algorithms into 3D-applications using today’s rendering libraries for real-time computer graphics is exceedingly difficult: On the one hand, the rendering algorithms are technically and algorithmically complicated for their own, on the other hand, combining several algorithms causes resource conflicts and side effects that are very difficult to handle. Scene graph libraries, which intend to provide a software layer to abstract from computer graphics hardware, currently offer no mechanisms for using these rendering algorithms, either.<br><br> The objective of this thesis is to design and to implement a software architecture for a scene graph library that models real-time rendering algorithms as software components allowing an effective usage of these algorithms for 3D-application development within the scene graph library. An application developer using the scene graph library controls these components with elements in a scene description that describe the effect of a rendering algorithm for some geometry in the scene graph, but that do not contain hints about the actual implementation of the rendering algorithm. This allows for deploying rendering algorithms in 3D-applications even for application developers that do not have detailed knowledge about them. In this way, the complexity of development of rendering algorithms can be drastically reduced.<br><br> In particular, the thesis focuses on the feasibility of combining several rendering algorithms within a scene at the same time. This requires to classify rendering algorithms into different categories, which are, each, evaluated using different approaches. In this way, components for different rendering algorithms can collaborate and adjust their usage of common graphics resources.<br><br> The possibility of combining different rendering algorithms can be limited in several ways: The graphical result of the combination can be undefined, or fundamental technical restrictions can render it impossible to use two rendering algorithms at the same time. The software architecture described in this work is not able to remove these limitations, but it allows to combine a lot of different rendering algorithms that, until now, could not be combined due to the high complexities of the required implementation. The capability of collaboration, however, depends on the kind of rendering algorithm: For instance, algorithms for rendering transparent geometry can be combined with other algorithms only with a complete redesign of the algorithm. Therefore, components in the scene graph library for displaying transparency can be combined with components for other rendering algorithms in a limited way only.<br><br> The system developed in this work integrates and combines algorithms for displaying bump mapping, several variants of shadow and reflection algorithms, and image-based CSG algorithms. Hence, major rendering algorithms are available for the first time in a scene graph library as components with high abstraction level. Despite the required additional indirections and abstraction layers, the system, in principle, allows for using and combining the rendering algorithms in real-time.

Tetrahedral meshes are becoming more and more important for geo-modeling applications. The presented work introduces new algorithms for efficient visualization and modeling of tetrahedral meshes. Visualization consists of a generic framework that includes the extraction of geological information like stratigraphic columns, fault block boundaries, simultaneous co-rendering of different attributes and boolean operations of Constructive Solid Geometry with constant complexity. Modeling can be classified into geometric and implicit modeling. Geometric modeling addresses local mesh refinement to increase the numerical resolution of a given mesh. Implicit modeling covers the definition and manipulation of implicitly defined models. A new surface reconstruction method was developed to reconstruct complex, multi-valued surfaces from noisy and sparse data sets as they occur in geological applications. The surface can be bounded and may have discontinuities. Further, this work proposes a new and innovative algorithm for rapid editing of implicitly defined shapes like horizons based on the GeoChron parametrization. The editing is performed interactively on the 3d-volumetric model and geological constraints are respected automatically.

Oftmals kann ein Problem erst dadurch gelöst werden, indem seine Komplexität reduziert wird. Erst diese Reduktion ermöglicht die Verwendung von Lösungsansätzen, die für weniger komplexe Problemstellungen existieren. Für 3d-Objekte ist die Skelettierung der Mechanismus, der die Objekte auf eine niedrigere Dimension abbildet und dadurch deren Komplexität reduziert. Seit nunmehr 40 Jahren werden entsprechende Verfahren und darauf basierende Anwendungen entwickelt. In jüngster Zeit traten auf innovativen Forschungsgebieten innerhalb des Maschinenbaus, der Nanotechnologie, der Medizintechnik und nicht zuletzt der Computergrafik Probleme auf, die durch Skelettierung bewältigt wurden oder in naher Zukunft zu bewältigen sind. Mit der vorliegenden Dissertation wird an den aktuellen Stand der Forschung angeknüpft und ein Skelettierungsverfahren vorgestellt, das nicht auf den bisher üblichen kartesischen Gittern, sondern auf den sogenannten kubisch-raumzentrierten Gittern operiert. Dadurch ergeben sich eine Vielzahl positiver Eigenschaften, sowohl unter topologischen als auch rechentechnischen Aspekten. Die auf Gitterstrukturen basierenden Verfahren haben traditionell Schwierigkeiten, rotationsinvariante Skelette zu generieren. Diese Eigenschaft ist jedoch für eine Reihe von Applikationen wünschenswert. Eine Ausnahme bilden Verfahren, die zunächst ein Vektorfeld berechnen, das Abstoßungen vom Objektrand simuliert. Mithilfe dieser Strukturen können Skelettpunkte identifiziert werden, die von der Gitterstruktur unabhängig sind. Allerdings sind die Verfahren, die derartige Skelette erzeugen, extrem ineffizient: Bezogen auf die Anzahl der Objektgitterpunkte ist die Komplexität quadratisch. Deshalb ist ein weiterer Schwerpunkt dieser Arbeit, eine qualitativ hochwertige Approximation des Vektorfeldes in linearer Zeitkomplexität zu erzeugen. Die zusätzlichen Informationen, die aus diesen Vektorfeldern gewonnen werden, kommen innerhalb des ursprünglichen Skelettierungsverfahrens zum Einsatz, um die Vorteile beider Verfahren zu kombinieren. Die auf diese Weise erzeugten eindimensionalen Skelettstrukturen der 3d-Objekte eignen sich für eine Vielzahl von Anwendungen. Drei Anwendungen, namentlich die Klassifizierung, die Segmentierung und die Manipulierung werden gezeigt. Für die Klassifizierung werden die erzeugten Skelette in eine Graphrepräsentation transformiert. Hierfür werden zwei Verfahren vorgestellt und darüber hinaus erläutert, wie die Graphrepräsentation optimiert und mit Attributen versehen werden kann. Insbesondere die Attributierung (z. B. mit Distanz- oder Krümmungsinformationen) ist von großer Bedeutung, da der Graph zunächst die Objektform nur grob abstrahiert und dadurch kein detaillierter Vergleich zwischen Objekten möglich wäre. Für die Segmentierung und die Deformierung von 3d-Objekten besteht der wichtigste Beitrag dieser Dissertation darin, eine präzise Zuordnung zwischen Abschnitten des Graphen und Meshregionen durchzuführen, die erforderlich ist, um Änderungen an der Graphstruktur (Auftrennen oder Deformieren) direkt auf das Mesh übertragen zu können. Hierfür wird eine spezielle Datenstruktur präsentiert, die diese Zuordnung ermöglicht, ohne die Komplexität des Skelettierungsverfahrens zu verschlechtern. Ein breites Spektrum an Vorschlägen für zukünftige, auf dieser Dissertation aufbauende Forschungsthemen schließen die Arbeit ab.

Techn. University, Diss., 2003--Darmstadt.

Oftmals kann ein Problem erst dadurch gelöst werden, indem seine Komplexität reduziert wird. Erst diese Reduktion ermöglicht die Verwendung von Lösungsansätzen, die für weniger komplexe Problemstellungen existieren. Für 3d-Objekte ist die Skelettierung der Mechanismus, der die Objekte auf eine niedrigere Dimension abbildet und dadurch deren Komplexität reduziert. Seit nunmehr 40 Jahren werden entsprechende Verfahren und darauf basierende Anwendungen entwickelt. In jüngster Zeit traten auf innovativen Forschungsgebieten innerhalb des Maschinenbaus, der Nanotechnologie, der Medizintechnik und nicht zuletzt der Computergrafik Probleme auf, die durch Skelettierung bewältigt wurden oder in naher Zukunft zu bewältigen sind. Mit der vorliegenden Dissertation wird an den aktuellen Stand der Forschung angeknüpft und ein Skelettierungsverfahren vorgestellt, das nicht auf den bisher üblichen kartesischen Gittern, sondern auf den sogenannten kubisch-raumzentrierten Gittern operiert. Dadurch ergeben sich eine Vielzahl positiver Eigenschaften, sowohl unter topologischen als auch rechentechnischen Aspekten. Die auf Gitterstrukturen basierenden Verfahren haben traditionell Schwierigkeiten, rotationsinvariante Skelette zu generieren. Diese Eigenschaft ist jedoch für eine Reihe von Applikationen wünschenswert. Eine Ausnahme bilden Verfahren, die zunächst ein Vektorfeld berechnen, das Abstoßungen vom Objektrand simuliert. Mithilfe dieser Strukturen können Skelettpunkte identifiziert werden, die von der Gitterstruktur unabhängig sind. Allerdings sind die Verfahren, die derartige Skelette erzeugen, extrem ineffizient: Bezogen auf die Anzahl der Objektgitterpunkte ist die Komplexität quadratisch. Deshalb ist ein weiterer Schwerpunkt dieser Arbeit, eine qualitativ hochwertige Approximation des Vektorfeldes in linearer Zeitkomplexität zu erzeugen. Die zusätzlichen Informationen, die aus diesen Vektorfeldern gewonnen werden, kommen innerhalb des ursprünglichen Skelettierungsverfahrens zum Einsatz, um die Vorteile beider Verfahren zu kombinieren. Die auf diese Weise erzeugten eindimensionalen Skelettstrukturen der 3d-Objekte eignen sich für eine Vielzahl von Anwendungen. Drei Anwendungen, namentlich die Klassifizierung, die Segmentierung und die Manipulierung werden gezeigt. Für die Klassifizierung werden die erzeugten Skelette in eine Graphrepräsentation transformiert. Hierfür werden zwei Verfahren vorgestellt und darüber hinaus erläutert, wie die Graphrepräsentation optimiert und mit Attributen versehen werden kann. Insbesondere die Attributierung (z. B. mit Distanz- oder Krümmungsinformationen) ist von großer Bedeutung, da der Graph zunächst die Objektform nur grob abstrahiert und dadurch kein detaillierter Vergleich zwischen Objekten möglich wäre. Für die Segmentierung und die Deformierung von 3d-Objekten besteht der wichtigste Beitrag dieser Dissertation darin, eine präzise Zuordnung zwischen Abschnitten des Graphen und Meshregionen durchzuführen, die erforderlich ist, um Änderungen an der Graphstruktur (Auftrennen oder Deformieren) direkt auf das Mesh übertragen zu können. Hierfür wird eine spezielle Datenstruktur präsentiert, die diese Zuordnung ermöglicht, ohne die Komplexität des Skelettierungsverfahrens zu verschlechtern. Ein breites Spektrum an Vorschlägen für zukünftige, auf dieser Dissertation aufbauende Forschungsthemen schließen die Arbeit ab.

Für die schnelle Visualisierung großer Modelle werden sogenannte Echtzeit-Visualisierungsverfahren (real time rendering techniques) eingesetzt. Durch parallele Verarbeitung der Objektdaten auf Multicore-CPUs ist es möglich, die Geschwindigkeit der Darstellung gegenüber GPU-basierten Verfahren weiter zu erhöhen. Insbesondere wurde die Möglichkeit untersucht, das Occlusion-Culling mit Hilfe der CPU durchzuführen. Dabei konnte speziell das Worst-Case-Verhalten verbessert werden. Mit der Anzahl der Systemkomponenten (z.B. Trackingsystem, Beamer, Rechner) steigt die Trägheit (Latenz) des Gesamtsystems, was eine Echtzeitverarbeitung der Daten deutlich erschwert. Durch Bewegungsvorhersagen, die speziell an das Nutzerverhalten im Rahmen der Anwendung angepasst sind, können auftretende Latenzen kompensiert werden. Die Entwicklungen erfolgten im Kontext einer immersiven Tischtennissimulation. Tischtennis gehört zu den schnellsten Sportarten und repräsentiert somit eine anspruchsvolle Umgebung. Ein weiterer wichtiger Aspekt bei der Interaktion mit virtuellen Umgebungen ist die Natürlichkeit (Intuitivität) der Benutzeroberfläche. Durch eine möglichst direkte (aus der Realität bekannte) Umsetzung der Benutzerbewegungen in Systembefehle wird eine höchstmögliche Effektivität im Umgang mit dem System erzielt. Im Rahmen einer Designanwendung wurden Interaktionstechniken realisiert, die den alltäglichen Bewegungsabläufen nachempfunden sind.

Point-based rendering methods have proven to be effective for the display of large point cloud surface models. For a realistic visualization of the models, transparency and shadows are essential features. We propose a method for point cloud rendering with transparency and shadows at interactive rates. Our approach does not require any global or local surface reconstruction method, but operates directly on the point cloud. All passes are executed in image space and no pre-computation steps are required. The underlying technique for our approach is a depth peeling method for point cloud surface representations. Having detected a sorted sequence of surface layers, they can be blended front to back with given opacity values to obtain renderings with transparency. These computation steps achieve interactive frame rates. For renderings with shadows, we determine a point cloud shadow texture that stores for each point of a point cloud whether it is lit by a given light source. The extraction of the layer of lit points is obtained using the depth peeling technique, again. For the shadow texture computation, we also apply a Monte-Carlo integration method to approximate light from an area light source, leading to soft shadows. Shadow computations for point light sources are executed at interactive frame rates. Shadow computations for area light sources are performed at interactive or near-interactive frame rates depending on the approximation quality.