3.基本图形生成算法.ppt

第3讲 基本图形生成及处理算法cad. 1主要内容3.1、 光栅显示器工作原理3.3、 直线生成算法3.4、 圆弧生成算法3.5、 字符生成算法3.6、 区域填充算法3.7、 多边形裁减算法3.8、 图形的反走样3.2、 基本几何定义描述23.13.1、光栅显示器工作原理、光栅显示器工作原理显示器用于显示字符、图形（触摸显示屏还可作为输入设备）显示器用于显示字符、图形（触摸显示屏还可作为输入设备）常规光栅显示器上的图形由荧光屏的点阵组成常规光栅显示器上的图形由荧光屏的点阵组成CRT是通过电子枪发射电子束，经过聚焦系统、加速电极、偏转系统，按行列次序扫描点矩阵，是通过电子枪发射电子束，经过聚焦系统、加速电极、偏转系统，按行列次序扫描点矩阵，轰击到荧光屏的不同点阵部位，被其内表面的荧光物质吸收，在该点发光产生可见的图形轰击到荧光屏的不同点阵部位，被其内表面的荧光物质吸收，在该点发光产生可见的图形阴极射线管显示器（阴极射线管显示器（Cathode Radiative Tube））彩色彩色CRT显示器的每个扫描点（即象素）有三个荧光点（红、绿、蓝三基色），由三支电子枪显示器的每个扫描点（即象素）有三个荧光点（红、绿、蓝三基色），由三支电子枪通过控制各自电子束强度实现不同亮度的颜色。

通过控制各自电子束强度实现不同亮度的颜色若每支电子枪发出的电子束的强度为若每支电子枪发出的电子束的强度为256个等级，则显示器能同时显示个等级，则显示器能同时显示256*256*256=16M种颜种颜色，色，称为真彩色系统称为真彩色系统3若屏幕尺寸一定，水平和竖直方向上能识别的最大像素个数描述，若屏幕尺寸一定，水平和竖直方向上能识别的最大像素个数描述，如如800*600，，1024*768，，1280*1024等象素（Pixel）      每个象素都对应于每个象素都对应于Buffer中的一个存储单元，用来存储象素颜色（灰度）值中的一个存储单元，用来存储象素颜色（灰度）值的存储器，称为的存储器，称为帧缓冲存储器帧缓冲存储器，，俗称俗称显存      象素的亮度值控制电子束对荧光屏的轰击强度，象素在帧缓存寄存器中的位象素的亮度值控制电子束对荧光屏的轰击强度，象素在帧缓存寄存器中的位置编码控制电子束的偏转位置置编码控制电子束的偏转位置 分辨率（Resolution）每秒钟重绘屏幕的次数，每秒钟重绘屏幕的次数， CRT产生稳定图像所需要的最小刷新频率：产生稳定图像所需要的最小刷新频率：      =  1秒秒  /  荧光物质的持续发光时间荧光物质的持续发光时间 （（Hz））刷新频率荧光屏上画面的每一光点称为一个象素。

荧光屏上画面的每一光点称为一个象素与电视工作原理类似，与电视工作原理类似，CRT电子束从上到下、从左到右电子束从上到下、从左到右扫描进行，每扫描一遍称为扫描进行，每扫描一遍称为一帧一帧帧缓冲存储器帧缓冲存储器液晶显示器原理不同于液晶显示器原理不同于CRT，不受刷新频率影响但是液晶显示有拖尾现象，主要是，不受刷新频率影响但是液晶显示有拖尾现象，主要是因为液晶偏转延迟所致，延时越长，拖尾越重因为液晶偏转延迟所致，延时越长，拖尾越重43.23.2、基本几何定义描述、基本几何定义描述        对于一个二维对于一个二维CAD系统来说，直线、圆、圆弧、样条曲线是最常见的基本几何要素系统来说，直线、圆、圆弧、样条曲线是最常见的基本几何要素对于一个三维对于一个三维CAD系统来说，除了具备上述要素外，还需平面、圆柱面、球面、圆环面及系统来说，除了具备上述要素外，还需平面、圆柱面、球面、圆环面及样条曲面考虑到样条曲线曲面及三维几何建模将在后面章节中详细介绍，在此仅介绍直线、样条曲面考虑到样条曲线曲面及三维几何建模将在后面章节中详细介绍，在此仅介绍直线、圆、圆弧的定义描述圆、圆弧的定义描述直线的定义直线通过点直线通过点P1 (x1,y1)和和P2 ( x2,y2 ) ，直线方程可表示为：，直线方程可表示为：       二点式方程二点式方程                               参数方程参数方程 也可表示为标准的直线方程形式：也可表示为标准的直线方程形式：     Ax+By+C=0 其中：其中：A = y2-y1，，  B = -(x2-x1)，，  C = -(Ax1+By1)也可用其它的数学表达方法来定义直线。

二点式表达时也可用其它的数学表达方法来定义直线二点式表达时应注意避免分母为应注意避免分母为0，不同的表达方法之间可相互转换，，不同的表达方法之间可相互转换，以便计算机快速稳定计算以便计算机快速稳定计算通常直线的数据结构只需记录起点、终点坐标以及直线通常直线的数据结构只需记录起点、终点坐标以及直线的属性即可的属性即可class LINE{            double  x1, y1, x2, y2；；      int   r, g, b;      int   lintype;      int   mattype;      ……      void draw_line();      void cal_length();      void interpolate();      ……} 5圆的定义给定圆心（给定圆心（xc,  yc）和半径）和半径R，圆的方程表示为：，圆的方程表示为：       一般的代数方程一般的代数方程 ：：           （（x – xc)^2 + (y - yc)^2 = R^2                                     参数方程参数方程 ：：             x = xc + R cosα              y = yc + R sinα 通常圆的数据结构只记录圆心、半径及其属性通常圆的数据结构只记录圆心、半径及其属性class CIRCLE{            double  xc, yc, R；；      int   r, g, b;      int   lintype;      ……      void draw_circle();      void circumference ();……} 圆弧的定义圆弧的表示方程和圆的方程完全相同，但是圆弧圆弧的表示方程和圆的方程完全相同，但是圆弧还需要给出起点和圆弧的角度，通常逆时针方向还需要给出起点和圆弧的角度，通常逆时针方向为正的角度，顺时针方向为负角度。

为正的角度，顺时针方向为负角度通常圆弧的数据记录圆心、半径、起点、角度其属通常圆弧的数据记录圆心、半径、起点、角度其属性但为了快速捕捉端点，还可记录终点但为了快速捕捉端点，还可记录终点class ARC{    double  xc,  yc, R，，                    x1, y1, α；；      int   r, g, b;      int   lintype;      ……      void  draw_arc();      void  arc_length ();      ……} 思考：为什么直线、圆弧的表示均不记录方程？思考：为什么直线、圆弧的表示均不记录方程？（几何变换后方程改变）（几何变换后方程改变）6画直线是画直线是CAD中最常用的操作数学上的直线是没有宽度的点集，显然，光中最常用的操作数学上的直线是没有宽度的点集，显然，光栅显示器只能近地似显示直线画一条从（栅显示器只能近地似显示直线画一条从（x1, y1）到（）到（x2, y2）的直线，实）的直线，实质上是寻找最佳逼近直线的象素序列，并填入色彩数据的过程（如左图），质上是寻找最佳逼近直线的象素序列，并填入色彩数据的过程（如左图），这个过程也称为这个过程也称为直线光栅化直线光栅化，也称，也称直线扫描转换直线扫描转换。

目前常用算法有：目前常用算法有：直线直线DDA算法、中点算法、算法、中点算法、Bresenham算法等直线中每一点坐标都可由前一点坐标变化一个增量（直线中每一点坐标都可由前一点坐标变化一个增量（△△x, △△ y）而得到，即表示为递归式：）而得到，即表示为递归式：        xi+1 = xi+ △△ x，，yi+1=yi+ △△ y，并有关系：，并有关系： △△ y = k · △△ x，递归式的初值为直线的起点（，递归式的初值为直线的起点（x1, y1），考虑），考虑象素为整数，则算法过程为：象素为整数，则算法过程为：1）直线）直线DDA算法算法   （即微分算法）（即微分算法）△△△△x x＝＝＝＝ x2 x2－－－－x1x1，，，，   △△△△ y  y＝＝＝＝y2y2－－－－y1y1，，，，k k＝＝＝＝   △△△△ y/  y/ △△△△x xy yi+1 i+1 = kx= kxi+1i+1+b = k(x+b = k(xi i+1)+b = y+1)+b = yi i+k+k(x(xi  i , y, yi i)→(x)→(xi i+1+1   , y, yi i+k)+k) yi = round (yi) = (int) (yi+0.5)算法特点算法特点上述算法简单，易实现；上述算法简单，易实现；但有浮点数取整运算，不利于硬件实现，效率低；但有浮点数取整运算，不利于硬件实现，效率低；算法仅适用于算法仅适用于 k  ≤1的情形：的情形：x每增加每增加1，，y最多增加最多增加1。

当当 k  1时，必须把时，必须把x，，y互换k ≤1k 13.33.3、直线生成算法、直线生成算法7算法应用举例算法应用举例直线起点直线起点P0（（0，，0），终点），终点P1（（5，，2））DDA算法实现算法实现82）） Bresenham算法算法Bresenham算法是目前使用最广泛的直线生成算法算法是目前使用最广泛的直线生成算法         过各行各列象素中心构造一组虚拟网格线按直线从起点到终点的顺序计过各行各列象素中心构造一组虚拟网格线按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素（如下图所示）点最近的象素（如下图所示） 假设直线方程为：假设直线方程为：yi+1 = yi + k ( xi +1 – xi )，且横坐标象素为，且横坐标象素为 xi，其纵坐标为，其纵坐标为yi ，斜，斜率率 k < 1 ；；那么下一个象素的横坐标为那么下一个象素的横坐标为 xi＋＋1，而纵坐标要么为，而纵坐标要么为yi，要么递增，要么递增1为为yi＋＋1，是否增，是否增1取决于误差项取决于误差项d的值。

的值误差项误差项 d 的初值的初值 d0 ＝＝ 0，，x 坐标每增加坐标每增加 1，，d 的值相应递增直线的斜率值的值相应递增直线的斜率值 k，即，即 d＝＝d＋＋k       一旦一旦  d≥1，就把它减去，就把它减去1，这样保证，这样保证 d 在在 0、、1 之间；之间；       当当 d ≥ 0.5 时，直线与垂线时，直线与垂线 x = xi ＋＋ 1 交点最接近于当前象素交点最接近于当前象素       (xi，，yi) 的的右上方象素右上方象素 ( xi＋＋1，，yi＋＋1 )；；       而当而当 d < 0.5 时，更接近于时，更接近于右方象素右方象素 ( xi＋＋1，，yi ) 为方便计算，令为方便计算，令e ＝＝d－－0.5，，e 的初值为－的初值为－0.5，增量为，增量为 k；；       当当e ≥ 0 时，取当前象素时，取当前象素 (xi，，yi)的右上方象素的右上方象素(xi＋＋1，，yi＋＋1)；；       而当而当 e < 0 时，取时，取 ( xi，，yi )右方象素右方象素 ( xi＋＋1，，yi )9算法举例用用Bresenham方法生成两点方法生成两点P0（（0, 0）和）和P1（（5, 2）的直线段）的直线段 x      y      e0     0     -0.51     0     -0.12     1     0.33     1     -0.34     2     0.1 5     2     -0.5void Bresenhamline ( int x0, int y0, int x1, int y1, int color ){      int x, y, dx, dy；；       float k, e;       dx = x1- x0；；dy = y1- y0；；k = dy / dx；；       e = - 0.5；； x = x0；；y = y0；；       for (i=0；；i < dx；；i++)       {    drawpixel (x, y, color);             x=x+1；；e=e+k;             if (e ≥ 0)             {   y++；； e = e - 1;  }       }} 算法程序10算法改进算法改进上述上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。

可以改用整算法在计算直线斜率与误差项时用到小数与除法可以改用整数以避免除法由于算法中只用到误差项（初值数以避免除法由于算法中只用到误差项（初值 e = dy/dx - 0.5）的符号，因此）的符号，因此可作替换：可作替换： e = 2*e*dx void InterBresenhamline ( int x0, int y0, int x1,  int y1, int color ){    int x, y, dx, dy，，e;     dx = x1-x0;  dy = y1- y0;      e = 2*dy - dx ;                // e = k - 0.5         *2*dx      x = x0；； y = y0;      for ( i =0;  i < dx;  i++ )      {    drawpixel (x, y, color);            if (e ≥ 0)             {    y++;   e = e - 2*dx;                // e = e – 1   *2*dx            }            x++;  e = e+2*dy;                      // e = e + k   *2*dx      }}算法避免了除法及浮点运算，且算法避免了除法及浮点运算，且2 的整倍数可采用移位操作，便的整倍数可采用移位操作，便于硬件实现，算法速度快，精度高。

于硬件实现，算法速度快，精度高11圆也是图形系统中常用的元素我们将圆定义为所以距离中心位圆也是图形系统中常用的元素我们将圆定义为所以距离中心位置置(xc, yc) 为给定值为给定值 r 的点集圆的方程为：的点集圆的方程为：圆的定义为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）不妨设为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）不妨设函数：函数：显然有：显然有：          F（（x，，y））<  0，则（，则（x,y)位于圆边界内位于圆边界内          F（（x，，y）＝）＝ 0，则（，则（x,y)位于圆边界上位于圆边界上          F（（x，，y））>  0，则（，则（x,y)位于圆边界外位于圆边界外考虑圆的八对称性，不妨以考虑圆的八对称性，不妨以第二个八分圆第二个八分圆进行分析，其它八分圆则可通进行分析，其它八分圆则可通过镜像实现过镜像实现yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oRP P1MP2构造判别式3.43.4、、 圆弧生成算法圆弧生成算法12圆的扫描转换算法有：圆的扫描转换算法有：直接离散法直接离散法、、中点法中点法、、Bresenham算法算法等。

等圆的圆的中点算法中点算法算法思路如下：算法思路如下：根据右图，圆上的点满足判别式：根据右图，圆上的点满足判别式：P P1M P2F( x, y ) = x 2+ y 2 – R 2 = 0中点中点M：M = ( xp+1, yp-0.5 )将中点将中点M代入判别式得：代入判别式得：当当 d ＜＜0时，时，M在圆内，在圆内，P1 距离圆弧近，取距离圆弧近，取P1 ( xp+1, yp )当当 d ＞＞0时，时，M在圆外，在圆外，P2 距离圆弧近，取距离圆弧近，取P2 ( xp+1, yp-1 )若若 d < 0,  取取P2为下一象素，再下一象素的判别式为：为下一象素，再下一象素的判别式为：若若d ≥ 0, 取取P1为下一象素，再下一象素的判别式为：为下一象素，再下一象素的判别式为：第一个象素点是第一个象素点是（（0,R），），判别式判别式d的初始值为：的初始值为：增量增量13中点算法（续）为提高算法的效率，将算法中的浮点为提高算法的效率，将算法中的浮点数改写成整数，数改写成整数，用用 e = d －－ 0.25 代替代替 d，，增量不变增量不变，，取取  e0 = 1 －－ R，则算法为：，则算法为：MidpointCircle(r, color){ x=0; y=r; d=1.25-r; drawpixel(x, y,color); while(x

度、精度及可靠性，为各种图形平台提供算法支撑        原则：尽量避免除法、浮点运算，尽可能采用整数加减及移原则：尽量避免除法、浮点运算，尽可能采用整数加减及移位等运算位等运算15给定一个字节，如何来确定它代表的是给定一个字节，如何来确定它代表的是ASCII码，还是国标码的区码和位码，还是国标码的区码和位码？码？通常采用字符中冗余的最高位来标识通常采用字符中冗余的最高位来标识：最高位为：最高位为0时，表示时，表示ASCII码；码；最高位为最高位为1时，表示汉字编码的区码（高位字节）或位码（低位字节）时，表示汉字编码的区码（高位字节）或位码（低位字节）基本概念基本概念ASCII码码国标码国标码ASCII码与国码与国标码的分辨标码的分辨3.5、 字符生成算法字符是指字母、数字、汉字、标点等符号为了在显示器等输出设备上输出字符，必须要有每字符是指字母、数字、汉字、标点等符号为了在显示器等输出设备上输出字符，必须要有每个字符的图形信息，这些信息保存在系统的字库中字符的图形表示方法有两种：个字符的图形信息，这些信息保存在系统的字库中字符的图形表示方法有两种：点阵点阵表示和表示和矢量矢量表示。

表示计算机中，字符由一个数字编码唯一标识，对于一个字符来说，它所对应的编码是由它所属的计算机中，字符由一个数字编码唯一标识，对于一个字符来说，它所对应的编码是由它所属的字符集决定字符集决定目前，国际上普遍采用的字符编码是目前，国际上普遍采用的字符编码是ASCII码用七位二进制数进行编码，共能表示码用七位二进制数进行编码，共能表示128个字个字符，其中编码符，其中编码 0～～31表示控制字符（不可显示），编码表示控制字符（不可显示），编码32～～127表示英文字母、数字、标点符表示英文字母、数字、标点符号等可显示字符一个字符的号等可显示字符一个字符的ASCII码用一个字节（码用一个字节（8位）表示，其位）表示，其最高位不用最高位不用或者作为奇偶或者作为奇偶校验位我国除采用我国除采用ASCII码外，还制定了汉字编码国家标准字符集（国标码），共收录常用汉字码外，还制定了汉字编码国家标准字符集（国标码），共收录常用汉字6763个，图形符号个，图形符号682个所有汉字和图形符号组成一个个所有汉字和图形符号组成一个94×94的矩阵，在此方阵中，每一的矩阵，在此方阵中，每一行称为行称为“区区”，用区码来标识；每一列称为，用区码来标识；每一列称为“位位”，用位码来标识，一个符号由一个区码和，用位码来标识，一个符号由一个区码和一个位码共同标识。

区码和位码分别需要一个位码共同标识区码和位码分别需要7个二进制位，同样，为了方便，各采用一个字节个二进制位，同样，为了方便，各采用一个字节表示所以在计算机中，汉字（符号）国标码占用两个字节所以在计算机中，汉字（符号）国标码占用两个字节16点阵字符点阵字符 在字符的点阵表示中，每个字符由一个位图（字符掩模）来表示，对于西文字符的掩模矩在字符的点阵表示中，每个字符由一个位图（字符掩模）来表示，对于西文字符的掩模矩阵一般不小于阵一般不小于5×7，而定义汉字的掩模矩阵一般不小于，而定义汉字的掩模矩阵一般不小于16×16一个字符的点阵数越多，字一个字符的点阵数越多，字符越清晰、美观符越清晰、美观 点阵字符的存储点阵字符的存储 点阵字符是由位图表示，保存字符就是保存位图即点阵字符的存储就是按行或按列进点阵字符是由位图表示，保存字符就是保存位图即点阵字符的存储就是按行或按列进行编码如上图行编码如上图(a)，每行右边的二进制或十六制的代码就是对该行的编码每行右边的二进制或十六制的代码就是对该行的编码 点阵字符的显示点阵字符的显示 从给定的字符编码到在屏幕上将它显示出来要经历两个步骤：从给定的字符编码到在屏幕上将它显示出来要经历两个步骤：　　　　1．从字库中将它的位置找到。

．从字库中将它的位置找到　　　　2．将该位置上的位图读到二维数组中进行显示，见上图．将该位置上的位图读到二维数组中进行显示，见上图(b)17矢量字符矢量字符 矢量字符由于其占空间少、美观、变换方便等优点，在字符的矢量表示方法中，矢量字符由于其占空间少、美观、变换方便等优点，在字符的矢量表示方法中，保存的是字符的笔画信息而不是整个位图在排版、保存的是字符的笔画信息而不是整个位图在排版、CAD软件应用广泛软件应用广泛矢量字符处于矢量字符处于局部坐标系局部坐标系中中 ，它由构成它，它由构成它的笔画组成，而每一笔画又由其两端点坐标的笔画组成，而每一笔画又由其两端点坐标和端点间是否连线的标志确定例如，汉字和端点间是否连线的标志确定例如，汉字“士士”有三画，六个端点，可以按图有三画，六个端点，可以按图(b)的的结构保存该汉字结构保存该汉字  点阵字符是图像变换，不光滑；矢量字符是几何变换，很光滑点阵字符是图像变换，不光滑；矢量字符是几何变换，很光滑矢量字符存储矢量字符存储是对笔画端点坐标进行存储，比点阵字符占用空间少矢量字符每种字体只需是对笔画端点坐标进行存储，比点阵字符占用空间少矢量字符每种字体只需保存一套字符，点阵需多套。

如图保存一套字符，点阵需多套如图(a)中的中的“士士”，表示一个端点，表示一个端点p(x,y)需要需要6+6+1=13位（可位（可表示局部坐标系范围：表示局部坐标系范围：64×64，另，另1位表示连线标志），六个端点需位表示连线标志），六个端点需6×13 / 8约为约为10个字节个字节而保存保存64×64的点阵字符，则需要的点阵字符，则需要64×64/8 = 512字节字节 今天，矢量字符已不仅用直线段来表示，而用更复杂的曲线段，显示更美观今天，矢量字符已不仅用直线段来表示，而用更复杂的曲线段，显示更美观18光栅显示的重要特点是能进行面着色，区域填充光栅显示的重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案区就是在一个闭合区域内填充某种颜色或图案区域填充一般分两类：域填充一般分两类：多边形填充多边形填充和和种子填充种子填充1) 1) 多边形填充多边形填充算法算法给定一顶点序列给定一顶点序列(Pi ，，i=0，，1，，…，，n )，依，依次连线构成一封闭多边形次连线构成一封闭多边形多边形内点判别 ——射线法•若射线与多边形边界的交点个数为奇数时，则该点为若射线与多边形边界的交点个数为奇数时，则该点为内点内点；；反之，交点个数为偶数时，则该点为反之，交点个数为偶数时，则该点为外点外点。

•当扫描线过多边形顶点时，则交点为当扫描线过多边形顶点时，则交点为奇异点奇异点奇异点为局奇异点为局部极值点应看成两点，若为非极值点应看成一点部极值点应看成两点，若为非极值点应看成一点 多边形内点判别 ——夹角法夹角和为夹角和为0，点，点p为为外点外点；夹角和为；夹角和为360°，点，点p为为内点内点CABDEPABCDEP3.6、 区域填充算法19这类算法建立在多边形边边界的矢量形式数据之上，这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色可用于程序填色，也可用交互填色该算法基于几何求交算法，步骤如下：该算法基于几何求交算法，步骤如下：•输入多边形顶点坐标；输入多边形顶点坐标；•求多边形顶点中最大和最小求多边形顶点中最大和最小y坐标，以确定范围；坐标，以确定范围；•计算每条扫描线起止点（交点），并扫描填充，直至所有计算每条扫描线起止点（交点），并扫描填充，直至所有扫描线处理完毕扫描线处理完毕本算法改进的关键所在：本算法改进的关键所在：•如何快速求扫描线与多边形交点；如何快速求扫描线与多边形交点；•扫描线填充利用扫描线填充利用画水平直线快速画法画水平直线快速画法(为什么不用斜线？为什么不用斜线？)；；•应该利用扫描线与多边形交点的连贯性加速求交算法（多应该利用扫描线与多边形交点的连贯性加速求交算法（多边形与扫描线相交，则与下一条扫描线很可能相交，交点边形与扫描线相交，则与下一条扫描线很可能相交，交点可直接计算）可直接计算）扫描线填充算法思路扫描线填充算法思路(Scan-Line Filling)算法步骤——边相关扫描线填充算法由于相邻扫描线上的交点是与多边形的边线相关的。

由于相邻扫描线上的交点是与多边形的边线相关的对同一条边，前一条扫描线对同一条边，前一条扫描线yi与该边的交点为与该边的交点为xi，而，而后一条扫描线后一条扫描线yi+1=yi+1与该边的交点则为与该边的交点则为xi+1=xi+1/m，利用相关性可省去大量求交运算，利用相关性可省去大量求交运算（算法详见图形学教材） 算法改进：20这类算法建立在多边形边界的图象形式数据之上，这类算法建立在多边形边界的图象形式数据之上，并需提供多边形界内一点的坐标，一般只能用于人并需提供多边形界内一点的坐标，一般只能用于人机交互填色，而难以用于程序填色机交互填色，而难以用于程序填色从多边形从多边形内部点内部点出发，沿出发，沿四连通方向四连通方向（或（或八连通方向八连通方向）扩散搜索区域内所）扩散搜索区域内所有待填充的象素点，适用于交互绘图有待填充的象素点，适用于交互绘图①①给定多边形边界颜色及内部填充颜色；给定多边形边界颜色及内部填充颜色；②②从内部点从内部点 ( x,  y ) 开始，检测该点与边界和填开始，检测该点与边界和填充色是否相同，均不相同则填充该点；充色是否相同，均不相同则填充该点；③③检测相邻点与边界和填充色是否相同，均不检测相邻点与边界和填充色是否相同，均不相同则填充该点；相同则填充该点；④④重复第重复第③③步直至所有象素点被填充。

步直至所有象素点被填充算法步骤：算法思想：算法特点：用用4连通填充算法的填充结果连通填充算法的填充结果用用8连通填充算法的填充结果连通填充算法的填充结果直接基于象素，用递归算法，不必求交但递归太多，存储不够，直接基于象素，用递归算法，不必求交但递归太多，存储不够，易造成堆栈溢出易造成堆栈溢出可用一个大的矩阵记录象素填充的状态来避免递归算法）（可用一个大的矩阵记录象素填充的状态来避免递归算法）2 2）种子填色算法（）种子填色算法（Seed FillingSeed Filling））213 3）图案填充算法（参考））图案填充算法（参考）实际应用中，有时需要用图案来填充平面区域，只需实际应用中，有时需要用图案来填充平面区域，只需将种子填充算法中写象素的那部分代码修改将种子填充算法中写象素的那部分代码修改 种种子点颜色改写为定义图案对应点颜色查表即可子点颜色改写为定义图案对应点颜色查表即可））－图案定位方法 相对定位法：相对定位法：把图案原点与填充区域边界或内部的某点对齐把图案原点与填充区域边界或内部的某点对齐当被填充的多边形移动时，图案也跟着移当被填充的多边形移动时，图案也跟着移动，看起来比较自然。

对于多边形，可取边界上最左边的顶点，对于圆和椭圆这样具有光动，看起来比较自然对于多边形，可取边界上最左边的顶点，对于圆和椭圆这样具有光滑边界的区域，最好取区域内部某一点，如取中心与图案原点对齐滑边界的区域，最好取区域内部某一点，如取中心与图案原点对齐绝对定位法：绝对定位法：把图案原点与屏幕原点对齐把图案原点与屏幕原点对齐将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住这种方法比较的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住这种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果但它有一个潜在的毛病，简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果但它有一个潜在的毛病，即当区域移动时，图案不会跟着移动其效果是区域内的图案变了即当区域移动时，图案不会跟着移动其效果是区域内的图案变了定义填充图案是一个定义填充图案是一个M×N的位图，用数组存放的位图，用数组存放M、、N常比需要填充区域尺寸小得多（常比需要填充区域尺寸小得多（8×8、、16×16等），图案等），图案设计成周期性的，使之重复使用构成任意尺寸图案。

设计成周期性的，使之重复使用构成任意尺寸图案 算法思路：算法思路： 例：砖墙图案22包容盒定义包容盒定义 Bounding Box在计算机图形学、在计算机图形学、CAD、、CAE中经常遇到相交（碰撞）测试如鼠标拾取，视中经常遇到相交（碰撞）测试如鼠标拾取，视窗裁剪、曲面求交、光线跟踪、布尔运算、装配干涉校验、动画漫游、运动碰窗裁剪、曲面求交、光线跟踪、布尔运算、装配干涉校验、动画漫游、运动碰撞、机器人与机床刀具的轨迹规划等尤其对较大规模数据的模型而言，处理撞、机器人与机床刀具的轨迹规划等尤其对较大规模数据的模型而言，处理相交（碰撞）测试的速度对系统效率影响很大相交（碰撞）测试的速度对系统效率影响很大为加速测试计算速度，通常采用包容盒方法为加速测试计算速度，通常采用包容盒方法1）相交（碰撞）测试算法）相交（碰撞）测试算法轴对齐包容盒（矩形盒）：：通常通常称称AABB，表面平行于坐标面表面平行于坐标面有向包容盒：简称OBB，即任意方向的，即任意方向的AABB，往往由一个中心，三个单位矢，往往由一个中心，三个单位矢量和三个半边长定义量和三个半边长定义AABBOBBn3n1n2n4s1d1maxd1minK－DOP球体包容盒：即用球体将形体包围，由一个中心盒一个半径定义。

即用球体将形体包围，由一个中心盒一个半径定义3.7、 多边形裁减算法23直线的包围盒，直线的包围盒，计算直接利用其特征点计算直接利用其特征点——起始点和终点就可得到起始点和终点就可得到矩形的包围盒矩形的包围盒是其本身，是其本身，圆的包围盒圆的包围盒是该圆的边界矩形是该圆的边界矩形圆弧的包围盒圆弧的包围盒，主要是由圆弧的起始点和终止点，以及与通过圆心的主要是由圆弧的起始点和终止点，以及与通过圆心的4个坐个坐标轴相交的交点标轴相交的交点自由曲线的包容盒，自由曲线的包容盒，可根据离散的小直线段的起始点和终止点比较后获得，可根据离散的小直线段的起始点和终止点比较后获得，若精确求解并不经济，因图形显示采用离散多边形，且图形变换频繁若精确求解并不经济，因图形显示采用离散多边形，且图形变换频繁复杂组合图形的包容盒，复杂组合图形的包容盒，可以在简单图形的包容盒基础上进行比较得到可以在简单图形的包容盒基础上进行比较得到包容盒计算包容盒计算 AABB：直接比较所有多面体（前面的离散多面体）顶点坐标即可得：直接比较所有多面体（前面的离散多面体）顶点坐标即可得球体包容盒：球体包容盒：计算麻烦较为简单的方法是先计算计算麻烦。

较为简单的方法是先计算AABB，再计算，再计算AABB的的中心，以此为球心，球心到最远顶点的距离即为半径其它更好更优的算法中心，以此为球心，球心到最远顶点的距离即为半径其它更好更优的算法可查资料可查资料显然，最远距离两点最为球的直径是最优解，关键是快速显然，最远距离两点最为球的直径是最优解，关键是快速OBB：计算方法较多，较繁琐方法之一是：：计算方法较多，较繁琐方法之一是：1）计算凸包；）计算凸包；2）计算凸包）计算凸包质心；质心；3）计算协方差矩阵的特征向量；）计算协方差矩阵的特征向量；4)  其其特征向量即为特征向量即为OBB三个方向三个方向；；5））向三个方向投影向三个方向投影即可求出半长值即可求出半长值AABB、圆球包容盒比较粗糙，各有优势圆球包容盒比较粗糙，各有优势K－－DOP 比比 AABB更紧致，更紧致，OBB 则较则较 k－－DOP 更优，选用何种包容盒视复杂度而定更优，选用何种包容盒视复杂度而定24相交测试相交测试 1）尽可能用最简单算法排除或确定相交情形，如采用包容盒排除；）尽可能用最简单算法排除或确定相交情形，如采用包容盒排除；2）充分利用前一次计算结果，尽量避免复杂计算（如）充分利用前一次计算结果，尽量避免复杂计算（如sin，开方等）；，开方等）；3）如果使用了多种测试，可以尝试改变内部顺序，或许会有意外收效；）如果使用了多种测试，可以尝试改变内部顺序，或许会有意外收效；4）尽量降低维数，使问题简化，确保计算鲁棒性。

尽量降低维数，使问题简化，确保计算鲁棒性算法实现的基本原则：求交计算是求交计算是CG&CAD最常用算法，计算量大，其准确性与效率直接影响系统最常用算法，计算量大，其准确性与效率直接影响系统的可靠性与实用性为加速测试过程，减小计算量，算法应注意：的可靠性与实用性为加速测试过程，减小计算量，算法应注意：注意：在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，注意：在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，难以绝对相等，相应地，求交运算中要引进容差难以绝对相等，相应地，求交运算中要引进容差      i）当两个点的坐标值充分接近时，即其距离充分近时，就被认为是）当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的重合的点点，一般取，一般取∆ =10-6或更小的数或更小的数      ii）当两条直线的夹角）当两条直线的夹角 接近接近0度（一般取度（一般取∆  =10-6或更小）时，就被认为或更小）时，就被认为是是两条平行线两条平行线      iii）同样，）同样，共线、共面、平行面共线、共面、平行面等的判断也是近似的等的判断也是近似的252）多边形裁剪算法）多边形裁剪算法 确定图形中哪些部分落在显示区之内确定图形中哪些部分落在显示区之内,以便显示落在显以便显示落在显示区内的那部分图形。

这个选择过程称为示区内的那部分图形这个选择过程称为裁剪裁剪只有窗口内的物体才能显示，窗口之外的物体都是不可见的口内的物体才能显示，窗口之外的物体都是不可见的Sutherland-Hodgeman 多边形裁剪算法多边形裁剪算法I.每次用窗口的一条边界每次用窗口的一条边界(包括延长线包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列点和窗口顶点，从而得到一个新的多边形顶点序列II.然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列形顶点序列III.依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形，如下图所示。

的裁剪好了的多边形，如下图所示1)(2)(3)(4)26新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：边界线把平面分成两个部分：边界内侧和边界外侧边界内侧和边界外侧如下图所示，依序考虑多边形的各条边假设当前处理的多边形的边为如下图所示，依序考虑多边形的各条边假设当前处理的多边形的边为SP(箭头表示顺箭头表示顺序关系，序关系，S为前一点，为前一点，P为当前点为当前点)，边，边SP与裁剪线的位置关系只有下面四种情况：与裁剪线的位置关系只有下面四种情况：　　　　1、、S在外侧，在外侧，P在内侧则交点在内侧则交点Q、当前点、当前点P保存到新多边形中保存到新多边形中　　　　2、、S、、P均在内侧则当前点均在内侧则当前点P保存到新多边形中保存到新多边形中　　　　3、、S在内侧，在内侧，P在外侧则交点在外侧则交点Q保存到新多边形中保存到新多边形中　　　　4、、S、、P均在外侧则没有点被保存到新多边形中均在外侧则没有点被保存到新多边形中算法思想(续) ：27上述算法中点在边界内侧的判断方法：上述算法中点在边界内侧的判断方法： 为了判断为了判断pi点是否在边界内侧，可用点是否在边界内侧，可用坐标比较法坐标比较法和和向量叉积符号判别法向量叉积符号判别法。

　　　　1）坐标比较法：将点的某个方向分量与边界进行比较例如，判断某点）坐标比较法：将点的某个方向分量与边界进行比较例如，判断某点是否在是否在下边界内侧下边界内侧,用条件判别式：用条件判别式： if ( p[i][1] >= ymin ) 即可对其它边界也即可对其它边界也一样      2）向量叉积法）向量叉积法  ：为简单计，测试点表示为：为简单计，测试点表示为P点假设窗口边界方向为顺时针，如图中所示，对于其中假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点任一边界向量，从向量起点A向终点向终点B看过去，如果看过去，如果被测试点被测试点P在该边界线右边在该边界线右边(即内侧即内侧)，，AB×AP的方向的方向与与X-Y平面垂直并指向屏幕里面，即右手坐标系中平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向轴的负方向  　反过来，如果　反过来，如果P在该边界线的左边在该边界线的左边(即外侧即外侧)，这时，这时AB×AP的方向与的方向与X-Y平面垂直并指平面垂直并指向屏幕外面，即右手坐标系中向屏幕外面，即右手坐标系中Z轴的正方向轴的正方向        Sutherland－－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以多边形裁剪算法具有一般性，被裁剪多边形可以是任意多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。

是任意多边形，裁剪窗口不局限于矩形，可以是任意凸多边形      上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序剪时的被裁剪多边形，即可得到完整的多边形裁剪程序 算法特点 ：283）剖面线算法）剖面线算法 （任意多边形裁减）（任意多边形裁减）剖面线是一组等距的平行线，用填充算法速度慢，直接多边形裁减更快，算法步剖面线是一组等距的平行线，用填充算法速度慢，直接多边形裁减更快，算法步骤：骤： i) 按多边形的初始条件及剖面线的角度和间距，计算剖面线的范围和数量；按多边形的初始条件及剖面线的角度和间距，计算剖面线的范围和数量；ii) 求剖面线与轮廓边的相交位置；求剖面线与轮廓边的相交位置；iii）对剖面线上的交点进行排序，并按奇偶规则绘制有效剖面线段对剖面线上的交点进行排序，并按奇偶规则绘制有效剖面线段 简化技巧：简化技巧：1) 跳过顶点处交点判断，避免奇异性判断跳过顶点处交点判断，避免奇异性判断                     2) 图形变换使剖面线成为水平线（或铅垂线），简化加图形变换使剖面线成为水平线（或铅垂线），简化加                         速求交计算。

速求交计算29在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状原因是图形信号是连在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素这种用离散量表示连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素这种用离散量表示连续量引起的失真现象称之为走样续量引起的失真现象称之为走样(aliasing)；用于减少或消除这种效果的技术称为反走样；用于减少或消除这种效果的技术称为反走样(antialiasing)光栅图形的走样现象：光栅图形的走样现象：       阶梯状边界阶梯状边界，如图，如图(a)所示，画出的直线边界实际上是阶梯状；所示，画出的直线边界实际上是阶梯状；       图形细节失真图形细节失真（比象素更窄的细节变宽，如图（比象素更窄的细节变宽，如图(b) ）；）；       狭小图形遗失狭小图形遗失（（ 如图如图(c)，在动画序列中将时隐时现，产生闪烁）在动画序列中将时隐时现，产生闪烁）因为计算机屏幕是不连续的离散象素组成，每个象素覆盖一定面积，因为计算机屏幕是不连续的离散象素组成，每个象素覆盖一定面积，而每个而每个象素只能显示一种颜色象素只能显示一种颜色。

也就是说，该象素只能显示该覆盖区域某一点处的也就是说，该象素只能显示该覆盖区域某一点处的颜色，不可能反映整个区域颜色，于是出现失真或图形丢失颜色，不可能反映整个区域颜色，于是出现失真或图形丢失常用的反走样方法主要有：常用的反走样方法主要有：提高分辨率提高分辨率、、区域采样区域采样、加权区域采样、加权区域采样等等 图图(a)图图(b)图图(c)反走样基本概念 ：3.8、 图形的反走样301）提高分辨率的反走样方法）提高分辨率的反走样方法方法简单，代价大如显示器水平与竖直分辩率提高方法简单，代价大如显示器水平与竖直分辩率提高1倍，则显示器点距减倍，则显示器点距减1倍，帧缓存容量则增加到原来的倍，帧缓存容量则增加到原来的4倍，扫描转换同样大小的图元却要花倍，扫描转换同样大小的图元却要花4倍时间2）区域采样）区域采样反走样方法反走样方法1）将直线段看作具有一定宽度的狭长矩形；）将直线段看作具有一定宽度的狭长矩形；2）直线段矩形与某象素正方形有交（或覆盖）时，求相交（或覆盖）区域面）直线段矩形与某象素正方形有交（或覆盖）时，求相交（或覆盖）区域面积；积；3）根据相交区域面积，确定该象素的亮度值）根据相交区域面积，确定该象素的亮度值l直线段对一个像素亮度的贡献与相交区域面积成正比；直线段对一个像素亮度的贡献与相交区域面积成正比；l当直线段和某个像素不相交时，它对该像素的亮度无影响；当直线段和某个像素不相交时，它对该像素的亮度无影响；l相同面积的相交区域对像素亮度贡献相同，与相交区域在像素内位置无关。

相同面积的相交区域对像素亮度贡献相同，与相交区域在像素内位置无关——区域采样方法特点：关键：如何快速计算这个面积？关键：如何快速计算这个面积？方法方法 2：面积离散近似计算，将象素细化子分为多象：面积离散近似计算，将象素细化子分为多象               素，子象素相交（或覆盖）的数目即为面积素，子象素相交（或覆盖）的数目即为面积方法方法 1：多边形精确求相交区域面积，效率低；：多边形精确求相交区域面积，效率低；31思考题：1、了解图形显示器的工作原理、了解图形显示器的工作原理2、理解直线、圆弧的扫描转换算法原理、理解直线、圆弧的扫描转换算法原理3、了解包容盒基本概念及算法思路、了解包容盒基本概念及算法思路4、了解区域填充、多边形裁减算法原理、了解区域填充、多边形裁减算法原理5、了解图形反走样算法原理、了解图形反走样算法原理上机练习：1、编程实现、编程实现任意斜率任意斜率直线扫描生成算法直线扫描生成算法2、编程实现、编程实现360度圆度圆的扫描生成算法的扫描生成算法3、、编程实现扫描线区域填充算法编程实现扫描线区域填充算法4、编程实现多边形裁减算法、编程实现多边形裁减算法32。