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

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

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

2、3)问题：问题：光栅图形显示器是画点设备，而二维图形并不是点的集合，如何在光栅图形显示器上构造基本二维几何图形(线 圆)？(4)解决方法：解决方法：进行图形扫描转换进行图形扫描转换 例：要在屏幕上显示一条直线时，只能确定出逼近直线的 一组像素，并按扫描线顺序对这些像素进行写操作，即进行扫描转换。结果:使所画的直线转换成为逼近理想直线的由无数个点构成的集合。画图形：可使用同样的方法，即进行图形的扫描转换.使所画的图形转换成为逼近理想图形的由 无数个点构成的集合。2扫描转换（光栅化）：扫描转换（光栅化）：1 什么叫扫描转换（光栅化）？什么叫扫描转换（光栅化）？在光栅显示器等数字设备上确定一个最佳逼

3、近于图形的象素集的过程。2 扫描转换的主要工作：扫描转换的主要工作：由于理想的图形是连续的，而光栅图像是离散的，因此显示过程中不可 避免地产生锯齿等畸变，扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算法。研究使光栅图像逼近原始的图形的算法。用一系列的象素点来逼近直线 3 学习扫描转换的目的：学习扫描转换的目的：(1)绘图函数具有局限性：在实际工作中遇到画线的工作时，可以方便地调用程序设计 语言中提供的绘图函数，不需要自己编写画线的程序。但它由局限性，不能满足用户特殊绘图要求，需要开发出满 足需求的绘图程序。(2)学习目的：掌握将数学的、模拟的、线形的图形变成数字的离散的图形 的过程中的

4、设计思想和方法，这些思想能够在科学研究和产 品开发中发挥作用。5.1 直线的生成直线的生成三三 算法要求：算法要求：1 准确：扫描点尽可能地逼近理想点。2 快速：改进算法尽 快提高扫描转换速度。一一 问题的提出：问题的提出：给定直线两端点P0(x0,y0)和P1(x1,y1)，在光栅显示器上画出该直线。二二 需要进行扫描转换：需要进行扫描转换：给出一个将直线转换为逼近理想直线的点的集合的算法。2 2 直线的斜截式方程：直线的斜截式方程：y=kx+b by1kx1 x从起点到终点每次增加1，用y=kx+b计算y值，再用putpixel(x,int(y+0.5)int(y+0.5),color)输

5、出该像素。3 该算法的缺点：该算法的缺点：画线效率低，每步都需要一个浮点乘法运算和一个 四舍五入运算，需要加以改进。5.2.数值微分法数值微分法(DDA算法算法 Digital Differential Analyzer)kxxyyxydxdy0101 1 直线的微分方程直线的微分方程：一一 数值微分法：是一种基于直线微分方程来生成直线的方法。数值微分法：是一种基于直线微分方程来生成直线的方法。二二 数值微分法的改进算法数值微分法的改进算法（关键：找到（关键：找到Pi(Xi,Yi),Pi+1(Xi+1,Yi+1)的关系）的关系）1 推导：推导：直线方程：y=kx+b 直线上的第i、第i+1个点

6、为：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,省略了浮点乘法。省略了浮点

7、乘法。xi+1=xi+1 yi+1=round(yi+k)(xi,yi)(xi+1,(int)(yi+k)(xi,(int)(yi)(xi+1,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

8、;dy=y1-y0;k=dy/dx;/计算斜率 y=y0;/设定第1点的y值 for(x=x0;x0 直线下方的点：F(x,y)0 Q在M的下方（M在直线的上方）则：取P1作为下一个象素，dk=dk=0 Q在M的上 （M在直线的上 ）则：同上 dk 0 Q在M的上方（M在直线的下方）则：取P2作为下一个象素，对每一个象素计算判别式d，根据它的符号判定下一个象素。d是xp，yp的线形函数，可以采用增量计算来提高运算效率。Q P1 P2 M P3 P4 P5 M1 M2 P 根据不同情况分析如下：第一种情况：当dk 0时，取正右方的象素p1，下一步则应在p3和p4当中选择，设它们的中点为M1（xp

9、+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。ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 第二种情况：当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+2

10、a+b(yp+1.5)+c =a(xp+1)+a+b(yp+0.5)+c+b =dk+a+b 下一步的判别式为：dk+1=dk+a+b d的增量为a+b。ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 初始值，第一个象素为起点（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 ax+by+c=0 Q P1 P

11、2 M P3 P4 P5 M1 M2 P 小结：1）根据M选择P1与P2之一：dk=a(xp+1)+b(yp+0.5)+c2）根据M1选择P3与P4之一：dk+1=dk+a3）根据M2选择P4与P5之一：dk+1=dk+a+b4)d 的初始值为：d0=a+0.5b ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 三三 进一步改进算法：进一步改进算法：注意到初始值中有浮点运算，消除浮点可以进一步改进算法。考察判别式dk，判别使用的仅仅是dk的符号，且dk的增量都是整数，故用2dk来代替dk，摆脱小数（浮点），从而提高速度。改进结果：改进结果：(中点画线法的精髓）中点画线

12、法的精髓）d0=2a+b (a=y0-y1,b=x1-x0)dk+1=dk+2a （dk0）此时取正右方像素）此时取正右方像素 dk+2a+2b （dk0）此时取右上方像素此时取右上方像素 ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 学习目标：学习目标：1 理解该算法的来龙去脉（上述结果是怎么得来的）。理解该算法的来龙去脉（上述结果是怎么得来的）。2 能够用上述结果解题，编程实现该算法。能够用上述结果解题，编程实现该算法。四四 总结中点画线算法：总结中点画线算法：1 基本思想：通过判断dk的值来确定下一个该点亮的像素 2 思路：(1)先求d0的值(利用中点M求）：

13、d0=2a+b (2)再找到dk+1与dk的关系：dk+1=dk+2a （dk0）此时取正右方像素）此时取正右方像素 dk+2a+2b （dk0）此时取右上方像素）此时取右上方像素 ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 五五 利用推导结果编程实现中点画线算法：利用推导结果编程实现中点画线算法：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=

14、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.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进改进1：令e=d-0.50)(e 0)(e 1111iiiiiyyyxx e初=-0.5，每走一步有e=e+k。if(e0)then e=e-1算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初

15、始值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来替换e e初=-x，每走一步有e=e+2y。if(e0)then e=e-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更新

16、为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(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 点M在圆的外边,圆离P2点近,取P2 F(M)=0 点M在圆的上边,取P2 F(M)0 点M在圆的里边,圆离P1点近,取P1 问题：下一次取