第2章 光栅图形学.ppt

《第2章 光栅图形学.ppt》由会员分享，可在线阅读，更多相关《第2章 光栅图形学.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章光栅图形学光栅图形学2002年10月24日12023/4/3上海交通大学计算机系 何援军2r直线光栅化算法直线光栅化算法qDDA算法算法qBresenham算法算法r圆光栅化算法圆光栅化算法q中点算法中点算法q中点整数算法中点整数算法q中点整数优化算法中点整数优化算法22023/4/3上海交通大学计算机系 何援军32.1直线光栅化算法直线光栅化算法rDDA算法（算法（DigitalDifferentialAnalyzer)rBresenham算法算法32023/4/3上海交通大学计算机系 何援军42.1.1DDA算法算法rDDA算法（算法（DigitalDifferentialAna

2、lyzer)q基本原理基本原理q根据直线的增量方程根据直线的增量方程nxi+1=xi+xnyi+1=yi+kxq算得直线理论点的坐标四舍五入得到光栅点算得直线理论点的坐标四舍五入得到光栅点q算法实现算法实现qDavidF.Rogers的描述的描述(适用于所有象限适用于所有象限)qJamesD.Foley的描述的描述(第一象限，且第一象限，且K1)q本教程的描述本教程的描述(适用于所有象限及任何端点适用于所有象限及任何端点)42023/4/3上海交通大学计算机系 何援军51)DavidF.Rogers描述描述r直线的基本微分方程是：直线的基本微分方程是：rDy/Dx常数常数(k)r设直线通过点设

3、直线通过点P1(x1,y1)和和P2(x2,yDy/Dx)，r则直线方程可表示为：则直线方程可表示为：rDy/Dx=(y2-y1)/(x2-x1)=k52023/4/3上海交通大学计算机系 何援军61)DavidF.Rogers描述描述r如果已知第如果已知第i点的坐标，可用步长点的坐标，可用步长StepX和和StepY得到第得到第i+1点的坐标为：点的坐标为：qxi+1=xi+StepXqyi+1=yi+StepY或或yi+1=yi+kStepXr例图中例图中q0k1qStepX=1qStepY=kr将算得的直线上每个点将算得的直线上每个点的当前坐标，按四舍五的当前坐标，按四舍五入得到光栅点的

4、位置入得到光栅点的位置62023/4/3上海交通大学计算机系 何援军71)DavidF.Rogers描述描述/DigitalDifferentialAnalyzer(DDA)routineforrasterizingaline/Thelineendpointsare(xs,ys)and(xe,ye)assumednotequal./Roundisthefunction.Note:ManyRound functionsarefloorfunctions,i.eRound(-8.5)=-9ratherthan-8.Thealgorithmassumesthisisthecase./Approxim

5、atethelinelengthif(|xs-xe|ys-ye|)then/插补长度插补长度Length|xs-xe|;elseLength|ys-ye|;end if72023/4/3上海交通大学计算机系 何援军81)DavidF.Rogers描述描述/Selectthelargerofxorytobeonerasterunit.StepX=(xe-xs)/Length;StepY=(ye-ys)/Length;x=xs;/首点首点y=ys;i=1;/Beginmainloopwhile(iLength)WritePixel(Round(x),Round(y),value);x=x+Step

6、X;y=y+StepY;i+;end while82023/4/3上海交通大学计算机系 何援军92)JamesD.Foley描述描述r令令k=(y2-y1)/(x2-x1)r有：有：yi+1=yi+kStepXr若若0kyq因光栅单位为因光栅单位为1，q可以采用每次可以采用每次x方向增加方向增加1，q而而y方向增加方向增加k的办法得到下一个直线点。的办法得到下一个直线点。92023/4/3上海交通大学计算机系 何援军102)JamesD.Foley描述描述rvoid Line(/设设0k1,xsxerint xs,ys;/左端点左端点rintxe,ye;/右端点右端点rintvalue)/赋给

7、线上的象数值赋给线上的象数值rrint x;/x以步长为单位从以步长为单位从xs增长到增长到xerdouble dx=xe-xs;rdouble dy=ye-ys;rdouble k=dy/dx;/直线之斜率直线之斜率krdoubley=ys;rfor(x=xs;x=xe;x+)rWritePixel(x,Round(y),value);/置象数值为置象数值为valuery+=k;/y移动步长是斜率移动步长是斜率kr/Endofforr/Line102023/4/3上海交通大学计算机系 何援军113)已有算法描述分析已有算法描述分析rRogers描述：描述：q采用采用x=x+StepX，y=y

8、+StepY，q逼近点并不一定是直线的一个最好的逼近；逼近点并不一定是直线的一个最好的逼近；rD.Foley描述：描述：q未分析直线端点不在象素点上的情况；未分析直线端点不在象素点上的情况；q只给出只给出045卦限的描述。卦限的描述。r为避免引起积累误差，为避免引起积累误差，D.Foley描述中采用描述中采用qdoubledx=xe-xs;qdoubledy=ye-ys;qdoublek=dy/dx;/直线之斜率直线之斜率k112023/4/3上海交通大学计算机系 何援军124)本教程描述本教程描述几个注记几个注记122023/4/3上海交通大学计算机系 何援军134)本教程描述本教程描述任意

9、方向直线插补算法任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法rvoidDDALine(rfloatxs,ys;/起点起点rfloatxe,ye;/终点终点rintvalue;/赋给线上的象数值赋给线上的象数值rrintn,ix,iy,idx,idy;rintFlag;/插补方向标记插补方向标记rint Length;/插补长度插补长度rfloat x,y,dx,dy;132023/4/3上海交通大学计算机系 何援军144)本教程描述本教程描述任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法rdx=xe-xs;rdy=ye-ys;r/初始点处理初始

10、点处理rif(fabs(dy)fabs(dx)/x方向跨距长，方向跨距长，|斜率斜率|1rLength=abs(Round(ye)-Round(ys);rFlag=0;riy=Round(ys);/初始初始y点点ridy=isign(dy);/y方向单位增量方向单位增量rx=xs+dx/dy*(float)(iy)-ys);/初始初始x点修正点修正rdx=dx/fabs(dy);/x方向斜率增量方向斜率增量r152023/4/3上海交通大学计算机系 何援军164)本教程描述本教程描述任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法rif (Flag)/x方向单位

11、增量方向单位增量rfor (n=0;n=Length;n+)/x方向插补过程方向插补过程rWritePixel(ix,Round(y),value);rix+=idx;ry+=dy;r/Endofforr/Endofif162023/4/3上海交通大学计算机系 何援军174)本教程描述本教程描述任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法任意方向直线插补算法r else/y方向斜率增量方向斜率增量rfor(n=0;n=Length;n+)/y方向插补过程方向插补过程rWritePixel(Round(x),iy,value);riy+=idy;rx+=dx;r/Endoffor

12、r/Endofelser/Finish172023/4/3上海交通大学计算机系 何援军184)本教程描述本教程描述首点校正对逼近的影响首点校正对逼近的影响首点校正对逼近的影响首点校正对逼近的影响182023/4/3上海交通大学计算机系 何援军192.1.2Bresenham算法算法rBresenham算法算法q基本原理基本原理qBresenham算法算法q整数整数Bresenham算法算法q一般整数一般整数Bresenham算法算法192023/4/3上海交通大学计算机系 何援军202.1.2Bresenham算法算法r从另一个角度看直线光栅化算法的原理：从另一个角度看直线光栅化算法的原理：q

13、一个方向上每次递增（减）一个方向上每次递增（减）1个单位个单位q另一个方向的递增（减）量为另一个方向的递增（减）量为0或或1q取决于实际直线与最近光栅网格点的距离取决于实际直线与最近光栅网格点的距离q这个距离的最大误差为这个距离的最大误差为0.5。202023/4/3上海交通大学计算机系 何援军211)Bresenham的基本原理的基本原理r假定直线斜率假定直线斜率k在在01之间。之间。q考虑考虑x方向每次递增方向每次递增1个单位个单位q决定决定y方向每次递增方向每次递增0或或1。r从从“四舍五入四舍五入”的观点：的观点：r下一个直线的点应为下一个直线的点应为(xi+1,y+k)qy递增递增k

14、后，与当前光栅点误差超过后，与当前光栅点误差超过0.5，递增，递增1qy递增递增k后，与当前光栅点误差小于后，与当前光栅点误差小于0.5，递增，递增0qy递增递增k后，与当前光栅点误差等于后，与当前光栅点误差等于0.5，递增，递增0/1212023/4/3上海交通大学计算机系 何援军221)Bresenham的基本原理的基本原理r引入误差项参数引入误差项参数d：直线与最近光栅点的：直线与最近光栅点的误差，有：误差，有：0d1当当d=0)theny=y+1;/取右上光栅点取右上光栅点d=d-1;/最近光栅点更新最近光栅点更新endifd=d+k;/下一点，下一点，误差更新误差更新r误差项误差项d

15、的初值：的初值：d00232023/4/3上海交通大学计算机系 何援军241)Bresenham的基本原理的基本原理if(d-0.5=0)thenr令令e=d-0.5，d的判别式和初值可简化成：的判别式和初值可简化成：if(e=0)then242023/4/3上海交通大学计算机系 何援军251)Bresenham的基本原理的基本原理if(e=0)theny=y+1;/取右上光栅点取右上光栅点e=e-1;/最近光栅点更新最近光栅点更新endife=e+k;/下一点，下一点，误差更新，增量仍为误差更新，增量仍为kre的初值：的初值：e0=-0.5(=d0-0.5)(d-0.5=0)252023/4

16、/3上海交通大学计算机系 何援军261)Bresenham的基本原理的基本原理rBresenham算法的构思巧妙：算法的构思巧妙：q引入动态误差引入动态误差e，根据，根据e的符号可十分方便地决的符号可十分方便地决定下一个光栅点的位置定下一个光栅点的位置qx方向每次递增方向每次递增1个单位，有：个单位，有：qe0，y方向递增方向递增1，更新光栅点：，更新光栅点：e=e-1qe0.5，选择，选择(1,1)q如果斜率如果斜率0.5，选择，选择(1,0)q如果斜率如果斜率=0.5，随意，随意r应该以点的绝对位置选择应该以点的绝对位置选择q虽然斜率虽然斜率=0)thenry=y+1rNe=Ne2*xr

17、end ifrx=x+1rNe=Ne+2*yrnextirfinishE=E-1E=E+y/x322023/4/3上海交通大学计算机系 何援军334)一般一般Bresenham算法算法r要使第一个八卦的要使第一个八卦的Bresenham算法适用于算法适用于一般直线，只需对以下一般直线，只需对以下2点作出改造：点作出改造：q当直线的斜率当直线的斜率|k|1时，改成时，改成y的增量总是的增量总是1，再用，再用Bresenham误差判别式确定误差判别式确定x变量是变量是否需要增加否需要增加1；qx或或y的增量可能是的增量可能是“+1”或或“-1”，视直，视直线所在的象限决定。线所在的象限决定。332

18、023/4/3上海交通大学计算机系 何援军344)一般一般Bresenham算法算法/Bresenhamsintegerlineresterizationalgorithmforallquadrnts/Thelineendpointsare(xs,ys)and(xe,ye)assumednotequal.Allvariablesareassumedinteger./initializevariablesrx=xs;ry=ys;rx=abs(xe-xs);ry=abs(ye-ys);rsx=isign(xe-xs);rsy=isign(ye-ys);/Swapxandydependingonth

19、eslopeoftheline.rifyxthenrSwap(x,y);rFlag=1;relserFlag=0;rend ifx=xe-xsy=ye-ys342023/4/3上海交通大学计算机系 何援军354)一般一般Bresenham算法算法/initializetheerrortermtocompensateforanonezerointerceptrNe=2*y-x/beginthemainlooprfori=1toxr WritePixel(x,y,value)r if(Ne=0)thenr if(Flag)then /yxrx=x+sxr elsery=y+syr end if /

20、EndofFlagrNe=Ne2*xr end if /EndofNerrory=y+1352023/4/3上海交通大学计算机系 何援军364)一般一般Bresenham算法算法r if(Flag)then/yxry=y+syr elserx=x+sxr end ifrNe=Ne+2*yrnext irfinishx=x+1362023/4/3上海交通大学计算机系 何援军374)一般一般Bresenham算法算法例子例子例子例子372023/4/3上海交通大学计算机系 何援军382.2圆光栅化算法圆光栅化算法382023/4/3上海交通大学计算机系 何援军392.2.1利用圆的八方对称性画圆利

21、用圆的八方对称性画圆r对圆的分析均假定圆心在坐标原点，因为对圆的分析均假定圆心在坐标原点，因为即使圆心不在原点，可以通过一个简单的即使圆心不在原点，可以通过一个简单的平移即可，而对原理的叙述却方便了许多平移即可，而对原理的叙述却方便了许多r即考虑圆的方程为：即考虑圆的方程为：x2+y2=R2392023/4/3上海交通大学计算机系 何援军402.2.1利用圆的八方对称性画圆利用圆的八方对称性画圆rvoidCirclePoints(int x,inty,int value)rrWritePixel(x,y,value);rWritePixel(-x,y,value);rWritePixel(-x

22、,-y,value);rWritePixel(x,-y,value);rWritePixel(y,x,value);rWritePixel(-y,x,value);rWritePixel(-y,-x,value);rWritePixel(y,-x,value);r显然，当显然，当x=0或或x=y或或y=0时，圆上的对称点时，圆上的对称点只有只有4个，因此，个，因此，CirclePoints()需要修正。需要修正。402023/4/3上海交通大学计算机系 何援军412.2.2中点圆算法中点圆算法原理原理r设设d是点是点p(x,y)到圆心的距离，有：到圆心的距离，有：rd=F(x,y)=x2+y2

23、-R2r按照按照Bresenham算法符号变量的思想，以圆的下算法符号变量的思想，以圆的下2个个可选象素中点的函数值可选象素中点的函数值d的符号的符号决定选择决定选择2个可选象个可选象素素T和和B中哪一个更接近圆而作为圆的显示点中哪一个更接近圆而作为圆的显示点？412023/4/3上海交通大学计算机系 何援军422.2.2中点圆算法中点圆算法原理原理rdM=F(xM,yM)=F(xp+1,yp-0.5)=(xp+1)2+(yp-05)2-R2如果如果dM0，表示下一中点，表示下一中点M在圆外，用在圆外，用B点逼近，此时点逼近，此时rdMB=F(xMB,yMB)=F(xp+2,yp-1.5)=(

24、xp+2)2+(yp-1.5)2-R2422023/4/3上海交通大学计算机系 何援军432.2.2中点圆算法中点圆算法原理原理r由于由于rdMT=(xp+2)2+(yp-0.5)2-R2rdMB=(xp+2)2+(yp-1.5)2-R2r的计算量均较大，试用增量法计算之，而的计算量均较大，试用增量法计算之，而rdMT=dMT-dM=2xp+3rdMB=dMB-dM=2xp-2yp+5r算法：根据中点算法：根据中点d的值，决定的值，决定q显示的光栅点（显示的光栅点（T或或B）q计算增量计算增量d（dMT或或dMB）q由由d更新更新d432023/4/3上海交通大学计算机系 何援军442.2.2

25、中点圆算法中点圆算法原理原理r初值初值r由由x0=0，y0=Rr得得xM0=0+1，ryM0=R-0.5rdM0=F(xM0,yM0)r=F(1,R-0.5)r=12+(R-05)2-R2r=1.25-R442023/4/3上海交通大学计算机系 何援军452.2.2中点圆算法中点圆算法实施实施/中点圆算法（假设圆的中心在原点）中点圆算法（假设圆的中心在原点）rvoidMidPointCircle(intradius,intvalue)rrint x=0;rint y=radius;rdoubled=1.25-radius;rCirclePoints(x,y,value);452023/4/3上

26、海交通大学计算机系 何援军462.2.2中点圆算法中点圆算法实施实施r While(yx)rif(d0)/选择选择Trd+=2.0*x+3.0;relse /选择选择Brd+=2.0*(x-y)+5.0;ry-;rrx+;rCirclePoints(x,y,value);r/Endofwhiler/Finish462023/4/3上海交通大学计算机系 何援军472.2.4中点圆整数算法中点圆整数算法原理原理r中点圆算法的半径是整数，而用于该算法中点圆算法的半径是整数，而用于该算法符号判别的变量符号判别的变量d（初值初值d=1.25-radius）采用浮点运算，会花费较多的时间。采用浮点运算，会

27、花费较多的时间。r为了将其改造成整数计算，定义新变量：为了将其改造成整数计算，定义新变量：rD=d-0.25r那么判别式那么判别式d0等价于等价于D-0.25。r在在D为整数情况下，为整数情况下，D-0.25和和Dx)rif(d=x)rCirclePoints(x,y,value);rif(dx)if(d0)/选择选择Td=d+dt;else/选择选择Bd=d+db;db+=2;y-;dt+=2;db+=2;x+;CirclePoints(x,y,value);/Endofwhile/Finish当当R5时，将会在时，将会在x=3,y=4和和x=4,y=3显示两次！显示两次！552023/4/

28、3上海交通大学计算机系 何援军562.2.5中点圆整数中点圆整数优化优化算法算法例子例子562023/4/3上海交通大学计算机系 何援军57总结总结r直线光栅化算法直线光栅化算法qDDA算法算法qBresenham算法算法r圆光栅化算法圆光栅化算法q中点算法中点算法q中点整数算法中点整数算法q中点整数优化算法中点整数优化算法r基本方法基本方法q增量算法增量算法q符号算法符号算法572023/4/3上海交通大学计算机系 何援军58课外作业课外作业r用交互式任意输入一直线段用交互式任意输入一直线段q1)以小正方格作为背景，实现直线的以小正方格作为背景，实现直线的“DDA算法算法”。可以单步，也可自动显。可以单步，也可自动显示直线的光栅化过程。示直线的光栅化过程。q2)用用“Bresenham算法算法”实现上题。实现上题。r用用“中点圆算法中点圆算法”，画出一条圆弧，画出一条圆弧r推推广广“中中点点圆圆算算法法”，画画出出一一个个内内部部填填充充的实心圆。的实心圆。58