# 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

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.