A New Approach to the Construction of Subdivision Algorithms. English Translation of the Dissertation: Ein neuer Ansatz zur Konstruktion von Subdivisionsalgorithmen

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