基于自适应步长的直线生成算法
ISSN 1000-0054CN 11-2223/N
清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2006年第46卷第10期
2006,V o l.46,N o.1021/40
1719-1722
基于自适应步长的直线生成算法
黄斌茂, 张 利
(清华大学电子工程系,北京100084)
收稿日期:2005-07-13
基金项目:国家自然科学基金资助项目(60172027)作者简介:黄斌茂(1981-),男(汉),江西,硕士研究生。通讯联系人:张利,副教授,
E-mail:chin azh angli@mail.tsingh https://www.wendangku.net/doc/886389023.html,
摘 要:为了改进计算机图形学中画线算法的效率,提出一种基于自适应步长的直线生成算法和一种集成了对称性、最大公约数和自适应步长的集成算法。由于直线仅包含一种或两种与斜率有关的像素模式,算法利用这一特性,自适应地采用最佳步长,在单次判决中生成多个像素。通过综合使用直线像素的中点对称性、最大公约数性质以及像素模式的有限性等3种相互独立的特性,集成算法在单次判决中可生成更多像素。算法的仿真结果表明:新算法生成直线的效率更高、速度更快。
关键词:Bresenham 算法;自适应步长;对称性;最大公约
数;像素模式
中图分类号:T P 391.4文献标识码:A
文章编号:1000-0054(2006)10-1719-04
Self -adaptive step straight -line algorithms
HUA NG Binmao ,ZH ANG Li
(Department of Electronic Engineering ,
T s inghua University ,Beij ing 100084,China )
Abstract :Line draw ing algorithm in computer grap hics sys tems is improved w ith a self-adaptive s tep straight-line algor ith m and an oth er integrated algorithm th at combines self-adaptive step algorithm w ith th e s ymmetr y an d greatest com mon divisor (GCD)-based algor ith ms.Th e self-adaptive step algorithm uses the limited pixel patter ns inherent in line s egments to adaptively determine the best step that corres ponds to the line slope an d then gen erates m ulti-pixels in each judgemen t.T he integrated algorithm utilizes the sym metry,GCD,an d limited pixel patterns and gen erates more p ixels in each https://www.wendangku.net/doc/886389023.html,parisons w ith Bresen ham 's algorithm sh ow th at the integrated algorithms are m ore effective and efficient.
Key words :Bresen ham's algorithm ;self-adaptive steps;s ymmetr y;
greatest common divisor (GCD);pixel patter n
直线段(简称直线)是图形的基本单元,图形渲染的速度很大程度上取决于直线的生成速度。
Br esenham 算法[1]
是目前使用最为广泛的直线生成算法,它采用整数加减运算,避免了浮点数操作和乘除运算,从而极大地提高了算法的效率。在该算法的
基础上,研究界提出了多种改进算法。其改进思路可分为两类:1)将直线分割成多条短线段,采用并行算法生成直线[2]
;2)通过一次误差判别操作,在一次循环中生成多个像素[312]。
直线上的像素点关于直线中点对称,文[5]利用这一特性,每个循环生成两个像素点。
对端点为S (x s ,y s )及E (x e ,y e )的直线,当 x e -x s 和 y e -y s 的最大公约数r 不为1时,直线上有r 段像素模式相同的线段。文[4]通过在每个循环内生成r 个像素,加速了直线的生成。但当r =1时,该算法比Brensenham 算法效率要低。文[68]采用N 步长(N ≥2)直线生成方法,将八分圆分成多个子区,每个子区有N +1种像素模式,根据直线的斜率可决定其子区归属。该算法每个循环可生成N 个像素。其不足是:每个子区中的N +1种像素模式的初始化开销很大;步长固定,不能采用最佳步长。还有一些研究者结合对称性、多步长、最大公约数提出集成算法[9]。
文[10]简要地提出自适应步长的思想,但未给出推导证明与具体算法;文[11,12]在直线斜率为0< m <0.5时,一次生成多个像素以提高直线的生成效率,但没有注意到直线像素模式关于m =±0.5的对称性。此外,文[11,12]都没有给出算法的仿真结果。
上述各种改进算法的共同点是在每个循环中生成多个像素,但每次生成的像素个数固定,不能自适应地采用最合适的步长。本文利用直线在八分圆中像素模式的对称性,以及任一直线只有一种或者两种与斜率相关的像素模式这一特性,提出一种基于
自适应步长的直线生成算法,并进一步集成基于对称性及基于GCD 的直线生成算法,给出一种更高效的集成算法。
1 自适应步长直线生成算法
本文将“直线”约定如下:起点为S (x s ,y s ),终点为E (x e ,y e ),斜率为m 。并使用D 、X 表示相邻像素(x i ,y i )和(x i +1,y i +1)处于对角位置或水平位置。误差判别项为p ,所需的条件测试数为t ,更新p 所需的操作数为i ,更新x 、y 所需的加减法操作数为a 。整数的加减操作、条件测试、累加操作都分别占用一个单位的运行时间,衡量算法性能的指标TEP(theor etical ev aluation perform ance)[10]
可这样
计算:TEP =t +a +i 。
直线斜率m 存在4种一般情况:-∞ -1,-1 1.1 直线的一些性质 对起点为S (x s ,y s )、终点为E (x e ,y e )的直线 L 1,通过将L 1的起点S (x s ,y s )平移为S 1 (0,0),可得到起点为S 1(0,0)、终点为E 1 (P ,Q )的直线L 0(其中P =x e -x s ,Q =y e -y s )。 性质1 当0 1DX n 2D …DX n Q +1 ; 2) i ∈N ,且1≤i ≤Q +1,n i 满足n i ∈N ,n i >0,且当2≤i ≤Q ,n i ∈{A ,A -1},其中A =1/m ; 3)n 1、n Q +1满足n 1=n Q +1=1/2m ; 4)m =Q Q + ∑Q +1 i =1 n i . 证明 初始化x =0、y =0、x end =P ,误差判别项p =m ;p 代表点C (理想直线与网格线的交点)与栅格点B 之间的差值。显然,若p <0.5,像素点B 比A 的误差要小,反之则应该使用像素点 A 逼近理想直线(按图1的情况,应该使用像素A )。 图1 中点判决准则 由此可得生成直线像素时的判决准则和误差判别项p 的更新方式为: if(p <0.5){p =p +m ;下一个像素相对位置为X ;}else {p =p -1;下一个像素相对位置为D ;}1)假设存在两个连续的D ,不妨设它们位于X n i 之后,设决定第n i 个X 的误差项为p i (-0.5≤p i <0.5);由假设,更新之后有p i +1=p i +m 且0.5≤p i +1<1,p i +2=p i -1+2m 且0.5≤p i +2<1。 由于0 2)假设存在i (2≤i ≤Q )使得n i 有其他取值,即n i A 。设决定n i 个X 之前的D 的误差项为p (0.5≤p <1且p -m <0.5)。由此可知:决定第n i 个X 的误差项为:p ′=p +n i m -1(-0.5≤p ′<0.5),决定第n i 个X 之后的D 的误差判别项为p ″=p +(n i +1)m -1(0.5≤p ″<0.5+m )。由于A =1/m ,因而1-m A 时,n i m ≥(A +1)m >1,由此可得:p ′≥0.5,矛盾!当n i 线L 0可表示为:L 0=X n 1DX n 2D …DX n Q +1。 3)由于直线关于中点对称,易得n 1=n Q 。 对于X n 1D ,假设决定D 的误差判别项为p ,此时p =(n 1+1)m ,且有0.5≤p <0.5+m ,由此可得 n 1=n Q =1/2m . 4)由L 0的表达式易得,证明过程略。图2显示了起点为S (0,0)、终点为E (14,3)的直线L 0的像素模式。该直线可表达为X 2 DX 3 DX 4 DX 2 。由性质1易得:A =14/3=4,n 1=n 4=14/6=2。由图可见:除去端点处的两小段像素X 2,该直线中存在的两种像素模式为DX 3和DX 4。由于篇幅限制,只能示意短直线的像素模式,对于稍长的直线,像素模式的有限性和重复性将更加明显。 图2 直线像素模式示意图 性质2 位于同一个八分圆中的直线关于m = 1720 清华大学学报(自然科学版)2006,46(10) ±0.5具有像素模式的对称性。 证明 不失一般性,假定0 将L1表达式中的X和D互换,得到与L1的像素模式相对应的像素模式为L2=D n1X D n2X…X D n Q,由性质14)易得L1的斜率m′=1-m(0.5< m′<1)。 由此可知,任取一条斜率满足0 1.2 基于自适应步长直线生成算法的实现 由性质1可知,在一个循环内可以生成A个(X A-1D)或A+1个(X A D)像素点。由于0 误差判别项p的初始值为 p=(n1+1)m-0.5=(1/2m+1)m-0.5. 更新方式为p=p+Am-1, if p<0{p=p+m;//像素模式:X A D}; else{//像素模式:X A-1D}。 在上文讨论直线性质的时候使用的误差判别项p是浮点数,更新p需要使用浮点数操作。浮点数操作耗费的运算量大,需要转换为整数操作,以提高算法效率。 m=Q/P,假设A=1/m=2n1+r2=21/2m+ r2,P=A Q+r1。乘以2P后误差判别项p的初始值为:p=2P(n1+1)m-P=(2-r2)Q-r1。 更新方式为p=p+2QA-2P=p-2r1, if p<0{p=p+Q;//像素模式:X A+1D}; else{//像素模式:X A D}。 基于自适应步长的直线生成算法SAS(self-adaptive step straight-line alg orithm)的C语言算法描述如下(0 初始化: x=P=x e-x s, y=Q=y e-y s,r1= mod(P,Q),A=P/Q,r2=mod(A,2),two Dy= y+ y;tw o R1=r1+r1;p=(2-r2) y-r1;x=x s;y=y s;y en d=y e;x end=x+n1; w hile(x≤x end)//生成起始点及前面n1个X {wr ite pixel(x,y);x=x+1;} y=y+1;p=p-two R1; w hile(y {if p<0 {p=p+tw o Dy;//像素模式:X A+1D x end=x+A+2; w hile(x≤x end)//生成A+2个像素; {wr ite pixel(x,y);x=x+1;} y=y+1;} else {x end=x+A+1;//像素模式:X A D; w hile(x≤x end)//生成A+1个像素; {wr ite pixel(x,y);x=x+1;} y=y+1;}} x end=x e; w hile(x≤x end)//生成1个D,以及n k个X; {wr ite pixel(x,y);x=x+1;} 由于对称性、最大公约数和自适应步长分别利用了直线的不同性质,因而可将它们集成起来,当GCD(P,Q)=r时,一个循环中可以生成2A r或者2(A+1)r个像素。集成算法ISAS(integ rated self-adaptive step line draw ing alg orithm)描述如下: 1)初始化: x=P=x e-x s, y=Q=y e-y s, r1=m od(P,Q),A=P/Q,c=GCD(P,Q),r2= m od(A,2),q x=P/c,q y=Q/c,two Dy= y+ y, tw o R1=r1+r1;p=(2-r2) y-r1;x=x s+1;y= y s;x1=x s+q x-1;y1=y s+q y; 2)从起点S(x s,y s)开始,x方向以q x为步长, y方向以q y为步长,生成c段连续短直线的端点共c+1个; 3)生成第一段直线中首末两端各n1-1个像素。更新x=x+n1,y=y+1,x1=x1-n1,y1= y1-1;将生成的像素x方向以q x为步长,y方向以q y为步长,复制生成剩余c-1段短直线首末两端的像素; 4)如果y 5)如果p<0,更新p为:p=p+tw o Dy;使用的像素模式为A+1个X和1个D;生成第一段直线上的2(A+2)个点;更新x=x+A+2,y= y+1,x1=x1-A-2,y1=y1-1; 否则(亦即p≥0),使用的像素模式为A个X 和1个D;生成第一段直线上的2(A+1)个点;更 1721 黄斌茂,等: 基于自适应步长的直线生成算法 新x=x+A+1,y=y+1,x1=x1-A-1,y1= y1-1; 复制生成剩下c-1段短直线的对应像素; 6)算法转4); 7)如果y=y1,算法转8),否则,算法转9); 8)生成第一段短直线从x到x1的像素,该段像素的纵坐标为y;以x方向以q x为步长,y方向以q y为步长拷贝生成剩下c-1段上的对应像素; 9)Exit. 2 仿真结果分析和比较 各种改进算法常常过高估计了算法的效率:利用对称性的文[5]认为其算法速度是Bresenham算法的2倍;利用N步长的文[68]认为其算法的效率是Bresenham算法的N倍,文[4]综合使用对称性和GCD改进算法,认为可以将Bresenham算法的速度提高1～11倍。上述文献普遍使用如下假设: 1)只考虑更新误差判别项所耗费的运算,忽略条件判断以及x、y的累加操作;2)若一次能生成M个点,那么算法的速度将是Bresenham算法的M倍。 实际上,进行一次条件判断或者累加操作耗费的运算量和一次加/减操作几乎一样多。本文使用前面定义的T EP作为比较算法的性能指标。 对于不同斜率的直线,基于对称性、最大公约数的改进算法以及SAS和ISAS算法等4种算法的效率各不相同。表1比较了当斜率为3/13,4种算法相对于Br esenham算法的T EP。其中P= x代表直线的长度,c为 x、 y的最大公约数。 表1 斜率为3/13时4种改进算法的相对TEP P c T EP/% 对称G CD SA S ISA S 91 764.7187.4775.9665.22 1431164.6581.5174.1458.76 7285664.5873.0271.5549.55 131310164.5672.0771.2648.53 521340164.5571.2071.0047.59 从表1可见,SAS算法能有效地改进Br esenham算法的画线效率;SAS算法和最大公约数c没有关系。ISAS算法集成了对称性、GCD和自适应步长,其性能则是最好的。对于该组斜率为3/13的直线,ISAS几乎可以将直线的生成速度提高1倍。 3 总结与讨论 本文通过使用直线中像素模式的重复性及有限性,提出一种基于自适应步长的直线生成算法SAS,并结合直线对中点的对称性和最大公约数法,得到一种更有效的ISAS算法。SAS和ISAS算法都可以有效地改进Bresenham算法的画线效率。 从仿真结果中,注意到基于GCD的Bresenham 改进算法和SAS、ISA S算法的额外运算开销较大,对于短直线来说,这笔额外的开销往往会抵消算法所节省的运算量。未来需要进一步研究如何优化算法以降低额外开销。此外,若对不同长度和斜率的直线自适应地采用最佳算法,还能进一步地提高直线的生成效率。 参考文献 (References) [1]Bresenham J E.Algorithm for compu ter con tr ol of a digital plotter[J].I B M S y stems J our nal,1965,4(1):2530. [2]W right W E.Parallelization of Bresenham's line and circle algorithm s[J].I E EE C G&A,1990,10(5):6067. [3]Earns haw W E.L ine track ing for incr emental plotters[J]. T he Comp uter J our nal,1980,23(1):4652. [4]Ch en J X.M ultiple segmen t line s can-conversion[J]. Comp uter G rap hics Forum,1997,16(5):257268. [5]Gardner P L.M odifications of Bresenham's algorithm for dis play[R].IBM T ech Dis clos ure Bull.18,1975:1595 1596. [6]W U Xiaolin,Rokn e J G.Double-step increm ental generation of lines and circles[J].C omp ute r Vision,Gr ap hics and I mag e P rocessing,1987,37(3):331344. [7]Bao P G,Rokn e J G.Quadru ple-step line generation[J]. Comp uter s&G rap hics,1989,13(4):461469. [8]Gill G W.N-s tep in cremental straig ht-line algorithms[J]. I E EE CG&A,1994,14(3):6672. [9]Rokne J G,Wyvill B,W U Xiaolin.Fast line s can-conversion [J].AC M T ransactions on G rap hics,1990,9(4):376388. [10]Boyer V,Borud in J J.Auto-adaptive step straight-line algorithm[J].I EE E CG&A,2000,20(5):6769. [11]郑宏珍,赵辉.改进的Bres en ham直线生成算法[J].中国图 象图形学报,1999,4A(7):605609. ZHENG Hon gzhen,ZHAO Hui.T he improvement of Bresenham algorithm[J].J our nal of I mag e and G rap hics, 1999,4A(7):606609.(in Chinese) [12]李高平,檀结庆.改进的直线Bres enh am算法[J].合肥工业 大学学报(自然科学版),2003,26(5):9991004. LI Gaoping,T AN Jieqing.A m od ified Br esenham's algorithm of line-d raw in[J].Journal of H e f ei Univ ersity of T echnology,2003,26(5):10001004.(in Chin es e) 1722清华大学学报(自然科学版)2006,46(10) 实验报告 课程名称计算机图形学 实验名称DDA直线生成算法编程的实现实验类型验证型 实验地点计通学院304实验日期2010-03-29指导教师 专业 班级 学号 姓名 成绩 辽宁石油化工大学计算机与通信工程学院 实验报告说明 1、封面内容 （1）课程名称：实验所属的课程的名称。 （2）实验名称：要用最简练的语言反映实验的内容。要求与实验指导书中相一致。 （3）实验类型：说明是验证型实验、设计型实验、创新型实验还是综合型实验。 2、正文内容 实验报告的正文内容须包括以下内容： （1）实验目的：目的要明确，要抓住重点，符合实验指导书中的要求。 （2）实验内容：说明本实验的主要内容。 （3）实验原理：简要说明本实验项目所涉及的理论知识。 （4）实验环境：实验用的软硬件环境（配置）。 （5）实验方案：对于验证性型实验，写明依据何种原理、操作方法进行实验；对于设计型和综合型实验，写明依据何种原理、操作方法进行实验，并画出硬件组成图、软件流程图、设计思路和设计方法，再配以相应的文字说明；对于创新型实验，除符合设计型和综合型实验要求外，还应注明其创新点、特色。（6）实验步骤：写明实验的实施步骤，包括实验过程中的记录、数据。 （7）实验结果与分析：写明实验的最终结果，并对结果进行分析，做出结论。（8）实验中遇到的问题及解决方法：写明实验过程中遇到的问题及所采取的解决方法。 （9）实验总结（在封底上）：写出对本次实验的心得体会、思考和建议。 实验原理：已知线段的起点坐标()11x y ，终点坐标()22x y ，直线的点斜 式方程为：y m x b =?+，斜率和截距分别为：2121y y m x x -= - ， 11b y m x =-? 。沿x 的增量为x ?，沿y 的增量为y ?，即： 1x y m ?= ??，y m x ?=??。当1m ≤时，取x 为一个像素单位长，即x 每次增加一个像素，然后利用公式计算相应的y 值：1k k k y y y y m x -=+?=+??，相反1m >时，可以通过质量y ?来计算相应的x 值：1k k k x x x x m y -=+?=+??。 实验内容：新建一个Win32 Application 的典型“Hello World ”程序，工程 命名为：DDA 直线生成算法，打开DDA 直线生成算法.cpp 文件， 在里面加入代码： void DDA_line(HDC hdc) { double x,y,dx,dy,L,x1=100,x2=400,y1=100,y2=400; if(abs(x2-x1)>=abs(y2-y1)) L=abs(x2-x1); else L=abs(y2-y1); dx=(x2-x1)/L; dy=(y2-y1)/L; x=x1,y=y1; for(int k=1;k<=L;k++) { SetPixel(hdc,x,y,RGB(255,0,255)); x=x+dx; y=y+dy; Sleep(10); } } 实验结果：调用程序运行得出一下结果： 以下是Bresenham的直线生成算法和整圆生成算法，已调试过，没有任何问题。Bresenham直线生成算法 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy, i; float k,e; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=-0.5; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+k; if(e>=0) { y++;e=e-1;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); } 当取e=2*dy-dx时，可以消除浮点和除法运算 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy, i,e; float k; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=2*dy-dx; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+2*dy; if(e>=0) { y++;e=e-2*dx;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); } 实验二 直线的生成算法的实现 班级 08信计2班 学号 59 姓名 分数 一、实验目的和要求 1.理解直线生成的基本原理。 2.掌握几种常用的直线生成算法。 3.利用Visual C++实现直线生成的DDA 算法。 二、实验内容 1.了解直线的生成原理，尤其是Bresenham 画线法原理。 2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。 3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。 三、实验步骤 1.直线的生成原理： （1）DDA 画线法也称数值微分法，是一种增量算法。是一种基于直线的微分方程来生成直线的方法。 （2）中点画线法原理 以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01 之间。中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最近者已经确定为(,)p p P x y ，用小实心圆表示。那么，下一个与直线最近的像素只能是正右方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。又假设Q 是理想直线与垂直线1p x x =+的交点。显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。 （3）B resenham 画线法原理 直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。 给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为： 0b kx y y)F(x,=--= （3-1） 构造中点偏差判别式d 。 b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),( 课程名称：计算机图形学指导教师：罗晓辉 上机实践名称：基本图形（直线）生成算法 年级：2008 姓名：孔广波 学号：312008********* 上机实践成绩： 上机实践日期：2011-4-10 实验一: 直线生成算法 上机实践报告 一、实验目的 理解直线生成的基本原理，掌握儿种常见的直线生成算法，利用Microsoft Visual C++6.0实现直线生成的DDA算法。 二、实验内容： 1）了解直线的生成原理。 2）掌握儿种基本的直线生成算法：DDA画线法、Bresenham画线法、中点画线法。 3）利用Microsoft Visual C++6.0实现直线生成的DDA算法，在屏幕上任意生成一条直线。 三、实验步骤： 1）预习教材关于直线的生成原理。 2）仿照教材关于直线生成的DDA算法，使用Microsoft Visual C++6.0实现该算法。 3）调试、编译、运行程序。 四、实验分析、源程序和结果： （1.1）中点算法分析： 中点画线算法原理示意图 直线斜率：k属于[0, 1] 线段的隐式方程：F(x,y) = ax + by + c = 0 ((x0 , y0), ( xl , yl )为两端点，式中a = yO - yl , b = xl - xO , c = xO * yl - xl * yO) 直线上方的点：F(x , y) > 0 直线下方的点：F ( x , y ) < 0 构造判别式：d = F(M) = F(Xp+l,Yp + 0.5) 由d>0, V0 可判定下一个象素，d 的初始值：d0 = F( X0 + 1 , Y0 + 0.5 ) = F( X0 , Y0 ) + a + 0.5b 因(X0, YO)在直线上，F(X0 , YO ) = 0,所以，dO = a + 0.5b (1.2)具体实现代码： void CGView::Line_DDA(long plxjong ply,long p2x,long p2y,CDC *pDC)〃画直线算法实现 ( int a,b,del 1 ,del2,d,x,y; b=p2x-plx; a=ply-p2y; d=2*a+b; dell=2*a; del2=2*(a+b); x=plx; y=piy； pDC->SetFixel(x,y,mJPenColor)； while(x 实验2 直线生成算法实现 1.实验目的 理解基本图形元素光栅化的基本原理, 掌握一种基本图形元素光栅化算法, 利用0penGL 实现直线光栅化的DDA算法。 2.实验内容 (1)根据所给的直线光栅化的示范源程序, 在计算机上编译运行, 输出正确结果。 (2)指出示范程序采用的算法, 以此为基础将其改造为中点线算法或Bresenham算法,写 入实验报告。 (3)根据示范代码,将其改造为圆的光栅化算法,写入实验报告。 (4)了解和使用OpenGL的生成直线的命令,来验证程序运行结果。 3.实验原理 示范代码原理DDA算法。下面介绍OpenGL画线的一些基础知识和glutReshapeFunc（）函数。 (1)数学上的直线没有宽度,但0penGL的直线则是有宽度的。同时, OpenGL的直线必须是有限长度,而不是像数学概念那样是无限的。可以认为, OpenGL的“直线”概念与数学上的“线段”接近,它可以由两个端点来确定。这里的线由一系列顶点顺次连接而成, 有闭合和不闭合两种。 前面的实验已经知道如何绘“点”,那么OpenGL是如何知道拿这些顶点来做什么呢? 是依次画出来,还是连成线? 或者构成一个多边形? 或是做其他事情? 为了解决这一问题, OpenGL要求:指定顶点的命令必须包含在glBegin函数之后, glEnd函数之前(否则指定的顶点将被忽略),并由glBegin来指明如何使用这些点。 例如: glBegin(GL P0INTS) , glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES,则两个点将被认为是直线的两个端点, OpenGL将会画出一条直线。还可以指定更多的顶点, 然后画出更复杂的图形。另一方面, glBegin支持的方式除了GL_POINTS和GL_LINES,还有GL LINE STRIP、GL LINE L0〇P、GL TRIANGLES、GL TRIANGLE STRIP、GL TRIANGLE_FAN等几何图元。 (2) 首次打开窗口、移动窗口和改变窗口大小时, 窗口系统都将发送一个事件, 以通知程序员。如果使用的是GLUT,通知将自动完成,并调用向glutReshapeFunc注册的函数。该函数必须完成下列工作: ①重新建立用作新渲染画布的矩形区域。 ②定义绘制物体时使用的坐标系。 如: void Reshape(int w, int h) { glViewport(0, 0, (GLsizei) w, (GLsizei) h); 第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为L(P0 ,P1)，则直线段L的斜率 L的起点P 的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L 的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y = kx i+1+b i+1 = k1x i+b+k x = y i+k x 所以，当x =1; y i+1 = y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。 DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 图3.1.1 直线段的扫描转换 注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y 进行四舍五入后取整，这使得它不利于硬件实现。 实验二基本图形元素（直线）生成算法的实现 1．实验目的： 理解基本图形元素光栅化的基本原理，掌握一种基本图形元素光栅化算法，利用OpenGL实现直线光栅化的DDA算法。 2．实验内容： （1）根据所给的直线光栅化的示范源程序，在计算机上编译运行，输出正确结果； （2）指出示范程序采用的算法，以此为基础将其改造为中点线算法或Bresenham算法，写入实验报告； （3）根据示范代码，将其改造为圆的光栅化算法，写入实验报告； （4）了解和使用OpenGL的生成直线的命令，来验证程序运行结果。 3．实验原理： 示范代码原理参见教材直线光栅化一节中的DDA算法。下面介绍下OpenGL画线的一些基础知识和glutReshapeFunc()函数。 （1）数学上的直线没有宽度，但OpenGL的直线则是有宽度的。同时，OpenGL的直线必须是有限长度，而不是像数学概念那样是无限的。可以认为，OpenGL的“直线”概念与数学上的“线段”接近，它可以由两个端点来确定。这里的线由一系列顶点顺次连结而成，有闭合和不闭合两种。 前面的实验已经知道如何绘“点”，那么OpenGL是如何知道拿这些顶点来做什么呢？是一个一个的画出来，还是连成线？或者构成一个多边形？或是做其它事情呢？为了解决这一问题，OpenGL要求：指定顶点的命令必须包含在glBegin函数之后，glEnd函数之前（否则指定的顶点将被忽略），并由glBegin来指明如何使用这些点。 例如： glBegin(GL_POINTS); glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES，则两个点将被认为是直线的两个端点，OpenGL将会画出一条直线。还可以指定更多的顶点，然后画出更复杂的图形。另一方面，glBegin 支持的方式除了GL_POINTS和GL_LINES，还有GL_LINE_STRIP，GL_LINE_LOOP，GL_TRIANGLES，GL_TRIANGLE_STRIP， 实验二：直线生成算法 班级 13软件+道铁1班学号 20132110050115姓名丁益 1.实验目的 a)通过实验，进一步理解直线段扫描转换的DDA算法、中点画线自算法 及bresenham算法的基本原理，掌握以上算法生成直线段的基本过程。 b)通过编程，掌握在C/C++环境下完成用DDA算法、中点画线算法及 bresenham算法对任意直线段的扫描转换，以及在C/C++环境下完成用中 点画圆及椭圆的绘制方法。 2.实验内容 c)阅读《openGL三维程序设计》（电子书）第二部分第四章，掌握OpenGL 基本建模方法，并调试其中程序。 d)参考教材第6章，编程实现整数DDA算法、中点画线法和Bresenham 画线法，绘制直线（直线宽度和线型可自定）。 2.1 DDA直线生成 2.1.1算法原理 已知过端点P0（x0,y0），P1（x1,y1）的直线段L(P0,P1)，斜率为k=(y1-y0)/(x1-x0)，画线过程从x的左端点x0开始，向x右端点步进，步长为1个像素，计算相应的y坐标为y=kx+B。计算y i+1 = kx i+B =kx i +B+kx =y i +kx 当x=1,y i+1=y i+k，即当x每递增1，y递增k。由计算过程可知，y与k可能为浮点数，需要取y整数，源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。 2.1.2 算法流程 2.1.3 算法实现关键代码 #include 直线生成算法——Bresenham法 最近的研究涉及在像素图上作直线，自己也不想花时间摸索，于是在网上找到了Bresenham的直线生成算法，有一篇博客讲得清晰明了，但是算法上有些问题，我进行了改进和移植，下面讲解Bresenham的直线生成算法时也是参考这篇博文。 1.算法简介 图1 算法思想：图1中，连接M点和N点的直线经过点B，由于是像素图，所以实际上B 点应该由A点或者C点代替。当B点更靠近A点时，选择点A（x+1,y+1）；当B点更靠近C点时，选择点C（x+1,y）。 因此，当ε+m < 0.5时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点，这里ε为累加误差，表达式为： 式中：表示在第n次计算时的值，表示在第n+1次计算时的值；m就是直线的 斜率。 由于斜率m的值有正有负，有可能为0，也可能为∞，为了避免分别讨论这些情况， 将上述公式两边都乘以dx, 并将ε*dx用ξ表示，则有 式中：表示在第n次计算时的值，表示在第n+1次计算时的值；dx为起 点和终点横坐标之差，dy为起点和终点纵坐标之差。 还需说明一点，由直线斜率的定义 故 值得注意的是，现在我们只考虑dx > dy，且x，y的增量均为正的情况，但实际上有8种不同的情况（但是算法思想不变），如图2所示 如图2 2.算法程序 前文提到的那篇博文提出了一种方法，能将这8种情况都考虑，很巧妙。但是实际应用时发现程序运行结果不是完全对，多次检查之后将程序进行了修改。 修改后的算法VB程序如下 ‘**************************************************************************** Type mypos '自定义数据类型 x As Integer y As Integer End Type ‘**************************************************************************** Function Bresenham(arr() As mypos, x1, y1, x2, y2) Dim x!, y!, dx!, dy!, ux%, uy%, eps! Dim cnt% ReDim arr(100) dx = x2 - x1 dy = y2 - y1 If dx >= 0 Then ux = 1 If dx < 0 Then ux = -1 生成直线的B resenham算法 从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。 在生成直线的算法中，B resenham算法是最有效的算法之一。B resenham算法是一种基于误差判别式来生成直线的方法。 一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。 我们首先讨论m=△y/△x，当0≤m≤1且x1 这两个距离差是 我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(x i+1，y i+1)象素较近，下一个象素点应取(x i+1，y i+1)。 (2)当此值为负时，d1 实验二直线段生成绘制的实现算法 班级 10信计专接本学号 20100504008 姓名吴晓楠分数 一、实验目的和要求： 1.了解计算机图形学的原理、方法和应用。 2.熟悉直线的生成算法，掌握直线的绘制 3.实现C语言编写图形程序。学会了解VC++的基本应用同时了解TC图形 环境配置，学习简单的图形画法，并比较画法的优劣，尝试在计算机实 现，得到图形，验证比较图形。 二、实验内容： 1、掌握直线段的生成算法，并用C/WIN-TC/VC++实现算法，包括中点法生成 直线，微分数值法生成直线段等。 2、编程实现DDA算法、Bresenham算法、中点画线法绘制直线段 三、实验结果分析 1、生成直线的DDA算法 算法思想：一个坐标轴上以单位间隔增量，决定另一个坐标轴上最靠近线段路径的对应整数值。假定x2﹣x1的绝对值大于y2﹣y1的绝对值，取x为一个象素单位长，即x 每次递增一个象素，然后利用下式计算相应的y值：yk+1﹦yk﹢△y﹦yk﹢m·△x 对于|m|＞1的线段，可通过计算由Y方向的增量△y引起的改变来生成直线：xk+1﹦xk﹢△x﹦xk﹢m·△y 生成直线的DDA算法思想是源用初中直线的方程得出来的，而生成直线的中点算法是通过将DDA算法的方程式改为隐函数形式，然后通过与中点的比较确定该取的像素，绘制图线。 /* DDA */ #include ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2006年第46卷第10期 2006,V o l.46,N o.1021/40 1719-1722 基于自适应步长的直线生成算法 黄斌茂, 张 利 (清华大学电子工程系,北京100084) 收稿日期:2005-07-13 基金项目:国家自然科学基金资助项目(60172027)作者简介:黄斌茂(1981-),男(汉),江西,硕士研究生。通讯联系人:张利,副教授, E-mail:chin azh angli@mail.tsingh https://www.wendangku.net/doc/886389023.html, 摘 要:为了改进计算机图形学中画线算法的效率,提出一种基于自适应步长的直线生成算法和一种集成了对称性、最大公约数和自适应步长的集成算法。由于直线仅包含一种或两种与斜率有关的像素模式,算法利用这一特性,自适应地采用最佳步长,在单次判决中生成多个像素。通过综合使用直线像素的中点对称性、最大公约数性质以及像素模式的有限性等3种相互独立的特性,集成算法在单次判决中可生成更多像素。算法的仿真结果表明:新算法生成直线的效率更高、速度更快。 关键词:Bresenham 算法;自适应步长;对称性;最大公约 数;像素模式 中图分类号:T P 391.4文献标识码:A 文章编号:1000-0054(2006)10-1719-04 Self -adaptive step straight -line algorithms HUA NG Binmao ,ZH ANG Li (Department of Electronic Engineering , T s inghua University ,Beij ing 100084,China ) Abstract :Line draw ing algorithm in computer grap hics sys tems is improved w ith a self-adaptive s tep straight-line algor ith m and an oth er integrated algorithm th at combines self-adaptive step algorithm w ith th e s ymmetr y an d greatest com mon divisor (GCD)-based algor ith ms.Th e self-adaptive step algorithm uses the limited pixel patter ns inherent in line s egments to adaptively determine the best step that corres ponds to the line slope an d then gen erates m ulti-pixels in each judgemen t.T he integrated algorithm utilizes the sym metry,GCD,an d limited pixel patterns and gen erates more p ixels in each https://www.wendangku.net/doc/886389023.html,parisons w ith Bresen ham 's algorithm sh ow th at the integrated algorithms are m ore effective and efficient. Key words :Bresen ham's algorithm ;self-adaptive steps;s ymmetr y; greatest common divisor (GCD);pixel patter n 直线段(简称直线)是图形的基本单元,图形渲染的速度很大程度上取决于直线的生成速度。 Br esenham 算法[1] 是目前使用最为广泛的直线生成算法,它采用整数加减运算,避免了浮点数操作和乘除运算,从而极大地提高了算法的效率。在该算法的 基础上,研究界提出了多种改进算法。其改进思路可分为两类:1)将直线分割成多条短线段,采用并行算法生成直线[2] ;2)通过一次误差判别操作,在一次循环中生成多个像素[312]。 直线上的像素点关于直线中点对称,文[5]利用这一特性,每个循环生成两个像素点。 对端点为S (x s ,y s )及E (x e ,y e )的直线,当 x e -x s 和 y e -y s 的最大公约数r 不为1时,直线上有r 段像素模式相同的线段。文[4]通过在每个循环内生成r 个像素,加速了直线的生成。但当r =1时,该算法比Brensenham 算法效率要低。文[68]采用N 步长(N ≥2)直线生成方法,将八分圆分成多个子区,每个子区有N +1种像素模式,根据直线的斜率可决定其子区归属。该算法每个循环可生成N 个像素。其不足是:每个子区中的N +1种像素模式的初始化开销很大;步长固定,不能采用最佳步长。还有一些研究者结合对称性、多步长、最大公约数提出集成算法[9]。 文[10]简要地提出自适应步长的思想,但未给出推导证明与具体算法;文[11,12]在直线斜率为0< m <0.5时,一次生成多个像素以提高直线的生成效率,但没有注意到直线像素模式关于m =±0.5的对称性。此外,文[11,12]都没有给出算法的仿真结果。 上述各种改进算法的共同点是在每个循环中生成多个像素,但每次生成的像素个数固定,不能自适应地采用最合适的步长。本文利用直线在八分圆中像素模式的对称性,以及任一直线只有一种或者两种与斜率相关的像素模式这一特性,提出一种基于 第25卷第10期 计算机应用与软件 Vol 125No .10 2008年10月 Computer App licati ons and Soft w are Oct .2008 改进的Bresenham 直线生成算法 刘 晶 李 俊 孙 涵 (南京航空航天大学信息科学与技术学院 江苏南京210016) 收稿日期:2007-02-01。刘晶,助教,主研领域:计算机图形学,计算机网络。 摘 要 直线是图形的基本元素,其生成算法具有重要意义。在经典的B resenha m 直线生成算法的基础上进行改进,提出一种新 的多点生成算法。该算法利用直线的第一像素行的像素点数目来计算其余各像素行的像素点数目,一次可以预测一个像素行,再利用直线的对称性一次生成两个像素行。新算法既保持B resenha m 算法不使用取整和小数运算的优点,又减少了计算量和循环次数,从而大幅提高了直线生成效率。 关键词 计算机图形学 B resenha m 算法 偏差量 A MOD I F I ED BRESENHAM AL GO R I TH M FO R L INE GENERAT I O N L iu J ing L i Jun Sun Han (College of Infor m ation Science and Technology,N anjing U niversity of Aeronautics and A stronautics,N anjing 210016,J iangsu,China ) Abstract The algorith m of line generati on is an i m portant basic theory of computer graphics .A ne w algorith m f or line generati on is p resen 2ted based on B resenha m algorith m.The p ixel amounts of the p ixel lines can be forecasted,referring t o the p ixel a mount of the first p ixel line .Then,t w o p ixel lines can be dra wn thr ough the sy mmetry of a line .The ne w algorith m i m p r oves the efficiency of straight line generati on without divisi on or deci m al fracti on . Keywords Computer graphics B resenha m algorith m Deviati on 0 引 言 直线是生成各种图形的基本元素,直线生成算法是其它各类图形算法的基础,因此直线的生成算法已得到了人们的广泛研究,并已出现许多有效的算法,其中最著名的是B resenha m 算法。该算法的优点在于不需要进行小数和取整运算,只需要使用整数加法和乘法来计算待生成的像素点。B resenha m 算法的缺点在于效率不高,没有充分利用像素之间的相关性,一次计算只能生成一个像素点[1,2]。 提高直线生成效率可以从两方面考虑:减少生成每个像素点所必需的计算量或一次计算可以生成多个像素点以减少循环次数。W u 和Rokne 对B resenha m 算法进行了改进,提出了双步直线生成算法,该算法一次预测两个而不是一个像素,从而提高了直线生成算法的效率[1]。双步直线生成算法的效率提高有限,某些情况下与B resenha m 算法效率基本一样。文献[3-8]对B resenha m 算法进行了一定程度的改进,但改进幅度不大,主要表现在:改进算法往往引入了浮点运算甚至除法或取整运算,这恰恰破坏了B resenham 算法不进行小数和取整运算的特点。这些改进算法一次计算虽然可以画多个像素点,但运算更加复杂。 本文在对B resenham 算法、双步算法和现有改进算法进行深入研究后,充分认识到经典的B resenha m 算法基本思想的重要性,又考虑到B resenha m 算法本身的缺陷,提出了一种改进算 法,克服了上述直线生成算法的弱点。新算法既保持B resenha m 算法只需要使用整数加法和乘法运算,不需要进行小数和取整运算的优点,又可以通过一次计算生成两个像素行,因此执行效率明显高于其它直线生成算法,并且算法实现简单、运算量少。 1 算法原理 本文的算法和程序只对斜率在[0,1]之间的直线进行讨论,并设直线的起点为(x 0,y 0),终点为(x 1,y 1),且x 1≥x 0、y 1≥y 0,对于一般的情况可以利用变换求得。下面首先提出并证明两个结论,再在这两个结论的基础上介绍改进算法。 结论1 用B resenham 算法生成的直线在除起始和终止两像素行外,其它各像素行点亮的像素点个数m 满足: Q ≤m ≤Q +1 式中Q =[dx /dy ](“/”表示除法、“[]”表示下取整)、dx =x 1-x 0、dy =y 1-y 0。 例如一条从(0,0)到(45,10)的线段,其Q =[dx /dy ]=4,则该直线除起始和终止两像素行外,其它各像素行点亮的个数为4或5个。 证明:B resenham 算法利用当前被选中的像素来选择下一个像素点,如图1,P 点已被选中,则直线的下一个像素点应该 实验二基本图元的生成算法 一、实验目的 1、初步了解显示窗口与视区的关系 2、掌握OpengGL点、直线、多边形的绘制 3、掌握DDA直线生成算法。 4、掌握Bresenham直线生成算法 二、实验环境 硬件要求： PC机，主流配置，最好为独立显卡，显存512M以上。 软件环境： 操作系统：Windows XP。 语言开发工具：VC6.0。 三、实验内容与要求 1、调出实验一的源代码运行，调整修改使得显示窗口大小改变时，绘制的矩形大小随之改变。如图2-1所示。 提示：(1)在main函数里添加注册窗口变化函数 glutReshapeFunc(myreshape); （放在glutMainLoop()之前） (2)在程序中添加窗口改变子函数，参数w,h为当前显示窗口的宽和高 void myreshape(GLsizei w, GLsizei h) { glViewport(0,0,w,h); //设置视区位置 glMatrixMode(GL_PROJECTION);//设置投影变换模式 glLoadIdentity(); //调单位矩阵，清空当前矩阵堆栈 if(w<=h) gluOrtho2D(0,300,0,300*(GLfloat)h/(GLfloat)w); //设置裁剪窗口大小 else gluOrtho2D(0,300*(GLfloat)w/(GLfloat)h,0,300); } a) 显示窗口改变前 b)显示窗口变大后 图2-1 未修改前的初始源程序参考如下： /*my first program.cpp*/ #include 实验一直线生成算法 一、实验目的及要求： 1．学习C语言的基本绘图方法； 2. 实习直线基本生成算法； 3．了解光栅图形显示器的工作原理和特点； 4．掌握课本所介绍的图形算法的原理和实现。 5. 基于光栅图形显示器，在c环境中使用基本图形生成算法画根粗细不同的直线。 1.）写出完整的DDA画线算法程序，使其可以画任意直线； 2.）写出完整的中点画线算法程序，使其可以画任意直线； 3．）写出完整的Breaenham画线程序，使其可以画任意直线； 二、理论基础： 1、DDA算法：实现的关键是如何步进和步进的方向：步进的正或负，决定能否正确的到达终点。步进的大小：它控制了变化最大的步进，令其为单位步进，而另一个方向的步进必小于1 ，这样不论斜率|m|≤1否，都会使直线的亮度均匀。 依公式：则下一点坐标为： 2、中点画法：假设x坐标为xp的各像素点中，与直线最近者已确定，为（xp,yp)。那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)或右上方的P2（xp+1,yp+1)两者之一。再以M表示P1与P2的中点，即M=（xp+1,yp+0.5)。又设Q是理想直线与垂直线x=xp+1的交点。若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1。 3、Bresenham算法：假设我们需要由 (x0, y0) 这一点，绘画一直线至右下角的另一点(x1, y1)，x,y分别代表其水平及垂直座标。在此我们使用电脑系统常用的座标系，即x座标值沿x轴向右增长，y座标值沿y轴向下增长。因此x及y之值分别向右及向下增加，而两点之水平距离为x1 ? x0且垂直距离为y1-y0。由此得之，该线的斜率必定介乎于1至0之间。而此算法之目的，就是找出在x0与x1之间，第x行相对应的第y列，从而得出一像素点，使得该像素点的位置最接近原本的线。 三、算法设计与分析： 1、DDA算法： (1)已知过端点P0 (x0, y0), P1(x1, y1)的直线段L ：y=kx+b (2)直线斜率为 :k=(y1-y0)/(x1-x0) (3)Xi+1=Xi+ε*ΔX Yi+1=Yi+ε*ΔY 其中， ε=1/max(|ΔX|,|ΔY|) max(|ΔX|,|ΔY|)= |ΔX| (|k|<=1) |ΔY| (|k|>1) (4)|k|<=1时：Xi+1=Xi+(或-)1 Yi+1=Yi+(或-)kDDA直线生成算法
Bresenham的直线生成算法和整圆生成算法完整代码
计算机图形学 直线的生成算法的实现
(1)直线生成算法.doc
OpenGL-实验2直线生成算法实现教学文案
直线和圆弧的生成算法
CG_实验2_基本图形元素(直线)生成算法的实现
直线生成算法的实现
直线生成算法——Bresenham法
直线的Bresenham算法
计算机图形学 直线段生成绘制的实现算法
基于自适应步长的直线生成算法
改进的Bresenham直线生成算法
实验二_基本图元生成算法
计算机图形学 实验一直线生成算法报告
- DDA直线算法生成
- 计算机图形学直线生成算法
- 计算机图形学圆的的生成算法的实现
- 直线生成算法 DDA画线算法、中点画线算法、Bresenham画线算法
- 直线和圆弧的生成算法
- 计算机图形学 直线段生成绘制的实现算法
- 计算机图形学-直线生成算法实验报告
- (1)直线生成算法.doc
- 直线生成算法——Bresenham法
- 直线和圆弧的生成算法
- 图形学实验报告一 直线生成算法
- CG_实验2_基本图形元素(直线)生成算法的实现
- 直线的Bresenham算法
- 直线生成算法的实现
- 计算机图形学 直线的生成算法的实现
- 计算机图形学直线生成
- 改进的Bresenham直线生成算法
- OpenGL-实验2直线生成算法实现教学文案
- OpenGL-实验2直线生成算法实现教学文案
- 直线生成算法