• 用绘图软件包 • OpenGL就是一个典型的、已经被接受的国际工业标 准的图形软件包。 • Java3D
• 用操作系统的绘图功能 • 如Windows中Win32API中就提供了基本的绘图功能
• 在数学上，理想的直线是一条由无穷多个无限小的连续的 点组成。
• 在光栅显示平面上，我们只能用二维光栅格网上尽可能靠 近这条直线的象素点的集合来表示它。每个象素具有一定 的尺寸，是显示平面上可被访问的最小单位，它的坐标x 和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不 是连续的。
������������ − ������������ = 20
第二步：在x轴方向上每次的变化量为∆������ 变化量为∆������ = ������������−������������ = 0.65
=
������������−������������ ������
=
−1，则y轴方向的
������
• DDA算法描述
• 设(xs,ys)和(xe,ye)分别为直线的起点坐标和终点坐标，则：
直线的斜率
=
∆������ ∆������
=
������������ ������������
− −
������������ ������������
• 可通过计算由x方向的增量 ∆������ 引起y的改变来生成直线。
由������������+1 = ������������ + ∆������，得到：
������������+1
=
������������
+
������ ������
×
∆������
=
������������
+
������������ ������������
− −
������������ ������������
=
������������+1
−
������������,������+ ������������,������+1 2
=
������������+1
−
������������,������
−
1 2
• 当������(������������+1) ≥ 0时，������������+1,������ = ������������,������ + 1，即选C点
第三步：循环计算点的坐标，并取整显示：
• Bresenham算法基本思想
•
令������
=
Δ������，直线方程：������
������
=
������
������
− ������������
+ ������������，其中
（������������, ������������）为起点坐标；
• DDA算法特点
算法简单，实现容易，但计算量较大，每产生一个像素 需要取整运算，此外算法还要除法运算，因此生成直线的 速度较慢。
例题1：已知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间 生成一段直线。
第一步：计算初值：������������ − ������������ = −4 − 16 = −20，������������ − ������������ = 8 − −5 = 13，由于20 > 13，所以选定x轴方向作为步进方向；������ =
• 直线生成算法
• DDA方法 • Bresenham算法
• 圆弧生成算法
• 中点圆生成算法
• 多边形的填充
• 多边形表示方法 • 多边形填充的扫描线算法 • 边缘填充算法 • 边界标志算法
• 区域填充
• 区域的基本概念 • 简单种子填充算法 • 扫描线种子填充算法
• 光栅图形的反走样算法
• 用现有绘图软件系统 • 画图\Word中的图文编辑工具\AutoCAD\Photoshop 等大型绘图软件
−
(������������,������
• 考虑0 ≤ ������ ≤ 1，则x方向增加1，y方向增加m，由起点
(xs,ys)可求得直线上的点(xi，yi)， i=1,2,3,…, 其中 x1= xs, y1= ys；
• 用坐标为(xi，round(yi))的象素来表示直线上的点，其中 round(yi)表示最靠近y的整数；
• Bresenham算法基本思想
• 令yi,r=round(yi), 用坐标为(xi，yi,r)的象素来表示直线上的点， 第i+1个点只能在C和D中选取。
• 令误差项������ ������������+1
=
������������+1
−
������������
=
������������+1
−
������������+������������ 2
∆������
• 同样，可通过计算由y方向的增量∆������引起x的改变来生
成直线。由������������+1 = ������������ + ∆������，得到：
������������+1
=
������������
+
������ ������
×
∆������
=
������������
������������+2
−
������������+1,������
−
1 2
=
(������������+1+������)
−
������������&#=
൞
������������+1 + ������
−
������������,������
−
1 2
������������+1 + ������
• 当������(������������+1) < 0时，������������+1,������ = ������������,������，即选D点
• Bresenham算法基本思想
• ������(������������+2)的递推公式
• ������ ������������+2
=
+
������������ ������������
− −
������������ ������������
∆������
• DDA算法基本思想
选定 ������������ − ������������ 和 ������������ − ������������ 中较大者作为步进方向，在此方 向上每次增加（或者减少）一个像素，然后计算另一个方 向上增量的值，把每次计算出的值经取整后顺序输出到显 示器，则可以得到光栅化的直线。