Digital surfaces and singular surfaces

( J.-O. Lachaud , Stéphane Simon )

Digital surfaces are sets of surfels with specific properties. For instance, the boundary of a set of voxels in 3D (defined as the cube faces that separates object voxels from background voxels) is a digital surface. Digital surfaces are defined in arbitrary dimension and can be seen as n-1-cells in the cubic cellular decomposition of Rn.
Digital surfaces can be used to extract isosurfaces in images. They can also be used to approach implicit surfaces by tracking changes of sign of the implicit surface. They can be efficiently implemented in arbitrary dimension. We are currently investigating the extraction of singular surfaces with digital surfaces and cubical complexes.

Efficient and generic implementation of digital topology algorithms

Digital objects, digital surfaces and other digital subsets can be modeled as subsets of some extended cartesian grid Zn, sometimes called cartesian complexes, subsets of Khalimsky space, subsets of the cubic regular cell decomposition of the Euclidean space. We have proposed an efficient technique to model cells, sets of cells, in arbritrary dimension, and implemented a lot of digital topology and geometry algorithms: digital surface tracking, isosurface reconstruction, geometric estimators.

[ Lachaud07b , Lachaud03c Lachaud03b , ]

Extraction of singular surfaces

A lot of surfaces are defined implicitly (meaning as the set of solution to some equation f(x,y,z)=0). Standard extraction and visualization algorithms rely on the change of sign around 0 to numerically determine a geometric model that approaches this set. It is clear however that the set f2(x,y,z)=0 being the same, it is a digital surface. It is also straightforward to see that one cannot rely on any change of sign to locate it. There are more complex examples, even with algebraic surfaces. This class of problematic surfaces is often called singular surfaces, and it is difficult to extract their singularities, ie places where the gradient is also nul. Such places may be 0-dimensional, 1-dimensional, or 2-dimensional. The following example shows simple implicit surfaces and their reconstruction with Maple.

Sphere Whitney's Umbrella Four lines example
f(x,y,z)=x^2+y^2+z^2-1 f(x,y,z)=x^2-y^2*z f(x,y,z)=x*y*(y-x)*(y-x*z)

We are developing an original technique for extracting singular surfaces, which combines digital surfaces in Z4 and digital surface tracking, cubical complexes, collapses, and projections. The following steps computes it.

Some examples are given below. The meshing algorithm correctly detect singularities of implicit surfaces. The handle of Whitney's umbrella is detected {z<0, x=y=0}, as well as the intersection of two sheaves around {z>=0, x=y=0}.

Sphere Whitney's Umbrella Four lines example
f(x,y,z)=x^2+y^2+z^2-1 f(x,y,z)=x^2-y^2*z f(x,y,z)=x*y*(y-x)*(y-x*z)
We give below a few other examples. On the left column, it is the extracted set {F=0} inter {t=0}. Middle left column represents these sets after collapse. Middle right column after projection with Newton-Raphson. Right columns show a raycasting rendering of the surface (taken from here, very nice but no reconstruction).
Implicit surface Cubical complex {F=0} inter {t=0} After collapse After projection Raycasting rendering
Whitney umbrella f(x,y,z)=x^2-y^2*z
Crixxi f(x,y,z)=(y^2+z^2-1)^2 +(x^2+y^2-1)^3 = 0
Buggle f(x,y,z)=x^4y^2+y^4x^2-x^2y^2+z^6 = 0

Lachaud07b , Lachaud03c , Lachaud03b