Delaunay cutting in triangle meshes

Cuts in 2D

Our previous idea for making cuts in meshes was flawed: flattening cut surfaces unconditionally easily leads to flattened elements. In our recent work, we try to use bona fide meshing techniques to come to a quantifiably better result. Cuts in 3-dimensional meshes are the end-target, but since 3-dimensional meshing is much harder, our first target was to try and produce nice cuts in 2-dimensional meshes, i.e. triangulations. A paper describing these results for triangulations has been accepted at WAFR2002.

In two dimensions, the standard technique for producing high quality triangulations is the Delaunay triangulation. For a given set of points, it computes the triangulation that has a minimum angle as large as possible. The attractive property of the Delaunay triangulation is that can be computed locally by means of edge-flips: points are inserted one by one, and by flipping edges around the inserted points, the triangulation is improved.

We don't have point insertions, instead, our points are moving, reflecting the progression of a cut. We employ edge-flips to update the triangulation around a moving node. On a small scale, this is demonstrated in the following diagram:

A picture of how this works on a larger scale is shown here. On the left, the boundary of the mesh is shown, and the dotted line shows the trajectory of the `scalpel'. On the right, all the triangles of the mesh are shown.

This approach is measurably better than subdivision: it produces less triangles, and the triangles have better shapes. If you want to try it out yourself, then you can find the 2D version over here.

Surfaces in 3D

This technique can also be generalized to 3-dimensional surfaces. In this case, the technique is less elegant, since flips change the shape of the surface. Nevertheless it gives a very satisfactory performance. A big complication is that in 3 dimensions, different incisions of the same surface may interact, leading to branches and annihilations. In the following picture, the scalpel (in red) hits a fold in the surface, and the cut branches into three incisions.

Here are two pictures showing a self-intersecting cut. The circle-shaped cut was started with a bifurcation.

Some animations of the process are available

A cut did not handle self-intersecting paths or multiple incisions. (here )
An path with self-intersecting paths and multiple incisions ( here).

The software that made this pictures is available here.

Cutting in tetrahedral meshes

For tetrahedral meshes, the situation is considerably more difficult. The Delaunay triangulation does generalize to higher dimensions, but it produces meshes that have so-called slivers (i.e. flat elements), and constructing them is much harder, let alone updating them.

GIVE > Virtual Environments > Virtual Surgery > Delaunay cutting in triangle meshes