计算机图形学_基本算法

11第三章基本图形生成算法§3-1图形扫描转换与直线生成算法的要求§3-3常见的生成圆的扫描转换方法§3-7区域填充§3-4常见的生成椭圆的扫描转换方法§3-5其它曲线的生成方法§3-6象素编址和物体的几何表示§3-8字符生成§3-2常见的生成直线扫描转换算法退出2第一节图形扫描转换与直线生成算法的要求1、1图形的扫描转换（光栅化）1、2计算机产生图形的特点1、3描绘直线的要求返回31.1图形的扫描转换（光栅化）返回图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。光栅图形显示：常用的光栅图形显示器可看成一个像素矩阵，每个像素可以用一种或多种颜色来表示，显示图形实际上是确定一种或多种颜色的像素集合的过程。4图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。例如：用一系列的象素点来逼近直线5确定一个像素集合及其颜色，用于显示一个图形的过程。一般分两步：（（11）先确定有关最佳逼近图形的像素集合，）先确定有关最佳逼近图形的像素集合，（（22）再用图形的颜色或其它属性在设备驱动）再用图形的颜色或其它属性在设备驱动程序的帮助下进行写操作，绘出图形。程序的帮助下进行写操作，绘出图形。在不考虑线宽时，一维图形的扫描转换主要是确定一维的像素序列，二维图形的扫描转换是确定平面区域所对应的像素集(称为区域填充称为区域填充))。6Ø一般微机系统板上都配有图形显示缓冲区，为了快速、及时地控制图形的输出为了快速、及时地控制图形的输出，系统在基本内存中开辟了从A0000H~CFFFFHA0000H~CFFFFH的的256256KK字节字节甚至到甚至到FFFFFHFFFFFH的的512512KK字节字节的存储空间，在显示卡上的空间更大，可达数十兆空间。Ø控制图形显示过程的软件主要是向显示缓冲区填入图形属性信息，从图形显示缓冲区到显示器的输出主要靠硬件控制电路，以红、绿、以红、绿、蓝、亮度合成以及同步信号的形式合成图形信蓝、亮度合成以及同步信号的形式合成图形信号，号，实现5050帧帧//秒的显示（不闪烁）速率秒的显示（不闪烁）速率，控制图形在显示器上逐行或隔行显示出来。27可产生模拟灰度、黑白、彩色、动态变化、动静组合、图文并茂的复杂图形。这些图形的共有特点是：这些图形的共有特点是：（（11）按数学方法产生的图形有规律，光滑、）按数学方法产生的图形有规律，光滑、整齐、规矩、严格；整齐、规矩、严格；（（22）图形纯净、美观、无噪声干扰；）图形纯净、美观、无噪声干扰；（（33）描绘客观世界与主观世界各种对象、发）描绘客观世界与主观世界各种对象、发挥人的创造性和想象力；挥人的创造性和想象力；（（44）交互式图形显示由用户控制，图形可修）交互式图形显示由用户控制，图形可修改、速度快、差错少。改、速度快、差错少。1.2计算机产生图形的特点返回8Ø数学上理想的直线是没有宽度的，理想的点也是没有大小的；Ø由于光栅设备本身的局限性，进行扫描转换（光栅化）会出现走样和其它失真现象，如一条倾斜的直线，转换成一个像素序列时，会出现锯齿现象，显示分辨率越低，问题越严重，而且和转换的过程、在光栅上确定像素位置的准确情况有关，即与如何生成图形的算法有关Ø因此，研究图形的扫描转换算法成为计算机图形学的基本问题之一，着重讨论生成直线的算法。9图图22--11屏幕上生成直线时的锯齿现象屏幕上生成直线时的锯齿现象10（（11）直线要直）直线要直屏幕上各个光栅像素点的位置是受物理设备限制的，水平线、垂直线、45度斜线容易画直，其余角度的直线就不易对准到理想位置了，即使直线段的始点与终点能对准在屏幕坐标的可寻址点上，但线段中间的点可能不在屏幕的坐标网格点上，需要选择最靠近的可寻址点来逼近直线。是否分配点还可考虑视觉效应的亮度、均匀性等问题（假定暂不考虑）。1.3描绘直线的要求返回11（（22））直线的终点要准直线的终点要准由于绘图设备的精度和算法造成的误差，导致直线图形的终点连接处出现小间隙，要求避免误差及累积误差造成小间隙，使误差最小。（（33））直线亮度与色泽要均匀：直线亮度与色泽要均匀：转角或宽直线应避免明、暗不均的感觉。（（44））画线的速度要快画线的速度要快直线生成算法是许多绘图算法的基础，应简明、速度快。速度与设备性能相关，但好的算法可以明显改善性能。12第二节常见的生成直线扫描转换算法Ø不同的设备生成图形的方式不尽相同，但一般的原理是相通的，多数是以增、减量为主的方法，在x、y两个互相垂直的方向上给出步进信号，从而产生位移的轨迹，描绘出图形。Ø对于任一给定的直线，各种方法所产生直线的x与y方向上的信号总和，在同一设备上应是相同的。分别等于这条线从起点到终点x和y方向上的位移量（Δx,Δy）除以设备的单位步长,方法间的不同点在于判断和生成x、y信号的过程与方式不同，以适应不同的设备。返回313Ø曲线也可由直线段逼近生成Ø解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。主要步骤可以表示如下：14返回••偏差判别：偏差判别：根据当前绘图点位置与理想位置的偏差情况，确定下一步走向；••移动绘图：移动绘图：沿X方向、Y方向移动一个步距，绘出一段图形；••终点判断：终点判断：判断当前作图点位置是否为终点，是则结束绘图，否则转向计算偏差；••计算偏差：计算偏差：根据偏差数学计算公式，计算出作图的偏差情况，作为下一步判断的依据，转向偏差计算。图图22--22一般线段绘制过程的主要步骤示意图一般线段绘制过程的主要步骤示意图移动绘图偏差计算Y初值偏差判别结束N终点判断152.1逐点比较法2.2对称的数值微分法2.4中点画线法2.3简单的数值微分法2.5Bresenham画线法2.6并行画线法返回162.1逐点比较法在绘图过程中，每移动一次，就与规定的（理想位置）图形进行比较，决定下一步的走向，用步步逼近的方法画出规定的图形。返回172.1.22.1.2偏差计算公式的推导：偏差计算公式的推导：以第一象限为例，再扩展到其它象限。偏差的判断可以用斜率比较的方式推导，也可用夹角进行比较。设：设：当前作图的位置是M，欲画的直线是OA则则：OM与OA的斜率之差为δδδ=tg=tgββ--tgtgαα=Ym/Xm=Ym/Xm––Ya/XaYa/Xa=(YmXa=(YmXa--YaXm)/(XmXa)YaXm)/(XmXa)图图22--33各象限的步进方向各象限的步进方向YX返回18YYA(Xa,Ya)A(Xa,Ya)αM2(x2,y2)M(Xm,Ym)。。M3(x3,y3)。M1(x1,y1)βXY(a)(b)图图22--44绘图时向误差减小的方向移动绘图时向误差减小的方向移动返回419在第一象限内，因为tgx为单调递增函数，所以移动规则为：当当δδ00时时::表示当前点处于表示当前点处于OAOA线段的下方，线段的下方，应向应向++YY方向前进一步；方向前进一步；当当δδ00时时::表示当前点处于表示当前点处于OAOA线段的上方，线段的上方，应向应向++XX方向前进一步；方向前进一步；由于表达式中的分母XmXa0,因此只需判断表达式中分子的正负即可。返回20这里仅关心正负号，不关心具体的值,由此可得第一象限的偏差判别公式为：Fm=YmXaFm=YmXa--YaXmYaXm该公式每次计算时都要计算两次乘法，一次减法，相对多步绘图过程计算较慢，需改进计算公式，提高计算速度。返回21如果设法利用前一点的偏差计算结果来推算后一点的走向及走步后的偏差，就可简化计算。如以第一象限为例（见图2-4（b））设设::绘图的当前位置为M1(x1,y1)下一步沿Y方向走到M2(x2,y2)则：则：(设单位步长为1)F1=Y1Xa-YaX10,步进形式为X2=X1;Y2=Y1+1;返回22M2处的偏差为：F2=Y2Xa-YaX2=(Y1+1)Xa-YaX1=Y1Xa+Xa-YaX1=F1+Xa;若若：：F2=0,向+X方向移动一步到M3则：则：X3=X2+1,Y3=Y2;M3的偏差F3=Y3Xa-YaX3=Y2Xa-YaX2-Ya=F2-Ya;返回23由此递推下去，得出计算与偏差判断规则：当当Fi=0Fi=0时时，走+X方向一步，偏差为：Fi+1=Fi-Ya;(i=1,2,…n)当当Fi0Fi0时，时，走+Y方向一步，偏差为：Fi+1=Fi+Xa;偏差Fi的推算，只用到终点的坐标值（Xa,Ya）而与中间的坐标值无关，且只需进行加减运算，简化了计算，画线的判别速度就加快了。返回24同理可以推出其它象限的步进方向和偏差计算公式如下：斜率斜率00第一象限：第一象限：Fi=0,走+X方向，Fi+1=Fi-|Ya|Fi0,走+Y方向,Fi+1=Fi+|Xa|第三象限：第三象限：Fi=0,走-X方向，Fi+1=Fi-|Ya|Fi0,走-Y方向,Fi+1=Fi+|Xa|斜率斜率0第二象限：第二象限：Fi=0,走+Y方向，Fi+1=Fi-|Xa|Fi0,走-X方向,Fi+1=Fi+|Ya|第四象限：第四象限：Fi=0,走-Y方向，Fi+1=Fi-|Xa|Fi0,走+X方向,Fi+1=Fi+|Ya|以上为逐点比较法生成直线的插补运算公式，其中|Xa|、|Ya|为Xa、Ya的绝对值，Xa、Ya均为步距数。返回525设：设：绘图设备的步距为t，直线段在x,y方向的增量分别为dx,dy,则：则：从起点到终点,在X方向上应走dx/t步在Y方向应走dy/t步取其中的大值作为步数控制器，保证不会丢失走的步数，也可取它们之和作为步数控制器，力求终点绘制准确。2.1.32.1.3终点判断终点判断2.1.42.1.4增量算法：增量算法：在一个算法中，如果每一步的X,Y的值都是用前一步的值加上一个增量来获得的，这种算法就成为增量算法。返回262.2对称的数值微分法DDA(DigitalDifferentialAnalyzer)DDA(DigitalDifferentialAnalyzer)是利用数值方法解微分方程的原理来生成直线的方法，也称数字微分分析器法。返回直线的微分方程为：直线的微分方程为：dy/dx=k(k为斜率)画直线画直线：：（X1,Y1）—(X2,Y2)27工作原理：工作原理：令：令：k=ΔY/ΔX=(Y2-Y1)/(X2-X1)ΔX、ΔY为X、Y方向的长度增量让X、Y方向绘图时每次微小增加，取整后绘图则：则：Xi+1=Xi+εΔXYi+1=Yi+εΔY其中:εΔX为小于1的小增量，保证绘图精度εΔY（绘图位置为整数值，设备坐标)将增量反复加到各自的小数部分，用四舍五入法,求出最接近Xi+1、Yi+1的新值作图。返回28图图22--55对称的对称的DDADDA法法整数小数部分部分整数小数部分部分εΔYεΔXXY⊕⊕εΔXεΔY返回292.3简单的数值微分法返回设:过端点P0(x0,y0)、P1(x1,y1)的直线段为L(P0,P1)则:直线段L的斜率为：k=(y1-y0)/(x1-x0)要在显示器显示L,必须确定最佳逼近L的象素集合设：直线的斜率|k|=1，dy/dx=ΔY/ΔX=k则：在X方向从L的起点P0的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个象素)，即：Xi+1-Xi=1用L的直线方程y=kx+b计算相应的y坐标，并取象素点(x,round(y))作为当前点的坐标。30返回因递推公式：Xi+1=Xi+1yi+1=kxi+1+b=k1xi+b+kΔx=yi+kΔx所以：当Δx=1;yi+1=yi+k。即当x每递增1，y递增k(即直线斜率)xiyxyixi+1yi+1DDA算法原理631注意：round(x)=(int)(x+0.5)DDA算法生成直线段(xi,yi)(xi+1,round(yi+k))(round(xi+1/k),yi+1)返回特点：Ø增量算法Ø直观、易实现Ø不利于用硬件实现32DDA画线算法程序：voidDDALine(intx0,inty0,intx1,inty1,intcolor){i