目录
三角形光栅化
光栅化是将几何数据经一系列变换，最终转换为像素，而在屏幕上显示的过程.
直线光栅化，在2D屏幕上，对两端点间插值，绘制一条直线（段）. 常用中点算法和Bresenham算法，Bresensham算法参见Bresenham画直线算法（所有斜率）.
类似地，视口变换后，需要在2D屏幕上绘制三角形\(\bm{abc}\)，顶点坐标分别为\(a(x_0,y_0),b(x_1,y_1),c(x_2,y_2)\). 三角形的绘制，需要用顶点的颜色或其他属性插值，即重心坐标插值（详见计算机图形：三角形及重心空间）.
假设三顶点颜色\(\bm{c_0,c_1,c_2}\)，那么三角形中任一点\(p(x,y)\)重心插值坐标为\((α,β,γ)\)，颜色为：
\[\bm{c}=α\bm{c_0}+β\bm{c_1}+γ\bm{c_2} \]tips: Gouraud明暗处理中，用这种方法对光强进行插值.
绘制三角形轮廓
可用中点算法（midpoint algorithm）绘制三角形轮廓.
图片from 计算机是怎么画线的？中点算法与Bresenham算法
中点算法思想：以斜率>0为例，画直线要确定下一像素时，将位于右侧和右上侧的2个待选像素中心点的中点代入直线方程，根据中点位于该直线的上方 or 下方决定下个像素. 当中点位于上侧，说明直线靠近右侧像素；反之，说明直线靠近右上侧像素.
填充三角形内部
总流程：重心坐标 \(\xrightarrow{α,β,γ\in (0,1)?}\) 是否像素绘制\(\xrightarrow{顶点插值颜色}\)像素颜色
平面上任一点\(p(x,y)\)，都能用以三角形三顶点\(\bm{a,b,c}\)为基础的重心坐标表示.
\[\bm{p}=α\bm{a}+β\bm{b}+γ\bm{c},α=\frac{A_a}{A},β=\frac{A_b}{A},γ=\frac{A_c}{A} \]其中，\(A_a,A_b,A_c,A\)分别表示三角形\(pbc,pac,pab,abc\)面积. 由于都是三角形面积比值，可以换算成同底不同高的比值.
该公式可用于颜色等属性插值.
当像素的重心坐标\(α,β,γ\in(0,1)\)时，认为像素中心位于三角形内，而避免顺序问题、消除孔洞.
得到了像素插值颜色，如何填充三角形内部像素？
可遍历屏幕所有像素点，当点位于三角形内部时，通过颜色插值进行绘制.
实践中，为减少要遍历的像素点，可用三顶点构造一个边界矩形，将检索范围限制在矩形内. 算法如下：
// a(xa,ya),b(xb,yb),c(xc,yc) consits of a 2D triangle, including color property
xmin = floor(x[i]);
xmax = ceiling(x[i]);
ymin = floor(y[i]);
ymax = ceiling(y[i]);
for (y = ymin; y <= ymax; y++) {
for (x = xmin ; x <= xmax; x++) {
alpha = f_bc(x, y) / f_bc(xa, ya);
beta = f_ac(x, y) / f_ac(xb, yb);
gamma = f_ab(x, y) / f_ab(xc, yc);
if (alpha > 0 && beta > 0 && gamma > 0) {
color = alpha * a + beta * b + gamma * c; // color of pixel(x,y)
drawpixel(x, y, color);
}
}
}
\(f_{ab}、f_{bc}、f_{ac}\)分别表示直线ab、bc、ac，对应方程：
\[\begin{aligned} f_{ab}(x,y)&=(y_a-y_b)x+(x_b-x_a)y+x_ay_b-x_by_a\\ f_{bc}(x,y)&=(y_b-y_c)x+(x_c-x_b)y+x_by_c-x_cy_b\\ f_{ac}(x,y)&=(y_c-y_a)x+(x_a-x_c)y+x_cy_a-x_ay_c \end{aligned} \]推导可参见计算机图形：三角形及重心空间
问题：为什么循环体内只测试\(α,β,γ>0\)，而不是验证\(\in (0,1)\)？
因为\(α+β+γ=1\)，如果3者都＞0，那么都位于区间\((0,1)\).
- 增量法节省计算量
绘制直线时，考虑到相邻像素，有以下关系：
\[\begin{aligned} f(x,y)&=Ax+By+C\\ \implies f(x+1,y)&=f(x,y)+A\\ f(x,y+1)&=f(x,y)+B \end{aligned} \]如此，只需1次加法，就能求出\(f(x,y+1),f(x+1,y)\)，从而减少求\(α.β,γ\)时间.
处理公共边界
如果一个像素中心位于2个三角形的公共边，该如何处理？
有3种策略：
-
下策：不绘制该像素，但是会在2个三角形之间形成孔洞.
-
中策：2个三角形都绘制该像素，但如果三角形是透明的，会造成双重着色.
-
上侧：属于哪个三角形不重要，选择明确即可.
一种简单的选择方法，是找一个屏幕外的点，比如\(p_0(-1,-1)\)，通常认为屏幕外的点不在直线上.
\(f_{bc}(\bm{p_0})\cdot f_{bc}(\bm{{a_1}})<0\)，表明\(\bm{p_0},\bm{a_1}\)在直线bc不同侧；
\(f_{bc}(\bm{p_0})\cdot f_{bc}(\bm{{a_2}})<0\)，表明\(\bm{p_0},\bm{a_2}\)在直线bc同侧；
那么，选择\(△a_2bc\)绘制公共边bc.
当\(α=0\)时, \(f_{bc}(x,y)=0\)，代表p在bc上；
当\(β=0\)时, \(f_{ac}(x,y)=0\)，代表p在ac上；
当\(γ=0\)时, \(f_{ab}(x,y)=0\)，代表p在ab上.
算法如下：
// a(xa,ya),b(xb,yb),c(xc,yc) consits of a 2D triangle, including color property
xmin = floor(x[i]);
xmax = ceiling(x[i]);
ymin = floor(y[i]);
ymax = ceiling(y[i]);
p0 = (-1, -1);
f_alpha = f_bc(xa, ya);
f_beta = f_ac(xb, yb);
f_gamma = f_ab(xc, yc);
for (y = ymin; y <= ymax; y++) {
for (x = xmin ; x <= xmax; x++) {
alpha = f_bc(x, y) / f_bc(xa, ya);
beta = f_ac(x, y) / f_ac(xb, yb);
gamma = f_ab(x, y) / f_ab(xc, yc);
if (alpha >= 0 && belta >= 0 && gamma >= 0 ) {
if ((alpha > 0 || f_alpha * f_bc(p0.x, p0.y))
&& (beta > 0 || f_beta * f_ac(p0.x, p0.y))
&& (gamma > 0 || f_gamma * f_ab(p0.x, p0.y))
) {
color = alpha * a + beta * b + gamma * c; // color of pixel(x,y)
drawpixel(x, y, color);
}
}
}
}
参考
[1] Marschner S , Shirley P , Ashikhmin M ,et al.Fundamentals of computer graphics, fourth edition[J].A. K. Peters, Ltd. 2015.
标签：bc,插值,bm,像素,绘制,三角形,光栅,图形 From： https://www.cnblogs.com/fortunely/p/18188180