《图形显示算法基础.pptx》由会员分享，可在线阅读，更多相关《图形显示算法基础.pptx（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1图形显示算法基础图形显示算法基础2生成直线的一般要求是：生成直线的一般要求是：1.DDA算法（数值微分法）算法（数值微分法）2.直线的直线的Bresenham算法算法 确定象素最佳逼近某图形的过程通常称为确定象素最佳逼近某图形的过程通常称为光栅化光栅化。图形生成算法的工作图形生成算法的工作:在显示器所给定的有限个象素组成的矩阵中在显示器所给定的有限个象素组成的矩阵中,确定最佳逼近于图形的象素点集确定最佳逼近于图形的象素点集.1.象素是均匀分布的象素是均匀分布的2.所画的线应是直的，且有精确的起点和终点所画的线应是直的，且有精确的起点和终点4.4.最后直线的生成速度要快最后直线的生成速度
2、要快3.所显示的亮度应沿直线不变，且与直线的长度和方向无关。所显示的亮度应沿直线不变，且与直线的长度和方向无关。3.1.23.1.2直线光栅化的方法直线光栅化的方法直线光栅化的方法直线光栅化的方法第1页/共82页3已知端点已知端点A(x1,y1)、B(x2,y2),直线的微分方程：直线的微分方程：dy/dx=(y2-y1)/(x2-x1)=常数常数=m yi+1yi+(y2-y1)/(x2-x1)*x=yi+m*x yi=m xi +Byi+1=m xi+1+B =m(xi+x)+B A(x1,y1)B(x2,y2)Pi(xi,yi)Pi+1(xi+1,yi+1)dy=kdxdx3.1.33.
3、1.3DDADDA算法算法算法算法(Digital Differential Algorithm)(Digital Differential Algorithm)通过同时对通过同时对x,yx,y各增加一个小的增量各增加一个小的增量,计算下一步的计算下一步的x,yx,y值。在一个值。在一个迭代算法中迭代算法中,如果每一步的如果每一步的x,yx,y值是用前一步的值加上一个增量来获得值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。那么这种算法称为增量算法。第2页/共82页4光栅中光栅中 x=1直线的递推公式直线的递推公式 yi+1yi+(y2-y1)/(x2-x1)xi+1xi+1do
4、uble x=x1,y=y1;m=(y2-y1)/(x2-x1);int k=abs(x2-x1);for(int i=0;ix10,y2y10第3页/共82页5oxyk1讨论讨论:oxyk1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+kk x1,y2 y1)以（以（x1,y1）为起点）为起点第5页/共82页7DDADDA算法的优、缺点算法的优、缺点 DDA算法的本质算法的本质:效率低效率低,不利于硬件实现不利于硬件实现 直观可行直观可行 DDA算法也是一个算法也是一个增量算法增量算法。缺陷缺陷:做除法做除法;须采用浮点数据计算须采用浮点数据计算要取整数要取整数-算法
5、效率不高算法效率不高算法程序实现算法程序实现k=abs(x2-x1);if(abs(y2-y1)k)double deltx=(x2-x1)/k;double delty=(y2-y1)/k;for(int i=0;i=k;i+)x+=deltx;/x=x+deltx;y+=delty;/y=y+delty;k=abs(y2-y1);putpixel(int)x,(int)y,2);用数值方法解微分方程用数值方法解微分方程(数值微分法数值微分法)第6页/共82页81.问题的提出问题的提出 2.基本思想基本思想 a.效率的意义效率的意义b.希望找到一个简单的判决条件希望找到一个简单的判决条件,迅
6、速确定直线上的点。迅速确定直线上的点。借助于一个决策变量借助于一个决策变量 d的正负符号的正负符号,来确定下一个该点亮的象素点来确定下一个该点亮的象素点。最逼近最逼近Pi+1点的点的象象素点是素点是Ti+1点还是点还是Si+1点？由点？由ti+1与与si+1二者的相对大小决定。二者的相对大小决定。若若ti+1si+1,则取则取Si点点(xi+1,yi)ti+1与与si+1二者的大小可以由二者的大小可以由si+1-ti+1的正负来判定。的正负来判定。stTiSi(r,q)3.1.43.1.4直线的直线的直线的直线的BresenhamBresenham算法算法算法算法第7页/共82页9 为讨论方便
7、为讨论方便,假定假定:直线斜率直线斜率k在在 0,1 之之 间间起点坐标起点坐标 A(x1,y1)终点坐标终点坐标 B(x2,y2)将直线平移到原点将直线平移到原点则起点坐标则起点坐标（0，0),终点坐标终点坐标B(dx,dy)dx=x2-x1dy=y2-y1其中其中直线方程为：直线方程为：且且其中其中r=xi-1,q=yi-1stT Ti iS Si i(r,q)所以所以定义定义di=dx(s-t)为决策变量为决策变量第8页/共82页10经推导经推导 di+1=di+2dy-2dx*(yi-yi-1)如果如果1)当当di0，即，即s-t0,st,则点亮则点亮Ti，2)当当di0，即，即s-t
8、0,s=0点亮点（点亮点（1，1）点亮点（点亮点（2，1）d3=d2+2dy-12*4=7=0d2=d1+2(dy-dx)12*(4-5)=-1=0点亮点（点亮点（4，3）d4=d3+2(dy-dx)52*(4-5)=3=0点亮点（点亮点（5，4）举例举例:从点从点A(0,0)到到B(5,4)画一直线画一直线.di0di0yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;第10页/共82页12一个完整的直线算法应考虑以下几个方面一个完整的直线算法应考虑以下几个方面1.水平线水平线2.垂直线垂直线4.直线的斜率为直线的斜率为m,|m|15.|m|16.y07.x yIn
9、ter=0d=2(x*dx-y*dy)+2*dy-dxi=1;putpixel(x,y,color)d0YNYNd0 x=x+s1 y=y+s2d=d+2(dy-dx)inter=1x=x+s1d=d+2*dyy=y+s2i=i+1YYNN第12页/共82页14void line(int x1,int y1,int x2,int y2,int c)/*参数参数c为直线的颜色为直线的颜色*/int dx,dy,x,y,d,const1,const2,tmp;int s1,s2,inter;dx=abs(x2-x1);dy=abs(y2-y1);if(x2x1)s1=1;else s1=-1;if
10、(y2y1)s2=1;else s2=-1;if(dydx)tmp=dx;dx=dy;dy=tmp;inter=1;else inter=-1;d=2*dy-dx;const1=2*dy;/*注意此时误差的注意此时误差的*/const2=2*(dy-dx);/*变化参数取值变化参数取值.*/x=x1;y=y1;putpixel(x,y,c);for(i=1;i=0)y+=s2;x+=s1;d+=const2;else if(inter=1)y+=s2;else x+=s1;d+=const2;putpiexl(x,y,c);第13页/共82页15生成直线算法的进一步改进生成直线算法的进一步改进
11、1987年有人提出二步法，即没循环一次不是绘制一个象素，而年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。只可能出现的四种情况只可能出现的四种情况A AB BC CD D同样，我们先考虑当直线的斜率同样，我们先考虑当直线的斜率m属于区间属于区间0，1时，在时，在x方方向每增加两个单元向每增加两个单元第14页/共82页163.2.1圆弧的扫描法圆弧的扫描法已知圆的圆心坐标为（已知圆的圆心坐标为（xc,yc），半径为），半径为R圆的直角坐标方程表示为圆的直角坐标方程表示为 (x-xc)2+
12、(y-yc)2=R2x0=xc-Ry0=y yc cxi+1=xi+1yi+1(xi+1,Round(yi+1)缺点缺点:(1)运算速度慢运算速度慢(2)显示质量不好显示质量不好(xc,yc)(xc-R,yc)角度角度DDA算法算法圆弧的扫描法圆弧的扫描法正负法、圆弧的正负法、圆弧的Bresenham算法、算法、T-N方法等方法等3.23.2圆弧的生成算法圆弧的生成算法圆弧的生成算法圆弧的生成算法第15页/共82页17由圆的参数方程由圆的参数方程推导出圆弧的增量算法的表达式推导出圆弧的增量算法的表达式:缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。缺点：所产生的圆是不封闭的，且该圆
13、的半径有不断增大的趋势。取微分取微分令令x0=Ry0=0起点起点(x0,y0)=02,为所画圆弧的圆心角为所画圆弧的圆心角单位为弧度单位为弧度d 2-m 角度增量，角度增量，m 为整数。为整数。已知圆的圆心坐标为（已知圆的圆心坐标为（0,0），半径为），半径为R(0,0)(R,0)3.2.23.2.2角度角度角度角度DDADDA算法算法算法算法(近似法近似法近似法近似法)第16页/共82页18PiPi+1原因：原因：Pi+1是在是在Pi上加一个小的矢量而得到，这上加一个小的矢量而得到，这个矢量垂直于位置矢量个矢量垂直于位置矢量Pi。因此新的半径经常比前一个半径大，从而因此新的半径经常比前一个半
14、径大，从而得到的曲线是一条螺线。得到的曲线是一条螺线。将第二式中的将第二式中的 xi 用用 xi+1 代替代替,则有则有:yi+1=yi+xi+1d=yi+(xi-yid)d=d xi+(1-d2)yixi+1=xi-yid为椭圆为椭圆 d 2-m，当，当m=4时，此椭圆与精确圆之间的误差时，此椭圆与精确圆之间的误差E1.63.2.33.2.3椭圆差分法椭圆差分法椭圆差分法椭圆差分法第17页/共82页192023/3/31 hjy-19dPi+1PiOXY1 pixel=R sin dd=arc sin-11/R令：令：3.2.43.2.4旋转法旋转法旋转法旋转法第18页/共82页20 xy(
15、xc,yc)方程方程若若F(x,y)0点点(x,y)在圆在圆外外若若F(x,y)=0点点(x,y)在圆在圆上上2.F(x,y)=0 是二阶光滑是二阶光滑FFFF1.F(x,y)=0 划分平面域为3个点集函数的特点：函数的特点：FF圆的方程为：圆的方程为：3.每一个点的曲率半径步长 (1 pixel)3.2.53.2.5正负法（隐函数曲线正负法（隐函数曲线正负法（隐函数曲线正负法（隐函数曲线)第19页/共82页21(0,R)若点若点Pi在圆内或圆上，在圆内或圆上，即即 F(xi,yi)0若点若点Pi在圆外，在圆外，即即 F(xi,yi)0以第一个以第一个1/4圆弧为例，取圆弧的最上方点为起始点圆
16、弧为例，取圆弧的最上方点为起始点(x0,y0)，x0=0 y0=R点点Pi+1取取R点，即点，即xi+1=xi+1,yi+1=yi点点Pi+1取取B点点，即，即xi+1=xi,yi+1=yi-1由当前点由当前点Pi(xi,yi)选择下一点选择下一点Pi+1(xi+1,yi+1)的规则是：的规则是：xyo第20页/共82页22则则当当xi+1=xi+1,yi+1=yi时时，当当xi+1=xi,yi+1=yi-1时时，第21页/共82页23结论结论第一个第一个1/4圆弧的正负法算法：圆弧的正负法算法：若若F(xi,yi)0（点在内侧，下一点选外侧）（点在内侧，下一点选外侧）若若F(xi,yi)0（
17、点在外侧，下一点选内侧）（点在外侧，下一点选内侧）xi+1=xi+1,yi+1=yixi+1=xi,yi+1=yi-1已知圆心坐标为（已知圆心坐标为（xc,yc），半径为），半径为R，起始点起始点(x0,y0)x0=xc y0=yc+R第22页/共82页以坐标原点为圆心的第一象限以坐标原点为圆心的第一象限1/4圆为例圆为例XYOV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)(0,R)(R,0)起点为起点为(0,R)，按顺时针方向生成圆，按顺时针方向生成圆则则y为为x的单调递减函数的单调递减函数设设P(xi,yi)点为当前点圆上的亮点点为当前点圆上的亮点下一个该
18、显示的象素有三种可能下一个该显示的象素有三种可能:右方象素右方象素H、右下方右下方D、下方象素下方象素V决定一象素使其与真正圆的距离的平方最小决定一象素使其与真正圆的距离的平方最小222)1(RyxmiiV-+=222)1()1(RyxmiiD-+=2 22 22 2)1 1(R Ry yx xmmi ii iH H-+=圆在与点圆在与点P(xi,yi)附近光栅网格的相附近光栅网格的相交关系只有交关系只有5种种123451.基本思想基本思想3.2.63.2.6圆弧的圆弧的圆弧的圆弧的BresenhamBresenham算法算法算法算法第23页/共82页25五种情况分解图：五种情况分解图：H,D
19、,V全在圆内全在圆内H H在圆外，在圆外，D,VD,V在圆内在圆内D在圆上，在圆上，H在圆外，在圆外，V在圆内在圆内D,H在圆外，在圆外，V在圆在圆内内D,V,H 全在圆外全在圆外3HDV5HDV4HDV2DVHV(xV(xi i,y,yi i-1)-1)P(xP(xi i,y,yi i)H(xH(xi i+1,y+1,yi i)D(xD(xi i+1,y+1,yi i-1)1)1 12 23 34 45 51HDV取取D点点取取H点或点或D点点取取D点或点或V点点取取H点点取取V点点第24页/共82页首先计算圆心到右下角象素首先计算圆心到右下角象素D的距离平的距离平方与圆心到圆弧上的点的距离
20、平方之差方与圆心到圆弧上的点的距离平方之差如果如果i0,说明说明D点在圆内点在圆内,只能是只能是1,2情情况，可选况，可选D点或点或H点点设设 为圆到象素为圆到象素H的距离平方与圆到象素的距离平方与圆到象素D的距离平方之的距离平方之差。差。|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|Mh Md如果如果 0,应选应选D(xi+1,yi-1)如果如果=0,规定选规定选D(xi+1,yi-1)V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123第25页/共82页对于情况对于情况2，左下角，左下角D总是位于圆内，总是位于圆内，而而H点
21、总是位于圆外点总是位于圆外(xi+1)2+(yi-1)2-R20 =2(i+yi)-1对于情况对于情况1,由于由于y为一单调递减函数，只能选取为一单调递减函数，只能选取H点点因为：因为：(xi+1)2+(yi)2-R20(xi+1)2+(yi-1)2-R20 =(yi-1)2-(yi)2=0V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|第26页/共82页如果如果i0,说明说明D点在圆外点在圆外,只能是只能是4,5情况，情况，可选可选V点或点或D点点设设 为圆到象素为圆到象素D的
22、距离平方与圆到象的距离平方与圆到象素素V的距离平方之差。的距离平方之差。|(xi+1)2+(yi-1)2-R2|-|(xi)2+(yi-1)2-R2|如果如果 0,如果如果=0,规定选规定选D(xi+1,yi-1)说明圆到说明圆到D点的距离大点的距离大 应选应选V(xi,yi-1)情况情况4:由于由于D在圆外，而在圆外，而V在在圆内圆内:(xi+1)2+(yi-1)2-R2=0(xi)2+(yi-1)2-R20结论与情况结论与情况4是一致的是一致的对于情况对于情况3,应选应选D点点V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)45第27页/共82页归纳总结：归
23、纳总结：当当i0时，时，0,取取D(xi+1,yi-1)点点当当i0时，时，0,取取V(xi,yi-1)点点当当i=0时，时，取取D(xi+1,yi-1)点点V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)第28页/共82页30水平移动到水平移动到H(xi+1,yi)点点Xi+1=xi+1yi+1=yii+1=(xi+1+1)2+(yi+1-1)2-R2(xi+1)2+(yi-1)2-R2 i+2xi+1+1对角移动到对角移动到D点点Xi+1=xi+1yi+1=yi-1i+1=i+2xi+1-2yi+1+2移动到移动到V点点Xi+1=xiyi+1=yi-1i+1
24、=i-2yi+1+1V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)圆弧的圆弧的Bresenham算法的优点算法的优点:起点和终点准确，分布均匀，计算简单。起点和终点准确，分布均匀，计算简单。由上面的分析由上面的分析,增量算法的递推公式增量算法的递推公式:第29页/共82页31画圆心为画圆心为(0,0),半径半径R=8的四分之一的圆弧的四分之一的圆弧初始条件初始条件:x1=0;y1=8;R=8 1=(x1+1)2+(y1-1)2-R2=1+49-64=-140;HD=2(1+y1)-1=2(-14+8)-1=-130取取H点点 2=1+2x2+1=-14+2*1
25、+1=-110 HD=2(2+y2)-1=2(-11+8)-1=-70取取D点点取取H点点点亮点点亮点(0,8)可能点亮可能点亮H或或D点点x2=1 y2=8 3=2+2x3+1=-11+2*2+1=-60 x3=2y3=8x4=3y4=74=3+2x4-2y4+2=-6+2*3-2*7+2=-120 HD=2(3+y4)-1=2(-12+7)-1=-110取取H点点x4=4y4=75=4+2x5+1=-12+2*4+1=-30取取D点点x5=5y5=66=5+2x5-2y5+2=-3+2*5-2*6+2=-30取取D点点x6=6y6=5V(xi,yi-1)P(xi,yi)H(xi+1,yi)
26、D(xi+1,yi-1)第30页/共82页7=6+2x6-2y6+2=-3+2*6-2*5+2=10取取D点点x7=7y7=4 DV=2(6-x6)-1=2(1-6)-1=-110 DV=2(7-x7)-1=2(9-7)-1=30取取V点点x8=7y8=39=8-2y8+1=9-2*3+1=40 DV=2(9-x8)-1=2(4-7)-1=-70 DV=2(10-x9)-1=2(18-8)-1=190取取V点点x10=8y10=111=10-2y10+1=19-2*2+1=160 DV=2(11-x10)-1=2(16-8)-1=150取取V点点x11=8y11=0第31页/共82页33Yy=
27、0YN结束结束 起点起点x=0 y=RD0YNYN1/4圆程序流程图圆程序流程图第32页/共82页34上机：上机：1.编制圆弧正负法的算法程序；编制圆弧正负法的算法程序；（下次上机时提交）（下次上机时提交）2.读懂并上机调试、运行圆弧的读懂并上机调试、运行圆弧的Bresenham算法程序；算法程序；手工：手工：画圆心为画圆心为(0,0),半径半径R=10的四分之一的圆弧用圆弧的的四分之一的圆弧用圆弧的Bresenham算法计算各个算法计算各个象象素点的坐标值素点的坐标值作业作业:1.完成直线完成直线DDA算法程序的实现算法程序的实现2.画（画（0，0）到（）到（8，4）之间的线段）之间的线段3
28、.完成直线完成直线Bresenham算法完整程序算法完整程序第33页/共82页353.3.1概概述述曲线曲线规则曲线规则曲线可用标准的解析式来描述的曲线。如圆、可用标准的解析式来描述的曲线。如圆、椭圆、抛物线、双曲线、渐开线、摆线等椭圆、抛物线、双曲线、渐开线、摆线等自由曲线自由曲线无法用标准的曲线方程来描述的曲线，通常由无法用标准的曲线方程来描述的曲线，通常由实际测量得到的一系列散乱的数据点实际测量得到的一系列散乱的数据点(型值点型值点)来确定。如汽车的外形曲线、等高线等。来确定。如汽车的外形曲线、等高线等。计算机显示曲线的基本原理是计算机显示曲线的基本原理是“以直代曲以直代曲”,即用许多能
29、满足精即用许多能满足精度要求的短的直线段代替曲线度要求的短的直线段代替曲线.如正多边形逼近圆如正多边形逼近圆3.33.3规则曲线的生成算法规则曲线的生成算法规则曲线的生成算法规则曲线的生成算法第34页/共82页36xyo圆圆-圆上任意一点的曲率都相等圆上任意一点的曲率都相等,因此因此用角度用角度DDA算法在屏幕上会产生较好的图算法在屏幕上会产生较好的图像像.1.椭圆等角度椭圆等角度DDA算法算法椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。希望：希望：曲率较小的两侧取较大的周长增量曲率较小的两侧取
30、较大的周长增量曲率较大的两侧取较小的周长增量曲率较大的两侧取较小的周长增量步长为等周长的椭圆算法的缺陷步长为等周长的椭圆算法的缺陷:1.曲率较小的两侧曲率较小的两侧,点过密点过密,曲率较大的两侧曲率较大的两侧,点过稀点过稀.2.将涉及椭圆积分将涉及椭圆积分,计算费时计算费时,算法效率算法效率低低.长轴两端的曲率太大长轴两端的曲率太大,用少数几个等角度用少数几个等角度增量计算出来的点无法较精确地描述椭圆增量计算出来的点无法较精确地描述椭圆.3.3.23.3.2椭圆的显示算法椭圆的显示算法椭圆的显示算法椭圆的显示算法第35页/共82页37因此椭圆用参数方程表示因此椭圆用参数方程表示:其中：圆心的坐
31、标为其中：圆心的坐标为(xc,yc),a,b为椭圆长短、半轴为椭圆长短、半轴,为参数为参数取微分得取微分得:分析分析:1.当当 角接近角接近0或或 时时,两端的曲率较大两端的曲率较大,有有:此时此时|dy|近似近似2.当当 角接近角接近/2或或3/2时时,两端的曲率较大两端的曲率较大,有有:此时此时|dx|近似近似由于由于ab，所以两端点多，而两侧点少。且周长增量大小之比所以两端点多，而两侧点少。且周长增量大小之比 a/b我们希望的周长增量可以自动获我们希望的周长增量可以自动获得得等于弧长等于弧长等于弧长等于弧长第36页/共82页38N椭圆上显示点的个数椭圆上显示点的个数i(xc,yc)第37
32、页/共82页392.椭圆的生成算法椭圆的生成算法-中点法中点法给定椭圆参数中心给定椭圆参数中心(0，0)、长半轴、长半轴a和短和短半轴半轴b，该椭圆的一般方程为：，该椭圆的一般方程为：X2/a2+Y2/b2=1F(x,y)=b2x2+a2y2-a2b2=0中点画圆法可以推广到一般二次曲线的生成中点画圆法可以推广到一般二次曲线的生成现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分，以弧上斜率为步把它分为两部分：上部分和下部分，以弧上斜率为-1的点作为分界。的点作为分界。上半部分，斜率的绝对值上半部分，
33、斜率的绝对值1,单位步长应为单位步长应为X方向，来确定下一个方向，来确定下一个象素的位置象素的位置下半部分，斜率的绝对值下半部分，斜率的绝对值1,单位步长应为单位步长应为Y方向，从而确定下一方向，从而确定下一个象素的位置个象素的位置则该公式可作为中点算法的判别式：则该公式可作为中点算法的判别式：F(x,y)0说明说明(x，y)在椭圆边界内在椭圆边界内说明说明(x，y)在椭圆边界上在椭圆边界上说明说明(x，y)在椭圆边界外在椭圆边界外第38页/共82页40椭圆的斜率：椭圆的斜率：dy/dx=-2b2x/(2a2y)中点画椭圆，当我们确定一个象素之后，接着在两个候选点的中中点画椭圆，当我们确定一个
34、象素之后，接着在两个候选点的中点计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。点计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。有一个象素点（有一个象素点（xp,yp),那么下一对候那么下一对候选象素的中点是（选象素的中点是（xp+1,yp-0.5)。xp,ypxp+1,yp-0.5当斜率为当斜率为-1时则：时则：2b2x=2a2y 上半部分的条件是：上半部分的条件是：2b2x=2a2y假如上半部分椭圆假如上半部分椭圆判别式为：判别式为：dp=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2如果如果dp 0,中点在椭圆外，则取右下方的
35、那个象素中点在椭圆外，则取右下方的那个象素且判别式应更新为：且判别式应更新为：dp+1=F(xp+2,yp-1.5)=dp+b2(2xp+3)+2a2(-yp+1)第39页/共82页41弧的起点为（弧的起点为（b,0)第一个中点是第一个中点是(1,b-0.5)判别式的初值判别式的初值 dp0=b2+a2(-b+0.25).步进方向由步进方向由x改为方向改为方向ydp=b2(xp+0.5)2+a2(yp-1)2-a2b2下半部分的终止条件为下半部分的终止条件为y=0假如为椭圆弧的下半部分假如为椭圆弧的下半部分如果上半部分的最后一个象素为（如果上半部分的最后一个象素为（xp,yp)，则，则且应改为
36、从正下方和右下方两个且应改为从正下方和右下方两个象象素中选择一个象素素中选择一个象素中点是（中点是（xp+0.5,yp-1)如果如果dp 0,中点在椭圆外，则取正下方的那个象素中点在椭圆外，则取正下方的那个象素Pl（xp,yp-1）且判别式应更新为：且判别式应更新为：dp+1=F(xp+0.5,yp-2)=dp+a2(2yp+3)在编写程序时应先更新决策变量在编写程序时应先更新决策变量d，再更新（，再更新（x，y）上半部分的终止条件为：上半部分的终止条件为：b2(x+1)3 时，曲线上将出现一个闭环。时，曲线上将出现一个闭环。第57页/共82页59 1962 年法国雷诺年法国雷诺(Renaul
37、t)汽车公司的汽车公司的P.E.Bezier构造了一种以逼近为基础的参数曲线构造了一种以逼近为基础的参数曲线,这种曲线称为这种曲线称为Bezier曲线，并以此为基础曲线，并以此为基础设计了设计了UNISURF系统系统,该公司于该公司于1972 年开始应用此系统。年开始应用此系统。Bezier曲线是由一组折线集，或称之为曲线是由一组折线集，或称之为Bezier曲线的特征多边形来定义的。曲线的特征多边形来定义的。曲线的起点和终点和该多边形的起点和终点重合，且多边形的第一条边和最后一条边表示曲线在起点和终点处的切矢量方向。曲线的起点和终点和该多边形的起点和终点重合，且多边形的第一条边和最后一条边表示
38、曲线在起点和终点处的切矢量方向。3.4.53.4.5 BEZIERBEZIER曲线曲线曲线曲线第58页/共82页60Coons曲线的几何信息是端点的位矢和切矢，曲线的几何信息是端点的位矢和切矢，曲线的形状很大程度上取决于切矢的大小。曲线的形状很大程度上取决于切矢的大小。为了能更加直观地控制曲线的形状为了能更加直观地控制曲线的形状:在两端点切矢上适当选择两个点在两端点切矢上适当选择两个点P0Q1Q0Q1Q0P0=Q0+(1/q)Q0P1=Q1-(1/q)Q1Q0=q(P0-Q0)Q1=q(Q1-P1)P(t)=TMB=t3 t2 t 1 代代入入=t3 t2 t 1 1.三次三次Bezier曲线
39、的公式曲线的公式通过切矢来控制曲线形状是比较困难的通过切矢来控制曲线形状是比较困难的并且用这两点并且用这两点P0 和和P 1以及以及Q0和和Q1四个点来描述控制曲线四个点来描述控制曲线Q0P0 和和Q0P0的长度取为各所在切矢长度的的长度取为各所在切矢长度的1/qP1第59页/共82页61BEZIER曲线的一般表达方式曲线的一般表达方式:P(t)=t3 t2 t 1（0 t 1）当当q=3时，曲线最为接近多边形时，曲线最为接近多边形Q0P0 P 1Q1。令令q3，得三次，得三次Bezier曲线的矩阵表达式：曲线的矩阵表达式：第60页/共82页62B0,3B3,3B2,3B1,3三次三次Bezi
40、er曲线的调和函数曲线的调和函数第61页/共82页63Q0,Q1,Q2,Q3曲线的特征矢量曲线的特征矢量一阶导数的表达式一阶导数的表达式第62页/共82页64用用B曲线逼近直线或圆弧曲线逼近直线或圆弧1.直线直线P(t)=(1-t)3Q1+3(1-t)2t Q2+3(1-t)t2 Q3+t3Q4=(Q4 Q1+3Q2 3Q3)t3+3(Q1 2Q2+Q3)t2+3(Q2-Q1)t+Q1由于由于P(t)为直线为直线,所以有所以有:Q4 Q1+3Q2 3Q3=0Q1 2Q2+Q3=0Q3=Q1+2/3(Q4 Q1)Q2=Q1+1/3(Q4 Q1)P(t)=(1-t)Q1+tQ4为典型的直线参数方程
41、为典型的直线参数方程Q1Q2Q3Q4Q1Q4Q2Q31/31/31/3第63页/共82页652.圆弧圆弧P(t)=(1-t)3Q1+3(1-t)2t Q2+3(1-t)t2 Q3+t3Q4=(Q4 Q1+3Q2 3Q3)t3+3(Q1 2Q2+Q3)t2+3(Q2-Q1)t+Q1半径为半径为1,第一象限的第一象限的1/4圆弧圆弧Q1=1,0Q4=0,1Q2=1,kQ3=k,1P(1/2)=,误差误差=0.0027%OYXQ1(1,0)Q4(0,1)Q2(1,k)Q3(k,1)t=1/2第64页/共82页66 当给定空间当给定空间n+1个点的位置矢量，个点的位置矢量，Bezier曲线上各点坐标的
42、公式为：曲线上各点坐标的公式为：Bi,n(t)Bernstein基函数，调和函数基函数，调和函数Qi构成该曲线的特征多边形各顶点的位置矢量构成该曲线的特征多边形各顶点的位置矢量当当n=3时，时，2.BEZIER曲线曲线第65页/共82页67当当n=1时时Bezier曲线的表达式：曲线的表达式：0=t=1;矩阵表示：矩阵表示：P(t)=t 1-1 11 0Q0Q10=1当当n=2时时Bezier曲线的表达式：曲线的表达式：0=t=1P(t)=t2 t 11-2 1-2 2 01 0 0Q0Q1Q20=t=1矩阵表示：矩阵表示：第66页/共82页68Bezier曲线的不足：曲线的不足：（1）曲线离
43、特征多边形较远，逼近效果不好）曲线离特征多边形较远，逼近效果不好（2）Bezier曲线改变某一个控制点的位置对整条曲线都有影响，曲线改变某一个控制点的位置对整条曲线都有影响，不能作局部修改，不易控制形状。不能作局部修改，不易控制形状。（3）特征多边形的顶点个数决定了）特征多边形的顶点个数决定了Bezier曲线的阶次，并且当曲线的阶次，并且当n较大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；较大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；1972年，年，Gordon（通用汽车公司）（通用汽车公司）,Riesenfeld（20多岁）等人多岁）等人拓扩了拓扩了Bezier曲线
44、，用曲线，用B样条函数代替了样条函数代替了Bernstein函数，从而改进了函数，从而改进了Bezier特征多边形与特征多边形与Bernstein多项式次数有关，且是整体逼近的弱点。多项式次数有关，且是整体逼近的弱点。由空间由空间n+1个控制点生成的个控制点生成的k阶阶B样条曲线是由样条曲线是由L+1(L=n-k+1)段段 B样条曲线逼近而成，每个曲线段的形状仅由点列中的样条曲线逼近而成，每个曲线段的形状仅由点列中的k+1个顺序排列的个顺序排列的点所控制。点所控制。1.概述概述3.4.63.4.6B-SPLINEB-SPLINE曲线曲线曲线曲线第67页/共82页69若从空间若从空间n+1个顶点
45、个顶点Qi（i=0,1,n）中取相邻的三个顶点，构造中取相邻的三个顶点，构造出一段两次均匀出一段两次均匀B样条曲线，其矩阵表示为：样条曲线，其矩阵表示为：2.二次均匀二次均匀B样条曲线样条曲线其中其中1)位置连续位置连续:相邻的两段曲线相邻的两段曲线 Pi(t)和和 Pi+1(t),分别在分别在t=0和和t=1处满足处满足:Pi-1(1)=Pi(0)1 i n-1 代入上式代入上式Qi-1QiQi+1第68页/共82页702)切矢连续：切矢连续：Pi-1(1)=Pi(0)1 i n-2 3)增加柯西条件:(坐标变换后形状不变性)解得解得:其矩阵表达式其矩阵表达式:第69页/共82页71二次均匀
46、二次均匀B样条曲线的特性样条曲线的特性几何特性几何特性首端首端:t=0 末端末端:t=1 曲线段的起点和终点为两线段的中点曲线段的起点和终点为两线段的中点切矢切矢:曲线段与两直线段相切曲线段与两直线段相切Qi+1QiQi-1移动一个控制点移动一个控制点,不影响整体不影响整体,局部性好局部性好第70页/共82页72如图所示如图所示,给出有序的给出有序的n+1个位置矢量个位置矢量Qi（i=0,1,n),每相邻四每相邻四个点一组个点一组,可以依次构成可以依次构成(n-2)个线性组合个线性组合,即即3.三次均匀三次均匀B样条曲线样条曲线Q0Q1Q2Q3Q8Q5Q6Q7Q41)位置连续位置连续:相邻的两
47、段曲线相邻的两段曲线 Pi(t)和和 Pi+1(t),分别在分别在t=0和和t=1处满足处满足:Pi-1(1)=Pi(0)1 i n-1 代入上式代入上式第71页/共82页732)切矢和曲率连续：切矢和曲率连续：Pi-1(1)=Pi(0)P”i-1(1)=P”i(0)(1 i n-2)3)增加柯西条件增加柯西条件:(坐标变换后形状不变性坐标变换后形状不变性)解得解得:和和考虑函数的对称性考虑函数的对称性,可以假设可以假设 X0(t)=X3(1-t)X1(t)=X4(1-t)第72页/共82页74其矩阵表达式其矩阵表达式:Qi-1QiQi+1Qi+2Pi(0)Pi(1)式中式中Qi-1 Qi Q
48、i+1 Qi+2 为特征多边形的四个相邻顶点为特征多边形的四个相邻顶点特征多边形有更多的顶点，则一特征多边形有更多的顶点，则一条完整的条完整的B-Spline曲线将由若干段曲曲线将由若干段曲线所组成。线所组成。第73页/共82页75均匀三次均匀三次B-Spline曲线的几何关曲线的几何关系系1.曲线段首、末端点的位置矢量曲线段首、末端点的位置矢量2.曲线段首、末端点的切矢量曲线段首、末端点的切矢量3.曲线段首、末端点的曲率曲线段首、末端点的曲率 Qi-1QiQi+1Qi+2ABCDPi(1)Pi(0)Pi(0)Pi(1)Pi(0)Pi(1)其中其中ABCD为此段为此段Bezier曲线的特征多边
49、形的四个相邻顶曲线的特征多边形的四个相邻顶点点第74页/共82页76（1）凸包性。即曲线位于控制多边形凸包范围内；）凸包性。即曲线位于控制多边形凸包范围内；（2）几何不变性。曲线的几何形状和位置与坐标系的选择无关；）几何不变性。曲线的几何形状和位置与坐标系的选择无关；（3）变差缩减性。）变差缩减性。（4）连续性。）连续性。（5）局部性。）局部性。（6）造型的灵活性。可构造直线段、尖点、切线等特殊情况。）造型的灵活性。可构造直线段、尖点、切线等特殊情况。4.B-SPLINE曲线的性质曲线的性质第75页/共82页77上机调试上机调试BEZIER曲线的生成程序，并编写曲线的生成程序，并编写B样条曲线
50、程序样条曲线程序。第76页/共82页78double x=x1,y=y1;m=(y2-y1)/(x2-x1);int k=abs(x2-x1);putpixel(int)x,(int)y,2);+x;/x=x+1x+;y+=m;/y=y+m;对于第一象限的直线，如斜率对于第一象限的直线，如斜率1，x1x2，其直线生成的程序为：，其直线生成的程序为：for(int i=1;i1时时,x ,y1因而造成隔行显示因而造成隔行显示解决办法解决办法:将将y看作自变量看作自变量分析：分析：公式变为公式变为:其中其中:m=(x2-x1)/(y2-y1)令令deltx=x;delty=y;第77页/共82页7