Piecewise surface flattening for non-distorted texture mapping.
This paper introduces new techniques for interactive piecewise flattening of parametric 3-D surfaces, leading to a non-distorted, hence realistic, texture mapping. Cuts are allowed on the mapped texture and we make a compromise between discontinuities and distortions. These techniques are based on results from differential geometry, more precisely on the notion of "geodesic curvature": isoparametric curves of the surface are mapped, in a constructive way, onto curves in the texture plane with preservation of geodesic curvature at each point. As an application, we give a concrete example which is a first step towards an efficient and robust CAD tool for shoe modeling.
Introduction
Texture mapping techniques are widely used to reproduce textural
information available in a planar image onto a 3-D surface. This
is made possible by making a correspondence between a planar
image and a 3-D surface, in order to give each sample point of the
output screen reached by the projected 3-D surface an intensity
value computed from a point or a set of points of the 2-D image
sample. This correspondence is called the "mapping function".
Catmull [8] first introduced a recursive subdivision algorithm to
map a 2-D rectangular image onto a 3-D bicubic patch. This
method has been refined and enhanced by several authors [9, 6].
These techniques are equivalent to warping the planar rectangle
until it takes the shape of the bicubic patch. Unfortunately, these
techniques do not preserve distances or angles, resulting in spatial
distortions of texture patterns, which can sometimes change
the visual appearance of the texture on the surface. Other authors
have proposed solutions to reduce these distortions. Bier et
al. [5] proposed a 2-part mapping which consists in decomposing
the mapping in two steps: the texture pattern is first embedded
in a 3-D intermediate surface and then projected onto the target
surface in a way that depends only on the geometry of the target
object. The distortion is reduced by heuristically choosing the
appropriate intermediate surface and the projection method. Unfortunately
this is not always easy to do. Fiume et al. [13] have
proposed a "polygonal conformal mapping" to map a polygon (e.g.,
a square) onto an arbitrary convex polygon with preservation of
angles. This technique gives good results on polygons for some
applications. However, the technique does not preserve distances,
Current address: Institut Francais du P'etrole 1 et 4 avenue de
thus creating distortions. Moreover, it is not easily extendable to
In [17], Ma et al. used an optimization technique
to minimize distortions for general surfaces. The mapping
is performed on a grid of sample points of the 3-D surface. Starting
from an arbitrary initial mapping, the algorithm converges to
the optimal mapping by minimizing a global metric taking into
account distances between each point and its direct neighbours on
the 3-D grid. A similar technique was proposed at the same time
by Schwartz et al. [11] for general surface flattening. Since most
surfaces are not developable (i.e. unfolded without deformations
or cuts, think of a sphere), distortions still remain. Moreover, optimization
techniques offer no control on the distribution of the
remaining distortions.
A non-distorted mapping of a planar texture onto a 3-D surface is
equivalent to a non-warped flattening of the surface. As it is well
known, fully spreading out a non-developable surface would induce
distortions. The basic idea of this work is to permit discontinuities
on the mapped texture and to make a compromise between cuts
and distortions. The cuts here play the role of seam lines (such as
on a cloth). The surface is first piecewise flattened (with different
maps in the plane), then texture is computed on the surface using
the flattened parts. This could have many applications in different
fields, varying from graphics concerning non-distorted texture
mapping, to cartography and manufacturing (cloth modeling) for
piecewise flattening. The example emphasised here is a first step
towards an efficient and robust CAD tool for shoe modeling.
This paper introduces new techniques for interactive piecewise flattening
of parametric 3-D surfaces, leading to a non-distorted texture
mapping. The flattening of a region grows around an isoparametric
curve selected by hand. A distortion metric is introduced
to control and stop the growth when the accumulated distortion
exceeds a previously determined threshold. The flattening methods
are based on results from differential geometry ([7] [12]), more
precisely on the notion of "geodesic curvature": isoparametric
curves of the surface are mapped in a constructive way onto curves
in the texture plane, with preservation of geodesic curvature at
each point.
The next section gives the outlines of the global texture mapping
approach. This section also reviews our previous work [3] on revolution
surface flattening. In section 3, concepts from differential
geometry (geodesic curvature) are introduced and utilized to
straightforwardly extend the previous work to more general sur-
faces. A more robust technique (based on a relaxation procedure)
is proposed in section 4. All these techniques are compared on well
known examples: a cone and a hemisphere. Section 5 presents an
application to shoe modeling. The paper concludes with a discussion
of the limitations of the proposed techniques and with some
suggestions for future developments.
General considerations and previous
work
The surfaces considered here are given by a piecewise parametric
We require the surfaces to be C 2 (to have continuous second order
derivatives at each point), especially on the joining curves (the
reason for this constraint is explained later). Moreover, the two
families of isoparametric lines must be nowhere tangent to each
other (i.e. a normal and a tangent plane exist at every point).
The surface is first regularly sampled into a grid of 3-D points,
along the isoparametrics (in parameters space). Moreover, the
sampling must be refined enough to approximate the arc length
between two successive sample points along an isoparametric by
their euclidian distance. In the following, sample curves along u
and v directions are respectively denoted C :j
We note the points of the 3-D grid M ij , and their
correspondents in the flattening plane . The euclidian distance
between two points M 1 and M 2 is loosely denoted
2.1 Outlines of the general approach
The texture mappingalgorithm can be divided into two main steps:
I) An initial chord curve (a portion of an isoparametric) is
first selected on the grid and the surface is unfolded around
this curve until a preliminarily fixed distortion threshold is
reached. The same process is repeated on the unprocessed
region of the grid until all the surface, or an interesting part
of it, is covered.
II) The processed regions of the grid are then triangulated, and
a locally affine interpolation, affine in each triangle, is used
to texture them.
Step I) constitutes the piecewise flattening part of the algorithm.
More precisely, for each presented flattening technique, an appropriate
distortion metric is defined. The initial curve is chosen by
hand depending on where the texture is desired to be the less dis-
torted. This curve divides the surface into two sub-regions, e.g.
"left" and "right". Let the curve be C
g.
Unfolding the surface around this curve is done in three steps:
1. Develop the initial curve: find for each sample point
this curve a corresponding point in the flattening plane
(e.g., a texture plane) .
2. develop the surface on the left side of the initial curve:
fix a left side threshold, then develop successively curves
(parallel to the initial one)
until the provided distortion exceeds the left side threshold,
or the current curve belongs to an already developed region.
3. Develop the surface on the right side of the initial curve using
a right side threshold (the same as the leftside development
but developed curves are fC i:
Step II) constitutes the texturing part: the triangulation
of a processed region is obtained by splitting each
quad fM of four neighbouring sample
points, into two triangles fM and
g. This gives rise to two triangles in the
texture plane, fP
where the P kl are the corresponding points of the M kl and have
already been obtained with the flattening process. The 3-D triangular
faces are projected onto the output screen. A triangle-to-
triangle affine interpolation from the texture plane to the output
screen is used to compute the texture value at each pixel of the
1 For the texture mapping application the flattening plane is
considered to be the texture space.
output screen. A Z-buffer is used for hidden surface parts elimination
and a prefiltered summed table [10] is used for antialiasing.
The locally affine approximation of the mapping function is well
explained in [4], and compared with the approximation proposed
by Oka. and al. in [18] (see [4] for more details). Local affine
approximations to a mapping are also discussed in [14].
From now on we will emphasize the geometrical aspect of the non
distorted piecewise flattening.
2.2 Previous work
In [3] we have proposed a piecewise flattening technique for surfaces
of revolution. The outline of the algorithm is:
1. Map an initial meridian C of the surface onto a straight line
in the plane with distance preservation between sample
points. One has only to fix a correspondence for a starting
point and a direction for the straight line. Obtaining the
other correspondences is immediate.
2. Extend the development step by step around C (at each
step a meridian C i: is reached) while mapping parallels onto
straight lines orthogonal to D preservation
between sample points, until the distortion threshold is
reached. (see Figure 1).
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Dio
C io .
If distortion > threshold
stop

Figure

1: Previous flattening of surfaces of revolution.
This method preserves distances on the initial meridian C
parallels C :j but not on the other meridians C i: (unless the surface
is a cylinder). Moreover, we preserve the cross angles between
Distance distortion on meridians and cross angle
distortion (between the two families of curves) increase as one gets
far from the first meridian. All distortions are concentrated on
meridians so we choose as a distortion metric for each
successive curve C i: , the mean of the errors induced on its chord
segments:
(1)
Here, N is the number of sample points of C i: , and P kl are the
corresponding texture points of 3-D points M kl . Note that here,
due to revolution symmetry, one has only one threshold for both
leftside and rightside development.

Figure

2 shows the development of a cone and a hemisphere with
this technique. We have developed them entirely, onto only one
piece, to emphasize the nature of distortions. Note that there are
fewer distortions than with Catmull's technique ([8]) where both
surfaces would be mapped onto a rectangle. Moreover, we find
for the hemisphere the well known Sanson's projection (pseudo-
cylindric projection) used in cartography.
Although the cone is a developable surface, the algorithm of [3]
does not give its proper development. However, this technique
gives satisfying results if we develop the surface into sufficiently
small pieces, because the meridians of a surface of revolution are
geodesics (they have at any point a zero curvature with respect to
the surface) so they are equivalent to straight lines in the plane.
One possible enhancement and extension of the algorithm of [3]

Figure

2: Cone and hemisphere flattening.
to more general surfaces (see Figure 3) consists in computing the
joining two extremal points of an initial curve and
mapping it onto a straight line D 1 in the plane (with distance
preservation). Then, for any other point M ij , compute the shortest
geodesic G starting from G 1 and joining M ij . Let M be the
intersection point of G and G 1 . The planar correspondent P of
M is obtained by preserving the distance between M and M 2
then given by drawing a straight line
D orthogonal to D 1 and by preserving the distance between M
x
x
x
x
x

Figure

3: A possible extension using geodesics.
Geodesics on a 3D surface are very attractive because they behave
much like straight lines on the plane. Unfortunately, although this
class of curves has long been studied in differential geometry [7] and
are now well known, their characterization is rather local. Given a
curve drawn on a 3-D surface one can determine whether or not it
is a geodesic at a given point. The entire curve is then a geodesic
if it is geodesic at each point. But what we need here is the inverse
problem: find a curve on a surface which is a geodesic between two
given surface points. This problem is very difficult because we have
to make a global numerical computation using local properties.
Numerical approximations of computation of geodesics proposed
up to now [16, 1] are very slow. In addition, they do not always
give good results.
In the next section we give an almost equivalent extension avoiding
geodesic computation.
3 Geodesic curvature preservation flat-
tening
Instead of mapping onto the plane unknown (and difficult to com-
pute) curves of the surfaces such as geodesics, we use already available
isoparametric curves and take into account their topological
properties in the mapping process. The main idea of the proposed
technique is to map isoparametric curves of the surface onto curves
of the plane, with geodesic curvature preservation at sample points
and with arc length (i.e. chord length) preservation.
We will first recall some results from the differential geometry of
curves in order to define the notion of geodesic curvature, then
outline the new general flattening algorithm, and finally give a
numerical and constructive algorithm for mapping curves of a surface
onto curves of a plane with geodesic curvature and arc length
preservation.
3.1 Local properties of curves and surface
curves: short review
The results in differential geometry that we use may be found in
and [12], both excellent references.
Let C be a curve in R 3 given by arc length parametrization:
where the Cartesian coordinates x(s); y(s) and z(s) of each point
of C, are differentiable functions of arc length s (the length of
C from X(0) to X(s)).
To study the local behavior of a curve, a fundamental concept
in differential geometry is to use a local frame and to express its
local change in its own coordinate system. The Frenet local frame
(X; t; m;b) is a good candidate for this purpose (see Figure 4).
The origin of the frame is point X around which one would like to
study the local behavior of the curve. Axes (t; m;b) are given by
the formulas:
ds
ffl b=t "m,
where primes denote derivatives with respect to arc length and
" denotes the cross product. t(s) is the tangent vector, m(s) is
called main normal vector and b(s) is called binormal vector at s.
The plane O(s) generated by t(s) and m(s) is called the osculating
plane at s; it is the plane which contains the curve around X(s).
One can easily show that variation of the Frenet frame can be
. m
a

Figure

4: a): Frenet frame variation along a curve, b): Local
behavior of a sphere circle, c): cones parallel to a sphere along
circles.
expressed through the following formulas:
The variables jk(s)j=kt 0 (s)k and j (s)j=kb 0 k are called respectively
main curvature and torsion at s. Curvature and torsion have
an intuitive geometric meaning: let dff(s) and d'(s) be respectively
the angle between t(s) and t(s + ds) and the angle between b(s)
ds), at "consecutive" points X(s) and X(s+ ds). Then:
ds
ds
k:
In other words k and  are the angular velocities of the tangent
and the osculating plane, respectively, as the frame is moved along
the curve with s playing the role of "time".
Moreover, these two variables are independent of parametrization.
When k is zero everywhere the curve is a straight line, and when
is zero everywhere the curve is planar.
Now, consider a surface S given by a parametric function from R 2
to
where the Cartesian coordinates x; z of a surface point are differentiable
functions of u and v. Let us suppose in addition, that
the isoparametric lines are nowhere tangent to each other:
where Xu an Xv are first derivatives vectors according to u parameter
and v parameter respectively.
The vector n= N
kNk is called the normal vector to S at point
X(u;v).
The plane Tp spanned by the set of points Y such that:
(where dot denotes the scalar product of vectors) is called the
tangent plane to surface S at point X.
Let C S be a curve belonging to surface S and given by arc length
parametric function X(s). Recall that the curvature is defined by
the acceleration t 0 =km of C S . This vector can be expressed with
two components where the one, t 0 g , is tangent to the surface and
the other, t 0 n , is normal to the surface:
Seen from a view-point linked to the surface, the acceleration t 0 is
reduced to tangential component t 0 g .
: The geodesic curvature kg of a curve C S belonging to
a surface S, at a point X, is the norm of tangential acceleration 2
of C S at X according to arc length parameter:
kg corresponds to the curvature of C S seen from a view-point attached
to the surface S. It is different from main curvature k (kg
could be null while k is not null).
C S is said to be geodesic at a point X if and only if kg is nil at
and C S is called a geodesic if it is geodesic at every point. One
necessary and sufficient condition for C S to be geodesic at point
X is that the main normal vector m of curve C S at X is parallel
to the normal vector n to surface S at X.
At any point X the local projection of a curve C S on the tangent
plane along the normal vector to the surface S provides a straight
line if C S is a geodesic, and non-zero curvature (at X) on the planar
curve otherwise. Figure 4 shows the behavior of circles of a
sphere: a circle is a geodesic if and only if it is a great circle.
Lemma: The Geodesic curvature kg of a curve C S belonging to
a surface S at a point X is equal to curvature at X of the planar
curve C Tp obtained by locally projecting C S onto the tangent plane
(Tp) along the normal vector to surface S at point X.
As for main curvature, intuitively geodesic curvature kg (s), at a
point X(s), is the angular velocity of tangents to the resulting
projected curve C Tp (s) according to arc length s.
This Lemma leads us to an efficient and constructive numerical
way of mapping a chord line of a surface onto a chord line in a
plane with preservation of chord length and geodesic curvature.
This is the basis of the new flattening algorithm described below.
3.2 Outline of the new general algorithm
The new algorithm runs as follows (see Figure 5):
2 That is the reason why we require a surface to be C 2 .
1. Map the initial selected curve C of the surface (for instance
curve in the plane with
geodesic curvature preservation at sample points and with
arc length preservation (distance preservation between any
pair of successive sample points).
2. Extend step by step the development on the left side of C
At each step one reaches a curve C i: mapping
transversal curves C :j curves in
the plane with geodesic curvature and arc length preservation.
At the same time, one requires preservation of the cross angle
between the initial curve C each transversal curve C :j .
The process is stopped when the left side distortion threshold
is reached, or curve C i: belongs to an already flattened region.
3. Extend the development on the right side of C according
to the right side threshold (same process as the left side one).
x
x
x
x
x
x
x
x
x
x
Surface Plane
if distortion>threshold
stop
C io .

Figure

5: Geodesic curvature preservation flattening.
Notice that here again distances are preserved along the initial
curve and in the transversal ones C :j . All distortions are concentrated
on curves C i: parallel to C So, the distortion metric
for a specific curve C i: is the same as for the previous technique
(formula (1)).
3.3 Mapping a 3D surface curve onto a planar
curve with arc length and geodesic curvature
preservation
Let us recall that the surface is sampled and that surface curves
are given by chord lines, arc length between two consecutive points
being approximated with euclidian distance. Suppose the curve C
that we want to map onto the plane contains
us denote by n i and Tp i , respectively, the
normal vector and the tangent plane to the surface at point M i .
The curve flattening algorithm can then be described as follows:
i) Map the first curve segment M 0 M 1 onto a segment
the plane (let us call this plane Oxy) such that d(M
It is sufficient to fix an initial point P 0 and a
direction in the plane.
ii) For each j; 2jn, P j is iteratively computed in the plane
as follows (see Figure 6):
1. Project M j and M j\Gamma2 onto the tangent plane to the
surface at M j\Gamma1 . This provides two points in Tp
called
M j\Gamma2 and given by the formulas:
~
~
2. Use a dilation in Tp j\Gamma1 to transform ~
into a point
j such that d(M
3. As P j\Gamma2 and P are already computed, the desired
point P j is the point of Oxy that preserves simultaneously
the angle '
, and the distance d(M
d
The way we obtain p j is to first compute coordinates
e 'M j-1
e 'j-2
~
Surface
Plane

Figure

Mapping a curve of a surface onto a planar curve:
step ii).
j according to the local orthogonalframe
1 and e 0
2 and the
coordinates are given by the formulas:
is the point of Oxy having the same coordinates
according to the orthogonal and positive frame
where (O; ~ is the canonical coordinate system of
Oxy.
Step ii) of this algorithm will be used in other circumstances, in
what follows . It can be thought of as an operator P. Given three
neighbouring surface points (M two corresponding
points in the flattening plane Oxy, P computes
point P 3 in Oxy, that preserves the distance
the projection of the angle '
. We will call
this operator the angle preserver and we will write:
Theorem: The above curve flattening algorithm preserves
geodesic curvature and arc lengths within the chord line approximation

As we initially have by construction of
are preserved.
As the sampling is sufficiently refined, the tangents to a curve can
be approximated with chord segments. So, at step ii), ' j\Gamma1 can
be considered as the angle variation between two "consecutive"
tangent vectors to the locally projected curve, into Tp j\Gamma1 . We
preserve ' j\Gamma1 and chord lengths. We then preserve locally the
angular velocity of tangents to the curve projection into Tp j\Gamma1 .
(Q.E.D).
Notice that the computation of P j involves geodesic curvature
preservation at M j\Gamma1 .
3.4 Preserving the cross angles between the initial
curve and a transversal curve
In fact, the preserved angles are the cross angles between the local
projection of the two curves onto the tangent plane at their
intersecting point (see Figure 7). Suppose that the initial curve

Figure

7: Cross angle preservation.
curve C :j meet at the point M i 0 j . Let us
denote by M i 0 respectively,
the neighbours of M i 0 j along the u and v direction. When we
project these four neighbours onto Tp i 0 j , we obtain a quadrilateral
must then be
preserved:
As the initial curve C already mapped, the points
are available in the flattening plane. In
addition, we have d
(geodesic curvature preservation at M i 0 j , on C We then only
have to preserve ' 1 and ' 4 , respectively, when we initialize the
mapping of C :j on the left side of C
and on the right side of C
implies the preservation of all the other angles. P
are then given by the angle preserver operators:
Moreover, this preserves the angle d
geodesic curvature at M i 0 j on C :j .
3.5 Flattening of the cone and the hemisphere

Figure

8-a and 8-b show the flattenings of the cone with this tech-
nique. In 8-a, the cone is spread out around a generatrix. In 8-b a
circle is used as initial curve. Both give the same result, which is
the proper development of the cone (an angular sector of a disc).
In

Figure

9, we show the mapping of a checkerboard pattern onto
the cone according to three different techniques: With Catmull's
technique, in 9-a and 9-b, squares are compressed along circles as
one gets close to the tip. The advantage of this technique is that
one can manage to avoid the line of discontinuities with repeated
patterns.
The second mapping (9-c and 9-d) is based on the flattening technique
described in section 2.2 (previous work). One can see that
distortions are not very noticeable beside the initial generatrix (9-
c). Squares are more and more stretched along meridians (the
inverse of flattening distortions impression) and angles more dis-
torted, beside the cutting line (9-d).
The mapping based on geodesic curvature flattening (9-e and 9-f)
provides no distortions but the texture contains a line of discontinuities
(9-f). Thus it is topologically faithful.

Figure

8: a) and b): Development of a cone around a meridian
and a parallel respectively. c) and d) Development of a hemisphere
around a meridian and the equator respectively.
The cone contains 1281 points. Its flattening takes about 0.05s
with the algorithm of section 2.2 and 0.5s with the geodesic curvature
preservation algorithm on a GOULD 9000. Mapping texture
from the flattened cone has taken about 25s.
The full development of the hemisphere around the central meridian
is shown in Figure 8-c. The initial meridian and the equator
are mapped onto straight lines, because both are geodesic curves.
The parallel circles are mapped onto circles, because along each
parallel circle there exists a cone tangent to the sphere: as along
the circle the tangent planes are the same according to the sphere
or to the cone, at each point geodesic curvature is the same according
to the two surfaces. So, flattening of a parallel circle of the
sphere gives the same result as if it were considered as belonging to
the cone, hence a circle. One can notice that with the latter flattening
technique, angles are less distorted than with the technique
of section 2.2 (Figure 2). The same flattening is obtained with
Bonne's projection (or pseudo-cylindric projection), also used in
cartography. In [2] it is shown that, starting from different initial
curves, geodesic curvature preservation flattening provides other
types of projections used in cartography. For instance, when the
initial curve is not a great circle, the development provides a cone
(a conic projection). The hemispherehas about 300 points. Its flattening
takes about 0.008s with the technique described in section
2.2 and has taken about 0.2s with the geodesic curvature preservation
algorithm.
The major disadvantage of this technique is due to preservation of
geodesic curvature in only one direction during the development
process. This concentrates all the distortions on the curves parallel
to the initial one. This also makes the technique strongly dependent
on the initial curve. Figure 8-d shows the development of
the hemisphere around the equator. One obtains a rectangle: the
equator is a geodesic, and is mapped onto a straight line. All the
meridians being geodesics, they are also mapped onto straight lines
orthogonal to the first one and having the same length. However
this technique remains suitable for all developable surfaces (or developable
parts of a surface). It also gives good results on almost
developable surfaces.
In the next section, we present a technique that takes into account
geodesic curvature in both directions and then reduce the drawbacks
encountered with non-developable surfaces.

Figure

9: Mapping a checkerboard onto a cone with different techniques

Incorporating geodesic curvature in
both directions: Relaxation technique
The technique described in this section consists of distributing distortions
in both directions. This is done in two steps:
1. One first develops the surface around an initial curve, taking
into account at each point the geodesic curvature in both directions
u and v and the projected cross angles. As will be
explained later, this development induces a gradient of distortions
on the flattened region. This gradient enables one to
measure the distortions and stop the development propagation
when necessary.
2. A relaxation procedure is then used to reduce and better
distribute the distortions in the flattened region.
For simplicity, in the following, the projected angle (in the
tangent plane) between two intersecting curves is loosely
called the angle.
4.1 Development technique
The new development algorithm is almost the same as the algorithm
of the previous section. One first maps the initial curve C
onto the plane with geodesic curvature and arc length preserva-
tion. The development of the region is then propagated step by
step to the curves parallel to C on the left side of C
on the right side of C . The new feature introduced here is the
way in which the points of the parallel curves are mapped onto the
flattening plane.
As illustrated in Figure 10, let be the point being
obtained by preserving at each neighbour
already processed, the
three angles are cross angles (fac-
ing between the curves that intersect at M kl . Preserving ' 3 kl
is equivalent to preserving the geodesic curvature at M kl on the
curve containing M ij and M kl . One can not always preserve all
three angles. For instance, in Figure 10 the point M i+1j\Gamma1 has
not yet been processed, so one cannot preserve ' 2 ij\Gamma1 . Each angle
qqqqqSurface
Plane

Figure

10: Preserving angles at processed neighbours (develop-
ment step).
preservation provides a different point in the flattening plane. This
point is obtained using the angle preserver:
The point corresponding to M ij in the flattening plane is then
the centroid of the points 3 P r;kl
ij .
The choice of the centroid induces slight errors on the angles and
distances. The accumulation of these errors provides a gradient of
distortions in the scanning direction. So, for a better distribution
of the distortions the curve being processed is not scanned from
one extremal point to the other extremal point. Instead, the curve
is scanned from the central point to the extremal points.
With this technique distortions are present on both C i: , C :j curves.
The distortions increase in diagonal directions as one gets far from
the central point of the initial curve. Let v j 1
on the
initial curve C . The distortion metric for a specific curve C i: is
Here one has
3 When the surface is developable the preservation of each angle
gives the same point in the flattening plane.
4.2 Relaxation procedure
In the above development, when mapping a point onto the flattening
plane, one does not take into account all the neighbouring
points (see figure 11). The reason is that some neighbours have not
been processed yet. In addition, for a given neighbour one can not
always preserve all the angles. The relaxation procedure consists
qqqq
Figure

11: Preserving three angles at four neighbours (relaxation
step).
of recomputing points of the obtained flat piece several times until
the change becomes insignificant. At each iteration one uses the
results of the previous iteration. The location of a point P n
ij at
iteration n is then:
ij is thus the centroid of the twelve points obtained by preserving
the three angles of each neighbour. The angle preserver P uses
the flattening points of iteration n \Gamma 1.
be a cluster of n points within a plane and let P
be a point in this plane. One calls the "dispersion" of the cluster
around P the value:
Dsp(P ) is minimum for the centroid Pm of the cluster of points.
Dsp(Pm ) is then called the dispersion of the cluster of points. For
our purposes, the quality of the flattening at a given point
can be measured by the dispersion Dsp(P ij ) of the twelve points
given by the twelve angle preservers. The smaller
the better is the flattening at P ij . Thus taking the centroid of
the twelve points at each iteration is better for distributing and
reducing the distortions.
The quality of the whole flattening can be measured by the mean
dispersion:
Here N is the number of points within the flattened piece. Thus,
the relaxation procedure stops when the dispersion Dsp n at iteration
n has not changed significantly, i.e. when jDsp n \GammaDsp
becomes less then some fixed variation threshold (about 10 \Gamma3 ).
The relaxation algorithm can thus be simply described as follows:
Greatnumber
Smallnumber
While jDsp n \GammaDsp
threshold
For each i,j indexing the region points
endFor
endWhile.
4.3 Flattening of the sphere

Figures

12-a and 12-b show the flattening of the hemispherearound
the central meridian before (12-a) and after (12-b) the relaxation
process. With the relaxation technique, it is clear that distortions
are better distributed and angles more preserved than previously
(i.e., with the geodesic curvature flattening preservation in only
one direction).

Figures

12-c and 12-d show the flattening of the hemisphere around
the equator before (12-c) and after (12-d) the relaxation process.
One can notice that after the relaxation, the flattening is almost
the same as when the initial curve is a meridian. Starting from

Figure

12: Development of a hemisphere - a: around a meridian
before and after relaxation b: around the equator before and after
relaxation.
the development around the meridian the relaxation has taken 6
iterations and 3 seconds. Starting from the development around
the equator the relaxation has taken about 16 iterations and 15s.

Figure

13 highlights the compromise between discontinuities and
distortions. A digitized photograph (in Figures 13-a and 13-b) and
an artificial material (in Figures 13-c and 13-d) are mapped onto
the sphere. Catmull's technique is used in the pictures on the left:
patterns are strongly deformed beside the pole, but there are no
discontinuities. In the pictures on the right the mapping is based
on the relaxation procedure. The sphere is segmented into four
equal pieces, a meridian being chosen for each piece. Distortions
are hardly noticeable, but seam lines are evident in the mapped
photograph. In the mapped material, seam lines are not quite
visible but one can guess where they are because of the sudden
changes of orientation.

Figure

13: Comparison on the sphere of Catmull's mapping and
the mapping based on the piecewise relaxation.
5 Application: shoe modeling
One of the possible applications of our mapping and texturing techniques
is computer-aided shoe design. Shoemakers naturally use
geodesics to cut patterns, by drawing lines on a shape of the shoe:
these lines become the edges of the flattened 3-D patterns constituting
the different pieces of the resulting shoe.
To determine the pattern of a region (see picture of Figure 14-a),
the shoemaker sticks a paper strip on a median curve of the region
to flatten. He then cuts the sheet from this line in fine "fish
bones"; each of them is folded back on the shoe form, determining
a geodesic on the surface. Finally, the trace of the region border is
marked on each bone, giving the edge of the flattened zone. One
notes that the choice of the geodesics is here completely empirical,
and therefore difficult to automate. Our method enables one to
overcome this difficulty.

Figure

14-b shows a wire frame of a shoe shape. A real wooden
shoe pattern has first been sampled by a laser sensor along successive
slices. Each slice has been approximated by a spline curve. A
spline surface (of NURBS type) has then been generated by transverse
interpolation between splines. The parametric surface has
then been sampled along isoparametrics. The parametric surface
modeling algorithm is explained in detail in [15].
In

Figure

14-b, the shoe model is being mapped: the pink zone
is already flattened, while the yellow side is currently treated: the
starting curve for development is drawn in green. The sole (in
white) is not treated yet.
As described above, we use isoparametrics as cut lines: starting
from a given curve, we develop the shoe surface until a deformation
threshold is reached. As the whole surface is not developable,
we can play on the width of the pieces by varying the distortion
threshold.
The shoe form is cut into three pieces (which flattenings are shown
in

Figures

14-c, 14-d and 14-e): the sole, the interior and the exterior
sides. The sole, as relatively flat, is flattened with the simple
geodesic curvature flattening. The relaxation process has been applied
to both sides.

Figures

14-f and 14-g show, from different viewpoints, the entirely
textured shoe shape, obtained by mapping on it successively a digitized
natural leather and an artificial weaving.

Figures

14-h and 14-i show the modeling of a sandal and its flattened
pieces. Small pieces have been obtained with the geodesic
curvature preservation algorithm. The big piece has needed the relaxation
algorithm. Finally, one can see the sandal textured with
the leather and the artificial material in Figures 14-j and 14-k.
Each of the shoe models has taken less than 3s computation time
for flattening the pieces. The affine interpolation for texture mapping
has taken between 15 and 20s.
From a practical point of a view, an efficient CAD tool should enable
one to draw "manually" the region edge curves on the 3-D
surface. Our techniques could then be used for the flattening of
each region, by developing the parametric pattern containing the
selected region, projecting the edges on the 2-D mapping, and finally
cutting the plane along these borders. In this case, the choice
of the initial development curve could even be automatic: the user
needs only to know the distortion rate induced on each piece of
the shoe. This will be pursued in future work. The algorithm of
drawing curves on 3-D surfaces is described in [15].
6 Conclusion
We have presented in this paper new and efficient algorithms for
non-distorted texture mapping. Unlike more conventional approaches
based on global minimization of distortions, our techniques
enable a controlled unfolding around an initial curve by
choosing a distortion metric on isoparametrics of the surface.
Moreover, distortions are lessened by introducing discontinuities on
the unfolded surface. Possible applications (among others) could
be umbrella and underwear designing, and, more generally, manufacturing

The new algorithms are easy to implement, although they are
based on uncommon concepts (from differential geometry); nev-
ertheless, they present several aspects for further study. First, a
human intervention for the choice of the initial curve and the distortion
threshold is necessary. Also, our techniques can only be
used on surfaces given explicitely by their parametric equations,
thus reducing their scope. The generalization to polygonal surfaces
would then be desirable. Another disadvantage is that seam
lines (cuts) are located on isoparametric curves, and thus depend
on the parametrization chosen. On most natural objects covered
with planar texture (clothes and walls for example), seam lines are
located on lines of main curvature, giving a harmonious look to the
mapping. It could then be useful to parametrize the surface again
along the main directions ([1]) before flattening it. This is not
always true, though, and in certain cases (shoe modeling for ex-
ample) aesthetics are important. This is a very subjective notion;
drawing edge curves by hand on the surface becomes necessary in
such cases.
Another interesting problem consists of how to reduce as much as
possible the number of cut pieces . A preliminary idea would be to
extend a previously mapped piece, by choosing its borders as being
the initial curves of the flattening algorithms described in this
paper. Another solution consists of finding a strategy to merge
different pieces previously obtained. This is still an open problem.
The last point that could be explored is the texture orientation:
how can one locate and orient the several flattened pieces in the
texture plane, in order to obtain a good appearance at seam lines.
A possible solution would consist of minimizing a global metric of
positions and orientations on the common borders of the unfolded
parts.

Acknowledgements

The authors are very grateful to Dr. D. Geman, Dr. J. Ralston and
Dr. P. Sander for revising the paper; to Dr. M. Gangnet and Dr.
F. Schmitt for their valuable comments; to L. Doghman, F. Ledru
and L. Vinet for their precious help; and to Dr. A. Gagalowicz for
his support.



--R

Surface analysis methods.
Synth'ese de textures hi'erarchiques planes - d'evel- oppement de surfaces 3d pour un placage de textures min- imisant les distorsions. Th'ese de Doctorat en Science
Hierarchical texture synthesis on 3-d surfaces
Mapping de textures sur une approximation triangulaire des surfaces.

Texture and reflection in computer generated images.

A subdivision algorithm for computer display of curved surfaces.


Computational neuroscience: Applications of computer graphics and image processing to 2d and 3d modelling of functional architechture of visual cortex.
Curves and surfaces for aided geometric design.
Conformal texture mapping.
Fundamentals of texture mapping and image warping.
Curve design on surfaces.
Determination of local coordinate systems for texture synthesis in 3-d surface
Optimal texture mapping.

--TR
Real-time manipulation of texture-mapped surfaces
Curves and surfaces for computer aided geometric design
Texture and reflection in computer generated images
Applications of Computer Graphics and Image Processing to 2D and 3D Modeling of the Functional Architecture of Visual Cortex
Summed-area tables for texture mapping
Fundamentals of Texture Mapping and Image Warping
A subdivision algorithm for computer display of curved surfaces.

--CTR
Emil Praun , Adam Finkelstein , Hugues Hoppe, Lapped textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.465-470, July 2000
Jrme Maillot , Hussein Yahia , Anne Verroust, Interactive texture mapping, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.27-34, September 1993
Fabrice Neyret , Marie-Paule Cani, Pattern-based texturing revisited, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.235-242, July 1999
David (grue) DeBry , Jonathan Gibbs , Devorah DeLeon Petty , Nate Robins, Painting and rendering textures on unparameterized models, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
Olga Sorkine , Daniel Cohen-Or , Rony Goldenthal , Dani Lischinski, Bounded-distortion piecewise mesh parameterization, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
Alla Sheffer, Skinning 3D meshes, Graphical Models, v.65 n.5, p.274-285, September
Leon Shirman , Yakov Kamen, Fast and Accurate Texture Placement, IEEE Computer Graphics and Applications, v.17 n.1, p.60-66, January 1997
Kun Zhou , John Synder , Baining Guo , Heung-Yeung Shum, Iso-charts: stretch-driven mesh parameterization using spectral analysis, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Dan Piponi , George Borshukov, Seamless texture mapping of subdivision surfaces by model pelting and texture blending, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.471-478, July 2000
Alla Sheffer , John C. Hart, Seamster: inconspicuous low-distortion texture seam layout, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
Anna Vilanova Bartrol , Rainer Wegenkittl , Andreas Knig , Eduard Grller, Nonlinear virtual colon unfolding, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
Yair Kurzion , Torsten Mller , Roni Yagel, Size preserving pattern mapping, Proceedings of the conference on Visualization '98, p.367-373, October 18-23, 1998, Research Triangle Park, North Carolina, United States
Huong Quynh Dinh , Anthony Yezzi , Greg Turk, Texture transfer during shape transformation, ACM Transactions on Graphics (TOG), v.24 n.2, p.289-310, April 2005
Bruno Lvy, Constrained texture mapping for polygonal meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.417-424, August 2001
Cyril Soler , Marie-Paule Cani , Alexis Angelidis, Hierarchical pattern mapping, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain
Gabriele Gorla , Victoria Interrante , Guillermo Sapiro, Texture Synthesis for 3D Shape Representation, IEEE Transactions on Visualization and Computer Graphics, v.9 n.4, p.512-524, October
R. Grossmann , N. Kiryati , R. Kimmel, Computational Surface Flattening: A Voxel-Based Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.433-441, April 2002
Jingqi Yan , Pengfei Shi , David Zhang, Transforming 3D mesh surfaces into images by parameterization, Integrated image and graphics technologies, Kluwer Academic Publishers, Norwell, MA, 2004
Takeo Igarashi , Dennis Cosgrove, Adaptive unwrapping for interactive texture painting, Proceedings of the 2001 symposium on Interactive 3D graphics, p.209-216, March 2001
Adam W. Bargteil , Funshing Sin , Jonathan E. Michaels , Tolga G. Goktekin , James F. O'Brien, A texture synthesis method for liquid animations, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
G. Zigelman , R. Kimmel , N. Kiryati, Texture Mapping Using Surface Flattening via Multidimensional Scaling, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.198-207, April 2002
Laurent Saroul , Sebastian Gerlach , Roger D. Hersch, Exploring Curved Anatomic Structures with Surface Sections, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.5, October 22-24,
Marcelo Walter , Alain Fournier , Daniel Menevaux, Integrating shape and pattern in mammalian models, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.317-326, August 2001
Mark Foskey , Miguel A. Otaduy , Ming C. Lin, ArtNova: touch-enabled 3D model design, ACM SIGGRAPH 2005 Courses, July 31-August
Alla Sheffer , Eric de Sturler, Smoothing an overlay grid to minimize linear distortion in texture mapping, ACM Transactions on Graphics (TOG), v.21 n.4, p.874-890, October 2002
Bruno Lvy , Jean-Laurent Mallet, Non-distorted texture mapping for sheared triangulated meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.343-352, July 1998
Steven Haker , Sigurd Angenent , Allen Tannenbaum , Ron Kikinis , Guillermo Sapiro , Michael Halle, Conformal Surface Parameterization for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.181-189, April 2000
Nathan A. Carr , John C. Hart, Meshed atlases for real-time procedural solid texturing, ACM Transactions on Graphics (TOG), v.21 n.2, p.106-131, April 2002
Matej Mlejnek , Anna Vilanova , Meister Eduard Groller, Interactive Thickness Visualization of Articular Cartilage, Proceedings of the conference on Visualization '04, p.521-528, October 10-15, 2004
P. N. Azariadis , N. S. Sapidis, Planar development of free-form surfaces: quality evaluation and visual inspection, Computing, v.72 n.1-2, p.13-27, April 2004
Simon Kolmiani , Nikola Guid, The flattening of arbitrary surfaces with approximation by developable stripes, From geometric modeling to shape modeling, Kluwer Academic Publishers, Norwell, MA, 2002
Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996
Sean Anderson , Marc Levoy, Unwrapping and Visualizing Cuneiform Tablets, IEEE Computer Graphics and Applications, v.22 n.6, p.82-88, November 2002
Alla Sheffer , Emil Praun , Kenneth Rose, Mesh parameterization methods and their applications, Foundations and Trends in Computer Graphics and Vision, v.2 n.2, p.105-171, January 2006
Phillip N. Azariadis , Andreas C. Nearchou , Nikos A. Aspragathos, An evolutionary algorithm for generating planar developments of arbitrarily curved surfaces, Computers in Industry, v.47 n.3, p.357-368, March 2002
Hans Khling Pedersen, Decorating implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.291-300, September 1995
Charlie C. L. Wang , Kai Tang, Woven model based geometric design of elastic medical braces, Computer-Aided Design, v.39 n.1, p.69-79, January, 2007
Hans Khling Pedersen, A framework for interactive texturing on curved surfaces, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.295-302, August 1996
F. Dong , G. J. Clapworthy , M. A. Krokos , J. Yao, An Anatomy-Based Approach to Human Muscle Modeling and Deformation, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.154-170, April 2002
differential geometry;geodesic curvature;piecewise surface flattening;non distorted texture mapping