Wachspress and Mean Value Coordinates

Abstract

This paper gives a brief survey of two kinds of generalized barycentric coordinates, Wachspress and mean value coordinates, and their applications. Applications include surface parameterization in geometric modeling, curve and surface deformation in computer graphics, and their use as nodal shape functions for polygonal and polyhedral finite element methods.

1 Introduction

There is no unique way to generalize barycentric coordinates to polygons and polyhedra. However, two specific choices have turned out to be useful in several applications: Wachspress and mean value coordinates, and the purpose of this paper is to survey their main properties, applications, and generalizations.

For convex polygons, the coordinates of Wachspress and their generalizations due to Warren and others [15, 22, 30–33] are arguably the simplest since they are rational functions (quotients of bivariate polynomials), and it is relatively simple to evaluate them and their derivatives. Some simple bounds on their gradients have been found recently in [6], justifying their use as shape functions for polygonal finite elements.

For star-shaped polygons, and arbitrary polygons, Wachspress coordinates are not well-defined, and mean value coordinates are perhaps the most popular choice, due to their generality and surprising robustness over complex geometric shapes [1, 2, 4, 8, 13, 16], even though they are no longer positive if the polygon is not star-shaped. They have been employed in various tasks in geometric modeling, such as surface parameterization and plane and space deformation, as well as shading and animation in computer graphics.

While most of this paper surveys previous results, we add two new ones. The first is a new formula for the gradients of mean value coordinates, which could be used in finite element methods. The second is an alternative formula for the mean value coordinates themselves, which is valid on the boundary of the polygon. Though it may not be of practical value, it offers an alternative way of showing that these coordinates extend continuously to the polygon boundary.

2 Barycentric Coordinates on Polygons

Let $P \subset \mathbb {R}^2$ be a convex polygon, viewed as an open set, with vertices $\mathbf {v}_1,\mathbf {v}_2,\ldots ,\mathbf {v}_n$, $n \ge 3$, in some anticlockwise ordering. Figure 1 shows an example with $n=5$. We call any functions $\phi _i: P \rightarrow \mathbb {R}$, $i=1,\ldots ,n$, (generalized) barycentric coordinates if, for $\mathbf {x}\in P$, $\phi _i(\mathbf {x}) \ge 0$, $i=1,\ldots ,n$, and

Fig. 1

Vertex ordering for a polygon

$$\begin{aligned} \sum _{i=1}^n \phi _i(\mathbf {x}) = 1, \qquad \sum _{i=1}^n \phi _i(\mathbf {x}) \mathbf {v}_i = \mathbf {x}. \end{aligned}$$

(1)

For $n = 3$, the functions $\phi _1,\phi _2,\phi _3$ are uniquely determined and are the usual triangular barycentric coordinates w.r.t. the triangle with vertices $\mathbf {v}_1,\mathbf {v}_2,\mathbf {v}_3$. For $n \ge 4$, the choice of $\phi _1,\ldots ,\phi _n$ is no longer unique. However, they share some basic properties, derived in [7]:

• The functions $\phi _i$ have a unique continuous extension to $\partial P$, the boundary of $P$.

• Lagrange property: $\phi _i(\mathbf {v}_j) = \delta _{ij}$.

• Piecewise linearity on $\partial P$:

  $$\begin{aligned} \phi _i((1-\mu )\mathbf {v}_j + \mu \mathbf {v}_{j+1}) = (1-\mu )\phi _i(\mathbf {v}_j) + \mu \phi _i(\mathbf {v}_{j+1}), \qquad \mu \in [0,1]. \end{aligned}$$

  (2)

  (Here and throughout, vertices are indexed cyclically, i.e., $\mathbf {v}_{n+1} := \mathbf {v}_1$ etc.)

• Interpolation: if

  $$\begin{aligned} g(\mathbf {x}) = \sum _{i=1}^n \phi _i(\mathbf {x}) f(\mathbf {v}_i), \qquad \mathbf {x}\in P, \end{aligned}$$

  (3)

  then $g(\mathbf {v}_i) = f(\mathbf {v}_i)$. We call $g$ a barycentric interpolant to $f$.

• Linear precision: if $f$ is linear then $g = f$.

• $\ell _i \le \phi _i \le L_i$ where $L_i,\ell _i : P \rightarrow \mathbb {R}$ are the continuous, piecewise linear functions over the partitions of $P$ shown in Fig. 2 satisfying $L_i(\mathbf {v}_j) = \ell _i(\mathbf {v}_j) = \delta _{ij}$.

Fig. 2

Partitions for $L_i$ and $\ell _i$

3 Wachspress Coordinates

Wachspress coordinates were developed by Wachspress [30], and Warren [32]. They can be defined by the formula

$$\begin{aligned} \phi _i(\mathbf {x}) = \frac{\textit{w}_i(\mathbf {x})}{\sum _{j=1}^n \textit{w}_j(\mathbf {x})}, \end{aligned}$$

(4)

where

$$ \textit{w}_i(\mathbf {x}) = \frac{A(\mathbf {v}_{i-1},\mathbf {v}_i,\mathbf {v}_{i+1})}{A(\mathbf {x},\mathbf {v}_{i-1},\mathbf {v}_i) A(\mathbf {x},\mathbf {v}_i,\mathbf {v}_{i+1})}, $$

and $A(\mathbf {x}_1,\mathbf {x}_2,\mathbf {x}_3)$ denotes the signed area of the triangle with vertices $\mathbf {x}_1,\mathbf {x}_2,\mathbf {x}_3$,

$$ A(\mathbf {x}_1,\mathbf {x}_2,\mathbf {x}_3) := \frac{1}{2} \left| \begin{matrix} 1 &{} 1 &{} 1 \\ x_1 &{} x_2 &{} x_3 \\ y_1 &{} y_2 &{} y_3 \end{matrix}\right| {,} $$

where $\mathbf {x}_k = (x_k,y_k)$; see Fig. 3. The original proof that these coordinates are barycentric was based on the so-called adjoint of $P$; see Wachspress [30], and Warren [32]. The following proof is due to Meyer et al. [22]. Due to (4), it is sufficient to show that

Fig. 3

Triangles defining Wachspress coordinates

$$\begin{aligned} \sum _{i=1}^n \textit{w}_i(\mathbf {x}) (\mathbf {v}_i - \mathbf {x}) = 0. \end{aligned}$$

(5)

Fix $\mathbf {x}\in P$ and let

$$ A_i = A_i(\mathbf {x}) = A(\mathbf {x},\mathbf {v}_i,\mathbf {v}_{i+1}) \qquad \hbox {and} \qquad B_i = A(\mathbf {v}_{i-1},\mathbf {v}_i,\mathbf {v}_{i+1}). $$

Then we can express $\mathbf {x}$ as a barycentric combination of $\mathbf {v}_{i-1},\mathbf {v}_i,\mathbf {v}_{i+1}$:

$$ \mathbf {x}= \frac{A_i}{B_i} \mathbf {v}_{i-1} + \frac{(B_i-A_{i-1}-A_i)}{B_i} \mathbf {v}_i + \frac{A_{i-1}}{B_i} \mathbf {v}_{i+1}, $$

regardless of whether $\mathbf {x}$ lies inside or outside the triangle formed by $\mathbf {v}_{i-1},\mathbf {v}_i,\mathbf {v}_{i+1}$. This equation can be rearranged in the form

$$ \frac{B_i}{A_{i-1}A_i} (\mathbf {v}_i - \mathbf {x}) = \frac{1}{A_{i-1}} (\mathbf {v}_i - \mathbf {v}_{i-1}) -\frac{1}{A_i} (\mathbf {v}_{i+1} - \mathbf {v}_i). $$

Summing both sides of this over $i$, and observing that the right hand side then cancels to zero, gives

$$ \sum _{i=1}^n \frac{B_i}{A_{i-1}A_i} (\mathbf {v}_i - \mathbf {x}) = 0, $$

which proves (5).

3.1 Rational Functions

Another way of expressing these coordinates is in the form

$$\begin{aligned} \phi _i(\mathbf {x}) = \frac{\hat{\textit{w}}_i(\mathbf {x})}{\sum _{j=1}^n \hat{\textit{w}}_j(\mathbf {x})}, \qquad \hat{\textit{w}}_i(\mathbf {x}) = B_i \prod _{j \ne i-1,i} A_j(\mathbf {x}), \end{aligned}$$

(6)

and since each area $A_j(\mathbf {x})$ is linear in $\mathbf {x}$, we see from this that $\phi _i$ is a rational (bivariate) function, with total degree $\le n-2$ in the numerator and denominator. In fact, the denominator, $W = \sum _{j=1}^n \hat{\textit{w}}_j$, has total degree $\le n-3$ due to linear precision: since (5) holds with $w_i$ replaced by $\hat{\textit{w}}_i$, it implies that

$$ \sum _{i=1}^n \hat{\textit{w}}_i(\mathbf {x}) \mathbf {v}_i = W(\mathbf {x}) \mathbf {x}. $$

The left hand side is a (vector-valued) polynomial of degree $\le n-2$ in $\mathbf {x}$ and since $\mathbf {x}$ has degree 1, the degree of $W$ must be at most $n-3$.

The degrees, $n-2$ and $n-3$, of the numerator and denominator of $\phi _i$ agree with the triangular case where $n=3$ and the coordinates are linear functions.

We note that the ‘global’ form of $\phi _i(\mathbf {x})$ in (6) is also valid for $\mathbf {x}\in \partial P$, unlike the ‘local’ form (4), though it requires more computation for large $n$.

3.2 Perpendicular Distances to Edges

An alternative way of expressing Wachspress coordinates is in terms of the perpendicular distances of $\mathbf {x}$ to the edges of $P$. This is the form used by Warren et al. [33], and it generalizes in a natural way to higher dimension.

For each $i$, let $\mathbf {n}_i \in \mathbb {R}^2$ be the outward unit normal to the edge $e_i = [\mathbf {v}_i,\mathbf {v}_{i+1}]$, and for any $\mathbf {x}\in P$ let $h_i(\mathbf {x})$ be the perpendicular distance of $\mathbf {x}$ to the edge $e_i$, so that

$$ h_i(\mathbf {x}) = (\mathbf {v}_i - \mathbf {x}) \cdot \mathbf {n}_i = (\mathbf {v}_{i+1} - \mathbf {x}) \cdot \mathbf {n}_i, $$

see Fig. 4. Then the coordinates in (4) can be expressed as

$$\begin{aligned} \phi _i(\mathbf {x}) = \frac{\tilde{\textit{w}}_i(\mathbf {x})}{\sum _{j=1}^n \tilde{\textit{w}}_j(\mathbf {x})}, \end{aligned}$$

(7)

where

$$\begin{aligned} \tilde{\textit{w}}_i(\mathbf {x}) := \frac{\mathbf {n}_{i-1} \times \mathbf {n}_i}{h_{i-1}(\mathbf {x}) h_i(\mathbf {x})}, \end{aligned}$$

(8)

and

$$ \mathbf {x}_1 \times \mathbf {x}_2 := \left| \begin{matrix} x_1 &{} x_2 \\ y_1 &{} y_2 \end{matrix}\right| . $$

for $\mathbf {x}_k = (x_k,y_k)$. To see this, observe that with $L_j = |\mathbf {v}_{j+1}-\mathbf {v}_j|$ (and $|\cdot |$ the Euclidean norm) and $\beta _i$ the interior angle of the polygon at $\mathbf {v}_i$,

$$ A(\mathbf {v}_{i-1},\mathbf {v}_i,\mathbf {v}_{i+1}) = \frac{1}{2} \sin \beta _i L_{i-1} L_i, $$

and

$$ A(\mathbf {x},\mathbf {v}_{i-1},\mathbf {v}_i) = \frac{1}{2} h_{i-1}(\mathbf {x}) L_{i-1}, \qquad A(\mathbf {x},\mathbf {v}_i,\mathbf {v}_{i+1}) = \frac{1}{2} h_i(\mathbf {x}) L_i, $$

so that

$$ {\textit{w}}_i(\mathbf {x}) = 2 \tilde{\textit{w}}_i(\mathbf {x}). $$

Fig. 4

Perpendicular distances

3.3 Gradients

The gradient of a Wachspress coordinate can be found quite easily from the perpendicular form (7 and 8). Since $\nabla h_i(\mathbf {x}) = -\mathbf {n}_i$, the gradient of $\tilde{\textit{w}}_i$ is [6]

$$\begin{aligned} \nabla \tilde{\textit{w}}_i(\mathbf {x}) = \tilde{\textit{w}}_i(\mathbf {x}) \left( \frac{\mathbf {n}_{i-1}}{h_{i-1}(\mathbf {x})} + \frac{\mathbf {n}_i}{h_i(\mathbf {x})} \right) . \end{aligned}$$

(9)

Thus the (vector-valued) ratio $\mathbf {R}_i := \nabla \tilde{\textit{w}}_i / \tilde{\textit{w}}_i$ is simply

$$ \mathbf {R}_i(\mathbf {x}) = \frac{\mathbf {n}_{i-1}}{h_{i-1}(\mathbf {x})} + \frac{\mathbf {n}_i}{h_i(\mathbf {x})}. $$

Using the formula [6]

$$\begin{aligned} \nabla \phi _i = \phi _i(\mathbf {R}_i - \sum _{j=1}^n \phi _j \mathbf {R}_j) \end{aligned}$$

(10)

for any function $\phi _i$ of the form (7), we thus obtain $\nabla \phi _i(\mathbf {x})$ for $\mathbf {x}\in P$.

3.4 Curve Deformation

While Wachspress’s motivation for these coordinates was finite element methods over polygonal partitions, Warren suggested their use in deforming curves. The coordinates can be used to define a barycentric mapping of one polygon to another, and such a mapping will then map, or deform, a curve embedded in the first polygon into a new one, with the vertices of the polygon acting as control points, with an effect similar to those of Bézier and spline curves and surfaces.

Assuming the second polygon is $P'$ with vertices $\mathbf {v}_1',\ldots ,\mathbf {v}_n'$, the barycentric mapping $\mathbf {g}:P \rightarrow P'$ is defined as follows. Given $\mathbf {x}\in P$,

• 1. express $\mathbf {x}$ in Wachspress coordinates, $\mathbf {x}= \sum _{i=1}^n \phi _i(\mathbf {x}) \mathbf {v}_i$,

• 2. set $\mathbf {g}(\mathbf {x}) = \sum _{i=1}^n \phi _i(\mathbf {x}) \mathbf {v}_i'$.

Figure 5 shows such a mapping. Figure 6 shows the effect of using the mapping to deform a curve (a circle in this case).

Fig. 5

Barycentric mapping

Fig. 6

Curve deformation

It is now known that Wachspress mappings between convex polygons are always injective; as shown in [9]. The basic idea of the proof is to show that $\mathbf {g}$ has a positive Jacobian determinant $J(\mathbf {g})$. To do this one first shows that $J(\mathbf {g})$ can be expressed as

$$ J(\mathbf {g}) = 2 \sum _{1 \le i < j < k \le n} \left| \begin{matrix} \phi _i &{} \phi _j &{} \phi _k \\ \partial _1\phi _i &{} \partial _1\phi _j &{} \partial _1\phi _k \\ \partial _2\phi _i &{} \partial _2\phi _j &{} \partial _2\phi _k \end{matrix} \right| A(\mathbf {v}_i',\mathbf {v}_j',\mathbf {v}_k'). $$

By the convexity of $P'$, the signed areas $A(\mathbf {v}_i',\mathbf {v}_j',\mathbf {v}_k')$ in the sum are all positive, and so $J(\mathbf {g}) > 0$ if all the $3 \times 3$ determinants in the sum are positive, and this turns out to be the case for Wachspress coordinates $\phi _i$.

4 Mean Value Coordinates

As we have seen, Wachspress coordinates are relatively simple functions, and lead to well-behaved barycentric mappings. They are, however, limited to convex polygons. For a nonconvex polygon they are not well-defined, since the denominator in the rational expression becomes zero at certain points in the polygon. An alternative set of coordinates for convex polygons is the mean value coordinates [4], which have a simple generalization to nonconvex polygons, though positivity is in general lost. Suppose initially that $P$ is convex as before, then the mean value (MV) coordinates are defined by (4) and

$$\begin{aligned} {\textit{w}}_i(\mathbf {x}) = \frac{\tan (\alpha _{i-1}/2) + \tan (\alpha _{i}/2)}{| \mathbf {v}_i - \mathbf {x}|}, \end{aligned}$$

(11)

with the angles $\alpha _j = \alpha _j(\mathbf {x})$, with $0 < \alpha _j < \pi$, as shown in Fig. 7. To show that these coordinates are barycentric, it is sufficient, as in the Wachspress case, to show that the $\textit{w}_i$ in (11) satisfy (5). This can be done in four steps:

Fig. 7

Notation for mean value coordinates

• 1. Express the unit vectors $\mathbf {e}_i := (\mathbf {v}_i - \mathbf {x})/|\mathbf {v}_i-\mathbf {x}|$ in polar coordinates:

  $$ \mathbf {e}_i = (\cos \theta _i,\sin \theta _i), $$

  and note that $\alpha _i = \theta _{i+1}-\theta _i$.

• 2. Use the fact that the integral of the unit normals $\mathbf {n}(\theta ) = (\cos \theta ,\sin \theta )$ on a circle is zero:

  $$ \int \limits _0^{2\pi } \mathbf {n}(\theta ) \, d\theta = 0. $$

• 3. Split this integral according to the $\theta _i$:

  $$\begin{aligned} \int \limits _0^{2\pi } \mathbf {n}(\theta ) \, d\theta = \sum _{i=1}^n \int \limits _{\theta _i}^{\theta _{i+1}} \mathbf {n}(\theta ) \,d\theta . \end{aligned}$$

  (12)

• 4. Show by trigonometry that

  $$ \int \limits _{\theta _i}^{\theta _{i+1}} \mathbf {n}(\theta ) \,d\theta = \frac{1-\cos \alpha _i}{\sin \alpha _i} (\mathbf {e}_i + \mathbf {e}_{i+1}) = \tan (\alpha _i/2) (\mathbf {e}_i + \mathbf {e}_{i+1}). $$

Substituting this into the sum in (12) and rearranging gives (5).

We can compute $\tan (\alpha _i/2)$ from the formulas

$$\begin{aligned} \cos \alpha _i = \mathbf {e}_i \cdot \mathbf {e}_{i+1}, \qquad \sin \alpha _i = \mathbf {e}_i \times \mathbf {e}_{i+1}. \end{aligned}$$

(13)

Figure 8 compares the contour lines of a Wachspress coordinate, on the left, with the corresponding MV coordinate, on the right.

Fig. 8

Wachspress (left). Mean value (right)

4.1 Gradients

Similar to the Wachspress case, the gradient $\nabla \phi _i$ of the MV coordinate $\phi _i$ can be computed from the formula (10) if we can find the ratio $\mathbf {R}_i := \nabla \textit{w}_i / \textit{w}_i$, with $\textit{w}_i$ in (11). Let $r_i = |\mathbf {v}_i - \mathbf {x}|$ and $t_i = \tan (\alpha _i/2)$ so that

$$ \textit{w}_i = \frac{t_{i-1} + t_i}{r_i}. $$

Further, define

$$ \mathbf {c}_i = \frac{\mathbf {e}_i}{r_i} - \frac{\mathbf {e}_{i+1}}{r_{i+1}}, $$

and for a vector $\mathbf {a}= (a_1,a_2) \in \mathbb {R}^2$, let $\mathbf {a}^\perp := (-a_2,a_1)$.

Theorem 1

For the MV coordinates,

$$ \mathbf {R}_i = \left( \frac{t_{i-1}}{t_{i-1}+t_i}\right) \frac{\mathbf {c}_{i-1}^\perp }{\sin \alpha _{i-1}} + \left( \frac{t_i}{t_{i-1}+t_i} \right) \frac{\mathbf {c}_i^\perp }{\sin \alpha _i} + \frac{\mathbf {e}_i}{r_i}. $$

We will show this using two lemmas.

Lemma 1

For $\mathbf {u}\in \mathbb {R}^2$, let $\mathbf {e}= (e_1,e_2) = (\mathbf {u}-\mathbf {x})/|\mathbf {u}-\mathbf {x}|$ and $r = |\mathbf {u}-\mathbf {x}|$. Then

$$ \nabla e_1 = \frac{e_2 \mathbf {e}^\perp }{r}, \qquad \nabla e_2 = -\frac{e_1 \mathbf {e}^\perp }{r}. $$

Proof

If $\mathbf {d}= (d_1,d_2) = \mathbf {u}- \mathbf {x}$, then using the fact that

$$ \nabla d_1 = (-1,0), \quad \nabla d_2 = (0,-1), \quad \hbox {and} \quad \nabla r = -\mathbf {d}/r, $$

the result follows from the quotient rule:

$$ \nabla e_k = \nabla \left( \frac{d_k}{r}\right) = \frac{r \nabla d_k - d_k \nabla r}{r^2}, \qquad k=1,2. ~~ {\square } $$

Lemma 2

Suppose $\mathbf {u}, \mathbf {v}\in \mathbb {R}^2$, and let

$$\begin{aligned} \mathbf {e}&= (\mathbf {u}-\mathbf {x})/|\mathbf {u}-\mathbf {x}|, \qquad r = |\mathbf {u}-\mathbf {x}|, \\ \mathbf {f}&= (\mathbf {v}-\mathbf {x})/|\mathbf {v}-\mathbf {x}|, \qquad s = |\mathbf {v}-\mathbf {x}|. \end{aligned}$$

Then

$$ \nabla (\mathbf {e}\cdot \mathbf {f}) = - (\mathbf {e}\times \mathbf {f}) \mathbf {c}^\perp \qquad \hbox {and} \qquad \nabla (\mathbf {e}\times \mathbf {f}) = (\mathbf {e}\cdot \mathbf {f}) \mathbf {c}^\perp , $$

where

$$ \mathbf {c}= \frac{\mathbf {e}}{r} - \frac{\mathbf {f}}{s}. $$

Proof

With $\mathbf {e}= (e_1,e_2)$ and $\mathbf {f}= (f_1,f_2)$,

$$\begin{aligned} \nabla (\mathbf {e}\cdot \mathbf {f})&= f_1 \nabla e_1 + e_1 \nabla f_1 + f_2 \nabla e_2 + e_2 \nabla f_2, \\\nabla (\mathbf {e}\times \mathbf {f})&= f_2 \nabla e_1 + e_1 \nabla f_2 - f_1 \nabla e_2 - e_2 \nabla f_1, \end{aligned}$$

and applying Lemma 1 to $\nabla e_k$ and $\nabla f_k$, $k=1,2$, gives the result. $\square$

We now prove Theorem 1. Recalling (13), Lemma 2 shows that

$$\begin{aligned} \nabla (\cos \alpha _i) = - (\sin \alpha _i) \mathbf {c}_i^\perp , \qquad \nabla (\sin \alpha _i) = (\cos \alpha _i) \mathbf {c}_i^\perp . \end{aligned}$$

(14)

From this it follows that

$$ \nabla t_i = \frac{t_i}{\sin \alpha _i} \mathbf {c}_i^\perp . $$

Since, $\nabla r_i = -\mathbf {e}_i$, this means that

$$ \nabla \left( \frac{t_j}{r_i}\right) = \frac{t_j}{r_i} \left( \frac{\mathbf {c}_j^\perp }{\sin \alpha _i} + \frac{\mathbf {e}_i}{r_i} \right) , \qquad j=i-1,i. $$

Therefore,

$$ \nabla \textit{w}_i = \frac{t_{i-1}}{r_i} \left( \frac{\mathbf {c}_{i-1}^\perp }{\sin \alpha _{i-1}} \right) + \frac{t_i}{r_i} \left( \frac{\mathbf {c}_i^\perp }{\sin \alpha _i} \right) + \textit{w}_i \frac{\mathbf {e}_i}{r_i}, $$

which, after dividing by $\textit{w}_i$, proves Theorem 1.

Incidentally, though we did not use it, we note that both equations in (14) imply that

$$ \nabla \alpha _i = \mathbf {c}_i^\perp . $$

Another derivative formula for MV coordinates can be found in [28].

4.2 Alternative Formula

We saw that Wachspress coordinates can be expressed in the “global form” (6) in which $\phi _i(\mathbf {x})$ is well-defined for $\mathbf {x}\in \partial P$ as well as for $\mathbf {x}\in P$. It turns out that MV coordinates also have a global form with the same property, though for large $n$, the resulting expression requires more computation, and involves more square roots, than the local form based on (11). Let $\mathbf {d}_i = \mathbf {v}_i - \mathbf {x}$, $i=1,\ldots ,n$.

Theorem 2

The MV coordinates in (4) can be expressed as

$$\begin{aligned} \phi _i(\mathbf {x}) = \frac{\hat{\textit{w}}_i(\mathbf {x})}{\sum _{j=1}^n \hat{\textit{w}}_j(\mathbf {x})}, \end{aligned}$$

(15)

where

$$\begin{aligned} \hat{\textit{w}}_i = (r_{i-1} r_{i+1} - \mathbf {d}_{i-1} \cdot \mathbf {d}_{i+1})^{1/2} \prod _{j \ne i-1,i} (r_j r_{j+1} + \mathbf {d}_j \cdot \mathbf {d}_{j+1})^{1/2}. \end{aligned}$$

(16)

Proof

From the addition formula for sines, we have

$$ {\textit{w}}_i = \frac{1}{r_i} \left( \frac{\sin (\alpha _{i-1}/2)}{\cos (\alpha _{i-1}/2)} + \frac{\sin (\alpha _i/2)}{\cos (\alpha _i/2)} \right) = \frac{\sin ((\alpha _{i-1} + \alpha _i)/2)}{r_i \cos (\alpha _{i-1}/2)\cos (\alpha _i/2)}. $$

Then, to get rid of the half-angles we use the identities

$$\begin{aligned} \sin (A/2)&= \sqrt{(1 - \cos A)/2}, \\\cos (A/2)&= \sqrt{(1 + \cos A)/2}, \end{aligned}$$

to obtain

$$ {\textit{w}}_i = \frac{1}{r_i} \left( \frac{2(1 - \cos (\alpha _{i-1}+\alpha _i))}{ (1 + \cos \alpha _{i-1}) (1 + \cos \alpha _{i})} \right) ^{1/2}. $$

Now we substitute in the scalar product formula,

$$ \cos (\alpha _{i-1} + \alpha _i) = \frac{\mathbf {d}_{i-1} \cdot \mathbf {d}_{i+1}}{r_{i-1} r_{i+1}}, $$

and similarly for $\cos \alpha _{i-1}$ and $\cos \alpha _i$, and the $1/r_i$ term cancels out:

$$ {\textit{w}}_i = \left( \frac{2(r_{i-1} r_{i+1} - \mathbf {d}_{i-1} \cdot \mathbf {d}_{i+1})}{(r_{i-1} r_{i} + \mathbf {d}_{i-1} \cdot \mathbf {d}_{i}) (r_i r_{i+1} + \mathbf {d}_i \cdot \mathbf {d}_{i+1})} \right) ^{1/2}, $$

which gives 15 and 16. $\square$

One can easily check that this formula gives the correct values (2) for $\mathbf {x}\in \partial P$.

4.3 Star-Shaped Polygons

The original motivation for these coordinates was for parameterizing triangular meshes [3, 5, 29]. In this application, the point $\mathbf {x}$ is a vertex in a planar triangulation, with $\mathbf {v}_1,\ldots ,\mathbf {v}_n$ its neighbouring vertices. Thus, in this case, the polygon $P$ (with vertices $\mathbf {v}_1,\ldots ,\mathbf {v}_n$) is not necessarily convex, but always star-shaped, with $\mathbf {x}$ a point in its kernel, i.e., every vertex $\mathbf {v}_i$ is “visible” from $\mathbf {x}$; see Fig. 9. In this case the angles $\alpha _i$ in (11) are again positive, and the weight ${\textit{w}}_i(\mathbf {x})$ is again positive. Thus the MV coordinates of $\mathbf {x}$ remain positive in this star-shaped case. The advantage of this is that when these coordinates are applied to the parameterization of triangular meshes, the piecewise linear mapping is guaranteed to be injective, i.e., none of the triangles “fold over,” when the boundary of the mesh is mapped to a convex polygon.

4.4 Arbitrary Polygons

It was later observed, in [13], that the coordinates are still well-defined, though not necessarily positive, when $P$ is an arbitrary polygon, provided that the angles $\alpha _i$ are treated as signed angles: i.e., we take $\alpha _i$ in (11) to have the same sign as $\mathbf {e}_i \times \mathbf {e}_{i+1}$, which will be the case if we use the formulas (13). The reason for this is that even though ${\textit{w}}_i(\mathbf {x})$ in (11) may be negative for some $i$, when $P$ is arbitrary, the sum $\sum _{i=1}^n {\textit{w}}_i(\mathbf {x})$ is nevertheless positive for any $\mathbf {x}$ in $P$. This was shown in [13], where it was also shown that these more general MV coordinates have the Lagrange and piecewise linearity properties on $\partial P$.

Fig. 9

A star-shaped polygon and its kernel

This generalization of MV coordinates allows the curve deformation method to be extended to arbitrary polygons. It was further observed in [13] that MV coordinates even have a natural generalization to any set of polygons, as long as the polygons do not intersect one another. The polygons may or may not be nested. These generalized MV coordinates were applied to image warping in [13].

5 Polygonal Finite Elements

There has been steadily growing interest in using generalized barycentric coordinates for finite element methods on polygonal (and polyhedral) meshes [6, 11, 23, 26, 27, 34]. In order to establish the convergence of the finite element method, one would need to derive a bound on the gradients of the coordinates in terms of the geometry of the polygon $P$. Various bounds on

$$ \sup _{\mathbf {x}\in P} |\nabla \phi _i(\mathbf {x})| $$

were derived in [11] for Wachspress (and other) coordinates, and in [23] for MV coordinates. For the Wachspress coordinates, a simpler bound was derived in [6]. If we define, for $\mathbf {x}\in P$,

$$\begin{aligned} \lambda (\mathbf {x}) := \sum _{i=1}^n |\nabla \phi _i(\mathbf {x})|, \end{aligned}$$

(17)

then $\lambda$ plays a role similar to the Lebesgue function in the theory of polynomial interpolation because for $g$ in (3),

$$ |\nabla g(\mathbf {x})| \le \sum _{i=1}^n |\nabla \phi _i(\mathbf {x})| |f(\mathbf {v}_i)| \le \lambda (\mathbf {x}) \max _{i=1,\ldots ,n} |f(\mathbf {v}_i )|. $$

It was shown in [6] that with

$$\begin{aligned} \varLambda := \sup _{\mathbf {x}\in P} \lambda (\mathbf {x}) \end{aligned}$$

(18)

the corresponding ‘Lebesgue constant’, and with $\phi _i$ the Wachspress coordinates,

$$ \varLambda \le \frac{4}{h_*}, $$

where

$$ h_*= \min _{i=1,\ldots ,n} \min _{j \ne i,i+1} h_i(\mathbf {v}_j). $$

6 Curved Domains

Consider again the barycentric interpolant $g$ in (3). Since $g$ is piecewise linear on the boundary $\partial P$, it interpolates $f$ on $\partial P$ if $f$ itself is piecewise linear on $\partial P$. Warren et al. [33] proposed a method of interpolating any continuous function $f$ defined on the boundary of any convex domain, by, roughly speaking, taking a continuous “limit” of the polygonal interpolants $g$ in (3). Specifically, suppose that the boundary of some convex domain $P \subset \mathbb {R}^2$ is represented as a closed, parametric curve $\mathbf {c}:[a,b] \rightarrow \mathbb {R}^2$, with $\mathbf {c}(b) = \mathbf {c}(a)$. Then any sequence of parameter values, $t_1,\ldots ,t_n$, with $a \le t_1 < t_2 < \cdots < t_n < b$, with mesh size $h = \max _i (t_{i+1}-t_i)$, defines a convex polygon $P_h$ with vertices $\mathbf {v}_i = \mathbf {c}(t_i)$; see Fig. 10. The barycentric interpolant $g$ in (3) with respect to this polygon is then

$$\begin{aligned} g_h(\mathbf {x}) = \sum _{i=1}^n \phi _i(\mathbf {x}) f(\mathbf {c}(t_i)). \end{aligned}$$

(19)

Taking the limit $g = \lim _{h \rightarrow 0} g_h$ over a sequence of such polygons, and letting the $\phi _i$ be the Wachspress coordinates, gives

$$\begin{aligned} g(\mathbf {x}) = \int \limits _a^b {\textit{w}}(\mathbf {x},t) f(\mathbf {c}(t)) \,dt \Bigg / \int \limits _a^b {\textit{w}}(\mathbf {x},t) \,dt, \qquad \mathbf {x}\in P, \end{aligned}$$

(20)

where

$$ {\textit{w}}(\mathbf {x},t) = \frac{(\mathbf {c}'(t) \times \mathbf {c}''(t))}{((\mathbf {c}(t) - \mathbf {x}) \times \mathbf {c}'(t))^2}. $$

It was shown in [33] that the barycentric property also holds for this $g$: if $f:\mathbb {R}^2 \rightarrow \mathbb {R}$ is linear, i.e., $f(\mathbf {x}) = ax + by + c$, then $g = f$. However, it also follows from the fact that if $f$ is linear, $g_h = f$ for all $h$.

Fig. 10

From polygons to curved domains

There is an analogous continuous MV interpolant, with $g$ also given by (20), but with the weight function ${\textit{w}}(\mathbf {x},t)$ replaced by

$$\begin{aligned} {\textit{w}}(\mathbf {x},t) = \frac{(\mathbf {c}(t) - \mathbf {x}) \times \mathbf {c}'(t)}{|\mathbf {c}(t) - \mathbf {x}|^3}. \end{aligned}$$

(21)

One can also derive the barycentric property of this continuous interpolant by applying the unit circle construction of Sect. 4 directly to the curved domain $P$. Figure 11 shows the MV interpolant to the function $\cos (2\theta )$, $0 \le \theta < 2\pi$, on the boundary of the unit circle.

Fig. 11

An MV interpolant on a circle

Similar to the generalization of MV coordinates to nonconvex polygons, the continuous MV interpolant also extends to arbitrarily shaped curve domains: one simply applies the same formula (21). Even though the cross product,

$$ (\mathbf {c}(t) - \mathbf {x}) \times \mathbf {c}'(t) $$

may be negative for some values of $t$, the integral $\int _a^b {\textit{w}}(\mathbf {x},t) \, dt$ of $w$ in (21) remains positive [2].

6.1 Hermite Interpolation

If the normal derivative of $f$ is also known on the boundary of the domain, we could consider matching both the values and normal derivatives of $f$. In [2, 10] two distinct approaches were used to construct such a Hermite interpolant, both based on the construction of MV interpolants. To motivate this, let $\pi _n$ denote the linear space of polynomials of degree $\le n$ in one real variable. Suppose that $f:[0,1] \rightarrow \mathbb {R}$ has a first derivative at $x=0$ and $x=1$. Then there is a unique cubic polynomial, $p \in \pi _3$, such that

$$ p^{(k)}(i) = f^{(k)}(i), \qquad i=0,1, \quad k=0,1. $$

There are various ways of expressing $p$. One is as

$$ p = l_0(x) + \omega (x) l_1(x), $$

where

$$ l_0(x) = (1-x)f(0) + x f(1), \quad \omega (x) = x(1-x), \quad l_1(x) = (1-x)m_0 + x m_1, $$

and

$$ m_0 = f'(0) - (f(1) - f(0)), \qquad m_1 = (f(1)-f(0)) - f'(1). $$

The basic idea of the Hermite interpolant in [2] is to generalize this construction to a general planar domain, replacing the linear interpolants $l_0$ and $l_1$ by MV interpolants, and replacing the weight function $\omega$ by an MV “weight” function. This gives a Hermite interpolant in 2D, but it does not in general have cubic precision. Another way of expressing $p$ above is as the minimizer of a functional. For a fixed $x \in (0,1)$, $p(x)$ is the value $s(x)$ of the spline $s$ that minimizes the functional

$$ E(s) = \int \limits _0^1 (s''(y))^2 \, dy, $$

in the spline space

$$ S = \{s \in C^1[0,1]: s|_{[0,x]}, s|_{[x,1]} \in \pi _3 \}, $$

subject to the boundary conditions

$$ s^{(k)}(i) = f^{(k)}(i), \qquad i=0,1, \quad k=0,1. $$

A generalization of this minimization was used in [10] to generate a function on a curved domain that appears, numerically, to interpolate the boundary data, but a mathematical proof of this is still missing. The cubic construction in [10] was recently derived independently through certain mean value properties of biharmonic functions by Li et al. [19]. They also give a closed-form expression for the coordinates on a polygonal domain when a suitable definition of the boundary data is used along the edges.

7 Coordinates in Higher Dimensions

So far we have only considered coordinates for points in $\mathbb {R}^2$, but there are applications of barycentric coordinates for points in a polyhedron in $\mathbb {R}^3$, such as in Fig. 12, or more generally for points in a polytope in $\mathbb {R}^d$. Both Wachspress and MV coordinates have been generalized to higher dimensions.

Fig. 12

Simple, convex polyhedron

7.1 Wachspress Coordinates in 3D

Warren [32] generalized the coordinates of Wachspress to simple convex polyhedra: convex polyhedra in which all vertices have three incident faces. In [33], Warren et al. derived the same coordinates in a different way (avoiding the so-called “adjoint”), generalizing (7) as follows. Let $P \subset \mathbb {R}^3$ be a simple convex polyhedron, with faces $F$ and vertices $V$. For each face $f \in F$, let $\mathbf {n}_f \in \mathbb {R}^3$ denote its unit outward normal, and for any $\mathbf {x}\in P$, let $h_f(\mathbf {x})$ denote the perpendicular distance of $\mathbf {x}$ to $f$, which can be expressed as the scalar product

$$ h_f(\mathbf {x}) = (\mathbf {v}- \mathbf {x}) \cdot \mathbf {n}_f, $$

for any vertex $\mathbf {v}\in V$ belonging to $f$. For each vertex $\mathbf {v}\in V$, let $f_1,f_2,f_3$ be the three faces incident to $\mathbf {v}$, and for $\mathbf {x}\in P$, let

$$\begin{aligned} \textit{w}_\mathbf {v}(\mathbf {x}) = \frac{\det (\mathbf {n}_{f_1},\mathbf {n}_{f_2},\mathbf {n}_{f_3})}{h_{f_1}(\mathbf {x}) h_{f_2}(\mathbf {x}) h_{f_3}(\mathbf {x})}, \end{aligned}$$

(22)

where it is understood that $f_1,f_2,f_3$ are ordered such that the determinant in the numerator is positive. Here, for vectors $\mathbf {a},\mathbf {b},\mathbf {c}\in \mathbb {R}^3$,

$$ \det (\mathbf {a},\mathbf {b},\mathbf {c}) := \left| \begin{matrix} a_1 &{} b_1 &{} c_1 \\ a_2 &{} b_2 &{} c_2 \\ a_3 &{} b_3 &{} c_3 \end{matrix} \right| . $$

Thus the ordering of $f_1,f_2,f_3$ must be anticlockwise around $\mathbf {v}$, seen from outside $P$. In this way, ${\textit{w}}_\mathbf {v}(\mathbf {x}) > 0$, and it was shown in [33] that the functions

$$\begin{aligned} \phi _\mathbf {v}(\mathbf {x}):= \frac{{\textit{w}}_\mathbf {v}(\mathbf {x})}{\sum _{\mathbf {u}\in V} {\textit{w}}_\mathbf {u}(\mathbf {x})} \end{aligned}$$

(23)

are barycentric coordinates for $\mathbf {x}\in P$ in the sense that

$$\begin{aligned} \sum _{\mathbf {v}\in V} \phi _\mathbf {v}(\mathbf {x}) = 1, \qquad \sum _{\mathbf {v}\in V} \phi _\mathbf {v}(\mathbf {x}) \mathbf {v}= \mathbf {x}. \end{aligned}$$

(24)

To deal with nonsimple polyhedra, it was suggested in [33] that one might decompose a nonsimple vertex into simple ones by perturbing its adjacent facets. Later, Ju et al. [15] found a cleaner solution, using properties of the so-called polar dual. With respect to each $\mathbf {x}$ in a general convex polyhedron $P \subset \mathbb {R}^3$, there is a dual polyhedron,

$$ \tilde{P}_\mathbf {x}:= \{\mathbf {y}\in \mathbb {R}^3: \mathbf {y}\cdot (\mathbf {z}-\mathbf {x}) \le 1, \mathbf {z}\in P \}. $$

It contains the origin $\mathbf {y}= 0$, and its vertices are the endpoints of the vectors

$$ \mathbf {p}_{f}(\mathbf {x}) := \frac{\mathbf {n}_{f}}{h_{f}(\mathbf {x})}, \qquad f \in F, $$

when placed at the origin. Suppose that a vertex $\mathbf {v}\in V$ has $k$ incident faces, $f_1,\ldots ,f_k$, for some $k \ge 3$, where we again assume they are ordered in some anticlockwise fashion around $\mathbf {v}$, as seen from outside $P$. The endpoints of the $k$ vectors $\mathbf {p}_{f_1}(\mathbf {x}), \ldots \mathbf {p}_{f_k}(\mathbf {x})$ form a $k$-sided polygon. This polygon is the face of $\tilde{P}_\mathbf {x}$, dual to the vertex $\mathbf {v}$ of $P$. This face and the origin in $\mathbb {R}^3$ form a polygonal pyramid, $Q_\mathbf {v}\subset \tilde{P}_\mathbf {x}$. It was shown in [15] that if we define

$$ {\textit{w}}_\mathbf {v}(\mathbf {x}) = \mathrm{vol}(Q_\mathbf {v}), $$

then the functions $\phi _\mathbf {v}$ in (23) are again barycentric coordinates. In practice, we could triangulate the face dual to $\mathbf {v}$ by connecting the endpoint of $\mathbf {p}_{f_1}(\mathbf {x})$ to the endpoints of all the other $\mathbf {p}_{f_i}(\mathbf {x})$, and so compute $\mathrm{vol}(Q_\mathbf {v})$ as a sum of volumes of tetrahedra. Thus, we could let

$$\begin{aligned} {\textit{w}}_\mathbf {v}(\mathbf {x}) = \sum _{i=2}^{k-1} \det (\mathbf {p}_{f_1}(\mathbf {x}),\mathbf {p}_{f_i}(\mathbf {x}),\mathbf {p}_{f_{i+1}}(\mathbf {x})). \end{aligned}$$

(25)

Some matlab code for evaluating these coordinates and their gradients can be found in [6].

7.2 MV Coordinates in 3D

MV coordinates were generalized to three dimensions in [8, 16], the basic idea being to replace integration over the unit circle, as in Sect. 4, by integration over the unit sphere.

Consider first the case that $P \subset \mathbb {R}^3$ is a convex polyhedron with triangular faces (though it does not need to be simple). Fix $\mathbf {x}\in P$ and consider the radial projection of the boundary of $P$ onto the unit sphere centered at $\mathbf {x}$. A vertex $\mathbf {v}\in V$ is projected to the point (unit vector) $\mathbf {e}_\mathbf {v}:= (\mathbf {v}-\mathbf {x})/|\mathbf {v}-\mathbf {x}|$. A face $f \in F$ is projected to a spherical triangle $f_\mathbf {x}$ whose vertices are $\mathbf {e}_\mathbf {v}$, $\mathbf {v}\in V_f$, where $V_f \subset V$ denotes the set of (three) vertices of $f$. Let $\mathbf {I}_f$ denote the (vector-valued) integral of its unit normals,

$$ \mathbf {I}_f := \int \limits _{f_\mathbf {x}} \mathbf {n}(\mathbf {y}) \,d\mathbf {y}. $$

Since the three vectors $\mathbf {e}_\mathbf {v}$, $\mathbf {v}\in V_f$, are linearly independent, there are three unique weights ${\textit{w}}_{\mathbf {v},f} > 0$ such that

$$\begin{aligned} \mathbf {I}_f = \sum _{\mathbf {v}\in V_f} {\textit{w}}_{\mathbf {v},f} \mathbf {e}_\mathbf {v}. \end{aligned}$$

(26)

The weights can be found as ratios of $3\times 3$ determinants from Cramer’s rule. Since the integral of all unit normals of the unit sphere is zero, and letting $F_\mathbf {v}\subset F$ denote the set of faces that are incident on the vertex $\mathbf {v}$, we find, by switching summations, that

$$ 0 = \sum _{f \in F} \mathbf {I}_f = \sum _{f \in F} \sum _{\mathbf {v}\in V_f} {\textit{w}}_{\mathbf {v},f} \mathbf {e}_\mathbf {v}= \sum _{\mathbf {v}\in V} \sum _{f \in F_\mathbf {v}} {\textit{w}}_{\mathbf {v},f} \mathbf {e}_\mathbf {v}, $$

and so the functions

$$\begin{aligned} {\textit{w}}_\mathbf {v}:= \sum _{f \in F_\mathbf {v}} \frac{{\textit{w}}_{\mathbf {v},f}}{|\mathbf {v}-\mathbf {x}|}, \end{aligned}$$

(27)

satisfy

$$ \sum _{\mathbf {v}\in V} {\textit{w}}_\mathbf {v}(\mathbf {x}) (\mathbf {v}-\mathbf {x}) = 0. $$

It follows that the functions $\phi _\mathbf {v}$ given by (23) with ${\textit{w}}_\mathbf {v}$ given by (27) are barycentric coordinates, i.e., they are positive in $P$ and satisfy (24).

It remains to find the integral $\mathbf {I}_f$ in terms of the points $\mathbf {v}\in V_f$ and $\mathbf {x}$. We follow the observation made in [8]. The spherical triangle $f_\mathbf {x}$ and the point $\mathbf {x}$ form a wedge of the solid unit sphere centered at $\mathbf {x}$. Since the integral of all unit normals over this wedge is zero, the integral $\mathbf {I}_f$ is minus the sum of the integrals over the three planar faces of the wedge. Suppose $\mathbf {v}_1,\mathbf {v}_2,\mathbf {v}_3$ are the vertices of $f$ in anticlockwise order, and let $\mathbf {e}_i = \mathbf {e}_{\mathbf {v}_i}$. For $i=1,2,3$, the $i$th side of the wedge is the sector of the unit circle formed by the two unit vectors $\mathbf {e}_i$ and $\mathbf {e}_{i+1}$, with the cyclic notation $\mathbf {v}_{i+3} := \mathbf {v}_i$. If $\beta _i \in (0,\pi )$ is the angle between $\mathbf {e}_i$ and $\mathbf {e}_{i+1}$ then the area of the sector is $\beta _i/2$, and hence

$$\begin{aligned} \mathbf {I}_f = \frac{1}{2} \sum _{i=1}^3 \beta _i \mathbf {m}_i, \end{aligned}$$

(28)

where

$$ \mathbf {m}_i = \frac{\mathbf {e}_i \times \mathbf {e}_{i+1}}{|\mathbf {e}_i \times \mathbf {e}_{i+1}|}. $$

Equating this with (26) gives

$$ \textit{w}_{\mathbf {v}_i,f} = \frac{1}{2} \sum _{j=1}^3 \beta _j \frac{\mathbf {m}_j \cdot \mathbf {m}_{i+1}}{\mathbf {e}_i \cdot \mathbf {m}_{i+1}}. $$

These 3D MV coordinates were used for surface deformation in [16] when the surface is represented as a dense triangular mesh. Some contour plots of the coordinate functions can be found in [8].

For a polyhedron with faces having arbitrary numbers of vertices, the same approach can be applied, but there is no longer uniqueness. Suppose $f \in F$ is a face with $k \ge 3$ vertices. The integral $\mathbf {I}_f$ is again well-defined, and can be computed as the sum of $k$ terms, generalizing (28). However, there is no unique choice of the local weights ${\textit{w}}_{\mathbf {v},f}$ in (26) for $k > 3$, since there are $k$ of these. Langer et al. [17] proposed using a certain type of spherical polygonal MV coordinates to determine the ${\textit{w}}_{\mathbf {v},f}$, but other choices are possible.

8 Final Remarks

We have not covered here other kinds of generalized barycentric coordinates, and related coordinates, which include Sibson’s natural neighbor coordinates [24], Sukumar’s maximum entropy coordinates [25], Gordon and Wixom coordinates [12], spherical barycentric coordinates [17], harmonic coordinates [14], Green coordinates [21], Poisson coordinates [18], Positive MV coordinates [20] and others. A more general survey paper is being planned in which some of these other coordinates will be included.