计算机图形学 第3章.ppt

第3章 基本图形 生成算法 3.1 生成直线的常用算法 均假定所画直线的斜率k∈[0，1]。 3.1.1 DDA画线算法 DDA（Digital Differential Analyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。 已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为： 假定端点坐标均为整数，取直线起点P0 (x0, y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y））作为当前点的坐标。 3.1.2 中点画线算法 假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。 设Q是理想直线与垂直线x=xp+1 的交点。显然，若M在Q的下方，则P2 离直线近，应取为下一个像素；否则应 取P1。 令a=y0-y1，b=x1-x0，c=x0y1-x1y0。 构造判别式： d=a(xp+1)+b(yp+0.5)+c d的初始值d0 = a+0.5b 在d≥0的情况下，取正右方像素P1， d1=a(xp+2)+b(yp+0.5)+c =d+a 在d0的情况下，取右上方像素P2， d2=a(xp+2)+b(yp+1.5) = d+a+b 由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。 如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。 3.1.3 Bresenham画线算法 过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。 由图3-5不难看出：若st， 则Si比较靠近理想直线，应 选Si;若s≥t，则Ti比较靠近 理想直线，应选Ti。 令dx=x2-x1，dy=y2-y1 递推公式 ： di的初值： 当di≥0时，选Ti， 当di0时，选Si， 由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。 3.1.4 直线属性 1．线型 2．线宽 3．线色 3.2 生成圆弧的常用算法 3.2.1 圆的特性 圆心位于原点的圆有四条对称轴：x=0，y=0，x=y和x=-y直线。若已知圆弧上一点（x,y），可以得到其关于四条对称轴的其它7个点，这种性质称为八对称性，如下图所示。 本节讨论的圆的生成算法 均只计算从x=0到x=y分段内 （1b区域）的像素点，其余的 像素位置利用八对称性即可得 出。 3.2.2 中点画圆算法 假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。 令M为P1和P2的中点，易知 M的坐标为（xp+1,yp-0.5）。 显然，若M在圆内，则P1离圆弧 近，应取为下一个像素；否则应 取P2。 判别式d： d的初始值为： 在d≥0的情况下，取右下方像素P2， 在d0的情况下，取正右方像素P1， 3.2.3 Bresenham画圆算法 假设生成圆心在坐标原点，半径为r，从x=0到x=y的1/8圆弧。 xi+1=xi +1 相应的y则在两种可能中选择： y=yi，或者y=yi-1 选择的原则是考察理想的y值 是靠近yi还是靠近yi-1。 判别式： d i+1=2(xi+1)2+yi2+(yi-1)2-2r2 判断式d的初始值为： d0= 3-2r。 如果d i+1=0，则y=yi-1， di+2 =d i+1 + 4(xi- yi)+10 如果d i+10，则y=yi， d i+2 =d i+1+ 4x i+6 3.3 区域填充 3.3.1 区域的表示和类型 顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。