基本图形生成算法研究-课程设计

1、*大学学生课程设计（论文）题 目：基本图形生成算法研究学 号：姓 名：专业年级：教师姓名：2015年 06月 03日摘 要计算机能够生成各种各样复杂的图形，但是无论如何复杂，这些图形都由一些基本图形组合而成的。所以学习基本图形生成算法是掌握计算机图形的基础。本章主要讨论一些基本图形的生成原理，如直线、椭圆生成、区域填充等。目前我们使用的主要图形输出设备显示器（一般为光栅图形显示器）和打印机（喷墨、激光打印机）本质上是一种画点设备，是由一定数量的网络状细小光点组成，使某些像素亮和某些像素不亮来显示图形。因此，基本图形生成的原理是指在点阵输出设备的情况下，如何尽可能地输出最接近于原图形的直线或曲线

2、图形，即以最快的速度确定最佳逼近于图形的像素集。确定图形的像素集合并显示的过程常称之为图形的扫描转换或光栅化。这一过程使用的计算方法称之为图形生成算法。【关键词】计算机图形学、快速绘制，单点生成，多点生成。AbstractComputer can produce a variety of complex graphics, but no matter how complex, these graphics are made up by some basic graphics. So learn basic graphics generation algorithm is the basis o

3、f mastering computer graphics.This chapter mainly discuss some basic graphics generation principle, such as the production of straight line, oval, area filling, etc. At present, we use the main display of graphics output devices (typically for raster graphics display) and printer (inkjet and laser p

4、rinter) is essentially a kind of painting equipment, is composed of a certain number of reticular tiny points of light, make certain pixel light and some pixels to display graphics.Therefore, the principle of basic pattern generation refers to the dot matrix under the condition of output devices, ho

5、w to output as much as possible the most close to the original graphics straight line or curve graphics, namely with the fastest speed to determine the optimal approximation in graphics set of pixels. Determine the set of graphical pixel scanning and display the process is often called graphics conv

6、ersion or rasterizer. This process using the calculation method of generation algorithm called graphics.【keywords】Computergraphics，fast rendering，Single-pointgeneration，Multi-pointgeneration。摘 要2Abstract3 一.直线段的生成51.1中点画线算法51.2 Bresenham算法画线法10二圆与椭圆的扫描转换132.1.1圆的特征132.1.2圆的方程产生圆弧132.1.3圆的扫描转换132.1.4

7、中点画圆法142.1.5 Bresenham画圆算法152.2.1椭圆的特征192.2.2中点法画椭圆192.2.3下半椭圆20参考文献22一.直线段的生成直线是点的集合，几何学中的一条直线是由两点决定，直线在数学上可以有多种表示方法，而在计算机图形学里，直线是由离散的像素点逼近理想直线段的点的集合。数学上的直线是没有宽度的，而计算机图形学中显示出的直线的宽度与像素点的大小有关，一个像素宽的直线的线粗为像素的边长。由计算机生成的图形中有大量的直线段，而且曲线也是由一系列短直线段逼近生成的。因此，研究直线生成的方法是计算机图形学的基本问题之一。 对计算机生成直线的一般要求是：线段端点的位置要准确

8、；构成线段的像素点的集合应尽可能分布均匀，其密度应该与线段的方向及长度无关；线段生成的速度要快。生成直线的算法有多种，这里介绍两种方法，即中点画线算法和Bresenham算法。1.1中点画线算法这里讨论的是斜率|K|1的直线。通过看图知道，在画直线的过程中，当前像素点为（xp,yp），则下一点有两个点可以选择，分别是p1（xp+1，yp）和p2（xp+1，yp+1）。设p1与p2的中点为M（xp+1，yp+0.5），设理想直线L与p1，p2的交点为Q。当M在Q的下方时，应取p2作为下一个像素点，当M在Q的上方时，应取p1作为下一个像素点。这就是中点画线法的原理。 对于直线L（p0（x0，y0）

9、，p1（x1，y1），采用方程F（x，y）=ax+by+c=0表示，其中a=y0-y1，b=x1-x0，c=x0y1-x1y0，于是有下述点与L的关系：当F（x,y）=0时，点在直线上。当F（x,y）0时，点在直线的上方。当F（x,y）0，点在直线的下方。 因此为了判定M在Q点的上方还是下方，只要把M代入到F（x，y），并判断它的符号即可。可构造下述判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c。当d0时，M在Q的上方，应取p1作为下一个像素点；当d=0时，选择p1或p2均可，约定取p1为下一个像素点。 为了方便计算，减少运算量，我们采用增量计算的方

10、法，具体如下：(1)若d0，则取正右方的p1(xp+1,yp)。判断下一个像素点的位置时，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，增量为a。 P=(xp,yp) P1 P2L (2)若d0，则取右上方的p2(xp+1,yp+1)。判断下一个像素点的位置时，应计算d1=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量为a+b。中点画线算法如下：floata,b,delta1,delta2,d,x,y;intx0,y0,x1,y1; if(sp0SetPixel(x,y,color); if(b=0) if(y

11、0y1) for(y=y0;ySetPixel(x0,y,color);else for(y=y0;y=y1;y-) pDC-SetPixel(x0,y,color);/ if(0=k&k=1) d=2*a+b;delta1=2*a;delta2=2*a+2*b; while(xx1) if(dSetPixel(x,y,color); if(k=-1&k=0) d=2*a-b;delta1=2*(a-b);delta2=2*a;while(xx1) if(dSetPixel(x,y,color); if(k1) d=2*b+a;delta1=2*b;delta2=2*(a+b);while(y

12、y1) if(dSetPixel(x,y,color); if(ky1) if(d0) y-; d+=delta1;else x+;y-;d+=delta2; pDC-SetPixel(x,y,color);实验结果：1.2 Bresenham算法画线法Bresenham算法是在计算机图形学领域内使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个像素取右边点还是右上点。算法原理如下：如图2-2所示，构造一组虚拟的网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个

13、误差项的符号，就可以确定该列所求的像素。 如图所示，设直线的方程为y=kx+b，则有yi+1=yi+k(xi+1-xi)=yi+k，其中k为直线的斜率。假设x列的像素坐标已经确定为xi，其行坐标为yi,那么下一个像素的列坐标为xi+1，而行坐标要么仍为yi，要么递增1为yi+1。是否增1取决于图2.2上的误差项d的值。因为直线的起始点在像素中心，所以误差项d的初值d0=0。x下标每增加1，d的值相应递增直线的斜率值k，即d=d+k。当d0.5时，直线与xi+1列垂直网格的交点最接近于当前像素的右上方的像素点(xi+1,yi+1)，该像素在y方向增加1，同时作为下一次计算的新基点，因此d值相应减

14、去1；而当d0.5时，更接近于右方像素(xi+1,yi)。为了方便计算，我们另e=d-0.5，e的初值为-0.5,增量为k。当e0时，取当前像素的右上方像素(xi+1,yi+1)，e减少1；而当ex0)zjx=1;else zjx=-1; if(y1y0)zjy=1;else zjy=-1;if(dydx) temp=dx;dx=dy;dy=temp;tag=1;else tag=0;e=2*dy-dx; for(i=1;iSetPixel(x,y,color);if(e=0) if(tag=0)y=y+zjy;else x=x+zjx;e=e-2*dx; if(tag=0)x=x+zjx;e

15、lse y=y+zjy;e=e+2*dy;实验结果：二圆与椭圆的扫描转换2.1.1圆的特征圆被定义为到给定中心位置(x,y)的距离为r的点集。根据圆的对称性原理：(1) 圆是满足x轴对称的，这样绘制圆弧只需要计算圆的1/2。(2) 圆是满足y轴对称的，这样绘制圆弧只需要计算(1)的1/2。(3) 同时，圆是满足y=x与y=-x轴对称的，这样只需要计算(2)的1/2。通过以上的分析，绘制圆弧只需要绘制圆上总数的1/8点的位置即可。假设在坐标系的第一象限的左上部分有目标点(x,y)，必然存在(x,-y)，(-x,y)，(-x,-y)，(y,x)，(y,-x)，(-y,x)，(-y,-x)这另外7个

16、对称点。这样，只需要计算圆上从x=0到x=y的1/8点的位置，然后通过对称性得到其他7个点的位置信息。2.1.2圆的方程产生圆弧圆的方程为：x+y=R，由此方程可以得到圆上的y坐标与x坐标的关系：yi=sqrt(R-xi)。当x取整时候，y须取整。用这个方法的不足在于浮点运算，需要开方取整，不均匀。2.1.3圆的扫描转换图形的扫描转换也叫图形的光栅化，是在光栅显示器等数字设备上确定一个对图形实现最佳逼近的象素集合，并用指定的颜色和灰度设置象素的过程。对于一维图形，在不考虑线宽因素时，用一个象素宽的直线或曲线来显示图形。对于二维图形，其光栅化必须要确定区域对应的象素集，将各个象素设置成指定的颜色

17、和灰度，也称之为区域填充。任何图形光栅化后，显示在屏幕上的一个窗口里，超出窗口的部分则不予显示。确定一个图形的哪些部分在窗口内，必须显示；哪些部分落在窗口之外，不予显示，这需要对图形进行裁剪。裁剪通常在扫描转换之前进行，对图形不可见部分则不需要进行扫描转换。根据圆的对称性，在进行圆的转换时，只要能生成八分之一圆，那么圆的其它部分可通过一系列的简单反射变换得到。所以本文只讨论生成八分之一圆弧的情况。2.1.4中点画圆法中点法还是讨论1/8圆弧的画法。如图2-3所示，针对当前点p，下一点应该选择p1(xp+1,yp)还是选择p2(xp+1,yp-1)。取p1还是p2取决于点M在圆弧内部还是在圆弧外

18、部。由圆的方程构造函数F(x,y)=x+y-R，对于圆上的点，F(x,y)=0；对于圆外的点，F(x,y)0；对于圆内的点，F(x,y)0，说明点M在圆弧的外部，应选p2(xp+1,yp-1)作为下一点。(2) 若d0时，则应取p2作为下一像素，而且下一像素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5，即d的增量为2(xp-yp)+5。因为这里讨论的是按照顺时针方向生成的第二个八分圆(见图2-3)，则第一个像素是(0,R)，判别式d的初值为d0=F(1,R-0.5)=5/4-R。中点画圆法算法：MidPointCircle(

19、intr) intx=0,y=r;floatd=1.25-r;while(x=y) circlepoints(x,y);if(d0) d+=2*x+3;elsed+=2*(x-y)+5;y-;x+;2.1.5 Bresenham画圆算法考虑圆心在原点，半径为r的第一个4分圆。取（r,0）为起点，按顺时针方向生成圆，如图3.6所示。从这段圆弧的任意一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，下一像素的取法只有三种可能的选择：正右方像素，右下方像素和正下方像素。分别记为H、 D和V。如图所示。这三个像素中，与理想圆弧最近者为所求像素。由于这里只考虑第一个4分圆，理想圆弧与这三个候选点之间的关

20、系只有下列三种情况：（1） H在圆外，D、V在圆内；（2） D在圆上，H 在圆外， V在圆内；（3） H、D在圆外，V在圆内；如图3.7所示。 上述三点到圆心的距离平方与圆弧上一点到圆心的距离平方之差分别为：H=（x+1）+y-rD=（x+1）+（y-1）-rV=x+（y-1）-r与Bresenham直线扫描算法一样，在选最佳逼近该圆的像素时，我们希望只判别误差项的符号。 如果DD0，那么右下方像素D在圆内，圆弧与候选点的关系只可能是(1)的情形。显然，这时最佳逼近圆弧的像素只可能是H或D这两个像素之一。为了确定H和D哪个更接近于圆弧，令HD=|H|-|D|=|(X+1)+Y-R|-|(X+1

21、)+(Y-1)-R|若HDD0，则圆到右下方像素D的距离较小，故应取D为下一像素。而当 0=DHD时，二者均可取，约定取正右方像素H。 在(1)的情形下，H总在圆外，D总在圆内，因此HD0，DD0，所以HDD可以简化为HD=H-D=(X+1)+Y-R+(X+1)+(Y-1)-R=2D+2y-1如果DD0，那么右下方像素D在圆内，圆弧与候选点的关系只可能是(1)的情形。显然，这时最佳逼近圆弧的像素只可能是H或D这两个像素之一。为了确定H和D哪个更接近于圆弧，令HD=|H|-|D|=|(X+1)+Y-R-|(X+1)+(Y-1)-R|若HD0，则圆到右下方像素D的距离较小，故应取D为下一像素。而当

22、 HD=0时，二者均可取，约定取正右方像素H。 在(1)的情形下，H总在圆外，D总在圆内，因此H0，D0的情况。这时，右下方像素D在圆外，最佳逼近圆弧的像素只可能是D与V二者之一，即情形(3)。令DV=|D|-|V|=|(X+1)+(Y-1)-R|-|X+(Y-1)-R|如果DV0，即圆到正下方像素的距离较小，那么应取正下方像素V。而当DV=0时，二者均可取，约定取右下方像素D。 在(3)的情形下，由于右下方像素D在圆外，而正下方像素V在圆内，所以D0， V0的情况下，若2(D-x)-10，应取D为下一像素，否则取V作为下一像素。 最后考虑情形(2)，即D=0。这时，右下方像素D恰好在圆上，故

23、应取D作为下一像素。 归纳上述讨论，可得计算下一像素的算法：当D0时，若DV0，则取D，否则取V；当D0时，若HD0，则取H，否则取D；当D=0时，取D。 由于HD与DV均可由D推算出来，所以，我们下面讨论如何简化DD的计算。与直线扫描算法类似，采用增量算法。首先考虑下一个像素为H的情况。对于像素H，其坐标为（x,y）=(x+1,y)其误差项为：D=(X+1)+1)+(Y-1)-R=D+2(X+1)+1=D+2X+1再考虑下一个像素为D的情况，其坐标与误差分别为（x,y）=(X+1,Y-1)D=D-2Y+1综上所述可写出完整的Bresenham画圆算法Bresenham画圆算法:voidBre

24、senhamCircle() intx=0,y=r;Floatd=3-2r;while(x=0) d+=4(x-y)+11;y-；else d+=4x+7; x+; 2.2.1椭圆的特征如图所示，椭圆的方程可以表示成：中心在（0，0）上的，F(x,y)=bx+ay-ab=0，其中，a为长半轴的长度，b为短半轴的长度由于椭圆的对称性，将椭圆分成四等份，只要画出一部分，其余的三部分就容易画出了。就第一象限来说，自变量的选取。不难看出，当由y轴向右看，x的变化比较大。过一个点后，y的变化比较大。所以应找到这一点，将第一象限部分再次分为上半部分和下半部分。以弧上斜率为-1的点作为分界点。由微积分知识得

25、到，该椭圆上一点（x,y）处的法向量为P(x,y)=2bx+2ay，即椭圆弧属于上半部分的条件为：aybx.2.2.2中点法画椭圆中点法也是最常用的椭圆绘制算法 之一。这里讨论图中弧AB的画法。椭圆弧的上半部分AC按顺时针方向生成，现在从A点开始向右下方逐点寻找显示弧AC要用的点，如果图中的点P是已选中的一个表示圆弧上的点，由于圆弧在AC两点之间斜率的绝对值小于等于I， 所以下一个点P应为P=P=(X+l，Y)或 P=P=(X+l，Y-1)，选P1还是选P2取决于点Pm在圆弧内部还是在圆弧外部。Pm的位置由F(x，Y)=bx+ay一ab=0来判断P的位置：d=F(M)=F(x+1,y-0.5)=b(x+1)+a(y-0.5)-ab(1) 当d0时，说明点M在椭圆外部，应取p2作为下一