直线和圆的生成算法.ppt

第四章二维图形的生成技术谢忠红南京农业大学复杂图形直线曲线都是点的集合4.1基本图元素-点•三维图形由曲面、平面组成二维图形曲线直线转化点图形点是图形中最基本的图素，直线、曲线以及其它图元都是点的集合。函数作用：使屏幕上坐标(x,y)的点辉亮P(x,y)putpixel(x,y,color)光栅显示器像素间为均匀网格•Putpixel(5,7,RED)直线是点的集合，（几何学定义：直线被定义为两个点之间的最小距离）图形学的直线：（1）图形显示器是由一个个排列有序的象素点构成的，象素之间为均匀的网格（2）点的坐标是指点所在象素点的位置，而象素点的位置是整型的，画一条直线实际上是依据一系列计算出来的位置得到靠近该位置的象素点。对于光栅显示器来说:1、像素间为均匀网格2、整型坐标系(10.48,20.51)(10,21)AB后果：对坐标取整使得显示的线段具有锯齿现象改进的方法：提高屏幕的分辨率800*6001024*10244.2直线段的生成（x0,y0）(x´,y´)1.数值微分法(DDA)基本思想:确定最佳逼近该直线的一组象素，并按扫描线的顺序显示这组象素点.条件：待连线的两点：直线斜率为00''xxyykP0(x0,y0)，P´(x´,y´)p0P’K=y/xy=kxx1=x0+x,x2=x1+x，…,xi=xi-1+xy1=y0+kx,y2=y1+kx，…，yi=yi-1+kx(x0,y0)设：x=1xi=xi-1+xyi=yi-1+kxxi=xi-1+1yi=yi-1+k(k=1)点的坐标：(xi,round(yi))•即：当x每递增1，y递增k(即直线斜率)；iXi=xi-1+1yi=yi-1+kround(yi)坐标000round(0)=0(0,0)110+0.4=0.4round(0.4)=0(1,0)220.4+0.4=0.8round(0.8)=1(2,1)330.8+0.4=1.2round(1.2)=1(3,1)441.2+0.4=1.6round(1.6)=2(4,2)551.6+0.4=2.0round(2.0)=2(5,2)例：用DDA算法画直线段P0(0,0)--P1(5,2)k=(2-0)/(5-0)=0.4012345321Line:P0(0,0)--P1(5,2)012345321Line:P0(0,0)--P1(5,2)该方法能画出所有直线吗？分析：上述分析的算法仅适用于k≤1的情形。原因：当|k|=1时，x每增加1(x=1),y最多增加1(|y|=|k|x≤1)。如果，当k1时，x每增加1，y可能会增加大于1的数(|y|=|k|x1)，这时象素点会稀疏，所画直线会断断续续。012345321Line:P0(0,0)--P1(5,2)xi=xi-1+1yi=yi-1+k(k1)K1时使用如下公式的效果图K1时怎么办？已知直线y=kx+b|k|1K=y/xyx即：yi=yi-1+1xi=xi-1+1/k令y=1x=y*1/k(round(xi),yi)例：画出p0(0,0)和p´(2,6)之间的一条直线。K=(6-0)/(2-0)=31采用通过yi的变化确定xi的变化即：y=1x=1/k1/k=1/3=0.33•iyi=yi-1+1xi=xi-1+1/kround(xi)坐标000round(0)=0(0,0)110+0.33=0.33round(0.33)=0(0,1)220.33+0.33=0.66round(0.66)=1(1,2)330.66+0.33=0.99round(0.99)=1(1,3)440.99+0.33=1.32round(1.32)=1(1,4)551.32+0.33=1.65round(1.65)=2(2,5)661.65+0.33=1.98round(1.98)=2(2,6)Line(0,0,2,6)读入直线的起点(x0,y0)和终点(x’,y’)x0x’x0与x´互换y0与y´互换计算xi=xi-1+1yi=yi-1+k输出（xi,round(yi)）y0y’y0与y´互换x0与x´互换计算yi=yi-1+1xi=xi-1+1/k输出(round(xi),yi）k=1?开始结束YN数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。DDA圆的生成算法如何使用计算机生成一个圆或圆弧呢？角度DDA法生成圆原理：把圆或者圆弧分成N等分。用N段相邻的直线来逼近圆弧或圆。x=x0+Rcosy=y0+Rsin圆心在（x0,y0）半径为R圆的参数方程若将整个圆分成N等分，θ=2π/N,则有参数式递推公式：其中i=i*θi=0,1,2,3,…N-1最后将相邻的（xi,yi）（xi+1,yi+1）用直线段一一相连就可近似地画出圆了。Xi=x0+RcosiYi=y0+Rsinii=0i=1i=2i=N-1N=12例：圆心(x0,y0)=(50,50)R=100N=6θ=2π/6=π/3(50,50)x0=50+100cos(0*π/3)y0=50+100sin(0*π/3)x1=50+100cos(1*π/3)y1=50+100sin(1*π/3)x2=50+100cos(2*π/3)y2=50+100sin(2*π/3)x3=50+100cos(3*π/3)y3=50+100sin(3*π/3)x4=50+100cos(4*π/3)y4=50+100sin(4*π/3)x5=50+100cos(5*π/3)y5=50+100sin(5*π/3)x6=50+100cos(6*π/3)y6=50+100sin(6*π/3)[PDDA_circle]请写出DDA画圆算法！voidDDA_circle(intn,intx0,inty0,intradius)//把圆分成n等分，(x0,y0)为圆心坐标,radius为圆的半径{inti;intx_start,y_start;//线段的起点坐标Intx_end,y_end;//线段的中点坐标for(i=0;in;i++)//循环地算初起点和终点坐标并连接这两点{x_start=x0+radius*cos(i*2*3.14/n);y_start=y0+radius*sin(i*2*3.14/n);x_end=x0+radius*cos((i+1)*2*3.14/n);y_end=y0+radius*sin((i+1)*2*3.14/n);my_line(x_start,y_start,x_end,y_end);}}还能改进吗？？voidDDA_circle(intn,intx0,inty0,intradius)//把圆分成n等分，(x0,y0)为圆心坐标,radius为圆的半径{inti;Intx_end,y_end;//线段的中点坐标my_Moveto(x0+radius,y0)for(i=1;i=n;i++)//循环地算终点坐标并连接这两点{x_end=x0+radius*cos(i*2*3.14/n);y_end=y0+radius*sin(i*2*3.14/n);my_lineto(x_end,y_end);}}直线Bresenham算法特点：-使用最广泛-由误差项符号决定下一个象素取正右方像素还是右上方像素优点整数运算，速度快精度高基本思想以K=1为例根据理想直线到位于直线下方的像素的距离d,确定与理想直线最近的象素P2P1d0.5d0.5X方向：每次走一步xi+1=xi+1y方向：走步与否取决于误差e值的大小如果e≥0.5时，最接近P2(xi+1,yi+1)y方向走一步如果e0.5时，最接近P1(xi+1,yi)y方向不走步e误差e计算从第一点开始：e=y/x为方便与0比较，设es=e-0.5s=y/x-0.5当s≥0时，最接近P2(xi+1,yi+1)y方向走一步当s0时，最接近P1(xi+1,yi)y方向不走步缺点：有除法，不宜硬件实现改进简化s与0的比较，拿分母与0比较s=y/x-0.5=(2y-x)/(2x)与0比较大小当t0≥0时，最接近P2(xi+1,yi+1)y方向走一步当t00时，最接近P1(xi+1,yi)y方向不走步下一个点如何判断呢？设t0=2y-x上一步误差计算下一步误差的计算当t0=0时，y方向走一步同样为了方便与0比较e’-0.5=2y/x-1-0.5=/(2x)e=y/xe’=2e-1=2y/x-1设t0=2y-x=0(2y-x+2y-2x)令分母为t1=t0+2y-2x当t00时，y方向不走步同样为了方便与0比较e’-0.5=2y/x-0.5e’=2y/x=(2y-x+2y)/(2x)令分母为t1=t0++2y设t0=2y-x0综上x=1y=kt0=2y-x=2K-1当ti≥0时，y方向走一步ti+1=ti++2y-2x=ti+2k-2当ti0时，y方向不走步ti+1=ti+2y=ti+2k例：利用Bresenham算法画出p0(0,0)和p´(6,2)之间的一条直线。解答K=(2-0)/(6-0)=1/3=1p0(0,0)•起点(0,0)ti坐标t0=2k-1=-1/30(1,0)∵t00∴t1=t0+2k=1/30(2,1)∵t10∴t2=t1+2k-2=-10(3,1)∵t20∴t3=t2+2k=-1/30(4,1)∵t30∴t4=t3+2k=1/30(5,2)∵t40∴t5=t4+2k-2=-10(6,2)t0=2k-1当ti≥0时ti+1=ti+2k-2当ti0时ti+1=ti+2k