A 3D hole closing algorithm

Involved people : Zouina Aktouf, Gilles Bertrand, Laurent Perroton.

A hole in a 3D object is not a region of space, as one can be convinced some by considering a full torus, which is an object comprising a single hole (see also the examples of the fig. ). Intuitively, the presence of a hole in an object can be characterized by the existence of a closed loop included in the object, and not being able to be transformed continuously into a single point, while remaining in the object.

To close holes in 3D objects is thus not a commonplace problem, in particular it is not possible to use, as in 2D, the connected component marking algorithms.

Based on the studies which we made on the topology of Z ³, we propose a method to close holes in a 3D object. Furthermore, this method allows us to control the "size" of the holes to be closed (fig. ). It works in linear time. To our knowledge, it is the first method to solve this problem [ ABP96 ].

The basic idea of the method consists in plunging the object X in which one wants to close the holes, in another object Y connected and without hole, such as a cube for example. One repeatedly thins Y by removing from it the points not belonging to the object X, and by making sure that the removal of these points does not create a hole. This test is carried out using the topological numbers (see above). In order to obtain a result which is "well centered" on the object X, we guide the thinning process by a distance map. This distance information allows us to select the holes that will be closed, according to a "size" criterion (see Figure 8 and Figure 8b).

Figure 8: Illustration of the 3D hole closing algorithm
Figure 8b: View (animation) of the hole closing process.