1、图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。图形显示前需要：扫描转换+裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；直线的扫描转换直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线
2、法Bresenham算法。dxdyxxyym1212设直线起点为（x1,y1），终点（x2,y2），则斜率m为)(,;21yroundxbmxystepxxxxxx令这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。计算yi+1=mxi+1+b =mxi+b+kx =yi+mx 当x=1;yi+1=yi+m 即：当x每递增1，y递增m(即直线斜率)；注意上述分析的算法仅适用于m 1的情形。在这种情况下，x每增加1,y最多增加1。当 m 1时，必须把x，
3、y地位互换1a1b2b2a3a3b4b4a(x1,y1)(x2,y2)直线从（x1，y1）到（x2，y2）的方向不同，分为8个极限。方向在第1a象限内的直线，取增量Dx=1，Dy=m；在1b象限内的，取增量Dy=1，Dx=1/m。表.1研究表.1的数据，可以得到如下规律：1、当|dx|dy|时|Dx|=1，|Dy|=m否则|Dx|=1/m，|Dy|=12、Dx，Dy的符号与dx，dy的符号相同依据上述规律可以生成直线，每生成一条直线做两次除法，画线中的每点做两次加法，所以DDA算法生成直线的速度还是很快的。void DDALine(int x0,int y0,int x1,int y1,int
4、 color)int x；float dx,dy,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;xx1,x+)drawpixel(x,int(y+0.5),color);y=y+k;0 1 2 3 4 5321Line:P0(0,0)-P1(5,2)缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。P=(xp,yp)QP2P1点在直线下方点在直线上方点在直线上面0,0,0,yxFyxFyxFP=(xp,yp)QP2P1P=(xp,yp)QP2P1P=(xp,yp)QP2P1P=(xp,yp)QP2P10 1 2
5、3 4 5321bmxy本算法是1122dxdyxxyymxmyb121211,此处讨论先将直线方向限于1a象限，当11iixx而y的相应增加值应当小于1。为了光栅化，只能选择图2.2中两种位置之一1iyyxiXi+1yid1d2yi+1图2.2yi+1的位置可以选择yi+1=yi或者yi+1=yi+1，选择的原则是看精确值y与yi和yi+1的距离d1和d2的大小而定。计算公式为bxmyi)1(iyyd1yydi12(2.1)(2.2)(2.3)如果d1-d20，则yi+1=yi+1，否则yi+1=yi。关键是简便的求出d1-d2的符号。将2.1，2.2，2.3代入d1-d2得122)1(21
6、2221byxdxdyyyddiii用dx乘等式两边，同时令pi=(d1-d2)dx得dxbdydxydyxpiii)12(222在1a象限内，dx总大于0，所以pi可以判断d1-d2的符号。Pi+1为dxbdydxyyydyxpiiiii)12(2)222(2111dxbdydxyyydyxiiii)12(2)222()1(21dxyydypiii)(221求误差的初值p1，可将x1，y1代入式2.4中的xi，yi，得到dxdyp 21（2.4）(2.5)第1a象限内的直线Bresenham算法如下：1、画点（x1，y1），dx=x2-x1，dy=y2-y1，误差初值 p1=2dy-dx，i
7、=12、直线的下一点位置xi+1=xi+1，如果pi0，则yi+1=yi+1，否则yi+1=yi3、画点（xi+1，yi+1）4、求下一个误差pi+1，如果pi0，则pi+1=pi+2dy-2dx，否则pi+1=pi+2dy5、i=i+1如果idx+1，则转步骤2，否则结束Bresenham优点：1、不必计算直线斜率，所以不做除法2、不用浮点数，只用整数3、只做整数加减运算和乘2运算，乘2可以用移位来实现基础知识-圆的表示1、直角坐标法 2、极坐标法222)()(ryyxxccsin,cosryyrxxccyxMP1P2P（Xp，Yp）MP1P2MP1P2MP1P2MP1P2圆的Bresenh
8、am算法yiyyi-1Xi+1xi01d2d我们设圆的半径为r，圆心在（，），考虑从（，r）顺时针方向/8圆周的生成过程。X从开始，到x=y结束。即有11iixx相应的yi+1就有两种选择：1,11iiiiyyyyyi+1取值就要看精确值y是靠近yi还是靠近yi-1，计算公式为：222)1(ixry222221)1(iiixryyyd222222)1()1()1(iiiyxryyd令pi=d1-d2，并代入d1，d2，则有22222)1()1(2ryyxpiiiiPi为误差。如果pi0，则yi+1=yi，否则yi+1=yi-1，pi的递归式为：（2.6）221212112)1()1(2ryyx
9、piiii212122122)11(2ryyxiii212221221)(2)(264)1(2ryyyyyyxxiiiiiiii2122212212)(22)(264)1(2ryyyyyyxxiiiiiiii)(2)(2642)1()1(212212222iiiiiiiiyyyyxryyx)(2)(2641221iiiiiiyyyyxpPi的初值由2.6式代入xi=0，yi=r得rp231Bresenham圆周生成算法如下：1、求误差初值，p1=3-2r，i=1，画点（0，r）2、求下一个光栅位置，其中xi+1=xi+1，如果pi0，则yi+1=yi，否则yi+1=yi-1 3、画点（xi+1
10、，yi+1）4、计算下一个误差，如果pi0，pi+1=pi+4xi+6，否则pi+1=pi+4(xi-yi)+105、i=i+1，如果x=y，则结束，否则返回步骤22.3.1基础知识区域填充：即给出一个区域的边界，要求对边界内所有像素单元赋予指定颜色代码。区域填充最常用的是多边形填色。多边形填色即给出一个多边形的边界，要求对边界内所有像素赋予指定的颜色。要完成这些任务，首要问题是判断一个像素是在多边形内还是多边形外。常用“扫描交点的奇偶数判断法”。1、将多边形画在平面内2、用一根水平线自左向右扫描，从而与多边形相交，扫描线与边界相交奇数次后进入多边形，相交偶数次后走出多边形。上述方法似乎很完美
11、，但并非如此，因为直线在光栅化后就变成了占有单位空间的离散点，在扫描部分点时用该方法会出错。所以要对该方法作周密的改善。abcdABC扫描线填色方法有两大类：1、扫描线填色算法（Scan-Line Filling）建立在多边形边界的矢量形式数据上，可用于程序实现，也可用于交互填色。2、种子填色算法（Seed Filling）建立在多边形边界的图形形式数据上，难于用程序实现。算法的基本思想：用水平线从上到下扫描有点线段构成的多段定义多边形。每根扫描线与多边形产生一系列交点。将这些交点按照X坐标进行分类，将分类后的交点成对取出，作为两个端点，以所需要的色彩画水平直线。多边形被扫描完毕后，填色也就完
12、成。基本思想中要解决几个问题：1、左右顶点处理 122313（a）左顶点（b）右顶点Y1y2y2y3当扫描线与多边形每个顶点相交时，会同时产生2个交点，这是因为一个顶点同属于多边形两条边的端点。如果所交的顶点是左顶点或右顶点，填色就会因为扫描交点的奇偶计数出错而出现错误。这时对所有的左右交点做如下处理：左右顶点的入边（以该顶点为终点的边）之终点删除。对于左顶点，入边端点（x1，y1）（x2，y2）修改为(x1，y1)、(x2-1/m，y2-1)；对于右顶点入边端点（x1，y1）（x2，y2）修改为(x1，y1)、(x2+1/m，y2-1)，其中1212xxyym对于多边形的上顶点或下顶点，奇偶
13、数目正确，因此不用修改。2、水平边处理水平边（y1=y2）与水平扫描线重合，无法求交点，因此将水平边删除。3、扫描线与边的交点求取办法采用递归算法以（x1,y1）（x2,y2）为端点的边与第i+1 条边的交点为11iiyy12121yyxxxxii4、减少求交计算量，采用活性边表每根扫描线与多边形所有边求交的操作是一种浪费，需要改进。活性表（Active List of Side）采用将多边形的边分成两个子集：与当前扫描线相交的边集合和与当前扫描线不相交的边集合。活性表构造方法：1）将经过左右顶点处理并剔除水平边后的多边形的各边按maxy值排序，存入一个线性表，表中每个元素代表一条边，第一个元
14、素是maxy值最大的边，最后一个是最小的边。2）设置两个指针first和last，这两个指针间是与当前扫描线相交的边的集合和已经处理完（即扫描完）的边的集合。区分这两者的办法是在处理完的边上面加记号0yLast指针后的是未与当前扫描线相交的边。这时每根扫描线只需与位于firstlast之间且 不为0的边求交即可。yscan1ADIHCEFGBscan2firstlast(a)扫描线填充(b)活性表及其指针3、活性表中每个元素的内容包含以下几项：（1）边的maxy值，记为y_top(2)与当前扫描线相交的点的X坐标值，记为x_int(3)边的Y方向当前总长，初始值为y2-y1记为(4)边的斜率的
15、倒数：记为x_change_per_scan4、活性表在每根扫描线扫描之后刷新，刷新2项y1212yyxx（1）调整 first和last指针间的参加求交运算的边的元素值：1yyscanperchangexxx_int_int_(2)调整first和last指针，以便使新边进入激活范围，处理完的边退出激活范围。当first指的边 为0时，first=first+1；当last指的下一条边的y_top大于下一扫描线的y值时，last=last+1y种子填色又称边界填色（Boundary Filling），功能是给出多边形光栅化后的边界位置、边界色代码以及多边形内一点（x，y）的位置，要求将颜色填
16、满多边形。通常有两种：四邻法、八邻法四邻法是已知(x,y)是多边形内一点，在这点的上下左右四个方向进行测试、填色、扩散。缺点是不能通过狭窄区域，因此不能填满多边形。八邻法是在多边形内一点的8个方向进行测试、填色、扩散。缺点是有时会超出多边形的边界。由于填不满往往比涂出更易于补救，所以四邻法比八邻法用的普遍。点阵式字符是将字符表示一个矩形点阵，由点阵中点的不同值表达字符的形状。由于光栅扫描显示器的普遍使用，点阵式字符表示已经成为一种字符表示的主要形式。如果从字库中读出原字符，经过变换复制到缓冲器中的操作用专门的硬件来完成，可大大加快字符生成速度。将字符表达为点坐标的序列，相邻两点表示一条矢量，字
17、符的形状由矢量序列刻画。由于调用矢量字符具有与图形一致的数据结构，因此可以接受任何对于图形的操作，如放大、旋转，甚至透视，矢量字符不仅可以用于显示，也可用于绘图机输出。方向编码式字符用有限的若干种方向编码来表达一个字符，常用的如8方向编码。可以在X，Y两个方向放大缩小以及45度旋转，但难于进行任意角度旋转。方向编码式字符不仅可以用于显示，也可用于绘图机输出。由于用点阵字符时每种字号，字体存储时要占用很大空间，所以采用压缩技术来解决这个问题，这就出现了轮廓字形技术。其中压缩技术中黑白段压缩法，方法简单，不失真，但压缩质量较差，一般用于低级文字处理系统。另一种是部件压缩法，压缩比大，缺点是字形质量
18、差。三是轮廓字形技术，压缩比大，字形质量高，是当今国际流行的方法。计算机图形学中常会遇到求交运算。求交运算是计算机辅助设计系统的重要组成部分，它的准确性和效率直接影响计算机辅助设计系统的可靠性与实用性。求交问题可分为求交点和求交线两类10,)(tBtAtP10,)(sDsCsQ1、直线段与直线段的交点假设两条直线段的端点分别为P1、P2和Q1、Q2，直线段用矢量形式表示为：其中A=P1,B=P2-P1,C=Q1,D=Q2-Q1，构造方程为DsCBtA(2.9)对三维空间中的直线段，上述方程组实际上是一个二元一次方程组，由三个方程组成，可以从其中两个解出s,t，再用第三个验证解的有效性。有效则找
19、到了解，否则两条直线不相交。根据矢量性质，可直接计算s,t，对方程(2.9)两边构造点积)()()()(DsCDCBtADC由于CD同时垂直于C和D等式右端为0BDCADCt)()(DBACBAs)()(2、直线段与二次曲线的交点考虑平面上一条直线与同平面的一条二次曲线的交点，曲线方程为0),(yxf直线方程为),(),(11tdyytdxxyx交点处有0),(11tdyytdxxf当曲线为二次曲线时，上述方程可写为02cbtat用二次方程求根公式即可求出t3、圆锥曲线与圆锥曲线的交点圆锥曲线表示方法有代数法、几何法、参数法。一对圆锥曲线求交时，把其中一条圆锥曲线用代数法或几何法表示为隐函数，
20、另一条用参数形式，将参数形式代入隐函数，可得到关于参数的四次方程，用四次方程求根公式解出交点参数。下面讨论线与面的交点求法：1、直线段与平面交点平面上的点表示为直线上的点为 ,二者的交点为R，假设线段不平行于平面，则它们交于 wCuBAwuP),(tEDtQ)()(),(tQwuPRtEDwCuBA等式两边点乘BC得).().(tEDCBwCuBACBECBDCBACBt).().().(BECAECDECu).().().(CEBAEBDEBw).().().(2、圆锥曲线与平面的交点将圆锥曲线表示成参数形式，代入平面方程，即可得到参数的二次方程，从而进行求解。3、圆锥曲线与二次曲面的交点将
21、圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用四次方程求根公式求解。1、平面与平面的交线先考虑最简单的情形。两个平面区域分别有P(u，w)Q(s，t)，(u、w、s、t属于0，1)，如果它们不共面且不分离，则必交于一直线段。这条直线必落在P(u,w)-Q(s,t)=0所定义的无限直线上。这是含有4个未知数、3个方程式的方程组，只要分别与8条边界线方程：u=0,u=1,w=0,w=1,s=0,s=1,t=0,t=1联立，既可求出线段的两个端点参数。当两个一般的多边形相交时，可能有多段交线，设两个多边形为A和B（1）把A所有边与B求交，求出所有有效交点（2）把B所有边与A求交，求
22、出所有有效交点（3）把所有交点先按 y、再按x的大小排序（4）把每对交点所形成线段的中点与A和B进行包含性检测，若该中点既在A中又在B中则这对交点定义了一条线段。2、平面与二次曲面的交线有两种方法：代数法和几何法代数法：二次曲面代数法表示为0222222222JIzHyGxFxzEyzDxyCzByAx通过平移与旋转坐标变换，把平面变为xoy平面，对二次曲面也做同样坐标变换。在新坐标系下平面的方程为z=0，则二次曲面方程中z项去掉。即为平面与二次曲面的交线方程。对该交线方程进行一次逆坐标变换，即可获得原坐标系下的交线方程。缺点是要进行坐标变换。几何法：存储曲线的类型以及定义参数（中心点、对称轴
23、、半径等）信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。优点：较少的变换。缺点：需要通过计算来判断曲线的种类，并计算曲线的定义参数。由于浮点数运算的不精确性，容易发生判错曲线类型以及定义参数的误差过大。3、平面与参数曲面的交线将表示参数曲面的变量（x(s,t),y(s,t),z(s,t)）代入平面方程得到参数表示的交线方程0dczbyax0),(),(),(dtscztsbytsax另一种方法是用平移和旋转对平面进行坐标变换，使平面成为新坐标系下的xoy平面，再将相同的变换应用于参数曲面方程，得到参数曲面在新坐标系下的方程，由此得到交线新坐标系下的方
24、程。),(),(),(),(*tsztsytsxzyx0),(*tsz在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面或三维形体中，线段是否包含在平面或三维形体中。许多包含判断问题可转化为点的包含判断问题，因此下面主要讨论关于点的包含判定问题。就是判断点与线的最短距离是否位于容差范围内，线段主要有三种：直线、圆锥曲线（主要是圆弧）、参数曲线。1、点与直线的包含判定点坐标为P(x,y,z)，直线端点为P1(x1,y1,z1)、P2(x2,y2,z2)，则点P到线段P1P2的距离的平方为)()()/()()()()()()(212212212211211211221
25、21212zzyyxxzzzzyyyyxxxxzzyyxxd当 时，认为点在线段（或其延长线）上，下面进一步判断点是否落在直线段的有效区间内。对坐标分量进行比较，当x-x1和x-x2异号时，点在线段有效区间内。22d2、点与圆锥曲线的包含判定以圆弧为例，点的坐标为(x,y,z)，圆弧中心点为(x0,y0,z0)，半径为r，起始角a1,终止角a2,圆弧所在平面为0dczbyax先判定点是否在该平面内，若不在，则点不可能被圆弧包含；若在，通过坐标变换，把问题转化二维空间中的问题。第一步判断点是否在圆的圆周上，第二步判断点是否在有效的圆弧上。|)()(|2020ryyxx3、点与参数曲线的包含判定设
26、点坐标为P(x,y,z)，曲线方程为Q(t)=(x(t),y(t),z(t)，点与参数曲线求交计算分3个步骤：（1）计算t的值，使P到Q(t)的距离最小（2）判断t是否在有效参数区间内（通常为0,1）（3）判断Q(t)与P的距离是否小于第一步计算参数t，使 最小，即下式最小|)(|tQP2|)(|)()()(tQPtQPtQPtR根据微积分知识，在该处 即0)(tR0)()(tQPtQ用数值方法解出t，再代入曲线参数方程，即可求出曲线上对应点的坐标。第2、3处理方法简单，不再讨论。4、点与平面区域的包含判定点坐标为P(x,y,z)，平面方程为ax+by+cx+d=0，则点到平面距离为222|c
27、badczbyaxdd则认为点在平面上，否则认为点不在平面上对落在平面上的点还应继续判别它是否在有效区域内，下面以平面区域多边形为例，介绍有关算法：（1）叉积判断法假设判断点为P0，多边形顶点按顺序排列为p1p2pn。令Vi=Pi-P0,其中i=1,2n,Vn+1=v1P0在多边形内冲要条件为叉积ViVi+1的方向相同。（2）夹角之和检验法假设平面上的点P0和多边形P1P2P3P4P5，将P0分别与各点连接，构成矢量Vi=Pi-P0，假设iiiaPPP10如果510iia则点P0在多边形之外，如果251iia则点P0在多边形之内（3）交点计数检验法当多边形为凹多边形，甚至带孔，可用此法判断点是
28、否在多边形内。从判断点作一射线至无限远，求射线与多边形边的交点个数，为奇数则点在多边形内，否则在多边形外。5、点与二次曲面/参数曲面的包含判定点为P(x0,y0,z0),二次曲面为Q(x,y,z)=0则点在二次曲面上。6、点与三维形体的包含判定2.5.4重叠判定算法一点与另一点是否重叠，判断二者距离是否等于0即可。|),(|000zyxQ判断两条线是否重叠，可先判断是否共线，即判断一条线段上任意两点是否在另一条线段上，若两条线段不共线，则不可能重叠；否则，可通过端点坐标的比较来判断两线段的重叠部分。判断两个平面重叠一种方法是判断一个平面不共线的3个点是否在另一个平面上；另一种是先比较两个平面的
29、法矢量，再判断一个平面上的某点是否在另一个平面上。我们将矩形窗口称为窗口，窗口确定后窗口外物体不参加标准转换及随后的显示操作，从而节约时间。裁剪（Clipping）是裁去窗口之外物体或物体部分的一种操作。2.6.1、直线的裁剪（1）整条直线在窗口内，不需要裁剪（2）整条直线在窗口外，不需要裁剪（3）部分直线在窗口内，部分在窗口外，需要求出交点，窗口外的直线部分裁剪掉。直线裁剪有两个主要步骤：首先将不需要裁剪的直线挑出，即删除窗口外的直线，然后对其余直线，逐条与窗框求交点，并将窗口外的部分删除。（1）（2）（3）下面的直线裁剪算法是有Cohen和Sutherland提出的：算法以区域编码为基础，
30、将窗口及周围的8个方向以4bit的二进制数进行编码，各编码分别代表窗外上下左右空间的编码值。100100010101100000001010001001000110一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：100110001010000100000010010101000110P1P2P3P4编码方法将窗口及邻域分为5个区域：（1）内域：0000（2）上域：1001，1000，1010（3）下域：0101，0100，0110（4）左域：1001，0001，0101（5）右域：1010，0010，0110优点：1、容易将不需要
31、裁剪的直线挑出，如果一条直线的两端在同一区域，不需要裁剪，否则裁剪2、对可能裁剪的直线缩小与之求交的边框范围，如果直线的一个端点在上（下、左、右）域，则此直线与上（下、左、右）边框求交，然后删去边框以外的部分。该规则对直线的另一端点也适用，这样一条直线至多只需与两条边框求交。Cohen-Sutherland算法：（1）对直线两端点P1、P2按各自所在区域编码。P1,P2编码分别记为,)(,)(222222111111dcbaPCdcbaPC其中，ai,bi,ci,di范围为1，0（2）如果ai=bi=ci=di=0，则显示整条直线，取出下一条直线，返回 1；否则进入步骤3（3）如果|a1-a2
32、|=1，则求直线与窗上边（y=yw-max）的交点，并删除交点以上部分；如果|b1-b2|=1，则求直线与窗下边（y=yw-min）的交点，删除交点以下部分如果|c1-c2|=1，则求直线与窗右边（x=xw-max）的交点，删除交点以右部分如果|d1-d2|=1，则求直线与窗左边（x=xw-min）的交点，删除交点以左部分（4）返回步骤1多边形裁剪比直线复杂，如果按直线裁剪算法对多边形裁剪，多边形裁剪后的边为一组不连贯的折线。多边形裁剪关键是不仅要保持窗口的边界部分，而且要使裁剪后的多边形的边保持封闭，这样填色得以正确进行。下面介绍Sutherland和Hodgman提出的算法：1、令多边形的
33、顶点按边线顺时针排序为P1,P2Pn，各边先与上窗框求交，求交后，删除多边形在窗框之上部分，并插入上窗边及其延长线与多边形的交点之间的部分，形成一新的多边形，然后新多边形按相同方法与右窗框相剪裁，如此重复，直至多边形与各窗框都相剪裁完毕。2、多边形与每条窗框相交、生成新多边形顶点序列的过程，是对多边形各顶点依次处理的过程。设当前处理的顶点为P，先前已处理的顶点为S，多边形各顶点处理规则如下：（1）如果点S、P均在窗框内侧，将点P保存（2）如果点S在窗框内侧，点P在窗框外侧，求出SP边与窗框的交点I，保存点I，舍去点P（3）如果点S、P都在窗框外侧，舍去点P（4）如果点S在窗框外侧，点P在内侧，那么求出SP边与窗框交点I，依次保存点I，P基于上述四种情况，可以归纳对当前点P的处理方法如下：（1）P在窗框内侧，则保存P：否则不保存点P（2）P和S在窗框的非同侧，则求交点I，并保存点I，将它插入P之前或S之后。172654326817543（a）裁剪前的多边形（b）与上窗边裁剪165784923110239476581510967811234（e）与左窗边裁剪（c）与右窗边裁剪（d）与下窗边裁剪spsssppp
