Mean Value Coordinates

Mean coordinates –Mean Value Coordinates(MVC) Is an important interpolation technique , It is widely used in parameterization 、 Mesh deformation and other geometric processing directions . But few blogs tell about MVC, Especially for computing triangular meshes MVC, Most people implement it directly according to the pseudo code in the paper . Recently I reread about MVC A few classic papers of , So here is a brief introduction .

1. The coordinates of the center of gravity

For triangles $△v_1{v}_2{v}_3$ At any point $p$ Expressed as a convex combination of three vertices of a triangle , That is, the following equation is satisfied ：

$p={\lambda }_1{v}_1+{\lambda }_2{v}_2+{\lambda }_3{v}_3$ （1）

${\lambda }_1+{\lambda }_2+{\lambda }_3=1$ （2）

For triangles , As shown in the figure below , Weights are easy to calculate （ The ratio of triangle area ）：

${\lambda }_1=A△p{v}_2{v}_3/A△v_1{v}_2{v}_3$,

${\lambda }_2=A△p{v}_1{v}_3/A△v_1{v}_2{v}_3$,

${\lambda }_3=A△p{v}_1{v}_2/A△v_1{v}_2{v}_3$

Why is it called barycentric coordinates ？ The following is an excerpt from ： The coordinates of the center of gravity （Barycentric coordinates）

equation (1) Can be converted to ：

${\lambda }_1(v_1-p)+{\lambda }_2(v_2-p)+{\lambda }_3(v_3-p)=0$

=> ${\lambda }_1\mathbf{p}{\mathbf{v}}_1+{\lambda }_2\mathbf{p}{\mathbf{v}}_2+{\lambda }_3\mathbf{p}{\mathbf{v}}_3=0$

It is equivalent to that we are at the three vertices of the triangle $v_1$ The hanging weight is ${\lambda }_1$, $v_2$ The hanging weight is ${\lambda }_2$, $v_3$ The hanging weight is ${\lambda }_3$ When the weight of , If you put $p$ Place it on the lightning rod , Can maintain balance , In this case $p$ Center of gravity .

2. Generalized barycentric coordinates

As mentioned above , It is easy to calculate the barycentric coordinates of a triangle , But we're not satisfied with that . We want to solve the interior vertex of a polygon Generalized barycentric coordinates , That is, the vertices inside the polygon are represented as convex combinations of polygon vertices ：

$p={\sum }_{i=1}^n{\lambda }_i{v}_i$ （3）

${\sum }_{i=1}^n{\lambda }_i=1$ （4）

There are many ways to find generalized barycentric coordinates, such as ： Mean coordinates (MVC), Green coordinates (GC), Harmonic coordinates (HC) etc. , Here we introduce the widely used calculation method of mean value .

3. 2D Mean coordinates

For general 2D The polygon of ,Floater The mean coordinate given is ：

${\lambda }_i=w_i/{\sum }_{j=1}^n{w}_j$,

$w_i=[tan({\alpha }_{i-1}/2)+tan({\alpha }_i/2)]/||v_i-p||$ （5）

It can be seen that the coordinates represented by this form are always positive , Now I'll simply move this proof process ,

Our goal is to convert the points inside the polygon $p$ Represented as a convex combination of polygon vertices ：$p={\sum }_{i=1}^n{\lambda }_i{v}_i$

Equivalent to ： ${\sum }_{i=1}^n{\lambda }_i(v_i-p)=0$, and ${\lambda }_i=w_i/{\sum }_{j=1}^n{w}_j$

Multiply the left and right sides by ${\sum }_{j=1}^n{w}_j$, Yes ：${\sum }_{i=1}^n{w}_i(v_i-p)=0$ （6）

Next , Use $v_0$ The polar coordinates at represent $v_i$： $v_i=v_0+||v_i-p||(cos{\theta }_i,sin{\theta }_i)$

So there are ：$(v_i-p)/||v_i-p||=(cos{\theta }_i,sin{\theta }_i)$ , ${\alpha }_i={\theta }_{i+1}-{\theta }_i$ （7）

take （5） Plug in （6）：

${\sum }_{i=1}^n[tan({\alpha }_{i-1}/2)+tan({\alpha }_i/2)]\cdot (v_i-p)/||v_i-p||=0$ （8）

take （7） Plug in （8）：

${\sum }_{i=1}^n[tan({\alpha }_{i-1}/2)+tan({\alpha }_i/2)](cos{\theta }_i,sin{\theta }_i)=0$ （9）

The above formula is further equivalent to ：

${\sum }_{i=1}^{n}tan({\alpha }_i/2)[(cos{\theta }_i,sin{\theta }_i)+(cos{\theta }_{i+1},sin{\theta }_{i+1})]=0$ （10）

If we can prove the equation （10） establish , Then the vertices inside the polygon can be represented by an equation （5） The coordinates shown represent （ interpolation ）.

First , We know , The sum of all unit vectors from the center of the circle to the circumference is 0 vector , Because any vector can find a vector with the same size and opposite direction .

$0={\int }_0^{2\pi }(cos\theta ,sin\theta )$

$={\sum }_{i=1}^k{\int }_{{\theta }_i}^{{\theta }_{i+1}}(cos\theta ,sin\theta )$

$={\sum }_{i=1}^k{\int }_{{\theta }_i}^{{\theta }_{i+1}}\frac{sin({\theta }_{i+1}-\theta )}{sin{\alpha }_i}(cos{\theta }_i,sin{\theta }_i)+\frac{sin(\theta -{\theta }_i)}{sin{\alpha }_i}(cos{\theta }_{i+1},sin{\theta }_{i+1})$

The third line here is cleverly constructed . Integral of the above formula ：

$={\sum }_{i=1}^k\frac{(cos{\theta }_i,sin{\theta }_i)}{sin{\alpha }_i}{\int }_{{\theta }_i}^{{\theta }_{i+1}}sin({\theta }_{i+1}-\theta )d\theta +\frac{(cos{\theta }_{i+1},sin{\theta }_{i+1})}{sin{\alpha }_i}{\int }_{{\theta }_i}^{{\theta }_{i+1}}sin(\theta -{\theta }_{i+1})d\theta$ （11）

and ${\int }_{{\theta }_i}^{{\theta }_{i+1}}sin({\theta }_{i+1}-\theta )d\theta ={\int }_{{\theta }_i}^{{\theta }_{i+1}}sin(\theta -{\theta }_{i+1})d\theta =1-cos{\alpha }_i$, therefore （11） The calculation result is ：

$={\sum }_{i=1}^k\frac{(1-cos{\alpha }_i)(cos{\theta }_i,sin{\theta }_i)}{sin{\alpha }_i}+\frac{(1-cos{\alpha }_i)(cos{\theta }_{i+1},sin{\theta }_{i+1})}{sin{\alpha }_i}$ （12）

because ： $\frac{1-cos{\alpha }_i}{sin{\alpha }_i}=tan({\alpha }_i/2)$, therefore （12） Equivalent to ：

$={\sum }_{i=1}^{k}tan({\alpha }_i/2)[(cos{\theta }_i,sin{\theta }_i)+(cos{\theta }_{i+1},sin{\theta }_{i+1})]$ （13）

therefore , equation （10） Obtain evidence .

Specific reference Floater The paper of ：Mean value coordinates. Computer aided geometric design, 2003

4. 3D Mean coordinates

Our goal is to transform any point inside the triangular mesh $p$ Represented as a convex combination of triangular mesh vertices ： Like the equation （3）（4） Shown .

If you can find this coordinate to represent $p$ Words , that , We will get the formula （6）：${\sum }_{i=1}^n{w}_i(v_i-p)=0$ （6）

Here we make $p$ A unit ball at the center of a ball , Project the triangular mesh onto the sphere .

The triangles on each mesh will be projected onto the sphere to form spherical triangles , Such as in the figure above (2)(3) Each spherical triangle in corresponds to an average vector $m$, This vector is all from $p$ Point to All points on the spherical triangle The result of the integral of the unit vector of （ Sum up ）.

according to Stokes’ Theorem, The integral of the unit normal vector of all points on a closed surface is 0 The vector has ：

${\sum }_{k=1}^3\frac{1}{2}{\theta }_k{n}_k+m=0$ （14）

among ,$\frac{1}{2}{\theta }_k$ The angle is ${\theta }_k$ The area of the sector ,$n_k$ Is the normal direction of this plane , therefore $\frac{1}{2}{\theta }_k{n}_k$ The normal integral of this surface .（14） indicate , Unit normal integral of three fan-shaped sides + Sum of unit vector integrals on a spherical triangle = 0 vector .

meanwhile , We found that $m$ It can also be expressed as a linear combination of three vectors ：

$m={\sum }_{k=1}^3{w}_k(v_k-p)$ （15）

Obviously , Upper figure （4） Wedge in , Three straight edges are three vectors $(v_k-p)$ Unit vector . And any vector $m$ Of course, these three basis vectors can uniquely represent .

combination （14）（15） We can get the following equation ：

$m={\sum }_{k=1}^3\frac{1}{2}{\theta }_k{n}_k={\sum }_{k=1}^3{w}_k(v_k-p)$ （16）

Suppose that the three vertices corresponding to the current triangle are $v_1,v_2,v_3$, Expanded :

$m=w_1(v_1-p)+w_2(v_2-p)+w_3(v_3-p)$ （17）

It should be noted that ：$p{v}_1$ And $p{v}_2$ The normal direction of the plane is $n_3$, $p{v}_2$ And $p{v}_3$ The normal direction of the plane is $n_1$, $p{v}_1$ And $p{v}_3$ The normal direction of the plane is $n_2$.

therefore , For the formula （17）, To separate $w_1$ Just multiply the left and right sides of the equation $n_1$ that will do , This will eliminate the last two items . So there is ：

$w_k=\frac{n_k\cdot m}{n_k\cdot (v_k-p)}$

Of course , This is just a triangle $△v_i{v}_j{v}_k$ Project onto a sphere , The calculated vertices of this triangle are relative to the inner vertices $p$ The contribution of , Actually, it's just here $v_i$ for , It may also be associated with other triangles , such as $△v_i{v}_j{v}_q$, In the actual calculation process, all triangles should be traversed for calculation .

Specific reference Tao Ju The paper of ：Mean value coordinates for closed triangular meshes, ACM Siggraph 2005 Papers. 2005
And corresponding slides： https://people.engr.tamu.edu/schaefer/teaching/689_Fall2006/talks/meanvalue.pdf