形学 光栅化详解（Rasterization）

计算机的屏幕是二维的平面坐标，以左上角为原点，x轴向右增加，y轴向下增加。

在3D图形学中，物体是3维的，拥有X, Y, Z三个坐标，并且拥有R, G, B三种颜色，alpha透明度，U, V贴图坐标，N法线。

三维物体在二维屏幕上的显示，大致分为以下几步：

在第二步中，我们计算出了3D模型每个顶点的颜色，这个是基于3维坐标的，顶点的三维坐标可以是 小数 。

但在屏幕渲染时，屏幕是只有X,Y二维的，并且其像素点坐标都是 整数 。1920×1080的屏幕只有1920×1080=2073600个像素点。所以光栅化的连点描边是一个近似过程。

光栅化主要有以下几步：

那么，假设我们已经得到了3个顶点的坐标，并且已知这个三角形是红色。

v1 (-1.5, 1.5, 1.5)

v2 (1.5, 1.5, 1.5)

v3 (0.2, 0.2, 0.2)

如何判断屏幕的哪些像素点在该三角形内部？

主流的算法有两种：

1.LEE（Linear Expression Evaluation）

2.Scan Line

本期只讲LEE，因为Scan Line我没有亲自搞过。

LEE大致原理如下：

需要注意的地方：

如何定义左边和上边?

由于重画这个问题只出现在边上，对于三角形内部的像素点，都是只画一次的，所以不用考虑内部点，只考虑三条边上的点。

如图所示：

1）假定三角形v1v2v3是这样的，我们当前要上色的像素点为P1（红色），落到了v1v3这条边上，那么就取不在这条边上的顶点v2，计算过v2的水平线与v1v3的交点R1，如果R1在v2的右侧，即R1.x > v2.x，那么说明P1是落在了 右侧 的边，所以 不画

2）假定我们当前要上色的像素点为P2（绿色），落到了v2v3这条边上，那么就取不在这条边上的顶点v1，计算过v1的水平线与v2v3的交点R2，如果R2在v1的右侧，即R2.x > v1.x，那么说明P2是落在了 右侧 的边，所以 不画

3）假定我们当前要上色的像素点为P3（蓝色），落到了v1v2这条边上，那么就取不在这条边上的顶点v3，计算过v3的水平线与v1v2的交点R3，如果R3在v3的右侧，即R3.x > v3.x，那么说明P3是落在了右侧的边，但图中是R3.x < v3.x，所以P3落在了 左侧 边， 要画

4） 如果存在垂直边或者水平边，怎么判断左右？

垂直边和上面是一种情况，不用单独拿出来考虑。

水平边的画，只画上方，即只画 左边和上边

还是看上图，假定边v2v3是水平的，那么我们取v1，发现v1的y比较小，即v1在v2v3上方，那么边v2v3就是 下边 ，所以 不画 ，反之则画。

可以参考的论文