《基本图形生成算法剖析》由会员分享，可在线阅读，更多相关《基本图形生成算法剖析（75页珍藏版）》请在金锄头文库上搜索。
1、* p 如何在指定的输出设备上根据坐标描述构造基 本几何图形（点、直线、圆、椭圆、多边形域 、字符串及其相关属性等）? 第3章 基本图形生成算法 1 * 2 p 图形生成的概念 p 直线段的扫描转换 p 圆的扫描转换 p 多边形的扫描转换与区域填充 p 属性处理 p 反走样技术 第3章 基本图形生成算法 2 * 点的生成 点是图形中最基本的图元，直线、曲线以及其它的图元都是 点的集合。 在几何学中，一个点既没有大小，也没有维数，点只是表示 坐标系统中一个位置。 在计算机图形学中，点是用数值坐标来表示的。在直角坐标 系中点由（x,y) 两个数值组成的坐标表示，在三维坐标系中点是 由（x,y,z)
2、三个数值组成的坐标表示。 在输出设备上输出一个点，就要把应用程序中的坐标信息转 换成所用输出设备的相应位置。对于一个CRT监视器来说，输出一 个点就是要在指定的屏幕位置上打上电子束，使该位置上的荧光 点亮。 在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程 序语言中都有描点语句。例如C语言为putpixel(x,y,color) ,putpixel(放,摆-像素)。 3.1 图形生成的概念 3 * o 图形的生成：是在指定的 输出设备上，根据坐标描 述构造二维几何图形。 o 图形的扫描转换：在光栅 显示器等数字设备上确定 一个最佳逼近于图形的像 素集的过程。 用像素点集逼近直线 3.
3、1 图形生成的概念 4 * 3.1 图形生成的概念 5 * 在数学上，理想的直线是没有宽度的、由 无数个点构成的集合。当我们对直线进行光栅 化时，只能在显示器所给定的有限个像素组成 的矩阵中，确定最佳逼近该直线的一组像素， 并且按扫描线顺序对这些像素进行写操作，这 就是通常所说的直线的扫描转换。 通常用于直线光栅化的算法有数值微分法（ DDA）、中点画线法和Bresenham画线算法。 3.2 直线的扫描转换 6 * 直线光栅化算法 o 直线段生成 o 求与直线段充分接近的像素集 7 * o 直线的绘制要求 （1）直线要直； （2）直线的端点要准确，无定向性无断裂； （3）直线的亮度、色泽要均
4、匀； （4）画线的速度要快； （5）具有不同的色泽、亮度、线型等。 3.2 直线的扫描转换 8 * o 解决的问题：给定直线两端点P0(x0,y0)和 P1(x1,y1)，画出该直线。 o 数值微分法(DDA算法) o 中点画线算法 o Bresenhan算法 3.2 直线的扫描转换 9 * 已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为： DDA（Digital Differential Analyzer）画线算法也 称数值微分法，是一种增量算法。它的算法实质是用数值方法 解微分方程，通过同时对x和y各增加一个小增量，计
5、算下一 步的x、y值。 3.2.1 数值微分法(DDA法) 10 * o 假定端点坐标均为整数，取 直线起点P0 (x0, y0)作为初 始坐标。画线过程从x的左端 点x0开始，向x右端点步进， 每步x递增1，计算相应的y 坐标， y=kx+b，取像素点 （x，round（y）作为当 前点的坐标。 o 问题:每步需要用到浮点数的 乘法、加法和取整运算，效 率不高。怎么办? 3.2.1 数值微分法(DDA法) 11 * o 增量算法 o 因为: y=kx+b,所以: yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k =yi+k (xi,yi)(xi+1,yi+k) 3.2.1 数值微
6、分法(DDA法) r例图中 k1 X=1 Y=k r将算得的直线上每个点的当前坐标，按四舍五入得到光栅点的位置 r浮点数取整 : yi=round(yi)=(int)(yi+0.5) 12 * 有： yi+1=yi+k X r若0k y q因光栅单位为1， q可以采用每次x方向增加1， q而y方向增加k的办法得到下一个直线点。 因: 3.2.1 数值微分法(DDA法) 演示 说明 13 * 例：画直线段P0(0,0)-P1(5,2) 解：斜率K=2/5=0.4，所 以X方向每次步长为1，Y方向递增 K。初始点为（0，0）。 x int(y+0.5) y 000 100.4 210.8 311.
7、2 421.6 522.0 当 k 1时，必须把x，y地位互换 yi+1=yi+k 14 * 程序实现： void DDALine(int x0,int y0,int x1,int y1,int color) int x; float dx,dy,k,y; dx=x1-x0; dy=y1-y0; k=dy/dx; y=y0; for(x=x0;x取P1; 此时再下一个像素的判别式为 d1=F(x+2, y+0.5)(F(x,y)=ax+by+c=0 ) =a(x+2)+b(y+0.5)+c = a(x +1)+b(y +0.5)+c +a =d+a； 增量为a d=F(M)=F(x+1, y+
8、0.5)=a(x+1)+b(y+0.5)+c 22 * 若dM在直线下方-取P2; 此时再下一个象素的判别式为 d2= F(x+2, y+1.5) =a(x+2)+b(y+1.5)+c = a(x+1)+b(y+0.5)+c +a +b =d+a+b ； 增量为ab 3.2.2 中点画线算法 d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c 23 * o 画线从(x0, y0)开始，d的初值（F(x,y)=a*x+b*y+c） o d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0+0.5)+c = ax0 +a+by0+0.5b+c = ax0+b
9、y0+c+a+0.5b =F(x0, y0)+a+0.5b = a+0.5b 注：由于（ x0, y0）在直线上，故F(x0, y0)=0 o 所以，d的初始值d0 = a+0.5b 3.2.2 中点画线算法 24 * 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。用2d代替d 后，d0=2a+b n d的增量都是整数(d1:2a, d2:2(a+b) 如果进一步把算法中2*a改为a+a等等，那么 这个算法不仅只包含整数变量，而且不包含乘除法 ，适合硬件实现。 3.2.2 中点画线算法 演示说明 d的初始值d0 = a+0.5b 25 * 解: K=dy
10、/dx=2/5=0.41,故x方向增1,y方向根据d的符号判断. a=y0-y1=-2; b=x1-x0=5; d0=2a+b=1; d1=2a=-4; d2=2(a+b)=6; x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 1 例:按照中点画线算法，确定直线（0，0）（5，2） 的点亮像素。列出计算过程，并列出所选像素坐标。 在d0的情况下，取正右方像素P1， 判断再下一像素应计算 d1=a(x+2)+b(y+0.5)+c =d+a ,故d的增量为a. 在d0的情况下，取右上方像素P2， 判断再下一像素应计算 d2=a(x+2)+b(y+1.5) = d
11、+a+b,故d的增量为a+b. d的初始值d0 = a+0.5b 用2d代替d后，d0=2a+b d的增量都是整数 d1：2a d2：2(a+b) 26 * 程序实现： void MidpointLine (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) if (d0) x+; y+; d+=d2; else x+; d
12、+=d1; drawpixel (x, y, color); 在d=0的情况下(M在直线(Q点 )上方)，取正右方像素P1,再下一 个像素的判别式为d1. 27 * 3.2.3 Bresenham画线算法 Bresenham算法是计算机图形学领域使用最广 泛的直线生成算法。假设直线斜率 k 0, 1。 Bresenham画线算法的基本原理是：按直线从 起点到终点的顺序计算直线与各垂直网格线的交点 ，然后确定该列像素中与此交点最近的像素。 这是计算机科学教授Jack Elton Bresenham最知名的 一项创新，开发于1962年。 28 * o 因为斜率较小，所以每条垂直线上最多选取一 个像素。如果像素点 Pi-1 (xi-1，yi-1) 是已经 选定的离直线最近的像素点，现在要决定下一 个像素点Pi是Ti 还是Si 。如图3
