Erst seit ungefähr 10 Jahren ist bekannt, wie sich die Glattheitsordnung der Unterteilungsflächen aus der Unterteilungsmatrix ergibt und erst in jüngster Zeit wurde versucht, auch die Güte, d.h. insbesondere die Krümmungsverteilung der Flächen in der Nähe ihrer Ausnahmepunkte zu analysieren, siehe z.B. [Umlauf ´99,Barthe & Kobbelt ´04,Peters & Reif ´04].
In dieser Arbeit werden die einschlägigen Arbeiten zur Gestalt und Güte von Unterteilungsflächen aufgearbeitet und es wird versucht, die üblichen Unterteilungsalgorithmen zu verbessern, um ,,gute`` Flächen zu erzeugen.
Die Glattheitseigenschaften einer Unterteilungsfläche werden durch das Flächenring-Modell und die diskrete Fourier-Transformation analysiert. Die Begriffe Unterteilungsmatrix, charakteristische Abbildung und zentrale Fläche werden definiert und ihre Bedeutung für die Glattheitseigenschaften einer Unterteilungsfläche ausführlich erklärt. Durch die diskrete Fourier-Transformation wird eine Unterteilungsfläche im Frequenzraum analysiert. Dadurch werden die geometrischen Eigenschaften der Eigenstruktur einer Unterteilungsmatrix klarer. Der Begriff Schrumpfungsfaktor und die Zuordnungstheorie werden vom Autor entwickelt, um solche geometrischen Eigenschaften genau zu charakterisieren. Anhand des Begriffs Fourierindex werden einige Bedingungen für die Stetigkeitsordnung gegeben. Am Ende der Analyse werden einige Kriterien für gute Unterteilungsalgorithmen zusammengefasst.
Weiter wird eine praktische Verbesserungsmethode durch ein Optimierungsverfahren mit zwei Phasen entwickelt. Bei der ersten Phase wird ein Unterteilungsalgorithmus im Allgemeinen optimiert und bei der zweiten Phase wird der Algorithmus zu konkreten Daten angepasst. Die erste Phase wurde implementiert und für die üblichen Unterteilungsalgorithmen angewendet und getestet. Außerdem werden die üblichen Unterteilungsalgorithmen genau analysiert. Die Ergebnisse der Analyse und der Verbesserung zeigen, dass die üblichen und die modifizierten üblichen Unterteilungsalgorithmen ohne flache Ausnahmepunkte nicht ## C^2##, aber durch Verbesserung fast ## C^2## sein können und die gewünschten Formen besser erhalten werden können.
Exemplarisch werden einige Sätze und Resultate vorgestellt.
für alle ## m \in \mathbb{Z}_{\geq 0}, f \in \mathbb{Z}_n\;.## Wobei ## \mathrm{DFT}## der Operator der diskreten Fourier-Transformation ist, ## \mathrm{DFT}^f## die Fourier-Komponente mit der Frequenz ## f## ist, ## \bf{Q}^{(m)}## die Punkte im ## m##-ten Kontrollnetz sind und ## A## die Unterteilungsmatrix ist.
Satz über dem Schrumpfungsfaktor
Der ## g##-te Schrumpfungsfaktor ## \sigma_g^{(m)}## eines polynomialen Teils eines Kontrollnetzes hängt von den Frequenzen, die diesen Teil beeinflusst, ab. Er ist daher von den Beträgen der zugehörigen Eigenwerte abhängig.
Hierbei ist ## \lambda^f_k## der ## k##-te größte Eigenwert von der ## f##-ten Fourier-Komponente der Unterteilungsmatrix und ## n## der Grad einer Masche oder eines Kontrollpunkts.
Zwei Unterteilungsflächen aus demselben Anfangsnetz nach ## 7## Unterteilungsschritten des ursprünglichen Catmull-Clark-Algorithmus (links) und des verbesserten Catmull-Clark-Algorithmus (rechts) sind im Bild zu sehen. Die Punkte des Anfangsnetzes liegen auf einem elliptischen Paraboloid mit ## z=2(3x^2+y^2)=4(x^2+y^2)+2(x^2-y^2)## im Bereich ## (x,y)\in[-0.1,0.1]^2##. Das Anfangsnetz enthält einen Ausnahmepunkt vom Grad ## n=7## als Ursprung. Auf der linken Fläche tritt eine ungewünschte hyperbolische Form auf. Auf der rechten Fläche bleibt die elliptische Form enthalten.
In dieser Arbeit werden die einschlägigen Arbeiten zur Gestalt und Güte von Unterteilungsflächen aufgearbeitet und es wird versucht, die üblichen Unterteilungsalgorithmen zu verbessern, um ,,gute`` Flächen zu erzeugen.
Die Glattheitseigenschaften einer Unterteilungsfläche werden durch das Flächenring-Modell und die diskrete Fourier-Transformation analysiert. Die Begriffe Unterteilungsmatrix, charakteristische Abbildung und zentrale Fläche werden definiert und ihre Bedeutung für die Glattheitseigenschaften einer Unterteilungsfläche ausführlich erklärt. Durch die diskrete Fourier-Transformation wird eine Unterteilungsfläche im Frequenzraum analysiert. Dadurch werden die geometrischen Eigenschaften der Eigenstruktur einer Unterteilungsmatrix klarer. Der Begriff Schrumpfungsfaktor und die Zuordnungstheorie werden vom Autor entwickelt, um solche geometrischen Eigenschaften genau zu charakterisieren. Anhand des Begriffs Fourierindex werden einige Bedingungen für die Stetigkeitsordnung gegeben. Am Ende der Analyse werden einige Kriterien für gute Unterteilungsalgorithmen zusammengefasst.
Weiter wird eine praktische Verbesserungsmethode durch ein Optimierungsverfahren mit zwei Phasen entwickelt. Bei der ersten Phase wird ein Unterteilungsalgorithmus im Allgemeinen optimiert und bei der zweiten Phase wird der Algorithmus zu konkreten Daten angepasst. Die erste Phase wurde implementiert und für die üblichen Unterteilungsalgorithmen angewendet und getestet. Außerdem werden die üblichen Unterteilungsalgorithmen genau analysiert. Die Ergebnisse der Analyse und der Verbesserung zeigen, dass die üblichen und die modifizierten üblichen Unterteilungsalgorithmen ohne flache Ausnahmepunkte nicht ## C^2##, aber durch Verbesserung fast ## C^2## sein können und die gewünschten Formen besser erhalten werden können.
Exemplarisch werden einige Sätze und Resultate vorgestellt.
Hauptsatz im Frequenzraum
Im Frequenzraum ## \mathbb{Z}_n = \{0,1,\ldots, n-1\}## gilt
##\mathrm{DFT}(\bf{Q}^{(m)})## ##=## ## (\mathrm{DFT}(A))^m \: \mathrm{DFT}(\bf{Q}^{(0)})##
##\mathrm{DFT}^f\bf{Q}^{(m)})## ##=## ##(\mathrm{DFT}^f(A))^m \: \mathrm{DFT}^f(\bf{Q}^{(0)})##
##\mathrm{DFT}^f\bf{Q}^{(m)})## ##=## ##(\mathrm{DFT}^f(A))^m \: \mathrm{DFT}^f(\bf{Q}^{(0)})##
für alle ## m \in \mathbb{Z}_{\geq 0}, f \in \mathbb{Z}_n\;.## Wobei ## \mathrm{DFT}## der Operator der diskreten Fourier-Transformation ist, ## \mathrm{DFT}^f## die Fourier-Komponente mit der Frequenz ## f## ist, ## \bf{Q}^{(m)}## die Punkte im ## m##-ten Kontrollnetz sind und ## A## die Unterteilungsmatrix ist.
Satz über dem Schrumpfungsfaktor
Der ## g##-te Schrumpfungsfaktor ## \sigma_g^{(m)}## eines polynomialen Teils eines Kontrollnetzes hängt von den Frequenzen, die diesen Teil beeinflusst, ab. Er ist daher von den Beträgen der zugehörigen Eigenwerte abhängig.
| Grad ## g## | Frequenzen | Abhängigkeit von ## \sigma_g^{(m)}\;(g<n/2)## |
| 0 | ## \{0\}## | ## \{|\lambda^0_0|\}## |
| ## 1## | ## \{\pm 1\}## | ## \{|\lambda^{\pm 1}_0|\}## |
| ## 2## | ## \{0, \pm 2\}## | ## \{|\lambda^0_1|, |\lambda^{\pm 2}_0|\}## |
| ## 3## | ## \{\pm 1, \pm 3\}## | ## \{|\lambda^{\pm 1}_1|, |\lambda^{\pm 3}_0|\}## |
| ## 4## | ## \{0, \pm 2, \pm 4\}## | ## \{|\lambda^0_2|, |\lambda^{\pm 2}_1|, |\lambda^{\pm 4}_0|\}## |
| ⋮ | ⋮ | ⋮ |
Ein Beispiel für den verbesserten Catmull-Clark-Algorithmus:
 |
 |
Literatur
- Barthe & Kobbelt ´04
Loïc Barthe and Leif Kobbelt. Subdivision scheme tuning around extraordinary vertices. Computer Aided Geometric Design, 21, Nr. 6, S. 561-583, July 2004. - Peters & Reif ´04
Jörg Peters and Ulrich Reif. Shape characterization of subdivision surfaces-basic principles. Computer Aided Geometric Design, 21, Nr. 6, S. 585-599, July 2004. - Umlauf ´99
Georg Umlauf. Glatte Freiformflächen und optimierte Unterteilungsalgorithmen. Dissertation, Universität Karlsruhe (TH), 1999.