计算机图形学 - GOOGLE CODE.ppt

《计算机图形学 - GOOGLE CODE.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章输出图元所谓图元的生成，是从图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。这个过程我们也称为扫描转换,主要工作包括确定像素集合及其颜色，显示图形对象。本章讨论这些常用图形对象的扫描转换算法以及图案、线宽、线型等属性的实现方法，最后两节介绍用于改善光栅图形的视觉效果的技术——图形保真技术和半色调技术。1图形显示前需要：扫描转换+裁剪●裁剪---〉扫描转换：最常用，节约计算时间。●扫描转换---〉裁剪：算法简单；●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内存。常用于字符显示。第三章输出图元2线

2、段的扫描转换算法圆和椭圆的扫描转换保持图形对象的数学性质多边形的扫描转换区域填充算法线宽和线型填充图案字符技术图形保真技术半色调技术本章内容第三章输出图元3线段的扫描转换算法圆和椭圆的扫描转换保持图形对象的数学性质多边形的扫描转换区域填充算法线宽和线型填充图案字符技术图形保真技术半色调技术内容线段的扫描转换算法圆和椭圆的扫描转换保持图形对象的数学性质多边形的扫描转换区域填充算法线宽和线型填充图案字符技术图形保真技术半色调技术内容43.1线段的扫描转换DDA算法Bresenham画线算法并行画线算法画线算法的讨论5DDA扫描转换直线段扫描转换直线段求与直线段充分

3、接近的像素集假设直线段的宽度为1像素间均匀网格整型坐标系线段的扫描转换6DDA扫描转换直线段数字微分(DDA)画线算法（digitaldifferentialanalyzer）条件：待扫描转换的直线段：P1(x1,y1),P2(x2,y2)∆x=x2-x1,∆y=y2-y1参数方程：x=x1+∆x*ty=y1+∆y*t0≤t≤1直接求交算法：划分区间[0,1],dt=1/n计算坐标.取整.7DDA扫描转换直线段复杂度：乘法+加法+取整DDA增量算法xi+1=x1+∆x*ti+1=xi+∆x*dt=xi+xincyi+1=y1+∆y*ti+1=yi+∆y*dt=

4、yi+yinc复杂度：加法+取整8DDA扫描转换直线段算法描述voidDDA_line(intx1,y1,x2,y2){intdeltax,deltay,n,i;floatx,y,xinc,yinc;deltax=x2-x1;deltay=y2–y1;if(abs(deltax)>abs(deltay))n=abs(deltax);elsen=abs(deltay);xinc=(float)deltax/n;yinc=(float)deltay/n;x=x1;y=y1;write_pixel(round(x),round(y));for(i=0;i

5、){x+=xinc;y+=yinc;write_pixel(round(x),round(y));}}9DDA扫描转换直线段DDA算法缺点需要进行浮点数运算运行效率低不便于用硬件实现10Bresenham扫描转换直线段Bresenham画线算法目标：消除DDA算法中的浮点运算条件：同DDA算法斜率：0≤k≤1直线段的隐式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+by+c=0式中a=y0-y1,b=x1-x0,c=x0y1-x1y011Bresenham扫描转换直线段分析线段的端点坐标:(x1,y1)和(x2,y2)线段方程:y=k*x+b，

6、将平面以(x1,y1)为坐标原点划分为八个卦限，考虑线段在第一卦限，即Δx=x2-x1>0，Δy=y2-y1≥0，并且Δx≥Δy的情况此时xinc=1，yinc=k（0≤k≤1）12Bresenham扫描转换直线段Bresenham画线算法示意图13Bresenham扫描转换直线段Bresenham画线算法的特点：只包括整数的加法、减法和左移（乘2）操作，效率高。适合用硬件实现。!请将第一卦限的Bresenham画线算法推广到其它卦限.14并行画线算法有p个处理器。将线段沿着x方向分为p个区段，区段的宽度为∆xp=ceiling(∆x/p)=(∆x+p-1)d

7、ivp其中∆x=xe-xs为线段宽度ceiling(∆x/p)为≥∆x/p的最小整数div为整数除法运算再将这p个区段按照从左向右的次序依次编号为0,1,…,p-1,则编号为i的区段的起点的x坐标xi=xs+i*∆xp15并行画线算法计算编号为i的区段的起点的y坐标yi和判别式fi的初始值。区段的高度∆yp=k*∆xpyi=y1+round(i*∆yp)ei=di-0.5=k*i*∆xp-round(i*∆yp)+k-0.5fi=2*∆x*ei=2*∆y*i*∆xp-2*∆x*round(i*∆yp)+2*∆y-∆xround(i*∆yp)=int(i*∆yp

8、+0.5)=(2*∆y*i*∆xp+∆