计算机辅助设计课件

《计算机辅助设计课件》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章计算机图形基本算法7.1离散直线的生成算法7.1.1DDA算法（DigitalDifferentialAlgorithm）假设已知直线段AB的端点坐标是A（x1，y1）、B(x2，y2),且dy/dx=m=常数,对于一般位置直线ax+by+c=0，显然可以导出下面的递推公式:=（7-1）又因为yi+1=yi+,所以yi+1=yi+.（7-2）这样，每增加一个增量，便可以按式（7-2）计算出yi+1来。由于屏幕上的像素只能是整数，因此要经过取整运算，即[(int)(xi+1),(int)(yi+1)]处的

2、像素点才是显示像素点。然而,乘法运算和取整运算都需要较多的时间，因此产生直线的速度会受到影响。显然，如果在式（7-2）中令=1，则可避免做费时的乘法，公式可以简化为：，。当m<1时，在X方向增加一个步长，就在Y方向得到一个增量，构成一个比1小的步距，经过取整运算，可以相应点亮一个像素点，如图7-1所示。当m>1时，那么在X方向增加一个步长，就有可能在Y方向上构成一个比1大的步距。遇到这种情况，为了保证图形显示精度，就应当把x、y的地位互换，把y看作是自变量，每次增加单位步长1，去计算因变量x，即，由于=1，所

3、以这样才不至于一次跳过多行。当然，也要对进行取整运算，再决定要显示的像素。这种情况如图7-2所示。图7-1m<1的情况图7-2m>1的情况可见DDA算法就是一个增量算法，在一个迭代算法中，其每一步的x、y值是用前一步的值加上一个增量来获得的，即称为增量算法。在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。7.1.2直线的Bresenham算法为了避免做费时的乘法运算和取整运算，人们不断努力，寻找到许多效率更高的显示直线段的算法。其中在二十世纪60年代，由Bresenham提

4、出的一种更好的直线生成算法，称为Bresenham算法。此算法的一个根本47思想是借助于一个决策变量di，来确定下一个该点亮的像素点。对于00，所以可以用dx(s-t)<0作为选择Si为下一个该点亮的像素点的条件。因为，则表示。从图7-3可以看出，在时，应选择Si点。定义，并称之为决策变量

5、，那么从图7-3可以看出，，，是表示前面一个亮点的坐标值，因此可以写出决策变量的初始值为将下标加1，则有如果≥0（即，）,则表示下一个亮点应该选Ti。一旦选择了Ti，则有，此时决策变量的表达形式如下：如果<0(即,)，则表示下一个亮点应该选。一旦选择了，则有，此时决策变量的表达形式如下：这样，便得到一种迭代方法：由上一个决策变量可以算出下一个决策变量，再根据决策变量的正、负对与Ti进行选择。上面讨论的是≥>0的情况。如果是>>0的情况，则要把x和y的变量地位互换。对于<0或<0的情况，则应将表达式和换成或。由

6、此可见，该算法中只有加法和乘以2的运算，这在计算机内部是用位移操作来实现的，所以Bresenham直线生成算法的速度明显高于前面介绍的其它方法。下面给出的是按Bresenham算法编写的直线生成程序：477．2圆弧的生成算法圆弧的生成算法与直线的生成算法一样，也有许多种。在一个高水平的图形系统中，我们总是希望采用运算速度更快、显示质量更高的算法。下面介绍几种有代表性的圆弧生成算法。7.2.1圆弧的扫描算法因为圆的方程可以简写为x2+y2=R2，写成y与x的函数表达式为显然，在给定的区域内，每取一个x值，便可算

7、出相应的y值，然后经取整运算，可以确定应该显示的像素点。但是，在这种算法中，开方运算和取整运算极大地影响了显示速度，而且还存在一个显示质量的问题，即x以相等步长变化，计算出来的相应的圆弧上的点却是间隔不均匀的，如图7-4所示。因此，在真正实用的图形系统中，一般不会采用这种算法。xy图7-4圆弧的扫描算法7.2.2圆弧的Bresenham算法在上述的代数法与增量法中，一些费时的运算，如乘法、开方等，使得算法的效率受到了影响。如何避开费时的运算，仅根据一些分析与判断，便能确定圆弧上的点的显示呢？人们采用的仍是Br

8、esenham算法。下面对Bresenham圆弧算法的分析过程作较为详细的介绍。现以第一现象中的1/4圆弧为例，如图7-5a所示。为了最佳逼近该圆弧，像素点P（xi，yi）为前一个已点亮的像素点，下一个该点亮的像素点应该是哪一个呢？这里只有三种可能：右方像素点H（xi+1，yi）、右下方像素点D（,）和下方像素点V（，）。如何决定这三个像素点的取舍呢？这里采用最小二乘法来决策。即被选取的像素点与圆弧