计算机图形学-直线的扫描转换

上个学期的专业选修课,现在想复习一下,趁机把手写的笔记草稿敲成了电子版

直线的扫描转换

在数学上,理想的直线是没有宽度的,它是由无数个点构成的集合。对直线进行光栅化时,只能在显示器说给定的有限个像素组成的矩阵中,确定最佳逼近于该直线的一组像素,并且按扫描线顺序。下面常见的几种方法:

  1. 逐点比较法:在绘图仪中多采用此方法
  2. 数值微分法(DDA):产生直线比较精确,逻辑简单,但是xyk必须使用浮点表示,每一步需要四舍五入,不利于硬件的实现
  3. 中点画线法
  4. Bresenham算法:只使用整数计算,少量乘法运算可以使用移位来避免,因此计算量少,效率高

1. 逐点比较法

每绘制一个点,就与原直线进行比较,根据比较的结果判断下一步的走向

  • ① 偏差判别
  • ② 选择像素点,根据的大小,判断下一步的走向
  • ③ 是否到达终点,如没有,计算偏差,返回①,到达终点则结束

2. 数值微分法(DDA)

针对斜率,直线段,满足微分方程

,则有

然后取像素点,round表示对y的值进行四舍五入

,xy地位互换,y每增加1,x增加

由于k和y必须使用浮点数表示,每一步都需要舍入取整,浮点运算,不利于硬件的实现,所以引入中点画线法

3. 中点画线法

直线的一般方程,我们假设,把某个点的坐标直线方程

假设有一个点,则我们计算它的下一步中点和直线的关系,将带入得到

根据的大小(即中点在直线的上方还是直线的下方),来确定选择下一步的目标点

4. Bresenham算法

基本思想:每次迭代在增量最大方向上走一步,其方向由增量的正负而决定,另一方向上是否也走,取决于计算出来的点与直线上的点的误差d,根据误差决定是否走下一步。

例如,当k<1时,我们取x方向为最大增量方向,则有

假设开始,则,一旦当 就把它减去1,使d始终在

以下有三个方法的对比和部分代码,来源博客

数值微分中点画线Bresenham

emm惊奇的发现,这三张图的结果是一样的,可能给出一个不同的例子更能显示之间的不同

文章作者:Jiadai Sun

最后更新:2019年09月25日 22:09:41

原始链接:https://sunjiadai.xyz/2019/06/26/计算机图形学-直线的扫描转换/

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 3.0 许可协议,转载请注明出处!


-----------本文结束-----------
0%