第二章：三角面片及其填充

本文是《从0开始图形学》笔记的第二章，主要说明模型的一般构成以及如何查找模型的有效范围，涉及三角面片的填充以及向量的叉乘计算。

概念解说

上一节中，我们画出了箱子的顶点和边缘线，箱子还只是一个骨架而已。这一节我们来将箱子的“皮”画出来，让箱子的形体更完整。

首先，我们需要将箱子的面由四边形进一步切割成三角形，并进行填充。为什么要将其切割成三角形？原因大概有这么几个

（1）三角形才是最简单的多边形，任何多边形都可以用三角形拼凑出来，或者说任何多边形都可以切割成多个三角形;

（2）三角形能保证其面上所有的点都在同一个平面，其他形状就没有这个特性，例如将一张A4纸沿着对角线对折，它还是只有4条边，但是它就变成了两个三角面，而且这两个三角面不在同一个平面上；

（3）绝大多数标准的3D数据都是由3角形构成，而且很多加载数据的软件一般都会提供将数据3角形化的接口！

数学计算

下一步如何填充三角形呢？最关键的点就是如何判别一个点是否在一个3角形中。

如下图，三角形ABC，任意点D，如果D在三角形内，则按顺序（如A->B->C）有：向量AB旋转到向量AD为逆时针，向量BC旋转到向量BD为逆时针，向量CA旋转到向量CD为逆时针，也就是说三个旋转的方向是一致的！而这个特性在数学上刚好有对应的表示方式----向量的叉乘

向量的叉乘，简单来说就是两个向量 $a\vec{}$ 、 $b\vec{}$ 叉乘结果会生成另外一个向量 $c\vec{}$ ，那么 $c\vec{}$ 垂直于 $a\vec{}$ 和 $b\vec{}$ 组成的平面，而且 $c\vec{}$ 的方向和 $a\vec{}$ 旋转到 $b\vec{}$ 的方向刚好对应！而且因为我们所有的操作都是在XY平面上，所以这里的 $c\vec{}$ 得x和y分量都为0，其z分量就刚好表示这个方向。

那么，向量的叉乘要怎么数学运算呢？很简单，假设向量AB为 [x1,y1,z1]，向量AD为 [x2,y2,z2]，那么根据公式，其叉乘的结果为 [y1*z2-y2*z1, z1*x2-z2*x1, x1*y2-x2*y1]。因为结果在2D的屏幕，所以z1和z2都为0，而结果向量中的z值（即x1*y2-x2*y1）的正负即代表方向。

C核心代码实现

代码上，首先，我们更改一下箱子数据，将其面数据从6个4边型改成12个3角形

int _planes[12][3] =      // 面的数据,12个3角形
{{0, 1, 2},     // 每个面3个角的顶点对应于索引值{2, 3, 0},{4, 5, 6},{6, 7, 4},{1, 5, 6},{6, 2, 1},{3, 2, 6},{6, 7, 3},{0, 4, 7},{7, 3, 0},{0, 1, 5},{5, 4, 0},
};

然后，在CGRender()函数中，根据上述的原理将每个在三角面片中的像素改颜色即可

void CGRender()
{float v1[3], v2[3];int bound[4];     // 每个三角面片的范围minx, miny, maxx maxy，用于减少计算量float crossZval[3];for (int i = 0; i < 12; ++i)    // 遍历箱子的12个三角面{// 首先获取三角面片的范围（外包围框）bound[0] = bound[1] = 1e6;bound[2] = bound[3] = -1e6;for (int j = 0; j < 3; ++j){if (bound[0] > _points[_planes[i][j]][0]) bound[0] = _points[_planes[i][j]][0];if (bound[1] > _points[_planes[i][j]][1]) bound[1] = _points[_planes[i][j]][1];if (bound[2] < _points[_planes[i][j]][0]) bound[2] = _points[_planes[i][j]][0];if (bound[3] < _points[_planes[i][j]][1]) bound[3] = _points[_planes[i][j]][1];}// 遍历包围框,以确定这些像素点在三角形的内外for (int y = bound[1]; y <= bound[3]; ++y){for (int x = bound[0]; x <= bound[2]; ++x){for (int j = 0; j < 3; ++j){// 通过点坐标的相减得到三角形边的向量v1v1[0] = _points[_planes[i][(j + 1) % 3]][0] - _points[_planes[i][j]][0];v1[1] = _points[_planes[i][(j + 1) % 3]][1] - _points[_planes[i][j]][1];// v1[2] = _points[_planes[i][(j + 1) % 3]][2] - _points[_planes[i][j]][2]; Z值用不上// 获取当前点和三角形顶点构成的向量v2v2[0] = x - _points[_planes[i][j]][0];v2[1] = y - _points[_planes[i][j]][1];// 计算v1和v2叉乘结果的Z值crossZval[j] = v1[0] * v2[1] - v1[1] * v2[0];}// 判断3个叉乘结果的方向（即Z值的正负）是否一样if ((crossZval[0] > 0 && crossZval[1] > 0 && crossZval[2] > 0)|| (crossZval[0] < 0 && crossZval[1] < 0 && crossZval[2] < 0)){_rstImage[y][x][1] = 255;       // 将其绿色通道值拉满，以显示出来}}}}
}