第3章 基本光栅图形生成技术显示器是由离散像素组成的矩阵，在绘制具有连续性显示器是由离散像素组成的矩阵，在绘制具有连续性 质的直线、曲线或区域等基本图形时，需要确定最佳逼近质的直线、曲线或区域等基本图形时，需要确定最佳逼近 它们的像素，这个过程称为它们的像素，这个过程称为光栅化光栅化。当光栅化按照扫描线。当光栅化按照扫描线 的顺序进行时，它被称为的顺序进行时，它被称为扫描转换扫描转换。对于一维图形，在不。对于一维图形，在不 考虑线宽时，用一个像素宽的直、曲线来显示图形。二维考虑线宽时，用一个像素宽的直、曲线来显示图形。二维 图形的光栅化必须确定区域对应的像素集，并用指定的属图形的光栅化必须确定区域对应的像素集，并用指定的属 性或图案显示之，即区域填充。性或图案显示之，即区域填充。光栅化和扫描转换是光栅光栅化和扫描转换是光栅 图形学的基本问题，其算法的好坏对系统的效率有直接的图形学的基本问题，其算法的好坏对系统的效率有直接的 关系。关系。VCVC提供了一个显示像素函数：提供了一个显示像素函数：SetPixelSetPixel(x,y, color);(x,y, color);而在而在TurboTurbo中显示像素函数为：中显示像素函数为：putpixel putpixel (x,y,color); (x,y,color);其中，其中，x x和和y y为像素的位置坐标，为像素的位置坐标，colorcolor为像素的颜色。为像素的颜色。安徽师范大学数学计算机科学学院 计算机图形学图形光栅化光栅化图形的处理本章的主要内容确定最佳逼近的象素集合 及其颜色，进而在光栅图 形显示器上显示一个图形 的过程。1、区域填充。2、线宽和线 型。3、字符。4、图形的裁 剪。5、图形的反走样。对 一个图形进行光栅化处理时 所出现的走样现象进行处理 。安徽师范大学数学计算机科学学院 计算机图形学直线（段）的光栅化区域填充安徽师范大学数学计算机科学学院 计算机图形学图案填充具有一定宽度的直线安徽师范大学数学计算机科学学院 计算机图形学点阵字符 点阵字库中的位图表示安徽师范大学数学计算机科学学院 计算机图形学二维图形的裁剪安徽师范大学数学计算机科学学院 计算机图形学反走样前的直线段反走样后的效果安徽师范大学数学计算机科学学院 计算机图形学 直线的扫描转换: 确定最佳逼近于该直线的一 组象素，并且按扫描线顺序，对这些象素进行 写操作。 三个常用算法： 数值微分法（DDA）中点画线法 Bresenham算法3.2 3.2 线的生成算法线的生成算法安徽师范大学数学计算机科学学院 计算机图形学1 数值微分(DDA)法 Digital Differential Analyzer 基本思想已知过端点 的直线段L：直线斜率为 从 的左端点 开始，向 右端点前进。步长 =1(个象素)，计算相应的y坐标 ；取象素 点(x, round(y)作为当前点的坐标(k 1时)。安徽师范大学数学计算机科学学院 计算机图形学作为最底层的光栅图形算法，在通常的 CAD/图形系统中，会被大量应用，因此，哪 怕节约一个加法或减法，也是很了不起的改进 。 由此出发点，导致增量算法的思想。 首先考虑k 1的情形。这种方法非常直观、容易理解，但是效 率较低。这是因为每步运算中都有一个浮点 乘法与一个舍入运算。安徽师范大学数学计算机科学学院 计算机图形学考虑到即：当x每递增1，y递增k(即直线斜率)； 例：画直线段 x floor(y+0.5) y 000 100.4 210.8 311.2 421.6 522.0 注：网格点表示象素中心K=0.4void DDALine(int x0,int y0,int x1,int y1,int color) int x; float dx, dy, y, k; dx = x1-x0, dy=y1-y0; k=dy/dx; for (x=x0, y=y0; xx1;x+) putpixel (x, floor(y+0.5), color); y=y+k;安徽师范大学数学计算机科学学院 计算机图形学注意上述分析的算法仅适用于k 1的情形 。 当 k 1时，会如何？(答案见下页)k 1 示意图0 1 2 3 4 5321Line: P0(0, 0)- P1(2, 5)54即：当y每递增1，x递增1/k. 安徽师范大学数学计算机科学学院 计算机图形学安徽师范大学数学计算机科学学院 计算机图形学void ddaline(int x0,int y0,int x1,int y1,int color) int x; float dx, dy, y, k; dx = x1-x0, dy=y1-y0; k=dy/dx, x=x0; for (y=y0; yy1; y+) putpixel (floor(x+0.5), y, color); x=x+1/k;void ddaline(int x0,int y0,int x1,int y1,int color) int i; float dx, dy, length,x,y; if (fabs(x1-x0)=fabs(y1-y0) length=fabs(x1-x0); else length=fabs(y1-y0); dx = (x1-x0)/length; dy=(y1-y0)/length; i=1;x= x0;y= y0; while(i00时，像素时，像素p2( (x xi i1 1，y yi i1)1)与直线上理想位置更接近；与直线上理想位置更接近； 当当d di i=0=0时，两个像素与直线上理想位置一样接近，可约定取时，两个像素与直线上理想位置一样接近，可约定取p2( (x xi i1 1，y yi i1)1)。yi+1yyixixi+1d2d1 pp2p1如果选择右上方像素，即： ，则：如果选择右方像素，即： ，则：对于每个整数对于每个整数x x，从线段的坐标端点开始，循环的进行误差量从线段的坐标端点开始，循环的进行误差量 的计算。在起始像素的计算。在起始像素( (x x0 0，y y0 0) )的第一个参数的第一个参数d d0 0为：为：yi+1yyixixi+1d2d1 pp2p1例：ixi yie 100-1 2103 321-3 4311 542-5 652 -1 安徽师范大学数学计算机科学学院 计算机图形学void Bresenham_Line (int x0,int y0,int x1, int y1,int color) int dx,dy,e,i,x,y;dx = x1-x0, dy = y1- y0, e=2*dy-dx; x=x0, y=y0;for (i=0; i=0) y+; e=e+2*dy-2*dx; else e=e+2*dy;思考:如何将Bresenham画线算法推广到k1情形 。安徽师范大学数学计算机科学学院 计算机图形学void bresenhamLine02 (int x0,int y0,int x1, int y1,int color)int dx,dy,e,i,x,y;dx = y1-y0, dy =x1- x0, e=2*dy-dx; x=y0, y=x0;for (i=0; i=0) y+; e=e+2*dy-2*dx; else e=e+2*dy;习题3.1安徽师范大学数学计算机科学学院 计算机图形学3.2 圆（弧）的扫描转换算法直角坐标法、参数方程法、中点画圆算法 和Bresenham画圆算法等。1、直角坐标法直角坐标法的缺点：1）效率太低。2）在圆的左右两 侧象素太稀疏。让x从xc-r到xc+r变化，每次递增1，就可以求出对应的y坐标。安徽师范大学数学计算机科学学院 计算机图形学draw_circle01(x1,y1,r,c) int x,y; for(x=x1-r;x #include main() int gdriver=DETECT,gmode; initgraph( draw_circle01(150,150,100,1); /*circle01.*/安徽师范大学数学计算机科学学院 计算机图形学2、参数方程法给出圆的极坐标方程：让从0到2变化，每次递增/180，可以求出圆周 上的离散象素点。该算法生成的象素均匀。但含有三角函数运算， 效率太低。安徽师范大学数学计算机科学学院 计算机图形学draw_circle02(x1,y1,r,c) int x1,y1,r,c; float x,y,theta; for(theta=0; theta #include #define PI 3.14 main() int gdriver=DETECT,gmode; initgraph( draw_circle02(150,150,100,1); /*circle02.c*/安徽师范大学数学计算机科学学院 计算机图形学3、中点画圆法圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。(y,x)(x,y)(-x,y)(-y,x)(-y,-x)(-x,-y)(x,-y)(y,-x)安徽师范大学数学计算机科学学院 计算机图形学考虑中心在原点，半径为R 的第二个8分圆。构造函数：构造判别式（圆方程）安徽师范大学数学计算机科学学院 计算机图形学若 d=0, 则应取P2为下一象素，而且下一象素的判别式为第 一个象素是（0,R）， 判别式d的初始值为安徽师范大学数学计算机科学学院 计算机图形学MidPointCircle(int r, int color) int x,y;float d;x=0; y=r; d=1.25-r;putpixel (x,y,color); while(x=0, 则应取P2为下一象素，而且下一象素的判别式为第 一个象素是（0,R）， 判别式d的初始值为MidPointCircle(int r, int color) int x,y,e;x=0; y=r; e=1-r;putpixel (x,y,color); while(x2a2y， 也就是说，在该 椭圆弧上一定存 在点P，在该点处 2b2x=2a2y。该点处的法向量 两分量相等上半部分 下半部分P（0，b）（a，0）安徽师范大学数学计算机科学学院 计算机图形学先讨论上半椭圆弧：假设当前象素为（xp,yp），那么 下一对侯选象素的中点为（xp+1,yp-0.5）。因此，判别式如果 ,应取正右方的 象素（xp+1,yp）；如果 , 应取右下方的象素（xp+1,yp-1）。与圆的中点扫描算法类似， 我们也可以采用增量算法计算判别式以提高计算效率。下半部分P（xp,yp）（xp+1,yp-1）（xp+1,yp）安徽师范大学数学计算机科学学院 计算机图形学如果 ,应取正右方的象素（xp+1,yp）；该象素 的判别式为如果 ,应取右下方的象素（xp+1,yp-1）。该象 素的判别式为初始时，安徽师范大学数学计算机科学学院 计算机图形