计算机图形学 ppt课件.ppt

《计算机图形学 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机图形学第四章基本图形生成算法引言光栅显示器可以看做一个像素的矩阵，每个像素可以用一种或多种颜色显示，在显示器上显示的任何一种图形，实际上都是一种或多种像素的集合。确定一个像素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。过程：确定有关像素→对像素进行写操作（设备驱动程序实现）主要工作：确定最佳逼近于图形的像素集裁剪和反走样基本的图形生成算法直线的扫描转换圆和椭圆的扫描转换填充算法线宽和线型字符裁剪反走样直线直线是基本的、常用的图形元素。9/20/2021绘制直线的要求生成的直线要直：选择最靠近直线的可寻址点来逼近直线。理想的绘制9/20

2、/2021绘制直线的要求起点和终点要准：在绘制直线的过程中由于受精度的影响，所绘直线的终点与原终点有一个累积误差，导致直线的终点不准。9/20/2021绘制直线的要求直线的粗细要均匀：由于选点不均匀，造成直线粗细不均匀，直观上反映出直线的亮度不均匀9/20/2021实际绘制9/20/20214.1直线的扫描转换一个像素线宽的直线的扫描转换逐点比较法数值微分法(DDA)中点画线法Bresenham画线算法1.逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线。保证要绘制的点尽可能的靠近

3、直线而不发生远离直线的趋向。9/20/2021绘制思路由一个点到下一个点的走法是只在X方向或Y方向走一步。9/20/2021计算偏差（确定X和Y的最大走向）这里X是最大的走向。K1K2(xA,yA)(7,5)’9/20/2021设=tg-tg于是有1)=0，点在直线上；2)>0，点在直线上方；3)<0，点在直线下方。设偏差计算公式为：9/20/2021偏差计算可以简化为根据计算出偏差，然后确定下一步的走向。以直线(0,0)-(7,5)为例，初始：x0=0,y0=0,则F0=0第一步：第二步：=F0-YA=F1+XA9/20/2021偏差递推公式1）时，走X方

4、向一步，即2）时，走Y方向一步，即9/20/2021偏差递推公式以上讨论的是起点为原点，X为最大步长方向的情况，对于起点是任意点，最大步长方向为其他情况下的绘制直线的偏差计算和偏差判别，自行推导。终点判别判别终点的方法：设立计数器，计数取X或Y方向的最大增量值（计长方向），在计长方向每走一步，计数器减1，直到计数器值为零为止。9/20/2021绘制直线9/20/20212.数值微分法DDA(DigitalDifferentialAnalyzer)该算法是建立在微分方程的基础上。由点(xA,yA)到点(xB,yB)的直线段满足的微分方程为：9/20/2021因此有则有令有9/2

5、0/2021直线的扫描转换原理:k＝(y1-y0)/(x1-x0)对于点(x,y),每步递增1，计算y=kx+B,取:(x,[y])(x1,y1)(x0,y0)(x,y)xx1xx0y直观又可行但效率低下：一个浮点乘法和一个舍入运算直线的扫描转换数值微分法改进算法:yi+1=kxi+1+B=k(xi+Δx)+B=kxi+B+kΔx=yi+kΔx=yi+Δy当Δx=1时,有yi+1=yi+kDDA绘制的直线9/20/2021直线的扫描转换数值微分法(程序)DDAline(x0,y0,x1,y1,color)intx0,y0,x1,y1,col

6、or{intx;floatk,y;k=(y1-y0)/(x1-x0);y=y0for(x=x0,x<=x1,x++){Putpixel(x,int(y+0.5),color)y=y+k}}举例用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段动画演示：数值微分画线算法（DDA）xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5直线的扫描转换3.中点画线法原理（0<斜率<1）:MPP1P2P(xp,yp)P1(xp+1,yp),P2(xp+1,yp+1)M(xp+1,yp+0.5)Q直线

7、的扫描转换F(x,y)=ax+by+c=0对于在直线上的点，F(x,y)=0;在直线上方的点，F(x,y)>0;在直线下方的点，F(x,y)<0将M代入上式,判断F(M)>0或者F(M)<0MPP1P2Q中点画线法由直线一般方程有:MP1P2Q直线的扫描转换P(xp,yp),P1与P2的中点M(xp+1,yp+0.5)d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+ci.若d>0，即M在直线线上方时，取P1点，则d1=F(xp+2,yp+0.5)=a(