这个文章是一个系列教程的一部分，点击阅读原文可看整个教程的索引。
欢迎回到我的即兴优化系列。今天我们不会看到一行代码，也不会看到一个分析器截图。这是因为我们的下一篇文章的主题是三角形光栅化器，在我们深入了解光栅化器之前，我们最好先梳理我们对三角形的了解。这里面的很多知识将涉及重心坐标，因此本篇文章由此得名。要警惕的是，这篇文章比以前的文章要枯燥得多，最终也没有什么大的收益。这是一个纯粹的未切割的信息转储。目的是在一个地方收集所有这些材料，以便我可以在必要的时候再次参考。
认识三角形
让我们从快速开始，假设你已经知道了有关三角形的一大堆事情。如果不是这样的话，维基百科可以帮助你，那里面的内容几乎可以相当于覆盖平面几何的任何数学教科书。
三角形是具有3个顶点v0，v，v2和3个边v0v，vv2，v2v0的多边形。你可以在左边看到一个精细的标本。退化三角形是三个顶点共线的三角形，即三个定点都落在同一行上（或者它们甚至都可能是相同的点）。任何三角形都位于一个平面上，对于所有非退化三角形而言，该平面是唯一确定的。这在任何维度上都保持不变，但在0D或D中会有些空洞，其中任何3个顶点将是共线的。
让我们暂时将讨论限制在2D中，像任何非自相交的平面多边形一样，三角形将平面分成两个区域：内部区域是有限的，而外部区域则不是。这两个区域由三角形的边界分开，三角形由三个边组成。为了光栅化三角形，我们基本上只需要查询通常直接对应于像素网格或以其他规则模式排列的一堆点，并确定它们是否在里面。由于这是一个二进制结果，我们的查询提供了一个三元回答（外部，边上，内部），我们需要定义边上的点如何被处理。有多种方法可以做到这一点，我将在关于实际三角形光栅化的文章中介绍它们。由于三角形总是位于一个平面上，通过在三角形所在的平面上工作（或者在三角形的平面中，如果它是退化的），很容易将这些定义扩展到更高的维度。
最后，三角形总是凸多边形：对于三角形内的任何两个点，连接它们的线也完全在三角形内。三角形是凸多边形这个结果是相当重要的：在平面上，具有n个边的凸多边形的内部可以总是写为n个半空间的相交。这个事实本身就足以编写一个三角形光栅化器，但如果你以前没有这样做过，你可能会想知道我在说什么。所以让我们退一步，花几秒钟谈论一下这种几何情况。
带方向的边
花时间考虑一下，上图中的边v0v。边本身是一个线段。对应的直线将平面划分成两半（我前面提到的半空间）：“左”侧和“右”侧。在上方的图像“左侧”被渲染出来。如果我们选择的边恰好是水平的（如果它们是垂直堆叠的话，这两个半空间哪一个是“左”）呢？所以我们要把所有相对于边的东西都放在一边，而不是像我们绘制的图片那样：想象你正在边上行走，从v0走向v。然后，我们将把你的左边的所有东西（如果你正在看着v）称为“正”的半空间，在右边的一切，就是“负”的半空间。最后，在你面前或者你身后的点（也就是落在这一点上的点）都不属于半空间。
现在，如果我们将相同的结构应用于其他两个边并将得到的结果全部叠加在一起，我们将获得这么一个图像：
让我们看下所有的颜色（向盲人道歉）：
l绿色区域在vv2和v2v0的正半空间（我将用“内部”代替正半空间），但在v0v的外部。
l青色区域在v2v0的内部，但在其他两个边的外部。
l蓝色在v0v和v2v0的内部。
l洋红色在v0v的内部-所有这些都在我们上面看到的左边区域。
l红色在v0v和vv2的内部。
l黄色在vv2的内部。
l最后，灰色区域在所有三个边的内部，这正是我们的三角形。
所以让我们先来看看我之前评论的“3个半空间相交”的照片。这意味着我们如果需要弄清楚一个点是否在三角形的内部，就是去弄清楚它是否处于三个正的半空间，而这一点相当容易。也就是说，假设这一点存在-如果v2已经在v0v的右侧而不是在左侧，或者说其他任何边发生同样的事情，会发生什么？我们会在一分钟后开始说这个事情，但让我们先来看看我们如何确定一个点是否在正半空间中。
面积，长度和方向
如果我们有所有涉及点的坐标，那么答案就是：行列式。不是任何一个老的行列式，给定三点a，b和c，我们想计算行列式
很显然，如果这个表达式是正的，那么c位于有向边ab的左边（即三角形abc逆时针渲染），那么我们就可以开始光栅化三角形。。。。
等等，这是什么？
对不起，这是一个经常被抱怨的问题。很多文章喜欢只是弹出这些表达而对你没有太多的解释。对于论文来说，这样很好，在那里你可以期待你的观众已经知道了这一点，但是即使是很多介绍性的文章也不耐烦对这些事情做一定的解释，这惹恼了我，因为这并不困难，虽然也不是很明显。
所以我们来看一下这个公司吧。首先，注意第一个表达式如何简单地将三个顶点通过附加的放在一个行列式之中–是的，这些顶点实际上是齐次坐标，谢谢你的注意。虽然我们不会在这里使用，但这值得一提。第二，因为我们只是使用顶点坐标作为列，这应该立即显而易见的是，这个表达式对于a，b，c的所有可能的排序都是相同的（这是一个行列式的特性），只有正负不一致。特别是，如果我们在a，b，c中插入顶点坐标，对于所有三个循环排列（v0vv2，vv2v0和v2v0v）总是获得相同的值（这次连符号也包括了）。这反过来意味着我们计算的“边缘性”对于所有三个边将是相同的，这就回答了我们上面的一个问题。
接下来，请注意，我们可以将第一个形式（3×3行列式）转换为第二个形式，通过从另外两列中减去第一个列，然后相对于第三行展开行列式，这应该可以使它减少一些神秘感。还有一个非常好的方式来从几何上理解这个公式，但我不会在这里解释-也许换一个时间我会解释。无论如何，现在我们知道如何推导出2×2的形式，让我们依次看看。使用任意二维向量p和q，行列式
给出由边向量p和q组成的平行四边形的（有符号）面积（我假设你知道这一点-这是一个标准的线性代数事实，证明它不在本文的范围内）。类似地，向量p，q，r的3×3行列式给出由三个向量组成的平行六面体的有符号体积，并且在较高维度中，n个向量的n×n行列式给出对应的n维超平行体的有符号n维体积，但我有点跑题了。
所以，考虑到这一点，我们首先来看看我们的三角形，并尝试计算Orient2D（v0，v，v2）。这应该有助于我们确定这个三角形是否是逆时针旋转（也就是说v2是否位于边v0v的左侧）。上面的表达式告诉我们计算行列式
这应该能告诉我们由边v0v和边v0v2组成的平行四边形的有符号面积。让我们把这个事情绘制在三角形之上，这样我们可以看到发生了什么：
现在，有两件事情值得一提：首先，如果我们要交换v和v2，我们将得到相同的边向量，只是在相反的顺序-我们交换行列式的两列，会翻转符号位，但留下的绝对值不变。现在，我们原始的三角形是按逆时针旋转：第三个顶点v2位于第一个边v0v的左边。如果我们交换v和v2，我们得到相同的三角形，只有这个时候第三个顶点（现在的v）在第一个边（现在是v0v2）的右边。更准确地说，如果我们第一次三角形是逆时针方向的，则行列式的符号是正的，如果我们第一次三角形是顺时针方向的，则行列式的符号是负的。如果结果为零，则所有三个顶点都是共线的，所以三角形是退化的–这个信息也是有用的。
第二件事是我们现在看到的平行四边形的面积很明显是我们开始时候三角形的面积的两倍。这不是偶然的-构造平行四边形的第四个顶点会产生与第一个三角形面积相同的另外一个三角形，所以这两个三角形具有相同的面积，因此平行四边形的面积是我们开始时候的三角形的面积的两倍。这给出了计算三角形面积的标准行列式：
计算三角形面积的另外一个标准公式是，其中b是三角形底边的长度（等于它其中一个边的长度），h是相应的高度（=通过顶点B的垂直线段的长度）。事实上，这个公式的证明使用了我们刚才看到的相同的平行四边形。比较这两个表达式，我们注意到我们的有符号面积计算可以写成
其中h（v2，v0v）表示的是v2向边v0v做垂线的有符号高度-这不是标准符号，但是请忍耐我一分钟。这里有一点要注意的是，这个有符号面积计算的值正比于v2向边v0v做垂线的有符号高度。这在三角形上起作用不应该是令人惊讶的-举个简单的例子来说，对于矩形也是如此-但是这里应该明确地说明这一点，因为我们将进行大量的有符号面积计算来确定什么是有效的有符号距离。所以重要的是要知道它们是等价的。
边的函数
现在，让我们回到我们使用这些行列式表达式的最初用途：弄清楚一个点在一个边的哪一边。所以让我们选择一个任意点p，看看它与边v0v的关系。把它扔到我们的行列式表达式中：
如果我们重新排列这些项，重新组合和简化我们得到。。。。
这就是我所说的边v0v的函数。如你所见，如果我们保持顶点位置不变，这只是p上的一个仿射函数。对其他两个边做一样的操作，我们得到了剩下两个边的函数：
如果所有三个表达式都是正的，那么p点在三角形的内部，假设三角形是逆时针旋转的，我将在本文的剩余部分继续使用这个假设。如果三角形是顺时针旋转的，则在开始测试之前只需交换两个顶点。现在，这些是正常的线性函数，但是从它们的推导和我们前面看到的行列式特征来看，我们知道它们实际上也是计算对应的平行四边形的有符号面积，这反过来是相应三角形的有符号面积的两倍。让我们在三角形内选一点，画出相应的图：
我们原来的三角形被划分成三个较小的三角形，它们完全覆盖原始三角形的面积。由于p在三角形的里面，所以这些三角形都是对自己逆时针渲染的：它们必须是，因为这些三角形具有对应于边函数的有符号区域，并且我们知道它们中的所有三个表达式都是正的，因为p在内部。所以这一切都很整洁。
但等等，还有更多！由于这些三角形相加等于原始三角形的面积，所以三个对应的边的函数应该加起是完整三角形v0vv2的有符号面积的两倍（之所以是两倍，是因为三角形面积具有/2因子，而边的函数没有）。或者，作为公式：
如果你查看包含px和py的边的函数中的项，这不应该是令人惊讶的：把px的三个项加起来会得到（v0y-vy+vy-v2y+v2y-v0y）=0，对py的三个项也能得到类似的结果。所以是的，这三个项的总和是不变的。现在，看下线性代数术语，这不应该是一个惊喜：我们有3个仿射函数只有2个变量-它们不会是独立的。但它仍然有助于理解基础几何。
为什么有符号的面积是个好主意
请注意，关于边的函数的总和等于三角形面积两倍的说法对于任何点都成立，而不仅仅是三角形内部的点。现在还不清楚当p在三角形外部的时候该如何工作，所以让我们来看看：
这一次，三角形实际上是相互重叠的：两个三角形v0vp和vv2p按照逆时针旋转，并且具有与之前相同的正面积，并且它们也延伸到原始三角形的区域之外。但是第三个（红色）三角形v2v0p按照顺时针旋转并具有负的面积，恰好抵消了两个其他三角形延伸到原始三角形v0vv2之外的的部分。所以这一切都行之有效。如果你以前没有看到过，这种抵消是一个重要的技巧，可以用来简化大量的东西，否则会非常的麻烦。举个简单的例子来说，它可以用于计算任意多边形的面积，无论多么复杂，只需将一组三角形的面积相加，每个边一个三角形。只使用面积为正的三角形进行相同操作的时候，首先需要对多边形进行三角测量，这是一个更加棘手的问题，但是我再次跑题了。
那么重心坐标现在在哪里了？
现在，这篇博客文章被称为“重心的阴谋”，但奇怪的是，我们似乎还没有看到一个重心坐标。这是怎么了？那么我们先来看看什么是重心坐标：在一个三角形中，一个点的重心坐标是数字的三元组（w0，w，w2），作为相应顶点的“权重”。所以三个坐标三元组（,0,0），（0,,0）和（0,0,）分别对应于v0，v和v2。更一般来说，我们允许权重是任何东西（除了全零），并且在最后除以它们的和。那么p的重心坐标三元组是（w0，w，w2）的话，可以得到：
由于我们除以它们的总和，它们有一个独特的放缩-就像你作为图形程序员所熟悉的齐次坐标一样。这是我们第二次在这篇文章中不小心碰到齐次坐标了。这不是意外。重心坐标是一种齐次坐标，事实上两者都是由M?bius于年在同一篇论文中引入的。我试图在这篇文章中坚持使用平面几何，因为它更容易绘制（并且如果你还没有习惯在投影几何中进行思考的话，这也更容易理解）。这意味着在这篇文章中，不怎么涉及齐次坐标的角度，但是相信我，我们在这里做的一切都可以在投影空间中正常工作。而且你已经看到了几何派生的一切，所以如果我们想的话，我们甚至可以做到完全与坐标无关（如果你不喜欢代数的话，能找到一个方法来知道如何避免使用代数总是很好的）。
但是回到重心坐标：我们已经知道我们边的函数的测量（有符号）面积，并且它们在它们各自的边上为零。那么v0和v都在边v0v上（这是很显然的事情），因此.
我们也已经知道，如果我们将第三个顶点插入到边的函数中，我们可以得到整个三角形有符号面积的两倍：.
可以在其他两个边上使用相同的技巧：每当涉及三个顶点的时候，我们得到整个三角形有符号面积的两倍，否则结果为零。我们已经知道他们是仿射函数。在这一点上，事情应该已经看起来很可疑，所以我要去破除这个疑虑：让我们做这样的设置
没错，在p处评估的三个边的函数给出了p的重心坐标，被归一化，所以它们的和是三角形面积的两倍。请注意，重心的权重总是来自我们正在谈论的边相对的顶点。现在你已经看到了面积图，应该清楚为什么：边函数F2(p)给出的是三角形vv2p的缩放面积，p离边vv2越远，三角形面积越大。在极端情况下，当p在v0的时候，它覆盖了我们原始三角形的全部面积。所以这一切都是有道理的。我们还要定义重心坐标的归一化版本，其总和总是为：
所以现在秘密出来了-我们一直在看的汗劣势，有符号面积和距离，甚至是边的函数-一直是重心坐标。它把所有都连在了一起！
重心插值
有了它，我们有了我们需要的所有数学内容，但我还想提醒下它还有更多的应用：如前所述，重心坐标是各个顶点的有效权重。定义使用这个来计算位置，但是我们可以使用相同的权重来插值应该在三角形上进行线性变化的其他东西，举个简单的例子来说，顶点属性。
现在，对于我们要查看的深度缓冲区光栅化器，我们只需要插入一个东西，这就是深度。如果我们在顶点有z值z0，z，z2，我们可以通过计算来确定内插深度
如果我们已经拥有代入p的边函数的值，那么它们是非常简单的，并且工作正常，而代价就是三次乘法和两次加法。但请记住，我们将整个事情归一化，所以lambda总和为。这意味着我们可以用其他两个项表达任任意ambda：
将其插入上面的表达式并简化，我们得到：
zi之间的差异在三角形上是不变的，所以我们可以只计算一次。这给了我们一个替代重心内插值的表达式，它使用两个乘法和两个加法，它们允许被执行为两个融合后的乘法加法。现在我们在本系列的上一篇文章中认识到一件事情，那就是计数操作往往是处理性能问题的错误方法，但是这一简化方法将会在内部循环中使用，指令执行的数目会成为这个方法的瓶颈。而重要的是，这也是图形处理器通常用于顶点属性插值的表达式。在某些时候，我可能会更多地谈论这个问题，但是这篇文章已经有足够多的内容了。那么让我们在下一篇文章中再见，那时候我们会学习如何把所有这一切变成一个光栅化器。
原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。
----------------------
今日推荐
小白慎入！资深大牛谈PBR纹理变换
《龙之谷》手游优化实战：内存VS帧率
添加小编白点风北京去哪家医院看白癜风