计算机图形学：Bresenham算法与多边形填充

"《计算机图形学》练习题(答案).doc" 计算机图形学是一门研究如何在计算机系统中表示和处理图形的学科。本练习题主要涵盖了直线扫描转换的Bresenham算法以及多边形的扫描填充算法，这些都是计算机图形学的基础内容。 1. **Bresenham算法**： Bresenham算法是一种用于绘制离散点构成的直线段的高效算法，尤其适用于光栅图形系统。对于斜率介于0和1之间的直线，算法步骤如下： - (1) 输入线段的两个端点(x0, y0)和(x1, y1)，其中x0 < x1。 - (2) 初始化：计算∆x = x1 - x0, ∆y = y1 - y0, p0 = 2 * ∆y - ∆x。 - (3) 从x0开始，对每个xk，判断p0是否小于0，如果小于0，则画点(xk+1, yk)，否则画点(xk+1, yk+1)。 - (4) 更新决策参数：pk+1 = pk + 2 * ∆y - (pk < 0 ? 0 : 2 * ∆x)。 - (5) 重复步骤3和4，直到xk = x1。 示例中，起点(1,1)和终点(8,5)的直线段，按照Bresenham算法生成的象素坐标为：(2,2), (3,2), (4,3), (5,3), (6,4), (7,4), (8,5)。 2. **多边形扫描填充算法**： 扫描线填充算法是用于填充多边形的一种方法，它通常涉及边分类表和活化边表的使用。 - (1) 边分类表：表1中记录了每条扫描线与多边形边的交点，例如扫描线4与边E1相交，扫描线5与边E2和E6相交，以此类推。 - (2) 边结构：表2中列出边的初始值可能包括边号、起点y坐标、终点y坐标和斜率的倒数。例如，边E1的起点y坐标可能是y1，终点y坐标可能是y2，斜率的倒数1/m为(y2 - y1) / (x2 - x1)。 - (3) 活化边表：随着扫描线的移动，边分类表中的边会进入或离开活化边表。例如，当扫描线为y=6时，活化边表只有边E6；y=7时，只有边E3；y=8时，有边E5和E3；y=9时，仅边E4；y=10时，没有边在活化边表中。 这些算法在计算机图形学中有着广泛的应用，如2D图形绘制、图像处理、游戏开发等。理解并熟练掌握这些基本算法，对于理解和实现复杂的图形渲染技术至关重要。