基本图形的生成与计算学习教案

《基本图形的生成与计算学习教案》由会员分享，可在线阅读，更多相关《基本图形的生成与计算学习教案（162页珍藏版）》请在装配图网上搜索。

1、会计学1基本图形的生成基本图形的生成(shn chn)与计算与计算第一页，共162页。2022年5月18日星期三23.1 基本图形元素基本图形元素3.2 直线直线(zhxin)段的生成算法段的生成算法 3.3 圆与椭圆的生成算法圆与椭圆的生成算法 3.4 区域填充算法区域填充算法3.5 线宽的处理与字符的生成线宽的处理与字符的生成3.6 图形裁剪图形裁剪3.7 反走样反走样(antialing)3.8 *图形求交算法图形求交算法本章(bn zhn)目录第1页/共161页第二页，共162页。2022年5月18日星期三3本章重点(zhngdin)、难点本章重点本章重点1、直线段的生成、直线段的生成

2、(shn chn)算法算法2、圆的生成、圆的生成(shn chn)算法算法 3、区域填充算法、区域填充算法4、线宽的处理与字符的生成、线宽的处理与字符的生成(shn chn)5、图形裁剪、图形裁剪本章难点本章难点1、直线段和圆的生成算法2、区域填充算法3、图形裁剪4、反走样和图形求交算法第2页/共161页第三页，共162页。2022年5月18日星期三4本章学习(xux)目标1.掌握(zhngw)二维图形学的基本思想，理解扫描转换法生成图形的基本原理与算法。2. 熟悉图形扫描转换、光栅化、区域填充、裁剪、反走样等基本概念。3.掌握(zhngw)直线段的扫描转换算法、圆和椭圆的扫描转换算法、区域填

3、充的扫描线算法、多边形裁剪算法、反走样算法的基本思想。4.多边形的扫描转换算法、区域采样的基本思想、字符的基本概念。第3页/共161页第四页，共162页。2022年5月18日星期三5绪论绪论(xln) p在图形显示器设备上显示出各种各样的图形是计算机图形学的最终目的。计算机图形显示设备有多种，例如：随机扫描图形显示器、光栅图形扫描显示器、绘图仪、打印机等。 p目前采用的显示器硬件大多数是采用光栅扫描方式工作的，而矢量式显示器装置已很少使用，因而图形学的研究内容也由矢量图形学转成光栅图形学。 p光栅(Raster)将屏幕分成显示网格，一般我们将网格线的交点定义(dngy)成像素(Pixel)。

4、第第3章章 基本图形的生成与计算基本图形的生成与计算屏屏幕幕光光栅栅第4页/共161页第五页，共162页。2022年5月18日星期三6 绪论绪论第第3章章 基本图形基本图形(txng)的生成与计的生成与计算算p光栅(gungshn)CRT图形显示器可以看作是一个由离散单元像素组成的矩阵，每一个像素都可以发亮，因此是一种点画设备。而且每个像素可以用一种或多种颜色显示，分别称为单色显示器或彩色显示器。 p在光栅(gungshn)显示器上显示的任何一种图形，实际上都是一些具有一种或多种颜色的像素的集合。例如：如左图所示。例如：如左图所示。说明：作图的任务就是根据特定的要求点亮特定的像素点，从而完成整

5、体图形的显示。第5页/共161页第六页，共162页。2022年5月18日星期三7第第3章章 基本图形基本图形(txng)的生成与计算的生成与计算 绪论绪论p确定一个像素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。 p对图形的扫描转换一般分为两步：p 确定有关像素；p 用图形的颜色或其他属性对像素进行某种写操作。p 扫描转换的主要工作就是确定一个最佳逼近于图形的像素集。p本章主要讨论一些基本图形的扫描转换问题，如一维线框图形直线、圆、椭圆的扫描转换。二维图形（多边形）的填充问题，字符的表示及输入、输出(shch)问题，以及图形的裁剪、反走样和图形求交问题。第6页/共161页

6、第七页，共162页。2022年5月18日星期三83.1 基本(jbn)绘图元素 本节我们主要(zhyo)介绍图形颜色设置的一些基本控制函数，包 括：颜色的设置和获取颜色信息.。1.1.绘图元素点绘图元素点2.2.绘图元素直线绘图元素直线. .其他基本绘图元素其他基本绘图元素第7页/共161页第八页，共162页。2022年5月18日星期三9 点是图形中最基本的元素，直线、曲线以及其他的图形元素都点是图形中最基本的元素，直线、曲线以及其他的图形元素都是点的集合。是点的集合。第第3章章 基本图形的生成与计算基本图形的生成与计算 一、点一、点（3.1.1）第8页/共161页第九页，共162页。2022

7、年5月18日星期三10Y0X. P(X,Y)YX0Z. P(X,Y,Z)点在二维、三维坐标点在二维、三维坐标(zubio)系统中表示系统中表示3.1 基本绘图元素基本绘图元素第第3章章 基本图形的生成与计算基本图形的生成与计算第9页/共161页第十页，共162页。2022年5月18日星期三11序的像素构成，划分的像素点越多分辨率就越高。例如VGA卡640X480的显示器，分成640X480个网格，网格单元称为像素，一条线段就是由一些连续可见(kjin)的像素所组成，如下图所示：3.1 基本绘图基本绘图(hu t)元素元素第第3章章 基本图形的生成与计算基本图形的生成与计算 二、直线二、直线（3

8、.1.2）第10页/共161页第十一页，共162页。2022年5月18日星期三12注：由上图可知，画一条注：由上图可知，画一条(y tio)直线实际上就是根据一系列计算出来并与该直线实际上就是根据一系列计算出来并与该直线靠近的像素绘制的。直线靠近的像素绘制的。各行各列像素(xin s)中心构成的一组虚拟网格线3.1 基本绘图元素基本绘图元素第第3章章 基本图形的生成与计算基本图形的生成与计算Line: P0(0,0)P1(5,2)0143215234光栅光栅yx像素单元像素单元第11页/共161页第十二页，共162页。2022年5月18日星期三133.2 直线段的生成(shn chn)算法 本

9、节我们主要介绍直线段生成(shn chn)的一些基本算法，包括：数值微分法（DDA法）、中点画线算法和直线的Bresenham算法 。1.1.数值微分法数值微分法（DDADDA法）法）2.2.中点画线算法中点画线算法. .直线的直线的BresenhamBresenham算法算法 第12页/共161页第十三页，共162页。2022年5月18日星期三14第第3章章 基本图形的生成与计算基本图形的生成与计算第13页/共161页第十四页，共162页。2022年5月18日星期三15p 一个图中可以包含成千上万条直线，所以要求直线绘制算法应尽一个图中可以包含成千上万条直线，所以要求直线绘制算法应尽可能的快

10、和准确。可能的快和准确。p 由于光栅网格由于光栅网格(wn )是由离散像素构成，因此我们画出的是由离散像素构成，因此我们画出的一条直线或多或少要产生一些一条直线或多或少要产生一些“台阶台阶”。如下图所示，只有当直线。如下图所示，只有当直线是水平、竖直或是水平、竖直或450时，它才是由像素组成的直线，所有其它直线时，它才是由像素组成的直线，所有其它直线都呈阶梯形。这种现象称为走样或锯齿现象。都呈阶梯形。这种现象称为走样或锯齿现象。3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第14页/共161页第十五页，共162页。2022年5月1

11、8日星期三16在讨论具体的画直线算法之前，我们先来研究一下这类算法的一般在讨论具体的画直线算法之前，我们先来研究一下这类算法的一般要求，即所生成的直线应该具有哪些特征。归纳起来，有以下要求，即所生成的直线应该具有哪些特征。归纳起来，有以下(yxi)几个方面：几个方面：v1.所画的线是直的。除了水平、竖直和450线是直的外，其他取向的线都呈阶梯形，所以必须选择靠近的可寻址像素点来逼近这条直线，选择的好，线就显的直。v2.具有(jyu)精确的起点和终点。画线即要直又要准确，否则会出现一条线的终点和下一条线的起点之间留有间隙，或由此出现积累误差。v3.线的浓度（亮度）应均匀。沿直线显示的像素点的灰度

12、级别度应一致，为此应等距分布，且与线段的长度和斜率无关。3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第15页/共161页第十六页，共162页。2022年5月18日星期三17v实际上，除了水平、竖直和450线的亮度沿整个线段不变外，其他(qt)方向的直线其亮度由于光栅化的结果而变得不均匀。此外，直线的亮度还与方向有关，例如：450线上像素的间隔大于垂直线和水平线像素的间隔，这使得垂直线和水平线较450线亮。v4. 画直线速度快。这要求算法的计算量最少。3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形

13、的生成与计算第16页/共161页第十七页，共162页。2022年5月18日星期三18对于上述这些要求，如同大多数设计准则一样，难以同时完全满对于上述这些要求，如同大多数设计准则一样，难以同时完全满足，如果选择足够高的分辨率和高效率的算法，还是可以获得满足，如果选择足够高的分辨率和高效率的算法，还是可以获得满意的结果。意的结果。生成直线段的算法之间的区别主要是判别和生成生成直线段的算法之间的区别主要是判别和生成x，y增量增量(zn lin)的过程和方法不同，所能适应的设备环境也不同。的过程和方法不同，所能适应的设备环境也不同。本节我们介绍一个象素宽直线的三个常用算法：数值微分法（本节我们介绍一个

14、象素宽直线的三个常用算法：数值微分法（DDA）、中点画线法和）、中点画线法和 Bresenham 算法。算法。 一、数值微分法一、数值微分法(DDA法法)（3.2.1）3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第17页/共161页第十八页，共162页。2022年5月18日星期三19YX(x1,y1)(x2,y2)xyxxyyk1212则有：则有： 1).可通过计算由可通过计算由x方向的增量方向的增量 引起引起y的改变生成的改变生成(shn chn)直线。直线。 由由 （ 为直线上某步的初值）为直线上某步的初值） 则则xyyyii 1iyxkyx

15、xxyyyyiii 121213.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第18页/共161页第十九页，共162页。2022年5月18日星期三20 2).也可通过计算也可通过计算(j sun)由由y方向的增量方向的增量 引起引起x的的改变生成直线。由改变生成直线。由 （ 为直线上某步的初为直线上某步的初值）值） 则：则：y xxxii 1ix211211iiixxxxyxyyyk 12yy 12xx 12xx xkyyii 1)(, 1(1iiyroundx此时此时|K|111()(0.5)iiround yInt y3.2 直线段的生成算法直线

16、段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算)(1 iyround1 iy第19页/共161页第二十页，共162页。2022年5月18日星期三21K=0.4xyyii 4.0150512 xx20212 yy1212xxyy Line: P0(0,0)P1(5,2)0143215234xInt(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.53.2 直线直线(zhxin)段的生成算法段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第20页/共161页第二十一页，共162页。2022年5月1

17、8日星期三22xkyyii11 k1 kykxxii11k112xx 12yy 取不同(b tn)的像素单位y为为步进方步进方向向时时当当1 kx为为步进方向步进方向3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第21页/共161页第二十二页，共162页。2022年5月18日星期三23dda_line (x1, y1, x2, y2, c)int x1, y1, x2, y2, c;float delta_x, delta_y, x, y;int dx, dy, steps, k;dx=x2-x1;dy=y2-y1;3.2 直线直线(zhxin)段

18、的生成算法段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第22页/共161页第二十三页，共162页。2022年5月18日星期三24运行运行(ynxng)DDA_li(ynxng)DDA_linene|K|1, 按按y方向每增加方向每增加1，steps为为y增加的步数。此时递推公式为增加的步数。此时递推公式为delta_x=dx/dy=1/kdelta_y=1ykxxii 113.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第23页/共161页第二十四页，共162页。2022年5月18日星期三25XY00K1-1K1K-13.2 直线

19、段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成基本图形的生成(shn chn)与计算与计算: 如下图第24页/共161页第二十五页，共162页。2022年5月18日星期三26XY0XY00K0 y+=delta_yxkyyii 1情况情况(qngkung)1：|K|1-1K0, 按按X方向每增加方向每增加1，steps为为X增加的步数。此时递推公式为增加的步数。此时递推公式为delta_x=1 x+=delta_xdelta_y=dy/dx=k1, 按按y方向方向(fngxing)每增加每增加1，steps为为y增加的步数。此时递推公式为增加的步数。此时递推公式为de

20、lta_x=dx/dy=1/k0 x+=delta_xdelta_y=1 y+=delta_y情况情况(qngkung)2：|K|1K-1, 按按y方向每增加方向每增加1，steps为为y增加的步数。此时递推公式为增加的步数。此时递推公式为delta_x=dx/dy=1/k0; 3. down直线下方的点直线下方的点: F(x, y)0; 因此，欲判断中因此，欲判断中M在在Q点的上方还是下方，只要把点的上方还是下方，只要把M代入代入F（x，y），并判断它的符号。构造判，并判断它的符号。构造判 cybxayxFMFdpppp )5 . 0() 1()5 . 0, 1()(3.2 直线段的生成算法

21、直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第29页/共161页第三十页，共162页。2022年5月18日星期三31注意注意(zh y)：d是是xp, yp的线性的线性函数，可采用增量计算，提高运算函数，可采用增量计算，提高运算效率。效率。cybxayxFMFdpppp )5 . 0()1()5 . 0, 1()(), 1(10ppyxpd 时为时为当当)1, 1(20 ppyxpd时为时为当当则下一个像素点坐标：则下一个像素点坐标：3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算)5 . 0, 1( ppyxMP2P1QMP

22、=(xP, yP)第30页/共161页第三十一页，共162页。2022年5月18日星期三320 d3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第31页/共161页第三十二页，共162页。2022年5月18日星期三33此为下一个此为下一个(y )判别判别点点M此为下一个判别点此为下一个判别点M取右上方象素取右上方象素P2取正右方象素取正右方象素P1)5 . 1, 2( ppyxM)5 . 0, 2( ppyxM以上分析如下图所示：以上分析如下图所示：0 dd0P2P1QP=(xP, yP)M3.2 直线段的生成算法直线段的生成算法

23、第第3章章 基本图形的生成与计算基本图形的生成与计算第32页/共161页第三十三页，共162页。2022年5月18日星期三34xyd000.510-1.5211.531-0.5422.5520.5解： a=y0-y1=-2; b=x1-x0=5; d0=a+0.5*b=0.5; d1=a=-2; d2=a+b=3 上图为：用中点画线法对连接两点的直线进行上图为：用中点画线法对连接两点的直线进行(jnxng)光栅化光栅化 1.当当 时时,取正右方的点取正右方的点,且且d的增量为的增量为a0 d2.当当 时时,取右上方的点取右上方的点,且且d的增量为的增量为a+b0 dd= 0.5+(-2)d=

24、-1.5+3Line: P0(0,0)P1(5,2)0143215234d= 1.5+ (-2)3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第33页/共161页第三十四页，共162页。2022年5月18日星期三355. 【参考【参考(cnko)程序】程序】 void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y; a=y0-y1; b=x1-x0; d=a+0.5*b; d1=a; d2=a+b; x=x0;y=y0; putpix

25、el(x, y, color); 说明：说明：1.x0,y0,x1,y1分别为直分别为直 线两端线两端(lin dun)点坐标点坐标;2.取正右方的点取正右方的点,且且d的增量为的增量为d1=a;3.取右上方的点取右上方的点,且且d的增量为的增量为d2=a+b;3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第34页/共161页第三十五页，共162页。2022年5月18日星期三36pwhile (xx1)p if (d0) p x+; y+; d+=d2; p else p x+; d+=d1;p putpixel (x, y, color);p /

26、* while */p /* mid PointLine */0 dd0P2P1QP=(xP, yP)M注：由于我们使用的只是注：由于我们使用的只是(zhsh)d的符号，而且的符号，而且d的增量都是的增量都是整数，只是整数，只是(zhsh)初始值包含小数。因此，我们可以用初始值包含小数。因此，我们可以用2d代替代替d来摆脱小数，写出仅包含整数运算的算法。来摆脱小数，写出仅包含整数运算的算法。d+=d2d+=d13.2 直线直线(zhxin)段的生成算法段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第35页/共161页第三十六页，共162页。2022年5月18日星期三37xyd

27、00110-321331-14255215a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1; d1=2*a=-4; d2=2*(a+b)=6 上图为：用中点画线法对连接上图为：用中点画线法对连接(linji)两点的直线进行光栅化两点的直线进行光栅化 1.当当 时时,取正右方的点取正右方的点,且且d的增量为的增量为2a0 d2.当当 时时,取右上方的点取右上方的点,且且d的增量为的增量为2(a+b)0 dd= 1+(-4)d= -3+6Line: P0(0,0)P1(5,2)01432152343.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生

28、成与计算第36页/共161页第三十七页，共162页。2022年5月18日星期三38 void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y;3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第37页/共161页第三十八页，共162页。2022年5月18日星期三39运行运行(ynxng)Mid_Li(ynxng)Mid_Line ne 说明说明(shumng)：1.d的初始值为的初始值为2*a+b;2.取正右方的点时取正右

29、方的点时,d的增量为的增量为d1=2*a;3.取右上方的点时取右上方的点时,d的增量为的增量为d2=2*(a+b);3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第38页/共161页第三十九页，共162页。2022年5月18日星期三40运行(ynxng)效果图3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第39页/共161页第四十页，共162页。2022年5月18日星期三41dydxd3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生

30、成与计算 三、直线的三、直线的Bresenham算法算法 （3.2.3）第40页/共161页第四十一页，共162页。2022年5月18日星期三42如右图所示，设直线如右图所示，设直线(zhxin)方程方程为为 ),(iiyx其中其中k=dy/dx。 假设假设x列的象素已经确定为列的象素已经确定为xi，其行，其行坐标为坐标为yi。那么下一个象素的列。那么下一个象素的列坐标为坐标为xi1，而行坐标要么不变，而行坐标要么不变为为yi，要么递增，要么递增1为为yi1。 行、列坐标（图形学）纵、横坐标几何学注：两者区别xkyxxkyyiiiii )(11dyddxd3.2 直线段的生成算法直线段的生成算

31、法第第3章章 基本图形的生成与计算基本图形的生成与计算第41页/共161页第四十二页，共162页。2022年5月18日星期三43例如例如: 如上图如上图-1，图，图-2所示，若要在屏幕上画一条斜率为所示，若要在屏幕上画一条斜率为K=0.4的从点的从点(0,0)到点到点(50,20)的直线的直线(zhxin)段段,为了便于分析为了便于分析,我们把它放在直角坐标系下考我们把它放在直角坐标系下考虑。注意直线虑。注意直线(zhxin)段在屏幕坐标系中的位置和在一般直角坐标系中的位段在屏幕坐标系中的位置和在一般直角坐标系中的位置的关系。置的关系。图图-1屏幕坐标系屏幕坐标系Max xMax y(0,0)

32、(50,20)图图-2直角坐标系直角坐标系两者的区别和联系Max y(0,0)ddMax x(50,20)ddF 但需要注意但需要注意(zh y)屏幕坐标系与直角坐标系的区别：屏幕坐标系与直角坐标系的区别：3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第42页/共161页第四十三页，共162页。2022年5月18日星期三44因为X下标每增加1，d的值相应(xingyng)递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。 1. 当当d0.5时，直线与时，直线与xi1列垂直列垂直网格交点最接近于当前象素（网格交点最接近于当

33、前象素（xi，yi）的）的右上方象素右上方象素（xi+1，yi1）；）； 2. 当当d0.5时，更接近于时，更接近于正右方象素正右方象素（xi1，yi）。）。 图图-1),(iiyx Bresenham算法误差项的几何含义算法误差项的几何含义dyddxd3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第43页/共161页第四十四页，共162页。2022年5月18日星期三45 2. 【结论【结论(jiln)】1. d的初值的初值d00， ddk；2.当当d0.5时，下一个像素取时，下一个像素取为为 右上方象素（右上方象素（xi+1，yi1）；）；3.当

34、当d0.5时，下一个像素取时，下一个像素取为正为正 右方象素（右方象素（xi1，yi）。）。 2. 当当e0时，更接近于正时，更接近于正右方象素点右方象素点: （xi1，yi）。 图图-1),(iiyx Bresenham算法误差项的几何含义算法误差项的几何含义dyddxd3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第44页/共161页第四十五页，共162页。2022年5月18日星期三46 3. 【参考【参考(cnko)程序】程序】 (0k1)：void Bresenhamline (int x0,int y0,int x1, int y1,in

35、t color) int x,y,i; float dx, dy ,k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i=0.5) e=e-1; if (e=0) y+; 注意注意(zh y) 说明：说明：因为一旦d1，就减去1，同样一旦e0.5，也减去1。这样保证e在-0.5到0.5之间。 3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第45页/共161页第四十六页，共162页。2022年5月18日星期三47d3.2 直线段的生成直线段的生成(shn chn

36、)算法算法第第3章章 基本基本(jbn)图形的生成与计算图形的生成与计算),(iiyxdyxe=-0.5e=e+kddBresenham 算法示意图e0e0第46页/共161页第四十七页，共162页。2022年5月18日星期三48-0.50.55 2 0.10.14 2-0.30.73 1 0.30.32 1-0.1-0.11 0-0.5-0.50 0 e判断前、判断判断前、判断后后 x y斜率斜率(xil)K=2/5=0.4e0=-0.5e 0e= e-1 e=d-0.5 , e=e+k, k=dy/dx当当e0时，取当前像素的右上方像素为下一个像素时，取当前像素的右上方像素为下一个像素当当

37、e0时，取当前像素的正右方像素为下一个像素时，取当前像素的正右方像素为下一个像素0143215234Line: P0(0,0)P1(5,2)3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第47页/共161页第四十八页，共162页。2022年5月18日星期三493.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第48页/共161页第四十九页，共162页。2022年5月18日星期三503.2 直线直线(zhxin)段的生成算法段的生成算法第第3章章 基本图形基本图形(txng)的生成与计算的生

38、成与计算第49页/共161页第五十页，共162页。2022年5月18日星期三51运行运行(ynxng) (ynxng) Bresenham_line-01Bresenham_line-01运行(ynxng)效果图3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第50页/共161页第五十一页，共162页。2022年5月18日星期三52void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy, e0; dx = x1-x0;dy = y1- y0; e0=-d

39、x; x=x0; y=y0; e=-0.5；e0=-dx02* *ee dx 5. 【改进算法【改进算法(sun f)程序】程序】 02* *ee dx3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第51页/共161页第五十二页，共162页。2022年5月18日星期三53 Bresenham 算法算法(sun f)的优点是：的优点是：1、不必计算直线之斜率，因此不做除法；、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；、不用浮点数，只用整数；3、只做整数加减法和乘、只做整数加减法和乘2运算，而乘运算，而乘2运算可以用硬件移位实现。运算

40、可以用硬件移位实现。Bresenham 算法算法(sun f)速度很快，并适于用硬件实现。速度很快，并适于用硬件实现。说明：说明：1. 因为因为e0=2*e*dx且且 e=e+k,则则2*e*dx= 2*e*dx +2*dx*k所以所以(suy)e0=e0+2*dy ；2.同理有同理有e=e-1改为改为: e0=e0-2*dx3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第52页/共161页第五十三页，共162页。2022年5月18日星期三54图图-1屏幕屏幕(pngm)坐标系坐标系Max xMax y(0,0)(50,20)图图-2直角坐标系直角

41、坐标系逆时针旋转逆时针旋转90度度Max yMax x(0,0)(50,20)dddd注意：此时注意：此时d或或e的增量为的增量为 kk1 kdd1 3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算 6. 【几点讨论和思考几点讨论和思考】 第53页/共161页第五十四页，共162页。2022年5月18日星期三55pfor(i=0;i=0.5) e=e-1;p if (e=0) x+ ;p p3.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第54页/共161页第五十五页，共162页。2022

42、年5月18日星期三56v(3)(3)举例：用举例：用BresenhamBresenham方法扫描转换连接方法扫描转换连接(linji)(linji)从点从点P0P0v（0,00,0）到）到PiPi（100,ix100100,ix100）(i=1,2,3,4,5)(i=1,2,3,4,5)的直线段。的直线段。运行运行(ynxng) (ynxng) Bresenham_line-1Bresenham_line-1直线斜率直线斜率K1运行效果图3.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第55页/共161页第五十六页，共162页。2022年5月18日星

43、期三573.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算一般的一般的Bresenham算法判别条件算法判别条件x=x+1y=y+1x=x+1y=y-1x=x-1y=y-1x=x-1y=y+1y增1y增1y减1y减1x增1x增1x减1x减1x1,y1xy(0,0)xy作为上机实验题作为上机实验题第56页/共161页第五十七页，共162页。2022年5月18日星期三583.2 直线直线(zhxin)段的生成算法段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第57页/共161页第五十八页，共162页。2022年5月18日

44、星期三593.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第58页/共161页第五十九页，共162页。2022年5月18日星期三603.2 直线段的生成直线段的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第59页/共161页第六十页，共162页。2022年5月18日星期三613.2 直线直线(zhxin)段的生成算法段的生成算法第第3章章 基本基本(jbn)图形的生成与计算图形的生成与计算第60页/共161页第六十一页，共162页。2022年5月18日星期三623.2 直线直线(zhxin)段的

45、生成算法段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第61页/共161页第六十二页，共162页。2022年5月18日星期三63运行运行(ynxng) (ynxng) Bresenham_lineBresenham_line算法参考算法参考(cnko)课本课本P943.2 直线段的生成算法直线段的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第62页/共161页第六十三页，共162页。2022年5月18日星期三643.3 圆与椭圆(tuyun)的生成算法 本节我们主要介绍圆弧与圆生成的一些基本(jbn)算法，包括：中点画圆算法和圆的Bresenham算法等 。1

46、.1.基础知识基础知识2.2.中点画圆算法中点画圆算法. .圆的圆的BresenhamBresenham算法算法 第63页/共161页第六十四页，共162页。2022年5月18日星期三653.3 圆与椭圆圆与椭圆(tuyun)的生的生成算法成算法22)(ccxxryy ),(ccyxNoImage222)()(ryyxxcc 第第3章章 基本图形的生成与计算基本图形的生成与计算 一、基础知识一、基础知识（3.3.1）程序演示动画.1第64页/共161页第六十五页，共162页。2022年5月18日星期三66 2.极坐标法：极坐标法：当当 从从0 度到度到360 作加作加1递增时，由此式便可求出圆

47、周上均匀递增时，由此式便可求出圆周上均匀分布的分布的360个点的个点的x, y坐标。存在问题：需经三角函数计算，计坐标。存在问题：需经三角函数计算，计算量大。算量大。 在计算机中上述在计算机中上述(shngsh)两个公式所示的方法生成圆周两个公式所示的方法生成圆周都颇费时，效率不高，下面介绍的算法则要简捷得多。都颇费时，效率不高，下面介绍的算法则要简捷得多。3.圆的对称性：圆的对称性： sincos rycyrxcxp圆被定义为到给定中心位置圆被定义为到给定中心位置 距离为距离为r的点集。在这的点集。在这节中，我们只考虑中心在原点，半径节中，我们只考虑中心在原点，半径(bnjng)为整数为整数

48、R的圆的圆),(ccyx222Ryx 3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算程序演示动画.2第65页/共161页第六十六页，共162页。2022年5月18日星期三67说明：说明：1. 对于中心不在原点的圆，可先通过平移变换，化为中对于中心不在原点的圆，可先通过平移变换，化为中心在原点的圆，在进行扫描转换，把所得的像素坐标加上心在原点的圆，在进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。一个位移量即得所求像素坐标。2. 在进行圆的扫描转换时，首先应注意，圆心位于原点在进行圆的扫描转换时，首先应注意，圆心位于原点的圆有四条对

49、称轴的圆有四条对称轴 x=0,y=0,x=y和和x=-y。若已知圆。若已知圆弧上一点（弧上一点（x,y）,可以得到其关于可以得到其关于(guny)四条对称四条对称轴的其它轴的其它7个点，这种性质称为八对称性。个点，这种性质称为八对称性。 因此，只要扫描转换八分之一圆弧，那么圆的其它部分因此，只要扫描转换八分之一圆弧，那么圆的其它部分可通过一系列的简单反射变换得到。如下图所示：可通过一系列的简单反射变换得到。如下图所示：3.3 圆与椭圆圆与椭圆(tuyun)的生成算法的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第66页/共161页第六十七页，共162页。2022年5月18日星期

50、三68设第设第1a象限象限(xingxin)中的某点中的某点已求出已求出 圆心在圆心在0,0点圆周生成点圆周生成(shn chn)时的对称变换时的对称变换 (y,-x)3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第67页/共161页第六十八页，共162页。2022年5月18日星期三693.3 圆与椭圆的生成圆与椭圆的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算第68页/共161页第六十九页，共162页。2022年5月18日星期三70下面下面(xi mian)讨论圆的两讨论圆的两种扫描转换算法：中点画圆法种

51、扫描转换算法：中点画圆法和圆的和圆的Bresenham算法。算法。 利用对称性画一圆利用对称性画一圆,右图所示，注意右图所示，注意(zh y)观察各点的分布情况。观察各点的分布情况。3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第69页/共161页第七十页，共162页。2022年5月18日星期三71p我们讨论我们讨论(toln):如何从点如何从点 到到 顺时针顺时针地确定最佳逼近于该圆弧的像素系列。地确定最佳逼近于该圆弧的像素系列。第二个第二个8分圆分圆), 0(R)2,2(RRyx), 0(R)2,2(RR3.3 圆与椭圆的生成算法圆与椭圆的

52、生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算 二、中点画圆法二、中点画圆法（3.3.2）第70页/共161页第七十一页，共162页。2022年5月18日星期三72当前当前(dngqin)像素与下一像素的侯选者像素与下一像素的侯选者px),(pPyxP), 1(1pPyxP ) 1, 1(2 pPyxPP1P2P=(xP,yP)M 1. 【中点画圆算法的实现中点画圆算法的实现】 3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第71页/共161页第七十二页，共162页。2022年5月18日星期三73当当 时时 ,M在圆内，这说明在圆

53、内，这说明(shumng)P1距离圆弧更近距离圆弧更近,应取应取P1作为下一个像素点。作为下一个像素点。当当 时时,在在P1和和P2之中随便取一个即可之中随便取一个即可,我们约定取我们约定取P2;当当 时时, P2离圆弧更近离圆弧更近,应取应取P2;222),(RyxyxF )5 . 0, 1( ppyxMp中点画圆算法中点画圆算法(sun f)判判别式的构造别式的构造1. 对于圆上的点对于圆上的点,2. 对于圆外的点对于圆外的点,3. 对于圆内的点对于圆内的点,0),( yxF0),( yxF0),( yxF假设假设M是是P1和和P2的中点，即的中点，即NoImage0)( MF那么那么，0

54、)( MF0)( MFP1P2P=(xP,yP)M3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算M1M2程序演示动画.3第72页/共161页第七十三页，共162页。2022年5月18日星期三74 情况情况(qngkung)1当当 时时 ,M在圆内，这说明在圆内，这说明P1距离圆弧更近距离圆弧更近,应取应取P1作为下一个像素点。作为下一个像素点。0)( MF构造构造(guzo)判别式为：判别式为：222) 5 . 0() 1() 5 . 0, 1()(RyxyxFMFdpppp 若若 则应取则应取P1为下一象素，为下一象素，而且而且再下一象素再下

55、一象素的判别式为的判别式为 32) 5 . 0() 2() 5 . 0, 2()(2221 pppppxdRyxyxFMFd所以，所以，沿正右方沿正右方，判别式，判别式d的增量为的增量为 2xp+3。), 1(1pPyxP 0 d此为下一个像素判别点此为下一个像素判别点 M1)5 . 0, 2(1 ppyxMP1P2P=(xP,yP)M3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算M1M2第73页/共161页第七十四页，共162页。2022年5月18日星期三75 情况情况2当当 时时 ,M在圆外，这说明在圆外，这说明P2距离圆弧更近距离圆弧更近

56、,应取应取(yn q)P2作为下一个像素点。作为下一个像素点。0)( MF) 1, 1(2 pPyxP构造构造(guzo)判别式为：判别式为：222) 5 . 0() 1() 5 . 0, 1()(RyxyxFMFdpppp 若若 ，则应取则应取P2为下一象素，为下一象素，而且而且再下一象素再下一象素的判别式为的判别式为 0 d)22()32()5 . 1()2()5 . 1, 2(222 ppppppyxdRyxyxFd次为下一个像素判别点次为下一个像素判别点 M) 5 . 1, 2(2 ppyxM所以，所以，沿右下方向沿右下方向，判别式，判别式d的增量为的增量为2(xp-yp)+5。P1P

57、2P=(xP,yP)M3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算M1M2第74页/共161页第七十五页，共162页。2022年5月18日星期三76（因为（因为(yn wi) ）RRFd 25.1)5 .0, 1(0222) 5 . 0() 1() 5 . 0, 1()(RyxyxFMFdpppp pMidPointCircle(int r ，int color)p p int x,y;p float d;p x=0; y=r; p d=1.25-r;p putpixel(x,y,color);yx), 0 (R)2,2(RR3.3 圆与椭圆

58、的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算 2. 【中点画圆算法参考程序中点画圆算法参考程序】 第75页/共161页第七十六页，共162页。2022年5月18日星期三77yx在第二个八分在第二个八分(b fn)圆内圆内X=Y)2,2(RR), 0(R第二个第二个8分圆分圆取取正右方正右方P1为下一象素为下一象素取取右下方右下方P2为下一象素为下一象素3.3 圆与椭圆圆与椭圆(tuyun)的生成算法的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第76页/共161页第七十七页，共162页。2022年5月18日星期三78从（从（0，10）顺时针地

59、确定）顺时针地确定(qudng)最佳逼近于该圆弧的像素序列。最佳逼近于该圆弧的像素序列。第一个像素(xin s)已知do= -8.75 P1(0,10)第二个像素(xin s)，d= -5.750, P2(1,10)第三个像素(xin s)，d= -0.750, P4(3,10)第五个像素(xin s)，d= -2.750, P6(5,9)第七个像素(xin s)，d= 5.250, P7(6,8)第八个像素(xin s)，d= 6.250, P8(7,7)01.258.75dR 32 pxd5)( 2 ppyxd右下方右下方正右方正右方3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章

60、基本图形的生成与计算基本图形的生成与计算 3.【应用举例应用举例】例例1：用中点画圆法生成半径为用中点画圆法生成半径为10的圆的圆利用圆的对称性通过一系列的简单反射变换得到其他部分的圆弧。利用圆的对称性通过一系列的简单反射变换得到其他部分的圆弧。第77页/共161页第七十八页，共162页。2022年5月18日星期三79 例例2：随机输入：随机输入(shr)半径和颜色，用中点画圆算法生成中心在半径和颜色，用中点画圆算法生成中心在(0,0)的第二个八分圆。的第二个八分圆。3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第78页/共161页第七十九页，

61、共162页。2022年5月18日星期三803.3 圆与椭圆圆与椭圆(tuyun)的生成算法的生成算法第第3章章 基本图形基本图形(txng)的生成与计算的生成与计算第79页/共161页第八十页，共162页。2022年5月18日星期三81运行运行(ynxng) (ynxng) MidPointCircle-2/8MidPointCircle-2/8运行运行(ynxng)结果图结果图3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第80页/共161页第八十一页，共162页。2022年5月18日星期三82初始化运算初始化运算(yn sun)d=1.25

62、-r对对应于应于e=1-r;判别式判别式d0对应于对应于e-0.253.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算 4. 【程序分析和算法改进程序分析和算法改进】 第81页/共161页第八十二页，共162页。2022年5月18日星期三83p else p e+=2*(x-y)+5; p x+;p y-;p putpixel(x,y,color);p /*while*/p/*MidPointCircle*/3.改进改进(gijn)的参考程序的参考程序d=1.25-re-0.25d0注意注意(zh y)程序改动的语句程序改动的语句3.3 圆与椭圆的

63、生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第82页/共161页第八十三页，共162页。2022年5月18日星期三84例如：采用改进的中点画圆法绘制例如：采用改进的中点画圆法绘制(huzh)中心在（中心在（0，0）半径为）半径为R的圆的第二个的圆的第二个8分圆以及用对称性生成第一个分圆以及用对称性生成第一个8分圆。分圆。运行运行(ynxng) (ynxng) MidPointCircle-1/4MidPointCircle-1/4F 注意注意: 利用对称性生成第一个利用对称性生成第一个八分圆八分圆,只需在算法程序只需在算法程序中中putpixel(x,y,co

64、lor)的语句后加一条的语句后加一条:putpixel(y, x,color)语句即可实现。语句即可实现。(x,y)(y,x)3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第83页/共161页第八十四页，共162页。2022年5月18日星期三85（0，R）YXOR第一个第一个4分圆分圆3.3 圆与椭圆的生成圆与椭圆的生成(shn chn)算法算法第第3章章 基本图形的生成与计算基本图形的生成与计算 三、圆的三、圆的Bresenham算法算法 （3.3.3）第84页/共161页第八十五页，共162页。2022年5月18日星期三86（0，R）YXO

65、R第一个第一个4分圆分圆(x,y)H(x+1,y)V(x,y-1)D(x+1,y-1)第一个第一个4分圆下一像素分圆下一像素(xin s)的的三个候选者三个候选者3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算 1. 【圆的圆的Bresenham算法的实现算法的实现】 第85页/共161页第八十六页，共162页。2022年5月18日星期三871. H、D、V全在圆内；全在圆内；2. H在圆外在圆外,D、V在圆内；在圆内；3. D在圆上在圆上,H在圆外在圆外, V在圆内在圆内;4. H、D、在圆外，、在圆外， V在圆内；在圆内；5. H、D、V全在

66、圆外；全在圆外； 3.3 圆与椭圆圆与椭圆(tuyun)的生成算法的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第86页/共161页第八十七页，共162页。2022年5月18日星期三88222) 1(RyxH 222) 1() 1(RyxD 222) 1()(RyxV p与与 Bresenham直线扫描算法一样，在选最佳逼近直线扫描算法一样，在选最佳逼近(bjn)该圆的像素时，我们希望只判别误差项的符号该圆的像素时，我们希望只判别误差项的符号 。3.3 圆与椭圆的生成算法圆与椭圆的生成算法第第3章章 基本图形的生成与计算基本图形的生成与计算第87页/共161页第八十八页，共162页。2022年5月18日星期三89情况情况(qngkung)（一）：一）：0 Dp如果如果 ,那么右下方像素那么右下方像素D在在圆内，圆弧与候选点的关系只可圆内，圆弧与候选点的关系只可能是能是1与与2的情形的情形(qng xing)。则。则这是最佳逼近圆弧的像素只可能这是最佳逼近圆弧的像素只可能是是H或或D两个像素之一。两个像素之一。0 D 为了确定为了确定H和和D哪个更接近于哪个更接近于圆弧圆