DGtal
1.3.beta

Part of the Topology package.
This part of the manual describes how to define digital surfaces, closed or open. A lot of the ideas, concepts, algorithms, documentation and code is a backport from ImaGene [53]. Digital surfaces can be defined in very different way depending on input data, but they can be manipulated uniformly with class DigitalSurface, whichever is the dimension. Note that the topology within digital surfaces is computed onthefly. Since 0.9.4, one can precompute the topology of a 3D digital surface with class IndexedDigitalSurface. In some usages (typically local traversals), this can speedup algorithms up to three times faster.
The following programs are related to this documentation: volToOFF.cpp, volMarchingCubes.cpp, volScanBoundary.cpp, volTrackBoundary.cpp, frontierAndBoundary.cpp, volBreadthFirstTraversal.cpp, trackImplicitPolynomialSurfaceToOFF.cpp, areaestimationwithdigitalsurface.cpp, areaestimationwithindexeddigitalsurface.cpp
Although continuous surfaces are well defined as nmanifolds, a digital or discrete analog of surface is more tricky to define. Several methods have been explored to define consistent digital surfaces. We mention three approaches here.
We focus here on the last method to define digital surfaces.
Formally, the elements of the digital space \( Z^n \) are called spels, and often pixels in 2D and voxels in 3D. A surfel is a couple (u,v) of faceadjacent voxels. A digital surface is a set of surfels. It is obvious that a spel is a ncell in the cellular grid decomposition of the space, while a surfel is clearly some oriented n1cell which is incident to the two ncells u and v (see Cellular grid space and topology, unoriented and oriented cells, incidence).
Let s be some surfel. It is incident to two oriented voxels. By convention, its interior pixel is the one that is positively oriented.
We assume from now on that you have instantiated some cellular space K of type KSpace (see dgtal_ctopo_sec4), for instance with the following lines:
A surfel is an oriented \(n1\)cell, i.e. some SCell. Surfel may be obtained from spels by incidence relation. Reciprocally, you can use incidence to get spels.
The direct orientation to some cell s is the one that gives a positively oriented cell in the boundary or coboundary of s.
You may now for instance define the digital surface that lies in the boundary of some digital shape \( S \subset Z^n \) as the set of oriented surfels between spels of S and spels not in S. Algebraically, S is the formal of its positively oriented spels, and its boundary is obtained by applying the boundary operator on S.
Defining a digital surface as a set of surfels is not enough for geometry. Indeed we need to relate surfels together so as to have a topology on the digital surface. The first step is to transform the digital surface into a graph.
The idea here is to connect surfels that share some \(n2\)cells. The obtained adjacency relations are called bel adjacencies in the terminology of Herman, Udupa and others. Generally an \(n2\)cell is shared by at most two \(n1\)cells, except in "cross configuration", symbolized below:
O  X X: interior spels O a X  +  O: exterior spels b + c X  O  and : surfels a,b,c,d X d O +: n2cell
A bel adjacency makes a deterministic choice to connect b to d and a to c when interior, and b to a and c to d when exterior. This choice has to be made along each possible pair of directions when going nD. In DGtal, this is encoded with the class SurfelAdjacency.
The following snippet shows the interior surfel adjacency (i.e. (6,18)surfaces).
Once the adjacency has been chosen, it is possible to determine what are the adjacent surfels to a given surfel. More precisely, any surfel (or \(n1\)cell) has exactly \(2n2\) adjacent surfels (for closed surfaces). More precisely, it has exactly 2 adjacent surfels along directions different from the orthogonal direction of the surfel.
In fact, we can be even more precise. We can use orientation to orient the adjacencies consistently. Given two surfels sharing an \(n2\)cell, this cell is positively oriented in the boundary of one surfel and negatively oriented in the boundary of the other. We have thus that there are \(n1\) adjacent cells in the direct orientation (positive) and \(n1\) adjacent cells in the indirect orientation (negative). The direct adjacent surfels look like:
The class SurfelNeighborhood is the base class for computing adjacent surfels. You may use it as follow, but generally this class is hidden for you since you will have more highlevel classes to move on surfaces.
Generally, methods SurfelNeighborhood::getAdjacentOnSpelSet, SurfelNeighborhood::getAdjacentOnDigitalSet, SurfelNeighborhood::getAdjacentOnPointPredicate, SurfelNeighborhood::getAdjacentOnSurfelPredicate are used to find adjacent surfels.
Since we have defined adjacencies between surfels on a digital surface, the digital surface forms a graph (at least in theory).
This section shows how to extract the boundary of a digital set, given some predicate telling whether we are inside or outside the surface.
Given a domain and a predicate telling whether we are inside or outside the object of interest, it is easy to determine the set of surfels by a simple scanning of the space. This is done for you by static methods Surfaces::uMakeBoundary and Surfaces::sMakeBoundary.
The following snippet shows how to get a set of surfels that is the boundary of some predicate on point by a simple scan of the whole domain (see volScanBoundary.cpp).
In many circumstances, it is better to use the above mentioned graph structure of digital surfaces. For instance it may be used to find the surface just by searching it by adjacencies. This process is called tracking. This is done for you by static method Surfaces::trackBoundary.
The following snippet shows how to get a set of surfels that is the boundary of some predicate on point given only a starting surfel and by tracking (see volTrackBoundary.cpp).
On the lobser.vol volume, volScanBoundary.cpp extracts 155068 surfels in 3866ms, while volTrackBoundary.cpp extracts 148364 surfels in 351ms.
# Commands $ ./examples/topology/volScanBoundary ../examples/samples/lobster.vol 50 255 $ ./examples/topology/volTrackBoundary ../examples/samples/lobster.vol 50 255
In the case you know beforehands that your surface is closed (i.e. without boundary), you should use preferentially Surfaces::trackClosedBoundary. This technique only follows direct adjacent surfels and extracts the whole surface when it is closed. This process can be illustrated as follows:
You can have a look at page Helpers for digital surfaces to see how to construct directly a 2D contour in \( Z^2 \), how to get the set of surface components, how to get 2D contours as slices onto a 3D surface.
You may also use the template class DigitalSurface2DSlice, which, given a tracker on a digital surface, computes and store a 2d slice on the associated surface. You may after visit the slice with iterators or circulators.
Digital surfaces arise in many different contexts:
Since there are so many digital surfaces, it is necessary to provide a mechanism to handle them generically. The class DigitalSurface will be the common proxy to hide models of concepts::CDigitalSurfaceContainer.
Since there may be several types of digital surfaces, there are several container classes for them. All of them follow the concept concepts::CDigitalSurfaceContainer. Essentially, a model of this class should provide methods begin() and end() to visit all the surfels, and a Tracker which allows to move by adjacencies on the surface. A Tracker should be a model of concepts::CDigitalSurfaceTracker. The architecture is sumed up below:
For now, the implemented digital surface container are (realization of concepts::CDigitalSurfaceContainer):
Depending of what is your digital surface, you should choose your container accordingly:
Light versions of containers should be preferred in mostly two cases:
The following snippet shows how to create a digital surface associated to a LightImplicitDigitalSurface. The LightImplicitDigitalSurface is connected to a shape described by a predicate on point (a simple digital set). The full code is in volBreadthFirstTraversal.cpp.
Once this is done, the object digSurf
is a proxy to your container. Here the dynamically allocated object is acquired by the digital surface, which will take care of its deletion.
Any DigitalSurface is a model of concepts::CUndirectedSimpleGraph (a refinement of concepts::CUndirectedSimpleLocalGraph). Essentially, you have methods DigitalSurface::begin() and DigitalSurface::end() to visit all the vertices, and for each vertex, you obtain its neighbors with DigitalSurface::writeNeighbors. You may thus for instance use the class BreadthFirstVisitor to do a breadthfirst traversal of the digital surface.
We may extract the whole surface by doing a breadthfirst traversal on the graph. The snippet below shows how to do it on any kind of digital surface, whatever the container.
Here, we only use it to get the maximal distance to the starting bel. A second pass could be done to display cells with a color that depends on the distance to the starting surfel.
We may call it as follows
# Commands $ ./examples/topology/volBreadthFirstTraversal ../examples/samples/lobster.vol 50 255 $ ./examples/topology/volBreadthFirstTraversal ../examples/samples/Al.100.vol 0 1 $ ./examples/topology/volBreadthFirstTraversal ../examples/samples/cat10.vol 1 255
to get these pictures:
Surfels of a digital surface can also be defined by a predicate telling whether or not some surfel belongs to it. Given an image of labels, the class functors::BoundaryPredicate and functors::FrontierPredicate are such predicates:
l
while the exterior spel of s has label different from l
.l1
while the exterior spel of s has label l2
.Using container ExplicitDigitalSurface, we can very simply define digital surfaces that are connected boundary of frontiers in some image. The following snippet is an excerpt from frontierAndBoundary.cpp.
Running it give the pictures:
We have shown before that a digital surface has a dual structure that is the graph whose vertices are n1cells and whose arcs are (almost) n2cells. We can go further and use n3cells to define faces on this graph. This is related to the concept of umbrellas in 3D (see [80]). More precisely, given a start surfel, an incident n2cell (the separator) and an incident n3cell (the pivot), one can turn around the pivot progressively to get a face. This gives precisely in 3D the dual to a digital surface that is a kind of marchingcube surface (see [57], [58]).
The main class for computing umbrellas is the class UmbrellaComputer. Turning around the pivot means moving the face and the separator once (in the track direction), such that the pivot is the same (ie +p), the track and separator directions being updated. Repeating this process a sufficient number of times brings the umbrella back in its original position, except in the case when the DigitalSurface has a boundary touching the pivot. You may use it to compute umbrellas given a tracker on your surface.
You may look at file testUmbrellaComputer.cpp to see how to use this class directly.
However, it is simpler to use directly the methods defined in DigitalSurface. It offers three types: DigitalSurface::Vertex, DigitalSurface::Arc, DigitalSurface::Face to get the combinatorial structure of the surface. An arc is an oriented edge, a face is a sequence of edges that is closed when the pivot is not on the boundary and open otherwise.
The following code lists the faces of a DigitalSurface object, and for each face it lists the coordinates of its vertices.
DigitalSurface provides you with many methods to get faces from edges or vertices and reciprocally.
In 3D, you may use faces to transform an arbitrary digital surface into a polygonal manifold (closed or open). You can for instance directly the method DigitalSurface::exportSurfaceAs3DOFF to do so, or look at its code to see how it works.
The following snippets of file volToOFF.cpp show how to extract all surfels in an image and then how to export the surface in OFF format. The output is a surface that is very much the classical marchingcube surface, except that vertices lies in the middle of the edge.
Digital surfaces are built upon digital surface containers. Although containers may be very differnt, digital surfaces provide a uniform interface to visit them and to explore their topology. But they are merely just an interface. Hence neighbors, umbrellas, and sometimes even vertices are recomputed onthefly as needed.
In some cases, it is a better idea to compute the topology once and for all and to store it as fixed arrays. This is the purpose of class IndexedDigitalSurface.
Similarly to a DigitalSurface, one creates an IndexedDigitalSurface with a model of digital surface container (concepts::CDigitalSurfaceContainer). The following snippet creates it from a DigitalSetBoundary (the boundary of a ball of radius 3 here).
Once the indexed surface is created, you may use it as a DigitalSurface. First it is a model of graph (concepts::CUndirectedSimpleGraph). Hence traversal operations and visitors apply. The main difference is that vertices, arcs and faces are now numbered consecutively starting from 0. Therefore you have methods to get a surfel from its vertex index, a linel from its arc index, a pointel from its face index.
An indexed digital surface associates positions to its vertices (see IndexedDigitalSurface::position and IndexedDigitalSurface::positions).
Then, most the services of DigitalSurface described in The digital surface graph is a combinatorial manifold are available in IndexedDigitalSurface.
The following services are also provided:
You should use an IndexedDigitalSurface when:
You should use a DigitalSurface when
Examples areaestimationwithdigitalsurface.cpp and areaestimationwithindexeddigitalsurface.cpp illustrate the similarities of classes DigitalSurface and IndexedDigitalSurface as well as their slight differences. They show how to estimate the area of a digital sphere.