图形学初识：三角形重心坐标插值算法详解
图形学初识：三角形重心坐标插值算法详解
三角形插值算法是计算机图形学中的一个重要概念，特别是在处理三角形网格的属性插值时。本文将详细介绍三角形重心坐标插值算法，通过数学推导和几何解释，帮助读者理解这一算法的核心思想和具体实现方法。
前言
在前面的文章中，我们讨论了直线光栅化和直线插值的内容。本篇文章将重点介绍三角形插值算法，主要利用重心坐标公式。虽然这里暂不涉及三角形光栅化的内容，但这些知识将为后续学习打下坚实的基础。
正文
为什么需要三角形插值？
在计算机图形学中，我们经常需要处理三角形网格。如果我们知道屏幕上三角形三个顶点各自的属性值（如颜色、纹理坐标等），如何得知三角形内部所有像素位置的属性值呢？这就是三角形插值要解决的问题。
什么是三角形插值？
用数学符号来描述：已知三角形的三个顶点 $v_0$、$v_1$、$v_2$，每个顶点的属性值 $f(v_0)$、$f(v_1)$、$f(v_2)$，我们需要计算三角形内任意顶点 $v_{in}$ 的属性值 $f(v_{in})$。
如何进行三角形插值？
虽然可能有其他三角形插值算法，但本文重点介绍重心坐标插值算法。
1. 结论
对于三角形 $\triangle ABC$ 内任意一点 $P$，都存在 $0 < \alpha, \beta, \gamma < 1$ 且 $\alpha + \beta + \gamma = 1$，使得
$$f(P) = \alpha f(A) + \beta f(B) + \gamma f(C)$$
为了简化算法核心内容的阐述，我们暂时忽略三角形边界情况，即不考虑取0和1的情况。
2. 核心理解
通过观察上述结论，可以发现：只要通过三角形三个顶点属性值的加权混合，就可以获得三角形内部任何位置的顶点的属性值。
3. 几何理解-重心坐标公式推导
（1）已知三角形 $\triangle ABC$，其中一点 $P$ 位于三角形内部
（2）借助向量辅助推导，推导出顶点 $P$ 和 $A$、$B$、$C$ 的关系
$$
\begin{aligned}
&\because 向量 \vec{AB} , \vec{AC} 线性无关\
&\therefore 一定 \exists 常数 \beta、\gamma 使得\vec{AP} = \beta\vec{AB} + \gamma\vec{AC}\
&\because\vec{AB} = B-A，\vec{AC} = C-A，\vec{AP} = P-A\
&\therefore P - A = \beta(B-A) + \gamma(C-A)\
&\therefore P = (1 - \beta - \gamma)A + \beta B + \gamma C\
&记\alpha = 1 - \beta - \gamma,从而\exists (\alpha + \beta + \gamma = 1),使得P = \alpha A + \beta B + \gamma C\
\end{aligned}
$$
（3）接下来的关键就是求解三个常数系数：$\alpha$、$\beta$、$\gamma$ 的值
针对上述的 $\triangle ABC$，我们需要作点 $P$ 和点 $B$ 分别到直线 $AC$ 的垂线，交点分别记作 $D$ 和 $E$，然后连接 $PC$
这里分别计算 $\triangle APC$ 和 $\triangle ABC$ 的面积：
$$
S_{APC} = 0.5 * AC * PD\
S_{ABC} = 0.5 * AC * BE
$$
上下两式相除，得到：
$$
\frac{S_{APC}}{S_{ABC}} = \frac{PD}{BE}
$$
记 $PD = h_p$，$BE = h_b$
（4）上述的计算看似没啥用，但是我们可以联想相似三角形的知识，类比转换！
做辅助线：过 $P$ 点做垂直于 $PD$ 的直线 $l_1$，交线段 $AB$ 于点 $F$。然后过点 $F$ 做平行线 $l_2$ 交线段 $AC$ 于点 $G$，如下图所示：
（5）向量加法几何理解突破
因为四边形 $PFGD$ 是矩形，所以 $PD == FG$，结合之前的公式：
$$
\frac{S_{APC}}{S_{ABC}} = \frac{PD}{BE} = \frac{FG}{BE}
$$
又因为 $\triangle AFG$ 和 $\triangle ABE$ 是相似三角形（为什么就不用多说了，初中知识），所以：
$$
\frac{FG}{BE} = \frac{AF}{AB}
$$
这时候，结合开头提到的公式：
$$
\vec{AP} = \beta \vec{AB} + \gamma \vec{AC}
$$
然后再结合向量加法的几何理解，我们可以得到：
$$
AF = \beta * AB
$$
从而得到：
$$
\frac{AF}{AB} = \beta
$$
也就得到了：
$$
\beta = \frac{S_{APC}}{S_{ABC}}
$$
（6）同理。我们也可以得到 $\alpha$ 和 $\gamma$ 的值，如下：
$$
\alpha = \frac{S_{BPC}}{S_{ABC}}\
\beta = \frac{S_{APC}}{S_{ABC}}\
\gamma = \frac{S_{APB}}{S_{ABC}}
$$
（7）至于三角形的公式，咱们不多说，这里贴出来：
$$
S_{BPC} = 0.5 *||\vec{PB} \times \vec{PC}||\
S_{APC} = 0.5 *||\vec{PA} \times \vec{PC}||\
S_{APB} = 0.5 *||\vec{PA} \times \vec{PB}||\
S_{ABC} = 0.5 *||\vec{AB} \times \vec{AC}||
$$
大功告成，希望对大家所有帮助！画图用的是在线软件：geogebra