Olga Sorkine and Daniel Cohen-Or
The School of Computer Science, Tel-Aviv University, Israel
Abstract
This paper introduces an implicit representation of the u;v texture mapping. Instead of using the traditional explicit u;v mapping coordinates, a non-distorted piecewise embedding of the triangular mesh is created, on which the original texture is remapped, yielding warped textures. This creates an effective atlas of the mapped triangles and provides a compact encoding of the texture mapping.
1. Introduction
In the past few years, much effort has been devoted to the development of mesh compression techniques, as the need to transfer 3D models over communication chan- nels constantly grows with the evolvement of Web-based applications3;8;9;10. The attention of the researchers has been focused on encoding polygonal meshes, in particular, tri- angular meshes. The representation of a mesh consists of set of vertex coordinates, known as the geometry, and the vertex/triangle adjacency list, known as the topology. While most of the attention has been devoted to the efficient encod- ing of the topology, the geometry is commonly encoded by some variation of delta-encoding, exploiting the intrinsic co- herence among the vertex coordinates. Such delta-encoding can be applied to any attributes associated with the vertices as long as they have similar spatial coherence to that of the vertices. In particular, this is true for the u;v texture coor- dinates, which are associated with each vertex of a textured mesh.
Encoding texture coordinates is important, since textured models are widespread in the commercial and entertainment world, and their size is a significant portion of the mesh rep- resentation. In this paper, we investigate a unique approach for encoding the texture mapping. The new approach is not based on delta-encoding, and moreover, avoids the explicit encoding of texture coordinates altogether.
The u;v coordinates are an explicit representation of the texture mapping, defining the source location of each ver- tex in the texture domain. Let T : R3!R2be the mapping function from the vertex coordinates space to the texture u;v space. Traditionally, T is described explicitly: for each
vertex point in R3, the corresponding mapping location in R2is stored. Given a triangular mesh M3R3, T embeds the triangles into a triangular mesh M2R2. We define an implicit representation of T by a composition of two map- pings, WH, where H is an embedding mapping from M3 to M02R2, and W is a warping function from M02to M2. The representation of T by WH is space efficient, since W is applied in a preprocess which warps the original tex- ture into a warped texture, and H is defined by the geom- etry of M3. This is illustrated in Figure1, where a simple object (pyramid) consisting of four triangles is displayed in (a), and its surface is mapped onto the texture in (b) by the T mapping. The warped texture defined by the embedding of the pyramid onto the plane is shown in (c). Since the tex- ture space is discrete, H and W should be chosen carefully to avoid sampling problems. In this paper, we construct an implicit H mapping which guarantees a proper sampling by the warping function W .
The paper is organized as follows. In the next section, we briefly discuss the embedding problem. In Section3we in- troduce a technique that constructs a proper embedding H.
Preliminary results are discussed in Section4.
2. Background
Embedding, or flattening, of a 3D mesh is a mapping of the 3D vertices onto the 2D plane, so that the topology of the mesh is preserved. Non-distorting embedding has been of much interest to the computer graphics community, since it provides a solution to different problems. In texture mapping applications, the flat texture is mapped onto the 3D surface by embedding the 3D surface triangles into the texture space.
(a) (b) (c)
Figure 1: A simple example of the remapping method: (a) A view of the textured 3D mesh, (b) The original texture mapping, (c) The warped texture
In this context, various embedding techniques have been de- veloped, which strive to flatten the surface while minimizing the deformation of the triangles using some global deforma- tion metric.
Eck et al.4treat the mesh as a system of springs, lying on the edges of the mesh, which obey some physical laws. The embedding is computed using harmonic maps, i.e. the 2D positions of boundary vertices are set along the unit disk and inner vertex positions are calculated while minimizing the total energy of the system. The resulting embedding mini- mizes the metric dispersion of the mesh. Maillot et al.7parti- tion the mesh into several areas using curvature information, and apply harmonic maps to each part, thus making a com- promise between discontinuities of the mapping and image distortion. Other works minimize the distortion by preserv- ing geodesic distances between vertices. Bennis et al.2first flatten an isoparametric curve on the surface with respect to the curvature and chord length and then unfold the sur- face around it, until a certain distortion threshold is reached.
Floater5 embeds a 3D mesh by first setting the positions of its boundary vertices along the boundary of a flat convex polygon (such as a rectangle or a circle), and then forcing the inner vertex positions to be placed in a convex combina- tion of their neighbors, while preserving the edge lengths as much as possible. These constraints define a linear system of equations for the flat vertex positions. Levy and Mallet6 attempt to preserve perpendicularity and distance between isoparametric curves on the surface by posing another set of linear constraints which minimizes a roughness criterion.
Azariadis and Aspragathos1 choose to decompose the mesh into parallel strips of triangles. Each triangle strip can be flat- tened by an isometric mapping to the 2D plane, i.e. no dis- tortion is caused to the triangles. The resulting texture map- ping, however, is not continuous along the strip borders. To solve this problem, the gaps between neighboring strips are closed, which distorts the flattened triangles.
All the above techniques focused on the local behavior of the mesh in order to prevent stretching of the texture. There- fore, the relations between neighboring triangles were im- portant. In contrast to those techniques, in our application,
we are concerned with the behavior of each individual trian- gle and thus, our embedding procedure guarantees that none of the triangles is distorted over some predefined threshold.
3. Non-distorting Embedding
Most known methods flatten the surface in one piece to avoid discontinuities in the texture mapping along the seam lines.
In our case, flattening is used to embed an existing texture mapping, therefore we can allow the embedding to be bro- ken into several patches. However, we would like to mini- mize the number of patches by generating patches as large as possible, so that their overall shape is compact. That is, the collection of textured patches should be contained in rectan- gular images so that their size is as small as possible.
Recall that our primary requirement is that none of the tri- angles is distorted above some threshold. One way to flatten a mesh without distorting the triangles is by simply recur- sively unfolding the triangles onto the plane. This, in gen- eral, yields overlapping of unfolded branches on the one hand and gaps among the branches on the other hand.
We use an iterative algorithm, which flattens each trian- gle with distortion below a certain predefined threshold. The process is as follows: an initial seed triangle is mapped to the plane as is. Then, we proceed iteratively by flattening its topological neighbors in bread-first-search order and grow- ing a patch P around the seed triangle. At each step, we find the set T of k triangles that share an edge with the triangles of P and attempt to flatten each of these candidate triangles.
This implies a set of new candidate vertices to be added to P. Given a candidate vertex q and its associated triangles
ftjg2T , we compute a set of positionsfqjgin the plane, such that qjis located by unfolding tjto the plane. The initial position q0 of q in the plane is the weighted average of qj, where the weights are defined by the distortion of the sup- porting edges of tjin P. The final position of q0is determined by applying a relaxation, which minimizes the distortions of the triangles t0j. (See Figure2) If the position of q0 causes one of its associated triangles to deform above the threshold or to overlap with P, the vertex is discarded from P, and will
00000000 00000000 00000000 11111111 11111111 11111111 00000 00000 00000 11111 11111 11111
00000 00000 00000 00000 00000 00000
11111 11111 11111 11111 11111 11111
00000000 00000000 00000000 11111111 11111111 11111111 00000 00000 00000 11111 11111 11111
00000 00000 00000 00000 00000 00000
11111 11111 11111 11111 11111 11111
(a) (b)
Figure 2: Growing a patch: the dark triangles were flattened in previous iterations. The white triangles are the candidates for embedding in the current iteration. In (a), q1;q2; q3are the unfolded 2D positions of the candidate vertex q. In (b), q0is the average 2D position of q.
be embedded in another patch. When the algorithm cannot add any vertex to P, it stops, and a new patch starts.
The distortion caused by embedding a triangle, is mea- sured by the following expression. Let e1; e2; e3 be the edges of the original triangle t and e01; e02; e03 the cor- responding edges of the embedded triangle t0. Denote by Li and li, i=1;2;3, the maximal and the minimal edge lengths, respectively. That is, Li=max(len(ei);len(e0i))and li=min(len(ei);len(e0i)). We define the distortion as the maximum ratio between the edge lengths:
distortion(t;t0)=max
i
(
Li li
);i=1;2;3:
Note that distortion(t;t0)1, and distortion(t;t0)=1 if and only if t and t0are isometric, since two triangles are isomet- ric iff their edge lengths are equal.
4. Preliminary Results
The piecewise non-distorting embedding algorithm has been developed in C++. We have tested it on several meshes, in particular, non-trivial ones which are not topologically equivalent to a disk or to a sphere. For example, the twisted loop in Figure3has a complex surface which cannot be flat- tened into one piece, and moreover, the surface curvature is relatively high. By applying our algorithm, the surface is de- composed into several patches, two of which are shown in Figure3(b-c).
The twisted cone (see Figure 4) is an example of an- other non-trivial surface, since the size of its triangles is non- uniform and the curvature varies over different regions. This surface can be embedded to the plane in one piece, but with significant distortion of the triangles. By applying a distor- tion threshold of 1.4, the surface is flattened into two pieces, shown in Figure4(c). Figures4(a),(d) show the twisted cone with texture and the two pieces of the warped texture, re- spectively.
We have tested our algorithm on several textured meshes with different distortion thresholds. The lower the maximum distortion is, the more patches are produced, which enlarges the total size of the images. We have found that a maximum distortion of 1.3 provides a good balance.
To generate a compact representation of the warped tex- ture, the patches are rotated to fit into a minimal bounding rectangle. The size of the warped textures is not necessarily larger than the original texture, since in many cases, the orig- inal texture has redundant parts and is not fully mapped. In fact, our algorithm creates an effective atlas of the mapped triangles. For example, the original JPEG size of the texture used in Figure4is 17.6KB, while the two warped textures’
size is 17.9KB. The overhead of the warped textures’ size is relatively small with respect to the u;v coordinates’ size. For example, the twisted cone model consists of around 6000 triangles and the original u;v coordinates of the VRML rep- resentation can be encoded with binary representation into 7.4KB.
We are currently working on the optimization of the em- bedding algorithm, in the sense that the algorithm will yield a minimal number of patches. We are also considering de- veloping an algorithm for compact packing of the patches.
Acknowledgments
We would like to thank Reuven Bik for his early work on this project, and Roman Manevich and Ronen Gvili for their contribution to the implementation of the algorithm.
References
1. Phillip Azariadis and Nikos Aspragathos. Design of plane developments of doubly curved surfaces.
Computer-aided Design, 29(10):675–685, 1997. 2 2. Chakib Bennis, Jean-Marc Vézien, Gérard Iglésias, and
(a)
(b)
(c)
Figure 3: Embedding of the twisted loop model. The 3D mesh and two of the patches created by the embedding algorithm.
André Gagalowicz. Piecewise surface flattening for non-distorted texture mapping. Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):237–246, July 1991. 2
3. Daniel Cohen-Or, David Levin, and Offir Remez. Pro- gressive compression of arbitrary triangular meshes.
IEEE Visualization ’99, pages 67–72, October 1999. 1 4. Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle. Mul- tiresolution analysis of arbitrary meshes. Proceedings of SIGGRAPH 95, pages 173–182, August 1995. 2 5. Michael S. Floater. Parametrization and smooth ap-
proximation of surface triangulations. Computer Aided Geometric Design, 14(3):231–250, 1997. 2
6. Bruno Lévy and Jean-Laurent Mallet. Non-distorted texture mapping for sheared triangulated meshes. Pro-
ceedings of SIGGRAPH 98, pages 343–352, July 1998.
2
7. Jérôme Maillot, Hussein Yahia, and Anne Verroust. In- teractive texture mapping. Proceedings of SIGGRAPH 93, pages 27–34, August 1993. 2
8. Renato Pajarola and Jarek Rossignac. Compressed pro- gressive meshes. IEEE Transactions on Visualization and Computer Graphics, 6(1):79–93, January - March 2000. 1
9. Gabriel Taubin, André Gueziec, William Horn, and Francis Lazarus. Progressive forest split compression.
Proceedings of SIGGRAPH 98, pages 123–132, July 1998. 1
10. Costa Touma and Craig Gotsman. Triangle mesh com- pression. Graphics Interface ’98, pages 26–34, June 1998. 1
(a) (b)
(c)
(d)
Figure 4: The results of the twisted cone model embedding. (a) The textured 3D mesh; (b) 3D mesh in wireframe; (c) The two patches created by the embedding algorithm; (d) The warped textures.
