共计 8080 个字符，预计需要花费 21 分钟才能阅读完成。
后面两天画了点和线，明天咱们来画一个最简略也是最弱小的面——三角形。
本文次要解说三角形绘制算法的推导和思路（只波及到一点点的向量常识），最初会给出代码实现，大家释怀的看上来就好。
本文源码 ????：toyRenderer-day3-draw-triangle
1. 如何画一个三角形？
在正式开始这一小节前，咱们先想一下如何利用上一节的画线算法绘制一个 实心的 三角形。
假如当初立体内有三个不共线的点组成一个三角形，咱们能够利用上一节的直线算法轻易的连贯三角形的三条边，这时候咱们会生成一个 空心的 、 关闭的 三角形。
那么这时候问题就转换为，如何把这个空心的三角形变为一个 实心 的三角形？
我想大家这时候曾经有思路了，就是 一行一行地扫描像素，把两个边界点之间的像素全副涂满上色就能够了。
这个办法必定是能够的，然而实现不是很优雅，也不是业内的支流实现形式。因为基于行扫描的算法不是本文的重点，所以具体的推导和代码实现就不提供了，感兴趣的同学能够本人尝试实现一下。
2. 利用向量叉乘画三角形
开始本节前先简略温习一下向量叉乘的几何意义。
2.1 数学推导
在三维空间中，两个三维向量 $\mathbf {a}$ 和 $\mathbf {b}$ 做叉乘，会失去一个和已知两个向量 垂直 的新向量 $\mathbf {a} \times \mathbf {b}$。
既然叉乘产生的是一个新向量，那么它必定有个方向，咱们个别用右手定则来判断：将右手食指指向 $\mathbf {a}$ 的方向、中指指向 $\mathbf {b}$ 的方向，则此时拇指的方向即为 $\mathbf {a} \times \mathbf {b}$ 的方向。
综上所述，咱们能够对向量叉乘做一个谨严的定义：
$${\displaystyle \mathbf {a} \times \mathbf {b} =\|\mathbf {a} \|\|\mathbf {b} \|\sin(\theta)\ \mathbf {n} }$$
其中 $\theta$ 示意 $\mathbf {a}$ 和 $\mathbf {b}$ 在它们所定义的立体上的夹角（$0^{\circ}\leq \theta \leq 180^{\circ}$）。${\displaystyle \|\mathbf {a} \|}$ 和 $\displaystyle \|\mathbf {b} \|$ 是向量 $\mathbf {a}$ 和 $\mathbf {b}$ 的模长，而 $\mathbf{n}$ 则是一个与 $\mathbf {a}$、$\mathbf {b}$ 所形成的立体垂直的单位向量，方向由右手定则决定。
有下面的实践，咱们就能够判断两个向量的绝对地位：
- $\mathbf {a}$ 向量叉乘 $\mathbf {b}$ 向量，如果值为 正，则示意 $\mathbf {b}$ 向量在 $\mathbf {a}$ 向量 左侧
- $\mathbf {a}$ 向量叉乘 $\mathbf {b}$ 向量，如果值为 负，则示意 $\mathbf {b}$ 向量在 $\mathbf {a}$ 向量 右侧
- $\mathbf {a}$ 向量叉乘 $\mathbf {b}$ 向量，如果值为 零，则示意 $\mathbf {b}$ 向量与 $\mathbf {a}$ 向量 共线
会判断两条线的绝对地位了，咱们能够做个实践迁徙，利用向量叉乘判断点和三角形的地位关系。
例如上面这里例子，对于三角形 $\Delta ABC$ 来说，把三条边看作 $\overrightarrow{A B}$、$\overrightarrow{B C}$、$\overrightarrow{C A}$ 三条首尾相连的向量，立体内有一个点 $P$，咱们通过向量叉乘来判断绝对地位：
- $\overrightarrow{A B} \times \overrightarrow{A P}$，值为 正，故 $P$ 在 $AB$ 左侧
- $\overrightarrow{B C} \times \overrightarrow{B P}$，值为 正，故 $P$ 在 $BC$ 左侧
- $\overrightarrow{C A} \times \overrightarrow{C P}$，值为 正，故 $P$ 在 $AC$ 左侧
综合以上三个限度条件，咱们能够判断 $P$ 在 $\Delta ABC$ 内。
如果下面三个计算中有值为负的状况，阐明 $P$ 在三角形外；如果有值为 0 的状况，阐明 $P$ 在三角形的边或顶点上。
2.2 代码实现
实践根底温习完了，咱们就能够写代码了。代码实现相当简略，咱们构建一个函数 crossProduct，传入三角形的三个顶点战争面上的任意一点 $P$，而后依据四个顶点构建出向量计算叉乘就能够了：
// 利用叉乘判断是否在三角形外部
Vec3i crossProduct(Vec2i *pts, Vec2i P) {
// 构建出三角形 ABC 三条边的向量
Vec2i AB(pts[1].x - pts[0].x, pts[1].y - pts[0].y);
Vec2i BC(pts[2].x - pts[1].x, pts[2].y - pts[1].y);
Vec2i CA(pts[0].x - pts[2].x, pts[0].y - pts[2].y);
// 三角形三个顶点和 P 链接造成的向量
Vec2i AP(P.x - pts[0].x, P.y - pts[0].y);
Vec2i BP(P.x - pts[1].x, P.y - pts[1].y);
Vec2i CP(P.x - pts[2].x, P.y - pts[2].y);
return Vec3i(AB^AP, BC^BP, CA^CP);
}代码十分的简略，咱们跑一个简略的例子验证一下：
void drawSingleTriangle() {
// 图片的宽高
int width = 200;
int height = 200;
TGAImage frame(width, height, TGAImage::RGB);
Vec2i pts[3] = {Vec2i(10, 10), Vec2i(150, 30), Vec2i(70, 160)};
Vec2i P;
// 遍历图片中的所有像素
for (P.x = 0; P.x <= width - 1; P.x++) {for (P.y = 0; P.y <= height - 1; P.y++) {Vec3i bc_screen = crossProduct(pts, P);
// bc_screen 某个重量小于 0 则示意此点在三角形外（认为边也是三角形的一部分）if (bc_screen.x<0 || bc_screen.y<0 || bc_screen.z<0) {continue;}
image.set(P.x, P.y, color);
}
}
frame.flip_vertically();
frame.write_tga_file("output/day03_cross_product_triangle.tga");
}看输入图像，咱们曾经胜利绘制了一个三角形：
触不迭防的安利：大家能够看我头像关注????️号「卤蛋实验室」，后盾回复「图形学」获取经典教材《虎书 4》和《Real Time Rendering 4》
3. 利用三角形重心坐标画三角形
本大节介绍一个更通用的定理——重心坐标（Barycentric Coordinate）。其实重心坐标用来画三角形还是有些大材小用了，他最重要的使用其实是用来做 插值，不过插值的具体使用咱们后续章节再探讨，明天咱们看看重心坐标的推导和代码实现。
3.1 数学推导
咱们临时只思考二维立体的三角形。对于一个三角形 $\Delta ABC$ 来说，假如立体内有一个点 $P$，很显然，$\overrightarrow{A P}$，$\overrightarrow{A B}$，$\overrightarrow{A C}$ 向量都是线性相关的，也就是说，能够用下式示意 $\overrightarrow{A P}$：
$$\overrightarrow{A P}=u \overrightarrow{A B}+v \overrightarrow{A C}$$
咱们把这个三角形放在一个笛卡尔坐标系下，咱们就能够这样示意：
$$A-P=u(A-B)+v(A-C)$$
把地位挪一下，合并同类项后，$P$ 点的地位能够示意为下式：
$$P=(1-u-v) A+u B+v C$$
联合几何意义，咱们很容易推出：
- 当 $(1 – u – v)$、$u$ 和 $v$ 均 大于 0 小于 1 时，P 位于三角形 外部
- 有 一个 重量等于 0 时，P 在三角形 边上
- 有 两个 变量等于 0 时，P 在某个 顶点 上
再对第一个式子做一下变形，能够失去下式：
$$u \overrightarrow{A B}+v \overrightarrow{A C}+\overrightarrow{P A}=0$$
因为三角形位于笛卡尔坐标系内，咱们能够把下面的式子沿 $x$ 和 $y$ 轴拆分为两个式子，他们和上式是等价的：
$$\left\{\begin{array}{l}u \overrightarrow{A B}_{x}+v \overrightarrow{A C}_{x}+\overrightarrow{P A}_{x}=0 \\ u \overrightarrow{A B}_{y}+v \overrightarrow{A C}_{y}+\overrightarrow{P A}_{y}=0\end{array}\right.$$
察看这个式子，咱们能够转换为矩阵乘法的模式：
$$\left[\begin{array}{lll}u & v & 1\end{array}\right]\left[\begin{array}{l}\overrightarrow{A B}_{x} \\ \overrightarrow{A C}_{x} \\ \overrightarrow{P A}_{x}\end{array}\right]=0$$
$$\left[\begin{array}{lll}u & v & 1\end{array}\right]\left[\begin{array}{l}\overrightarrow{A B}_{y} \\ \overrightarrow{A C}_{y} \\ \overrightarrow{P A}_{y}\end{array}\right]=0$$
察看下面的式子，咱们要寻找一个向量 $[\begin{array}{lll}u & v & 1\end{array}]$，它要与向量 $[\begin{array}{l}\overrightarrow{A B}_{x} \ \overrightarrow{A C}_{x} \ \overrightarrow{P A}_{x}\end{array}]$ 和 $[\begin{array}{l}\overrightarrow{A B}_{y} \ \overrightarrow{A C}_{y} \ \overrightarrow{P A}_{y}\end{array}]$ 同时点乘为 0。
略微思考一下，这不就意味着向量 $[\begin{array}{lll}u & v & 1\end{array}]$ 同时垂直 于向量 $[\begin{array}{l}\overrightarrow{A B}_{x} \ \overrightarrow{A C}_{x} \ \overrightarrow{P A}_{x}\end{array}]$ 和 $[\begin{array}{l}\overrightarrow{A B}_{y} \ \overrightarrow{A C}_{y} \ \overrightarrow{P A}_{y}\end{array}]$ 吗！
所以咱们间接求 后两个向量的叉乘 就能够求出向量 $[\begin{array}{lll}u & v & 1\end{array}]$ 了。
后两个向量做叉乘的时候有个小细节须要留神一下，向量叉乘的 间接后果（先假如后果为 $[\begin{array}{lll}e & f & g\end{array}]$）个别只是和 $[\begin{array}{lll}u & v & 1\end{array}]$ 平行，想要正确求出 $u$ 和 $v$ 的值，咱们须要对向量 $[\begin{array}{lll}e & f & g\end{array}]$ 除以 $g$，也就是说 $u = e/g$，$v = f/g$，$1 = g/g$。
这个时候问题就来了，下面的除法成立，必须要建设在 $g$ 不为 0 的根底上，那么咱们就要钻研一下 $g$ 为 0 的数学含意了。
依据向量的叉乘公式：
$$\mathbf{u} \times \mathbf{v}=\left|\begin{array}{cc}u_{2} & u_{3} \\ v_{2} & v_{3}\end{array}\right| \mathbf{i}-\left|\begin{array}{cc}u_{1} & u_{3} \\ v_{1} & v_{3}\end{array}\right| \mathbf{j}+\left|\begin{array}{cc}u_{1} & u_{2} \\ v_{1} & v_{2}\end{array}\right| \mathbf{k}$$
$g$ 向量能够示意为这样的行列式：
$$\left|\begin{array}{ll}\overrightarrow{A B}_{x} & \overrightarrow{A C}_{x} \\ \overrightarrow{A B}_{y} & \overrightarrow{A C}_{y}\end{array}\right|$$
如果这时候的叉乘后果为 0，把这个行列式 从列向量的视角看 ，就相当于 $\overrightarrow{A B}$ 和 $\overrightarrow{A C}$ 向量叉乘后果为 0，也就是说 $\overrightarrow{A B}$ 和 $\overrightarrow{A C}$ 向量共线。这时候三角形 $\Delta ABC$ 就 进化为一条线段。
对于咱们当初利用场景来说，只有检测到 $g$ 为 0，就意味着这个三角形进化为一条线段了，咱们间接舍弃掉它就好了，对最初的后果也没有影响。
3.2 代码实现
依据下面的公式推导，咱们能够间接写出基于三角形重心坐标的绘制算法，思路理清了，代码实现就十分的简略：
// 利用重心坐标判断点是否在三角形外部
Vec3f barycentric(Vec2i *pts, Vec2i P) {Vec3i x(pts[1].x - pts[0].x, pts[2].x - pts[0].x, pts[0].x - P.x);
Vec3i y(pts[1].y - pts[0].y, pts[2].y - pts[0].y, pts[0].y - P.y);
// u 向量和 x y 向量的点积为 0，所以 x y 向量叉乘能够失去 u 向量
Vec3i u = x^y;
// 因为 A, B, C, P 的坐标都是 int 类型，所以 u.z 必然是 int 类型，取值范畴为 ..., -2, -1, 0, 1, 2, ...
// 所以 u.z 绝对值小于 1 意味着三角形进化了，间接舍弃
if(std::abs(u.z) < 1) {return Vec3f(-1, 1, 1);
}
return Vec3f(1.f- (u.x+u.y) / (float)u.z, u.x / (float)u.z, u.y / (float)u.z);
}用下面的算法画个三角形验证一下，很完满：
4. 绘制模型
算法写好了，咱们就要投入到理论利用中了，昨天里咱们画了个三维模型的线框图，明天咱们就个这个模型上色。
4.1 随机着色
为了辨别每个三角形，咱们随机给三角形上不同的色：
triangle(screen_coords, frame, TGAColor(rand() % 255, rand() % 255, rand() % 255, 255));这里还有个对于性能的小细节。这次咱们绘制的图像大小为 800*800，如果依照之前的算法，每次画三角形，都要把所有像素遍历一遍，这个模型大略有 2000 个三角形，那就是要循环 2000*800*800 即 12.8 亿 次！
这个量级是很恐怖的，其中很多的运算都是不必要的，比如说下图，咱们其实只有循环由三个顶点计算出的 红色突围盒里的像素 就能够了，不须要计算图片内的所有像素：
所以咱们要在遍历像素前加先求一遍三角形突围盒的边界，正式画三角形时只有遍历突围盒内的像素就能够了：
// 定义突围盒
Vec2i boxmin(image.get_width() - 1, image.get_height() - 1);
Vec2i boxmax(0, 0);
// 图片的边界
Vec2i clamp(image.get_width() - 1, image.get_height() - 1);
// 查找突围盒边界
for (int i = 0; i < 3; i++) {
// 第一层循环，遍历三角形的三个顶点
for (int j = 0; j < 2; j++) {
// 第二层循环，依据顶点数值放大突围盒的范畴
boxmin.x = std::max(0, std::min(boxmin.x, pts[i].x));
boxmin.y = std::max(0, std::min(boxmin.y, pts[i].y));
boxmax.x = std::min(clamp.x, std::max(boxmax.x, pts[i].x));
boxmax.y = std::min(clamp.y, std::max(boxmax.y, pts[i].y));
}
}最初咱们绘制出的后果就是这样的，看着还是有些酷炫的：
4.2 简略的光照着色
随机着色的益处是能够很分明的体现出模型各个三角形的轮廓，然而也失去了模型的辨识度，很多细节都失落了。
咱们在这里引入一个非常简单的光照模型，认为 单位面积上接管到的光，和立体法线与光照方向的余弦值成正比：
所以着色的思路就很清晰了：
- 咱们要先定义一个三维空间里的 光照方向（向量），而后计算三维空间里各个三角形的 法线（向量）
- 两个向量 归一化 后，而后计算这两个向量的点乘，会失去一个值
- 这个值小于 0，阐明光在三角形的另一侧，从物理上看是照耀不到三角形外表的，所以间接舍弃此三角形
- 这个值大于 0，值 越大 ，阐明单位面积上接管到的光 越多 ，三角形 越亮
把下面的思路翻译成代码就是这样的：
// 这个是用一个模仿光照对三角形进行着色
Vec3f light_dir(0, 0, -1); // 假如光是垂直屏幕的
for (int i = 0; i < model->nfaces(); i++) {std::vector<int> face = model->face(i);
Vec2i screen_coords[3];
Vec3f world_coords[3];
// 计算世界坐标和屏幕坐标
for (int j = 0; j < 3; j++) {Vec3f v = model->vert(face[j]);
// 投影为正交投影，而且只做了个简略的视口变换
screen_coords[j] = Vec2i((v.x + 1.) * width / 2., (v.y + 1.) * height / 2.);
world_coords[j] = v;
}
// 计算世界坐标中某个三角形的法线（法线 = 三角形任意两条边做叉乘）Vec3f n = (world_coords[2] - world_coords[0]) ^ (world_coords[1] - world_coords[0]);
n.normalize(); // 对 n 做归一化解决
// 三角形法线和光照方向做点乘，点乘值大于 0，阐明法线方向和光照方向在同一侧
// 值越大，阐明越多的光照射到三角形上，色彩越白
float intensity = n * light_dir;
if (intensity > 0) {triangle(screen_coords, frame, TGAColor(intensity * 255, intensity * 255, intensity * 255, 255));
}
}最初生成的图片就是这样的：
到这里渲染出的图像就有些人样了，然而大家应该也发现了，上图的嘴巴和眼睛处看上去怪怪的。这里确实是有问题，因为它把背地的三角形渲染进去了，要想解决这个问题，就要引入一个新的概念——z-buffer。
举荐间接浏览原文，更新更及时，浏览体验更佳
如果你喜爱我的文章，心愿点赞???? 珍藏 ???? 在看 ???? 三连反对一下！！！谢谢你，这对我真的很重要！
欢送大家关注我的微信公众号：卤蛋实验室，目前专一前端技术，对图形学也有一些渺小钻研。
