《第3章基本图形的生成课件》由会员分享，可在线阅读，更多相关《第3章基本图形的生成课件（43页珍藏版）》请在金锄头文库上搜索。
1、第3章 基本图形生成原理,一 光栅扫描： 1 光栅扫描的基本原理： 电子束在荧光屏上按照固定的扫描线和扫描顺序扫出 一个由行和列组成的光的栅网。 2 像素： 栅网中的每一个孤立的光点，它是光栅显示的最小单位。 像素可以有不同的亮度,像素的坐标值都是整数。,概论,3 提出问题,(1)目前使用的图形输出设备显示器：光栅图形显示器 (2)光栅图形显示器: 以光栅扫描方式刷新线段、字符和图形。 其本质: 是一种画点设备，是由一定数量的网格状细小光点 （像素）组成，使其某些像素亮，某些像素不亮来显 示图形或文字. (3)问题： 光栅图形显示器是画点设备，而二维图形并不是点的集合， 如何在光栅图形显示器上
2、构造基本二维几何图形(线 圆)？ (4)解决方法： 进行图形扫描转换 例： 要在屏幕上显示一条直线时，只能确定出逼近直线的 一组像素， 并按扫描线顺序对这些像素进行写操作，即进行扫描转换。 结果: 使所画的直线转换成为逼近理想直线的由无数个点构成的集合 。 画图形：可使用同样的方法，即进行图形的扫描转换. 使所画的图形转换成为逼近理想图形的由 无数个点构成的集合 。,扫描转换（光栅化）： 1 什么叫扫描转换（光栅化）？ 在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程 。 2 扫描转换的主要工作： 由于理想的图形是连续的，而光栅图像是离散的，因此显示过程中不可 避免地产生锯齿等畸变
3、， 扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算法。,3 学习扫描转换的目的： (1) 绘图函数具有局限性： 在实际工作中遇到画线的工作时，可以方便地调用程序设计 语言中提供的绘图函数，不需要自己编写画线的程序。 但它由局限性，不能满足用户特殊绘图要求，需要开发出满 足需求的绘图程序。 (2) 学习目的： 掌握将数学的、模拟的、线形的图形变成数字的离散的图形 的过程中的设计思想和方法，这些思想能够在科学研究和产 品开发中发挥作用。,5.1 直线的生成,三 算法要求： 1 准确：扫描点尽可能地逼近理想点。 2 快速：改进算法尽 快提高扫描转换速度。,一 问题的提出： 给定直线两端点P0
4、(x0,y0)和P1(x1,y1)， 在光栅显示器上画出该直线。 二 需要进行扫描转换： 给出一个将直线转换为逼近理想直线的点的集合的算法。,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 直线的微分方程：,一 数值微分法：是一种基于直线微分方程来生成直线的方法。,二 数
5、值微分法的改进算法（关键：找到Pi(Xi,Yi), Pi+1(Xi+1,Yi+1)的关系）,1 推导： 直线方程：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
6、+1 yi+1=round ( yi+k) /进行取整运算,分析：下一点的y坐标为当前点y 坐标加上斜率k,省略了浮点乘法。,xi+1=xi+1 yi+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=x
7、1-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),color);/画点，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）或
8、P2（xp+1,yp+1). 4 Q点是直线与垂直线x=xp+1的交点。M（xp+1，yp+0.5）为 P1与P2的中点。 若直线上的点Q在M的下方，说明直线离P1近，则应取P1为下一点。 若直线上的点Q在M的上方，说明直线离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的
9、上方 （M在直线的下方）则：取P2作为下一个象素，,对每一个象素计算判别式d，根据它的符号判定下一个象素。 d是xp，yp的线形函数，可以采用增量计算来提高运算效率。,根据不同情况分析如下： 第一种情况：当dk 0时，取正右方的象素p1，下一步则应在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的增
10、量为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)+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
11、+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)+c 2）根据M1选择P3与P4之一： dk+1= dk+a 3）根据M2选择P4与P5之一： dk+1 = dk+a+b 4) d 的初始值为： d0=a+0.5b,三 进一步改进算法： 注意到初始值中有浮点运算，消除浮点可以进一步改进算法。 考察判别式dk，判别使用的仅仅是dk的符号，且dk的增量都是整数， 故用2dk
12、来代替dk，摆脱小数（浮点），从而提高速度。,学习目标： 1 理解该算法的来龙去脉（上述结果是怎么得来的）。 2 能够用上述结果解题，编程实现该算法。,四 总结中点画线算法： 1 基本思想：通过判断dk的值来确定下一个该点亮的像素 2 思路： (1)先求d0的值(利用中点M求）：d0=2a+b (2)再找到dk+1与dk的关系： dk+1= dk+2a （dk0）此时取正右方像素 dk+2a+2b （dk0 ）此时取右上方像素,五 利用推导结果编程实现中点画线算法： void MidpointLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int
13、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; else x+;d+=delta1; putpixel(x,y,color); /while /MidpointLine,课后作业题： 用中点画线算法扫描转换从像素点(1,1)到(8,
14、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,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。,改进1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k。 if (e0) t
15、hen 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来替换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
