当前位置：文档之家 › 计算机图形学4圆及椭圆的扫描转换

计算机图形学4圆及椭圆的扫描转换

  • 格式：ppt
  • 大小：354.00 KB
  • 文档页数：38

下载文档原格式

  / 38

合集下载

第7讲 椭圆的扫描转换

第7讲 椭圆的扫描转换

若d2≤0，取 (xi+1,yi-1) 若d2>0，取(xi,yi-1) 用上半部分计算的最后点(x，y)来计算下半部分中d的初值： d=b2(x+0.5)2+a2(y-1)2-a2b2
递推式
yi
P
d>0,取正下方元素（xi，yi-1）
yi-1 yi-2
xi xi+1 xi+2
(b) d>0的情况
误差项的递推 d1≤0： 取Pu(xi+1,yi)
yi
P
yi-1 yi-2 xi xi+1 xi+2
(a) d<=0的情况
d1 F(xi 2,yi 0.5 ) b 2(xi 2 )2 a 2(yi 0.5 )2 a 2b 2
b 2(xi 1 )2 a 2(yi 0.5 )2 a 2b 2 b 2( 2 xi 3 ) d1 b 2( 2 xi 3 )
void CBrhellipseView::OnBrhellipse() { CDC* pDC=GetDC(); int a=200,b=100,xc=300,yc=200,c=0xff00ff; int x,y;double d1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); pDC->SetPixel(x+300,y+200,c);pDC->SetPixel(-x+300,y+200,c); pDC->SetPixel(x+300,-y+200,c);pDC->SetPixel(-x+300,-y+200,c); while(b*b*(x+1)<a*a*(y-0.5)) { if(d1<0) { d1+=b*b*(2*x+3); x++; } else { d1+=b*b*(2*x+3)+a*a*(-2*y+2); x++;y--; } pDC->SetPixel(x+xc,y+yc,c);pDC->SetPixel(-x+xc,y+yc,c); pDC->SetPixel(x+xc,-y+yc,c);pDC->SetPixel(-x+xc,-y+yc,c); Sleep(50); }

第三章 基本图形的扫描转换讲解

第三章 基本图形的扫描转换讲解
第三章
本章学习目标
扫描转换的基本概念 Jack Elton Bresenham简介 直线的扫描转换算法 圆的扫描转换算法
本章内容
直线的扫描转换 圆的扫描转换 本章小结
直线、圆、椭圆是二维场景中的最基本图形。尽管 MFC的CDC类已经提供了相关的绘制函数，但直接使用 这些函数仍然无法满足真实感图形绘制的要求。光栅扫 描显示器是画点设备，基本图形的光栅化就是在像素点 阵中确定最佳逼近于理想图形的像素点集，并用指定颜 色显示这些像素点集的过程。当光栅化与按扫描线顺序 绘制图形的过程结合在一起时，也称为扫描转换。本章 从基本图形的生成原理出发，使用绘制像素点函数实现 基本图形的扫描转换。绘制像素点函数的原型为
1,
(di 0) (di 0)
（3-3）3.1.3 递推公式来自1.中点误差项的递推公式
M(x i+2,y i+1.5）
M(x i+2,y i+0.5)
Pu
Pu
Pi(xi,yi）
Pd
Pd
（a）di<0
Pi(xi,yi） （b）di≥0 中点的递推
(1)当d<0时
di1 F(xi 2, yi 1.5)
k y y1 y0 x x1 x0
直线水平方向位移 ：
x x1 x0
直线垂直方向位移 ：
y y1 y0
理想直线将平面划分成三个区域：对于直线上的 点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0； 对于直线下方的点，F（x，y）＜0。
假 设 直 线 的 斜 率 为 0≤k≤1 ， 则 |△x|≥|△y| ，
y
O
x
圆的扫描转换

计算机图形学基础（第2版）课后习题答案__陆枫__何云峰

计算机图形学基础（第2版）课后习题答案__陆枫__何云峰

计算机图形学基础（第2版）课后习题答案__陆枫__何云峰第⼀章绪论概念：计算机图形学、图形、图像、点阵法、参数法、图形的⼏何要素、⾮⼏何要素、数字图像处理；计算机图形学和计算机视觉的概念及三者之间的关系；计算机图形系统的功能、计算机图形系统的总体结构。

第⼆章图形设备图形输⼊设备：有哪些。

图形显⽰设备：CRT的结构、原理和⼯作⽅式。

彩⾊CRT：结构、原理。

随机扫描和光栅扫描的图形显⽰器的结构和⼯作原理。

图形显⽰⼦系统：分辨率、像素与帧缓存、颜⾊查找表等基本概念，分辨率的计算第三章交互式技术什么是输⼊模式的问题，有哪⼏种输⼊模式。

第四章图形的表⽰与数据结构⾃学，建议⾄少阅读⼀遍第五章基本图形⽣成算法概念：点阵字符和⽮量字符；直线和圆的扫描转换算法；多边形的扫描转换：有效边表算法；区域填充：4／8连通的边界／泛填充算法；内外测试：奇偶规则，⾮零环绕数规则；反⾛样：反⾛样和⾛样的概念，过取样和区域取样。

5.1.2 中点 Bresenham 算法（P109）5.1.2 改进 Bresenham 算法（P112）习题解答习题5（P144）5.3 试⽤中点Bresenham算法画直线段的原理推导斜率为负且⼤于1的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程）。

（P111）解： k<=-1 |△y|/|△x|>=1 y为最⼤位移⽅向故有构造判别式：推导d各种情况的⽅法(设理想直线与y=yi+1的交点为Q)：所以有： y Q-kx Q-b=0 且y M=y Qd=f(x M-kx M-b-(y Q-kx Q-b)=k(x Q-x M)所以，当k<0，d>0时，M点在Q点右侧（Q在M左），取左点 P l(x i-1,y i+1)。

d<0时，M点在Q点左侧（Q在M右），取右点 Pr(x i,y i+1)。

d=0时，M点与Q点重合（Q在M点），约定取右点 Pr(x i,y i+1) 。

计算机图形学——圆的扫描转换（基本光栅图形算法）

计算机图形学——圆的扫描转换（基本光栅图形算法）

计算机图形学——圆的扫描转换（基本光栅图形算法）与直线的⽣成类似，圆弧⽣成算法的好坏直接影响到绘图的效率。

本篇博客将讨论圆弧⽣成的3个主要算法，正负法、Bresenham 法和圆的多边形迫近法，在介绍算法时，只考虑圆⼼在原点，半径为R的情况。

⼀、正负法1、基本原理假设已选取Pi-1为第i-1个像素，则如果Pi-1在圆内，就要向圆外⽅向⾛⼀步；若已在圆外就要向圆内⾛⼀步。

总之，尽量贴近圆的轮廓线。

2、正负法的具体实现1）圆的表⽰：设圆的圆⼼为(0,0),半径为R，则圆的⽅程为：F(x,y)=x2+y2–R2=0当点(x,y)在圆内时，F(x,y)<0。

当点(x,y)在圆外时，F(x,y)>0。

2）实现步骤第1步：x0=0，y0=R第2步：求得Pi(x i,y i)后找点P i+1的原则为：当P i在圆内时(F(xi,yi)≤0)，要向右⾛⼀步得P i+1，这是向圆外⽅向⾛去。

取x i+1= x i+1, y i+1= y i当P i在圆外时(F(xi,yi)>0)，要向下⾛⼀步得P i+1，这是向圆内⽅向⾛去，取x i+1= x i, y i+1= y i-1⽤来表⽰圆弧的点均在圆弧附近且 F(xi, yi)时正时负假设已经得到点（x i, y i），则容易算出F(x i, y i)，即确定了下⼀个点（x i＋1, y i＋1），则如何计算F(x i+1, y i+1)，以确定下下个点（x i＋2, y i＋2）？分为两种情况：右⾛⼀步后：x i+1=x i+1，y i+1=y i，此时：F(x i+1, y i+1)=x i+12+y i2-R2=x i2+y i2-R2+2x i+1 = F(x i, y i)+2x i+1下⾛⼀步后：x i+1=x i，y i+1=y i-1， 此时：F(x i+1, y i+1)=x i2+（y i-1)2-R2= F(x i, y i)-2y i+1由此可得：确定了F(xi+1, yi+1)之后，即可决定下⼀个点(xi+2, yi+2)，选择道理同上。

{实用}直线圆的各种插补算法

{实用}直线圆的各种插补算法

第四章、基本图形生成算法教学目的：1、知道图形生成中的基本问题；2、熟练掌握直线的扫描转换、圆与椭圆的扫描；3、掌握区域填充；4、了解线宽与线型的处理。

�在光栅显示器上显示的任何一种图形，实际上都是一些具有一种或多种颜色的象素的集合。

�生成算法即图形设备生成图形的方法，也叫光栅化或或图形的扫描转换，是确定一个象素集合及其颜色，用于显示一个图形的过程。

确定一个象素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。

�对图形的扫描转换分为两部分：先确定像素，再用图形的颜色或其他属性进行某种写操作。

绘图元素�构成图形的基本元素，主要有点、直线、圆和曲线等。

图形元素包含的信息：①图元的类型②图元的几何信息③图元的非几何信息；④图元的指针信息11、点22、位置33、像素44、直线55、曲线66、填充点、线图形基元包括：多边形、曲线、字符串 实心图形（或称图形填充）一级图形元素二级图形元素第一节、扫描转换算法一、坐标系1．用户坐标系�在实际世界中用来描述物体的位置、形状等。

坐标单位任意，坐标值是实数、范围不限。

2．笛卡尔坐标系（直角坐标系）�在计算机图形学中使用用来描述物体。

3．设备坐标系�在某一特定设备上用来描述物体，如显示器的屏幕坐标系，绘图仪的绘图坐标系。

坐标单位为像素、步长，即设备的分辨率。

坐标值是整数，有固定的取值范围。

4．规范坐标系�在通用图形软件包中使用的用来描述物体数据所采用的坐标系。

�目的是为了使通用图形软件包摆脱对具体物理设备的依赖性，也为了便于在不同应用和不同系统之间交换图形信息。

�坐标单位任意取，坐标取值范围是［０，１］区间。

笛卡儿坐标系与屏幕坐标系的转换�屏幕（x，y）=（x笛卡儿+x最大分辨率/2，y最大分辨率/2- y笛卡儿）二、笛卡尔坐标系和设备坐标系中相关概念的区别（1）像素点�·在几何学中，点没有准数，没有大小，只表示了在坐标系统中的一个位置。

·在图形系统中，点要由数值坐标表示。

计算机图形学教案

计算机图形学教案

装订首页
工业学院教案
课程：计算机图形学
学期：2013/14第一学期
课时：理论52，实验12
教材：计算机图形学基础教程
计算机图形学实践教程
教师：孔令德静丽亚
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案
工业学院教案。

哈理工教学设计《计算机图形学》(一表)

电子信息工程专业《计算机图形学》教学设计卢迪王鹏张开玉哈尔滨理工大学电气与电子工程学院2006年9月1 课程的基本描述课程名称：计算机图形学Computer Graphics课程性质：学科基础必修课适用专业：电子信息工程教材选用：陈传波，陆枫. 计算机图形学基础.北京：电子工业出版社，2002总学时：60 理论学时：48实验学时：12 课程设计：无学分： 3.5 开课学期：第六学期前导课程：高等数学、线性代数、C语言程序设计后续课程：数字图像处理2 教学定位2.1 能力培养目标本课程主要培养学生以下三个方面的能力：1. 认知和理解能力理解计算机图形学的基本概念、图形的表示与数据结构、曲线曲面的基本概念。

2. 逻辑思维能力理解基本图形的生成算法，并能对现有的算法进行改进，理解图形的变换和裁减算法。

3. 程序设计能力能够根据图形生成算法、裁剪算法设计相应的实现程序。

2.2 课程的主要特点计算机图形学是研究怎样利用计算机来显示、生成和处理图形的原理、方法和技术的一门学科。

是一门复杂的综合性的新兴学科，内容丰富，涵盖的知识面较广。

既有具体的图形软硬件，又有抽象的理论和算法。

为学生以后从事图形图像处理工作打下坚实的基础。

2.3 教学定位计算机图形学是一门应用广泛的新兴学科，主要介绍图形标准、图形硬件、图形的表示、基本图形的生成算法，以及图形的变换和观察等。

通过本课程的学习，学生可以了解图形系统的框架及其涉及的软件、硬件技术；了解图形学的基本问题，掌握图形学的基本概念、方法与算法；对于图形相关的应用及当前的研究热点有一个初步认识；具有一定实践体会和相关的编程能力。

3 知识点与学时分配3.1 计算机图形学及其相关概念计算机图形学及其相关概念、计算机图形系统（学时：0.5学时）计算机图形学、图形的要素、图形的表示方法（理解、核心）计算机图形学与相关学科间的关系（了解、推荐）计算机图形系统的功能（理解、核心）计算机图形系统的结构（了解、推荐）计算机图形学的发展、应用、研究动态（学时：1.5学时）计算机图形学的发展、计算机图形学的应用、计算机图形学的研究动态（了解、推荐）共2学时3.2 图形设备图形输入设备（学时：1.5学时）键盘、鼠标、光笔、触摸屏、图形扫描仪（理解、核心）操纵杆、跟踪球、数据手套、数字化仪、声频输入系统（了解、可选）图形显示设备（学时：2学时）阴极射线管、CRT图形显示器（理解、核心）平板显示器、三维观察设备（了解、可选）图形显示子系统（学时：2学时）显示子系统的结构（理解、核心）分辨率、像素与帧缓存、颜色查找表、显示长宽比（理解、核心）PC图形显示卡（了解、可选）图形绘制设备（学时：0.5学时）打印机、绘图仪（理解、推荐）共6学时3.3 图形的表示与数据结构基本图形元素与段（理解、推荐）几何信息与拓扑信息、坐标系、几何元素（理解、核心）实体、正则集合运算（了解、可选）共2学时3.4 图形的生成、变换和观察基本图形生成算法（学时：12学时）直线的扫描转换（数值微分法、中点Bresenham算法、改进的Bresenham算法）（运用、核心）圆的扫描转换（简单方程产生圆弧、中点Bresenham画圆）（运用、核心）椭圆的扫描转换（椭圆的中点Bresenham画圆）（运用、核心）多边形的扫描转换与区域填充（X扫描线算法、改进的有效边表算法、边缘填充算法、边界填充算法、泛填充算法）（运用、核心）字符处理、属性处理（了解、推荐）反走样（过取样、简单的区域取样、加权区域取样）（理解、核心）二维变换及二维观察（学时：10学时）基本概念（齐次坐标、几何变换、二维变换矩阵）（理解、核心）基本几何变换（平移变换、比例变换、旋转变换、对称变换、错切变换、二维图形几何变换的计算）（运用、核心）二维观察（基本概念、用户坐标系到观察坐标系的变换、窗口到视区的变换）（运用、核心）裁减（点的裁减、直线段的裁减、多边形的裁减、其他裁减）（运用、核心）三维变换及三维观察（学时：4学时）基本概念（三维齐次坐标变换矩阵、几何变换、平面几何投影、观察投影）（理解、核心）三维几何变换（三维基本几何变换、三维复合变换）（理解、核心）共26学时3.5 曲线和曲面基本概念（学时：2学时）曲线曲面数学描述的发展（了解、推荐）曲线曲面的表示、插值和逼近样条、样条描述（理解、核心）三次样条（学时：2学时）自然三次样条、三次Hermite样条（理解、核心）Bezier曲线曲面（学时：2学时）Bezier曲线定义和性质（理解、核心）Bezier曲线的生成（了解、可选）B样条曲线曲面（学时：2学时）定义、性质（理解、核心）B样条曲面（了解、可选）共8学时3.6 其它学时习题课(学时：4学时)实验(学时：12学时)3.7 课程覆盖的知识领域和知识单元汇总4 讲授提示及方法4.1计算机图形学及其相关概念重点：计算机图形学的定义、图形的要素、图形的表示方法、计算机图形系统的功能。

利用仿射变换把圆变成椭圆的例子

利用仿射变换把圆变成椭圆的例子标题：利用仿射变换将圆变成椭圆的例子摘要：此篇文章将介绍利用仿射变换将圆变成椭圆的例子。

我们将从概念及定义入手，逐步深入探讨仿射变换的原理，并通过具体的例子来展示其应用。

我们将总结仿射变换在几何变换中的重要性，并分享个人对此主题的观点和理解。

正文：1. 引言仿射变换是一种几何变换，在计算机图形学和计算机视觉等领域有着广泛的应用。

它可以通过改变平面上点的位置、旋转和缩放等方式，将一个几何图形转换成另一个图形，从而实现对图像的变形处理。

2. 什么是仿射变换仿射变换是指一类线性的几何变换，它保持平行关系和比例关系不变。

简单来说，它是由一个线性变换和一个平移变换组成的合成变换。

假设我们有一个平面上的点 (x, y)，经过仿射变换后，它将变成 (x',y')。

仿射变换可以用矩阵表示：```[x'] = [a b] [x] + [tx][y'] [c d] [y] [ty]```其中，a、b、c、d是线性变换的参数；tx、ty是平移变换的参数。

3. 仿射变换将圆变成椭圆的例子考虑一个以原点 O(0, 0) 为圆心、半径为 r 的圆。

现在我们希望将这个圆变成一个椭圆，即改变其形状。

我们需要找到一个仿射变换，使得圆上的点变换后仍然位于椭圆上。

假设仿射变换的矩阵表示为：```[x'] = [a b] [x] + [tx][y'] [c d] [y] [ty]```为了让变换后的点 (x', y') 位于椭圆上，我们需要满足以下条件：- 变换后的点 (x', y') 到原点 O(0, 0) 的距离与原点到圆心 O(0, 0) 的距离之比应该相等，即 |(x', y')| / r = |(x, y)| / r。

- 变换后的点 (x', y') 在相同的方向上离原点 O(0, 0) 的距离应该相等。

东北大学计算机图形学4

xi 1 xi x xi yi 1 yi y yi 1 1 x xi y k 1 y yi 1 y
DDA算法原理
• 对求出的xi+1，yi+1进行四舍五入，即 round(xi+1)=(int)(x i+1+0.5)或round(y i+1)=(int)(y i+1+0.5)
DDA算法原理
xi 1 xi x yi 1 yi y
其中，
yi+1 ε△y yi xi ε△x xi+1 x
y
1 / | x |, | x || y | 1 / max(|x |, | y |) 1 / | y |, | y || x |
示例图片
右图中，
红色填充点表示的线段： 起点为(0，0) 终点为(10，20)
绿色填充点表示的线段：
起点为(0，0) 终点为(20，10)
• • • • • • • • • • • • • • • • •
Void DDAline(int x0,int y0,int x1,int y1) { int dx,dy,epsl,k; 变量定义：整数型： dx,dy,epsl,k; float x,y,xIncre,yIncre; 符点型：x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; 变量赋初值：线段起点与终点的x,y轴向 x=(float)x0; y=(float)y0; 增量；起点变量类型转换后赋值。 if( abs(dx)>abs(dy)) epsl=abs(dx); else 求x,y轴向增量的大值。 epsl=abs(dy); xIncre=(float)dx/(float)epsl; 求线段在x,y轴向上的步进增量 yIncre=(float)dy/(float)epsl; for(k=0;k<=epsl;k++) { putPixel((int)(x+0.5),(int)(y+0.5))); x+=xIncre; y+=yIncre; } 增量式依次计算线段上个点，并输出。 }

基本图形的扫描转换


= xi +1/k 即当y每递增1时，x递增斜率1/k
18 of 126
输出坐标求整
• 由于屏幕上的坐标为整数坐标，则真正作 为输出显示为：y输出=ROUND(yn)，其中函 数ROUND ()是指舍尾的整数 • 因此y输出和yn 之间的量化误差最大为1。 为了改善这方面的误差，使x和y的值增加 0.5,使量化误差在(-0.5,0.5)范围之间 x=x0+0.5 y=y0+0.5 • ROUND(a)=(int)(a+0.5)
– （5）显示线段的速度应快
• 生成直线可用软件和硬件来实现，一般情况下，硬 件要比软件实现得快。
14 of 126
3.1.2 数值微分DDA直线生成算法
• 数值微分法，DDA（Digital Differential Analyzer）是根据数学上直线的微分方程来设计 的 • 设A(x0,y0)，B(x1,y1)是直线的端点坐标，首先计 算出直线的斜率 k=dy/dx=△y/△x=(y1-y0)/(x1-x0) 直线方程为：y=kx+B 或 x=1/k*y+T
确定一个像素集合及其颜色用于显示一个图形的过程称为图形的扫描转换或光栅化也叫图形的生成126图形生成图形生成是根据图形的几何信息和属性信息结合图形生成算法计算出要显示的中间像素而不像图像生成是保存了图像的每一像素点的信息基本图形的生成首先要根据基本图形的特征找出它的几何信息然后根据一定的生成算法实时地在显示器上显示出完整的图形126图形扫描转换步骤一般分为两个步骤
24 of 126
3.1.3 中点直线生成算法
• 假定直线斜率0<K<1，且 已确定点亮象素点P(xi,yi)， 则下一个与直线最接近的 像素只能是P1(xi+1,yi)点或 P2(xi+1,yi+1)点。设 M(xi+1,yi+0.5)为中点，Q 为交点 • 问题：如何确定下一个点 亮的象素？
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
M P2
M
即d 的增量为 2xp +3.
若d>=0, 则P2 为下一个象素，那么再下一个象 素的判别式为： d1 = F(xp + 2, yp - 1.5) 2 2 2 = (xp + 2) + (yp - 1.5) - r = d + （2xp + 3）+（-2 yp + 2）
P1 M
即d 的增量为 2 (xp - yp) +5.
3 Bresenham画圆法
Bresenham画圆法与中点画圆法有很 多共同之处，不同之处主要是判别式的设 计。
Bresenham画圆算法
顺时针画第一四分圆，下一步选择哪个点？ 基本思想：
通过比较像素与圆的距离平方来避免开方运算
下一像素有3种可能的选择
mH=|(xi+1)2+yi2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|xi2 +(yi-1)2-R2 |
当i=0时，
选D
Bresenham画圆算法
判别式的递推关系 当取H(xi+1,yi)时
i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1
当取V(xi,yi-1)时
i+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1
若d<0，则选H 若d>0，则选D
情形①也 适用
若d=0，则选H
Bresenham画圆算法
当i>0时，D在圆外， ④⑤ 情形④，选mv ，mD 中最小者 d’=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1
P2 M
最后一个问题：判别式d的初始值
d 0 F (1, r 0 . 5 ) 1 ( r 0 .5 )法步骤：
1.输入圆的半径R。
2.计算初始值d=1.25-R、x=0、y=R。
3.绘制点(x,y)及其在八分圆中的另外七个对称点。
4.判断d的符号。若d<0，则先将d更新为d+2x+3，再
x i 1 x i 1 x 0, R
2 2
2
2
2
y

2

y i 1 round ( R x i 1 )
缺点：浮点运算，开方， 取整，不均匀。
x
也可应用圆的参数方程画出分布比较均匀的点． x = Rcos y = Rsin
i 1 i ( 为一固定角度步长
3 Bresenham画圆法
实验三
实验目的：理解和掌握圆的扫描转换 的中点画圆算法。 实验名称：圆的中点画圆算法 实验步骤：（写出实际实现的程序和 结果） 实验总结。
若d’<0，则选D 若d’>0，则选V
情形⑤也 适用
若d’=0，则选D
Bresenham画圆算法
当i=0时，D在圆上， ③ 取D点作为下一个象素
Bresenham画圆算法
当i<0时,
若d≤0，选H
若d>0，选D
当i>0时,
若d’ ≤0，选D 若d’>0，选V
5.当x<=y时，重复步骤3和4。否则结束。
中点画圆法程序代码
MidpointCircle(int r, int color) { int x,y; float d; x=0; y=r; d=1-r; drawpixel(x,y,color); while(x<=y){ if(d<0){ d+ = 2*x+3; x++ } else{d+ = 2*(x-y) + 5; x++;y--; } } }
MidpointCircle(int r, int color) { int x,y; int d; x=0; y=r; d=1-r; deltx =3; delty =-2*r+2; while(x<y) { drawpixel(x,y,color); if(d<0) { d+ = deltx; x++; deltx +=2 } else {d+ = deltx + delty; x++;y--; deltx +=2; delty+=2; } } }
当i<0时，D在圆内，①② 当i=0时，D在圆上，③
①
Pi(xi,yi)
⑤ ④ ②
H(xi+1,yi)
当i>0时，D在圆外，④⑤
V
D (xi+1,yi-1)
③
(xi,yi-1)
Bresenham画圆算法
当i<0时，D在圆内，①② 情形②，选mH ，mD 中最小者 d=mH - mD =|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2| =(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2 =2 (i+yi)-1
第四讲 圆和椭圆的扫描转换
1 基础知识 2 中点画圆法 3 Bresenham画圆法
1 基础知识
1）直接利用圆的方程生成圆 下面先以圆心在原点、半径r为整数的圆 为例，讨论圆的生成算法。
假设圆的方程为： 2 2 2 x + y = r
x + y = r y = sqrt(r2 - x2) 在一定范围内，每给定一 x值，可得一y值。
将 (x,y) 更 新 为 (x+1,y) ； 否 则 先 将 d 更 新 为 d+2(x-
y)+5，再将(x,y)更新为(x+1,y-1)。
5.当x<=y时，重复步骤3和4。否则结束。
中点画圆法程序代码
MidpointCircle(int r, int color) { int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(x<=y){ if(d<0){ d=d+2*x+3; x++ } else{d= d+2*(x-y) + 5; x++;y-;} } }
算法优化
为了进一步提高算法的效率，可以将上面 的算法中的浮点数改写成整数，将乘法运 算改成加法运算，即仅用整数实现中点画 圆法。 使用e=d-0.25代替d e0=1-r 当e为整数时（e<0)(e<-0.25)
算法步骤：
1.输入圆的半径R。 2.计算初始值d=1-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。若d<0，则先将d更新为d+2x+3， 再 将 (x,y) 更 新 为 (x+1,y) ； 否 则 先 将 d 更 新 为 d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。
while(y>=0) {drawpixel(x,y,color); if(delta<0) {delta1=2*(delta+y)-1; if(delta1<=0) direction=1; else direction=2; }
else if (delta>0) {delta2=2*(delta-x)-1; if (delta<=0) direction=2; else direction=3;} else direction=2; switch(direction) {case 1: x++; delta+=2*x+1; break; case 2: x++;y--; delta+=2*(x-y+1); break; case 3: y--; delta+=(-2*y+1); break;} } }
x i 1 round ( R cos i 1 ) y i 1 round ( R sin i 1 ) )
但仍要采用浮点运算、乘法运算、取整运算。
2）八分法画圆
利用圆的对称性：
y y=-x
(-y,x)
(y,x)
y=x
(-x,y)
(-x,-y)
(x,y)
(x,-y)
(-y,-x)
对于圆心在（x0,y0)、半径为r的圆，先对圆心在原 点，半径为r的8分圆进行扫描转换，每确定一个象素，可 输出原始圆的8个点。 void Circle8Points(int x0,int y0, int x,int y,COLORREF c) { pDC->SetPixel(x0+x,y0+y,c); pDC->SetPixel(x0-x,y0+y,c); pDC->SetPixel(x0+x,y0-y,c); pDC->SetPixel(x0-x,y0-y,c); pDC->SetPixel(x0+y,y0+x,c); pDC->SetPixel(x0-y,y0+x,c); pDC->SetPixel(x0+y,y0-x,c); pDC->SetPixel(x0-y,y0-x,c); }