第2章 图形生成技术简介.ppt

计算机制图与数据库,主讲教师武法东,地球科学与资源学院遥感第四纪教研室,教学用书实用计算机制图武法东、田明中、柴春媚编著地质大学出版社（校内），1998,主要参考计算机图形技术原理及其应用王汝传编著人民邮电出版社1998计算机图形学基础唐泽圣、周嘉玉、李新友编著清华大学出版社,课程主要内容,绪论计算机图形学研究概述第一章计算机图形系统第二章图形生成技术简介第三章Worksheet的使用第四章Grapher绘制二维图形第五章Surfer绘制等值线图第六章Surfer绘制其它三维图形第七章CorelDRAW绘图简介第八章MapGIS绘图简介,第二章图形生成技术与变换简介,,由计算机产生的图形根据它们实际所在的空间，可将图形分为二维图形和三维图形，二维图形又可称为平面图形，三维图形又叫立体图形。我们还可以发现，三维图形最终还是用二维图形的形式来表示。例如机械零件的三视图、土木结构图等，由于它们所在的空间是一个平面，因此，这些图形是二维图形。因此，可以认为，二维图形的生成是三维图形生成的基础，研究计算机生成图形就必须先从二维图形的生成开始。,图形生成过程,本章将主要叙述些能在指定输出设备上，根据坐标描述构造二维几何图形的方法。一幅图最简单的几何成分是点和直线，还有曲线、多边形区域以及字符串等，我们将着重讨论生成这些因素的基本技术和算法。为在输出设备上输出一个点，就要把应用程序中的坐标信息转换成所用输出设备的相应指令。①对于一个CRT监视器来说，输出个点就是要在指定的屏幕位置上开启接通电子束，使该位置上的荧光点辉亮。②对于黑白光栅显示器来说，则是要将帧缓存中指定坐标位置处的位置为“1”，然后，当电子扫视每一条水平扫描线时，每当遇到帧缓存中值为“1”的点，就发射一亮光，即输出一个点。无论是用绘图仪还是用显示器作为图形输出设备，最基本图形显示方式是直线方式绘图仪最基本的走步动作是直线运动．图形显示器屏幕上的像素组成的点阵是直线网格状点阵。无论什么复杂图形，它们无非是由直线段和曲线段组成，三维图形经投影后最终变成了二维图形，而图形设备显示曲线段时，最终还是将曲线段转化成一系列直线段逼近表示。因此，所有图形我们都可以看成是由直线段组成。,第二章图形生成技术与变换简介,第一节基本绘图元素第二节直线段的生成第三节曲线生成第四节二维图形变换,,,,,,第一节基本绘图元素,坐标系统确定之后，需要使用不同的绘图元素来描述图形，它们是点、直线、曲线和其它基个的图形元素。一、点二、直线三、曲线四、区域填充,,,,,,,一、点,点是图形中最基本的图素，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中一个位置。在计算机图形学中，点是用数值坐标来表示的。在直角坐标系中点由x，y两个数值组成的坐标表示，在三维坐标系中点是由x，y，z三个数值组成的坐标表示，如图所示,,,,,,,,x,y,x,y,z,二、直线,直线是点的集合，在几何学中直线被定义为两个点之间的最短距离。也就是说一条直线是指所有在它上面的点的集合，直线是一维的。直线向一个方向及其相反的方向无限伸长，这不是计算机图形学中研究的，它研究的对象是直线段。下面来考查直线上存在于两个端点xs，ys和xe，ye之间的任意点。线段的起点坐标xs，ys，终点坐标（xe，ye，这两点就确定了这条线段，线段上的任意一点x，y均满足一般来讲，任何图形输出设备都能准确地画出水平线x和垂直线Y，但要画准确地出一条斜线却不容易。那么在图形显示器上如何生成斜线段呢。,,,图形显示器是由一个个排列有序的像素所构成，能划分的像素点越多则分辨率越高。例如VGA卡640480的显示器，分成640480个网格，网格的单元称为像素，一条线段就是由一些连续可见的像素所组成，如右图所示，画一条直线实际上是根据一系列计算出来并与该线靠近的像素而绘制。,在绘图设备中，绘图仪绘制线段是笔在X,Y方向移动，画线时单方向的一次移动距离称为步距，设备的步距越小，绘出的图形越精确。较精密的绘图仪的步矩为0.025mm，则0.025mm是一个形成线段的最小单元。绘图仪的精度比图形显示器要高得多，画出的线段比显示的线段好。绘图仪绘线段过程如图所示,由像素组成的线段,绘图仪画线段,,,,,,,,,,,,,,,,三、曲线,曲线包括圆、椭圆、弧线和由许多类型的方程所确定的图形。在计算机图形程序设计中，将曲线定义成不能构成直线的点的集合。曲线被认为是图形学的基础，在生产设计中经常遇到的是曲线问题，这是因为曲线更能满足人们的设计要求。生成曲线与直线一样，也用计算接近曲线的像素位置，曲线通过具有相同颜色的像素在显示表面上显示出来，曲线并不存在于显示表面上，而是仅存于数据库中。三次参数曲线如图所示,曲线图,,,四、区域填充,区域填充是一个彩色区域，可以是均匀的也可以是不均匀的，区域边界可以是直线也可以是曲线。正如多种不同类型的线条一样，可提供不同的内部填充类型用以充满区域内部，填充的类型可能是不同的颜色，不同的灰度或者不同的填充图案。还可以用方程生成的梯度变化曲线完成填充过程。,阴影填充元素图,阴影填充可以通过来自一个光源的投影直线计算出，因而在填充区域中的像素相应地发生变化。用户可根据系统硬件和软件，用一种或几种色彩进行填充，也可使用多种颜色填充区域。阴影填充如图所示。,第二节直线段的生成,,直线段是最基本的图形,它生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。例如一个较复杂的曲面，它可能是由上万条很短的直线组成的。质量上如果设计的直线段生成算法所产生的直线质量很差，那么这一复杂的曲面绘出来效果就会很差；速度上如果直线段生成的速度很慢，就会使得这一曲面绘出的速度很慢，从而直接影响图形软件运行的效率。所以，直线生成算法在图形软件设计中起着关键的作用。无论是绘图仪还是显示器，它们最基本的绘图方式是画X方向或Y方向上的直线段，由于所画的这种直线段可以很短很短，因此就可以通过一系列这样很短的直线段来近似表示任意位置上的一条直线段。在光栅显示器上显示图形是指将线段上所有像素点亮的过程。如果已知直线段两个端点，可以有很多种不同的数学方法来决定应改变在两端点之间的哪些像素的亮度值才能显示出两点间的直线。在绘图仪上绘直线段，主要决定x、y方向上的位移量，这些算法之间的区别主要是判别和生成x、y增量的过程和方法不同，所能适应的设备环境也不同。,第二节直线段的生成,一、逐点比较法二、数值微分法（DDA法）三、Bresenham法,,,,,一、逐点比较法点,绘图仪中画直线多采用逐点比较法，在绘图过程中，绘图笔每画一步就与规定图形进行比较，然后决定走向，用步步逼近的方法画出规定的图形。我们以坐标系第一象限中的直线为例讨论如下。如下图所示，要画直线OA，画笔当前位置在M，用0M与OA线段斜率之差来计算偏差δ,当δ0时，表示笔在OA线段上方，应该向＋x方向走一步。由于公式中分母xMxA0,只需判断分子的正负即可，得到偏差公式FMyMxA-yAxM,,对任意点（xi，yi），偏差函数的一般形式为FiyixA-yAxi其中，xA，yA是终点坐标。为了简化计算，可设法用前一点的偏差来推算后一点的走步方向，以及走步后的偏差，这种方法称递推法。递推法公式如下当Fi≥0时，向x方向走一步，此时偏差Fi1Fi-yAI1,2.n当Fi＜0时，向y方向走一步，此时偏差Fi1FixAI1,2.n偏差Fi的推算，只用到终点座标值xA，yA，而与中间点的坐标值无关，且只需进行加减运,非常适合计算机实现。递推公式可根据下图用偏差函数判断笔进方向的图例得出。,,递推公式可根据下图用偏差函数判断笔进方向的图例得出。设笔当前位置为M1xl,y1，此时Fl＝ylxAyAxl＜0，应走y一步到M2，即x2x1y2y11此处1表示向正方向走一个设备单位步长，这里假设x,y坐标值均已转换为当前设备单位。M2处的偏差为F2＝y2xAyAx2＝ylxAxAyAxlF1xA若F2≧0，应走＋x一步到M3，则x3x21y3y2F3＝y3xAyAx3＝y2xA-yAyAx2F2-yA,,,X,,,,,M1x1,y1,AxA,yA,O,Y,,,,,,M2x2,y2,M3x3,y3,这样依次进行下去，就得到上述递推公式。对于第二、三、四象限的直线如图所示，也可类似推出。当直线段处于第二、三、四象限时，偏差值的计算及走步方向见表4．1。,,逐点比较法的执行过程如图所示。终点判断通常采用减法计数器设绘图步距为t，直线在x、y方向增量分别为x和y，从直线起点画到终点在x方向应走x／t步，在y方向应走y／t。取max（x／t，y／t）作为长度控制数，并存入计数器内，在计长的方向上每走一步计数器减1，直到计数器为0时作图停止。（源程序）,,二、数值微分法（DDA法）,数值微分法即DDADigitalDifferentialAnalyzer法，这是一种基于直线的微分方程来生成直线的方法。设x1，y1和x2，y2分别为所求直线的端点坐标，由直线的微分方程得,可通过计算由x方向的增量Δx引起y的改变来生成直线由yi＋1＝yi＋Δyyi为直线上某步的初值则,,即,（式2-1）,（式2-2）,二、数值微分法（DDA法）,也可通过计算由y方向的增量Δy引起x的改变来生成直线若设xi＋1＝xi＋Δx则由（式2-1）可得,（式2-3）,式22和23是递推的。,二、数值微分法（DDA法）,本算法的基本思想是选定x2xl和y2yl中较大者作为步进方向假设x2x1较大,取该方向上的Δx为一个像素单位长，即x每次递增一个像素，然后利用22式计算相应的y值，把每次计算出的xi1,yi1经取整后顺序输出到显示器，则得光栅化后的直线。简单DDA算法，选择Δx或Δy中较大者为一个像素单位，其相应方向的增量为l，具体算法如下,逐点比较法生成直线C语言源程序,,三、Bresenham法,DDA法是根据直线的斜率来计算出下一个y值，经取整后以确定下一个像素点。因为进行取整运算，这就难以避免所取像素点偏在实际直线的某一侧。而Bresenham算法根据直线的斜率确定或者选择变量在X轴或Y轴方向每次递增一个单位，另一个变量的增量根据实际直线与网格的距离取0或1，这个距离称为误差，记作e。,Bresenham法最初是为数字绘图仪设计的，同样也适用于光栅图形显示器，其基本思想是使得每次只要检查误差项的符号就可以决定实际的增量值。,,三、Bresenham法,以第一个八分图的直线为例，即直线的斜率在0，1之间，如图所示。若通过0,0的直线的斜率大于l／2，即e1／2，它与x＝1直线的交点离y＝1直线较y＝0直线近，因此取像素点1，1。如果斜率小于1／2，即e1／2，则应取像素点1，0。当斜率等于1／2时，即e＝1／2，没有确定选择标推，但算法选择1，1像素点。,Bresenham法思路,直线y1,直线X1,直线y0,,,,,Bresenham法误差项计算,为了简化判断，可设e＝e－1／2，这样只要判断e的符号即可。如果e＝Δy/Δx－1/2大于或等于零，则x加1，y加1；如果e小于零，x加1，y不动。对于下一步误差项计算，一般分两种情况，如图所示对e≥0，y增加一步，新的误差项e＝e＋Δy/Δx－1对e＜0，y没有走步，e＝e十Δy／Δx。,,,一般Bresenham算法判断条件,实际上，误差项e的数值大小与算法的执行没有什么关系，相关的只是e的符号，因而我们可以改变e的定义，在右边两项同乘以2Δx，可消除除法运算令初始e＝2*Δy－Δx如果e≧0则e＝e＋2ΔyΔx如果e＜0则e＝e十2Δy根据上述思想．我们可以将算法扩展到任一八分圆坐标空间图形成一般Bresenham算法，如所示是各象限判别条件。,将“Δy/Δx－1/2”乘以2Δx将“Δy/Δx－1”乘以2Δx将“Δy／Δx”乘以2Δx即得上述结果,e＝Δy/Δx－1/2,,第三节曲线的生成,一、圆弧的生成二、规则曲线的生成三、自由曲线的生成,,,,,常常需要绘制曲线，且根据要求往往不同，通常遇到的有下述几种情况（1）规则曲线已知曲线的方程，要求画出曲线。（2）拟合曲线根据试验或观测得到的数据点，用一个函数近似地表明数据点之间的关系，并画出函数的图像。（3）曲线插值由试验、观测或计算得到了由若干个离散点组成的点列，要求用光滑的曲线把这些离散点联结起来。（4）曲线逼近在曲线形状设计中，给定了折线轮廓，要求用曲线逼近这个折线轮廓。,一、圆弧的生成,（一）逐点比较法（二）数值微分法（DDA法）（三）正负法,,,,,（一）逐点比较法,,逐点比较法绘制圆弧的原理与逐点比较法生成线段类似，也是在图形输出设备上每次输出去逼近欲画的圆弧。逆时针画第一象限中AB圆弧的过程如下,①从始点（xA、yA）开始画起，首先向圆内走一步，也就是先向－X方向走一步，然后与所要画的圆弧进行比较。（2）判断结果，落在圆内时向Y方向走一步，依次类推，一直到达圆处为止。（3）当判断结果落在圆外时，向－X方向走一步。直到再次到达圆内为止。（4）当画到点B（xB，yB）时，终止比较，AB圆弧绘制结束。,从上面绘制圆弧的过程可知，归根到底是用什么方法来比较当前点是否落在圆内，还是落在圆外，然后决定走向。设圆心为O（xO，yO），起点坐标为A（xA，yA），终点坐标为B（XB，yB），并假定绘图笔当前位置为MxM,yM，于是圆的半径为R，即,,令FMRM-R作为判别函数为了简化计算，取FMRM2-R2。显然①FM＜0，表示M点在圆弧内②FM＞0，表示M点在圆弧外③FM＝0，表示M点在圆弧上因此根据FM的正负,可以确定画弧走向,M点半径,因为起始点A在圆上，所以FM＝0，根据约定应向－X方向一步Δx，移动后坐标值为x1xa－Δxy1ya则有F1R12-R2x1-xo2y1-yo2-R2（将x1、y1代入）xa-Δx-xo2ya-yo2-R2xa-xo2Δx2-2Δxxa-xoya-yo2-R2Fa-2Δxxa-xoΔx2,,A点半径平方,由于Fa＝0（在圆上），（xa－xo）≥Δx且Δx≥0所以F1＜0,应向＋Y方向走一步Δy，移动后的坐标值为,x2x1y2y1＋Δy则有F2R22-R2x2-xo2y2-yo2-R2（将x2、y2代入）x1-xo2y1＋Δy-yo2-R2x1-xo2y1-yo2Δy2-2Δyy1-yo-R2F1-2Δyy1-yoΔy2,,如此推导下去，对于第i步（i0，1，2，，n），如果Fi≥0（点在圆外），则走一步-Δxxi1xi-Δxyi1yiFi1Fi-2Δxxi-xoΔx2,,如果Fi＜0（点在圆内），则走一步Δyxi1xiyi1yiΔyFi1Fi2Δyyi-yoΔy2,当原点坐标为（0,0），Δxy1时Fi≥0时，坐标值及判断函数为xi1xi-1yi1yiFi1Fi-2xi1Fi＜0时，坐标值及判断函数为xi1xiyi1yiΔyFi1Fi2Δyyi-yoΔy2,对于其它象限的情况，可以仿照推导,,（二）数值微分法（DDA法）,,（三）正负法,,VB中常用画线命令,一、鼠标画线命令1mousmoveline-x,y2mousdown3mousup二、画点pset[step]x,y[,color]三、按线段端点坐标画线line（x1,y1-x2,y2,color四、画圆circle（x，y），半径,,