In numerous fields, non-invasive acquisition devices are required for observation, measurements or diagnostic aids. Those acquisition devices usually generate volumic data, i.e., 3D images, composed of regularly spaced data in a cuboidal domain. 3D volumes are voxel sets obtained from the segmentation of those 3D images. They are also generated in scientific modeling because numerous simulation schemes rely on the regularity of the data support.

The boundaries of 3D volumes are also called digital surfaces. They are only made up of unit square faces whose normal vector is parallel to an axis. As a consequence, they do not directly provide a relevant normal vector field, which is however required for many tasks in computer graphics, vision and 3D image analysis. In this talk, we will review a new class of algorithms that can be used to estimate a normal vector field or reconstruct a polygonal surface from a digital surface.

Plane-probing algorithms compute a normal vector from a starting element and a membership predicate: "is x in the surface?". That predicate is used to probe the surface as locally as possible and decide on-the-fly the next elements to consider, based on arithmetic and geometric criteria. Those algorithms are indeed closely linked to three-dimensional continued fraction algorithms on one hand and to 3D Delaunay triangulations on the other hand. Contrary to most of the other estimation methods, those algorithms require no parameter and present theoretical guarantees, e.g., they extract the exact normal vector of any digital plane. However, we will see that questions remain in order to process arbitrary digital surfaces and especially their non-convex parts.