文档介绍：第七章 计算机图形基本算法
7. 1. 1 DDA 算法(Digital Differential Algorithm)
假设已知直线段AB的端点坐标是A (xi , yi)、B(x2 , y2),且dy/d 1和尤=尤+1换成y = y-1或 x=x-1o
由此可见，该算法中只有加法和乘以2的运算，这在计算机内部是用位移操作来实现 的，所以Bresenham直线生成算法的速度明显高于前面介绍的其它方法。
下面给出的是按Bresenham算法编写的直线生成程序：
7. 2圆弧的生成算法
圆弧的生成算法与直线的生成算法一样，也有许多种。在一个高水平的图形系统中，我 们总是希望采用运算速度更快、显示质量更高的算法。下面介绍几种有代表性的圆弧生成算 法。
因为圆的方程可以简写为x2+y2=R2,与成y与x的函数表达式为
y = +V R2 — x1
显然，在给定的区域内，每取一个x值，便可算出相应的y值，然后经取整运算，可以确定 应该显示的像素点。但是，在这种算法中，开方运算和取整运算极大地影响了显示速度，而 且还存在一个显示质量的问题，即
x以相等步长变化，计算出来的相应的圆弧上的点却是间 隔不均匀的，如图7-4所示。因此，在真正实用的图形系统中，一般不会采用这种算法。
圆弧的Bresenham算法
在上述的代数法与增量法中，-些费时的运算，如乘法、开方等，使得算法的效率受 到了影响。如何避开费时的运算，仅根据一些分析与判断，便能确定圆弧上的点的显示呢？ 人们采用的仍是Bresenham算法。下面对Bresenham圆弧算法的分析过程作较为详细的介绍。
现以第-现象中的1/4圆弧为例，如图7-5a所示。为了最佳逼近该圆弧，像素点P (如 yD为前一个已点亮的像素点，下一个该点亮的像素点应该是哪一个呢？这里只有三种可能: 右方像素点H(Xi+1,协)、右下方像素点D (m + l,y, —1)和下方像素点V (弟，》-1)。 如何决定这三个像素点的取舍呢？这里采用最小二乘法来决策。即被选取的像素点与圆弧的 距离的平方应为最小：
Mh=\ (x, + l)2+(y,)2-7?2 I
Md=\ (x, + l)2+(y -l)2-7?2 I
Mv=l (Xi)2 + (yi-I)2-R2 I
为了更准确地分析问题，把圆弧与当前显示点P (x“为)附近的光栅网格归纳为五种情况, 并放大显示于图7-5(b)中。显然，圆心到右下角像素点D (JG + 1, 1)的距离平方与圆
心到圆弧上的点的距离平方之差为
A, = (x； + l)2+(y,-l)2-7?2
如同直线Bresenham算法-•样，在决策下一个该显示的像素点时，希望只利用误差项△，的 符号来帮助决策，而不是具体计算A的值。若A, < 0 ,则说明右下角点在圆内，即1、2两 种情况见图7-5(b)o在此种情况下，只能选择像素点D 3 + 1, y, -l)或H (为+1,为)。 究竟选择哪-个像素点呢？先行考察第一•种情况，为此要计算两个距离平方的差：
5 =1 (%, +1)2 + (y；)2 (xi +1)2 + (y,-1)2 -R2 I
(a) (b)
图7-5光栅网格的坐标关系
如果5<0,则说明圆弧到像素点D的距离大于圆弧到像素点H的距离，显然应该选择H 点为下一个该显示的圆弧上的像素点。反之，如果$〉0,则应该选取D像素点。当3 = 0 时，规定取H像素点。
首先，考虑图7-5(b)中的第1种情况。在这种情况下，右下角像素点D在圆弧内，右 上方像素点H在圆弧外。因此，可以作下面的推论：
因为 (m +1)? + (y —1)~ < 0 (D点在圆弧内)
所以 5 =(X,. +1)2 +(乂)2 -R2 +3 +1)2 +3 —1)2 -R2
通过加、减代数式(-2y + l),并把y•配成一个完全平方项，则有 此时，5值可能有下列两种情况：
^<0,则选择H点为下一个该显示的圆弧上的像素点；
J>0,则选择D点为下一个该显示的圆弧上的像素点。
其次，考虑图7-5(b)中的第2种情况。由于此时右上方像素点H和右下方像素点D均 在圆弧内侧，所以5表达式有如下关系：
(S + l)2+(yz)2-^2 <0
(x, + l)2+(y/-l)2-7?2 <0
8 = 一O +1)2 — 0)2 + 我2 +(为 +1)2 + 顷 _ 1)2 一 我2 = _2y 一 [ < 0 (第一分角 y >0) 显然，此时应选择像素点H为圆弧上的点。
用类似的方法讨论第3种情况和第4种情况。对于第3种情况，通过加、减代数式
(2x