圆椭圆多边形和字符串等曲线及一些其他的复杂图形均可用线段课件.ppt

1、甘朝华第三章 基本图元的生成3.13.1 线段的生成线段的生成3.23.2 圆的生成圆的生成3.33.3 区域填充区域填充3.43.4 字符的生成字符的生成3.53.5 其他曲线其他曲线3.6 3.6 图元属性控制图元属性控制3.7 3.7 反走样反走样基本图元基本图元复杂图形复杂图形组合、变换组合、变换 基本图元的生成算法研究是计算基本图元的生成算法研究是计算机图形学的基本问题之一机图形学的基本问题之一。基本的二维图元有点、线段、圆、基本的二维图元有点、线段、圆、椭圆、多边形和字符串等。椭圆、多边形和字符串等。曲线及一些其他的复杂图形均可曲线及一些其他的复杂图形均可用线段或多边形用线段或多边

2、形拟合拟合得到。得到。光栅扫描转换理解所有算法过程的思维主线：理解所有算法过程的思维主线：（1 1）该问题在数学或几何上的意义是）该问题在数学或几何上的意义是什么，相应的数学计算公式是什么；什么，相应的数学计算公式是什么；（2 2）在光栅显示器上每一个像素点都）在光栅显示器上每一个像素点都占据一定的空间；占据一定的空间；（3 3）生成某种图形的算法可能有多种，）生成某种图形的算法可能有多种，可以根据使用场合不同，用某些指标可以根据使用场合不同，用某些指标来衡量算法的效能。来衡量算法的效能。3.1 3.1 线段的生成线段的生成数学基础：数学基础：设线段的设线段的2 2个端点为（个端点为（x xs

3、 s,y,ys s）和）和（x xe e,y,ye e），直线的斜率截距方程为：），直线的斜率截距方程为：y=my=mx+bx+b （3.13.1）3.1 3.1 线段的生成线段的生成 数字微分分析法（数字微分分析法（digital digital differential analyzerdifferential analyzer，简称，简称DDADDA）是）是一种线段扫描转换算法。一种线段扫描转换算法。3.1.1 DDA3.1.1 DDA画线算法画线算法 在图形生成算法中由于几何图形在在图形生成算法中由于几何图形在空间位置上具有连贯性，成为多种图形空间位置上具有连贯性，成为多种图形生成算法

4、的基本思想。生成算法的基本思想。基于这种思想的图形绘制算法中所基于这种思想的图形绘制算法中所需要解决的问题就是如何确定后一个像需要解决的问题就是如何确定后一个像素点。（素点。（中点画线、中点画线、BresenhamBresenham画线、中画线、中点画圆、点画圆、BresenhamBresenham画圆画圆）。）。3.1 3.1 线段的生成线段的生成3.1.2 3.1.2 中点画线算法中点画线算法几何图形在空间位置上具有连贯性：几何图形在空间位置上具有连贯性：（1 1）根据图形的几何方程式构造判断条）根据图形的几何方程式构造判断条件（即判别式），根据判断条件的值与件（即判别式），根据判断条件的

5、值与0 0之间的关系可以确定下一个图形取值点之间的关系可以确定下一个图形取值点的坐标；的坐标；（2 2）根据坐标增量规律计算判别条件之）根据坐标增量规律计算判别条件之间的递推关系，并确定在起点坐标处的间的递推关系，并确定在起点坐标处的初始判别条件值；初始判别条件值；（3 3）观察判别条件中有无可能进行一些）观察判别条件中有无可能进行一些调整来减少运算的复杂程度。调整来减少运算的复杂程度。3.1 3.1 线段的生成线段的生成3.1.2 3.1.2 中点画线算法中点画线算法3.1 3.1 线段的生成线段的生成3.1.2 3.1.2 中点画线算法中点画线算法3.1 3.1 线段的生成线段的生成处理方

6、法分析处理方法分析优化计算过程优化计算过程程序实现程序实现3.1.2 3.1.2 中点画线算法中点画线算法3.1 3.1 线段的生成线段的生成算法思想：算法思想：假定线段位于第一象限（假定线段位于第一象限（m0m0，11），其它象限雷同。），其它象限雷同。3.1.3 Bresenham3.1.3 Bresenham画线算法画线算法3.1 3.1 线段的生成线段的生成算法思想：算法思想：3.1.3 Bresenham3.1.3 Bresenham画线算法画线算法3.1 3.1 线段的生成线段的生成两头并进算法、双步算法、两头并进算法、双步算法、N N步画线算法步画线算法 利用并行计算机进行并行处

7、理也是利用并行计算机进行并行处理也是提高画线速度的一种方式。提高画线速度的一种方式。通过某种分割方法将线段分解成若通过某种分割方法将线段分解成若干部分，并分配到多个处理器上分别进干部分，并分配到多个处理器上分别进行线段像素位置计算。行线段像素位置计算。3.1.4 3.1.4 并行画线算法并行画线算法3.23.2 圆的生成圆的生成 圆是一种常用图元，由于其具有圆是一种常用图元，由于其具有8 8子子象限对称性，因此在下面的讨论中只要象限对称性，因此在下面的讨论中只要生成其某一个子象限的圆弧，就可根据生成其某一个子象限的圆弧，就可根据其对称性画出整个圆。其对称性画出整个圆。3.23.2 圆的生成圆的

8、生成直角坐标法直角坐标法极坐标法极坐标法圆的圆的8 8对称性对称性3.2.1 3.2.1 圆的特性圆的特性3.23.2 圆的生成圆的生成 中点画圆算法与中点画线算法类似，中点画圆算法与中点画线算法类似，只是构造判别式有所不同。只是构造判别式有所不同。3.2.2 3.2.2 中点画圆算法中点画圆算法3.23.2 圆的生成圆的生成3.2.3 3.2.3 BresenhamBresenham画圆算法画圆算法3.33.3 区域填充区域填充填充区域（填充区域（fill areafill area）:由一定的边界围成的一个区间，其由一定的边界围成的一个区间，其内部用某种颜色或图案进行填充。内部用某种颜色或

9、图案进行填充。填充区域的边界可有多种形式，如填充区域的边界可有多种形式，如圆形、折线、不规则曲线等，但规定在圆形、折线、不规则曲线等，但规定在计算机图形学中只用多边形来表示填充计算机图形学中只用多边形来表示填充区域。区域。3.33.3 区域填充区域填充凸（凸（convexconvex）多边形）多边形凹（凹（concaveconcave）多边形）多边形内角内角3.3.1 3.3.1 多边形分类与识别多边形分类与识别3.33.3 区域填充区域填充1.1.识别凹多边形识别凹多边形3.3.1 3.3.1 多边形分类与识别多边形分类与识别3.33.3 区域填充区域填充2.2.分割凹多边形分割凹多边形 向

10、量法（向量法（vector methodvector method）旋转法（旋转法（rotational methodrotational method）3.3.1 3.3.1 多边形分类与识别多边形分类与识别3.33.3 区域填充区域填充多边形有两种表示方法多边形有两种表示方法：顶点表示顶点表示 点阵表示点阵表示3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.33.3 区域填充区域填充区域填充的过程可以分为两步区域填充的过程可以分为两步：（1 1）确定哪些像素属于区域内部，哪些）确定哪些像素属于区域内部，哪些属于区域外部；属于区域外部；（2 2）对属于区域内部的像素，按所要求）对属于

11、区域内部的像素，按所要求的填充色或图案来填充对应的像素。的填充色或图案来填充对应的像素。3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.33.3 区域填充区域填充填充算法分为两大类：填充算法分为两大类：（1 1）扫描线填充算法（）扫描线填充算法（scan-line scan-line fillingfilling）（2 2）种子填充算法（）种子填充算法（seed fillingseed filling）3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.33.3 区域填充区域填充1.1.扫描交点奇偶数判断法扫描交点奇偶数判断法3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.

12、33.3 区域填充区域填充2.2.改进的扫描线填充算法改进的扫描线填充算法顶点计数问题处理顶点计数问题处理扫描线与相交边求交点扫描线与相交边求交点减少求交计算量减少求交计算量-活性边表活性边表3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.33.3 区域填充区域填充2.2.改进的扫描线填充算法改进的扫描线填充算法3.3.2 3.3.2 扫描线填色算法扫描线填色算法3.33.3 区域填充区域填充3.3.3 3.3.3 种子填色算法种子填色算法3.33.3 区域填充区域填充1.1.堆栈式种子像素填充法堆栈式种子像素填充法3.3.3 3.3.3 种子填色算法种子填色算法3.33.3 区域填充

13、区域填充2.2.四邻法种子填充算法四邻法种子填充算法3.3.3 3.3.3 种子填色算法种子填色算法3.33.3 区域填充区域填充 完整的完整的OpenGLOpenGL多边形是用多边形是用glBeginglBegin、glEndglEnd之间所描述的顶点集合来描述，多之间所描述的顶点集合来描述，多边形的形状由边形的形状由glBeginglBegin函数中参数的函数中参数的6 6种种不同的符号常量来决定。不同的符号常量来决定。1.1.多边形形状描述常量多边形形状描述常量 2.2.像素阵列函数像素阵列函数3.3.4 3.3.4 OpenGLOpenGL多边形区域填充函数、像素阵列函数多边形区域填充

14、函数、像素阵列函数3.33.3 区域填充区域填充1.1.多边形形状描述常量多边形形状描述常量3.3.4 3.3.4 OpenGLOpenGL多边形区域填充函数、像素阵列函数多边形区域填充函数、像素阵列函数3.33.3 区域填充区域填充2.2.像素阵列函数像素阵列函数 像素阵列是多边形填充的一种形式，像素阵列是多边形填充的一种形式，它是用一个图像阵列重复填充一个多边它是用一个图像阵列重复填充一个多边形的内部。形的内部。两类：由彩色像素构成的阵列称为两类：由彩色像素构成的阵列称为一个像素图（一个像素图（pixmappixmap）;阵列每个像素的值为阵列每个像素的值为0 0或或1 1的像素阵的像素阵

15、列称为位图（列称为位图（bitmapbitmap），其颜色构成只），其颜色构成只有黑、白两种。有黑、白两种。3.3.4 3.3.4 OpenGLOpenGL多边形区域填充函数、像素阵列函数多边形区域填充函数、像素阵列函数3.4 3.4 字符的生成字符的生成 字符是图形中的主要组成部分，主字符是图形中的主要组成部分，主要用来作为图形表达意义的补充形式。要用来作为图形表达意义的补充形式。3.4 3.4 字符的生成字符的生成 在点阵字库中，每个字符都被定义在点阵字库中，每个字符都被定义成字符掩膜的矩阵。成字符掩膜的矩阵。3.4.1 3.4.1 点阵式字符点阵式字符3.4 3.4 字符的生成字符的生成

16、 矢量字符记录字符的笔画信息而不矢量字符记录字符的笔画信息而不是整个位图，具有存储空间小、不变形、是整个位图，具有存储空间小、不变形、美观、变换方便等优点。美观、变换方便等优点。对于字符的旋转、缩放等变换，点对于字符的旋转、缩放等变换，点阵字符的变换需要对表示字符位图中的阵字符的变换需要对表示字符位图中的每一像素进行；而矢量字符的变换只要每一像素进行；而矢量字符的变换只要对其笔画端点进行变换就可以了。对其笔画端点进行变换就可以了。3.4.2 3.4.2 矢量字符矢量字符3.4 3.4 字符的生成字符的生成 矢量轮廓字符采用直线、二次三矢量轮廓字符采用直线、二次三次次BezierBezier曲线

17、及提示（曲线及提示（HintHint）技术描述）技术描述字型。字型。3.4.2 3.4.2 矢量字符矢量字符3.4 3.4 字符的生成字符的生成 OpenGL OpenGL基本库仅提供了显示单个字基本库仅提供了显示单个字符和文字串的基本支持。符和文字串的基本支持。3.4.3 3.4.3 OpenGLOpenGL字符函数字符函数3.53.5 其他曲线其他曲线 许多曲线函数在对象建模、动画轨许多曲线函数在对象建模、动画轨迹的描述、数据和函数的图形化及其他迹的描述、数据和函数的图形化及其他图形应用中均是重要的图元图形应用中均是重要的图元。常见曲线有圆锥曲线、三角和指数常见曲线有圆锥曲线、三角和指数函

18、数、概率分布、通用多项式和样条函函数、概率分布、通用多项式和样条函数数。3.63.6 图元属性控制图元属性控制 任何影响图元显示方式的参数都可任何影响图元显示方式的参数都可称为图元属性控制参数，图元的类型不称为图元属性控制参数，图元的类型不同其控制参数类型也有所不同。同其控制参数类型也有所不同。一般的属性控制参数包括颜色、大一般的属性控制参数包括颜色、大小、线型、填充方式、字体、可见性、小、线型、填充方式、字体、可见性、可检测性等。可检测性等。3.63.6 图元属性控制图元属性控制3.6.1 3.6.1 颜色颜色3.63.6 图元属性控制图元属性控制 点的属性一般涉及颜色和大小点的属性一般涉及

19、颜色和大小2 2个属个属性，这些属性由系统的状态变量的当前性，这些属性由系统的状态变量的当前值决定。值决定。3.6.2 3.6.2 点的属性点的属性3.63.6 图元属性控制图元属性控制 直线的基本显示属性包括颜色、线直线的基本显示属性包括颜色、线宽、线型。其颜色属性仍由系统状态表宽、线型。其颜色属性仍由系统状态表中当前颜色值决定，线宽和线型需要进中当前颜色值决定，线宽和线型需要进行其他处理。行其他处理。3.6.3 3.6.3 线的属性线的属性3.63.6 图元属性控制图元属性控制1 1 线宽线宽:标准的直线绘制宽度为标准的直线绘制宽度为1 1个像素，其个像素，其他线宽是标准线宽的整数倍。他线

20、宽是标准线宽的整数倍。在光栅实现中，通过沿相邻水平线在光栅实现中，通过沿相邻水平线路径（或相邻垂直线路径）绘制额外的路径（或相邻垂直线路径）绘制额外的像素而得到。像素而得到。3.6.3 3.6.3 线的属性线的属性3.63.6 图元属性控制图元属性控制1 1 线宽线宽:缺点缺点:2 2个线段在交点处有缺口个线段在交点处有缺口 线的粗细不一样线的粗细不一样 线段的始末端总是水平或垂直的线段的始末端总是水平或垂直的3.6.3 3.6.3 线的属性线的属性3.63.6 图元属性控制图元属性控制1 1 线宽线宽:解决方法解决方法:采用斜角连接或圆连接或斜切连接采用斜角连接或圆连接或斜切连接的方式的方式

21、 采用反走样技术采用反走样技术 采用线帽（方帽、圆帽、突方帽）采用线帽（方帽、圆帽、突方帽）方法方法3.6.3 3.6.3 线的属性线的属性3.63.6 图元属性控制图元属性控制2 2 线型线型:线型指定了线段在绘制中的形状属线型指定了线段在绘制中的形状属性，即构成线段的各个像素是否绘制的性，即构成线段的各个像素是否绘制的属性属性。实线实线虚线虚线点线点线3.6.3 3.6.3 线的属性线的属性3.63.6 图元属性控制图元属性控制填充方式填充方式:实填充实填充 图形填充图形填充 图案填充图案填充 符号填充符号填充3.6.4 3.6.4 多边形填充多边形填充属性属性3.73.7 反走样反走样

22、基本图元生成算法绘制的非水平且基本图元生成算法绘制的非水平且非垂直的直线、多边形的边或圆弧、椭非垂直的直线、多边形的边或圆弧、椭圆弧时，会产生锯齿状图形的现象，称圆弧时，会产生锯齿状图形的现象，称为走样为走样(aliasing)(aliasing)。3.73.7 反走样反走样解决走样问题的解决走样问题的3 3种方法：种方法：过取样（过取样（supersamplingsupersampling）区域取样区域取样(area sampling)(area sampling)像素移相像素移相硬件反走样硬件反走样3.73.7 反走样反走样3.7.1 3.7.1 直线段的过取样直线段的过取样3.73.7 反走样反走样1 1 加权区域取样加权区域取样3.7.2 3.7.2 区域取样区域取样3.73.7 反走样反走样2 2 区域边界的反走样区域边界的反走样3.7.2 3.7.2 区域取样区域取样3.73.7 反走样反走样 该方法需要硬件系统具有支持根据该方法需要硬件系统具有支持根据像素直径的小数部分来移动电子束的能像素直径的小数部分来移动电子束的能力力。3.7.3 3.7.3 像素移相像素移相习题习题Q Q&A A？