当前位置：网站首页>[barycentric coordinate interpolation, perspective correction interpolation] principle and usage opinions

[barycentric coordinate interpolation, perspective correction interpolation] principle and usage opinions

2022-04-23 13:30:00 【Zong haoduolao】

List of articles

1、Barycentric Coordinates（ The coordinates of the center of gravity ）
2 The calculation formula of center of gravity
3 Perspective projection interpolation correction

1、Barycentric Coordinates（ The coordinates of the center of gravity ）

For reference only , Math is weak , There is no guarantee of correctness .. But there should be a harvest after reading it

1.1 The concept of barycentric coordinates

With 2D For example ：

Any point inside the triangle ( Including vertices ) Can be expressed as a linear combination of three vertices . Three coefficients satisfying the following relationship (α,β,γ) Is the center of gravity coordinate of the point . Another limitation is that these three coefficients must be nonnegative , Otherwise it's outside the triangle
In short , It's a point inside the triangle (x,y) The representation in the center of gravity coordinate is (α,β,γ)
The center of gravity coordinates of the three vertices are
A：(1,0,0)
B：(0,1,0)
C：(0,0,1)

1.2 Calculation method of center of gravity coordinates

For the interior points of the triangle P How to calculate its central coordinates

Method 1： Area ratio

A The coefficient of α： Its corresponding triangular area A_A( The red part ) Ratio to total area
B The coefficient of β： Its corresponding triangular area A_B( The yellow part ) Ratio to total area
C The coefficient of γ： Its corresponding triangular area A_C( The blue part ) Ratio to total area

Method 2： Use the formula derived from
Say first conclusion , The second part explains the derivation process in detail
$\color{red}\large β=\frac{ (y- y_{\tiny A})(x_{\tiny C} - x_{\tiny A})-(x - x_{\tiny A})(y_{\tiny C} - y_{\tiny A}) }{(y_{\tiny B} - y_{\tiny A})(x_{\tiny C} - x_{\tiny A})-(x_{\tiny B} - x_{\tiny A})(y_{\tiny C} - y_{\tiny A})}\\ \: \\ \large γ=\frac{ (y- y_{\tiny A})(x_{\tiny B} - x_{\tiny A})-(x - x_{\tiny A})(y_{\tiny B} - y_{\tiny A}) }{(y_{\tiny C} - y_{\tiny A})(x_{\tiny B} - x_{\tiny A})-(x_{\tiny C} - x_{\tiny A})(y_{\tiny B} - y_{\tiny A})}\\ \: \\ α=1-β-γ\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:$

1.3 Center of gravity coordinates interpolation

The calculation method of known center of gravity coordinates , How to interpolate attributes ？

The calculated center of gravity coordinates (α,β,γ), In fact, it is equivalent to a weight ratio , Put the corresponding V_AV_BV_C Switch to uv coordinate 、 Color 、 normal 、 Depth value 、 Material properties ,V That is, what you want
Insert picture description here

2 The calculation formula of center of gravity

Insert picture description here

It is known that 2D In the plane $△ A B C$ The coordinates of the three vertices $\large A:(x_A,y_A),B:(x_B,y_B),C:(x_C,y_C)$ And any point inside the triangle P Coordinates of $\large P:(x, y)$

spot $P$ Two conditions must be met ：
$\begin{cases} P=\alpha A + \beta B +\gamma C\cdots\cdots\cdots\cdots① \\ \alpha+\beta+\gamma = 1 \cdots\cdots\cdots\cdots\cdots\cdots② \end{cases}$

How to calculate... According to known conditions $\alpha、\beta、\gamma$ ？

Step 1
The formula ② Plug in ①, We can eliminate an unknown quantity （ Here I put α Kill first ,101 In the course, they were killed γ, The process is the same ）
$P = (1 - β - γ) A + β B + γ C$
Open parentheses , Merge similar items and simply move items , It is easy to conclude that
$P-A=β(B-A)+γ(C-A)\cdots\cdots\cdots\cdots③$

This formula. , Can be understood in terms of vector operations , $\overrightarrow {AP} = β\overrightarrow {AB}+γ\overrightarrow {AC}$

Step 2
By formula ③, The known points $A 、 B 、 C 、 P$ Substitute the coordinates of , Available
$\large \begin{pmatrix} x - x_{\tiny A} \\y- y_{\tiny A} \end{pmatrix}= β\large\begin{pmatrix} x_{\tiny B} - x_{\tiny A} \\ y_{\tiny B} - y_{\tiny A} \end{pmatrix}+ γ\large\begin{pmatrix}x_{\tiny C} - x_{\tiny A} \\ y_{\tiny C} - y_{\tiny A} \end{pmatrix}$
Open write , Available equations ( Two unknowns , Two equations )
$\begin{cases} (x - x_{\tiny A}) =β(x_{\tiny B} - x_{\tiny A})+γ(x_{\tiny C} - x_{\tiny A})\cdots\cdots④\\ (y- y_{\tiny A})=β(y_{\tiny B} - y_{\tiny A})+γ(y_{\tiny C} - y_{\tiny A})\cdots\cdots\cdot⑤ \end{cases}$

$④\times(y_{\tiny C} - y_{\tiny A}),⑤\times(x_{\tiny C} - x_{\tiny A})$ have to ：
$x_{\tiny A})(y_{\tiny C} - y_{\tiny A}) = β(x_{\tiny B} - x_{\tiny A})(y_{\tiny C} - y_{\tiny A})+\cancel{γ(x_{\tiny C} - x_{\tiny A})(y_{\tiny C} - y_{\tiny A})} \cdots\cdots⑥\\ (y- y_{\tiny A})(x_{\tiny C} - x_{\tiny A}) = β(y_{\tiny B} - y_{\tiny A})(x_{\tiny C} - x_{\tiny A})+\cancel{γ(y_{\tiny C} - y_{\tiny A})(x_{\tiny C} - x_{\tiny A})}\cdots\cdots⑦$
$⑦ - ⑥$ obtain β, The same can be γ

Step 3
Final $α 、 β 、 γ$ expression
$\color{red}\large β=\frac{ (y- y_{\tiny A})(x_{\tiny C} - x_{\tiny A})-(x - x_{\tiny A})(y_{\tiny C} - y_{\tiny A}) }{(y_{\tiny B} - y_{\tiny A})(x_{\tiny C} - x_{\tiny A})-(x_{\tiny B} - x_{\tiny A})(y_{\tiny C} - y_{\tiny A})}\\ \: \\ \large γ=\frac{ (y- y_{\tiny A})(x_{\tiny B} - x_{\tiny A})-(x - x_{\tiny A})(y_{\tiny B} - y_{\tiny A}) }{(y_{\tiny C} - y_{\tiny A})(x_{\tiny B} - x_{\tiny A})-(x_{\tiny C} - x_{\tiny A})(y_{\tiny B} - y_{\tiny A})}\\ \: \\ α=1-β-γ\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:$

Here we are , The interpolation of barycentric coordinates is over , Calculate the center of gravity coordinates separately in the two-dimensional plane or three-dimensional plane according to the coordinates of four points ( The weight ) And then interpolation P Normal of 、uv Coordinates and everything , Can get very correct results

however , The interpolation after projection is very particular

Basic knowledge of perspective projection , I won't go into that here , Its related detailed steps , Visible Of this article 4.3 part

For a particular triangle in space , Only three vertices carry coordinate information $(x, y, z)$ , Do perspective projection on it , These three points change to the screen space of the camera , here , What do we do if we want to get a depth map ？

Method of establishing deep cache

First create a deep cache , It's actually a two-dimensional array zbuffer[width][height], And initialize each array element to infinity
Traverse each pixel covered by each triangle , take The point in the scene corresponding to this pixel z value Follow zbuffer Corresponding to position z The comparison , Small ones cover

The question is how to know Of the pixel z How much is the ？

(1) You might think , We already know the coordinates of the three vertices after projection transformation on the screen $\large(x_{\tiny A},y_{\tiny A}),(x_{\tiny B},y_{\tiny B}),(x_{\tiny C},y_{\tiny C})$ And target pixels P $(x, y)$ . Work out P The center of gravity coordinates of the point , Then I have the depth of three known vertices Z, Interpolation is enough . Good idea , But this approach is In the wrong , Can't be calculated by interpolation $(α, β, γ)$ There are many reasons for direct interpolation , Part of the reason is as follows ：

After projection, the shape of the triangle will generally change . An equilateral triangle in space , After projection, it may become a particularly narrow triangle , At this time, I calculate the weight ratio of the pixel ( The coordinates of the center of gravity ) It must be different from the weight ratio of the point corresponding to the pixel in the space in the triangle , So direct interpolation , Not an option .
After projection , Far away from the vertebral body / Points near the plane , after Squish After transformation ,z The value is constant , But the point in the middle of the optic vertebral body , After transformation z The absolute value of will become larger , So on the projected triangle Direct interpolation , Not an option

（2） You may also think of , Target pixels in screen space P Point application Inverse of perspective projection matrix , Do an inverse transformation and change it back to the original space , Then you know P The exact position of the point in space , Then interpolate the depth , Write back to the deep cache P Pixel position . OK This is very accurate , however , Each pixel has to do an inverse matrix operation , The resolution of my depth map may be millions of pixels , this The amount of calculation is unacceptable

A lot of wordiness , I hope I have no problem , Some questions are clear in my mind , But I don't know how to say it . If there is a mistake, please give us more advice

3 Perspective projection interpolation correction

Insert picture description here

3.1 After fluoroscopy correction `Depth interpolation formula`

International practice , Say first conclusion , If you are not interested in deriving a direct set of formulas
$\displaystyle\large\color{red} \frac{1}{Z}=α'\frac{1}{Z_A}+β'\frac{1}{Z_B}+γ'\frac{1}{Z_C}$
Symbol description ： belt $^{'}$ All are projected values , What you don't bring is the value in world space

$\\α'、β'、γ'： The center of gravity coordinates calculated in screen space \\Z_A、Z_B、Z_C： The depth value of three vertices in space$

Derivation process The core idea ： Through the projected interior point of the triangle $P^{'}$ Of $α^{'} 、 β^{'} 、 γ^{'}$ , Calculate the inner point of the triangle before projection $P$ Depth value of

Step 1： Find the relationship between the center of gravity coordinates before and after projection

For the formula $1 = α^{'} + β^{'} + γ^{'}$ Do identity deformation
$\frac{Z}{Z}=\frac{Z_A}{Z_A}α'+\frac{Z_B}{Z_B}β'+\frac{Z_C}{Z_C}γ'$
Left and right are the same ×Z
$=(\frac{Z}{Z_A}α')Z_A+(\frac{Z}{Z_B}β')Z_B+(\frac{Z}{Z_C}γ')Z_C\dots\dots\dots①$
Compare the interpolation formula before projection
$αZ_A+βZ_B+γZ_C\cdots\cdots\cdots\cdots②$
To unite ①②, have to
$α=\frac{Z}{Z_A}α',β=\frac{Z}{Z_B}β',γ=\frac{Z}{Z_C}γ'$
Step 2： The depth interpolation formula after perspective correction is obtained

because $1 = α + β + γ$ , And $\displaystyle α=\frac{Z}{Z_A}α',β=\frac{Z}{Z_B}β',γ=\frac{Z}{Z_C}γ'$

therefore
$\frac{Z}{Z_A}α'+\frac{Z}{Z_B}β'+\frac{Z}{Z_C}γ'\cdots\cdots\cdots③$
Yes ③ Left and right are the same $\times \frac{1}{Z}$
$\displaystyle\color{red}\Large\frac{1}{Z}=α' \frac{1}{Z_A}+β'\frac{1}{Z_B}+γ'\frac{1}{Z_C}$

At this point, a deep cache can be well generated 、shadow map 了

3.2 A very important detail of perspective projection

Note that after completing the perspective projection , Three vertices in screen space $A^{'} B^{'} C^{'}$ Of $z$ component $Z_A,Z_B,Z_C$ It does not store the correct depth of the three vertices originally located in world space , After applying the projection matrix, this z The storage depth of components has become far away , Original Z, After transformation , Run to the homogeneous coordinates of w On weight

Now let's take any point inside the vertebral body $P = (x, y, z, 1)$ , Apply perspective projection matrix
$\Large \begin{bmatrix} \frac{2n}{r-l}&0&\frac{l+r}{l-r}&0 \\ 0 & \frac{2n}{t-b}&\frac{b+t}{b-t}&0 \\ 0&0&\frac{n+f}{n-f}&\frac{2nf}{n-f}\\ 0&0&1&0 \end{bmatrix}·\begin{bmatrix}x\\y\\z\\1\end{bmatrix} = \begin{bmatrix} \small No concern \\\small Too lazy to count \\ \small Is not important \\ \color{red}\mathbf z \end{bmatrix}$

ok, After applying the perspective projection matrix , Triangle vertices in screen space ,vertex[0].w() It's the apex 0 The correct depth value before perspective projection , With interpolation formula $Z_A$ Take this value , Don't take it .z() component

About Squish The problem that matrices push points away is also particularly simple , Choose any one , Left multiplication M_squish And then determine z That's enough

3.2 More general ： `Arbitrary attribute interpolation formula`

Don't understand the meaning of existence , The above formula should be enough . Who knows, can you tell me

$I$ Is the target attribute of the target point in the triangle

Barycentric coordinate interpolation formula ： $\large I = αI_A+βI_B+γI_C$
Again because
$\largeα=\frac{Z}{Z_A}α',β=\frac{Z}{Z_B}β',γ=\frac{Z}{Z_C}γ'$
therefore $I = α'I_A+β'I_B+γ'I_C$ It can be written as
$\large\color{red} I=Z·(α'\frac{I_A}{Z_A}+β'\frac{I_B}{Z_B}+γ'\frac{I_C}{Z_C})$

$\\ I_A、I_B、I_C Is any attribute of three vertices$


// The center of gravity coordinates are calculated here 
auto [alpha, beta, gamma] = computeBarycentric2D(i+0.5, j+0.5, t.v);

// w_reciprocal That's the pixel p The depth value in the corresponding observation space z
float w_reciprocal = 1.0 / (alpha / v[0].w() + beta / v[1].w() + gamma / v[2].w());
//  But here we use arbitrary attribute interpolation formula , I'm a little confused ,  also IA Taken v[0].z()
float z_interpolated = w_reciprocal*(alpha*v[0].z()/v[0].w() + beta*v[1].z()/v[1].w() + gamma*v[2].z()/v[2].w());

$\displaystyle\large w\_reciprocal=\frac{1}{α' \frac{1}{Z_A}+β'\frac{1}{Z_B}+γ'\frac{1}{Z_C}}$ （ It's calculated here Z As the following Z, To calculate any attribute ）

$\displaystyle\large z\_interpolated =\color{red}Z\color{normal} ·(α'\frac{I_A}{Z_A}+β'\frac{I_B}{Z_B}+γ'\frac{I_C}{Z_C})$ （ And any attribute is calculation Z- - ...）

Then the process of interpolating any attribute is divided into two steps ：

（1） interpolation $z$ , Because... Must be used in the formula of interpolating any attribute z
（2） Arbitrary interpolation properties $I$ . $I_A、I_B、I_C$ The selection method is the information contained in the three vertices of the screen space （ As above A_Z It's really V[0].z()）, Whether it changes after projection or not , Directly into , This is the value of this formula . Now what I can think of is this , Leave a hole and fill it when you're sure