Marching Chains algorithm for Alexandroff-Khalimsky spaces
Xavier Daragon, Michel Couprie, Gilles Bertrand · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2002
The Marching Cubes algorithm is a popular method which allows the rendering of 3D binary images, or more generally of iso-surfaces in 3D digital gray-scale images. Yet the original version does not give satisfactory results from a topological point of view, more precisely the extracted mesh is not a coherent surface. This problem has been solved in the framework of digital topology, through the use of different connectivities for the object and the background, and the definition of ad-hoc templates. Another framework for discrete topology is based on an heterogeneous grid (introduced by E.D. Khalimsky) which is an order, or a discrete topological space in the sense of P.S. Alexandroff. These spaces possess nice topological properties, in particular, the notion of surface has a natural definition. This article introduces a Marching Chains algorithm for the 3D Khalimsky grid H3. Given an object X which is a subset of H3, we define, in a natural way, the frontier of X which is also an order. We prove that this frontier order is always a union of surfaces. Then we show how to use frontier order to design a Marching Cubes-like algorithm. We discuss the implementation of such an algorithm and show the results obtained on both artificial and real objects.