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

.,1,甘朝华,.,2,第三章基本图元的生成,3.1线段的生成3.2圆的生成3.3区域填充3.4字符的生成3.5其他曲线3.6图元属性控制3.7反走样,.,3,基本图元,复杂图形,组合、变换,基本图元的生成算法研究是计算机图形学的基本问题之一。基本的二维图元有点、线段、圆、椭圆、多边形和字符串等。曲线及一些其他的复杂图形均可用线段或多边形拟合得到。,光栅扫描转换,.,4,理解所有算法过程的思维主线：（1）该问题在数学或几何上的意义是什么，相应的数学计算公式是什么；（2）在光栅显示器上每一个像素点都占据一定的空间；（3）生成某种图形的算法可能有多种，可以根据使用场合不同，用某些指标来衡量算法的效能。,.,5,3.1线段的生成,数学基础：设线段的2个端点为（xs,ys）和（xe,ye），直线的斜率截距方程为：y=mx+b（3.1）,.,6,3.1线段的生成,数字微分分析法（digitaldifferentialanalyzer，简称DDA）是一种线段扫描转换算法。,3.1.1DDA画线算法,.,7,在图形生成算法中由于几何图形在空间位置上具有连贯性，成为多种图形生成算法的基本思想。基于这种思想的图形绘制算法中所需要解决的问题就是如何确定后一个像素点。（中点画线、Bresenham画线、中点画圆、Bresenham画圆）。,3.1线段的生成,3.1.2中点画线算法,.,8,几何图形在空间位置上具有连贯性：（1）根据图形的几何方程式构造判断条件（即判别式），根据判断条件的值与0之间的关系可以确定下一个图形取值点的坐标；（2）根据坐标增量规律计算判别条件之间的递推关系，并确定在起点坐标处的初始判别条件值；（3）观察判别条件中有无可能进行一些调整来减少运算的复杂程度。,3.1线段的生成,3.1.2中点画线算法,.,9,3.1线段的生成,3.1.2中点画线算法,.,10,3.1线段的生成,处理方法分析优化计算过程程序实现,3.1.2中点画线算法,.,11,3.1线段的生成,算法思想：假定线段位于第一象限（m0，1），其它象限雷同。,3.1.3Bresenham画线算法,.,12,3.1线段的生成,算法思想：,3.1.3Bresenham画线算法,.,13,3.1线段的生成,两头并进算法、双步算法、N步画线算法利用并行计算机进行并行处理也是提高画线速度的一种方式。通过某种分割方法将线段分解成若干部分，并分配到多个处理器上分别进行线段像素位置计算。,3.1.4并行画线算法,.,14,3.2圆的生成,圆是一种常用图元，由于其具有8子象限对称性，因此在下面的讨论中只要生成其某一个子象限的圆弧，就可根据其对称性画出整个圆。,.,15,3.2圆的生成,直角坐标法极坐标法圆的8对称性,3.2.1圆的特性,.,16,3.2圆的生成,中点画圆算法与中点画线算法类似，只是构造判别式有所不同。,3.2.2中点画圆算法,.,17,3.2圆的生成,3.2.3Bresenham画圆算法,.,18,3.3区域填充,填充区域（fillarea）:由一定的边界围成的一个区间，其内部用某种颜色或图案进行填充。填充区域的边界可有多种形式，如圆形、折线、不规则曲线等，但规定在计算机图形学中只用多边形来表示填充区域。,.,19,3.3区域填充,凸（convex）多边形凹（concave）多边形内角,3.3.1多边形分类与识别,.,20,3.3区域填充,1.识别凹多边形,3.3.1多边形分类与识别,.,21,3.3区域填充,2.分割凹多边形向量法（vectormethod）旋转法（rotationalmethod）,3.3.1多边形分类与识别,.,22,3.3区域填充,多边形有两种表示方法：顶点表示点阵表示,3.3.2扫描线填色算法,.,23,3.3区域填充,区域填充的过程可以分为两步：（1）确定哪些像素属于区域内部，哪些属于区域外部；（2）对属于区域内部的像素，按所要求的填充色或图案来填充对应的像素。,3.3.2扫描线填色算法,.,24,3.3区域填充,填充算法分为两大类：（1）扫描线填充算法（scan-linefilling）（2）种子填充算法（seedfilling）,3.3.2扫描线填色算法,.,25,3.3区域填充,1.扫描交点奇偶数判断法,3.3.2扫描线填色算法,.,26,3.3区域填充,2.改进的扫描线填充算法顶点计数问题处理扫描线与相交边求交点减少求交计算量-活性边表,3.3.2扫描线填色算法,.,27,3.3区域填充,2.改进的扫描线填充算法,3.3.2扫描线填色算法,.,28,3.3区域填充,3.3.3种子填色算法,.,29,3.3区域填充,1.堆栈式种子像素填充法,3.3.3种子填色算法,.,30,3.3区域填充,2.四邻法种子填充算法,3.3.3种子填色算法,.,31,3.3区域填充,完整的OpenGL多边形是用glBegin、glEnd之间所描述的顶点集合来描述，多边形的形状由glBegin函数中参数的6种不同的符号常量来决定。1.多边形形状描述常量2.像素阵列函数,3.3.4OpenGL多边形区域填充函数、像素阵列函数,.,32,3.3区域填充,1.多边形形状描述常量,3.3.4OpenGL多边形区域填充函数、像素阵列函数,.,33,3.3区域填充,2.像素阵列函数像素阵列是多边形填充的一种形式，它是用一个图像阵列重复填充一个多边形的内部。两类：由彩色像素构成的阵列称为一个像素图（pixmap）;阵列每个像素的值为0或1的像素阵列称为位图（bitmap），其颜色构成只有黑、白两种。,3.3.4OpenGL多边形区域填充函数、像素阵列函数,.,34,3.4字符的生成,字符是图形中的主要组成部分，主要用来作为图形表达意义的补充形式。,.,35,3.4字符的生成,在点阵字库中，每个字符都被定义成字符掩膜的矩阵。,3.4.1点阵式字符,.,36,3.4字符的生成,矢量字符记录字符的笔画信息而不是整个位图，具有存储空间小、不变形、美观、变换方便等优点。对于字符的旋转、缩放等变换，点阵字符的变换需要对表示字符位图中的每一像素进行；而矢量字符的变换只要对其笔画端点进行变换就可以了。,3.4.2矢量字符,.,37,3.4字符的生成,矢量轮廓字符采用直线、二次三次Bezier曲线及提示（Hint）技术描述字型。,3.4.2矢量字符,.,38,3.4字符的生成,OpenGL基本库仅提供了显示单个字符和文字串的基本支持。,3.4.3OpenGL字符函数,.,39,3.5其他曲线,许多曲线函数在对象建模、动画轨迹的描述、数据和函数的图形化及其他图形应用中均是重要的图元。常见曲线有圆锥曲线、三角和指数函数、概率分布、通用多项式和样条函数。,.,40,3.6图元属性控制,任何影响图元显示方式的参数都可称为图元属性控制参数，图元的类型不同其控制参数类型也有所不同。一般的属性控制参数包括颜色、大小、线型、填充方式、字体、可见性、可检测性等。,.,41,3.6图元属性控制,3.6.1颜色,.,42,3.6图元属性控制,点的属性一般涉及颜色和大小2个属性，这些属性由系统的状态变量的当前值决定。,3.6.2点的属性,.,43,3.6图元属性控制,直线的基本显示属性包括颜色、线宽、线型。其颜色属性仍由系统状态表中当前颜色值决定，线宽和线型需要进行其他处理。,3.6.3线的属性,.,44,3.6图元属性控制,1线宽:标准的直线绘制宽度为1个像素，其他线宽是标准线宽的整数倍。在光栅实现中，通过沿相邻水平线路径（或相邻垂直线路径）绘制额外的像素而得到。,3.6.3线的属性,.,45,3.6图元属性控制,1线宽:缺点:2个线段在交点处有缺口线的粗细不一样线段的始末端总是水平或垂直的,3.6.3线的属性,.,46,3.6图元属性控制,1线宽:解决方法:采用斜角连接或圆连接或斜切连接的方式采用反走样技术采用线帽（方帽、圆帽、突方帽）方法,3.6.3线的属性,.,47,3.6图元属性控制,2线型:线型指定了线段在绘制中的形状属性，即构成线段的各个像素是否绘制的属性。实线虚线点线,3.6.3线的属性,.,48,3.6图元属性控制,填充方式:实填充图形填充图案填充符号填充,3.6.4多边形填充属性,.,49,3.7反走样,基本图元生成算法绘制的非水平且非垂直的直线、多边形的边或圆弧、椭圆弧时，会产生锯齿状图形的现象，称为走样(aliasing)。,.,50,3.7反走样,解决走样问题的3种方法：过取样（supersampling