《线上线下混合式计算机图形学基础实验教程》课件-第3章

第3章图元扫描转换3.1实验内容简述和实验目标3.2扫描转换直线段(DDA)3.3基于Bresenham算法绘制直线段3.4基于Bresenham算法绘制圆3.5课外拓展性实验

3.1实验内容简述和实验目标

基本实验内容包括：扫描转换直线段、基于Bresenham算法绘制直线段、基于Bresenham算法绘制圆。

完成本实验后，读者能够：

(1)描述光栅化的原因和原理(布鲁姆知识模型：记忆和理解)；

(2)列举常见的光栅化绘制现象(布鲁姆知识模型：理解)；

(3)复述DDA、中点、Bresenham算法流程(布鲁姆知识模型：记忆)；

(4)推导DDA、中点、Bresenham算法绘制二次曲线的递推公式，并能够算法化(布鲁姆知识模型：理解和应用)；

(5)基于OpenGL，采用中点、Bresenham算法编程绘制二次曲线(布鲁姆知识模型：应用)；

(6)检查并发现图元光栅化绘制效果存在的问题，判断原因，找出对策并改善(布鲁姆知识模型：应用、分析、评价)。

3.2扫描转换直线段(DDA)

给定直线方程y

=k

×x

+b上两点(x0，y0)和(x1，y1)，绘制上述两点之间的直线段。

(3.1)

对应算法步骤为：

(1)输入直线段的两端点p0(x0，y0)和p1(x1，y1)。

(2)计算公式(3.1)中的初始值k。

(3)令直线段上的点为(xf，yf)，初始为(x0，y0)。

(4)当xf

<=x1时，迭代以下两步骤，否则结束

①将(xf，yf)取整为(xi，yi)，并进行绘制。

②计算直线段上的下一点，即xf

=xf

+1，并根据公式(3.1)计算下一点的yf。

1.关键函数代码实现

2.案例效果

用DDA方法绘制一条直线段，直线段的两端点如图3-1(a)所示，坐标分别为(-200，-200)和(200，200)，最终效果如图3-1(b)所示。

图3-1用DDA方法绘制直线段

3.3基于Bresenham算法绘制直线段

假设当前像素点坐标为(xi，yi,r)，且当前直线段的斜率小于等于1，则逼近直线段的下一个像素点坐标(xi+1，yi+1,r)的具体取值规则如下：xi+1=xi

+1；yi+1,r的值由公式(3.2)给出。这里，di为yi+1,r取值的判别公式，由其决定下一像素点为(xi+1，yi,r)还是(xi+1，yi,r

+1)。此处，令di=yi+1–yi,r

–0.5，其中yi+1为当前直线段与x

=xi+1相交时的真实y坐标。

为此，当di≥0时，说明当前直线段的下一实际交点(xi+1，yi+1)离(xi+1，yi,r

+1)更近，即yi+1,r更适合为yi,r

+1；否则，yi+1,r更适合取值yi,r。同时，判别式的递推公式为di+1

=yi+2

–yi+1,r

–0.5=yi+1

+k

–yi+1,r

–0.5，也取决于yi+1,r的取值，如公式(3.3)所示。此处，k为当前直线段的斜率(dy

÷dx)，为此，di的初始值为k–0.5。

为了提高算法的效率，对上述公式实施整数计算。为此，对判别式乘以2 × dx，此时公式(3.3)更新为公式(3.4)，且初始di为2

×dy

–dx。

(3.4)

对应算法步骤如下：

(1)输入直线的两端点p0(x0，y0)和p1(x1，y1)。

(2)计算初始值dy，dx，d。

(3)绘制点(xf，yf)，初始值为(x0，y0)。

(4)判断d的符号。若d>=0，则下一个(x，y)更新为(x

+1，y

+1)，同时将d更新为d

+ 2 × (dy

-

dx)；否则，将下一个(x，y)更新为(x+1，y)，d更新为d

+ 2 × dy。

(5)当xf

<x1时，迭代步骤(3)和(4)。否则结束。

1.关键函数代码实现

2.案例效果

用Bresenham算法绘制一条直线段，直线段的两端点如图3-2(a)所示，坐标分别为(0，0)和(100，100)，最终效果如图3-2(b)所示。

图3-2用Bresenham算法绘制直线段

3.4基于Bresenham算法绘制圆

基于Bresenham算法绘制圆的算法的主要步骤如下：

(1)输入圆的半径r，默认圆心为(0，0)。

(2)计算初始值x、y，判别式d = 3-2r。

(3)根据圆的对称性绘制点(x，y)，(-x，y)，(x，-y)，(-x，-y)，(y，x)，(-y，x)，(y，-x)，(-y，-x)。

(4)根据d的符号确定下一点y的取值。如果d＞0，则下一个(x，y)更新为(x+1，y-1)，同时将判别式d更新为d+4(x-y)+10；否则下一个(x，y)更新为(x+1，y)，将判别式d更新为d+4x+6。

(5)迭代步骤(3)和(4)，直至圆绘制结束。

1.关键函数代码实现

2.案例效果

用Bresenham算法绘制一个圆心在(0，0)、半径为200