基本图形生成算法分析

1、画一条从(x1, y1)到(x2, y2)的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为直线光栅化。连续性粗细、亮度要均匀像素逼近待画直线速度2.1.1 直线直线DDA算法算法 (Digital Differential Analyser)假设 直线的起点坐标为P1 (x1,y1)，终点坐标为P2 (x2,y2) x方向的增量为 xx2x1 ；y方向上增量为 yy2y1 直线的斜率为 k ky yx x 当 x xy y 时，让 x 从 x1 到 x2 变化，每步递增 1， 那么，x 的变化可以表示为 xi+1xi1 y 的变化可以表示为 yi+1yik 用

2、上式可求得图中直线 P1P2 和 y 向网格线的交点，但显示时要用舍入 找到最靠近交点处的象素点耒表示。 当 xxdy? DxDy1a true 1 m1b false 1/m 12a true -1 m2b false -1/m 13a true -1 -m3b false -1/m -14a true 1 -m4b false 1/m -1表2.1 8个象限中的坐标增量值研究表中的数据，可以发现两个规律。 当dxdy时Dx = 1，Dy = m否则Dx = 1/m，Dy = 1 Dx、Dy的符号与dx、dy的符号相同。2.1.1 直线直线DDA算法算法 （续）（续）算法描述如下：dda_l

3、ine(xa, ya, xb, yb, c)int xa, ya, xb, yb, c;float delta_x, delta_y, x, y;int dx, dy, steps, k;dx=xbxa;dy=ybya;if(abs(dx)abs(dy)steps=abs(dx);else steps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;2.1.1 直线直线DDA算法算法 （续）（续）x=xa;y=ya;set_pixel(x, y, c);for(k=1;k0，则yi+1=yi+1，否则y

4、i+1=yi。将式(2.1)、(2.2)、(2.3)代入d1d2，再用dx乘等式两边，并以Pi=(d1d2) dx代入上述等式，得 Pi = 2xidy2yidx+2dy+(2b1) dx (2.4)d1d2是用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi+1为 Pi+1 = Pi+2dy2(yi+1yi) dx (2.5)2.1.2 直线直线Bresenham算法算法( ( 续）续） 求误差的初值P1，可将x1、y1和b代入式(2.4)中的xi、yi而得到 P1 = 2dydx 综述上面的推导，第1a象限内的直线Bresenham算法思想如下： 画

5、点(x1, y1)，dx=x2x1，dy=y2y1，计算误差初值P1=2dy dx，i=1； 求直线的下一点位置 xi+1 = xi + 1 如果Pi0，则yi+1=yi+1，否则yi+1=yi； 画点(xi+1, yi+1)； 求下一个误差Pi+1，如果Pi0，则Pi+1=Pi+2dy2dx，否则 Pi+1=Pi+2dy； i=i+1；如果i|dy|为分支，并分别将2a、3a象限的直线和3b、4b象限的直线变换到1a、4a和2b、1b象限方向去，以实现程序处理的简洁。2.2.1 基础知识基础知识 给出圆心坐标(xc, yc)和半径r，逐点画出一个圆周的公式有下列两种： 直角坐标法直角坐标法(

6、xxc)2 + (yyc)2 = r2由上式导出：cc22()yyrxx当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，xxc越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。2.2.1 基础知识基础知识( (续）续） 极坐标法极坐标法x = xc + r cos，y = yc + r sin当从0到作递增时，由此式便可求出圆周上均匀分布的360个点的(x, y)坐标。利用圆周坐标的对称性，此算法还可以简化。将圆周分为8个象限(图2.3)，只要将第1a象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。图2.3

7、圆心在(0, 0)点圆周生成时的对称变换2.2.2 圆的圆的Bresenham算法算法 设圆的半径为r。先考虑圆心在(0, 0)，并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有xi+1 = xi + 1相应的yi+1则在两种可能中选择：yi+1 = yi或者yi+1 = yi1选择的原则是考察精确值y是靠近yi还是靠近yi1(图2.4)，计算式为y2 = r2(xi+1)2d1 = yi2y2 = yi2r2+(xi+1)2d2 = y2(yi1)2 = r2(xi+1)2(yi1)2图2.4 y的位置 2.2.2 圆的圆

8、的Bresenham算法算法( (续）续） 令pi=d1d2，并代入d1、d2，则有 pi = 2(xi+1)2 + yi2 + (yi1)22r2 (2.6)pi称为误差。如果pi0则yi+1=yi，否则yi+1=yi1。pi的递归式为 pi+1 = pi + 4xi +6+2(yi2+1 yi2) 2(yi+1yi) (2.7)pi的初值由式(2.6)代入xi=0，yi=r而得 p1 = 32r (2.8)根据上面的推导，圆周生成算法思想如下： 求误差初值，p1=32r，i=1，画点(0, r)； 求下一个光栅位置，其中xi+1=xi+1，如果pi0则yi+1=yi，否则yi+1=yi1；

9、 画点(xi+1, yi+1)； 计算下一个误差，如果pi0则pi+1=pi+4xi+6，否则pi+1=pi+4(xiyi)+10； i=i+1，如果x=y则结束，否则返回步骤2。2.2.2 圆的圆的Bresenham算法算法( (续）续）圆的Bresenham算法的程序实现如下：circle(xc, yc, radius, c)int xc, yc, radius, c;int x, y, p;x=0;y=radius;p=32*radius；while(xy)plot_circle_points(xc,yc,x,y,c);if(p0) p=p+4*x+6;elsep=p+4*(xy)+10

10、;y=1; x+=1;if(x=y)plot_circle_points(xc,yc,x,y,c);2.2.2 圆的圆的Bresenham算法算法( (续）续）plot_circle_points(xc, yc, x, y, c)int xc, yc, x, y, c;set_pixel(xc+x, yc+y, c);set_pixel(xcx, yc+y, c);set_pixel(xc+x, ycy, c);set_pixel(xcx, ycy, c);set_pixel(xc+y, yc+x, c);set_pixel(xcy, yc+x, c);set_pixel(xc+y, ycx,

11、 c);set_pixel(xcy, ycx, c);2.3.1 基础知识基础知识 区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。多边形的表示方法多边形的表示方法顶点表示顶点表示点阵表示点阵表示图2.5 扫描线与多边形相交 图2.6 光栅化后直线变成离散点 多边形填色一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判断法”。 2.3.1 基础知识基础知识( (续）续） 2.3.1 基础知识基础知识( (续）续） 填色算法分为两大类： 扫描线填色(Scan-Line Filling)算法

12、。这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。 种子填色(Seed Filling)算法。这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。2.3.2 扫描线填色算法扫描线填色算法 算法的基本思想。多边形以n、x_array、y_array的形式给出，其中，x_array、y_array中存放着多边形的n个顶点的x，y坐标。用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交点。这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端

13、点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。2.3.2 扫描线填色算法扫描线填色算法( (续）续） 上述基本思想中，有几个问题需要解决或改进： 左、右顶点处理。当以1、2、3的次序画多边形外框时，多边形的左顶点和右顶点如图2.7中所示的顶点2。它们具有以下性质。左顶点2：y1y2y2y3其中y1、y2、y3是3个相邻的顶点的y坐标。图2.7 多边形的顶点 当扫描线与多边形的每个顶点相交时，会同时产生2个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。因此，对所有左、右顶点作如下处理：2.3.2 扫描线填色算法扫描线填色算法( (续）续） 左、右顶点的入边(以该顶点

14、为终点的那条边，即12边)之终点删去。对于左顶点，入边端点(x1, y1)、(x2, y2)修改为(x1, y1)、(, y21)；对于右顶点，入边端点(x1, y1)、(x2, y2)修改为(x1, y1)、(, y2+1)；其中，即入边的斜率。对于多边形的上顶点(y2y1、y2y3)或下顶点(y2y1、y2s.r)两个面无交；2.5.2 求交线算法求交线算法 （续）（续） else所求交线是圆。其圆心、半径、圆所在平面法向量为c=s.cd*p.w;r=sqrt(s.r2d2);w=p.w; 2.5.2 求交线算法（续）求交线算法（续） 平面与参数曲面的交线 求平面与参数曲面的交线，最简单的

15、方法是把表示参数曲面的变量(x(s, t), y(s, t), z(s, t)代入平面方程 ax+by+cz+d=0得到用参数曲面的参数s、t表示的交线方程 ax(s, t)+by(s, t)+cz(s, t)+d=0 另一种方法是，用平移和旋转对平面进行坐标变换，使平面成为新坐标系下的xOy平面。再将相同的变换应用于参数曲面方程，得到参数曲面在新坐标系下的方程 (x*, y*, z*)=(x*(s, t), y*(s, t), z*(s, t)由此得交线在新坐标系下的方程为z*(s, t)=0。2.5.3 包含判定算法包含判定算法 在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点

16、是否包含在线段、平面区域或三维形体中，线段是否包含在平面区域或三维形体中，等等。 许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上的问题可以转化为判断线段两端点是否在平面上。 判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有3种，即直线段、圆锥曲线段(主要是圆弧)和参数曲线(主要是Bezier曲线、B样条与NURBS曲线)。点与面的包含判定也类似地分为3种情况。下面分别予以讨论。2.5.3 包含判定算法（续）包含判定算法（续） 点与直线段的包含判定假设点坐标为P(x, y, z)，直线段端点为P1(x1, y1, z1)、P2(x2, y

17、2, z2)，则点P到线段P1P2的距离的平方为d2=(xx1)2+(yy1)2+(zz1)2(x2x1)(xx1)+(y2y1)(yy1)+(z2z1)(zz1)2/(x2x1)2+(y2y1)2+(z2z1)2当d22时，认为点在线段(或其延长线)上，这时还需进一步判断点是否落在直线段的有效区间内。对坐标分量进行比较，假设线段两端点的x分量不等(否则所有分量均相等，那么线段两端点重合，线段退化为一点)，那么当xx1与xx2异号时，点P在线段的有效区间内。2.5.3 包含判定算法（续）包含判定算法（续） 点与圆锥曲线段的包含判定以圆弧为例，假设点的坐标为(x, y, z)，圆弧的中心为(x0

18、, y0, z0)，半径为r，起始角为1，终止角为2。圆弧所在平面为ax+by+cz+d=0 先判断点是否在该平面上；若点在该平面上，则通过坐标变换，把问题转换成二维空间中的问题。对于平面上一点P(x, y)，判断P是否在圆弧上，可分两步进行。第一步判断P是否在圆心为(x0, y0)，半径为r的圆的圆周上，即下式是否成立第二步判断P是否在有效的圆弧段内。2200)()xxyyr（2.5.3 包含判定算法（续）包含判定算法（续） 点与参数曲线的包含判定设点坐标为P(x, y, z)，参数曲线方程为Q(t)=(x(t), y(t), z(t)。点与参数曲线的求交计算包括3个步骤。 计算参数t的值，

19、使P到Q(t)的距离最小。 判断t是否在有效参数区间内(通常为0, 1)。 判断Q(t)与P的距离是否小于。若第(2)、(3)步的判断均为“是”，则点在曲线上；否则，点不在曲线上。第一步应计算参数t，使得|PQ(t)|最小，即R(t)=(PQ(t)(PQ(t)=|PQ(t)|2最小。根据微积分知识，在该处R(t)=0，即Q(t)PQ(t)=0。用数值方法解出t值，再代入曲线参数方程，可求出曲线上对应点的坐标。第(2)、(3)步不再赘述。2.5.3 包含判定算法（续）包含判定算法（续） 点与平面区域的包含判定设点坐标为P(x, y, z)，平面方程为ax+by+cz+d=0。则点到平面的距离为若

20、dCi其中，常数d=0.035 557 3。当i时，可判定P0在多边形内。当i时，可判定P0在多边形外。,4iiiSdC,24iiiSdC 交点计数检验法当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远00(0)xxu uyy2.5.3 包含判定算法（续）包含判定算法（续）求射线与多边形边的交点个数。若交点个数为奇数，则点在多边形内；否则，点在多边形外。如图2.18所示，射线a、c与多边形分别交于2个点和4个点，为偶数，故判断点A、C在多边形外。而射线b、d与多边形分别交于3个点和1个点，为奇数，所以点B、D在多边形内。图2.18 交

21、点计数法 当射线穿过多边形顶点时，必须特殊对待。若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。按这种方法，交点计数为偶数时点在多边形外；交点计数为奇数时点在多边形内。 2.5.3 包含判定算法（续）包含判定算法（续） 点与二次曲面/参数曲面的包含判定假设点坐标为P(x0, y0, z0)，二次曲面方程为Q(x, y, z)=0，则当|Q(x0, y0, z0)|时，认为点在该二次曲面上。有时还要判断点是否在曲面有效范围内。 点与三维形体的包含判定判断点是否被三维形体所包含，可先判断点是否在三维形体的表面上，然后判断点是否在形体内部，其方法因形体不同而异。以凸多面体为例。设凸多面体某

22、个面的平面方程为ax+by+cz+d=0，调整方程系数的符号，使当ax+by+cz+d0时，点(x, y, z)位于该平面两侧方向包含该凸多面体的一侧。于是要检验一个点是否在凸多面体内部，只要检验它是否对凸多面体的每一个面均满足以上的不等式即可。2.5.4 重叠判定算法重叠判定算法 判断空间一点与另一点是否重叠，只要判断两点之间的距离是否等于0即可。判断两条线段是否重叠，可先判断它们是否共线，即判断一条线段上的任意两点是否在另一条线段所在的直线上，或是比较两条线段的方向向量并判断一条线段上的任意一点是否在另一条线段所在的直线上。若两条线段不共线，则它们不可能重叠；否则，可通过端点坐标的比较来判

23、断两线段的重叠部分。判断两个平面的重叠关系，一种方法是判断一个平面上不共线的3个点是否在另一个平面上；另一种方法是先比较两个平面的法向量，再判断一个平面上的某点是否在另一个平面上。2.5.5 凸包计算凸包计算 一个图形的凸包，就是包含这个图形的一个凸的区域。例如，一个平面图形的凸包可以是一个凸多边形，一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是惟一的。在进行图形求交计算时，如果两个图形的凸包不相交，显然它们不可能相交。否则，需要进一步计算。包围盒是一种常用的凸包。二维包围盒是二维平面上的一个矩形，它的两条边分别与两条坐标轴x、y平行，可以表示xminxxmax、yminyymax。

24、三维空间中的包围盒是一个长方体，可表示为3个不等式，即xminxxmax、yminyymax、zminzzmax。两个包围盒相交的充要条件是它们在每一个坐标轴方向上都相交。2.5.5 凸包计算凸包计算 求多边形或多面体的包围盒是相当简便的。只要遍历其所有顶点，就的方法求出包围盒。对于一般的几何形体，则要根据其具体性质来求。对含有曲线、曲面的几何体进行求交时，常常先求它们的一个凸多边形或凸多面体的凸包。由于凸多边形和凸多面体间的求交相对简单，因此可以节省一定的计算量。例如，Bezier曲线、B样条和NURBS曲线、曲面具有凸包性质，其控制多边形或控制网格是其本身的凸包一般的凸包的求法因具体情况而

25、异，下面举一个求圆弧凸包的例子。设圆弧段的圆方程为(xx0)2+(yy0)2=r2，圆弧起始角为1，终止角为2。对圆弧计算凸包如图2.19所示。先根据起始角1与终止角2求出相应的弧端点P1、P2坐标，进而求出弧的弦中点Pm=(P1+P2)/2。 2.5.5 凸包计算（续）凸包计算（续） 再用下式计算弧中点Pc：则该弧的包围盒顶点为P1、P1+(PcPm)、P2+(PcPm)、P2。m0c0m0PPPPrPP图2.19 圆弧的凸包 裁剪(clipping)是裁去窗口之外物体或物体部分的一种操作。2.6.1 直线的剪裁直线的剪裁 直线和窗口的关系可以分为如下3类(图2.20)： 整条直线在窗口内。

26、此时，不需剪裁，显示整条直线。 整条直线在窗口外，此时，不需剪裁，不显示整条直线。 部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。 直线剪裁算法有两个主要步骤。首先将不需剪裁的直线挑出，即删去 在窗外的直线。然后，对其余直线，逐条与窗框求交点，并将窗口外的 部分删去。 图2.20 直线与窗口的关系 2.6.1 直线的剪裁（续）直线的剪裁（续） Cohen-SutherlandCohen-Sutherland直线剪裁算法直线剪裁算法以区域编码为基础，将窗口及其周围的8个方向以4 bit的二进制数进行编码。图2.21 直线剪裁

27、算法中的区域编码 图2.21所示的编码方法将窗口及其邻域分为5个区域： 内域：区域(0000)。 上域：区域(1001, 1000, 1010)。 下域：区域(0101, 0100, 0110)。 左域：区域(1001, 0001, 0101)。 右域：区域(1010, 0010, 0110)。 2.6.1 直线的剪裁（续）直线的剪裁（续） 算法的主要思想是，对每条直线P1P2： 对直线两端点P1、P2编码分别记为C1(P1)=a1, b1, c1, d1，C2(P2)=a2, b2, c2, d2其中，ai、bi、ci、di取值范围为1, 0，i1, 2。 如果ai=bi=ci=di=0，则