第3章基本图形 生成算法
第3章 基本图形 生成算法
第彐章基本圜形生成算法 31生成直线的常用算法 均假定所画直线的斜率k∈[0,11 3,,DDA画线算法 DDA( Digital Differential Analyzer 画线算法也称数值微分法,是一种增量算 法。它的算法实质是用数值方法解微分方 程,通过同时对x和y各增加一个小增量, 计算下一步的x、y值
第3章 基本图形生成算法 3.1 生成直线的常用算法 ◼ 均假定所画直线的斜率k∈[0，1]。 ◼ 3.1.1 DDA画线算法 ◼ DDA（Digital Differential Analyzer） 画线算法也称数值微分法，是一种增量算 法。它的算法实质是用数值方法解微分方 程，通过同时对x和y各增加一个小增量， 计算下一步的x、y值
第彐章基本圜形生成算法 已知一条直线段L(P,P1),其端点 坐标为:P0x2y0),P1(x1y1)。可计算出直 线的斜率k为: k 假定端点坐标均为整数,取直线起 业(X作为初始坐标。画线过程从x的 点ⅹ开始,向x右端点步进,每步x递增 1,y递增k(即直线斜率);取像素点(x, 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 − − =
第彐章基本圜形生成算法 31.2甲点画线算法 假设x坐标为x的各像素点中,与直线最 近者已确定,为P(xyn),那么,下一个 与直线最近的像素只能是正右方的 P1(x+12y),或右上方的P2(xp+1yp+1)两 者之一。令M为P和P2的中点 为(x2+12y+0.5)。 设Q是理想直线与垂直线 X-X 的交点。显然,若M在Q的下方月 ■离直线近,应取为下一个像素;否则应
第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 ◼ 离直线近，应取为下一个像素；否则应 取P
第彐章基本圜形生成算法 a-yo y1, b=X1-Xo, C=X0y1-X1yo 构造判别式: d=a(X2+1)+b(y+0.5)+c d的初始值dn=a+0.5b 在d>0的情况下,取正右方像素P1, d=a(X+2)+byp+0.5)+c=d+a 在d<0的情况下,取右上方像素P d2=a(xp+2)+b(yp+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画线算法 过各行各列像素中心构造一组虚拟网格线 按直线从起点到终点的顺序计算直线与各垂 直网格线的交点,然后确广 交点最近的像素。 由图35不难看出:若S 口则S:比较靠近理想直线, 选S;若s≥t,则T比较靠近 理想直线,应选T;。 31(1,51) 图3-5 Bresenham画线算法原理示意图
第3章 基本图形生成算法 ◼ 3.1.3 Bresenham画线算法 ◼ 过各行各列像素中心构造一组虚拟网格线， 按直线从起点到终点的顺序计算直线与各垂 直网格线的交点，然后确定该列像素中与此 交点最近的像素。 ◼ 由图3-5不难看出：若s<t， ◼ 则Si比较靠近理想直线，应 ◼ 选Si ;若s≥t，则Ti比较靠近 ◼ 理想直线，应选Ti
第彐章基本圜形生成算法 d 递推公式:=4+2b-2(-y) 4的初值=24-在 当d≥0时,选T, i+1 2+2(dy-ax) 当d<0时,选8,+2d 由于只包含加、减法和左移(乘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
第彐章基本圜形生成算法 31.4直线属性 1.线型 2.线宽 3.线色
第3章 基本图形生成算法 ◼ 3.1.4 直线属性 ◼ 1．线型 ◼ 2．线宽 ◼ 3．线色
第彐章基本圜形生成算法 3,2生成圆弧的常用算法 32L圆的特性 圆心位于原点的圆有四条对称轴:x=0, y=0,xy和x=y直线。若已知圆弧上一点 (xy),可以得到其关于四条对称轴的其 它7个点,这种性质称为八(@3 所示。 2b 1b ( 本节讨论的圆的生成算 均只计算从x=0到x=y分段 3b 4b 1b区域)的像素点,其 (又 伯害位罟和阳敌可但
第3章 基本图形生成算法 3.2 生成圆弧的常用算法 ◼ 3.2.1 圆的特性 ◼ 圆心位于原点的圆有四条对称轴：x=0， y=0，x=y和x=-y直线。若已知圆弧上一点 （x,y），可以得到其关于四条对称轴的其 它7个点，这种性质称为八对称性，如下图 所示。 ◼ 本节讨论的圆的生成算法 ◼ 均只计算从x=0到x=y分段内 ◼ （1b区域）的像素点，其余的 ◼ 像素位置利用八对称性即可得