Ein neuer Ansatz zur Konstruktion von Subdivisionsalgorithmen

In dieser Arbeit wird ein neuer Ansatz zur Konstruktion von Subdivisionsalgorithmen für verallgemeinerte quadratische und kubische B-Spline-Subdivision für Subdivisionsflächen und -volumen vorgestellt. Dabei wird zunächst ein Katalog von Qualitätskriterien für diese Subdivisionsalgorithmen erarbeitet, an denen sich die Konstruktion orientiert. Die Konstruktion erstellt in einem ersten Schritt die gewünschten subdominanten Eigenvektoren als Ecken regelmäßiger konvexer 2-Polytope für Flächen und als Ecken konvexer 3-Polytope für Volumen mittels Kreispackungen. Anschließend wird mithilfe dieser Polytope eine Colin-de-Verdière-Matrix für die verallgemeinerte quadratische und eine Colin-de-Verdière-artige Matrix für die verallgemeinerte kubische B-Spline-Subdivision erzeugt. Diese Matrizen werden anschließend mithilfe des Matrixexponentials so angepasst, dass die Subdivisionsmatrizen mit den gewünschten Eigenschaften entstehen.

Alle in dieser Arbeit vorgestellten Subdivisionsalgorithmen weisen empirisch einen subdominanten Eigenwert 1/2 mit gewünschter algebraischer und geometrischer Vielfachheit auf. Für den quadratischen Fall lässt sich diese Eigenschaft sogar formal beweisen. Außerdem bilden die zugehörigen Eigenvektoren im zentralen Bereich für die verallgemeinerten quadratischen B-Spline-Subdivisionsalgorithmen ein konvexes Polytop und für die verallgemeinerten kubischen B-Spline-Subdivisionsalgorithmen bilden sie die Verfeinerung eines konvexen Polytops. Zusätzlich erfüllen die so konstruierten Subdivisionsalgorithmen eine Vielzahl weiterer Qualitätskriterien wie die der affinen Invarianz und die der konvexen Hülle. Zudem haben sie einen dominanten Eigenwert 1, respektieren alle Symmetrien der zugrundeliegenden Struktur und weisen geeignete Träger der Verfeinerungsregeln auf.

Der wissenschaftliche Mehrwert dieser Arbeit liegt in der Ausarbeitung der Qualitätskriterien und in der neuartigen Konstruktion der Subdivisionsalgorithmen mit zugehörigen Beweisen und empirischer Analyse. Speziell für verallgemeinerte kubische B-Spline-Subdivisionsflächen wird eine Alternative zum Catmull-Clark-Algorithmus mit subdominantem Eigenwert 1/2 vorgestellt. Für verallgemeinerte volumetrische B-Spline-Subdivision werden insbesondere Subdivisionsalgorithmen mit geeignetem Spektrum vorgestellt, die damit vielversprechende Kandidaten für die Anwendung sind, beispielsweise für Simulation im Rahmen der isogeometrischen Analysis. Darüber hinaus wird gezeigt, dass sich der Catmull-Clark-Algorithmus [CC78] in seiner ursprünglichen Version nicht zur Verallgemeinerung auf volumetrische Subdivision eignet und dass die etablierten Subdivisionsalgorithmen [Baj+02] und [JM99] für etliche kombinatorische Anordnungen kein geeignetes Spektrum aufweisen. Zudem werden Forschungsansätze für den volumetrischen Fall zur Verallgemeinerung von hexaedrischen auf beliebige Strukturen vorgestellt.

Die Konstruktion der Subdivisionsmatrizen wurde zudem algorithmisch in Matlab umgesetzt. Das zugehörige Softwarepaket inklusive Funktionen zur uniformen Verfeinerung und zum Plotten von Subdivisionsvolumen findet sich unter: https://doi.org/10.48328/tudatalib-1841

In this thesis, a new approach for constructing subdivision algorithms for generalized quadratic and cubic B-spline subdivision for subdivision surfaces and volumes is presented. First, a catalog of quality criteria for these subdivision algorithms is developed, serving as a guideline for the construction process.

The construction begins by generating the desired subdominant eigenvectors as the vertices of regular convex 2-polytopes for surfaces and convex 3-polytopes for volumes using circle packings. Subsequently, these polytopes are utilized to construct a Colin-de-Verdière-matrix for the generalized quadratic and a Colin-de-Verdière-like matrix for the generalized cubic B-spline subdivision. These matrices are then adjusted using the matrix exponential to obtain subdivision matrices with the desired properties.

All subdivision algorithms introduced in this paper empirically exhibit a subdominant eigenvalue of 1/2 with the desired algebraic and geometric multiplicity. For the quadratic case, this property can even be formally proven. Moreover, the corresponding eigenvectors form a convex polytope in the central region for the generalized quadratic B-spline subdivision algorithms, while for the generalized cubic B-spline subdivision algorithms, they represent the refinement of a convex polytope. Additionally, the constructed subdivision algorithms fulfill various other quality criteria, such as affine invariance and convex hull preservation. Furthermore, they possess a dominant eigenvalue of 1, respect all symmetries of the underlying structure, and exhibit appropriate support for the refinement rules. The scientific contribution of this work lies in the elaboration of the quality criteria and the novel construction of the subdivision algorithms, including corresponding proofs and empirical analyses. Specifically, an alternative to the Catmull-Clark algorithm with a subdominant eigenvalue of 1/2 is presented for generalized cubic B-spline subdivision surfaces. For generalized volumetric B-spline subdivision, subdivision algorithms with a suitable spectrum are introduced, making them promising candidates for applications such as simulations in isogeometric analysis. Furthermore, it is demonstrated that the original Catmull-Clark algorithm [CC78] is not suitable for generalization to volumetric subdivision and that the established subdivision algorithms [Baj+02] and [JM99] do not exhibit a suitable spectrum for several combinatorial configurations. Additionally, research approaches for the volumetric case are proposed, aiming to generalize from hexahedral to arbitrary structures.

The construction of the subdivision matrices was also implemented algorithmically in Matlab. The corresponding software package, including functions for uniform refinement and for plotting subdivision volumes, can be found at: https://doi.org/10.48328/tudatalib-1841