EuroGIGA_Medial Axis Computation

The planned research in this project focuses on the two topics of medial axis computation and approximations of the signed distance function, which are naturally related. The medial axis, which was introduced by Blum in 1967, provides an efficient way for shape description. It has found applications in numerous scientific areas, ranging from shape recognition in Computer Vision to offset curve and surface trimming in Computer-Aided Design. The highly non-trivial task of fast and stable computation of the medial axis of a given free-form shape is of vital interest. Recently we formulated a novel algorithm for medial axis computation in the plane, which was shown to be efficient and to be accessible for a geometrically robust implementation. We were able to prove that the medial axes of arbitrary planar domains can approximately be computed (with a convergence guarantee) by considering domains with (suitably defined) piecewise circular boundaries. In this project we plan to extend these results to three-dimensional domains. We are currently working on the robust computation of the medial axis of domains with triangulated boundaries with respect to piecewise linear approximations of the Euclidean metric. While this ongoing-research has already produced promising results, it has also led to a number of challenging open problems. These include the possibility of obtaining an efficient algorithm (e.g., by using a Divide-and-Conquer-type approach) and the identification of the most stable part of the medial axis. In order to deal with the issue of robustness, we will also explore the novel approach of considering the medial axis computation in the framework of inverse problems. This general framework allows to derive stable solutions for ill-posed problems, where the unknown object is to be computed from (possibly noisy) observations / data. The data and the unknown object are linked by an operator. In order to use this approach, we plan to identify each object with its signed distance function, which can be recovered nicely from the medial axis transformation (MAT), i.e., from the centers and radii of the maximum inscribed balls. As a related application of the close connection between maximal inscribed balls and the oriented distance function we will consider the challenging problem of 3D object reconstruction from noisy point cloud data. In this context we plan to use approximations of the signed distance function that are obtained by considering a relatively small number of maximal balls, corresponding to a subset of the vertices in the Voronoi diagram. Based on these approximations, we will derive correctly oriented normal vectors associated with the data and use them to define the boundary surface.

The work in this subproject was divided into three main topics. The first part is dedicated to descriptors for solid objects. To begin with, we introduced a new algorithm to compute a topological skeleton called the Reeb graph. As opposed to existing algorithms, we only use a boundary mesh of the object as an input, not a full volume description. This leads to substantial computational advantages for two reasons. On the one hand, a surface representation requires typically a smaller data volume than a volumetric representation. On the other hand, in many cases only the surface of the object is known. In this case, we can avoid the expensive construction of a full volume representation. Some restrictions to the general set-up are necessary to allow this construction. For a very special choice, however, the presented algorithm is used in the simulation of dip-coating processes in automotive industry. As an extension of the Reeb graph, we explored the Reeb space. While the Reeb graph is defined using one function on the area of interest, the Reeb space considers two or more functions. The Reeb space of a solid object induces a skeletal structure of the object. It consists of connected surface patches inside the object, which span the basic structure of the object. Other such skeletal structures are defined in the literature, for example the medial axis. While the medial axis has some very nice characteristics, its computation in the three-dimensional case is very expensive. Therefore, the Reeb space may serve as a more efficient alternative. We introduced a first algorithm to compute an abstract representation of the Reeb space, which we call the layered Reeb graph. Like for the Reeb graph, our algorithm uses only a boundary description of the given shape. In the second part of this work, we introduce a new distance measure in the plane. As an input, it takes known distances between some given sites, like the travel times between certain cities. By using an embedding into higher-dimensional space, this input is used to generate a global distance measure. In the example, this measure approximates the travel times between any two cities, also for cases where no travel times were given in the input. In the third part, we considered the medial axis of planar domains. It gives a skeleton of the area of interest, consisting of several connected curve-segments which represent the basic structure of the domain. If the area of interest has a very rugged boundary curve, however, the medial axis contains much more branches than it would be necessary to describe its basic shape. We present an algorithm which smoothes the boundary curve in a specifically suitable way before computing the medial axis, thereby reducing the number of superfluous branches of the medial axis drastically.