图形学基本图元

图形学基本图元第1页，课件共91页，创作于2023年2月引言什么是基本图元？基本图元，即基本图形元素，指图形系统能够产生的最基本的图形包括点、直线、圆、圆弧、区域填充、字符等这些图形元素是生成复杂图形图像的基础也称为图形基元，或输出图形元素第2页，课件共91页，创作于2023年2月

光栅图形显示器可以看作一个像素的矩阵，每个像素可以用一种或多种颜色显示；在光栅显示器上显示任何图形，实际上都是一些具有一种或多种颜色的像素的集合！光栅图形学主要研究内容：直线、圆弧、多边形的扫描转换算法区域填充、字符、裁剪、反走样、消隐等光栅图形学显示的图形←→像素的集合第3页，课件共91页，创作于2023年2月扫描转换将图形描述转换成用像素矩阵表示的过程每次的图形改变都要进行扫描转换，因此高效快速的扫描转换算法显得尤为重要！在选择算法时，计算速度与图形质量的权衡折中是一个基本问题！图形描述→像素矩阵第4页，课件共91页，创作于2023年2月§3基本图元的生成§3-1直线的扫描转换算法DDA画线算法中点画线算法Bresenham画线算法§3-2圆的扫描转换算法中点画圆算法Bresenham画圆算法§3-3区域填充算法第5页，课件共91页，创作于2023年2月§3-1直线的扫描转换算法直线的扫描转换确定最佳逼近于该直线的一组像素按扫描线的顺序，对这些像素进行写操作此即用显示器绘制直线，或直线的扫描转换三个常用算法1DDA画线算法（数值微分法）2中点画线算法3Bresenham画线算法第6页，课件共91页，创作于2023年2月好算法的判断标准绘制出的线段应尽可能地逼近原直线；线的亮度应均匀且与线的方向无关；线段两端截断要精确；要尽可能快速地画出整条线段！

…………第7页，课件共91页，创作于2023年2月讨论的前提假设条件像素间均匀网格整型坐标系讨论直线段斜率0<k<1的情况；对k＞1的情况，将x、y互换即可第8页，课件共91页，创作于2023年2月光栅图形中点的表示每个像素由其左下角的坐标表示第9页，课件共91页，创作于2023年2月直线段的两个端点：

P0(x0,y0)，P1(x1,y1)其直线方程为：y=kx+b…………①式其中:k=(y1-y0)/(x1-x0)

b=(x1y0-x0y1)/(x1-x0)………………②式已知条件第10页，课件共91页，创作于2023年2月最直接的画线算法根据上述已知条件，得到直线扫描转换最直接的算法，步骤如下：给出端点坐标P0(x0,y0)和P1(x1,y1)；利用②式，求出k和b的值；当∣k∣≤1时，利用①式进行乘法&加法运算求出y值，再取整;当∣k∣≥1时，则通过y计算x值！第11页，课件共91页，创作于2023年2月算法评价

优点：既直观，又可行！

缺点：效率低，计算量大（每步均包含乘法&加法运算、取整运算）作为最底层的光栅图形算法，在CAD等图形系统中会被大量应用，因此哪怕节约一个加法或减法，也是很了不起的改进！由此出发，引出了增量算法的思想！

请思考：何谓增量算法？第12页，课件共91页，创作于2023年2月一、DDA画线算法数值微分法DDAdigitaldifferentialanalyzer基本思想已知过端点P0(x0,y0)，P1(x1,y1)的直线从直线起点P0开始，向终点P1步进：令x每步递增1(个像素)，计算相对应的y坐标；取（x,round(y)）作为当前点的坐标！第13页，课件共91页，创作于2023年2月基本思想第14页，课件共91页，创作于2023年2月数值微分(DDA)法

增量算法推导：其中，xi+1=xi+△x增量：当△x=1时，△y=k对应点的坐标：(xi,yi)→(xi+1,yi+k)第15页，课件共91页，创作于2023年2月DDA算法本质用数值方法解微分方程

通过同时对x和y各增加一个小增量，计算下一步的x、y的值在一个迭代算法中，如果每一步的x和y的值是用前一步的值加上一个增量来获得，那么这种算法就称为增量算法

DDA算法是一个增量算法！数值微分(DDA)法第16页，课件共91页，创作于2023年2月练习题—DDA法2251.6241.2130.8120.401000Y值Round(y)X值Line:P0(0,0)—P1(5,2)012345321第17页，课件共91页，创作于2023年2月DDA算法参考程序voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x≤x1,x++)

setpixel(x,int(y+0.5),color); y=y+k;

第18页，课件共91页，创作于2023年2月数值微分(DDA)法DDA算法的不足之处包含浮点数取整运算不利于硬件实现效率低仅适用于k

≤1的情形:x每增加1,y最多增加1；当k

1时，必须把x，y互换！第19页，课件共91页，创作于2023年2月引申与思考采用增量思想的DDA算法，每计算一个像素，只需计算一个加法，是否最优？如非最优，如何改进？

改进的目标－>

进一步将一个加法运算改进为一个整数加法运算

新思路－>DDA算法采用点斜式直线表示方式，可否采用其他的直线表示方式？第20页，课件共91页，创作于2023年2月基本思想当前像素点为(xp,yp),下一像素点为P1或P2；设M点为P1与P2之中点，Q点为理想直线与垂线x=xp+1的交点；将Q与M的y坐标进行比较：若M在Q的下方，则取P2为下一个像素点；若M在Q的上方，则取P1为下一点像素点！二、中点画线算法第21页，课件共91页，创作于2023年2月中点法示意图P=(xp,yp)QP2P1M第22页，课件共91页，创作于2023年2月中点画线算法需要解决的问题判断距离理想直线最近的下一个像素点已知条件线段两端点(x0,y0)和(x1,y1)直线方程：F(x,y)=ax+by+c=0，其中：a=y0-y1b=x1-x0c=x0y1-x1y0第23页，课件共91页，创作于2023年2月M如何判断M点在Q点上方还是下方？第24页，课件共91页，创作于2023年2月如何判断M与Q的关系？构造判别式d=F(M)

=

F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c

其中：a=y0-y1,b=x1-x0,c=x0y1-x1y0当d<0时，M在直线(Q)下方，取P2为下一个像素当d>0时，M在直线(Q)上方，取P1为下一个像素当d=0时，选P1或P2均可，约定取P1点！由直线方程F(x,y)=ax+by+c=0M点坐标（xp+1,yp+0.5）第25页，课件共91页，创作于2023年2月MP1P2P(Xp+1,Yp+0.5)中点画线法演示第26页，课件共91页，创作于2023年2月进一步思考上述算法，每一个像素的计算量包括加法与乘法是否也可以采用增量算法呢？由于d是xp,yp的线性函数，因此可采用增量计算，以提高运算效率！第27页，课件共91页，创作于2023年2月分两种情形考虑再一下个像素的判定当d≥0时，M在直线上方，取正右P1(xp+1，yp)再下一个像素的判别式为d1=F((xp+1)+1,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a

第一种情况，d的增量为a！当d＜0时，M在直线下方，取右上方P2(xp+1,yp+1)再下一个像素的判别式为：d2=F((xp+1)+1,(yp+1)+0.5)=a(xp+2)+b(yp+1.5)+c=d+a+b第二种情况，d的增量为a+b！MP1P2MP1P2第28页，课件共91页，创作于2023年2月再讨论d的初始值d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b=a+0.5b令：2d代替d，则d0=2a+b从而使得d的增量都是整数因为(X0,Y0)在直线上，所以F(X0,Y0)=0中点画线法当d≥0时，△d=2a当d＜0时，△d=2(a+b)d的初始值第29页，课件共91页，创作于2023年2月优点：只有整数运算，摆脱了小数，提高了运算效率不含乘除法，计算速度快有利于硬件实现

……留待上机验证中点画线法第30页，课件共91页，创作于2023年2月练习题—中点法用中点画线法：（0，0）→（5，2）12565245-11343123-30121001dyixii012345321第31页，课件共91页，创作于2023年2月中点法参考程序voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,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(x<x1){if(d<0){x++,y++,d+=d2;}else{x++,d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/第32页，课件共91页，创作于2023年2月三、Bresenham画线算法引言DDA算法采用点斜式，中点法采用隐式表示中点法可以有整数算法其他表示可以推出整数算法吗？基本思想与中点画线法的思想类似由误差项符号决定下一个点取正右方像素还是右上方像素第33页，课件共91页，创作于2023年2月Bresenham画线算法基本思想比较d1和d2根据距离误差项的符号确定与理想直线最近的像素若d1＜d2，选B点若d1≥d2，选A点AB第34页，课件共91页，创作于2023年2月Bresenham画线算法构造判别量p=△x（d1-d2）结论初始值：p=2△y-△x增量：当p≥0时，△p=2(△y-△x)当p＜0时，△p=2△y已知条件给定端点坐标P0(x0,y0)和P1(x1,y1)则△x=x1-x0；△y=y1-y0AB第35页，课件共91页，创作于2023年2月Bresenham算法参考程序voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy，p;x=x0;y=y0;dx=x1-x0,dy=y1-y0;p=2*dy-dx;for(x=x0;xx1;x++){setpixel(x,y,color);if(p0){y++,p+=2*(dy-dx);}else{p+=2*dy;}}}第36页，课件共91页，创作于2023年2月练习题-Bresenham法已知(0,0)→(5,2)△x=5;△y=2;P初始=2△y-△x=-1△p(≥0)=2(△y-△x)=-6△p(＜0)=2△y=4-125-524113-312301-100pyx★p≥0,y加1★p＜0,y不变★第37页，课件共91页，创作于2023年2月Bresenham画线算法优点整数运算，速度快计算精度高乘2运算可用移位实现，适于硬件实现

……留待上机验证第38页，课件共91页，创作于2023年2月后续展望至此，直线光栅化算法是否终结？新方法：

BRDC:binaryrepresentationofdisplacementcodeforlineMiaoLF,LiuXG,PengQS,BaoHJCOMPUTERS&GRAPHICS-UK26(3):401-408JUN2002第39页，课件共91页，创作于2023年2月§3-2圆的扫描转换算法圆的扫描转换在光栅网格中挑选出最靠近圆周的像素假设条件

圆心在原点，半径为R；圆的方程：x2+y2=R2；对于圆心不在原点的圆，可以通过平移变换，化为中心在原点的圆！第40页，课件共91页，创作于2023年2月最直接的画圆方法令x以单位步长从0增至R；求出每一步对应将y值取整从而可以得到1/4圆周！包括乘方和开方运算，效率不高在x接近R时，圆周上点间隔较大

R2-x2y=第41页，课件共91页，创作于2023年2月寻求更好的算法圆的特征八对称性—只要能生成八分之一的圆弧，就可以得到整个圆！令x从0→求出对应y值其它点即可相应得出如何画这1/8圆周？yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR2/R第42页，课件共91页，创作于2023年2月一、中点画圆法当前点P(xi,yi)下一点可能是P1(xi+1,yi)P2(xi+1,yi-1)第43页，课件共91页，创作于2023年2月构造函数：F(x,y)=x2+y2-R2圆上的点，F(x,y)=0圆外的点，F(x,y)>0圆内的点，F(x,y)<0

P1和P2的中点M（xp+1,yp-0.5）d=F(M)<0时，M在圆内，取P1点

d=F(M)>0时，M在圆外，取P2点

d=F(M)=0时，P1或P2均可，约定取P2

中点画圆法P=(xp,yp)P1P2M第44页，课件共91页，创作于2023年2月中点画圆法判别式：若d＜0,取P1为下一像素，再下一像素的判别式为若d≥0,取P2为下一像素，再下一像素的判别式为222)5.0()1()5.0,1()(RyxyxFMFdpppp--++=-+==32)5.0()2()5.0,2('222++=--++=-+=pppppxdRyxyxFd5)(2)5.1()2()5.1,2('222+-+=--++=-+=ppppppyxdRyxyxFd第45页，课件共91页，创作于2023年2月中点画圆法设初始像素是P0（0，R）判别式d的初值为d0=F（1，R-0.5）=1.25-R设当前点为P（xp，yp）,则下一点的选择当d＜0时,取P1为下一像素，且△d=2xp+3当d≥0时,取P2为下一像素，且△d=2(xp-yp)+5第46页，课件共91页，创作于2023年2月中点画圆法参考程序voidMidpointCircle(intR){intx,y;doubled; x=0;y=R;d=1.25-R; SetPixel(x,y); while(x<y) {if(d<0){d+=2*x+3;x++;

} else{d+=2*(x-y)+5;x++;y--; } SetPixel(x,y); }}第47页，课件共91页，创作于2023年2月改进—中点法为了进一步提高算法的效率，可以将上述算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法改进措施：令e=d-0.25代替d初始值：e0=1-Re初始值为整数，运算中增量也为整数再次改进：只有整数运算，且不含乘法第48页，课件共91页，创作于2023年2月中点画圆法参考程序（改进）voidMidpointCircle2(intR){intx,y,deltax,deltay,d; x=0;y=R;d=1-R;deltax=3;deltay=5-R-R; SetPixel(x,y); while(x<y) {if(d<0) {d+=deltax;deltax+=2;x++;

} else {d+=(deltax+deltay);deltax+=2;deltay+=2; x++;y--;} SetPixel(x,y); }}第49页，课件共91页，创作于2023年2月二、Bresenham画圆算法

在0≤x≤y的1/8圆周上，像素坐标x值单调增加，y值单调减少。设：第i步已确定（xi,yi）是要画圆上的像素点，看第i+1步像素点（xi+1,yi+1）应如何确定：可能是(xi+1,yi)可能是(xi+1,yi-1)第50页，课件共91页，创作于2023年2月21)i(y21)i(x2RDd2R2iy21)i(xHd--+-=-++=判别量Bresenham画圆法第51页，课件共91页，创作于2023年2月Bresenham画圆法若精确圆弧是③则dH>0和dD>0若pi<0，即dH<dD应选H点若pi≥0，即dH≥dD应选D点若精确圆弧是①或②，显然H是应选择点此时dH≤0，dD>0，必有pi<0若精确圆弧是④或⑤，显然D是应选择点此时dH>0，dD≤0，必有pi>0结论：pi做判别量：当pi＜0时，选H点为下一个像素点当pi≥0时，选D点为下一个像素点第52页，课件共91页，创作于2023年2月voidBresenhamCircle(intR){intx,y,p; x=0;y=R;p=3-2*R; for(;x<=y;x++) {SetPixel(x,y); if(p>=0) {p+=4*(x-y)+10;y--;}else {p+=4*x+6; } }}Bresenham算法参考程序第53页，课件共91页，创作于2023年2月

只需修改语句SetPixel(x,y)，画八个对称的点，即可画出整个圆；若加一个平移变换，就可以画出圆心在任意位置的圆！圆的完成第54页，课件共91页，创作于2023年2月§3-3区域填充算法区域填充本节将讨论如何用一种颜色或图案来填充一个二维区域需要讨论的两个问题确定需要填充哪些像素确定用什么颜色或图案来填充第55页，课件共91页，创作于2023年2月区域填充算法

填充算法

扫描线填充算法

按照扫描线顺序

种子填充算法

从区域内部的一个点出发第56页，课件共91页，创作于2023年2月一、扫描线填充算法多边形域的填充

这里讨论的多边形可以是凸多边形、凹多边形，或者是含内环的多边形！第57页，课件共91页，创作于2023年2月扫描线填充算法算法的基础一条直线与任意封闭的曲线相交时，总是从第一个交点进入内部，再从第二个交点退出即奇数次进入，偶数次退出算法的思想按照扫描线顺序，计算扫描线与多边形的相交区间，再用指定颜色显示这些区间的像素！第58页，课件共91页，创作于2023年2月算法思想以扫描线“6”为例与多边形的边界交于A、B、C、D四个点把扫描线划分为五个区间①②③④⑤其中②和④落在多边形内，该区间内像素应取填充色，其余区间的像素取背景色！0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)①②③④⑤多边形P1P2P3P4P5P6，注意相交顺序及交点排序问题第59页，课件共91页，创作于2023年2月算法填充过程1．求交计算扫描线与多边形各边的所有交点；2．排序按x坐标递增顺序对交点进行排序；3．交点配对第1、2个，第3、4个为一对等等，每对代表一个区间4．区间填色区间内像素置成填充色，区间外像素置成背景色第60页，课件共91页，创作于2023年2月需要注意的两个问题问题一扫描线过顶点的情况问题二边界上像素的取舍问题第61页，课件共91页，创作于2023年2月请分析：扫描线“2”的情况0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第62页，课件共91页，创作于2023年2月分析过程按照前述方法分析扫描线“2”的情况扫描线“2”分别与多边形的P1P2、P2P3、P6P1边相交交点排序后的x坐标为：2，2，8填充：区间【2，2】置为填充色不填充：区间【2，8】置为背景色从而出现异常情况！第63页，课件共91页，创作于2023年2月修正措施当扫描线与多边形顶点相交时，相同的点只取一个！由此，扫描线“2”与多边形交于2，8；填充区间【2，8】，从而得到期望的结果！请根据新规定再分析：扫描线“7”的情况！第64页，课件共91页，创作于2023年2月请再分析：扫描线“7”的情况0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第65页，课件共91页，创作于2023年2月分析过程根据新规定分析扫描线“7”的情况扫描线“7”分别与多边形的P3P4、P4P5、P5P6、P6P1边相交交点排序后的x坐标为：2，9，11填充：区间【2，9】置为填充色不填充：区间【9，11】置为背景色从而，又出现异常情况！第66页，课件共91页，创作于2023年2月解决问题一针对扫描线过顶点的情况，如何进行交点的取舍？情况1：共享顶点的两边分别落在扫描线的两边交点只算一个！情况2：共享顶点的两边落在扫描线的同一边交点取为零个或两个！具体实现时：检查顶点所在两条边的另外两外端点的y值；按照两个y值大于交点处y值的个数是0，1，2

…来决定取交点个数是0，1，2个第67页，课件共91页，创作于2023年2月结论对于局部最高点→取0个交点例如：P6对于局部最低点→取2个交点例如：P2、P5对其它点→取1个交点例如：P1第68页，课件共91页，创作于2023年2月问题二：边界像素的取舍问题请填充图中的矩形区域P1P2P3P4

请分析

请仔细观察填充结果存在什么问题012345671234567yxP1P2P3P4第69页，课件共91页，创作于2023年2月填充结果存在问题：矩形实际面积4×3；而填充后面积为5×4！产生面积扩大化的问题！012345671234567yx012345671234567yxP1P2P3P4第70页，课件共91页，创作于2023年2月解决问题二问题分析面积扩大是由于对边界上的所有像素均进行填充而引起的如何解决制定填充规则：

“左闭右开”

“下闭上开”012345671234567yx第71页，课件共91页，创作于2023年2月算法讨论AET的概念活性边表（Active-Edge-Table）与当前扫描线相交的边称为活性边，把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为活性边表！引入活性边表的概念，目的在于提高计算效率，在处理每一条扫描线时，不必将其与所有边求交，只需考虑与活性边求交即可！第72页，课件共91页，创作于2023年2月AETAET中结点内容x：当前扫描线与边的交点坐标△x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax例：扫描线6的活性边表第73页，课件共91页，创作于2023年2月0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第74页，课件共91页，创作于2023年2月AET的更新每离开一条扫描线，进入下一条扫描线之前，应做的工作：将与当前扫描线相交而与下一条扫描线不相交的边，从AET表中清除！将下一条扫描线新交上的边，加入AET中适当的位置！第75页，课件共91页，创作于2023年2月请做练习请写出扫描线“7”的活性边表0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第76页，课件共91页，创作于2023年2月答案扫描线7的活性边表AET结点内容x：当前扫描线与边的交点坐标△x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymaxP4P5P3P49281108∧FG第77页，课件共91页，创作于2023年2月AET&NETAET的作用通过AET，可以充分利用边的连贯性和扫描线的连贯性，减少求交计算量，提高排序效率NET概念的引入为了方便活性边表的建立与更新，为每条扫描线建立一个新的边表称之为NET（New-Edge-Table）第78页，课件共91页，创作于2023年2月NET的概念新边表（NET）存放在该扫描线中第一次出现的边！即：若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中第7