Isabelle Sivignon
email: sivignon@lis.inpg.fr

Florent Dupont
email: florent.dupont@liris.cnrs.fr

Jean-Marc Chassery
email: chassery@lis.inpg.fr

Reversible Polygonalization of a 3D Planar Discrete Curve: Application on Discrete Surfaces

Reversible polyhedral modelling of discrete objects is an important issue to handle those objects. We propose a new algorithm to compute a polygonal face from a discrete planar face (a set of voxels belonging to a discrete plane). This transformation is reversible, i.e. the digitization of this polygon is exactly the discrete face. We show how a set of polygons modelling exactly a discrete surface can be computed thanks to this algorithm.

Introduction

Since a few years now, many methods have been proposed in order to compute a polyhedral representation of a discrete object, or more precisely of its surface. Indeed, such a transformation has many useful properties such as:

a compression of the discrete data: a polyhedral representation suppresses the redundancy of the discrete representation; modelling of the discrete object better visualization, . . . Two kinds of reconstruction exist: either we only need an approximation of the discrete surface, or the reversibility of the transformation is desired.

A first naive method consists in computing the convex hull of the discrete points composing the discrete object. This approach simply needs an efficient convex hull algorithm, which is a very well known problem (see [START_REF]Qhull[END_REF] for instance). Nevertheless, the polyhedral surface reconstructed is close to the discrete object only in case of convex, or nearly convex objects.

The Marching-Cubes algorithms [START_REF] Lorensen | Marching cubes: a high resolution 3D surface construction algorithm[END_REF][START_REF] Kenmochi | Polyhedra generation from lattice points[END_REF] are the most popular methods to get a polyhedral (triangulated in this case) surface from a discrete object. This transformation is reversible along a classical digitization scheme (OBQ). Nevertheless, this construction is based on local configurations: this induces that the number of faces of the polyhedral surface depends directly on the number of surface voxels of the discrete object. In order to compute a surface composed of a number of faces not related to the number of discrete points, a global study of the discrete object geometry is needed.

Then, another class of methods is based on the following outline: first, the discrete object surface is decomposed into pieces of discrete planes, and second, a polyhedral representation of the discrete object based on those discrete faces is computed. Such a framework has been used for instance by Borianne and Françon in [4] where a pair digitization/reconstruction is proposed. The authors conjecture that this pair defines a reversible transformation, but this has not been proven yet. In [START_REF] Françon | Polyhedrization of the boundary of a voxel object[END_REF], Françon and Papier also proposed an algorithm based on this scheme. Nevertheless, in this case, they directly transform the discrete faces into polygonal non coplanar faces, which is not a satisfactory modelling of the object.

The last two methods we recall in this short state of the art compute an approximation of the discrete surface. The first one was proposed by Burguet and Malgouyres in [START_REF] Burguet | Strong thinning and polyhedrization of the surface of a voxel object[END_REF] and uses a "topological Voronoi Diagram". This diagram is used in order to decompose the discrete surface into regions, which are triangulated to get the polyhedral representation. Finally, Yu and Klette [START_REF] Yu | An approximative calculation of relative convex hulls for surface area estimation of 3D digital objects[END_REF] use the minimum length polygon algorithm on each slice of the discrete object and sue those polygons together to obtain an approximation of the discrete object surface.

The algorithm presented in this paper is based on a segmentation of the discrete object surface into pieces of discrete planes. We present an algorithm that computes, for each discrete face, a planar polygon containing the voxels of the discrete face in its digitization. Such a transformation is achieved via an analytical modelling of the discrete face, which defines a compact description of the discrete object itself.

This paper is composed of three sections. In Section 2, we present the general framework of our algorithm, defining the notions of discrete plane, surface, connectivity and segmentation we use together with the dual spaces. The third section deals with the description of our algorithm and finally, application results of this algorithm over each discrete face of discrete surfaces are proposed in Section 4.

Framework and Tools

Preliminaries

First of all, we define the framework used in this paper. Our algorithm takes in input a discrete surface that has already been segmented into pieces of discrete planes. The definitions of discrete plane and discrete surface used for the segmentation process are induced by the reconstruction we propose. Indeed, our transformation defines a discrete polygon (analytical description) from a discrete face (defined by a set of discrete points). The notion of discrete polygon was introduced by Andrès in [START_REF] Andrès | Defining discrete objects for polygonalization : the standard model[END_REF] using the standard digitization model. This digitization scheme is based on the supercover digitization which states that any pixel (or voxel) crossed by the object belongs to the digitized object. Supercovers may contain "bubbles", i.e. many digitization pixels for one point (points with halfinteger coordinates for instance). To cope with that problem, an orientation convention is defined and leads to the standard digitization scheme.

Consequently, standard planes must be used for the segmentation process. A standard plane is the thinnest 6-connected discrete plane without tunnels: any path (6-connected, 18-connected or 26-connected) joining the two background sides of a plane contains at least one voxel of the plane. An illustration of a standard plane is given in Figure 1(a).

Concerning the definition of discrete surfaces, two main approaches exist: the surface elements are either object voxels or object voxels' faces. In this work, we will define the object surface as the set of voxels' faces (called surfels, see Figure 1(b)) belonging to an object and a background voxel. In other words, the surface is composed of the faces visible when the object is displayed. This definition of surface is well-adapted for standard planes segmentation: in this case, discrete (lattice) points are not the object voxels but the vertices of those voxels (called pointels, see Figure 1(b)). It is easy to see that those vertices are linked along the 6-connectivity, which is consistent with the use of standard planes.

Using standard planes also induces the connectivities we consider for the object. Standard planes have a combinatorial structure of 2-dimensional manifolds [START_REF] Françon | Discrete combinatorial surfaces[END_REF][START_REF] Françon | Sur la topologie d'un plan arithmétique[END_REF]. Thus, the discrete surface we work on should have the properties of a 2D combinatorial manifold as well, which implies that 6-connectivity has to be considered for the discrete object.

At this point, we have defined all the elements needed for a segmentation process: discrete plane and surface, connectivity. Now let us describe the properties the segmentation must fulfill:

1. pointels adjacent to a common surfel belong to a common discrete face 2. the projection of each discrete face along its main direction (direction given by the maximum parameter of its normal vector) is a set of 4-connected pixels 3. each discrete face is homeomorphic to a topological disk. Those three conditions imply that any discrete face is a combinatorial 2manifold with boundary, and that this boundary can be described as a 6connected 3D discrete curve.

Figure 2(a) gives an example of the result we get with a segmentation algorithm fulfillingthosethreeconditions(see [START_REF] Sivignon | Discrete surface segmentation into discrete planes[END_REF]).Notethatthetopofthetorusisdecomposed into two discrete faces instead of one, so that each discrete face is homeomorphic to a disk. On Figure 2(b), a discrete face is depicted, and each pointel belonging to this face is marked by a small sphere. The boundary of this discrete face can be described as a 6-connected curve, as illustrated in Figure 2(c).

Principle

Since each discrete face is composed of discrete points belonging to a standard plane, there exist a Euclidean plane crossing all the discrete face points. The overall algorithm consists in computing for each discrete face f crossed by a plane p, a polygonal line embedded in p and crossing all the boundary points of f . This polygonal line defines a polygon containing exactly the discrete points of f in its standard digitization.

The result of such an algorithm is a set of polygons, one for each discrete face, such that the standard digitization of each polygon is exactly a standard face, and finally, the standard digitization of the set of polygons is exactly the initial discrete object surface.

To compute a polygonal line from a discrete face boundary, we propose the following outline, that we present in [START_REF] Sivignon | Discrete analytical curve reconstruction without patches[END_REF] in the case of 2D discrete curves and non coplanar 3D discrete curves. Consider a 6-connected discrete curve S described as an ordered set of discrete points {v 1 , v 2 , . . . v n }. A Euclidean point r 1 is chosen inside the first point v 1 , and the following voxels are added one by one (they define a discrete segment s 1 ) while there exist a Euclidean line going through r 1 , through all the voxels of s 1 and embedded in the carrier plane p. In other words, s 1 is incrementally extended while:

s 1 is a 3D discrete segment among the lines which contain s 1 in their digitization, there exist at least one line that is embedded in p and that goes through the fixed point r 1 .

When one of those two conditions is no more fulfilled, the first real segment endpoint r 2 is computed as a common point of the computed line and s 1 's last pixel. The fixed extremity of the next real segment is set to r 2 and this process starts over.

Dual Spaces and Preimages

Dual Spaces. In order to polygonalize discrete faces boundaries, the question " does this set of voxels belong to a discrete segment ?" will need an answer, and one method to solve this problem is to rewrite it in a dual space. The main idea is that a line in the Euclidean space is represented by a point in the dual space, and conversely, a point in the Euclidean space corresponds to a line in the dual space. This tranformation is very similar to the Hough Transform [START_REF] Hough | Method and means for recognizing complex patterns[END_REF][START_REF] Maître | Un panorama de la transformation de Hough[END_REF] that is classically used in image analysis for shape detection problems. The main difference between the Hough transform and the transform we use here is that the uncertainty related to the discrete nature of the data is not handled during a quantification step but during the tranform itself. Many works in discrete geometry use this transform for 2D discrete line or plane recognition [START_REF] Mcilroy | A note on discrete representation of lines[END_REF][START_REF] Lindenbaum | On recursive, O(n) partitioning of a digitized curve into digital straight segments[END_REF][START_REF] Vittone | Recognition of digital naive planes and polyhedrization[END_REF]] but we will not provide a full state of the art on this point here.

An illustration of the mapping we use is given in Figure 3. Note that in this figure, the dual representation of the line defined by the equation ax -by + r = 0 is the point ( a b , r b ), and thus, that this representation is based on a normalization along one direction (direction y in this case). Consequently, two dual spaces can be defined in the 2D space, one for each direction. Since line parameters are represented in dual spaces, those spaces are also called parameter spaces.

Similarly, three dual spaces can be defined in 3D. One plane in the Euclidean space is represented by one point in the dual space and conversely. One 3D line in the Euclidean space E is represented by another 3D line in the parameter space P. In the following, we will denote by E the operator which transforms one element of the parameter space into its corresponding element in the Euclidean space.

One important point for this work is how to represent in the parameter space the embedding of a 3D line into a given plane. It is actually easy to see that since a 3D line l maps to another 3D line E -1 (l) (each point of E -1 (l) corresponds to a plane containing l), and since a plane P maps to the point E -1 (P ), then l is embedded in P if and only if E -1 (l) goes through E -1 (P ) (see Figure 4).

Preimages. Consider a set of pixels and a digitization scheme D. We call preimage of the set of Euclidean lines containing in their digitization. This set is represented in the dual space as a set of points.

Let us consider for instance the line l defined by ax -by + r = 0 where a > 0 and b > 0. Then, the standard digitization of l is the set of discrete points (x, y) fulfilling the inequalities -a+b 2 ≤ ax -by + r < a+b 2 . The lines containing the point (x 0 , y 0 ) in their digitization are those of parameters (α, β) (defined by the equation αx -y + β = 0) fulfilling the inequalities -α+1 2 ≤ αx 0 -y 0 + β < α+1 2 . Thus, each discrete point defines two half-spaces in the parameter space, and the intersection of those half-spaces is the set of parameters of the lines containing this discrete point in their digitization. Given a set of discrete points, we call preimage of this set the convex polygon of the parameter space defined by the intersection of the constraints related to the discrete points (see Figure 5).

Reversible Polygonalization of a Planar 3D Discrete Curve

In this section, we present a new algorithm to compute a polygonal planar curve from a 3D discrete planar curve in a reversible way. This algorithm is based on three steps, described in the following three paragraphs.

Recognition of a 3D Standard Segment

The first step is to define an algorithm to recognize a 3D standard segment, i.e. the standard digitization of a 3D line segment. A standard discrete line can be defined in an analytical way:

Definition 1.
Let us consider a 3D straight line of directional vector (a, b, c) going through the point (x 0 , y 0 , z 0 ). Then the standard digitization of this line is the set of integer points fulfilling the conditions given by the following double inequalities:

-|a|+|b| 2 ≤ bx -ay + ay 0 -bx 0 < |a|+|b| 2 -|a|+|c| 2 ≤ cx -az + az 0 -cx 0 < |a|+|c| 2 -|b|+|c| 2 ≤ cy -bz + bz 0 -cy 0 < |b|+|c| 2
where (b > 0 or (b = 0 and a > 0)) and (c > 0 or (c = 0 and a > 0)) and (c > 0 or (c = 0 and b > 0)) (otherwise, the strict and large inequalities of those equations are exchanged, see [START_REF] Andrès | Defining discrete objects for polygonalization : the standard model[END_REF]).

From this definition, we derive that if a set of voxels is a 3D standard segment, then the three projections of this set of voxels are 2D standard segments.

Consequently, in order to ensure that the three projections of the set of voxels are 2D standard segments, we compute the three preimages of those sets of pixels. If the three preimages are not empty, then this condition is fulfilled, otherwise, the set of voxels is not a 3D standard segment. Moreover, we said in Paragraph 2.2 that before the recognition step, a point is fixed inside one voxel of the set considered. Thus, the only lines which are interesting for us are the ones which go through this fixed point. As illustrated in Figure 5(a), the projection of this fixed point p onto the three coordinate planes defines three points p x , p y and p z that are represented by three lines in the parameter spaces. Thus, the preimages we work one are no more polygons but simply segments denoted by I x , I y and I z (see Figure 5(b)).

Nevertheless, this condition over the three projections is not sufficient to define a 3D standard segment, and a compatibility condition between the parameters of the three projections needs to be added (see [START_REF] Sivignon | Discrete analytical curve reconstruction without patches[END_REF], where non planar curves are studied, for details). In the case of planar curves, this compatibility condition does not need to be handled since we will see that it is ensured while considering the embedding of the curve into a plane.

Ensure Coplanarity

In the following, we consider the general case where the carrier plane P is defined by the equation ax + by + cz + µ = 0, with a, b and c not equal to zero. It is easy to see that any of the three preimage segments I x , I y and I z can be represented in two out of the three dual spaces P x , P y and P z . Indeed, those preimage segments are embedded in the planes α = 0 or β = 0 in those dual spaces. For instance, consider the dual space P x where the two segments I z and I y can be represented. In this space, the carrier plane P is represented by a point E -1 (P ). Thus, the 3D lines l embedded in P and containing the set of voxels considered in their digitization are those such that E -1 (l) crosses E -1 (P ), I y and I z .

A reduction process of the segments I z and I y according to E -1 (P ) is done, as illustrated in Figure 6. The grey cone drawn on this figure represents all the lines going through one point of I z and the point E -1 (P ). Thus, the points of I y which do not belong to this cone must be deleted since there does not exist a line going through I z , E -1 (P ) and those points (depicted between brackets on Figure 6). After the reduction of I y , the reduction of I z is computed.

This pair of reductions is computed in each dual space P x , P y and P z , such that each preimage I x , I y and I z is reduced twice. Finally, we have the following result: Proposition 1. After the six reductions presented above, the preimages of the three projections of the set of voxels S represent exactly the set of 3D lines that are solution for S and embedded in the carrier plane.

The proof of this proposition is directly derived from the fact that one point in the preimage of one of S' projections defines a unique 3D line in the Euclidean Moreover, those reductions ensure that the preimages of the projections are compatible, i.e. that there exist a 3D line such that its projections contain the projected set of pixels in their standard digitization (see previous paragraph).

Choice of Fixed Extremities

In Section 2.2, we saw that the first step of our algorithm is to choose an initial point in the first voxel of the curve and in the carrier plane P . This point belongs to the intersection between a voxel and a Euclidean plane. From the definition of standard plane, we know that the voxels cut by a given plane are those belonging to the standard digitization of this plane. The geometry of this intersection has been studied by Reveillès [START_REF] Reveillès | The geometry of the intersection of voxel spaces[END_REF] and Andrès et al. [START_REF] Andrès | New methods in oblique slice generation[END_REF] who show that the only five geometric shapes possible are a triangle, a trapezoid, a pentagon, a parallelogram or an hexagon (Figure 7). They moreover characterize completely the shape of the intersection between a plane and a voxel according to the position of the voxel in the corresponding standard plane. In [START_REF] Reveillès | The geometry of the intersection of voxel spaces[END_REF], Reveillès gives the arithmeticalexpression of intersection vertices coordinates. Thus, the initial point chosen in our algorithm is simply the barycentre of the vertices computed thanks to Reveillès [START_REF] Reveillès | The geometry of the intersection of voxel spaces[END_REF] and Andrès et al. [START_REF] Andrès | New methods in oblique slice generation[END_REF] results. The result of this algorithm over a single discrete face is represented in Figure 8. In (a), the pointels belonging to this face are labelled. In (b), a polygonal curve embedded in the Euclidean plane that is solution for the discrete face is computed: on this figure, the boundary pointels of (a) are replaced by unit cubes centered on the pointels, so that it is easier to check that the computed line is entirely included in the curve. Finally, the polygon computed is represented in (c), together with the discrete face it corresponds to: the standard digitization of the polygon is exactly the set of pointels of the discrete face.

On the complexity point of view, each discrete point of the face boundary is seen only once, computing the reduction of the preimages intervals according to a new discrete point is done in logarithmic time (using Grabiner algorithm, see [START_REF] Vittone | Recognition of digital naive planes and polyhedrization[END_REF]) and the reductions of the intervals presented in Proposition 1 is done in constant time. Finally, the overall complexity of this algorithm is in O(n log n) where n denotes the number of boundary points for a given curve.

If we consider complex objects, this algorithm is applied over each discrete face computed by the segmentation algorithm. A set of polygons (one for each face) is computed such that the standard digitization of this set of polygons is exactly the surface pointels of the initial discrete object. Figure 9 presents two results over a torus and the image named "Al": the initial discrete object is depicted on the left, and the set of polygons computed is represented on the right.

Conclusion

In this paper we described a new algorithm to transform a discrete face into a discrete polygon and a Euclidean polygon. The discrete polygon is defined analytically thanks to the decomposition of the discrete face boundary into discrete analytical segments. The transformation into a Euclidean polygon is done incrementally at the same time, fixing the first extremity of each segment as the last extremity of the previous segment. Next we applied this algorithm onto each discrete face defined by a discrete surface segmentation algorithm. We get a set of polygons modelling the discrete surface in a reversible way: the standard digitization of each polygon is exactly a discrete face of the segmentation.

An interesting future work would be to improve this modelling by sewing the different polygons in order to get a surface while preserving the reversibility property. This problem may be related to the polygonal reconstruction of several adjacent discrete regions in 2D.

Fig. 1 .

 1 Fig. 1. (a) Example of a discrete standard plane. (b) Decomposition of a voxel into lower dimensional elements

Fig. 2 .

 2 Fig. 2. Example of a segmentation result required for the reconstruction: (a) on a torus, (b) detail of a discrete face and (c) of its boundary

Fig. 3 .Fig. 4 .

 34 Fig. 3. Representation of the links between the Euclidean (top) and the dual spaces (bottom) for elementary geometric objects

Fig. 5 .

 5 Fig. 5. Recognition of the three projections of a given set of voxels with a fixed point p

1 Fig. 6 .

 16 Fig. 6. Example of dual segments reductions according to the carrier plane P

Fig. 7 .

 7 Fig. 7. The five possible intersections between a voxel and a plane

Fig. 8 .Fig. 9 .

 89 Fig. 8. Different steps of the polygonalization of a discrete face: (a) the discrete face pointels, (b) computation of the polygonal line, (c) final polygon