Towards Smooth Approximation of Triangle Meshes through the Medial Axis Transform

Download Source code: mat.zip

1. Introduction

The aim of this project is to design and implement a method that utilizes the Medial Axis Transform to approximate a given triangle mesh by a smooth G1 surface. The obtained smooth surface can then be used for an ε-Sampling of the triangle mesh where the local feature size is defined as the radius of the corresponding medial sphere. The smooth G1 surface is meant to be formed by patches of Medial Spheres connected by tangent triangles and patches of cones.

2. Implementation

During the project an algorithm following the steps below has been implemented in C++ using the CGAL library for geometry processing and Eigen library for solving quadratic equations.

For every edge in the mesh that is not on the boundary:

1. It is determined whether it is concave, convex or flat.

2. The Wing Axis is defined as the axis that lies on the bisector plane of the edge, is perpendicular to the edge and originates from the center of the edge. (See Fig.1)

3. A Medial Sphere is assigned to the edge.

· For convex or flat edges this Medial Sphere is defined as the largest inscribed sphere of the mesh that has its center on the Wing Axis and touches (not intersects) the two adjacent triangles of the edge. In cases where this medial sphere only touches the two adjacent triangles of the edge, one of the two touch points lies on another edge of that adjacent face. (See Fig.1)

· For concave edges, the sphere is defined the same way as in the convex case with the only difference being that it lies on the outside of the mesh.

This definition of a Medial Sphere for an edge is the result of careful research on how a Medial Sphere can best be assigned to an edge of a mesh. It has been chosen since it can be combined with further assignments of spheres to vertices, can be modified to capture convexity and concavity of the edge in later reconstruction steps and cannot lead to Medial Spheres with zero radius. In this implementation the Medial Sphere is found by initializing it with the largest sphere on the Wing Axis that touches both triangles and then reducing its radius (and distance from its edge) until it does not intersect the mesh. The user can set the precision of this iteration. The relevant data of the Medial Sphere (center, radius, distance to corresponding edge, touch points with faces etc. ) is stored in a map with edges as keys.

Figure 1: Definition of the (blue) Wing Axis of an edge (a, b) and location of the touch point of the Medial Sphere assigned to that edge.

4. For convex edges, the touch point of the Medial Sphere with each adjacent triangle of the edge is stored in a map with the triangle as the key. This will store three touchpoints per face which define a new triangle within the face. This new inscribed triangle is called an Intrinsic Triangle of the face.

After creating a Medial Sphere for every edge of the mesh the concave edges are iterated through. For each concave edge:

1. It is checked whether neighboring edges are convex.

2. The centers of neighboring Medial Spheres belonging to convex edges are projected onto the Wing Axis belonging to the concave edge. The set of these projections has a point with minimal distance to the concave edge. It is called m.

3. If m is closer to the concave edge than the center of the Medial Sphere of the concave edge, the center of the Medial Sphere is set to m and its radius is reduced accordingly.

This reduction of radii for concave spheres ensures that in a later step the Medial Spheres can be connected to form a smooth G1-surface, approximating the mesh such that the contributing patch of this Medial Sphere is a concave neighborhood of the G1 surface.

After reducing the concave spheres in the last step, neighboring spheres had to be connected through tangent triangles. This means a new triangle mesh has to be formed with Medial Spheres as vertices. This step turned out to be very complicated. Even though extensive research was conducted on mathematical concepts that could allow this, no solution has been found yet for this problem. The already mentioned Intrinsic triangles each provide a G1 connection between some spheres: For every face of the original triangle mesh that is bounded by three convex edges an Intrinsic triangle exists that is tangent to the Medial Spheres of the face edges. In the next step we want to find tangent triangles of the Medial Spheres that belong to the ring of outgoing edges around a vertex. These triangles are called Extrinsic Triangles since there is no canonic triangulation scheme that derives from the structure of the mesh for this case. See Fig. 2 for a schematic sketch of tangent Intrinsic and Extrinsic triangles. See next section (Calculating tangent triangles for three spheres) for details on finding the tangent triangles of three spheres.

Figure 2: Intrinsic Triangles (blue) and Extrinsic Triangles (red) tangent to the spheres associated with the ring of outgoing edges around a vertex.

To find Extrinsic Triangles, the following scheme has been implemented:

For every inner vertex of the mesh the Medial Spheres of its incident edges are considered (called the Medial Sphere ring):

1. The centroid of the centers of these Medial Spheres is calculated.

2. The line through the center vertex and the centroid is calculated.

3. For every center of the Medial Spheres of the vertex ring its projection onto this line is calculated

4. Now the following triangulation scheme is applied:

a. Starting with the sphere with the smallest such projection we consider four consecutive spheres (s0, s1, s2, s3) in the Medial Sphere ring. (If the ring has only three spheres the task is trivial.)

b. The tangent triangles of s0, s1, s2 and s1, s2, s3 are calculated.

i. If the tangent triangles (s0, s1, s2) and (s1, s2, s3) have an angle smaller than 90 degrees (our selection criterion) the tangent triangle (s0, s1, s2) is saved as an Extrinsic Triangle. s1 is excluded from further consideration in the scheme and the scheme restarts with s1, s2, s3, s4 to find the next Extrinsic Triangle.

ii. If the tangent triangles of s0, s1, s2 and s1, s2, s3 have a dihedral angle greater than 90 degrees we save this angle and try the triangles (s1, s2, s3) and (s2, s3, s4) and so on.

c. If after a full cycle through the Medial Sphere ring no tangent triangle matched our criterion, we save the tangent triangle that has smallest dihedral angle with its next neighbor as an Extrinsic Triangle (s_i, s_j ,s_k). s_j is removed from further considerations in the triangulation scheme.

d. If looping through the Medial Sphere ring did not find any triangle matching our criterion, we save the triangle with smallest dihedral angle to its next neighbor as an Extrinsic Triangle (s_i, s_j ,s_k). If no neighboring triangle pairs exist, we save the first tangent triangle that could be found as an Extrinsic Triangle (s_i, s_j ,s_k). s_j is removed from further considerations in the triangulation scheme.

e. If during this cycle we encounter three consecutive spheres s_i, s_j ,s_k that have no tangent triangle, we remove s_j from this triangulation process.

f. The scheme is restarted with the reduced Medial Spheres ring until no more triangles are found or the whole Medial Spheres ring is triangulated.

In many scenarios this triangulation scheme fails in completely triangulating the Medial Spheres ring. (See sections Results and Discussion)

As a final step the Medial Spheres are triangulated and together with the tangential Extrinsic and Intrinsic Triangles written to a mesh for rendering of the results.

3. Calculating tangent triangles for three spheres

The problem of finding the tangent triangles of three given oriented spheres is solved with a common approach using Lie Sphere Geometry. The term “oriented” in this case refers to a Medial Sphere belonging to a convex or concave edge. (Medial Spheres of concave edges are assumed to have their normal pointing inward). In general, there are two oriented tangent planes for three oriented spheres or none at all. The planes are the solutions of a quadratic equation which is solved using the Eigen library. Medial Spheres of concave edges lie on one side of each plane, Medial Spheres of convex edges on the other side. Each plane has one touch point with each sphere thus the two tangent planes yield two tangent triangles. We choose the triangle whose touchpoint with one of the three Medial Spheres lies closer to the associated edge than the other triangle’s touchpoint with this Medial Sphere. This condition will then automatically be fulfilled for the other two Medial Spheres as well. This way we find a tangent triangle that ensures that, when connected with the Medial Spheres to form G1 surface, the Medial Sphere patch it touches is convex / concave if the associated edge is convex / concave.

4. Results

Images of the obtained Medial Spheres with Intrinsic and Extrinsic Triangles are shown in the figure below.

Figure 3: Left: the original mesh, center: the Medial Spheres of convex (white) and concave (green) edges with tangent Intrinsic (blue) and Extrinsic (red) Triangles, right: a close-up revealing tangent Extrinsic Triangles intersecting other tangent triangles.

The results show that the algorithm delivers a good approximation of the shape through Medial Spheres while in many places no tangent Extrinsic Triangles could be found or they intersect other triangles, which is not desirable . Therefore, this method for finding tangent triangles needs to be extended by a fix these cases.

5. Discussion and future work

The results show that the chosen approach cannot yet deliver the desired result of a smooth surface made from patches of Medial Spheres, Intrinsic and Extrinsic Triangles since the Extrinsic Triangles intersect other triangles and, in many cases, no Extrinsic Triangle can be found at all, leaving many gaps. The reason for this remains to be found. Maybe further reduction of the size of Medial Spheres of concave edges helps. Maybe another approach for connecting all Medial Spheres through tangent triangles must be chosen or even the concept of assigning a Medial Sphere to every edge has to be abandoned or modified. A different approach for finding tangent Extrinsic Triangles could be to keep the tangent Intrinsic Triangles and introduce auxiliary Medial Spheres at vertices to prevent intersection of Extrinsic Triangles. If the current approach cannot be modified to yield non-intersecting tangent triangles connecting all Medial Spheres to a new mesh it might be helpful to introduce a different scheme for creating Medial Spheres, e.g. assigning one Medial Sphere to every face. Once this issue has been solved, another problem remains to be solved. The tangent triangles and sphere patches must be connected through smooth ruled surfaces. For three Medial Spheres that belong to only convex or only concave edges this is possible with cone patches. For a set of Medial Spheres that belong to convex and concave edges, the connecting surface patch cannot be a cone as depicted in the figure below.

Figure 4: The Medial Sphere S0 belongs to a convex edge while S2 belongs to a concave edge. A ruled surface patch is required that contains the tangential triangle edges A and B and is tangential to S0 and S2. This surface patch will have positive mean curvature where it touches S0 and negative mean curvature where it touches S2. Thus, it cannot be a cone.

More generally it also remains an open question whether it is possible to assign a Medial Sphere to every edge or every face of an arbitrary triangle mesh, such that the Medial Spheres can be connected by non-intersecting tangential triangles forming a water-tight mesh where the Medial Spheres are vertices and the tangential triangles are faces. This would mean that the Medial Spheres must be arranged in such a way that the setup in the figure below can always be avoided when building the tangent triangles.

Figure 5: A setup of three Medial Spheres S0,S1,S3 of convex edges and one Medial Sphere S2 of a concave edge where non-intersecting tangential Extrinsic Triangles do not exist