Available online at www.sciencedirect.com DIRECT COMPUTERS &GRAPHICS ELSEVIER Computers Graphics 29 (2005)972-979 www.elsevier.com/locate/cag Technical Section A novel constrained texture mapping method based on harmonic map Yanwen Guoa.b.*,Jin Wanga,Hanqiu Sun,Xiufen Cui,Qunsheng Penga.b AState Key Lab of CAD&CG,Zhejiang University,Hangzhou 310027.China Department of Mathematics,Zhejiang University,Hangzhou 310027,China Department of Computer Science and Engineering.CUHK,Hong Kong Abstract In this paper,we present a novel constrained texture mapping method based on the harmonic map.We first project the surface of a 3D model on a planar domain by an angle-based-flattening technique and perform a parametrization. The user then specifies interactively the constraints between the selected feature points on the parametric domain of the 3D model and the corresponding pixels on the texture image;the texture coordinates of other sample points on the 3D model are determined based on harmonic mapping between the parametric domain of the model and the texture image; finally we apply an adaptive local mapping refinement to improve the rendering result in real-time.Compared with other interactive methods,our method provides an analytically accurate solution to the problem,and the energy minimization characteristic of the harmonic map reduces the potential distortion that may result in the constrained texture mapping.Experimental data demonstrate good rendering effects generated by the presented algorithm. C 2005 Elsevier Ltd.All rights reserved. Keywords:Texture mapping:Parametrization:Harmonic map 1.Introduction is commonly performed.Furthermore,it is frequently necessary to ensure a rigid correspondence between the Texture mapping has been widely applied in computer feature points of the 3D object and the respective pixels graphics and virtual reality.Without it,modeling and on the texture plane.For example,consider the mapping rendering the details of complex models would be a shown in Fig.1,where an image of Andrey Hepburn is time-consuming task.The fundamental issue of texture to be mapped onto the 3D head model.In this case we mapping is to construct a one-to-one mapping between must ensure the precise mapping of the eyes,nose,etc. each point on the specified surface area of a 3D object from the image and the model.This problem is and that on the texture plane.To facilitate such a commonly referred to as constrained texture mapping, mapping,a parametrization of the specified surface area for which the texture coordinates of some given feature points on the model must first be specified by the user. *Project supported by National 973 program (No. whereas the rest need be solved by some mechanism. 2002CB312101)and NSFC Grant (No.60033010)and (No. These given feature points are usually called constrained 60403038).and CUHK Direct Grant (No.4450002). points. *Corresponding author.Tel.:+86 571 88206681(503): The constrained texture mapping of a 3D mesh is fax:+8657188206680. more tedious since no intrinsic parametrization of the E-mail address:ywguo@cad.zju.edu.cn (Y.Guo). 3D mesh satisfying such constraints is available. 0097-8493/S-see front matter 2005 Elsevier Ltd.All rights reserved. doi:10.1016j.cag.2005.09.013
Computers & Graphics 29 (2005) 972–979 Technical Section A novel constrained texture mapping method based on harmonic map$ Yanwen Guoa,b,, Jin Wanga , Hanqiu Sunc , Xiufen Cuia , Qunsheng Penga,b a State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310027, China b Department of Mathematics, Zhejiang University, Hangzhou 310027, China c Department of Computer Science and Engineering, CUHK, Hong Kong Abstract In this paper, we present a novel constrained texture mapping method based on the harmonic map. We first project the surface of a 3D model on a planar domain by an angle-based-flattening technique and perform a parametrization. The user then specifies interactively the constraints between the selected feature points on the parametric domain of the 3D model and the corresponding pixels on the texture image; the texture coordinates of other sample points on the 3D model are determined based on harmonic mapping between the parametric domain of the model and the texture image; finally we apply an adaptive local mapping refinement to improve the rendering result in real-time. Compared with other interactive methods, our method provides an analytically accurate solution to the problem, and the energy minimization characteristic of the harmonic map reduces the potential distortion that may result in the constrained texture mapping. Experimental data demonstrate good rendering effects generated by the presented algorithm. r 2005 Elsevier Ltd. All rights reserved. Keywords: Texture mapping; Parametrization; Harmonic map 1. Introduction Texture mapping has been widely applied in computer graphics and virtual reality. Without it, modeling and rendering the details of complex models would be a time-consuming task. The fundamental issue of texture mapping is to construct a one-to-one mapping between each point on the specified surface area of a 3D object and that on the texture plane. To facilitate such a mapping, a parametrization of the specified surface area is commonly performed. Furthermore, it is frequently necessary to ensure a rigid correspondence between the feature points of the 3D object and the respective pixels on the texture plane. For example, consider the mapping shown in Fig. 1, where an image of Andrey Hepburn is to be mapped onto the 3D head model. In this case we must ensure the precise mapping of the eyes, nose, etc. from the image and the model. This problem is commonly referred to as constrained texture mapping, for which the texture coordinates of some given feature points on the model must first be specified by the user, whereas the rest need be solved by some mechanism. These given feature points are usually called constrained points. The constrained texture mapping of a 3D mesh is more tedious since no intrinsic parametrization of the 3D mesh satisfying such constraints is available. ARTICLE IN PRESS www.elsevier.com/locate/cag 0097-8493/$ - see front matter r 2005 Elsevier Ltd. All rights reserved. doi:10.1016/j.cag.2005.09.013 $Project supported by National 973 program (No. 2002CB312101) and NSFC Grant (No. 60033010) and (No. 60403038), and CUHK Direct Grant (No. 4450002). Corresponding author. Tel.: +86 571 882 06681(503); fax: +86 571 882 06680. E-mail address: ywguo@cad.zju.edu.cn (Y. Guo)
Y.Guo et al Computers Graphics 29 (2005)972-979 973 Previous methods of constrained texture mapping of 3D need to bind the boundary of a 3D mesh to a convex meshes are mainly based on iterative optimization which polygon [1-3.10].while others [4,9,12]do not have such provide only an approximate solution.In this paper we constraints and the boundary of the embedded triangles present a novel analytical solution to this problem based is computed during the parametrization. on harmonic map.Our new method is not only accurate While the above approaches allow an image to be but also more efficient than previous methods.Experi- mapped onto a 3D mesh,they make no guarantee of ments show good results of this method(Fig.2). matching features between the model and the texture. Continuous efforts were therefore made concerning constrained texture mapping.Most of the proposed 1.1.Previous work methods [3,13-15]deal with the mesh model with disc topology as the parametrization of sample points within An important step of texture mapping onto a 3D a disc domain and can easily be converted to a problem mesh is the parametrization of the mesh model.This of solving a set of linear equations [2,12].On the other process generates a 2D planar mesh in the parametric hand,a complicated mesh model can always be space which maintains the same topology as the original decomposed into several "meaningful"disc topological 3D mesh,meanwhile minimizing the distortion of metric patches [16]. structures.A valid parametrization must ensure that the Levy et al.proposed a method capable of dealing with parameterized triangles have no foldovers or tears.In iso-parametric curves [3].Subsequently Levy solved the the past several years,many methods of 3D mesh problem of feature mapping by respecting an arbitrary parametrization have been proposed [1-12].For exam- set of constrained features [13].Levy's method works ple:Floater presented a shape preserving method [2], well for a small number of constraints but can lead to Eck et al.based their parametrization method on a invalid parametrization when dealing with a large set of harmonic model [1].and the methods in [9,12]try to constraints.Tang et al.presented a fast analytic method approximate a conformal map.Some of these methods of constrained texture mapping based on radial basis function (RBF)interpolation [14].However their method relies heavily on the choice of the basis function of RBF and the result would be unsatisfactory if the basis functions employed are improper. In a later work,Kraevoy et al.brought forward a P method based on iterative optimization and obtained fine results [15].This method first parameterizes the 3D meshes onto the planar region;then it triangulates the S(xy.z) texture plane with respect to the specified constraints and divides the planar mesh consistently to construct the A correspondence between the texture and the planar X(4,) mesh.Secondly,it conducts a refinement operation to adjust the texture coordinates of the mesh points.This Fig.1.Constrained texture mapping.S(x,y,z)defines a one-to- method needs to add Steiner vertices [15]and the one correspondence between surface A of R'and a subset D of number of Steiner vertices varies from several tens to R2 with some user-defined constraints.For example,the point P thousands according to the complexity and density of on the canthus of the 3D model must correspond with the pixel the mesh model.Consequently,the efficiency of their Pl on the canthus of Hepburn.X()is the inverse of S(). method is low and the solution is approximate. Fig.2.A cow head mapped with the image of a leopard,using the algorithm presented in this paper
Previous methods of constrained texture mapping of 3D meshes are mainly based on iterative optimization which provide only an approximate solution. In this paper we present a novel analytical solution to this problem based on harmonic map. Our new method is not only accurate but also more efficient than previous methods. Experiments show good results of this method (Fig. 2). 1.1. Previous work An important step of texture mapping onto a 3D mesh is the parametrization of the mesh model. This process generates a 2D planar mesh in the parametric space which maintains the same topology as the original 3D mesh, meanwhile minimizing the distortion of metric structures. A valid parametrization must ensure that the parameterized triangles have no foldovers or tears. In the past several years, many methods of 3D mesh parametrization have been proposed [1–12]. For example: Floater presented a shape preserving method [2], Eck et al. based their parametrization method on a harmonic model [1], and the methods in [9,12] try to approximate a conformal map. Some of these methods need to bind the boundary of a 3D mesh to a convex polygon [1–3,10], while others [4,9,12] do not have such constraints and the boundary of the embedded triangles is computed during the parametrization. While the above approaches allow an image to be mapped onto a 3D mesh, they make no guarantee of matching features between the model and the texture. Continuous efforts were therefore made concerning constrained texture mapping. Most of the proposed methods [3,13–15] deal with the mesh model with disc topology as the parametrization of sample points within a disc domain and can easily be converted to a problem of solving a set of linear equations [2,12]. On the other hand, a complicated mesh model can always be decomposed into several ‘‘meaningful’’ disc topological patches [16]. Levy et al. proposed a method capable of dealing with iso-parametric curves [3]. Subsequently Levy solved the problem of feature mapping by respecting an arbitrary set of constrained features [13]. Levy’s method works well for a small number of constraints but can lead to invalid parametrization when dealing with a large set of constraints. Tang et al. presented a fast analytic method of constrained texture mapping based on radial basis function (RBF) interpolation [14]. However their method relies heavily on the choice of the basis function of RBF and the result would be unsatisfactory if the basis functions employed are improper. In a later work, Kraevoy et al. brought forward a method based on iterative optimization and obtained fine results [15]. This method first parameterizes the 3D meshes onto the planar region; then it triangulates the texture plane with respect to the specified constraints and divides the planar mesh consistently to construct the correspondence between the texture and the planar mesh. Secondly, it conducts a refinement operation to adjust the texture coordinates of the mesh points. This method needs to add Steiner vertices [15] and the number of Steiner vertices varies from several tens to thousands according to the complexity and density of the mesh model. Consequently, the efficiency of their method is low and the solution is approximate. ARTICLE IN PRESS Fig. 1. Constrained texture mapping. Sðx; y; zÞ defines a one-toone correspondence between surface A of R3 and a subset D of R2 with some user-defined constraints. For example, the point P on the canthus of the 3D model must correspond with the pixel Pj on the canthus of Hepburn. Xð Þ is the inverse of Sð Þ. Fig. 2. A cow head mapped with the image of a leopard, using the algorithm presented in this paper. Y. Guo et al. / Computers & Graphics 29 (2005) 972–979 973
974 Y.Guo et al.Computers Graphics 29 (2005)972-979 1.2.Overview of our new approach its application in constrained texture mapping.Section 4 describes the details of an adaptive approach for local Our proposed method consists also of three steps.It texture coordinate refinement.Experiment data are first parameterizes a 3D mesh model using the angle- given in Section 5.In the last section,we summarize based-flattening (ABF)method [9]:it then specifies the the proposed method and highlight the future work. corresponding feature points on the 3D model and the texture plane by user interaction and calculates the texture coordinates of all other sample points on the 3D 2.ABF parametrization mesh by harmonic mapping;finally it performs an "adaptive local mapping refinement"to adjust the Our texture mapping method first parameterizes the texture coordinates of some points within the mis- 3D mesh onto the planar region.The chosen parame- matched area.Compared with previous methods,our trization method should minimize the angular or metric method has the following advantages: distortion of the embedded 2D mesh,while still guaranteeing its validity.The ABF method [9]intro- Distortion minimization.Due to the energy minimiza- duced by Sheffer et al.satisfies these conditions.This tion property of the harmonic mapping,the metric method defines the flattening problem entirely in terms distortion of our constrained texture mapping is of angles and minimizes the shape distortion of the small,as is testified by the results. embedded triangles by maintaining a consistent angular Analytical solution.It is an analytically accurate distribution of incident edges around each vertex on the solution to the constrained texture mapping problem, parametric plane.After the angular distributions have while other methods [13,15]are based on iterative been computed by solving an energy equation,the flat optimization and provide only approximate solutions. mesh can be fully determined once we fix the position of High performance.Our method can deal with a large an initial interior vertex and the length and direction of amount of data.Since it involves solving only sparse an initial edge incident to that vertex. linear symmetric equations,our algorithm is much As the ABF method can ensure the validity of more efficient and much faster than others. parametrization and minimize the angular distortion,it Real-time refinement.With our "adaptive local is employed in our approach to parameterize the 3D mapping refinement"technique,the result of the mesh.Fig.3 shows the parametrization results of two mapping can be refined in real-time. 3D mesh models. Concise process.Our method need only specify a few correspondence constraints then solves the texture coordinates using a harmonic map while the method 3.The harmonic map provided by Kraevoy et al.needs to segment the mesh and texture into several patches with Steiner We apply the harmonic map technique to establish the vertices [15]. correspondence between the parameterized 2D mesh and the texture plane.Harmonic maps have been The remainder of this paper is organized as follows. studied intensively by many researchers over a long Section 2 gives a brief review of ABF parametrization. period of time.It is an extreme of the energy density Section 3 introduces the concept of harmonic map and that satisfies the corresponding Euler-Lagrange (a) (b) (c) (d) Fig.3.3D models and corresponding results of ABF parametrization.(a),(c)the face model (1344 triangles and 690 vertices)and the cow head model (1896 triangles,972 vertices);(b),(d)the parametrization results of (a)and (c)
1.2. Overview of our new approach Our proposed method consists also of three steps. It first parameterizes a 3D mesh model using the anglebased-flattening (ABF) method [9]; it then specifies the corresponding feature points on the 3D model and the texture plane by user interaction and calculates the texture coordinates of all other sample points on the 3D mesh by harmonic mapping; finally it performs an ‘‘adaptive local mapping refinement’’ to adjust the texture coordinates of some points within the mismatched area. Compared with previous methods, our method has the following advantages: Distortion minimization. Due to the energy minimization property of the harmonic mapping, the metric distortion of our constrained texture mapping is small, as is testified by the results. Analytical solution. It is an analytically accurate solution to the constrained texture mapping problem, while other methods [13,15] are based on iterative optimization and provide only approximate solutions. High performance. Our method can deal with a large amount of data. Since it involves solving only sparse linear symmetric equations, our algorithm is much more efficient and much faster than others. Real-time refinement. With our ‘‘adaptive local mapping refinement’’ technique, the result of the mapping can be refined in real-time. Concise process. Our method need only specify a few correspondence constraints then solves the texture coordinates using a harmonic map while the method provided by Kraevoy et al. needs to segment the mesh and texture into several patches with Steiner vertices [15]. The remainder of this paper is organized as follows. Section 2 gives a brief review of ABF parametrization. Section 3 introduces the concept of harmonic map and its application in constrained texture mapping. Section 4 describes the details of an adaptive approach for local texture coordinate refinement. Experiment data are given in Section 5. In the last section, we summarize the proposed method and highlight the future work. 2. ABF parametrization Our texture mapping method first parameterizes the 3D mesh onto the planar region. The chosen parametrization method should minimize the angular or metric distortion of the embedded 2D mesh, while still guaranteeing its validity. The ABF method [9] introduced by Sheffer et al. satisfies these conditions. This method defines the flattening problem entirely in terms of angles and minimizes the shape distortion of the embedded triangles by maintaining a consistent angular distribution of incident edges around each vertex on the parametric plane. After the angular distributions have been computed by solving an energy equation, the flat mesh can be fully determined once we fix the position of an initial interior vertex and the length and direction of an initial edge incident to that vertex. As the ABF method can ensure the validity of parametrization and minimize the angular distortion, it is employed in our approach to parameterize the 3D mesh. Fig. 3 shows the parametrization results of two 3D mesh models. 3. The harmonic map We apply the harmonic map technique to establish the correspondence between the parameterized 2D mesh and the texture plane. Harmonic maps have been studied intensively by many researchers over a long period of time. It is an extreme of the energy density that satisfies the corresponding Euler–Lagrange ARTICLE IN PRESS Fig. 3. 3D models and corresponding results of ABF parametrization. (a), (c) the face model (1344 triangles and 690 vertices) and the cow head model (1896 triangles, 972 vertices); (b), (d) the parametrization results of (a) and (c). 974 Y. Guo et al. / Computers & Graphics 29 (2005) 972–979
Y.Guo et al.Computers Graphics 29 (2005)972-979 975 equation.Owing to its important properties of energy Since Bi,B,and B are computed as linear expressions minimization,harmonic maps have wide applications to of s and y,the above equations define a mapping problems such as mesh parametrization [1]and surface between n and u,v.Assume the mapping is i.e., matching[l7刀. (p)=p,what we need to do is to solve for the In the following,we consider a special 2D harmonic minimum of Egs.(3)and (4). map that maps between two simple manifolds with disc Note that in the discrete case,(3)and (4)are topology. approximated by: 3.1.Two-dimensional harmonic map 1=∑Iau/e)2+(au/an1, (7) Suppose:D and R are two parametric domains of disc Iw)-∑【ou/e2+(au/an门 (8) topology on the2 Dplane,(e,)∈D,(u,t)∈2.φ represents a mapping between D and 2,i.e.,(,n)= Substituting (5),(6)on each triangle in (7),(8)and (u,v)with u=(e,n)and v=(n).is harmonic if minimizing them,respectively,we obtain two sets of satisfy the following two equations: linear algebraic equations: △u=a2u/6e2+a2u/0m2=0∈2， (1) Anxn kunxl: (9) △x=a2v/ae2+av/r2=0∈2. (2) Anxn了=Enx (10) To get the analytical form of a harmonic map,let: where A isa coefficient matrix andkkare two known =∫a/aer+a/aidd (3) vectors related to the specified texture coordinates of constrained points,which can be easily obtained through the minimization process.u=(u,u...,u) +dedn. (4) andv=(v1,2,...,are the unknown vectors to be solved.They represent the texture coordinates of the It is easy to show that the solution of min /(u)and unconstrained sample points.Due to the uniform min I(v)yields a 2D harmonic mapping.In fact I(u)and coefficients about u and v in (5)and(6),the coefficient I(v)stand for the energy function which estimates the matrices about u and v are the same. distortions of a 2D mesh when it is mapped to the It is easy to see that the matrix A is symmetric, texture plane,the harmonic map minimizes such positive definite and sparse,the conjugate gradient distortions.In the following we describe in detail how method can be used to solve the equations effectively to find the harmonic map. [18- 3.2.Applying harmonic map to texture mapping 4.Adaptive local mapping refinement Suppose the source region D of the harmonic map is a planar embedding of the 3D mesh resulting from parametrization:DUA',where A'represents a triangle Constrained texture mapping normally involves spe- cifying a large number of accurate feature points on of D with A'=A(ppp),p=(,is the embedding both the mesh model and the texture plane.If the feature point of a vertex on the 3D mesh.The solution region points on the 3D model are not matched precisely with is the triangular mesh on the texture plane with the same the respective pixels in the texture,the texture mapping topology as D: result will be poor (see Fig.5d).We then need to adjust 2≈UA,△=△p,P,Pk),pi=(u,), interactively the constrained texture pixels with respect where p;refers to the texture coordinate of p'. to the selected feature points on the 3D model in order Assume that a point p'=(,n)lies in A'and Bi,B and to generate a satisfactory rendering effect.Unfortu- nately,most previous methods need to re-calculate B&are the barycentric coordinates of p'in A',let a point texture coordinates of the entire vertex set of the 3D p=(u,v)in A with the same barycentric coordinates as p',then in each triangle A we have: model when adjusting the texture coordinate of even one vertex.This significantly decreases the efficiency of p=BiP:+BiP+BkPk, constrained texture mapping.In fact,the effect imposed by adjusting the texture coordinate of a vertex is mainly i.e., exerted in a local area (see Appendix),so we need only u=B西十Bj西+Bkk, (5) refine the texture coordinates of the vertices which are near to the concerned vertex.We call this approach Bivi+Bjtj +Bkuk. (6) "adaptive local mapping refinement
equation. Owing to its important properties of energy minimization, harmonic maps have wide applications to problems such as mesh parametrization [1] and surface matching [17]. In the following, we consider a special 2D harmonic map that maps between two simple manifolds with disc topology. 3.1. Two-dimensional harmonic map Suppose: D and O are two parametric domains of disc topology on the 2D plane, ð; ZÞ 2 D, ðu; vÞ 2 O. f represents a mapping between D and O, i.e., fð; ZÞ ¼ ðu; vÞ with u ¼ fuð; ZÞ and v ¼ fvð; ZÞ. f is harmonic if fu, fv satisfy the following two equations: Du ¼ q2 u=q 2 þ q2 u=qZ2 ¼ 0 2 O, (1) Dv ¼ q2 v=q 2 þ q2 v=qZ2 ¼ 0 2 O. (2) To get the analytical form of a harmonic map, let: IðuÞ ¼ 1 2 Z Z O ½ðqu=qÞ 2 þ ðqu=qZÞ 2 d dZ (3) IðvÞ ¼ 1 2 Z Z O ½ðqv=qÞ 2 þ ðqv=qZÞ 2 d dZ. (4) It is easy to show that the solution of min IðuÞ and min IðvÞ yields a 2D harmonic mapping. In fact IðuÞ and IðvÞ stand for the energy function which estimates the distortions of a 2D mesh when it is mapped to the texture plane, the harmonic map minimizes such distortions. In the following we describe in detail how to find the harmonic map. 3.2. Applying harmonic map to texture mapping Suppose the source region D of the harmonic map is a planar embedding of the 3D mesh resulting from parametrization: D [D0 , where D0 represents a triangle of D with D0 ¼ Dðp0 i ; p0 j ; p0 kÞ, p0 i ¼ ði; ZiÞ is the embedding point of a vertex on the 3D mesh. The solution region O is the triangular mesh on the texture plane with the same topology as D: O [D; D ¼ Dðpi; pj; pkÞ; pi ¼ ðui; viÞ, where pi refers to the texture coordinate of p0 . Assume that a point p0 ¼ ð; ZÞ lies in D0 and Bi; Bj and Bk are the barycentric coordinates of p0 in D0 , let a point p ¼ ðu; vÞ in D with the same barycentric coordinates as p0 , then in each triangle D we have: p ¼ Bipi þ Bjpj þ Bkpk, i.e., u ¼ Biui þ Bjuj þ Bkuk, (5) v ¼ Bivi þ Bjvj þ Bkvk. (6) Since Bi, Bj and Bk are computed as linear expressions of and Z, the above equations define a mapping between , Z and u, v. Assume the mapping is f, i.e., fðp0 Þ ¼ p, what we need to do is to solve for the minimum of Eqs. (3) and (4). Note that in the discrete case, (3) and (4) are approximated by: IðuÞ ¼ 1 2 X½ðqu=qÞ 2 þ ðqu=qZÞ 2 , (7) IðvÞ ¼ 1 2 X½ðqv=qÞ 2 þ ðqv=qZÞ 2 . (8) Substituting (5), (6) on each triangle in (7), (8) and minimizing them, respectively, we obtain two sets of linear algebraic equations: Ann !u ¼ ku !n1, (9) Ann !v ¼ kv !n1, (10) where A is a coefficient matrix and ku !, kv ! are two known vectors related to the specified texture coordinates of constrained points, which can be easily obtained through the minimization process. !u ¼ ðu1; u2; ... ; unÞ and !v ¼ ðv1; v2; ... ; vnÞ are the unknown vectors to be solved. They represent the texture coordinates of the unconstrained sample points. Due to the uniform coefficients about u and v in (5) and (6), the coefficient matrices about !u and !v are the same. It is easy to see that the matrix A is symmetric, positive definite and sparse, the conjugate gradient method can be used to solve the equations effectively [18]. 4. Adaptive local mapping refinement Constrained texture mapping normally involves specifying a large number of accurate feature points on both the mesh model and the texture plane. If the feature points on the 3D model are not matched precisely with the respective pixels in the texture, the texture mapping result will be poor (see Fig. 5d). We then need to adjust interactively the constrained texture pixels with respect to the selected feature points on the 3D model in order to generate a satisfactory rendering effect. Unfortunately, most previous methods need to re-calculate texture coordinates of the entire vertex set of the 3D model when adjusting the texture coordinate of even one vertex. This significantly decreases the efficiency of constrained texture mapping. In fact, the effect imposed by adjusting the texture coordinate of a vertex is mainly exerted in a local area (see Appendix), so we need only refine the texture coordinates of the vertices which are near to the concerned vertex. We call this approach ‘‘adaptive local mapping refinement’’. ARTICLE IN PRESS Y. Guo et al. / Computers & Graphics 29 (2005) 972–979 975
976 Y.Guo et al.Computers Graphics 29 (2005)972-979 (a) (b) (c) Fig.4.(a)On the 3D mesh model,the green vertices belong to 1-ring of vi;the blue are 2-ring of vi.(b)The green vertices are 2-ring region of vi.(c)On the texture plane,t;is the texture point corresponding to ti.A,A2 of v;is the sum of displacement of the green points,blue points,respectively,during each adjustment of t;on the texture plane. Assume that vi,P,are a pair of constrained feature Use harmonic map (as in Section 3.2)to adjust points on the 3D mesh and the texture plane that need to those texture coordinates of the vertices included be adjusted.Normally,we adjust the positions of p on in k-ring region of ti: the texture plane to fit ti. Compute△of vi;△=△k; For description convenience,we give the following =k+1; notations for a 3D mesh model (see Fig.4): if k>K return; end topological distance between vi and vi:the number of end edges on the shortest path connecting vi with v. k-ring of vi:those vertices whose topological distance Since our approach involves solving low rank sparse to vi is k. equations,it is efficient and can be performed in real- k-ring region of v:those vertices whose topological time.If several pairs of feature points on the 3D model distance from v is not greater than k. and the texture plane need to be adjusted,the above .Ak of v:total texture coordinates'variance of the approach can be performed iteratively.Fig.5 shows an vertices within the k-ring of vi. example of real-time adjustment. After the user adjusts p,our algorithm first re- calculates the texture coordinates of vertices within the 5.Experimental results 1-ring of vi by using the harmonic model described in Section 3 and solving a set of equations whose rank is We employed several typical models and textures to equal to the vertex number of the I-ring,while the test our algorithm on an Intel Pentium IV 1.6GHz PC texture coordinates of vertices outside the 1-ring with 256 MB main memory under the Windows XP remain unchanged;if Al of t is smaller than a given operating system (In Figs.2,6-8,the red dots are the threshold,the algorithm terminates:otherwise the constraints).Table I lists the performance statistics of algorithm continues to adjust the texture coordinates our algorithm,including the number of triangles and of the 2-ring region of vi which involves solving vertices of the mesh model (#Tris/Vers),the number of equations of a higher rank.The above process is constraints specified (#Cons),the rank of Egs.(3)and iteratively conducted until the final variance is smaller (4)(#Egas),the number of iterations for solving the than the threshold or the iterative count reaches a equations (#Ites)and the computation time (Running maximum constant.This approach can be described time). briefly as follows. In Fig.6,the image of a tiger (a)and a leopard(c)are mapped onto a face model with 23 and 24 constraints, respectively.Fig.6(b)and (d)show two rendering Algorithm:Adaptive local mapping refinement results. Fig.7 shows the mapping of an image of girl shirt stepl Given a threshold and a positive constant K. onto a body model composed of 3016 triangles,it takes step2 Set k 1 and A=+o0. 0.472s to get the fine rendering result (Fig.7(c)). step3 while△>e Fig.8 shows the result of mapping a tiger image to the begin cow head model (the same one as Fig.3(c)),which has
Assume that vi, pi are a pair of constrained feature points on the 3D mesh and the texture plane that need to be adjusted. Normally, we adjust the positions of pi on the texture plane to fit vi. For description convenience, we give the following notations for a 3D mesh model (see Fig. 4): topological distance between vi and vj: the number of edges on the shortest path connecting vi with vj. k-ring of vi: those vertices whose topological distance to vi is k. k-ring region of vi: those vertices whose topological distance from vi is not greater than k. Dk of vi: total texture coordinates’ variance of the vertices within the k-ring of vi. After the user adjusts pi, our algorithm first recalculates the texture coordinates of vertices within the 1-ring of vi by using the harmonic model described in Section 3 and solving a set of equations whose rank is equal to the vertex number of the 1-ring, while the texture coordinates of vertices outside the 1-ring remain unchanged; if D1 of vi is smaller than a given threshold, the algorithm terminates; otherwise the algorithm continues to adjust the texture coordinates of the 2-ring region of vi which involves solving equations of a higher rank. The above process is iteratively conducted until the final variance is smaller than the threshold or the iterative count reaches a maximum constant. This approach can be described briefly as follows. Algorithm: Adaptive local mapping refinement step1 Given a threshold and a positive constant K. step2 Set k ¼ 1 and D ¼ þ1. step3 while n4 begin Use harmonic map (as in Section 3.2) to adjust those texture coordinates of the vertices included in k-ring region of vi; Compute Dk of vi; D ¼ Dk; k ¼ k þ 1; if k4K return; end end Since our approach involves solving low rank sparse equations, it is efficient and can be performed in realtime. If several pairs of feature points on the 3D model and the texture plane need to be adjusted, the above approach can be performed iteratively. Fig. 5 shows an example of real-time adjustment. 5. Experimental results We employed several typical models and textures to test our algorithm on an Intel Pentium IV 1.6 GHz PC with 256MB main memory under the Windows XP operating system (In Figs. 2, 6–8, the red dots are the constraints). Table 1 lists the performance statistics of our algorithm, including the number of triangles and vertices of the mesh model (#Tris/Vers), the number of constraints specified (#Cons), the rank of Eqs. (3) and (4) (#Eqas), the number of iterations for solving the equations (#Ites) and the computation time (Running time). In Fig. 6, the image of a tiger (a) and a leopard (c) are mapped onto a face model with 23 and 24 constraints, respectively. Fig. 6(b) and (d) show two rendering results. Fig. 7 shows the mapping of an image of girl shirt onto a body model composed of 3016 triangles, it takes 0.472 s to get the fine rendering result (Fig. 7(c)). Fig. 8 shows the result of mapping a tiger image to the cow head model (the same one as Fig. 3(c)), which has ARTICLE IN PRESS Fig. 4. (a) On the 3D mesh model, the green vertices belong to 1-ring of vi; the blue are 2-ring of vi. (b) The green vertices are 2-ring region of vi. (c) On the texture plane, ti is the texture point corresponding to vi. D1, D2 of vi is the sum of displacement of the green points, blue points, respectively, during each adjustment of ti on the texture plane. 976 Y. Guo et al. / Computers & Graphics 29 (2005) 972–979
Y.Guo et al.Computers Graphics 29 (2005)972-979 977 (b) (c) (d) (e) (n (g) Fig.5.Mapping a facial image (b)to a 3D face model (a),we get (c).However,the quality of the eyelid (region in red rectangle of (c)) is less satisfactory and needs be refined.(d)is a close-up of the eyelid.(f)is the result of"adaptive local mapping refinement"with two iterations after adjusting p;and (g)is a close-up of the refined eyelid.(e)is the zoomed region surrounded by the red rectangle in (a);the vertices within the 2-ring region of t;are showed in green;while the vertices included in the 3-ring of v;are shown in yellow.As the 2-ring region of v;contains rare vertices,solving the local mapping is real-time. (a) (b) (c) (d) Fig.6.A face model is mapped with different textures:(a).(c)are original textures with constrained feature points;(b).(d)are textured results. 1896 triangles.28 constraints were imposed.The are achieved,and the result can be refined in real-time equations were solved by 118 iterations in 0.0638s.In with an "adaptive local mapping refinement"technique. Fig.2,a leopard face is mapped onto the cow head Experiments show that our algorithm is efficient and model. robust. An interesting problem for future research is the automatic specification of constraints,the technology of 6.Conclusions and future work biometrics and computer vision can help with the placement of these constraints.Besides,currently a In this paper a novel constrained texture mapping complicated model,(e.g.,one with several genera)must method based on harmonic mapping is presented;it be cut into several parts for texture mapping leading to provides an analytically accurate solution to the discontinuity of the rendering result.How to resolve this problem of constrained texture mapping.Good results problem is another piece of future work
1896 triangles. 28 constraints were imposed. The equations were solved by 118 iterations in 0.0638 s. In Fig. 2, a leopard face is mapped onto the cow head model. 6. Conclusions and future work In this paper a novel constrained texture mapping method based on harmonic mapping is presented; it provides an analytically accurate solution to the problem of constrained texture mapping. Good results are achieved, and the result can be refined in real-time with an ‘‘adaptive local mapping refinement’’ technique. Experiments show that our algorithm is efficient and robust. An interesting problem for future research is the automatic specification of constraints, the technology of biometrics and computer vision can help with the placement of these constraints. Besides, currently a complicated model, (e.g., one with several genera) must be cut into several parts for texture mapping leading to discontinuity of the rendering result. How to resolve this problem is another piece of future work. ARTICLE IN PRESS Fig. 6. A face model is mapped with different textures: (a), (c) are original textures with constrained feature points; (b), (d) are textured results. Fig. 5. Mapping a facial image (b) to a 3D face model (a), we get (c). However, the quality of the eyelid (region in red rectangle of (c)) is less satisfactory and needs be refined. (d) is a close-up of the eyelid. (f) is the result of ‘‘adaptive local mapping refinement’’ with two iterations after adjusting pi and (g) is a close-up of the refined eyelid. (e) is the zoomed region surrounded by the red rectangle in (a); the vertices within the 2-ring region of vi are showed in green; while the vertices included in the 3-ring of vi are shown in yellow. As the 2-ring region of vi contains rare vertices, solving the local mapping is real-time. Y. Guo et al. / Computers & Graphics 29 (2005) 972–979 977
978 Y.Guo et al.Computers Graphics 29 (2005)972-979 (a) (b) (c) Fig.7.Texturing of a body model:(a)3D body model;(b)the texture image with constrained feature points(red dots):(c)textured model. (a) (b) (c) Fig.8.Texturing of a cow head:(a)the texture image with constrained feature points (red dots);(b).(c)textured model at different views. Table 1 Performance results Model/Texture #Tris/Vers #Cons #Eqas #Ites Running time(s) Cow/Leopard 1896/972 21 951 122 0.064 Rachel/Sadam 1344/690 4 666 81 0.045 Rachel/Tiger 1344/690 667 86 0.047 Rachel/Leopard 1344/690 666 83 0.046 Body/Shirt 3016/1650 1 1631 436 0.472 Cow/Tiger 1896/972 8 944 118 0.0638 Appendix coordinates of the vertices within I-ring of v are re-calculated. Without losing generality assume that vi,Pare a pair The equations deduced from the harmonic map of constrained feature points on the 3D mesh and to solve initial texture coordinates in Subsection 3 texture image,we show that the "adaptive local is the formula (5).Here,we only consider Au=ku, mapping refinement"with one iteration after adjusting where A=(dij)nxm is a symmetric matrix relating the texture coordinate of one constrained feature vertex to the 3D model.=(.u)is the initial on the 3D mesh produces an approximation to the texture coordinates vector and ku=(k,k,...,k)T accurate solution.In this case,only the texture is the vector resulting from constrained feature points
Appendix Without losing generality assume that vi, pi are a pair of constrained feature points on the 3D mesh and texture image, we show that the ‘‘adaptive local mapping refinement’’ with one iteration after adjusting the texture coordinate of one constrained feature vertex on the 3D mesh produces an approximation to the accurate solution. In this case, only the texture coordinates of the vertices within 1-ring of vi are re-calculated. The equations deduced from the harmonic map to solve initial texture coordinates in Subsection 3 is the formula (5). Here, we only consider A u! ¼ ku !, where A ¼ ðai;jÞnn is a symmetric matrix relating to the 3D model, !u ¼ ðu1; u2; ... ; unÞ T is the initial texture coordinates vector and ku ! ¼ ðku1; ku2; ... ; kunÞ T is the vector resulting from constrained feature points. ARTICLE IN PRESS Fig. 8. Texturing of a cow head: (a) the texture image with constrained feature points (red dots); (b), (c) textured model at different views. Table 1 Performance results Model/Texture #Tris/Vers #Cons #Eqas #Ites Running time (s) Cow/Leopard 1896/972 21 951 122 0.064 Rachel/Sadam 1344/690 24 666 81 0.045 Rachel/Tiger 1344/690 23 667 86 0.047 Rachel/Leopard 1344/690 24 666 83 0.046 Body/Shirt 3016/1650 19 1631 436 0.472 Cow/Tiger 1896/972 28 944 118 0.0638 Fig. 7. Texturing of a body model: (a) 3D body model; (b) the texture image with constrained feature points (red dots); (c) textured model. 978 Y. Guo et al. / Computers & Graphics 29 (2005) 972–979
Y.Guo et al.Computers Graphics 29 (2005)972-979 979 Assume:1-ring of v=(v1,...,vi,2-ring (+1, References ,4m小，=(，)，m=(u+1,,+m)T =(u+m+l...,u),ka =(kul......u),kam [1]Eck M,DeRose T.Duchamp T,Hoppe H,Lounsbery M, Stuetzle W.Multiresolution analysis of arbitrary meshes. ()m),kam=(m),then In:Proceedings of SIGGRAPH'95,Los Angeles,CA: 1995.p.173-82. Au=ku can be written as: [2]Floater MS.Parametrization and smooth approximation of surface triangulations.Computer Aided Geometric Alxl Bixm 0x-1-m Design1997:143:231-50. Dmxm Emx(n-f-m) [3]Levy B.Mallet JL.Non-distortion texture mapping for 0(n-f-m)xl 。Ea--m)xm Grin--mx-l sheared triangulated meshes.In:Proceedings of SIG- (11) GRAPH'98,Orlando,FL;1998.p.343-52. [4]Hormann K,Greiner G.MIPS-An efficient global para- in particular,the upper-right and lower-left submatrices metrization method.In:Curve and surface design con- of A are zero matrices reflecting that there are no edges ference proceedings,Saint,Malo;1999.p.153-62. that directly link l-ring vertices of v with the vertices out [5]McCarteny J,Hinds BK,Seow BL.The flattening of of 2-ring. triangulated surfaces incorporating darts and gussets. After adjusting P,kul..u are changed to Computer Aided Design 1999:31(4):249-60. kl+△l,…kl+△l.Let△=(dwl,,△d),thus [6]Marcum DL,Gaiter JA.Unstructured surface grid the objective equation is changed to: generation using global mapping and physical space approximation.In:Eighth international meshing round. table,South Lake Tahoe,CA:1999.p.397-406. 0xe-l- Emxie-l-m) [7]Haker S.Angenent S,Tannenbaum A.Kikinis R.Sapiro -1-mxl E(n--m)xm G(n-1-m)x(n- G,Halle M.Conformal surface parametrization for texture mapping.IEEE Transactions on Visualization and Computer Graphics 2000;6(2):181-9. (12) [8]Ecksteinl L.Surazhsky V,Gotsman C.Texture mapping where u=()is the accurate solution with hard constraints.Computer Graphics Forum deduced from the harmonic map. 2001:20(3):95-104. However the texture coordinates vector derived after [9]Sheffer A.Sturler ED.Parametrization of faceted surfaces for meshing using angle-based flattening.Engineering with “adaptive local mapping refinement'”is7 Computers200:17(3):326-37. (u),in which u i.e.the texture coordinates [10]Sander PV,Snyder J,Gortler S,Hoppe H.Texture mapping progressive meshes.In:Proceedings of ACM of 1-ring are computed by solving: SIGGRAPH'01,Los Angeles CA:2001.p.409-16. Ax+Bxmd=k+。 [1I]Desbrun M,Meyer M,Alliez P.Intrinsic parametrizations of surfaces meshes.Computer Graphics Forum It is casy to see that and正satisfy(⑦by 2002:21(3)210-8. [12]Levy B.Petiejean S.Ray N.Maillot J.Least squares substituting with,while dose not satisfy: conformal maps for automatic texture atlas gene- ration.ACM Transactions on Graphics 2002:21(3): 362-71. Bmxlu+Daxm U+Emx(a-1-m)=kum [13]Levy B.Constrained texture mapping for polygonal However.it follows from (6)that: meshes.In:Proceedings of SIGGRAPH'01,Los Angeles CA:2001.p.417-24. Bm+Dmm·+Emxa--m=K+Bnx·(-). [14]Tang Y,Wang J.Bao HJ,Peng QS.RBF-based constrained texture mapping.Computers and Graphics and therefore, 2003:27(3):415-22. [15]Kraevoy V,Sheffer A.Gotsman C.Matchmaker:Con- 言-d=A-l.△i油AE=0.,0,(Bwx-(间-t》,0.,0. structing constrained texture maps.ACM Transactions on Graphics2003,22(3):326-33. In general,the total displacement of texture coordinates [16]Zuckerberger E,Tal A,Shlafman S.Polyhedral surface decomposition with applications.Computers and Graphics of 1-ring is relatively small.Hence if ll(u)< 2002:26(5):733-43. thenl-uI≤e,IA-lI·lBmx. [17]Zhang D,Hebert M.Harmonic maps and their applica- tions in surface matching.In:IEEE proceedings of This shows that the texture coordinates derived by computer vision and pattern recognition,Colorado; "adaptive local mapping refinement"is an acceptable 1999.p.524-30. approximation to the accurate solution computed from [18]Cheng YP.Matrix theory.Xian,China:Northwestern harmonic map. Polytechnical University Press:2001
Assume: 1-ring of vi ¼ fv1; ... ; vlg, 2-ring ¼ fvlþ1; ... ; vlþmg, ul ! ¼ ðu1; ... ; ulÞ T, um ! ¼ ðulþ1; ... ; ulþmÞ T, un ! ¼ ðulþmþ1; ... ; unÞ T, kul ! ¼ ðku1; ... ; kulÞ T, kum ! ¼ ðkuðlþ1Þ; ... ; kuðlþmÞÞ T, kun ! ¼ ðkuðlþmþ1Þ; ... ; kunÞ T, then A u! ¼ ku ! can be written as: All Blm 0lðnlmÞ Bml Dmm EmðnlmÞ 0ðnlmÞl EðnlmÞm GðnlmÞðnlmÞ 0 B@ 1 CA ul ! um ! un ! 0 B@ 1 CA ¼ kul ! kum ! kun ! 0 BB@ 1 CCA, (11) in particular, the upper-right and lower-left submatrices of A are zero matrices reflecting that there are no edges that directly link 1-ring vertices of vi with the vertices out of 2-ring. After adjusting pi, ku1,ykul are changed to ku1 þ Du1,y,kul þ Dul. Let Dl ! ¼ ðDu1; ... ; DulÞ T, thus the objective equation is changed to: All Blm 0lðnlmÞ Bml Dmm EmðnlmÞ 0ðnlmÞl EðnlmÞm GðnlmÞðnlmÞ 0 B@ 1 CA u1 l ! u1 m ! u1 n ! 0 BBBB@ 1 CCCCA ¼ kul ! þ Dl ! kum ! kun ! 0 BB@ 1 CCA, (12) where u !1 ¼ ðu1 l !; u1 m !; u1 n !Þ is the accurate solution deduced from the harmonic map. However the texture coordinates vector derived after ‘‘adaptive local mapping refinement’’ is u !0 ¼ ðu1 l !; um !; un !Þ, in which u1 l !, i.e. the texture coordinates of 1-ring are computed by solving: All u1 l !þ Blm um ! ¼ kul ! þ Dl !. It is easy to see that u1 l ! and un ! satisfy (7) by substituting u1 m ! with um !, while um ! dose not satisfy: Bml u1 l !þ Dmm um ! þ EmðnlmÞ un ! ¼ kum !. However, it follows from (6) that: Bml u1 l !þ Dmm um ! þ EmðnlmÞ un ! ¼ kum ! þ Bml ðu1 l ! ul !Þ, and therefore, u !0 u !1 ¼ A1 Dku ! with Dku ! ¼ ð0; ... ; 0;ðBml ðu1 l ! ul !ÞÞT; 0; ... ; 0Þ. In general, the total displacement of texture coordinates of 1-ring is relatively small. Hence if kðu1 l ! ul !Þko, then k u !0 u !1 kp kA1 kkBmlk: This shows that the texture coordinates derived by ‘‘adaptive local mapping refinement’’ is an acceptable approximation to the accurate solution computed from harmonic map. References [1] Eck M, DeRose T, Duchamp T, Hoppe H, Lounsbery M, Stuetzle W. Multiresolution analysis of arbitrary meshes. In: Proceedings of SIGGRAPH’95, Los Angeles, CA; 1995. p. 173–82. [2] Floater MS. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 1997;14(3):231–50. [3] Levy B, Mallet JL. Non-distortion texture mapping for sheared triangulated meshes. In: Proceedings of SIGGRAPH’98, Orlando, FL; 1998. p. 343–52. [4] Hormann K, Greiner G. MIPS-An efficient global parametrization method. In: Curve and surface design conference proceedings, Saint, Malo; 1999. p. 153–62. [5] McCarteny J, Hinds BK, Seow BL. The flattening of triangulated surfaces incorporating darts and gussets. Computer Aided Design 1999;31(4):249–60. [6] Marcum DL, Gaiter JA. Unstructured surface grid generation using global mapping and physical space approximation. In: Eighth international meshing roundtable, South Lake Tahoe, CA; 1999. p. 397–406. [7] Haker S, Angenent S, Tannenbaum A, Kikinis R, Sapiro G, Halle M. Conformal surface parametrization for texture mapping. IEEE Transactions on Visualization and Computer Graphics 2000;6(2):181–9. [8] Ecksteinl L, Surazhsky V, Gotsman C. Texture mapping with hard constraints. Computer Graphics Forum 2001;20(3):95–104. [9] Sheffer A, Sturler ED. Parametrization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers 2001;17(3):326–37. [10] Sander PV, Snyder J, Gortler S, Hoppe H. Texture mapping progressive meshes. In: Proceedings of ACM SIGGRAPH’01, Los Angeles CA; 2001. p. 409–16. [11] Desbrun M, Meyer M, Alliez P. Intrinsic parametrizations of surfaces meshes. Computer Graphics Forum 2002;21(3):210–8. [12] Levy B, Petiejean S, Ray N, Maillot J. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 2002;21(3): 362–71. [13] Levy B. Constrained texture mapping for polygonal meshes. In: Proceedings of SIGGRAPH’01, Los Angeles CA; 2001. p. 417–24. [14] Tang Y, Wang J, Bao HJ, Peng QS. RBF-based constrained texture mapping. Computers and Graphics 2003;27(3):415–22. [15] Kraevoy V, Sheffer A, Gotsman C. Matchmaker: Constructing constrained texture maps. ACM Transactions on Graphics 2003;22(3):326–33. [16] Zuckerberger E, Tal A, Shlafman S. Polyhedral surface decomposition with applications. Computers and Graphics 2002;26(5):733–43. [17] Zhang D, Hebert M. Harmonic maps and their applications in surface matching. In: IEEE proceedings of computer vision and pattern recognition, Colorado; 1999. p. 524–30. [18] Cheng YP. Matrix theory. Xian, China: Northwestern Polytechnical University Press; 2001. ARTICLE IN PRESS Y. Guo et al. / Computers & Graphics 29 (2005) 972–979 979