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