第3章基本图形的生成.ppt

《第3章基本图形的生成.ppt》由会员分享，可在线阅读，更多相关《第3章基本图形的生成.ppt（43页珍藏版）》请在课桌文档上搜索。

1、第3章 基本图形生成原理,一 光栅扫描：1 光栅扫描的基本原理：电子束在荧光屏上按照固定的扫描线和扫描顺序扫出 一个由行和列组成的光的栅网。2 像素：栅网中的每一个孤立的光点，它是光栅显示的最小单位。像素可以有不同的亮度,像素的坐标值都是整数。,概论,3 提出问题,(1)目前使用的图形输出设备显示器：光栅图形显示器(2)光栅图形显示器:以光栅扫描方式刷新线段、字符和图形。其本质:是一种画点设备，是由一定数量的网格状细小光点（像素）组成，使其某些像素亮，某些像素不亮来显 示图形或文字.(3)问题：光栅图形显示器是画点设备，而二维图形并不是点的集合，如何在光栅图形显示器上构造基本二维几何图形(线

2、圆)？(4)解决方法：进行图形扫描转换 例：要在屏幕上显示一条直线时，只能确定出逼近直线的 一组像素，并按扫描线顺序对这些像素进行写操作，即进行扫描转换。结果:使所画的直线转换成为逼近理想直线的由无数个点构成的集合。画图形：可使用同样的方法，即进行图形的扫描转换.使所画的图形转换成为逼近理想图形的由 无数个点构成的集合。,扫描转换（光栅化）：1 什么叫扫描转换（光栅化）？在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。2 扫描转换的主要工作：由于理想的图形是连续的，而光栅图像是离散的，因此显示过程中不可 避免地产生锯齿等畸变，扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算

3、法。,3 学习扫描转换的目的：(1)绘图函数具有局限性：在实际工作中遇到画线的工作时，可以方便地调用程序设计 语言中提供的绘图函数，不需要自己编写画线的程序。但它由局限性，不能满足用户特殊绘图要求，需要开发出满 足需求的绘图程序。(2)学习目的：掌握将数学的、模拟的、线形的图形变成数字的离散的图形 的过程中的设计思想和方法，这些思想能够在科学研究和产 品开发中发挥作用。,5.1 直线的生成,三 算法要求：1 准确：扫描点尽可能地逼近理想点。2 快速：改进算法尽 快提高扫描转换速度。,一 问题的提出：给定直线两端点P0(x0,y0)和P1(x1,y1)，在光栅显示器上画出该直线。二 需要进行扫描

4、转换：给出一个将直线转换为逼近理想直线的点的集合的算法。,2 直线的斜截式方程：y=kx+b by1kx1 x从起点到终点每次增加1，用y=kx+b计算y值，再用putpixel(x,int(y+0.5),color)输出该像素。3 该算法的缺点：画线效率低，每步都需要一个浮点乘法运算和一个 四舍五入运算，需要加以改进。,5.2.数值微分法(DDA算法 Digital Differential Analyzer),1 直线的微分方程：,一 数值微分法：是一种基于直线微分方程来生成直线的方法。,二 数值微分法的改进算法（关键：找到Pi(Xi,Yi),Pi+1(Xi+1,Yi+1)的关系）,1 推

5、导：直线方程：y=kx+b 直线上的第i、第i+1个点为：Pi(Xi,Yi),Pi+1(Xi+1,Yi+1),计算Pi+1 时：x为xi+1,（在第1象限x 总是向右前进一步），y为 y（画水平线时，y的值不变）yi+1（画非水平线时，y的值变化，需要计算）其中：yi+1的计算为：yi+1=kxi+1+B=k(xi+x)+B=kxi+kx+B=kxi+B+kx/yi=kxi+B=yi+kx=yi+k/当x的步进为1时 故Pi+1点的坐标为：xi+1=xi+1 yi+1=round(yi+k)/进行取整运算,分析：下一点的y坐标为当前点y 坐标加上斜率k,省略了浮点乘法。,xi+1=xi+1 y

6、i+1=round(yi+k),数值微分法示意图,2 算法：1)计算斜率 k=y/x 2)画第1个点(x0,y0)3)计算下一个点（x，y）的值P，x=x+1,y=y+k 小数部分0.5,则 y=y+1 循环 小数部分 0.5,则 y=y 画点（x，y）,void ddaline(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int x;float dx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx;/计算斜率 y=y0;/设定第1点的y值 for(x=x0;x=x1;x+)/x 加1 putpixel(x,(int)(y+0.5),col

7、or);/画点，y值取整 y=y+k;/计算y的值,3 程序：,4 分析：本算法中k值需要使用浮点，每一步都要进行取整运算，不利于硬件实现。可以用中点画线法解决。,3.2.2 中点画线法：,1 有直线F(x,y)=ax+by+c=0，假定其斜率在0，1之间.2 直线在x方向增加一个单位，则在y方向上的增量只能在0与1之间。3 当前点为P（xp，yp）,下一点有两种选择:P1（xp+1,yp）或P2（xp+1,yp+1).4 Q点是直线与垂直线x=xp+1的交点。M（xp+1，yp+0.5）为 P1与P2的中点。若直线上的点Q在M的下方，说明直线离P1近，则应取P1为下一点。若直线上的点Q在M的

8、上方，说明直线离P2近，则应取P2为下一点，问题：如何判断Q在M的什么位置?,一 原理:,二 判别式推导：1 直线方程：F(x,y)=ax+by+c=0 直线上的点：F(x,y)=0 直线上方的点：F(x,y)0 直线下方的点：F(x,y)0 Q在M的下方（M在直线的上方）则：取P1作为下一个象素，dk=dk=0 Q在M的上（M在直线的上）则：同上 dk 0 Q在M的上方（M在直线的下方）则：取P2作为下一个象素，,对每一个象素计算判别式d，根据它的符号判定下一个象素。d是xp，yp的线形函数，可以采用增量计算来提高运算效率。,根据不同情况分析如下：第一种情况：当dk 0时，取正右方的象素p1

9、，下一步则应在p3和p4当中选择，设它们的中点为M1（xp+2，yp+0.5）,则判断式d1为：dk+1=F(M1)=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a xp+2a+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=dk+a下一步的判别式为：dk+1=dk+1+a d的增量为a。,第二种情况：当d0时，取正上方的象素p2，下一步则应在p4和p5当中选择，设它们的中点为M2（xp+2，yp+1.5）,则判断式d2为：dk+1=F(M2)=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a xp+2a+b(yp+1.5)

10、+c=a(xp+1)+a+b(yp+0.5)+c+b=dk+a+b 下一步的判别式为：dk+1=dk+a+b d的增量为a+b。,初始值，第一个象素为起点（x0，y0），相应的判别式值为M0，由于起点（x0，y0）在直线上，故F（x0，y0）=0。推导：d0=F(M0)=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=a x0+by0+c+a+0.5b=F(x0，y0)+a+0.5b/起点必在直线上，F(x0，y0)=0=a+0.5b,小结：1）根据M选择P1与P2之一：dk=a(xp+1)+b(yp+0.5)+c2）根据M1选择P3与P4之一：dk+1=dk+a3）根据

11、M2选择P4与P5之一：dk+1=dk+a+b4)d 的初始值为：d0=a+0.5b,三 进一步改进算法：注意到初始值中有浮点运算，消除浮点可以进一步改进算法。考察判别式dk，判别使用的仅仅是dk的符号，且dk的增量都是整数，故用2dk来代替dk，摆脱小数（浮点），从而提高速度。,学习目标：1 理解该算法的来龙去脉（上述结果是怎么得来的）。2 能够用上述结果解题，编程实现该算法。,四 总结中点画线算法：1 基本思想：通过判断dk的值来确定下一个该点亮的像素 2 思路：(1)先求d0的值(利用中点M求）：d0=2a+b(2)再找到dk+1与dk的关系：dk+1=dk+2a（dk0）此时取正右方像

12、素 dk+2a+2b（dk0）此时取右上方像素,五 利用推导结果编程实现中点画线算法：void MidpointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int a,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;/d为d0，d=a+0.5b，2d=2a+b，D=2a+b,D=a+a+b delta1=2*a;/delta1为d1 delta2=2*(a+b);/delta2为d2 x=x0;y=y0;putpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=delta2

13、;else x+;d+=delta1;putpixel(x,y,color);/while/MidpointLine,课后作业题：用中点画线算法扫描转换从像素点(1,1)到(8,5)线段的 像素位置,3 改进的Bresenham算法,假定直线段的0k1基本原理：,误差项的计算d初=0，每走一步：d=d+k 一旦y方向上走了一步，d=d-1,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,

14、y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,改进1：令e=d-0.5,e初=-0.5，每走一步有e=e+k。if(e0)then e=e-1,算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,改进2：用2ex来替换ee初=-x，每走一步有e=e+2y。if(e0)then e=e

15、-2x,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,三 利用推导结果编程实现bresenham算法：,void bresenhamline(int x0,int y0,int x1,int y1)int x,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;while(

16、x0)y=y+1;e=e-2*dx;,五 中点画线算法与bresenham算法的比较：相似处：1 求出d0的值2 再找到dk+1与dk的关系.3 利用dk的值判断下一个该点亮的像素：不同点：1 求d0时：中点画线法：利用中点M坐标来求，d02ab bresenham法：利用始点终点来求，d02 y-x2 利用dk的值取像素时：bresenham法：dk0 时取右上方像素 dk0 时取右方像素 中点法正相反：dk0 时取右方像素 dk0 时取右上方像素,课后作业题：用bresenham算法扫描转换从像素点(1,1)到(8,5)线段的 像素位置。,3.3 圆的生成3.3.1 八分法画圆算法,思路：

17、（考虑到圆的对称性）画出A点则剩下的7个点都能画出，画出B点则剩下的7个点都能画出，因此，只讨论8分圆的画法即可,二 算法原理：利用其函数方程，直接离散计算,圆的函数方程为：,缺点：计算量过大,三 圆的极坐标方程为：,可先通过平移变换，把计算所得的像素(x1,y1)坐标加上 一个位移量(delta_x和delta_y)即得所求像素坐标(x2,y2)。即：x2=x1+delta_x y2=y1+delta_y,四 中点不在原点的圆：,3.3.2 中点画圆算法（关键：找到d的增量）,一 基本思路：利用中点M来选择下一个要显示的像素。二 分析：M的坐标是（x+1,y-0.5）F(M)0 点M在圆的外

18、边,圆离P2点近,取P2 F(M)=0 点M在圆的上边,取P2 F(M)0 点M在圆的里边,圆离P1点近,取P1 问题：下一次取P3？P4？P5？,1 构造判别式：,若d0 点M在圆的里边，圆离P1点近,则应取P1 下一个中点M2的判别式为：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3 即求出d的增量为：2xp+3 若d0 点M在圆的外边,圆离P2点近,则应取P2 下一个中点M3的判别式为：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5 即求出d的增量为：2(xp-yp)+5总结求得的d的增量：

19、2xp+3 d0 2(xp-yp)+5 d0,2 求d的增量：（目的：判断下一个该显示的像素）,解决方法：,p,3 求d的初始值d0：起始点（即第一个像素)为（0,R）,判别式d的初始值为：d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R4 推导出的结果:d01.25-R d+2xp+3 d0 d+2(xp-yp)+5 d0,d=,5 可以利用推导出的结果，编写程序。,三 算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为

20、(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。,改进：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。,四 源程序：,void MidpointCircle(r,color)int r,color;int x

21、,y,d;x=0;y=r;d=1-r;wholecircle(x,y,color);,while(x y)if(d 0)d+=2*x+3;x+;else d+=2*(x-y)+5;x+;y-;wholecircle(x,y,color);,void WholeCircle(xc,yc,x,y.color)int xc,yc,x,y,color;putpixel(xc+x,yc+y,color);putpixel(xc-x,yc+y,color);putpixel(xc+x,yc-y,color);putpixel(xc-x,yc-y,color);putpixel(xc+y,yc+x,colo

22、r);putpixel(xc-y,yc+x,color);putpixel(xc+y,yc-x,color);putpixel(xc-y,yc-x,color);,圆的半径为r，圆心在原点，顺时针方向画1/8圆的过程。X每次增加1个步长。,y则有两种可能,或,选择的原则是，y更靠近yi，还是更靠近yi-1,令,3、Bresenham画圆算法,令,pi0 下个像素点yi+1=yi 否则 yi+1=yi-1,结论：,1、求误差初值，p0=3-2r,画点（0，r）,2、求下一个点坐标。xi+1=xi+1,如果pi0,则yi+1=yi，pi+1=pi+4xi+6。否则yi+1=yi-1，pi+1=pi+4(xi-yi),3、i=i+1，重复2。,