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

如何判断屏幕的哪些像素点在该三角形内部？
主流的算法有两种：
1.LEE（Linear Expression Evaluation）
2.Scan Line
本期只讲LEE，因为Scan Line我没有亲自搞过。
LEE大致原理如下：

1. 首先因为屏幕只有二维，所以判断点和边的位置关系的时候可以先不管Z，Z只是用来判断前后遮挡的。
2. 按照顺时针（或者逆时针）的顺序，连接v1v2, v2v3, v3v1，这样就得到了三条边。
3. 假定边的头是（X+dX, Y+dY），尾是（X, Y）
   计算这3条边的方程：E(x,y) = dY(x-X)-dX(y-Y)
   展开之后是dY*x + (-dX)*y + (dX*Y-dY*X) = 0
   即Ax + By + C =0
   其中A = dY, B = -dX, C = dX*Y-dY*X
   我们把v1v2, v2v3, v3v1三条边的A, B, C都求出来，就得到了3条边的方程E1, E2, E3。
4. 将屏幕像素点的x,y带入方程，A1x + B1y + C1 = E1，如果点在边上，则E1=0，如果点不在边上，则E1！=0。
5. 最神奇的地方来了。
   如果点（x,y）带入3个方程的结果E1, E2, E3同时大于0或者同时小于0，即同号，则该点在三角形内，如果异号，则在三角形外。
6. 每次获得3个点之后，取出其中的min_x, max_x, min_y, max_y构成的四边形，将屏幕像素点（x,y）中，在该范围内的点取出，带入LEE公式比较结果。
   如果该点在三角形内，并且没有被遮挡（需要对Z进行判断），则上色，否则不上色。不断迭代，直到所有的三角形都被处理完成，3D模型也画到了屏幕上。

需要注意的地方：

1. 如何判断遮挡，即得到三角形内的点的Z值？
   答：我们知道了v1, v2, v3三个点，可以求三角形平面方程，求出之后，只需要将某个点的（x,y）代入，即可求出z。
   平面方程一般式为：Ax + By + Cz + D = 0
   取E1, E2两个边向量，进行叉乘，得到法向量N(A,B,C)。
   没错，你没看错，N的X, Y, Z即是A, B, C。（数学真神奇）
   然后取v1(x, y, z)带入方程，求出D，平面解析式就得到了。
   然后将想求z的点的x,y带入，就可以求出z了。

2. 屏幕的Z轴是朝里的，所以z越大说明离我们越远，z越小就里我们越近，近处的会遮挡远处的。

3. LEE的特殊情况
   由于多个三角形的边和边是互相挨着的，所以如果直接按上面的方法画，会有很多边重复画了2遍，为了提高渲染效率，我们需要保证每条边只画一遍。
   怎么保证呢？
   答：只画三角形的左边和上边

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

如图所示：
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就是下边，所以不画，反之则画。

可以参考的论文

1. Siggraph 1985 - "Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes," Henry Fuchs,et. al.

2. 2000 Sig/Euro Workshop on Graphics Hardware - "Tiled Polygon Traversal Using Half-Plane Edge Functions," Joel McCormack, Robert McNamara

3. Siggraph 1988 - "A Parallel Algorithm for Polygon Rasterization," Juan Pineda

4. Siggraph 2005 - “Resolution-Independent Curve Rendering Using Programmable Graphics Hardware,” Charles Loop, Jim Blinn

最后

以上就是愉快柠檬为你收集整理的如何判断屏幕的哪些像素点在该三角形内部？的全部内容，希望文章能够帮你解决如何判断屏幕的哪些像素点在该三角形内部？所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。