《课件 计算机图形学 基本图形生成》由会员分享，可在线阅读，更多相关《课件 计算机图形学 基本图形生成（65页珍藏版）》请在金锄头文库上搜索。
1、第三章 基本图形生成原理3.1 概论 3.2 直线的生成3.2.1 数值微分法3.2.2 中点画线法3.2.3 Bresenham画线算法 3.3 圆的生成3.3.1 八分法画圆算法3.3.2 中点画圆算法 3.4 区域填充3.4.1 种子填充算法3.4.2 扫描线填充算法一 光栅扫描：1 光栅扫描的基本原理：电子束在荧光屏上按照固定的扫描线和扫描顺序扫出一个由行和列组成的光的栅网。2 像素：栅网中的每一个孤立的光点，它是光栅显示的最小单位。像素可以有不同的亮度,像素的坐标值都是整数。3.1 概论3 提出问题(1)目前使用的图形输出设备显示器：光栅图形显示器 (2)光栅图形显示器:以光栅扫描方
2、式刷新线段、字符和图形。其本质: 是一种画点设备，是由一定数量的网格状细小光点（像素）组成，使其某些像素亮，某些像素不亮来显示图形或文字. (3)问题：光栅图形显示器是画点设备，而二维图形并不是点的集合，如何在光栅图形显示器上构造基本二维几何图形(线 圆)？ (4)解决方法： 进行图形扫描转换例： 要在屏幕上显示一条直线时，只能确定出逼近直线的 一组像素， 并按扫描线顺序对这些像素进行写操作，即进行扫描转换。结果: 使所画的直线转换成为逼近理想直线的由无数个点构成的集合 。 画图形：可使用同样的方法，即进行图形的扫描转换.使所画的图形转换成为逼近理想图形的由 无数个点构成的集合 。 二 扫描转
3、换（光栅化）：1 什么叫扫描转换（光栅化）？在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程 。2 扫描转换的主要工作：由于理想的图形是连续的，而光栅图像是离散的，因此显示过程中不可避免地产生锯齿等畸变，扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算法。用一系列的象素点来逼近直线3 学习扫描转换的目的：(1) 绘图函数具有局限性：在实际工作中遇到画线的工作时，可以方便地调用程序设计语言中提供的绘图函数，不需要自己编写画线的程序。但它由局限性，不能满足用户特殊绘图要求，需要开发出满足需求的绘图程序。(2) 学习目的：掌握将数学的、模拟的、线形的图形变成数字的离散的图形的过程中
4、的设计思想和方法，这些思想能够在科学研究和产品开发中发挥作用。3.2 直线的生成三 算法要求：1 准确：扫描点尽可能地逼近理想点。2 快速：改进算法尽 快提高扫描转换速度。一 问题的提出：给定直线两端点P0(x0,y0)和P1(x1,y1)， 在光栅显示器上画出该直线。二 需要进行扫描转换：给出一个将直线转换为逼近理想直线的点的集合的算法。2 直线的斜截式方程： y=kx+b by1kx1x从起点到终点每次增加1，用y=kx+b计算y值，再用putpixel(x,int(y+0.5),color)输出该像素。3 该算法的缺点：画线效率低，每步都需要一个浮点乘法运算和一个四舍五入运算，需要加以改
5、进。 3.2.1 数值微分法(DDA算法 Digital Differential Analyzer )1 直线的微分方程：一 数值微分法：是一种基于直线微分方程来生成直线的方法。 二 数值微分法的改进算法（关键：找到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
6、=k(xi+x)+B=kxi+kx +B=kxi+B+kx /yi=kxi+B=yi +kx=yi +k /当x的步进为1时故Pi +1点的坐标为：xi+1=xi+1yi+1=round ( yi+k) /进行取整运算分析：下一点的y坐标为当前点y 坐标加上斜率k,省略了浮点乘法。Pi +1点的坐标为：xi+1=xi+1yi+1=round ( yi+k)(xi, yi)(xi+1,(int) (yi+k)(xi, (int) (yi)(xi+1, yi+k)数 值 微 分 法 示 意 图理想直线上的坐标点 扫描转换后的像素点2 算法：1)计算斜率 k=y/x2)画第1个点(x0,y0)3)计
7、算下一个点（x，y）的值P，x=x+1, y=y+k 小数部分0.5, 则 y=y+1 循环小数部分0直线下方的点： F(x,y)0 Q在M的下方 （M在直线的上方）则：取P1作为下一个象素，dk = dk =0 Q在M的上 （M在直线的上 ） 则：同上dk 0,取上边的点(像素)，x增1,y增1. 若d1-d20 所以: dk与d1-d2的符号相同）因此：可以将判断d1-d2 的值转化为判断dk的值。由上推出： dk = 2 yxk -2 x yk+ cdk0 :取右上方像素 dk0 :约定取右上方像素存在问题:求dk 的式子中仍有多次乘法，并不能提高效率，求dk+1, dk+2 用上面的方
8、法可以推导出运算公式，但仍然涉及该问题。 解决思路： 试想：如果求出d0的值并找到dk+1与dk的关系式并且这个关系式不含有复杂的运算。则编写程序时可使用循环结构来实现，初值是d0，循环部分是dk+1与dk的关系式需要解决两个问题： （终于找到目标）1 求初值d02 求dk+1与dk的关系式具体思路：1 求出d0的值 2 再找到dk+1与dk的关系.目的: 可用d0的值分别求出d1,d2,. dk. .的值 3 可利用dk的值判断下一个该点亮的像素：dk0 时取右上方像素 dk=0) y=y+1; dk=dk-2*dx; 四课后作业题：用bresenham算法扫描转换从像素点(1,1)到(8,
9、5)线段的像素位置。 五 中点画线算法与bresenham算法的比较：相似处： 1 求出d0的值 2 再找到dk+1与dk的关系. 3 利用dk的值判断下一个该点亮的像素： 不同点： 1 求d0时：中点画线法：利用中点M坐标来求，d02abbresenham法：利用始点终点来求，d02 y- x 2 利用dk的值取像素时：bresenham法 ：dk0 时取右上方像素 dk0 点M在圆的外边,圆离P2点近,取P2F(M)=0 点M在圆的上边 , 取P2F(M)0 点M在圆的里边, 圆离P1点近,取P1问题：下一次取P3？P4？P5？M1P1P2M2M3P3P4P51 构造判别式：若d0 点M在
10、圆的里边，圆离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的增量： 2xp+3 d02(xp-yp )+5 d0 2 求d的增量： （目的：判断下一个该显示的像素）解决方法：M1P1P2M2M3P3P4P5p3 求d的初
11、始值d0：起始点（即第一个像素)为（0,R）, 判别式d的初始值为： d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R4 推导出的结果:d01.25-Rd+2xp+3 d0d+2(xp-yp )+5 d0 M1P1P2M2M3P3P4P5d=5 可以利用推导出的结果，编写程序。三 算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-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)
12、。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,y,d;x = 0; y = r; d = 1-r;wholecircle(x,y,co
13、lor);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,color);putpixel(xc-y,yc+x,
14、color);putpixel(xc+y,yc-x,color);putpixel(xc-y,yc-x,color);3.4 区域填充:区域填充研究如何用一种颜色或一个图案来充满一个二维区域。一 区域：一组具有相同的属性相邻又相连的象素。 二 区域填充：根据边或顶点的简单描述生成区域的过程叫作区域填充。 三 区域填充要做的两个工作：1 在什么地方填充，2 填充什么内容。 四 区域填充算法分为两大类：1. 扫描转换填充算法：按扫描线的顺序确定。2. 种子填充算法：假设在多边形或区域的内部，至少有一个象素是已知的，然后设法找到区域内所有其它象素，并对它们进行填充。 3.4.1 种子填充算法一 种子
15、填充算法的原理：假设在多边形区域内部有一像素已知，由此出发找到区域内的所有像素。假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有象素均不取这一特定值，而边界外的像素则可具有与边界相同的值。从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。图 (a)所示的区域是四连通区域。特点： 区域内像素由四向连接，而区域的边界却是八连通式的。二 几个概念：区域分两种：四向连通区域和八向连通区域1 四向连通区域：2 区域内每个象素，可以通过左、右、上、下、左上、右上、 3 左下、右下这八个方向的移动的组合来到达区域内的任意象素。
16、4 图 (b)所示的区域是八连通区域。 5 特点：区域内象素由八向连接。 6 如两个矩形的连接处为右上连接。 7 但是区域的边界是四连通式的。 8 2 八向连通区域：允许从四个方向寻找下一象素，称为四向算法；允许从八个方向寻找下一象素，称为八向算法。八向算法可以填充八向连通区域，也可以填充四向连通区域。四向算法只能填充四向连通区域，而不能填充八向填充区域。如果图 (b)中的区域是两个分离的区域，并且每个区域需填成不同的颜色，那么，用八向算法会使两个区域被错误地填上同一颜色。3 四向算法和八向算法：1 问题点： 采用什么数据结构？(1)联想迷宫求解问题：相似处：迷宫图中的每一个方块象一个像素，所有的通道块象要填充的区域。不同处：求解迷宫路径：不是所有的通
