图形显示算法基础.ppt_三一办公31ppt.com

资源描述

《图形显示算法基础.ppt》由会员分享，可在线阅读，更多相关《图形显示算法基础.ppt（83页珍藏版）》请在三一办公上搜索。

1、1,所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元。,第7章图形显示算法基础,2,3.1直线的生成算法,基本知识,只有画水平线,垂直线,及正方形对角线时,象素点集的位置才是准确的。,显示一条直线,实际上是用最靠近这条直线的象素点集来近似地表示这条直线.,有限的象素矩阵,画点设备,光栅显示器:缓冲存储器，显示控制器，数/模转换器，阴级射线管（CRT）,在纸上画一条直线和在计算机屏幕上画一条直线有什么本质的区别?,3,生成直线的一般要求是：,1.DDA算法（数值微分法）,2.直线的Bresenha

2、m算法,确定象素最佳逼近某图形的过程通常称为光栅化。,图形生成算法的工作:,在显示器所给定的有限个象素组成的矩阵中,确定最佳逼近于图形的象素点集.,直线光栅化的方法,4,=yi+m*x,yi=m xi+B,yi+1=m xi+1+B,=m(xi+x)+B,DDA算法(Digital Differential Algorithm),通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。,5,光栅中 x=1,直线的递推公式,如果x2x10,y2y10,6,讨论:,xi+1=xi+1yi+1=yi+

3、k,因而造成隔行显示,解决办法:,将y看作自变量,7,结论：第一象限的直线DDA算法：,起点（x1,y1），终点（x2,y2）(x2 x1,y2 y1),以（x1,y1）为起点,8,DDA算法的优、缺点,DDA算法的本质:,效率低,不利于硬件实现,直观可行,DDA算法也是一个增量算法。,缺陷:,做除法;,须采用浮点数据计算,要取整数-算法效率不高,算法程序实现,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;

4、,y+=delty;/y=y+delty;,k=abs(y2-y1);,putpixel(int)x,(int)y,2);,用数值方法解微分方程(数值微分法),9,1.问题的提出,2.基本思想,a.效率的意义,b.希望找到一个简单的判决条件,迅速确定直线上的点。,借助于一个决策变量 d的正负符号,来确定下一个该点亮的象素点。,最逼近Pi+1点的象素点是Ti+1点还是Si+1点？由ti+1与si+1二者的相对大小决定。,若ti+1si+1,则取Ti点(xi+1,yi+1),若ti+1si+1,则取Si点(xi+1,yi),ti+1与si+1二者的大小可以由si+1-ti+1的正负来判定。,直线的

5、Bresenham算法,10,直线方程为：,且,其中r=xi-1,q=yi-1,所以,定义di=dx(s-t)为决策变量,11,经推导 di+1=di+2dy-2dx*(yi-yi-1),如果1)当di0，即s-t0,st,则点亮Ti，,2)当di0，即s-t0,st,则点亮Si，,di+1=di+2(dy-dx),下一个决策变量,下一个决策变量,di+1=di+2dy,起点为(0,0)时,初始值 d1=2dy-dx,12,x=0,y=0,dx=5,dy=4,决策变量的初值d0=2*x*dx-2*y*dy+2*dy-dx,3,点亮点（0，0）,d1=d0+2(dy-dx)32*(4-5)=1=

6、0,点亮点（1，1）,点亮点（2，1）,d3=d2+2dy-12*4=7=0,d2=d1+2(dy-dx)12*(4-5)=-1=0,点亮点（3，2）,d3=d2+2(dy-dx)72*(4-5)=5=0,点亮点（4，3）,d4=d3+2(dy-dx)52*(4-5)=3=0,点亮点（5，4）,13,一个完整的直线算法应考虑以下几个方面,1.水平线,2.垂直线,4.直线的斜率为m,|m|1,5.|m|1,6.y0,7.x0 等,3.45线,Bresenhanm算法的优点：,(3)只有加法和乘 2 运算,在计算机内部是用位移操作实现的,效率高。,因此，Bresenhanm算法的运算速度很快，并适

7、于用硬件实现。,(1)不必计算直线的斜率，因此不必作除法；(2)不用浮点数，只用整数；,14,15,void 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)s2=1;else s2=-1;if(dydx)tmp=dx;dx=dy;dy=tmp;inter=1;else inter=-1;d=2*dy-dx;const1=

8、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);,16,生成直线算法的进一步改进,1987年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。,只可能出现的四种情况,同样，我们先考虑当直线的斜率m属于区间0，1时，在x方向每增加两个单元,17,圆弧的扫描法,已知圆的圆心

9、坐标为（xc,yc），半径为R,圆的直角坐标方程表示为(x-xc)2+(y-yc)2=R2,x0=xc-Ry0=yc,缺点:(1)运算速度慢(2)显示质量不好,角度DDA算法,圆弧的扫描法,正负法、圆弧的Bresenham算法、T-N方法等,3.2圆弧的生成算法,18,由圆的参数方程,推导出圆弧的增量算法的表达式:,缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。,取微分,令,=02,为所画圆弧的圆心角单位为弧度,d 2-m 角度增量，m 为整数。,已知圆的圆心坐标为（0,0），半径为R,角度DDA算法(近似法),19,原因：,Pi+1是在Pi上加一个小的矢量而得到，这个矢量垂直于位

10、置矢量Pi。,因此新的半径经常比前一个半径大，从而得到的曲线是一条螺线。,将第二式中的 xi 用 xi+1 代替,则有:,为椭圆,d2-m，当m=4时，此椭圆与精确圆之间的误差E1.6,椭圆差分法,20,2023/6/19 hjy-20,1 pixel=R sin d,d=arc sin-11/R,令：,旋转法,21,方程,2.F(x,y)=0 是二阶光滑,圆的方程为：,3.每一个点的曲率半径步长(1 pixel),正负法（隐函数曲线),22,若点Pi在圆内或圆上，即 F(xi,yi)0,若点Pi在圆外，即 F(xi,yi)0,以第一个1/4圆弧为例，取圆弧的最上方点为起始点(x0,y0)，x

11、0=0 y0=R,由当前点Pi(xi,yi)选择下一点Pi+1(xi+1,yi+1)的规则是：,23,则,当xi+1=xi+1,yi+1=yi时，,当xi+1=xi,yi+1=yi-1时，,24,结论第一个1/4圆弧的正负法算法：,若F(xi,yi)0（点在内侧，下一点选外侧）,若F(xi,yi)0（点在外侧，下一点选内侧）,已知圆心坐标为（xc,yc），半径为R，,起始点(x0,y0)x0=xc y0=yc+R,以坐标原点为圆心的第一象限1/4圆为例,(0,R),(R,0),起点为(0,R)，按顺时针方向生成圆,则y为x的单调递减函数,设P(xi,yi)点为当前点圆上的亮点,下一个该显示的象

12、素有三种可能:,右方象素H、,右下方D、,下方象素V,决定一象素使其与真正圆的距离的平方最小,圆在与点P(xi,yi)附近光栅网格的相交关系只有5种,1.基本思想,圆弧的Bresenham算法,26,五种情况分解图：,H,D,V全在圆内,H在圆外，D,V在圆内,D在圆上，H在圆外，V在圆内,D,H在圆外，V在圆内,D,V,H 全在圆外,取D点,取H点或D点,取D点或V点,取H点,取V点,首先计算圆心到右下角象素D的距离平方与圆心到圆弧上的点的距离平方之差,如果i0,说明D点在圆内,只能是1,2情况，可选D点或H点,设为圆到象素H的距离平方与圆到象素D的距离平方之差。,|(xi+1)2+(yi)

13、2-R2|-|(xi+1)2+(yi-1)2-R2|Mh Md,如果0,说明圆到D点的距离大于圆到H点的距离，,应选H(xi+1,yi),如果0,应选D(xi+1,yi-1),如果=0,规定选D(xi+1,yi-1),对于情况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)20,结论与情况2是一致的,所以有：(xi+1)2+(yi)2-R2=0,|(xi+1)2+(yi)2-R2

15、(xi)20,结论与情况4是一致的,对于情况3,应选D点,归纳总结：,当i0时，,=0,取H(xi+1,yi)点,0,取D(xi+1,yi-1)点,当i0时，,=0,取D(xi+1,yi-1)点,0,取V(xi,yi-1)点,当i=0时，,取D(xi+1,yi-1)点,31,水平移动到H(xi+1,yi)点,Xi+1=xi+1,yi+1=yi,i+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+1,yi+1=yi-1,i+1=i+2xi+1-2yi+1+2,移动到V点,Xi+1=xi,yi+1=yi-1

16、,i+1=i-2yi+1+1,圆弧的Bresenham算法的优点:起点和终点准确，分布均匀，计算简单。,由上面的分析,增量算法的递推公式:,32,画圆心为(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=-110,HD=2(2+y2)-1=2(-11+8)-1=-70,HD=2(3+y3)-1=2(-6+8)-1=30,取D点,取H点,点亮点(0,8),可能点亮H或D点,x2=1,y2=8,3

17、=2+2x3+1=-11+2*2+1=-60,x3=2,y3=8,x4=3,y4=7,4=3+2x4-2y4+2=-6+2*3-2*7+2=-120,HD=2(3+y4)-1=2(-12+7)-1=-110,取H点,x4=4,y4=7,5=4+2x5+1=-12+2*4+1=-30,HD=2(4+y4)-1=2(-3+7)-1=90,取D点,x5=5,y5=6,6=5+2x5-2y5+2=-3+2*5-2*6+2=-30,HD=2(6+y6)-1=2(-3+6)-1=50,取D点,x6=6,y6=5,7=6+2x6-2y6+2=-3+2*6-2*5+2=10,取D点,x7=7,y7=4,DV=

18、2(6-x6)-1=2(1-6)-1=-110,8=7+2x7-2y7+2=1+2*7-2*4+2=90,DV=2(7-x7)-1=2(9-7)-1=30,取V点,x8=7,y8=3,9=8-2y8+1=9-2*3+1=40,DV=2(9-x8)-1=2(4-7)-1=-70,取D点,x9=8,y9=2,10=9+2x9-2y9+2=4+2*8-2*2+2=180,DV=2(10-x9)-1=2(18-8)-1=190,取V点,x10=8,y10=1,11=10-2y10+1=19-2*2+1=160,DV=2(11-x10)-1=2(16-8)-1=150,取V点,x11=8,y11=0,3

19、4,y=0,结束,起点x=0y=R,D0,D0,1/4圆程序流程图,35,上机：1.编制圆弧正负法的算法程序；（下次上机时提交）2.读懂并上机调试、运行圆弧的Bresenham算法程序；,手工：画圆心为(0,0),半径R=10的四分之一的圆弧用圆弧的Bresenham算法计算各个象素点的坐标值,作业:,1.完成直线DDA算法程序的实现,2.画（0，0）到（8，4）之间的线段,3.完成直线Bresenham算法完整程序,36,概述,规则曲线,可用标准的解析式来描述的曲线。如圆、椭圆、抛物线、双曲线、渐开线、摆线等,自由曲线,无法用标准的曲线方程来描述的曲线，通常由实际测量得到的一系列散乱的数据点

20、(型值点)来确定。如汽车的外形曲线、等高线等。,计算机显示曲线的基本原理是“以直代曲”,即用许多能满足精度要求的短的直线段代替曲线.,如正多边形逼近圆,3.3规则曲线的生成算法,37,圆-圆上任意一点的曲率都相等,因此用角度DDA算法在屏幕上会产生较好的图像.,1.椭圆等角度DDA算法,椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。,希望：曲率较小的两侧取较大的周长增量曲率较大的两侧取较小的周长增量,步长为等周长的椭圆算法的缺陷:,1.曲率较小的两侧,点过密,曲率较大的两侧,点过稀.,2.将涉及椭圆积分,计算费时,算法效率低.,长轴两端的曲率太大,用少数几个等角度增量

21、计算出来的点无法较精确地描述椭圆.,椭圆的显示算法,38,因此椭圆用参数方程表示:,其中：圆心的坐标为(xc,yc),a,b为椭圆长短、半轴,为参数,取微分得:,分析:,1.当角接近0或时,两端的曲率较大,有:,此时|dy|近似,2.当角接近/2或3/2时,两端的曲率较大,有:,此时|dx|近似,由于ab，所以两端点多，而两侧点少。且周长增量大小之比 a/b,我们希望的周长增量可以自动获得,等于弧长,等于弧长,39,N椭圆上显示点的个数,40,2.椭圆的生成算法-中点法,给定椭圆参数中心(0，0)、长半轴a和短半轴b，该椭圆的一般方程为：X2/a2+Y2/b2=1,中点画圆法可以推广到一般二次

22、曲线的生成,现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分，以弧上斜率为-1的点作为分界。,上半部分，斜率的绝对值1,单位步长应为X方向，来确定下一个象素的位置,下半部分，斜率的绝对值1,单位步长应为Y方向，从而确定下一个象素的位置,则该公式可作为中点算法的判别式：,F(x,y),0,说明(x，y)在椭圆边界内说明(x，y)在椭圆边界上说明(x，y)在椭圆边界外,41,椭圆的斜率：dy/dx=-2b2x/(2a2y),中点画椭圆，当我们确定一个象素之后，接着在两个候选点的中点计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。,有一个象素点（x

23、p,yp),那么下一对候选象素的中点是（xp+1,yp-0.5)。,当斜率为-1时则：2b2x=2a2y,上半部分的条件是：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-0.5)=dp+b2(2xp+3),如果dp 0,中点在椭圆外，则取右下方的那个象素,且判别式应更新为：dp+1=F(xp+2,yp-1.5)=dp+b2(2xp+3)+2a2(-yp+1),42,弧

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

25、素Pl（xp,yp-1）,且判别式应更新为：dp+1=F(xp+0.5,yp-2)=dp+a2(2yp+3),在编写程序时应先更新决策变量d，再更新（x，y）,上半部分的终止条件为：b2(x+1)a2（y-0.5),下半部分的d的初值为上半部分计算的最后点,下半部判别式的初值 dp0=b2(x+0.5)2+a2(y-1)2-a2b2,43,或,抛物线标准方程为:y=4ax(a为抛物线焦距),N显示点的个数,抛物线的显示算法,44,基圆圆心在原点的渐开线参数方程为,令起始角s=0,终止角e=,N显示点的个数,渐开线的显示算法,45,基本概念,1.插值-构造一函数，使曲线或曲面严格通过所有的已知点

26、。,通常用已知函数代替被插的函数。,2.逼近-构造一函数，但曲线或曲面不严格通过各型值点，只要求最靠近。,Bezier、B-Spline,型值点,在曲线曲面的描述中，所构造的数学模型要：,保证：1.空间的唯一性 2.物体的有界性、连续性 3.坐标变换后形状不变性（坐标独立性）,3.4自由曲线的生成算法,46,对数学式的一些要求是：,1.有足够强的描述能力（局部、整体光滑）2.易控制（形）、易预测（闭凸包性、变差减小性-不稳、摆动）,曲线的表示方法,47,1）易于处理多值问题；2）在多值的情况下，可以方便地指定曲线的延伸范围；3）具有几何不变性，其形状与坐标的选择无关，可以不依靠坐标系来研究图

27、形的几何性质；4）易于进行几何变换，如仿射变换、射影变换等；5）易于计算曲线上的点（计算方便）；6）易定义空间曲线（规定曲线的范围和边界等）；7）便于曲线的分段描述。,参数曲线描述的优点：,48,1.型值点,2.控制点,指用来控制或调整曲线形状的特殊点。如BEZIER曲线段中的Q1与Q2点。,3.位置矢量,表示曲线上任一点的坐标的矢量 P(t)=x(t)y(t)z(t),指通过测量或计算得到的曲线或曲面上少量描述曲线或曲面几何形状的数据点。,常用名词术语,49,4.切矢量,5.曲率,T单位切矢量,C-弧长,当Q趋向于r时：在极限情况下|P|=C,设以弧长c为参数，曲线的方程为p(c),若曲线上

28、R，Q两点的参数分别为 t 和t t，矢量pp(t+t)-p(t),50,6.几何连续性,指两段曲线或两片曲面在连接处的连续状态。,(1)Q1(1)=Q2(0)C0（几何位置的连续）和G0连续,C1连续（切矢连续）,(3)Q1(t)和Q2(t)在P点处已有C0，C1连续 Q1(1)=Q2(0),C2连续（曲率连续）,51,7.插值函数逼近的重要方法,插值设计方法：要求建立的曲线与曲面数学模型，严格通过已知的每一个型值点。,在曲线、曲面中最常用的是线性插值和抛物线插值。,（1）线性插值,点斜式,两点式,假设给定函数f(x)在两个不同点x1和x2的值，y1=f(x1),y2=f(x2),现要求用一

29、线性函数：y=(x)=ax+b,近似代替y=f(x).,52,（2）抛物线插值-二次插值,(0t 1),设已知f（x）在三个互异点P1,P2,P3,要求构造一个函数(x)，使得(x)在各结点处与f（x）的值相等。,53,8.逼近,逼近设计方法:用这种方法建立的曲线与曲面数学模型只是近似地接近已知的型值点。,逼近最常用的方法是最小二乘法。逼近好坏常用各点偏差的平方和或加权的方差和最小。,9.拟合,拟合是指在曲线、曲面的设计中，用插值或逼近的方法使生成的曲线、曲面达到某些设计要求。如在允许的范围内贴近原始的型值点或控制点序列；曲线、曲面看上去要“光滑”等。,54,三次曲线：,二次曲线：,参数变量的

30、规格化,一次曲线：,0次曲线：,连接两点的多项式的参数方程为：,（A0，A1，A2，A3）为向量常数,一次曲线：,t=1,P1,t=0,P0,P(0)=P0=A0,P(1)=P1=A0+A 1t=P1,P(t)=P0+(P1-P0)t,55,P(0)=P0=A0,P(1)=A0+A 1t+A 1t2=P1,二次曲线：,P(0)=A 1+2A 1t=P0,P(t)=P0+P0 t+(P1-P0-P0)t2,三次曲线：,P(0)=P0=A0,P(1)=A0+A 1t+A 1t2=P1,P(0)=A 1+2A 1t=P0,P(1)=A 1+2A 1t=P1,P(t)=P0+P0 t+(3P1 P1-

31、3P0-2P0)t2+(2P1-2P0+P1+P0)t3,56,三次曲线的参数方程的几何形式如下：,其中 T=t3 t2 t1 1,A=A3 A2 A1 A0T 代数系数矩阵,已知曲线的端点位置矢量及切矢量：P0，P1，P0，P1,P(t)=3A3t2+2A2t+A1,三次参数样条曲线-HERMITE插值曲线,57,P(t)=(2P0-3P1+P0+P1)t3+(3P0+3P1-2P0-P1)t2+P0t+P0=(2t3-3t2+1)P0+(-2t3+3t2)P1+(t3-2t2+t)P0+(t3-t2)P1,令 H1=2t3-3t2+1 H2=-2t3+3t2 H3=t3-2t2+t H4=

32、t3-t2,其中 H=H1 H2 H3 H4 调和函数,调和函数通过端点及其切失量产生整个t值范围内的其余各点列的坐标，并且只与参数t有关，由此便于我们通过修改边界条件来改变曲线形状。,B=P0 P0 P0 P1 T 几何系数矩阵或边界条件矩阵,58,A=MB,P(t)=TMB表示的曲线是由端点及其切矢量定义的三次参数曲线，称为三次Hermite曲线或Ferguson曲线或Coons曲线。,59,Coons曲线的性态分析:,P(t)=H0,0(t)*0,0+H0,1(t)*1,0+H1,0(t)*k,k+H1,1(t)*k,-k,设给出曲线的始点P0=0,0 终点P1=1,0 切矢的方向 P0

33、=k,+k，P 1=k,-k,给出位置矢量曲线P0，P1和切矢量P0，P 1，可以唯一确定一条Coons曲线。,若切矢的方向和大小改变，则曲线的形状也随之变化。,为了求出尖点，可令：,（1）当t=1/2,k=3 时，曲线上将产生一个尖点。曲线不光滑,（2）当 k=0 时，曲线退化为连接两个端点的直线段,（3）当 k3 时，曲线上将出现一个闭环。,60,1962年法国雷诺(Renault)汽车公司的P.E.Bezier构造了一种以逼近为基础的参数曲线,这种曲线称为Bezier曲线，并以此为基础设计了UNISURF系统,该公司于1972年开始应用此系统。,Bezier曲线是由一组折线集，或称之为B

34、ezier曲线的特征多边形来定义的。,曲线的起点和终点和该多边形的起点和终点重合，且多边形的第一条边和最后一条边表示曲线在起点和终点处的切矢量方向。,BEZIER曲线,61,Coons曲线的几何信息是端点的位矢和切矢，曲线的形状很大程度上取决于切矢的大小。,为了能更加直观地控制曲线的形状:在两端点切矢上适当选择两个点,Q0=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的长度取为各所在切矢

35、长度的1/q,62,BEZIER曲线的一般表达方式:,P(t)=t3 t2 t 1,（0t 1）,当q=3时，曲线最为接近多边形Q0P0 P 1Q1。,令q3，得三次Bezier曲线的矩阵表达式：,63,三次Bezier曲线的调和函数,64,Q0,Q1,Q2,Q3曲线的特征矢量,一阶导数的表达式,65,用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=0,Q1 2Q2+Q3=

36、0,Q3=Q1+2/3(Q4 Q1),Q2=Q1+1/3(Q4 Q1),P(t)=(1-t)Q1+tQ4,为典型的直线参数方程,66,2.圆弧,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圆弧,P(1/2)=,误差=0.0027%,67,当给定空间n+1个点的位置矢量，Bezier曲线上各点坐标的公式为：,Bi,n(t)Bernstein基函数，调和函数,Qi构成该曲线的特征多边形各顶点的位置矢量,当n=3时，,2.BEZIER曲线,

37、68,当n=1时Bezier曲线的表达式：,0=t=1;,矩阵表示：,69,Bezier曲线的不足：（1）曲线离特征多边形较远，逼近效果不好（2）Bezier曲线改变某一个控制点的位置对整条曲线都有影响，不能作局部修改，不易控制形状。（3）特征多边形的顶点个数决定了Bezier曲线的阶次，并且当n较大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；,1972年，Gordon（通用汽车公司）,Riesenfeld（20多岁）等人拓扩了Bezier曲线，用B样条函数代替了Bernstein函数，从而改进了Bezier特征多边形与Bernstein多项式次数有关，且是整体逼近的弱点。,由空间

38、n+1个控制点生成的k阶B样条曲线是由L+1(L=n-k+1)段 B样条曲线逼近而成，每个曲线段的形状仅由点列中的k+1个顺序排列的点所控制。,1.概述,B-SPLINE曲线,70,若从空间n+1个顶点Qi（i=0,1,n）中取相邻的三个顶点，构造出一段两次均匀B样条曲线，其矩阵表示为：,2.二次均匀B样条曲线,1)位置连续:,相邻的两段曲线 Pi(t)和 Pi+1(t),分别在t=0和t=1处满足:,71,2)切矢连续：,Pi-1(1)=Pi(0)1 i n-2,其矩阵表达式:,72,二次均匀B样条曲线的特性,几何特性,首端:t=0,末端:t=1,曲线段的起点和终点为两线段的中点,切矢:,曲

39、线段与两直线段相切,移动一个控制点,不影响整体,局部性好,73,如图所示,给出有序的n+1个位置矢量Qi（i=0,1,n),每相邻四个点一组,可以依次构成(n-2)个线性组合,即,3.三次均匀B样条曲线,1)位置连续:,相邻的两段曲线 Pi(t)和 Pi+1(t),分别在t=0和t=1处满足:,74,2)切矢和曲率连续：,Pi-1(1)=Pi(0)P”i-1(1)=P”i(0)(1 i n-2),考虑函数的对称性,可以假设 X0(t)=X3(1-t)X1(t)=X4(1-t),75,其矩阵表达式:,式中Qi-1 Qi Qi+1 Qi+2 为特征多边形的四个相邻顶点,特征多边形有更多的顶点，则一

40、条完整的B-Spline曲线将由若干段曲线所组成。,76,均匀三次B-Spline曲线的几何关系,1.曲线段首、末端点的位置矢量,2.曲线段首、末端点的切矢量,3.曲线段首、末端点的曲率,A,B,C,D,Pi(1),Pi(0),Pi(0),Pi(1),Pi(0),Pi(1),其中ABCD为此段Bezier曲线的特征多边形的四个相邻顶点,77,（1）凸包性。即曲线位于控制多边形凸包范围内；（2）几何不变性。曲线的几何形状和位置与坐标系的选择无关；（3）变差缩减性。（4）连续性。（5）局部性。（6）造型的灵活性。可构造直线段、尖点、切线等特殊情况。,4.B-SPLINE曲线的性质,78,上机调试B

41、EZIER曲线的生成程序，并编写B样条曲线程序。,作业,79,double 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;i=k;i+),因而造成隔行显示,解决办法:,将y看作自变量,分析：,公式变为:,其中:m=(x2-x1)/(y2-y1),令deltx=x;delty=y;,80,改进的Bresenham算法,由图可知若(xi+1)0 yi+1,r

42、=yir+1，(2)若(xi+1)0 yi+1,r=yir，,xi列上已用（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)=yi+1,r-yir-0.5（1）,若B在A的下面，则有(xi+1)0。,81,由式（1）和式（2）可得到,m:=deltay/deltax e:=m-0.5 for i:=1 to deltax do

43、 begin plot(x,y);if e=0 then begin y:=y+1;e:=e-1 end;x:=x+1 e:=e+m end;,f:=2*deltay-deltax for i:=1 to deltax do begin plot(x,y);if f=0 then begin y:=y+1;f:=f-2*deltax end;x:=x+1 f:=f+2*deltay end;,由式（1）和式（2）可得到初值：(x2)=y2-y1-0.5=m-0.5(4)根据这个算法可得下列产生直线的程序：,(xi+2)=yi+2-yi+1,r-0.5=yi+1+m-yi+1,r-0.5(3),

44、82,我们利用上面方法来讨论这个问题。令(xi+2)=yi+2-yir-0.5假定：当yi+2-yir0.5时绘制图A。当0.5 yi+2-yir1 时绘制图B。当1 yi+2-yir1.5 时绘制图C。当yi+2-yir1.5 时绘制图D。,(xi+2)+2m,当(xi+2)0(xi+2)+2m-1,当1(xi+2)0(xi+2)+2m-2,当(xi+2)1,(xi+4)=yi+4-yi+2,r-0.5=yi+2+2m-yi+2,r-0.5,类似式(4)可取(x3)=y3-y1-0.5=2m-0.5相应的程序为：,=,=,83,圆的多边形迫近法,当圆的内接多边形边数足够多时，该多边形可以和

45、圆接近到任意程度，因此在允许的范围内，可以用显示多边形代替显示圆。显示多边形的边可用Bresenham算法来实现。现在来说明如何求圆的内接正多边形。,c,i,Pi+1,Pi,设要绘的圆的圆心为c(xc,yc)，半径为R。设内接多边形的一个顶点为Pi(xi,yi)，cPi的幅角为i（见图3.10），则：xi=xc+Rcosiyi=yc+Rsini 设多边形每条边所对的圆心角为，则下一个顶点Pi+1的坐标为 xi+1=xc+Rcos(i+)=xc+(xi-xc)cos-(yi-yc)sin yi+1=yc+Rsin(i+)=xc+(xi-xc)sin-(yi-yc)cos 用矩阵表示为 xi+1 cos-sin xi-xc xc yi+1 sin cos yi-yc yc 上式就是计算圆的内接正多边形的递推公式。因为是常数，cos和sin只要在开始时计算一次，这样，算一个(xi+1,yi+1)只要作四次乘法运算。,用正多边形迫近圆弧法,=+,

展开阅读全文