教育学图形学.pptx

第3章 基本图形 生成算法第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)2 物体的形状和颜色可用象素矩阵或直线线段和多边形填充区域等基本几何结构来描述。点和直线段是最简单的几何成分，其它可供构造图形的输出图元有圆及其它圆锥曲线、二次曲面和多边形填充区域以及字符串等。而二维图形的生成是三维图形生成的基础，研究计算机生成图形需先从二维图形的生成开始。下面将讨论一些基本二维图元生成技术和算法，以光栅图形系统的扫描转换方法为基础。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)3最基本的图形显示方式是直线方式。实际上，无论什么复杂图形，它们无非是由直线段和曲线段组成。而对于曲线及各种复杂的图形，可以将其离散成许多小直线段，连接各直线来逼近欲生成的曲线或其它复杂图形，所以一般图形都可以看成是由直线段组成。因此，直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。在光栅显示器上显示图形是将线段上所有象素点亮的过程。如果已知直线段两个端点，可以有很多种不同的数学方法来决定应改变在两端点之间的那些象素的亮度值才能显示出两点间的直线。在绘图仪上绘直线段，主要决定X、Y方向上的位移量，这些算法之间主要区别是判别和生成x、y增量的过程和方法的不同。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)41.1.点的生成点的生成 点是图形中最基本的图素，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中一个位置。在计算机图形学中，点是用数值坐标来表示的。在直角坐标系中点由（x,y)两个数值组成的坐标表示。在输出设备上输出一个点，就要把应用程序中的坐标信息转换成所用输出设备的相应位置。对于一个CRT监视器来说，输出一个点就是要在指定的屏幕位置上打开电子束，使该位置上的荧光点亮。在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程序语言中都有描点语句。例如C语言为putpixel(x,y,color)。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)5直线是点的集合，在几何学中直线被定义为两个点之间的最短距离。也就是说一条直线是指所有在它上面的点的集合。直线是一维的，即它们具有长度但没有面积。直线可以向一个方向及其相反的方向无限伸长，这不是计算机图形学中所需要的，在图形学中研究的对象是直线段。已知线段的起点坐标（x1,y1），终点坐标（x2,y2)，这两点就确定了一条线段。一般来讲，任何图形输出设备都能准确地画出水平线X和垂直线Y,或对角线，但要画出一条准确斜线不是件容易的事。在光栅系统中，线段通过象素绘制，水平和垂直方向的台阶大小受象素的间隔限制。这就是说，必须在离散位置上对线段取样，并且在每个取样位置上决定距线段最近的象素，画一条直线实际上就计算出来一系列与该线靠近的象素。3.1 生成直线的常用算法第3章 基本图形生成算法(0,0)_(5,2)K=0.4(0,0)-(1,0)-(2,1)-(3,1)-(4,2)-(5,2)X=1,y1=y0+k*(x1-x0)=y0+k=0+0.4=0.4Round(y)=round(0.4)=0Y2=y1+k=0.4+0.4=0.8 round(y2)=1第3章 基本图形生成算法均假定所画直线的斜率k0，1。3.1.1 DDA画线算法DDA（Digital Differential Analyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。第3章 基本图形生成算法已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为：假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y）作为当前点的坐标。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)9DDA直线生成算法的伪语言描述如下：begin if abs(x2x1)abs(y2y1)then lenghtabs(x2x1)else lenghtabs(y2y1)endif x(x2x1)/lenght y(y2y1)/lenght xx1 yy1 k1 while(klenght)putpixel(x,y)xxx yyy kk1 endwhile endDDA方法计算象素位置要比直接使用代数方程快。它利用光栅特性消除了代数方程中的乘法，而在X和Y方向使用合适的增量来逐步沿线段的路径计算各象素位置。但浮点增量的连续迭加中取整误差的积累会使长线段所计算的象素位置偏离实际线段，而且算法中的取整操作和浮点运算仍然十分耗时。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)10DDA直线绘制的直线绘制的C+实现实现void DDA直线绘制(HDC hdc)int k;double x1=50,y1=50,x2=300,y2=350;double x,y,deltx,delty,length;if(fabs(x2-x1)=fabs(y2-y1)length=fabs(x2-x1);else length=fabs(y2-y1);deltx=(x2-x1)/length;delty=(y2-y1)/length;x=x1;y=y1;k=1;while(k=length)SetPixel(hdc,x,y,RGB(0,0,0);x=x+deltx;y=y+delty;k=k+1;Sleep(50);第3章 基本图形生成算法3.1.2 中点画线算法 假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。设Q是理想直线与垂直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1。第3章 基本图形生成算法令a=y0-y1，b=x1-x0，c=x0y1-x1y0。构造判别式：d=a(xp+1)+b(yp+0.5)+c d的初始值d0=a+0.5b 在d0的情况下，取正右方像素P1，d1=a(xp+2)+b(yp+0.5)+c=d+a-d1=2a在d0的情况下，取右上方像素P2，d2=a(xp+2)+b(yp+1.5)=d+a+b-d2=2(a+b)第3章 基本图形生成算法 由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)14 Bresenham直线生成算法是由Bresenham提出的一种精确而有效的光栅线段生成算法，算法的目标是选择表示直线的最佳光栅位置。为此，算法根据直线的斜率确定选择变量在X方向上或在Y方向上每次递增一个单位，另一变量的增量为0或1，它取决于实际直线与最近网格点位置的距离，这一距离称为误差。算法的构思巧妙，使得每次只需检查误差项的符号即可确定所选象素。3.1.3 Bresenham画线算法第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)15 以第一象限的直线为例。假设斜率m在01之间。如下图所示。若通过（0,0）的直线的斜率ml2，它与x1直线的交点离yl直线较y0直线近，光栅点（1,1）比（1,0）更逼近于该直线，因此应该取象素点（1,1）。如果斜率ml2，则应取象素点（1,0）。当斜率ml2时，差值相同，可以任选（1,1）或（1,0）象素点。第3章 基本图形生成算法 过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。由图3-5不难看出：若st，则Si比较靠近理想直线，应选Si;若st，则Ti比较靠近理想直线，应选Ti。第3章 基本图形生成算法令dx=x2-x1，dy=y2-y1递推公式：di的初值：当di0时，选Ti，当di0时，选Si，由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)18 根据上述思想的Bresenham直线生成算法描述如下：begin xx1 yy1 xx2-x1 yy2-y1 my/x e-1/2 for k1 to x putpixel(x,y)eem if(e0)yy1 ee1 endif xx1 next k endfor end此Bresenham算法在计算直线斜率和误差项时要用到浮点算术运算和除法，如果采用整数算术运算和避免除法，可以加快算法的速度。实际上，误差项e的数值大小与算法的执行没有什么关系，相关的只是e的符号，因此作简单变换，即可得到整数算法。第3章 基本图形生成算法2024/9/20 周五计算机图形学演示稿 岳俊华制作(C)19Bresenham算法直线绘制例子：考虑绘制从点（0，0）到（8，4）的线段。初值计算：x=0 y=0 x=8 y=4(循环计算过程部分：e-x for k1 To x putpixel(x,y)ee2y If(e0)yy1 ee2x endif xx1)第3章 基本图形生成算法3.1.4 直线属性基本的线属性是线型、线颜色和线宽度。1线型:对线型的指定包括实线、虚线和点划线等。2线宽:常把图形设备能产生的最小直线宽度认为是1个点宽度，例如1个象素的宽度。以此作为基本线宽，再定义二倍或四倍线宽。线宽的默认值常选取基本线宽。3线色:线颜色由控制RGB监视器中三支电子枪的亮度的RGB分量来给出。第3章 基本图形生成算法3.2 生成圆弧的常用算法3.2.1 圆的特性 圆心位于原点的圆有四条对称轴：x=0，y=0，x=y和x=-y直线。若已知圆弧上一点（x,y），可以得到其关于四条对称轴的其它7个点，这种性质称为八对称性，如下图所示。本节讨论的圆的生成算法均只计算从x=0到x=y分段内（1b区域）的像素点，其余的像素位置利用八对称性即可得出。第3章 基本图形生成算法3.2.2 中点画圆算法 假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。第3章 基本图形生成算法判别式d：d的初始值为：在d0的情况下，取右下方像素P2，在d=0，则y=yi-1，di+2=d i+1+4(xi-yi)+10如果d i+1=ymax的结点 对于留在AEL中的每个结点，执行xi+1=xi+1/k 对AEL中的各结点按x值从小到大排序 y=y+1，成为下一条扫描线的坐标 第3章 基本图形生成算法3.3.3 边填充算法基本原理：对每一条扫描线，依次求与多边形各边的交点，将该扫描线上交点右边的所有像素求补。算法虽然简单易行，但对于复杂图形而言，一些像素的颜色值需反复改变多次，且多边形外的像素处理过多，输入、输出的量比有序边表大的多。第3章 基本图形生成算法栅栏填充算法：对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补，也就是说，若交点位于栅栏左边，则将交点之右、栅栏之左的所有像素取补；若交点位于栅栏右边，则将栅栏之右、交点之左的所有像素取补。多边形外的像素处理大大减少，被重复取补的像素数目也有减少，但仍有一些像素被重复取补。第3章 基本图形生成算法边标志算法：对多边形边界所在像素置一个特殊标志；对于每条与多边形相交的扫描线，从左至右逐个访问该扫描线上的像素。使用一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。inside 的初始值为假，每当当前访问像素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。若访问当前像素时，对inside作必要操作之后，inside为真，则把该像素置为多边形要填充的颜色。对每个像素只访问一次，硬件执行速度快。第3章 基本图形生成算法3.3.4 种子填充算法基本思想：假设在多边形区域内部至少有一个像素是已知的（此像素称为种子像素），由此出发找到区域内所有其他像素，并对其进行填充。由于区域可采用边界定义和内点定义两种方式，区域按连通性又可分为四连通区域和八连通区域两类，所以常用的种子填充算法有：边界表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法边界表示的八连通区域种子填充算法内点表示的八连通区域种子填充算法第3章 基本图形生成算法1边界表示的四连通区域种子填充算法基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素，若其不是边界像素且没有被填充过，对其填充，并重复上述过程，直到所有像素填充完毕。可以使用栈结构来实现该算法，算法的执行步骤如下：种子像素入栈，当栈非空时，重复执行如下三步操作：（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。第3章 基本图形生成算法2内点表示的四连通区域种子填充算法基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素，如果是区域内的像素，则对其填充，并重复上述过程，直到所有像素填充完毕。它也常称为漫水法。可以使用栈结构来实现该算法，算法的执行步骤如下：种子像素入栈，当栈非空时，重复执行如下三步操作：（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素是区域内的像素，则把该像素入栈。第3章 基本图形生成算法3扫描线种子填充算法算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。可以填充有孔区域，对于每一个待填充区段，只需入栈一次，因此提高了区域填充的效率。第3章 基本图形生成算法3.3.5 圆域的填充对每条扫描线，计算它与圆域的相交区间。接着，为每一条扫描线建立一个新圆表，存放在该行第一次出现的圆的有关信息。然后，为当前扫描线设置一个活化圆表。由于一条线与一个圆只能相交一个区间，所以在活性圆表中，每个圆只需一个结点即可。结点内存放当前扫描线的区间端点，以及用于计算下一条扫描线与圆相交的区间端点所需的增量。该增量用于在当前扫描线处理完毕之后，对端点坐标进行更新计算，以便得到下一条扫描线的区间端点。第3章 基本图形生成算法3.3.6 区域填充属性1填充样式2填充颜色3填充图案第3章 基本图形生成算法3.4 字符3.4.1 字符存储与显示1点阵字符每个字符都是利用掩膜来定义，并将其写入帧缓存保存和显示。点阵字符的显示：首先从字库中将它的位图检索出来，然后将检索到的位图写到帧缓冲器中。读取帧缓存中这些像素值，就可以在屏幕上显示此字符。如果将保存在帧缓存中某字符掩膜相应像素值均置成背景色或背景光强，就可以擦除帧缓存中的该字符。第3章 基本图形生成算法2矢量字符矢量字符被表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。矢量字符的显示：首先从字库中读它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。第3章 基本图形生成算法3.4.2 字符属性显示的字符的外观由字体、字形、字号、字间距、行间距等属性控制。一般来说，字体确定风格，字形确定外观，字号确定尺寸。1单个字符属性2文本属性第3章 基本图形生成算法3.5 裁剪3.5.1 点的裁剪对于一点P（x,y），要判断其是否可见，可利用下面的不等式组来判断此点是否落在窗口范围内：满足上述不等式组的点则在窗口范围内，可见，予以保留；反之，该点落在窗口外，不可见，舍弃（裁剪）。第3章 基本图形生成算法3.5.2 直线裁剪1Cohen-Sutherland裁剪算法（编码裁剪法）基本思想：对于每条待裁剪的线段P1P2分为三种情况处理：（1）若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之；（2）若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；（3）若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。第3章 基本图形生成算法Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围的八个方向以4 bit的二进制数进行编码，如图3-42所示。具体编码过程为：延长窗口的四条边线（yt、yb、xr、xl），将二维平面分成九个区域。任何一条线段的端点都按其所处区域赋予4位编码CtCbCrCl。第3章 基本图形生成算法如果某线段的两个端点的四位 二进制编码全为“0000”，可直 接保留；如果对两端点的四位二进制编码进行逻辑与（按位乘）运算，结果不为零，可直接舍弃；否则，这一线段可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，也赋予四位二进制编码，并对分割后的线段重复进行检查，直到全部线段均被舍弃或被保留为止。裁剪窗口第3章 基本图形生成算法2中点分割算法基本思想：当一条直线段既不能直接保留也不能直接舍弃，需要求其与区域的交点时，不断地用对分方法，舍去线段的不可见部分，用中点去逼近线段与窗口边界的交点。第3章 基本图形生成算法3梁友栋-barsky裁剪算法 定义直线的参数化方程为：首先按参数化形式写出裁剪条件：这四个不等式可以表示为形式：第3章 基本图形生成算法 其中，参数pk,qk定义为：任何平行于裁剪边界之一的直线pk=0，其中k对应于裁剪边界（k=1,2,3,4对应于左、右、下、上边界），如果还满足qk0，则线段完全在边界外，舍弃该线段。如果qk0，则该线段平行于裁剪边界并且在窗口内。当pk0时，线段从裁剪边界延长线的内部延伸到外部。当pk0时，可以计算出线段与边界k的延长线的交点的u值：u=qk/pk。第3章 基本图形生成算法梁友栋-Barsky裁剪算法在寻找线段可见部分（如果有可见线段）时可以归结为四个步骤：（1）如果对所有的k都有pk=0和qk0，删除线段并结束。否则继续执行下一步。（2）对所有pk0的k，计算rk=qk/pk，将1和各个rk值之中的最小值赋给u2。（4）如果u1u2，则线段完全落在裁剪窗口之外，不可见，可直接舍弃。否则，裁剪后线段的端点由参数u的两个值u1、u2计算出来。第3章 基本图形生成算法3.5.3 多边形裁剪1Sutherland-Hodgman算法基本思想：每次用窗口的一条边界对多边形进行裁剪，把落在窗口外部的图形去掉，落在窗口内部的图形保留，并把它作为下一次待裁剪的多边形。这样，当连续用窗口的四条边界对原始多边形进行裁剪后，最后得到的就是裁剪后的结果多边形。第3章 基本图形生成算法2Weiler-Atherton裁剪算法基本思想：将待裁剪多边形（简写为P1）和裁剪矩形窗口（简写为P2）均设定为按顺时针方向排列。算法从P1的任一顶点出发，沿着它的边向下处理，当P1和P2相交时（假定交点为I）：（1）若P1的边是进入P2，则继续沿P1的边往下处理，同时输出该线段；（2）若P1的边是从P2中出来，则从此交点I开始，沿着窗口边框向右检测P2的边，即用P2的有效边框去裁剪P1的边，找到P1和P2最靠近交点I的新交点，同时输出由I到S之间窗边上的线段；（3）返回交点I，再沿着P1处理各条边，直到处理完P1的每一条边，回到起点为止。第3章 基本图形生成算法3.5.4 曲线裁剪对于被裁剪的曲线所围成的区域，找出包围（外接）此区域的最小矩形，称其为曲线边界对象的包围矩形（或包围盒），然后测试包围矩形是否与矩形裁剪窗口有重叠。如果包围矩形完全落在裁剪窗口内，则全部保留该对象；如果包围矩形完全落在裁剪窗口外，则全部舍弃该对象；如果不满足上述矩形测试的条件，则要求解直线-曲线联立方程组，得出裁剪窗口与曲线边界线的交点，即裁剪交点，再进行判断。第3章 基本图形生成算法3.5.5 字符裁剪1字符串裁剪把整个字符串作为整体来对待。2字符裁剪分别对每个字符来处理。3矢量像素裁剪每个字符都看作是由一系列矢量（线段）或像素构成的，故对每一个矢量或像素都必须个别地进行裁剪。第3章 基本图形生成算法3.5.6 三维图形的裁剪把二维线段的Cohen-Sutherland裁剪算法稍加改进，就能推广到三维平行投影的裁剪算法中。对空间任意一点P（x,y,z）按其所处位置赋予6位二进制编码。（1）两个端点的编码全为“0000”，直接保留；（2）对两端点的编码进行逻辑与运算，结果不为零，可直接舍弃；（3）否则，计算出线段与窗口表面的交点，并将线段分段后继续处理，直到余下的线段符合前两种简单情况为止。第3章 基本图形生成算法3.6 反走样对图形进行光栅化时，是用离散的像素显示在连续空间定义的对象。这种用离散量表示连续量时引起的失真现象称为走样。用于减少或消除走样的技术称为反走样。第3章 基本图形生成算法3.6.1 光栅图形的走样现象1阶梯形走样2狭小图形遗失3细节失真第3章 基本图形生成算法3.6.2 常用反走样技术1提高分辨率2简单的区域取样3加权区域取样