当前位置：文档库 › mean_value

mean_value

Mean Value Coordinates

Michael S.Floater

Abstract:We derive a generalization of barycentric coordinates which allows a vertex in a planar triangulation to be expressed as a convex combination of its neighbouring vertices. The coordinates are motivated by the Mean Value Theorem for harmonic functions and can be used to simplify and improve methods for parameterization and morphing. Keywords:barycentric coordinates,harmonic function,mean value theorem,parameteri-zation,morphing.

1.Introduction

Let v0,v1,...,v k be points in the plane with v1,...,v k arranged in an anticlockwise order-ing around v0,as in Figure1.The points v1,...,v k form a star-shaped polygon with v0 in its kernel.Our aim is to study sets of weightsλ1,...,λk≥0such that

i=1λi v i=v0,(1.1)

i=1λi=1.(1.2)

Equation(1.1)expresses v0as a convex combination of the neighbouring points v1,...,v k. In the simplest case k=3,the weightsλ1,λ2,λ3are uniquely determined by(1.1)and(1.2) alone;they are the barycentric coordinates of v0with respect to the triangle[v1,v2,v3], and they are positive.This motivates calling any set of non-negative weights satisfying (1.1–1.2)for general k,a set of coordinates for v0with respect to v1,...,v k.

There has long been an interest in generalizing barycentric coordinates to k-sided polygons with a view to possible multisided extensions of B′e zier surfaces;see for example [8].In this setting,one would normally be free to choose v1,...,v k to form a convex polygon but would need to allow v0to be any point inside the polygon or on the polygon, i.e.on an edge or equal to a vertex.

More recently,the need for such coordinates arose in methods for parameterization [2]and morphing[5],[6]of triangulations.Here the points v0,v1,...,v k will be vertices of a(planar)triangulation and so the point v0will never lie on an edge of the polygon formed by v1,...,v k.

If we require no particular properties of the coordinates,the problem is easily solved. Because v0lies in the convex hull of v1,...,v k,there must exist at least one triangle

T=[v i

1,v i

,v i

]which contains v0,and so we can takeλi

,λi

to be the three

barycentric coordinates of v0with respect to T,and make the remaining coordinates zero. However,these coordinates depend randomly on the choice of triangle.An improvement is to take an average of such coordinates over certain covering triangles,as proposed in[2]. The resulting coordinates depend continuously on v0,v1,...,v k,yet still not smoothly.The

Figure1.Star-shaped polygon.

main purpose of this paper is to address this latter problem.We derive coordinates which depend(in?nitely)smoothly on the data points v0,v1,...,v k through a simple algebraic formula.

Several researchers have studied closely related problems[9,11,14,15].In the special case that the polygon v1,...,v k is convex,Wachspress[14]found a solution in which the coordinates can be expressed in terms of rational polynomials,

λi=

w i

j=1w j,w i=A(v i?1,v i,v i+1)

A(v i?1,v i,v0)A(v i,v i+1,v0)

cotγi?1+cotβi

||v i?v0||2

,(1.3)

where A(a,b,c)is the signed area of triangle[a,b,c]andγi?1andβi are the angles shown in Figure1.The latter formulation in terms of angles is due to Meyer,Lee,Barr,and Desbrun [9].Of course these coordinates depend smoothly on the data points v0,v1,...,v k and are therefore suitable when the polygon is convex.However,for star-shaped polygons the coordinateλi in(1.3)can be negative,and,in fact,will be so precisely whenγi?1+βi>π.

Another set of previously found weights can be expressed as

λi=

w i

j=1w j,w i=cotβi?1+cotγi.(1.4)

These weights arise from the standard piecewise linear?nite element approximation to the Laplace equation and appear in several books on numerical analysis,e.g.[7],and probably go back to the work of Courant.They have since been used in the computer graphics literature[10],[1].However,for our purposes these weights su?er from the same problem as the last ones,namely that they might be negative.The weightλi is negative if and only ifβi?1+γi>π.

Another possible set of coordinates might be Sibson’s natural neighbour coordinates [11],if we treated the points v1,...,v k as a set of scattered data points.However,despite various other good properties,Sibson’s coordinates,like those of[2],su?er from being de?ned piecewise,and have in general only C1dependence on the point v0.Moreover, several of Sibson’s coordinates might be zero,since the only non-zero ones would correspond to Voronoi neighbours of v0.

2.Mean Value Coordinates

We now describe a set of coordinates which satisfy all the properties we would like.Let αi ,0<αi <π,be the angle at v 0in the triangle [v 0,v i ,v i +1],de?ned cyclically;see Figure 1.Proposition 1.The weights

λi =w i j =1

w j ,w i =tan(αi ?1/2)+tan(αi /2)||v i ?v 0||,(2.1)

are coordinates for v 0with respect to v 1,...,v k .

As will be explained in Section 3,these weights can be derived from an application of the mean value theorem for harmonic functions,which suggests calling them mean value coordinates .They obviously depend smoothly on the points v 0,v 1,...,v k .

Proof:Since 0<αi <π,we see that tan(αi /2)is de?ned and positive,and therefore λi is well-de?ned and positive for i =1,...,k ,and by de?nition the λi sum to one.It remains to prove (1.1).From (2.1),equation (1.1)is equivalent to

k i =1w i (v i ?v 0)=0.(2.2)

We next use polar coordinates,centred at v 0,so that

v i =v 0+r i (cos θi ,sin θi ).

Then we have

v i ?v 0||v i ?v 0||

=(cos θi ,sin θi ),and αi =θi +1?θi ,and equation (2.2)becomes

k i =1(tan(αi ?1/2)+tan(αi /2))(cos θi ,sin θi )=0,

or equivalently

k i =1tan(αi /2)((cos θi ,sin θi )+(cos θi +1,sin θi +1))=0.(2.3)

To establish this latter identity,observe that

0= 2π

0(cos θ,sin θ)dθ

k i =1 θi +1θi (cos θ,sin θ)dθ=k i =1

θi +1

θi sin(θi +1?θ)sin αi (cos θi ,sin θi )+sin(θ?θi )sin αi

(cos θi +1,sin θi +1)dθ,(2.4)3

the last line following from the addition formula for sines.Since also

θi+1

θi

sin(θi+1?θ)dθ= θi+1θi sin(θ?θi)dθ=1?cosαi,(2.5)

and

tan(αi/2)=1?cosαi

sinαi

,(2.6)

equation(2.4)reduces to equation(2.3).

Not only are these coordinates positive,but we can bound them away from zero.This might be useful when considering the conditioning of the linear systems used in[2,5,6]. If L =max i||v i?v0||,L =min i||v i?v0||andα =max iαi,α =min iαi,then from (2.1)we have

2tan(α /2)

L ≤w i≤

2tan(α /2)

and

1 Ck ≤λi≤

,(2.7)

where

C=L tan(α /2)

L tan(α /2)

≥1.

The inequality(2.7)becomes an equality when C=1which occurs when v1,...,v k is a regular polygon and v0is its centre.

3.Motivation

The motivation behind the coordinates was an attempt to approximate harmonic maps by piecewise linear maps over triangulations,in such a way that injectivity is preserved. Recall that a C2function u de?ned over a planar region?is harmonic if it satis?es the Laplace equation

u xx+u yy=0.

Suppose we want to approximate the solution u with respect to Dirichlet boundary con-ditions,u|??=u0,by a piecewise linear function u T over some triangulation T of?. Thus u T will be an element of the spline space S01(T).The?nite element approach to this problem is to take u T to be the unique element of S01(T)which minimizes

?|?u T|2dx

subject to the boundary conditions.As is well known,this leads to a sparse linear system in the values of u T at the interior vertices of the triangulation T.To be precise,suppose

v0in Figure1is an interior vertex of the triangulation.As described in several books on numerical analysis,the equation associated with v0can be expressed as

u T(v0)=

i=1λi u T(v i),(3.1)

whereλi is given by equation(1.4).

Suppose now that we use this method component-wise to approximate a harmonic mapφ:?→l R2,that is a mapφ=(φ1,φ2)for which bothφ1andφ2are harmonic functions,by a piecewise linear mapφT:?→l R2.We would like the mapφT to be injective and a su?cient condition has been derived in[13]and[4]:ifφT is a convex combination map,i.e.at every interior vertex v0of T,we have

φT(v0)=

i=1λiφT(v i),(3.2)

for some positive weightsλ1,...,λk which sum to one,and ifφT maps the boundary?T homeomorphically to the boundary of a convex region,thenφT is one-to-one.

From this point of view,the standard?nite element approximationφT has a drawback: the theory of[13]and[4]cannot be applied.The mapφT will not in general be a convex combination map because the weightsλi in(1.4)can be negative which can lead to“foldover”in the map(an example is given in[3]).

This motivates,if possible,approximating a harmonic mapφby a convex combina-tion mapφT,i.e.,one with positive weights in(3.2).Consider the following alternative discretization of a harmonic function u.Recall that harmonic functions satisfy the mean value theorem.The mean value theorem comes in two forms.

Circumferential Mean Value Theorem.For a disc B=B(v0,r)??with bound-

aryΓ,

u(v0)=

2πr Γu(v)ds.

Solid Mean Value Theorem.

u(v0)=

πr2 B u(v)dx dy.

This suggests?nding the element u T of S01(T)which satis?es one of the two mean value theorems locally at every interior vertex v0of T.We will concentrate on the?rst version

and demand that

u T(v0)=

2πr Γu T(v)ds,(3.3)

for r su?ciently small that the disc B(v0,r)is entirely contained in the union of the triangles containing v0;see Figure2.It turns out that this equation can be expressed in the form of(3.1)where the weightsλi are those of(2.1),independent of the choice of r.

To see this,consider the triangle T i=[v0,v i,v i+1]in Figure2and letΓi be the part ofΓcontained in T i.

Figure2.Circle for the Mean Value Theorem. Lemma1.If f:T i→l R is any linear function then

i f(v)ds=rαi f(v0)+r2tan(αi/2) f(v i)?f(v0)

||v i?v0||

f(v i+1)?f(v0)

||v i+1?v0|| .(3.4)

Proof:We represent any point v∈Γi in polar coordinates with respect to v0,i.e.,

v=v0+r(cosθ,sinθ),

and we let

v j=v0+r j(cosθj,sinθj),j=i,i+1.

Then

Γi

f(v)ds=r θi+1θi f(v)dθ.(3.5) Since f is linear,and using barycentric coordinates,we have

f(v)=f(v0)+λ1(f(v i)?f(v0))+λ2(f(v i+1)?f(v0)),(3.6) whereλ1=A1/A andλ2=A2/A and A1and A2are the areas of the two triangles [v0,v,v i+1],[v0,v i,v]and A the area of the the whole triangle T https://www.wendangku.net/doc/731194636.html,ing trigonometry we have

A=1

r i r i+1sinαi,A1=

rr i+1sin(θi+1?θ),A2=

rr i sin(θ?θi),

and

λ1=r sin(θi+1?θ)

r i sinαi

,λ2=

r sin(θ?θi)

r i+1sinαi

.(3.7)

It follows that the substitution of the expression for f(v)in(3.6)into equation(3.5)and applying the identities(2.5–2.6)leads to equation(3.4).

It is now a simple matter to show that equation(3.3)reduces to the linear combination (3.1)with the coordinatesλi of(2.1).

Proposition2.Suppose the piecewise linear function u T:?→l R satis?es the local mean value theorem,i.e.,for each interior vertex v0,it satis?es equation(3.3)for some r>0suitably small.Then u T(v0)is given by the convex combination in(3.1)with the weightsλi of(2.1).

Proof:Equation(3.3)can be written as

u T(v0)=

2πr

i=1 Γi u T(v)ds,

which,after applying Lemma1to u T,reduces to

i=1tan(αi/2) u T(v i)?u T(v0)

||v i?v0||

u T(v i+1)?u T(v0)

||v i+1?v0|| ,

which is equivalent to equation(3.1)with the weights of(2.1).

We now notice that Proposition1follows from Proposition2due to the simple obser-vation that linear bivariate functions are trivially harmonic.

It is not di?cult to show that Proposition2remains true when the solid mean value theorem is used instead of the circumferential one,the main point being thatλ1andλ2in equation(3.7)are linear in r.

We remark?nally that it is well known that the standard?nite element approximation u T converges to u in various norms as the mesh size of the triangulation T tends to zero, under certain conditions on the angles of the triangles.Initial numerical tests suggest that the mean value‘approximation’does not converge to u in general.An interesting question for future research is whether it is in fact possible to approximate a harmonic map by a convex combination map over an arbitrary triangulation with su?ciently small mesh size.

4.Applications

In the parameterization method of[2],the triangulation is a spatial one,so that the vertices v0,...,v k are points in l R3.However,the mean value coordinates can be applied directly to the triangulation;we simply compute the coordinatesλi of equation(2.1) directly from the vertices v0,...,v k∈l R3.The numerical example of Figure3shows the result of parameterizing a triangle mesh(3a)and mapping a rectangular grid in the parameter plane back onto the mesh.The three parameterizations used are uniform(3b) (i.e.Tutte’s embedding),shape-preserving(3c),and mean value(3d).In this example the mean value parameterization looks at least as good as the‘shape-preserving’one of[2]. In addition,the mean value coordinates are faster to compute than the shape-preserving coordinates,and have the theoretical advantage that the resulting parameterization will depend smoothly on the vertices of the triangulation.

Mean value coordinates can also be used to morph pairs of compatible planar triangu-lations,adapting the method of[5].Such a morph will depend smoothly on the vertices of the two triangulations.Surazhsky and Gotsman found recently that mean value morphs are visually smoother than previous morphs;see[12]for details.

https://www.wendangku.net/doc/731194636.html,parisons from left to right:

(3a)Triangulation,(3b)Tutte,(3c)shape-preserving,(3d)mean value

5.Final remarks

When k=3the mean value coordinates,like Wachspress’s coordinates,are equal to the three barycentric coordinates,due to uniqueness.When k=4the mean value coordi-nates and Wachspress coordinates are di?erent in general.For example,when the points v1,v2,v3,v4form a rectangle,the Wachspress coordinates are bilinear,while the mean value coordinates are not.

If the points v1,...,v k form a convex polygon,the mean value coordinates are de?ned for all points v0inside the polygon,but due to the use of the anglesαi in formula(2.1), it is not obvious whether the coordinates can be extended to the polygon itself.Though this paper was not intended to deal with this issue,it would be important if these co-ordinates were to be used for generalizing Bezier surfaces,as in[8].For Wachspress’s coordinates(1.3),this is not a problem because by multiplying by the product of all areas A(v j,v j+1,v0),they have the well-known equivalent expression

λi=

w i

j=1w j,w i=A(v i?1,v i,v i+1) j=i?1,i A(v j,v j+1,v0).

It turns out that the mean value coordinates can also be continuously extended to the polygon itself.Moreover,like Wachspress’s coordinates,they are linear along each edge of the polygon and have the Lagrange property at the vertices:if v0=v i thenλi=1 andλj=0for j=i.A proof of this as well as other properties of these coordinates will appear in a forthcoming paper.

Acknowledgement.I wish to thank Mathieu Desbrun for supplying the data set for the numerical example and the referees for their comments.This work was partly supported by the European Union project MINGLE,contract num.HPRN-CT-1999-00117.

References

1.M.Eck,T.DeRose,T.Duchamp,H.Hoppe,M.Lounsbery,and W.Stuetzle,Multires-

olution analysis of arbitrary meshes,Computer Graphics Proceedings,SIGGRAPH95 (1995),173–182.

2.M.S.Floater,Parametrization and smooth approximation of surface triangulations,

Comp.Aided Geom.Design14(1997),231–250.

3.M.S.Floater,Parametric tilings and scattered data approximation,Intern.J.Shape

Modeling4(1998),165–182.

4.M.S.Floater,One-to-one piecewise linear mappings over triangulations,to appear in

https://www.wendangku.net/doc/731194636.html,p.

5.M.S.Floater and C.Gotsman,How to morph tilings injectively,https://www.wendangku.net/doc/731194636.html,p.Appl.

Math.101(1999),117–129.

6.C.Gotsman and V.Surazhsky,Guaranteed intersection-free polygon morphing,Com-

puters and Graphics25-1(2001),67–75.

7.A.Iserles,A?rst course in numerical analysis of di?erential equations,Cambridge

University Press,1996.

8.C.Loop and T.DeRose,A multisided generalization of B′e zier surfaces,ACM Trans.

Graph.8(1989),204–234.

9.M.Meyer,H.Lee,A.Barr,and M.Desbrun,Generalizing barycentric coordinates to

irregular n-gons,preprint,Caltech,2001.

10.U.Pinkall and K.Polthier,Computing Discrete Minimal Surfaces and Their Conju-

gates.Exp.Math.2(1993),15–36.

11.R.Sibson,A brief description of natural neighbour interpolation,in Interpreting Mul-

tivariate data,Vic Barnett(ed.),John Wiley,Chichester,1981,21–36.

12.V.Surazhsky and C.Gotsman,Intrinsic morphing of compatible triangulations,

preprint.

13.W.T.Tutte,How to draw a graph,Proc.London Math.Soc.13(1963),743–768.

14.E.Wachspress,A rational?nite element basis,Academic Press,1975.

15.J.Warren,Barycentric coordinates for convex polytopes,https://www.wendangku.net/doc/731194636.html,p.Math.6(1996),

97–108.

Michael S.Floater

SINTEF

Postbox124,Blindern

0314Oslo,NORWAY

mif@math.sintef.no