Theory and Applications of Bijective Barycentric Mappings

You are cordially invited to attend the PhD Dissertation Defense of Teseo SCHNEIDER on Monday, June 12th 2017 at 10h30 in room SI-003 (Informatics building)

Abstract:

Barycentric coordinates provide a convenient way to represent a point inside a triangle as a convex combination of the triangle's vertices, and to linearly interpolate data given at these vertices. Due to their favourable properties, they are commonly applied in geometric modelling, finite element methods, computer graphics, and many other fields. In some of these applications it is desirable to extend the concept of barycentric coordinates from triangles to polygons. Several variants of such generalized barycentric coordinates have been proposed in recent years.

An important application of barycentric coordinates consists of barycentric mappings, which allow to naturally warp a source polygon to a corresponding target polygon, or more generally, to create mappings between closed curves or polyhedra. The principal practical application is image warping, which takes as input a control polygon drawn around an image and smoothly warps the image by moving the polygon vertices. A required property of image warping is to avoid fold-overs in the resulting image. The problem of fold-overs is a manifestation of a larger problem related to the lack of bijectivity of the barycentric mapping. Unfortunately, bijectivity of such barycentric mappings can only be guaranteed for the special case of warping between convex polygons or by triangulating the domain and hence renouncing smoothness. In fact, for any barycentric coordinates, it is always possible to construct a pair of polygons such that the barycentric mapping is not bijective. In the first part of this thesis we illustrate three methods to achieve bijective mappings.

The first method is based on the intuition that, if two polygons are sufficiently close, then the mapping is close to the identity and hence bijective. This suggests to "split" the mapping into several intermediate mappings and to create a composite barycentric mapping which is guaranteed to be bijective between arbitrary polygons, polyhedra, or closed planar curves. We provide theoretical bounds on the bijectivity of the composite mapping related to the norm of the gradient of the coordinates. The fact that the bound depends on the gradient implies that these bounds exist only if the gradient of the coordinates is bounded. We focus on mean value coordinates and analyse the behaviour of their directional derivative and gradient at the vertices of a polygon.

The composition of barycentric mappings for closed planar curves leads to the problem of blending between two planar curves. We suggest to solve it by linearly interpolating the signed curvature and then reconstructing the intermediate curve from the interpolated curvature values. However, when both input curves are closed, this strategy can lead to open intermediate curves. We present a new algorithm for solving this problem, which finds the closed curve whose curvature is closest to the interpolated values. Our method relies on the definition of a suitable metric for measuring the distance between two planar curves and an appropriate discretization of the signed curvature functions.

The second method to construct smooth bijective mappings with prescribed behaviour along the domain boundary exploits the properties of harmonic maps. These maps can be approximated in different ways, and we discuss their respective advantages and disadvantages. We further present a simple procedure for reducing their distortion and demonstrate the effectiveness of our approach by providing examples.

The last method relies on a reformulation of complex barycentric mappings, which allows us to modify the "speed" along the edges to create complex bijective mappings. We provide some initial results and an optimization procedure which creates complex bijective maps.

In the second part we provide two main applications of bijective mapping. The first one is in the context of finite elements simulations, where the discretization of the computational domain plays a central role. In the standard discretization, the domain is triangulated with a mesh and its boundary is approximated by a polygon. We present an approach which combines parametric finite elements with smooth bijective mappings, leaving the choice of approximation spaces free. This approach allows to represent arbitrarily complex geometries on coarse meshes with curved edges, regardless of the domain boundary complexity. The main idea is to use a bijective mapping for automatically warping the volume of a simple parametrization domain to the complex computational domain, thus creating a curved mesh of the latter.

The second application addresses the meshing problem and the possibility to solve finite element simulations on polygonal meshes. In this context we present several methods to discretize the bijective mapping to create polygonal and piece-wise polynomial meshes.

Dissertation Committee:

• Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Michael Bronstein, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Rolf Krause, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Bert Jüttler, Johannes Kepler University Linz, Austria (External Member)
• Prof. Mirela Ben-Chen, Technion, Israel (External Member)