《基本图形光栅化》PPT课件

《《基本图形光栅化》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机图形学第3章基本图形光栅化主讲教师：尉秀梅第3章基本图形光栅化3.1直线的光栅化3.2圆的光栅化3.3区域填充3.4字符表示3.5反走样3.1直线的光栅化在数学上，理想的直线是没有宽度的、由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序对这些像素进行写操作，这就是通常所说的直线的扫描转换。通常用于直线光栅化的算法有数值微分法（DDA）、中点画线法和Bresenham画线算法。3.1.1DDA算法DDA（DigitalDifferentialAnalyzer）法

2、是根据直线的微分方程来画直线的。设直线的起点坐标为Ps(xs,ys)，终点坐标为Pe(xe,ye)，令△x=xe-xs，△y=ye-ys，则要绘制的直线的微分方程为取时间步长为1/△t，则可得上述微分方程数值解的递推公式为3.1.1DDA算法通常情况下，直线的方向分为8个不同的区域，每个区域的处理方法有所不同。区域dxdy1a1△y/△x1b△x/△y12a-1△y/△x2b-△x/△y13a-1-△y/△x3b-△x/△y-14a1-△y/△x4b△y/△x-13.1.1DDA算法例：画直线段P0(0,0)--P1(5,2)解：斜率K=2/5=0.4，

3、所以X方向每次步长为1，Y方向递增K.初始点为（0，0）。xint(y+0.5)y000100.4210.8311.2421.6522.03.1.2中点画线法为了讨论方便，假设直线的斜率在0到1之间，若直线在x方向上增加一个光栅单位，则在y方向上的增量只能在0到1之间。设P（x,y）是直线上的一点，与P点最近的网格点为（xi,yi）,那么，下一个与直线最近的像素只能是正右方的网格点PB（xi+1,yi）或右上方的网格点PT（xi+1,yi+1）两者之一。再以点M（xi+1,yi+0.5）表示PB和PT的中点，设Q是直线与垂直线x=xi+1的交点。显然，若

4、M在Q的下方，则PT离直线较近，应取PT为下一个像素点，否则应取PB做为下一个像素点，这就是中点画线算法的基本思想。3.1.2中点画线法设直线的起点和终点分别为（x0,y0)和(x1,y1)，则直线方程为F(x,y)=ax+by+c=0其中a=y0-y1，b=x1-x0，c=x0y1-x1y0。构造判别式：采用增量计算d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c在d≥0的情况下，取正右方像素PB，判断下一像素应计算d1=a(x+2)+b(y+0.5)+c=d+a在d<0的情况下，取右上方像素PT，判断下一像素应计算d2=a(

5、x+2)+b(y+1.5)=d+a+bd的初始值d0=a+0.5b3.1.2中点画线法由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。3.1.3Bresenham画线算法原理:过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。若s

6、。设直线的起点和终点分别为（x1,y1)和(x2,y2)，则直线方程为y=y1+dy/dx(x-x1)，其中dx=x2-x1，dy=y2-y1直线方程经变换后可表示为从（0，0）到(dx,dy)，方程可简化为y=dy/dx*xs-t=2**(xi-1+1)-2yi-1-1s=*(xi-1+1)-yi-1t=(yi-1+1)-*(xi-1+1)dx(s-t)=2(xi-1dy-2yi-1dx)+2dy-dx3.1.3Bresenham画线算法递推公式：当di≥0时，选Ti,当di<0时，选Si，di的初值：令di=dx(s-t),则di+1=2(xidy-

7、2yidx)+2dy-dxdi+1-di=2dy(xi-xi-1)-2dx(yi-yi-1)di=2(xi-1dy-2yi-1dx)+2dy-dx3.1.3Bresenham画线算法3.1.3Bresenham画线算法上面讨论的是直线斜率0≤k≤1的情况。对于一般情况可作如下处理：（1）当斜率的绝对值k>1时，将x、y和dx、dy对换，即以y向作为增长方向，y总是增1（或减1），x是否增减1，则根据的符号判断：d≥0时x增1（或减1）；d<0时，x不变。（2）根据dx和dy的符号来控制(x或y)增1还是减1。双步算法1987年有人提出二步法，即每循环一次

8、不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。下图为