3 图元扫描转换

3.1 图元扫描转换

3.1.1 直线段扫描转换

• 数值微分(DDA)法
这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

• 中点画线法
只有整数运算，不含乘除法；可用硬件实现



此外，根据d的不同，可以得到不同的d的迭代结果



需要注意的是，弱斜率大于1，则需要将x-y轴翻转进行考虑

• Bresenham画线算法
使用最广泛，与中点画线法的思想类似 由误差项符号决定下一个象素取正右方像素还是右上方像素

3.1.2 圆弧扫描转换算法

• 中点画圆法
如果中点在圆内就取上，在圆外就取下

• Bresenham画圆算法
看上下两个点哪个距离圆心更近

• 生成圆弧的正负法

• 圆的内接正多边形逼近法

3.2 实区域填充算法

3.2.1 判断点是否在图形内部

• 检验夹角之和
若夹角和为0，则点p在多边形外

• 四象限法
由于上述方法计算量过大，可以考虑使用四象限法，做出四象限，分别做该点和顶点的连线，若该连线和上次的连线不在同一象限内，则角度+Π/2，若最后为2Π则争取。（粗略估计）

• 射线法检验交点数

3.2.2 有序边表算法

作业

GAMES101