Page - 65 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

Mesh quality. An important aim is to keep mesh quality high, since this is needed for the finite element simulation to work. A high mesh quality means that the tedrahedra are non-degenerate, disjoint, and that there is only a small number of very flat tetrahedra. The latter is important since many flat tetrahedra would cause numerical problems in the simulations. Our assumption is that the quality of the original mesh is sufficiently high, therefore we design the constraints such that the movementofthenodesdoesnotsignificantlyworsenmeshquality. Inparticular,wewanttoguarantee that noself-intersection of the surfacesof the tetrahedraoccurs. Convexity of Ω. Convexity yields several advantages in optimisation, such as allowing to apply a large range of optimisation methods and ensuring that indeed global optima are approximated. Thus, we aim to define constraints which can be represented as a family of point constraints given in a way that the set of admissiblepoint-coordinates is convex. Insummary, toachievethebest resultswithourmethod,welookforaconvexsetofconstraintswhich allowssufficientmovementof thenodeswhilemaintainingahighmeshquality. Adaptive constraints. We define Ω by fixing an individual radiusri for each nodevi, and allowing the node only to move within a ball of this radius centered at its original location. Our approach to choose ri is as follows: Let us fix a surface vertex v in a tetrahedronT. Since the goal is to avoid degenerate tetrahedra,onemust inparticularpreventself-intersection. Geometrically interpreted, this means thateachof thenodesmustnotpass to theoppositesideofT. Thismotivates the incorporation of the heights on the nodes inT. Indeed, if the other nodes did not change, the distance of v to the opposite side ofT would be determined by the corresponding heighth of the tetrahedron and one could use h as a limitation on how far the vertex is allowed to move. But since the movement of the other points of the tetrahedron also affects this consideration, and since the node v is not only a node ofT, but of several neighbouring tetrahedra, we use all heightsh of all tetrahedra containing v to define the constraints. Indeed, for a fixed node vi, we denote byhT the minimum of the four heights of a tetrahedronT and hˆi = min{hT : vi contained inT}. We limit the movements ofvi by αhˆiwith a parameter 0<α< 1/2, which is expected to ensure that, even though all nodes move simultaneously, no self-intersections occur. Letu0i denote the original coordinates of the vertex vi. Thus, thecorresponding radii and the resulting feasible sets aregivenby ri=αhˆi with hˆi= min{hT : vi∈T}andhT = min{h:hheightofT}, (3) Ω ={u∈U : ‖ui−u0i‖≤ ri for i= 1, . . . ,N}. (4) Thisensures thatnoself-intersectionoccursandmeshquality ismaintained. Figure1 illustrates such constraints for the case of 2D triangles. In the three-dimensional setting, also the interior vertices adjacent to the surfaceof themesh will be incorporated in thecomputationofconstraints. 4. Numerical solution The aim in this section is to describe an algorithmic framework for the solution of (2) with Ω as in (4). For this purpose, we will use the primal-dual algorithm described in [5], which is an iterative method that allows to solve convex-concave saddle-point problems with non-smooth structure. A non-smooth optimisation method is required to incorporate the proposed point constraint, however, due to differentiability of the graph-Laplacian regularisation and simplicity of the feasible set, also othermethods, suchas FISTA[1], could beused. 3 65