《图形显示算法基础》PPT课件.ppt

《《图形显示算法基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图形显示算法基础》PPT课件.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、所谓图元的生成，是指完成图元的参数表示形式所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）由图形软件包的使用者指定）到点阵表示形式到点阵表示形式（光栅显示系统刷新时所需的表示形式）（光栅显示系统刷新时所需的表示形式）的转换。的转换。通常也称扫描转换图元。通常也称扫描转换图元。第第7章图形显示算法基础章图形显示算法基础1直线的生成算法直线的生成算法基本知识基本知识只有画水平线只有画水平线,垂直线垂直线,及正方形及正方形对角线时对角线时,象素点集的位置才是准确的。象素点集的位置才是准确的。显示一条直线显示一条直线,实际上是用最靠实际上是用最靠近这条直线的象素点集来近似地表示近

2、这条直线的象素点集来近似地表示这条直线这条直线.有限的象素矩阵有限的象素矩阵画点设备画点设备 光栅显示器光栅显示器:缓冲存储器，显示控制器，缓冲存储器，显示控制器，数数/模转换器，阴级射线管（模转换器，阴级射线管（CRTCRT）A(x1,y1)、B(x2,y2)、在纸上画一条直线和在计算机屏幕上画一条直线在纸上画一条直线和在计算机屏幕上画一条直线有什么本质的区别有什么本质的区别?2生成直线的一般要求是：生成直线的一般要求是：1.DDA算法（数值微分法）算法（数值微分法）2.直线的直线的Bresenham算法算法 确定象素最佳逼近某图形的过程通常称为确定象素最佳逼近某图形的过程通常称为光栅化光栅

3、化。图形生成算法的工作图形生成算法的工作:在显示器所给定的有限个象素组成的矩阵中在显示器所给定的有限个象素组成的矩阵中,确定确定最佳逼近于图形的象素点集最佳逼近于图形的象素点集.1.象素是均匀分布的象素是均匀分布的2.所画的线应是直的，且有精确的起点和终点所画的线应是直的，且有精确的起点和终点4.4.最后直线的生成速度要快最后直线的生成速度要快3.所显示的亮度应沿直线不变，且与直线的长度和方向所显示的亮度应沿直线不变，且与直线的长度和方向无关。无关。直线光栅化的方法直线光栅化的方法3已知端点已知端点A(x1,y1)、B(x2,y2),直线的微分方程：直线的微分方程：dy/dx=(y2-y1)/

4、(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=kdxdxDDA算法算法(Digital Differential Algorithm)通过同时对通过同时对x,yx,y各增加一个小的增量各增加一个小的增量,计算下一步的计算下一步的x,yx,y值。在一个值。在一个迭代算法中迭代算法中,如果每一步的如果每一步的x,yx,y值是用前一步的值加上一个增量来获得值是用前一步的值加上一个增量来获得,那么这种

5、算法称为增量算法。那么这种算法称为增量算法。4光栅中光栅中 x=1直线的递推公式直线的递推公式 yi+1yi+(y2-y1)/(x2-x1)xi+1xi+1double x=x1,y=y1;m=(y2-y1)/(x2-x1);int k=abs(x2-x1);for(int i=0;ix10,y2y105oxyk1讨论讨论:oxyk1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+kk x1,y2 y1)以（以（x1,y1）为起点）为起点7DDADDA算法的优、缺点算法的优、缺点 DDA算法的本质算法的本质:效率低效率低,不利于硬件实现不利于硬件实现 直观可行直观可行 D

6、DA算法也是一个算法也是一个增量算法增量算法。缺陷缺陷:做除法做除法;须采用浮点数据计算须采用浮点数据计算要取整数要取整数-算法效率不高算法效率不高算法程序实现算法程序实现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);用数值方法解微分方程用数值方法解微分方程(数数值微分法值微分法)81.问题的提出问题的

7、提出 2.基本思想基本思想 a.效率的意义效率的意义b.希望找到一个简单的判决条件希望找到一个简单的判决条件,迅速确定直线上的点。迅速确定直线上的点。借助于一个决策变量借助于一个决策变量 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)直线的直线的B

8、resenham算法算法9 为讨论方便为讨论方便,假定假定:直线斜率直线斜率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)为决策变量为决策变量10经推导经推导 di+1=di+2dy-2dx*(yi-yi-1)如果如果1)当当di0，即，即s-t0,st,则点亮则点亮Ti，2)当

9、当di0，即，即s-t0,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;12一个完整的直线算法应考虑以下几个方面一个完整的直线算法应考虑以下几个方面1.水平线水平线2.垂直线垂直线4.直线的斜率为直线的斜率为m,|m|15.|m|16.y07.x y

10、Inter=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+1YYNN14void 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(y2y1)s

11、2=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);15生成直线算法的进一步改进生成直线算法的进一步改进1987年有人提出二步法，即没循

12、环一次不是绘制一个象素，而年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。只可能出现的四种情况只可能出现的四种情况A AB BC CD D同样，我们先考虑当直线的斜率同样，我们先考虑当直线的斜率m属于区间属于区间0，1时，在时，在x方向方向每增加两个单元每增加两个单元16圆弧的扫描法圆弧的扫描法已知圆的圆心坐标为（已知圆的圆心坐标为（xc,yc），半径为），半径为R圆的直角坐标方程表示为圆的直角坐标方程表示为 (x-xc)2+(y-yc)2=R2x0=xc-Ry0=y yc cxi+1

13、=xi+1yi+1(xi+1,Round(yi+1)缺点缺点:(1)运算速度慢运算速度慢(2)显示质量不好显示质量不好(xc,yc)(xc-R,yc)角度角度DDA算法算法圆弧的扫描法圆弧的扫描法正负法、圆弧的正负法、圆弧的Bresenham算法、算法、T-N方法等方法等圆弧的生成算法圆弧的生成算法17由圆的参数方程由圆的参数方程推导出圆弧的增量算法的表达式推导出圆弧的增量算法的表达式:缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。取微分取微分令令x0=Ry0=0起点起点(x0,y0)=02,为所画圆弧的圆心角为所画圆弧的圆

14、心角单位为弧度单位为弧度d 2-m 角度增量，角度增量，m 为整数。为整数。已知圆的圆心坐标为（已知圆的圆心坐标为（0,0），半径为），半径为R(0,0)(R,0)角度角度DDA算法算法(近似法近似法)18PiPi+1原因：原因：Pi+1是在是在Pi上加一个小的矢量而得到，这上加一个小的矢量而得到，这个矢量垂直于位置矢量个矢量垂直于位置矢量Pi。因此新的半径经常比前一个半径大，从而因此新的半径经常比前一个半径大，从而得到的曲线是一条螺线。得到的曲线是一条螺线。将第二式中的将第二式中的 xi 用用 xi+1 代替代替,则有则有:yi+1=yi+xi+1d=yi+(xi-yid)d=d xi+(1

15、-d2)yixi+1=xi-yid为椭圆为椭圆 d 2-m，当，当m=4时，此椭圆与精确圆之间的误差时，此椭圆与精确圆之间的误差E椭圆差分法椭圆差分法1910/30/2022 hjy-20dPi+1PiOXY1 pixel=R sin dd=arc sin-11/R令：令：旋转法旋转法20 xy(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)正

16、负法（隐函数曲线正负法（隐函数曲线)21(0,R)若点若点Pi在圆内或圆上，在圆内或圆上，即即 F(xi,yi)0若点若点Pi在圆外，在圆外，即即 F(xi,yi)0以第一个以第一个1/4圆弧为例，取圆弧的圆弧为例，取圆弧的最上方点为起始点最上方点为起始点(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)的规则是：的规则是：xyo22则则当当xi+1=xi+1,yi+1=yi时时，当当xi+1=xi,

17、yi+1=yi-1时时，23结论结论第一个第一个1/4圆弧的正负法算法：圆弧的正负法算法：若若F(xi,yi)0（点在内侧，下一点选外侧）（点在内侧，下一点选外侧）若若F(xi,yi)0（点在外侧，下一点选内侧）（点在外侧，下一点选内侧）xi+1=xi+1,yi+1=yixi+1=xi,yi+1=yi-1已知圆心坐标为（已知圆心坐标为（xc,yc），半径为），半径为R，起始点起始点(x0,y0)x0=xc y0=yc+R24以坐标原点为圆心的第一象限以坐标原点为圆心的第一象限1/4圆为例圆为例XYOV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)(0,R)(R,

18、0)起点为起点为(0,R)，按顺时针方向生成圆，按顺时针方向生成圆则则y为为x的单调递减函数的单调递减函数设设P(xi,yi)点为当前点圆上的亮点点为当前点圆上的亮点下一个该显示的象素有三种可能下一个该显示的象素有三种可能:右方象素右方象素H、右下方右下方D、下方象素下方象素V决定一象素使其与真正圆的距离的平方最小决定一象素使其与真正圆的距离的平方最小222)1(RyxmiiV-+=222)1()1(RyxmiiD-+=2 22 22 2)1 1(R Ry yx xmmi ii iHH-+=圆在与点圆在与点P(xi,yi)附近光栅网格的相交附近光栅网格的相交关系只有关系只有5种种123451.

19、基本思想基本思想圆弧的圆弧的Bresenham算法算法25五种情况分解图：五种情况分解图：H,D,V全在圆内全在圆内H H在圆外，在圆外，D,VD,V在圆内在圆内D在圆上，在圆上，H在圆外，在圆外，V在圆内在圆内D,H在圆外，在圆外，V在圆内在圆内D,V,H 全在圆外全在圆外HDVHDVHDVDVHV(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 5HDV取取D点点取取H点或点或D点点取取D点或点或V点点取取H点点取取V点点26首先计算圆心到右下角

20、象素首先计算圆心到右下角象素D的距离平方的距离平方与圆心到圆弧上的点的距离平方之差与圆心到圆弧上的点的距离平方之差如果如果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)12327对于情况对于情

21、况2，左下角，左下角D总是位于圆内，而总是位于圆内，而H点总是位于圆外点总是位于圆外(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|28如果如果i0,说明说明D点在圆外点在圆外,只能是只能是4,5情况，情况，可选可选V

22、点或点或D点点设设 为圆到象素为圆到象素D的距离平方与圆到象素的距离平方与圆到象素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,

23、yi-1)4529归纳总结：归纳总结：当当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)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=y

24、i-1i+1=i-2yi+1+1V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)圆弧的圆弧的Bresenham算法的优点算法的优点:起点和终点准确，分布均匀，计算简单。起点和终点准确，分布均匀，计算简单。由上面的分析由上面的分析,增量算法的递推公式增量算法的递推公式: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+1=

25、-110 HD=2(2+y2)-1=2(-11+8)-1=-70取取D点点取取H点点点亮点点亮点(0,8)可能点亮可能点亮H或或D点点x2=1y2=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)D(xi

26、+1,yi-1)327=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=033Yy=0YN结束结束 起点起点x=0 y=RD

27、0YNYN1/4圆程序流程图圆程序流程图34上机：上机：1.编制圆弧正负法的算法程序；编制圆弧正负法的算法程序；（下次上机时提交）（下次上机时提交）2.读懂并上机调试、运行圆弧的读懂并上机调试、运行圆弧的Bresenham算法程序；算法程序；手工：手工：画圆心为画圆心为(0,0),半径半径R=10的四分之一的圆弧用圆弧的四分之一的圆弧用圆弧的的Bresenham算法计算各个算法计算各个象象素点的坐标值素点的坐标值作业作业:1.完成直线完成直线DDA算法程序的实现算法程序的实现2.画（画（0，0）到（）到（8，4）之间的线段）之间的线段3.完成直线完成直线Bresenham算法完整程序算法完整程

28、序35概述概述曲线曲线规则曲线规则曲线可用标准的解析式来描述的曲线。如圆、可用标准的解析式来描述的曲线。如圆、椭圆、抛物线、双曲线、渐开线、摆线等椭圆、抛物线、双曲线、渐开线、摆线等自由曲线自由曲线无法用标准的曲线方程来描述的曲线，通常由无法用标准的曲线方程来描述的曲线，通常由实际测量得到的一系列散乱的数据点实际测量得到的一系列散乱的数据点(型值点型值点)来确定。如汽车的外形曲线、等高线等。来确定。如汽车的外形曲线、等高线等。计算机显示曲线的基本原理是计算机显示曲线的基本原理是“以直代曲以直代曲”,即用许多能满足精即用许多能满足精度要求的短的直线段代替曲线度要求的短的直线段代替曲线.如正多边形

29、逼近圆如正多边形逼近圆规则曲线的生成算法规则曲线的生成算法36xyo圆圆-圆上任意一点的曲率都相等圆上任意一点的曲率都相等,因因此用角度此用角度DDA算法在屏幕上会产生较好的图算法在屏幕上会产生较好的图像像.1.椭圆等角度椭圆等角度DDA算法算法椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。希望：希望：曲率较小的两侧取较大的周长增量曲率较小的两侧取较大的周长增量曲率较大的两侧取较小的周长增量曲率较大的两侧取较小的周长增量步长为等周长的椭圆算法的缺陷步长为等周长的椭圆算法的缺陷:1.曲率较小的两侧曲

30、率较小的两侧,点过密点过密,曲率较大的两侧曲率较大的两侧,点过稀点过稀.2.将涉及椭圆积分将涉及椭圆积分,计算费时计算费时,算法效率算法效率低低.长轴两端的曲率太大长轴两端的曲率太大,用少数几个等角度用少数几个等角度增量计算出来的点无法较精确地描述椭圆增量计算出来的点无法较精确地描述椭圆.椭圆的显示算法椭圆的显示算法37因此椭圆用参数方程表示因此椭圆用参数方程表示:其中：圆心的坐标为其中：圆心的坐标为(xc,yc),a,b为椭圆长短、半轴为椭圆长短、半轴,为参数为参数取微分得取微分得:分析分析:1.当当 角接近角接近0或或 时时,两端的曲率较大两端的曲率较大,有有:此时此时|dy|近似近似2.

31、当当 角接近角接近/2或或3/2时时,两端的曲率较大两端的曲率较大,有有:此时此时|dx|近似近似由于由于ab，所以两端点多，而两侧点少。且周长增量大小之比所以两端点多，而两侧点少。且周长增量大小之比 a/b我们希望的周长增量可以自动获得我们希望的周长增量可以自动获得等于弧长等于弧长等于弧长等于弧长38N椭圆上显示点的个数椭圆上显示点的个数i(xc,yc)392.椭圆的生成算法椭圆的生成算法-中点法中点法给定椭圆参数中心给定椭圆参数中心(0，0)、长半轴、长半轴a和短和短半轴半轴b，该椭圆的一般方程为：，该椭圆的一般方程为：X2/a2+Y2/b2=1F(x,y)=b2x2+a2y2-a2b2=

32、0中点画圆法可以推广到一般二次曲线的生成中点画圆法可以推广到一般二次曲线的生成现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分，以弧上斜率为把它分为两部分：上部分和下部分，以弧上斜率为-1的点作为分界。的点作为分界。上半部分，斜率的绝对值上半部分，斜率的绝对值1,单位步长应为单位步长应为X方向，来确定下一个方向，来确定下一个象素的位置象素的位置下半部分，斜率的绝对值下半部分，斜率的绝对值1,单位步长应为单位步长应为Y方向，从而确定下一个方向，从而确定下一个象素的位置象素的位置则该公式可作为中点算法

33、的判别式：则该公式可作为中点算法的判别式：F(x,y)0说明说明(x，y)在椭圆边界内在椭圆边界内说明说明(x，y)在椭圆边界上在椭圆边界上说明说明(x，y)在椭圆边界外在椭圆边界外40椭圆的斜率：椭圆的斜率：dy/dx=-2b2x/(2a2y)中点画椭圆，当我们确定一个象素之后，接着在两个候选点的中点中点画椭圆，当我们确定一个象素之后，接着在两个候选点的中点计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。有一个象素点（有一个象素点（xp,yp),那么下一对候那么下一对候选象素的中点是（选象素的中点是（xp+1,yp-0.

34、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,中点在椭圆外，则取右下方的那个象素中点在椭圆外，则取右下方的那个象素且判别式应更新为：且判别式应更新为：dp+1=F(xp+2,yp-1.5)=dp+b2(2xp+3)+2a2(-yp+1)41弧的起点为（弧的起点为（b,0)第一个中点是第一个中点是(1,b-0.5)判别式的初值判别式的初值 dp

35、0=b2+a2(-b+0.25).步进方向由步进方向由x改为方向改为方向ydp=b2(xp+0.5)2+a2(yp-1)2-a2b2下半部分的终止条件为下半部分的终止条件为y=0假如为椭圆弧的下半部分假如为椭圆弧的下半部分如果上半部分的最后一个象素为（如果上半部分的最后一个象素为（xp,yp)，则，则且应改为从正下方和右下方两个且应改为从正下方和右下方两个象象素中选择一个象素素中选择一个象素中点是（中点是（xp+0.5,yp-1)如果如果dp 0,中点在椭圆外，则取正下方的那个象素中点在椭圆外，则取正下方的那个象素Pl（xp,yp-1）且判别式应更新为：且判别式应更新为：dp+1=F(xp+0

36、.5,yp-2)=dp+a2(2yp+3)在编写程序时应先更新决策变量在编写程序时应先更新决策变量d，再更新（，再更新（x，y）上半部分的终止条件为：上半部分的终止条件为：b2(x+1)3 时，曲线上将出现一个闭环。时，曲线上将出现一个闭环。59 1962年法国雷诺年法国雷诺(Renault)汽车公司的汽车公司的P.E.Bezier构造构造了一种以逼近为基础的参数曲线了一种以逼近为基础的参数曲线,这种曲线称为这种曲线称为Bezier曲线，曲线，并以此为基础设计了并以此为基础设计了UNISURF系统系统,该公司于该公司于1972年开始应年开始应用此系统。用此系统。Bezier曲线是由一组折线集，

37、曲线是由一组折线集，或称之为或称之为Bezier曲线的特征多边曲线的特征多边形来定义的。形来定义的。曲线的起点和终点和该多边曲线的起点和终点和该多边形的起点和终点重合，且多边形形的起点和终点重合，且多边形的第一条边和最后一条边表示曲的第一条边和最后一条边表示曲线在起点和终点处的切矢量方向。线在起点和终点处的切矢量方向。BEZIER曲线曲线60Coons曲线的几何信息是端点的位矢和切矢，曲线的几何信息是端点的位矢和切矢，曲线的形状很大程度上取决于切矢的大小。曲线的形状很大程度上取决于切矢的大小。为了能更加直观地控制曲线的形状为了能更加直观地控制曲线的形状:在两端点切矢上适当选择两个点在两端点切矢

38、上适当选择两个点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曲线的公式曲线的公式通过切矢来控制曲线形状是比较困难的通过切矢来控制曲线形状是比较困难的并且用这两点并且用这两点P0 和和P 1以及以及Q0和和Q1四个点来描述控制曲线四个点来描述控制曲线Q0P0 和和Q0P0的长度取为各所在切矢长度的的长度取为各所在切矢长度的1/qP161BEZIER曲线的一般表达方式曲线的一般表达方式:P(t)=t3 t2 t 1（0 t 1）当当q=

39、3时，曲线最为接近多边形时，曲线最为接近多边形Q0P0 P 1Q1。令令q3，得三次，得三次Bezier曲线的矩阵表达式：曲线的矩阵表达式：62B0,3B3,3B2,3B1,3三次三次Bezier曲线的调和函数曲线的调和函数63Q0,Q1,Q2,Q3曲线的特征矢曲线的特征矢量量一阶导数的表达式一阶导数的表达式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+

40、3Q2 3Q3=0Q1 2Q2+Q3=0Q3=Q1+2/3(Q4 Q1)Q2=Q1+1/3(Q4 Q1)P(t)=(1-t)Q1+tQ4为典型的直线参数方程为典型的直线参数方程Q1Q2Q3Q4Q1Q4Q2Q31/31/31/3652.圆弧圆弧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,

41、k)Q3(k,1)t=1/266 当给定空间当给定空间n+1个点的位置矢量，个点的位置矢量，Bezier曲线上各点坐曲线上各点坐标的公式为：标的公式为：Bi,n(t)Bernstein基函数，调和函数基函数，调和函数Qi构成该曲线的特征多边形各顶点的位置矢量构成该曲线的特征多边形各顶点的位置矢量当当n=3时，时，曲线曲线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 12-2 2 031 0 0Q0Q1Q20=t=1

42、矩阵表示：矩阵表示：68Bezier曲线的不足：曲线的不足：（1）曲线离特征多边形较远，逼近效果不好）曲线离特征多边形较远，逼近效果不好（2）Bezier曲线改变某一个控制点的位置对整条曲线都有影响，曲线改变某一个控制点的位置对整条曲线都有影响，不能作局部修改，不易控制形状。不能作局部修改，不易控制形状。（3）特征多边形的顶点个数决定了）特征多边形的顶点个数决定了Bezier曲线的阶次，并且当曲线的阶次，并且当n较较大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；1972年，年，Gordon（通用汽车公司）（通用汽车公司）,R

43、iesenfeld（20多岁）等人拓多岁）等人拓扩了扩了Bezier曲线，用曲线，用B样条函数代替了样条函数代替了Bernstein函数，从而改进了函数，从而改进了Bezier特征多边形与特征多边形与Bernstein多项式次数有关，且是整体逼近的弱点。多项式次数有关，且是整体逼近的弱点。由空间由空间n+1个控制点生成的个控制点生成的k阶阶B样条曲线是由样条曲线是由L+1(L=n-k+1)段段 B样条曲线逼近而成，每个曲线段的形状仅由点列中的样条曲线逼近而成，每个曲线段的形状仅由点列中的k+1个顺序排列的个顺序排列的点所控制。点所控制。1.概述概述B-SPLINE曲线曲线69若从空间若从空间n

44、+1个顶点个顶点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+1702)切矢连续：切矢连续：Pi-1(1)=Pi(0)1 i n-2 3)增加柯西条件:(坐标变换后形状不变性)解得解得:其矩阵表达式其矩阵表达式:71二次均匀二次均匀B样条曲线的特性样

45、条曲线的特性几何特性几何特性首端首端:t=0 末端末端:t=1 曲线段的起点和终点为两线段的中点曲线段的起点和终点为两线段的中点切矢切矢:曲线段与两直线段相切曲线段与两直线段相切Qi+1QiQi-1移动一个控制点移动一个控制点,不影响整体不影响整体,局部性好局部性好72如图所示如图所示,给出有序的给出有序的n+1个位置矢量个位置矢量Qi（i=0,1,n),每相邻四每相邻四个点一组个点一组,可以依次构成可以依次构成(n-2)个线性组合个线性组合,即即3.三次均匀三次均匀B样条曲线样条曲线Q0Q1Q2Q3Q8Q5Q6Q7Q41)位置连续位置连续:相邻的两段曲线相邻的两段曲线 Pi(t)和和 Pi+

46、1(t),分别在分别在t=0和和t=1处满足处满足:Pi-1(1)=Pi(0)1 i n-1 代入上式代入上式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)74其矩阵表达式其矩阵表达式:Qi-1QiQi+1Qi+2Pi(0)Pi(1)式中式中Qi-1 Qi Qi+1 Qi+2 为特征多边形的四个相邻顶点为特征多边形的四个相邻顶点特征多边形

47、有更多的顶点，则一特征多边形有更多的顶点，则一条完整的条完整的B-Spline曲线将由若干段曲线曲线将由若干段曲线所组成。所组成。75均匀三次均匀三次B-Spline曲线的几何关系曲线的几何关系1.曲线段首、末端点的位置矢量曲线段首、末端点的位置矢量2.曲线段首、末端点的切矢量曲线段首、末端点的切矢量3.曲线段首、末端点的曲率曲线段首、末端点的曲率 Qi-1QiQi+1Qi+2ABCDPi(1)Pi(0)Pi(0)Pi(1)Pi(0)Pi(1)其中其中ABCD为此段为此段Bezier曲线的特征多边形的四个相邻顶点曲线的特征多边形的四个相邻顶点76（1）凸包性。即曲线位于控制多边形凸包范围内；）

48、凸包性。即曲线位于控制多边形凸包范围内；（2）几几何何不不变变性性。曲曲线线的的几几何何形形状状和和位位置置与与坐坐标标系系的的选选择无关；择无关；（3）变差缩减性。）变差缩减性。（4）连续性。）连续性。（5）局部性。）局部性。（6）造造型型的的灵灵活活性性。可可构构造造直直线线段段、尖尖点点、切切线线等等特特殊殊情况。情况。4.B-SPLINE曲线的性质曲线的性质77上机调试上机调试BEZIER曲线的生成程序，并编写曲线的生成程序，并编写B样样条曲线程序条曲线程序。78double x=x1,y=y1;m=(y2-y1)/(x2-x1);int k=abs(x2-x1);putpixel(i

49、nt)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;79改进的改进的Bresenham算法算法由图可知由图可知 若若(xi+1)0 yi+1,r=yir+1，(2)若若(xi+1)0 yi+1,r=yir，x xi iX Xi+1i+1

50、Y Yi,ri,rY Yi+1,ri+1,rB BA AD D(x)的几何意义的几何意义C Cxi列上已用（列上已用（xi,yir）作为表示直线的点，作为表示直线的点，设设B点是直线上的点，其坐标为（点是直线上的点，其坐标为（xi+1,yi+1）显然下一个表示直线的点（显然下一个表示直线的点（xi+1,yi+1,r）只能从图中的只能从图中的C或者或者D点中去选。点中去选。设设A为为CD边的中点边的中点若若B在在A点上面则应取点上面则应取D点作为点作为（xi+1,yi+1,r）否则应取否则应取C点（点（xi+1,yi,r）为了能确定为了能确定B在在A点上面或下面，令点上面或下面，令(xi+1)=