![第3章基本图形的生成_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/14/6538f8b3-9961-4090-bdbb-c2b394efec71/6538f8b3-9961-4090-bdbb-c2b394efec711.gif)
![第3章基本图形的生成_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/14/6538f8b3-9961-4090-bdbb-c2b394efec71/6538f8b3-9961-4090-bdbb-c2b394efec712.gif)
![第3章基本图形的生成_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/14/6538f8b3-9961-4090-bdbb-c2b394efec71/6538f8b3-9961-4090-bdbb-c2b394efec713.gif)
![第3章基本图形的生成_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/14/6538f8b3-9961-4090-bdbb-c2b394efec71/6538f8b3-9961-4090-bdbb-c2b394efec714.gif)
![第3章基本图形的生成_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/14/6538f8b3-9961-4090-bdbb-c2b394efec71/6538f8b3-9961-4090-bdbb-c2b394efec715.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第第2章章 基本图形生成原理基本图形生成原理一一 光栅扫描:光栅扫描: 1 光栅扫描的基本原理:光栅扫描的基本原理: 电子束在荧光屏上按照固定的扫描线和扫描顺序扫出 一个由行和列组成的光的栅网。 2 像素:像素: 栅网中的每一个孤立的光点,它是光栅显示的最小单位。 像素可以有不同的亮度,像素的坐标值都是整数。 概论概论 3 提出问题提出问题(1)目前使用的图形输出设备显示器:目前使用的图形输出设备显示器:光栅图形显示器(2)光栅图形显示器光栅图形显示器: 以光栅扫描方式刷新线段、字符和图形。 其本质: 是一种画点设备,是由一定数量的网格状细小光点 (像素)组成,使其某些像素亮,某些像素不亮来显
2、 示图形或文字.(3)问题:问题: 光栅图形显示器是画点设备,而二维图形并不是点的集合, 如何在光栅图形显示器上构造基本二维几何图形(线 圆)?(4)解决方法:解决方法: 进行图形扫描转换进行图形扫描转换 例: 要在屏幕上显示一条直线时,只能确定出逼近直线的 一组像素, 并按扫描线顺序对这些像素进行写操作,即进行扫描转换。 结果: 使所画的直线转换成为逼近理想直线的由无数个点构成的集合 。 画图形:可使用同样的方法,即进行图形的扫描转换. 使所画的图形转换成为逼近理想图形的由 无数个点构成的集合 。 扫描转换(光栅化):扫描转换(光栅化): 1 什么叫扫描转换(光栅化)?什么叫扫描转换(光栅化
3、)? 在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程 。 2 扫描转换的主要工作:扫描转换的主要工作: 由于理想的图形是连续的,而光栅图像是离散的,因此显示过程中不可 避免地产生锯齿等畸变, 扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算法。研究使光栅图像逼近原始的图形的算法。 用一系列的象素点来逼近直线 3 学习扫描转换的目的:学习扫描转换的目的: (1) 绘图函数具有局限性: 在实际工作中遇到画线的工作时,可以方便地调用程序设计 语言中提供的绘图函数,不需要自己编写画线的程序。 但它由局限性,不能满足用户特殊绘图要求,需要开发出满 足需求的绘图程序。 (2) 学习目的
4、: 掌握将数学的、模拟的、线形的图形变成数字的离散的图形 的过程中的设计思想和方法,这些思想能够在科学研究和产 品开发中发挥作用。2.1 直线的生成直线的生成三三 算法要求:算法要求: 1 准确:扫描点尽可能地逼近理想点。 2 快速:改进算法尽 快提高扫描转换速度。 一一 问题的提出:问题的提出: 给定直线两端点P0(x0,y0)和P1(x1,y1), 在光栅显示器上画出该直线。 二二 需要进行扫描转换:需要进行扫描转换: 给出一个将直线转换为逼近理想直线的点的集合的算法。 2 2 直线的斜截式方程:直线的斜截式方程: y=kx+b by1kx1 x从起点到终点每次增加1,用y=kx+b计算y
5、值, 再用putpixel(x,int(y+0.5)int(y+0.5),color)输出该像素。 3 该算法的缺点:该算法的缺点: 画线效率低,每步都需要一个浮点乘法运算和一个 四舍五入运算,需要加以改进。 2.2. 数值微分法数值微分法(DDA算法算法 Digital Differential Analyzer ) kxxyyxydxdy0101 1 直线的微分方程直线的微分方程:一一 数值微分法:是一种基于直线微分方程来生成直线的方法。数值微分法:是一种基于直线微分方程来生成直线的方法。 二二 数值微分法的改进算法数值微分法的改进算法(关键:找到(关键:找到Pi(Xi,Yi), Pi+1
6、(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+1 yi+1=round ( y
7、i+k) /进行取整运算分析:分析:下一点的下一点的y坐标为当前点坐标为当前点y 坐标加上斜率坐标加上斜率k,省略了浮点乘法。省略了浮点乘法。 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
8、,y) int x0,y0,x1,y1; int x; float dx,dy,k,y; dx=x1-x0; 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
9、M2 P 根据不同情况分析如下:第一种情况:当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的增量为a。 ax+by+c=0 Q P1 P2 M P3 P4 P5 M1 M2 P 第二种情况:当d0时,取正上方的象素p2,下一步则应在p4和p5当中选择, 设
10、它们的中点为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。 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) =
11、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 P2 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 三三 进一步改进算法:进一步改
12、进算法: 注意到初始值中有浮点运算,消除浮点可以进一步改进算法。 考察判别式dk,判别使用的仅仅是dk的符号,且dk的增量都是整数, 故用2dk来代替dk,摆脱小数(浮点),从而提高速度。 改进结果:改进结果:(中点画线法的精髓)中点画线法的精髓) 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 理解该算法的来龙去脉(上述结果是怎么得来的)。理解该算法的来龙
13、去脉(上述结果是怎么得来的)。2 能够用上述结果解题,编程实现该算法。能够用上述结果解题,编程实现该算法。四四 总结中点画线算法:总结中点画线算法: 1 基本思想:通过判断dk的值来确定下一个该点亮的像素 2 思路: (1)先求d0的值(利用中点M求):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 利用推导结果编程实现中点画线算法:利用推导结果编程实现中点画线算法: int x0,
14、y0,x1,y1; 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; DrawPixel(x,y); /DrawPixel为自己编写的函数。显示x,y点 while(xx1) if(d0.5,则(x,y)更新为(x+1,y+1),同时将d更新为d-1;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。改
15、进改进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.计算初始值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
16、-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=-
17、dx;x=x0;y=y0; while(x0) y=y+1; e=e-2*dx; 课后作业题:课后作业题: 用bresenham算法扫描转换从像素点(1,1)到(8,5)线段的 像素位置。 3.3 圆的生成圆的生成3.3.1 八分法画圆算法八分法画圆算法思路思路: (考虑到(考虑到圆的对称性)圆的对称性) 画出A点则剩下的7个点都能画出,画出B点则剩下的7个点都能画出, 因此,只讨论8分圆的画法即可(x,y)yy=-xy=xA(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)B二二 算法原理算法原理: 利用其函数方程,直接离散计算 圆的函数方程为: 222R
18、yx )(121211iiiixRroundyxx缺点:计算量过大三三 圆的极坐标方程为:圆的极坐标方程为: sincosRyRx)sin()cos()11111iiiiiiRroundyRroundx ( 为一固定角度步长 可先通过平移变换,把计算所得的像素(x1,y1)坐标加上 一个位移量(delta_x和delta_y)即得所求像素坐标(x2,y2)。 即: x2=x1+delta_x y2=y1+delta_y四四 中点不在原点的圆:中点不在原点的圆:3.3.2 中点画圆算法中点画圆算法 (关键:找到(关键:找到d的增量)的增量)一一 基本思路:基本思路: 利用中点M来选择下一个要显示
19、的像素。二二 分析:分析: M的坐标是(x+1,y-0.5) F(M)0 点M在圆的外边,圆离P2点近,取P2 F(M)=0 点M在圆上 , 取P2或者P1 F(M)0 点M在圆的里边, 圆离P1点近,取P1 问题:下一次取问题:下一次取P3P3?P4P4?P5P5? M1P1P2M2M3P3P4P5222)5 . 0() 1()5 . 0, 1(),(RyxyxFyxFdppppMM1 构造判别式:构造判别式:若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的增量: 2xp+3 d0 2(xp-yp )+5 d0 2 求求d的增量:的增量: (目的:判断下一个该显示的像素)解决方法:解决方法:M1P1P2M2M3P3P4P5p3 求求d的初始值的初始值d0: 起始点(即第一个像素)为(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度工程项目施工图设计与审查服务协议
- 2025年度国际贸易仲裁条款专用销售合同
- 2024-2030年中国电力监测设备行业市场全景监测及投资前景展望报告
- 2025年橡胶棍项目可行性研究报告
- 职工困难申请书
- 2025年度建筑工程施工劳务人员劳动合同变更合同
- 中国皮卡行业市场前景预测及投资方向研究报告
- 测井设备项目可行性报告范文参考
- 公共建筑节能评估报告编制的指南2025-图文
- 2025年度城市基础设施建设项目造价咨询与监理服务合同范本
- 网络安全攻防演练报告
- 新《学前教育法》知识讲座课件
- 公文写作题库(500道)
- 学校教学常规管理学习活动课件
- 广东省湛江市2023-2024学年高一上学期期末考试 历史 含解析
- 2024-2030年中国大闸蟹养殖行业运营形势分析及未来销售格局研究报告
- 餐饮业绩效考核表(店长、前厅领班、吧台、厨师长、后厨、服务员、收银员、库管、后勤)3
- (2024版)中国血脂管理指南
- 集成墙板购销合同范本(2024版)
- 2023九年级历史下册 第三单元 第一次世界大战和战后初期的世界第10课《凡尔赛条约》和《九国公约》教案 新人教版
- 持续质量改进项目汇报
评论
0/150
提交评论