计算机图形学课件（C版）

第3章，光栅扫描图形学，3.1直线生成算法，3.2日元和椭圆的生成算法，主要教育内容，3.3实际区域的扫描变换，3.4区域填充，3.5图形的抗混叠基础，DD-line(x1，y1，x2，y2，color)intx1，y1，x2，y2 intlength； floatx、y、x、y； length=ABS (x2-x1 ) if (ABS (y2-y1 ) length ) length=ABS (y2-y1 )； x=(x2-x1)/length； y=(y2-y1)/length； x=x10.5 * sign (x ) y=y10.5 * sign (y ) for (I=1； i=length； i )putpixel(Int(x )，Int(y )，color； x=x x； y=y； ，putpixel (30，50，2 )； (30，50 )中用2号颜色表示一点。 在帧缓存的相应位置存储像素亮度。 简单DDA算法，int (x ) :等于或小于x的最大整数，P132示例：起点(0，0 )，终点(-8，-4)分别为(-1，-1)、(-2，-1)、(-3，-2)、(-4，-2)、(-5，-3)、(-6，-3)、(-7，-4)、(-8，-4)、-1-2-3-4， -8-7-6-5-4-3-2-1简单DDA算法的应用示例包括： (2)对称DDA方法：取t=2-n，2n-1=max(|X|，|Y|)2n，思考问题：使用对称DDDA方法处理上例，并写入各轨迹点的坐标。 为什么，DDA方法比直接使用线性方程式的方法快，没有浮点乘法，但是有浮点数的加法，在DDA的整数操作和浮点运算还需要时间。 3.1.2Bresenham的线性算法与简单的DDA法相似，增量向最慷慨的方向一步一步地走，用e的值决定另一个方向是否走。 假定一条直线的起点(xs，ys )，终点(xe，ye )，斜率m=y/x=(ye-ys)/(xe-xs )，e(xi 1)=yi 1-yi，r-0.5，0=m=0，则b位于a之上，并且下一步是d，yi 1，r=yi，r 1若e(xi 1)0，其中，b位于a之下，并且下一步是d，yi 1，r=yi，r 1若e(xi 1)0 成为r，e(xi 1)=yi 1-yi，r-0.5，e(x2)=y2-y1，r-0.5=y2- y1-0.5=y1m-y1-0.5=m-0.5，e初始值？ Bresenham-line(x1，y1，x2，y2，color)intx1，y1，x2，y2，color； intx，y，x，y； 浮动，m； x=x1； y=y1； x=x2-x1； y=y2-y1； m=y/x； e=m-0.5； for(i=1； i=0y=y 1； e=e-1； x=x 1； e=e m； 作为匹配0=m1的第一象限直线的Bresenham算法，P134的示例：在Bresenham中绘制直线算法以生成从(0，0 )到(8，3 )的直线段。 (0，0 )、(1，0 )、(2，1 )、(3，1 )、(4，2 )、(5，2 )、(6，2 )、(7， 3 )当e(xi)0时，即当f (Xi )0) f (Xi1)=2* e (Xi1) *x=2* (e (Xi )y /x ) ) *x=f (Xi ) 2y，0=m=0时(即当f (Xi )=0) f (Xi1)=2* e (Xi1) *x=2* (e (Xi )y/) 2y-2x，f (x2 )=2* e (x2 ) *x=2* (y /x-0.5 ) *x=2y -x，f(Xi1 )和f(Xi )之间的关系如何？ f的初始值？ Inter.bresenham-Line(x1，y1，x2，y2，color)intx1，y1，x2，y2，color； intx，y，x，y，e； x=x1； y=y1； x=x2-x1； y=y2-y1； e=2*y-x； for(i=1； i=0)y=y 1； e=e-2*x； x=x 1； e=e 2*y； ，(0=适合mx ) temp=x； x=y； y=temp； interchange=1； elseinterchange=0； e=2*y-x； for(i=1； i=0)if(interchange=1)x=x s1； elsey=y s2； e=e-2*x； if(interchange=1)y=y s2； elsex=x s1； e=e 2*y； 1，适用于各种象限和各种倾斜线的典型Bresenham算法，P136示例：使用典型的Bresenham线算法生成AB线，并写入起点a (0，0 )、终点b (-8，4 )和轨迹点坐标。 适用于、和各种象限以及各种斜率直线的典型Bresenham算法如何生成具有指定宽度的直线，显示(0，0 )、(-1，-1)、(-2，-1)、(-3，-2)、(-4，-2)、(-5，-3)、(-6，-3)、(-7，-4)、 (1)最简单的方法是利用“线刷”。 直线的斜率|m|1表示水平线刷，直线段的基本属性包括线型、宽度和颜色。 线型有实线、虚线、虚线等。 putpixel(x，y-1，RED) putpixel(x，y，RED) putpixel(x，y 1，RED )使用垂直笔刷生成putpixel(x-1，y，RED )的putpixel(x，y， 用RED) putpixel(x 1，y，RED )水平笔刷创建宽度为3的直线段，采用“线性笔刷”的优点：简单易行。示例：如何使用画笔创建宽度为3的直线？ (3)区域填充，(2)正方形刷子也可以用上述方法生成粗曲线。 如果生成半径为16、线宽为4的圆，则会生成半径为14和17的两个同心圆，并填充两个圆之间的区域。 另外，在产生闭合圆周时，如果产生第一象限的1/8圆弧，则可利用对称点获得其馀部分。 圆弧的扫描变换：决定最适合圆弧的近似像素的集合。按扫描线顺序写入这些像素。方法1:使用圆形方程式并且y2=r2-x2，x从0增加到r/2，以利用方程式确定y值，其效率较低且利用均方、减法和平方根。 x=r.cos，y=r.sin，从0变为/4，计算相应的x和y值，但是计算正弦和馀弦值需要比以前更长的时间。方法利用bersenham画圆的算法、中点法、正负法、逐点插值法、以中心为原点，半径为r (顺时针画圆)。 仅考虑到第1象限的1/8圆周的情况，可以对称地求出其馀的部分。 圆的方程式是：X2 Y2-R2=0、b、a、3.2.1圆弧的bresenham算法p137、3.2圆和椭圆的生成算法，D(Si)=XSi2 YSi2-R20，Si在圆之外时D(Ti)=XTi2 YTi2-R20，Ti接近圆，Ti di=0，2点都是di0，Si接近圆周，Si现在(从Pi-1的右下)寻找从a点向右下显示弧AB的点。 图中的点Pi-1表示圆弧上的点被选择，依据圆弧a-b的方向，下一点应该从Si或者Ti中选择。 显然应该在Si和Ti中选择离AB最近的点。 对于起点A(0，r )，S1(1，r )，T1(1，r-1)d1=1r2-r2=3-2r，对于起点，d1的值是多少？如何快速计算di？ 将di 1和di的关系导出如下。 di=d (si ) d (ti )=(Xi-1 ) 2yi-12-r2(Xi-1 )2(yi-1-1 )2- r2(1)如果di=0，则为ti，Xi 1=Xi-1 1，Yi 1=Yi-1-1.Pi-1(Xi-1，Yi-1).Si(Xi-1 1，Yi-1).Si(Xi-1 1，yi-1 ) Yi-1-1).Ti 1(Xi-1 2，yi-1-2 ) di1=d (si1) d (ti1)=(Xi-1-2 )2- r2(yi-1-2 )2- r2=di4(Xi-1-yi-1 ) 10，黄铜线(r，color)intr，颜色； intx，y，d； x=0； y=r； d=3-2*r； while(x=0)d=d 4*(x-y) 10； y=y-1； elsed=d 4*x 6； x=x 1； 例如，圆弧的bresenham算法，x，y，0123456789，9876543210，P139 :使用在bresenham中画圆的算法，生成X2 Y2-64=0的第一象限的1/4圆弧。 同样，可以导出中心不在原点的第一象限圆弧的di的递归式(di 1和di的关系)。 圆方程式为：(X-Xc)2 (Y-Yc)2-R2=0，BresenhamCircle(xc，yc，r，color)intxc，yc，r，color； intx，y，d； x=0； y=r； d=3-2*r； while(x=0)d=d 4*(x-y) 10； y=y-1； elsed=d 4*x 6； x=x 1； 适用于if(x=y)circle-pointS(x，y，color) 、中心为(xc，yc )的Bresenham绘制圆周算法。 circle-pointS(x、y、color)putpixel(x xc、y yc、color )； putpixel(y xc，x yc，color) putpixel(y xc，-x yc，color )； putpixel(x xc，-y yc，颜色) putpixel(x xc，-y yc，颜色)； putpixel(-y xc，-x yc，color )； putpixel(-y xc，x yc，color )； putpixel(-x xc，y yc，color )； 对于，(xc，yc )，y，x，对称点，扫描变换椭圆，方法1:是椭圆方程式，根据x2/a2 y2/b2=1，对第1象限内的每0=x=1的x值，代入方程式，求对应的y值，x=a.cos，y=b.sin，从0变为/2 计算对应的x和y值，速度慢的方法2:采用中点法，考虑椭圆方程式：F(x，y)=b2x2 a2y2-a2b2=0椭圆的对称性，仅考虑第一象限椭圆弧的生成，分为上下两部分，以切线斜率为-1的点为边界点。(0，0 )，3.2.2椭圆的生成(中点法)，椭圆方程式：F(X，Y)=b2X2 a2Y2-a2b2=0，生成中点法椭圆，di=F(Mi)=F(Xi 1，yi-0.5 )=B2 (xi1 )2a2 (yi-0.5 )2- a2 B2 (1) di=0时Ti，即Xi 1 Yi 1=Yi-1下一个中点是Mi 1(Xi 2，Yi-1.5).Pi(Xi，Yi).Si(Xi 1，Yi).Mi(Xi 1，Yi-0.5).Ti(Xi 1，Yi-1).Mi 1(Xi 2，Yi-1).Mi 1(Xi 2，Yi-1.5).(Xi 2，yi-2 ) di1=f (mi1) Yi-1.5 )=B2 (xi2 )2a2 (yi-1.5 )2- a2 B2=B2 (xi1 )2a2 (yi-0.5-1 )2- a2 B2=di2 (2xi3) a2 (-2yi2)，2 .下部椭圆弧. Pi(Xi，Yi).Bi(Xi，Yi-1).Mi.Ti(Xi 1，yi-1 )其中yi-1 )为di=F(Mi)=F(Xi 0.5，yi-1 )，如果di=0则为di0，如果Mi在椭圆之外，则Bi接近椭圆，取得Bi (从Pi向正下方进一步) di的递归式：用中点法生成椭圆，di=F(Mi)=F(Xi 0.5， Yi-1 )=b2(Xi0.5)2a2(yi-1 )2- a2b2(1)当di=0时，Bi，即Xi 1=Xi，Yi 1=Yi-1阶中点是Mi 1(Xi 0.5，Yi-2).Pi(Xi，Yi).Bi(Xi，Yi-1).Mi.Ti(Xi 1，yi-1 )，其中Yi-2).Mi 1.(Xi 1，Yi-2 )其中Mi 1(Xi 0.5，yi-2 ) di1=f (mi1)=f (Xi0.5yi-2 )=b2(Xi0.5)2a2(yi-2 )2- a2b2=di2(-2 y I3)，下椭圆弧，上部d初始值：d1=F(1， B- 0.5 )=1* B2