03-第三章_直线和圆弧的生成算法(上)网络学堂_547501374.pdf

第三章直线和圆弧的生成算法
§1 引言
(1) 版画
(2) 看图释义
(3) 再看一个手机界面
直线和圆弧的生成算法
上述演示的结论:
(I) 线条是最基本的图形,用途广
(II) 纯粹的线条组合也产生美
(III) 人工书写---->计算机产生
(IV) 有些是纯艺术,但计算机也可以产生
(V) 图形设备将越来越被广泛使用
这里讲直线与圆弧在计算机中的快速生成方法,
§2. 直线的快速生成
已知线段的两个端点: 起始点(xs, ys)和结束点(xe, ye).
求: 离散线段的中间各点.
(xe, ye)
(xs, ys)
利用直线方程直接求
YYes−
Yi = ()XXis−+Ys
XXes−
有乘除法, 不适合于没有乘法运算器的普通处理器
要尽量避免乘除法
关键问题:怎样只用加减法?
直线和圆弧的生成算法
把
线
段
放
大
观察结论:在X,Y方向上,必有一个方向上的间距始终为“1”
而另一个方向上或者为0, 或者为1.
取决于: 斜率.
DDA(Digital Differential Analyzer)算法
设所画直线的斜率m有0<m<1,则相邻点有:
∆x=1, ∆y=m
于是:
xk+1 =xk+1
yk+1=yk+m
除了浮点运算外,该方法有一个缺点. 是什么?
误差累积问题!
Bresenham算法
仍借助于DDA算法中的一个结论:
在离散的空间中, 对一条线段而言,相邻两个点必
有一个方向上其坐标值相差为1
再借助于另一个结论:看另一个方向上的模拟增
量是否大于1/2,从而判断下一步在这个方向上是
增1还是不变。
引入迭代法
Bresenham 直线算法
根据已知条件求出斜率:
y − y ∆y
m = e s =
xe − xs ∆x
并假设当前点为第k个点,其坐标(xk, yk)已经求出
问题转化为: 求第k+1个点(xk+1, yk+1)
z 我们将以0<m<1为例进行推导,其他的情况可
以利用对称关系得到。