这里表达的是用一个“判别变量 d”来画直线每次不用重新代入直线方程算而是用增量更新。它本质上是在讲Bresenham / 中点画线算法。1. 这条直线先被写成隐式方程图里给了(,)(0−1)(1−0)01−10这其实就是过两点(0,0),(1,1)的直线方程。它的作用不是直接求 (ykxb)而是判断一个点 ((x,y)) 在直线的哪一侧。对于这条直线(,)0表示点正好在直线上。如果(,)0说明点在直线一侧。如果(,)0说明点在直线另一侧。在常见的数学坐标系下假设 (0k1)也就是直线从左下往右上走那么(,)0通常表示点在直线上方(,)0表示点在直线下方。2. 画线时每次 x 增加 1假设我们从左往右画线并且斜率满足01也就是说直线比较平缓。那么每走一步(x) 必然加 1。但是 (y) 有两个选择选择 1往右走(1,)这个像素可以叫做 EEast。选择 2往右上走(1,1)这个像素可以叫做 NENorth-East。所以问题变成下一步到底选 ((x1,y))还是选 ((x1,y1))3. 用中点判断选下面还是上面这两个候选像素中间有一个点(1,0.5)它就是下面像素和上面像素之间的中点。也就是(x1, y1) 上面的候选像素 (x1, y0.5) 中点 (x1, y) 下面的候选像素于是算法的判断逻辑是如果真实直线在这个中点上方那么上面的像素更接近直线选(1,1)如果真实直线在这个中点下方那么下面的像素更接近直线选(1,)所以我们只需要判断(1,0.5)的符号。图里写(01,00.5)这个 (d) 就是第一次的中点判别值。4. 为什么 d 0 时 y y 1图里的伪代码是if d 0 then y y 1 d d (x1 - x0) (y0 - y1) else d d (y0 - y1)这里的含义是当前中点是(1,0.5)计算()如果0说明这个中点在直线下方。也就是说真实直线比中点更高。因此上面的像素 ((x1,y1)) 更接近直线所以1如果≥0说明中点在直线上方或正好在线上那么下面的像素 ((x1,y)) 更合适所以 (y) 不变。5. 重点为什么后面不用重新算 f如果每一步都重新算(1,0.5)那就要做乘法、加法比较麻烦。但是观察这个函数(,)(0−1)(1−0)01−10它是一个一次函数。所以当 (x) 增加 1 时(f) 的变化量是固定的。情况一下一步只向右走也就是从(,)变成(1,)那么(1,)(,)(0−1)这就是图里第一条(1,)(,)(0−1)意思是横坐标加 1纵坐标不变时f 的值只需要加上 ((y_0-y_1))。情况二下一步向右上走也就是从(,)变成(1,1)那么(1,1)(,)(0−1)(1−0)这就是图里第二条(1,1)(,)(0−1)(1−0)意思是横坐标加 1纵坐标也加 1 时f 的值只需要加上两个增量。6. 把整个过程用人话说一遍假设当前已经画到了(,)下一列一定是1但是有两个候选像素(1,)和(1,1)于是看它们中间的点(1,0.5)如果真实直线在这个中点上方就选上面的像素。如果真实直线在这个中点下方就选下面的像素。判断中点在直线哪边用(1,0.5)如果0说明中点在直线下方选上面的像素所以1如果≥0说明中点在直线上方选下面的像素所以 (y) 不变。然后更新 (d)。关键是更新 (d) 不用重新算 (f)只需要加固定增量。7. 图里的伪代码整体含义y y0 d f(x0 1, y0 0.5) for x x0 to x1 do draw(x, y) if d 0 then y y 1 d d (x1 - x0) (y0 - y1) else d d (y0 - y1)对应的中文解释是从起点 ((x_0,y_0)) 开始。初始 (yy_0)。先计算第一个中点的判别值(01,00.5)每次画当前像素 ((x,y))。然后判断下一步应该走右边还是右上。如果 (d0)说明真实直线在中点上方所以 (y) 加 1。如果 (d 0)说明真实直线在中点下方或附近所以 (y) 不变。每次根据走法更新 (d)避免重新计算直线方程。
【图形学入门】直线光栅化——Bresenham / 中点画线算法
这里表达的是用一个“判别变量 d”来画直线每次不用重新代入直线方程算而是用增量更新。它本质上是在讲Bresenham / 中点画线算法。1. 这条直线先被写成隐式方程图里给了(,)(0−1)(1−0)01−10这其实就是过两点(0,0),(1,1)的直线方程。它的作用不是直接求 (ykxb)而是判断一个点 ((x,y)) 在直线的哪一侧。对于这条直线(,)0表示点正好在直线上。如果(,)0说明点在直线一侧。如果(,)0说明点在直线另一侧。在常见的数学坐标系下假设 (0k1)也就是直线从左下往右上走那么(,)0通常表示点在直线上方(,)0表示点在直线下方。2. 画线时每次 x 增加 1假设我们从左往右画线并且斜率满足01也就是说直线比较平缓。那么每走一步(x) 必然加 1。但是 (y) 有两个选择选择 1往右走(1,)这个像素可以叫做 EEast。选择 2往右上走(1,1)这个像素可以叫做 NENorth-East。所以问题变成下一步到底选 ((x1,y))还是选 ((x1,y1))3. 用中点判断选下面还是上面这两个候选像素中间有一个点(1,0.5)它就是下面像素和上面像素之间的中点。也就是(x1, y1) 上面的候选像素 (x1, y0.5) 中点 (x1, y) 下面的候选像素于是算法的判断逻辑是如果真实直线在这个中点上方那么上面的像素更接近直线选(1,1)如果真实直线在这个中点下方那么下面的像素更接近直线选(1,)所以我们只需要判断(1,0.5)的符号。图里写(01,00.5)这个 (d) 就是第一次的中点判别值。4. 为什么 d 0 时 y y 1图里的伪代码是if d 0 then y y 1 d d (x1 - x0) (y0 - y1) else d d (y0 - y1)这里的含义是当前中点是(1,0.5)计算()如果0说明这个中点在直线下方。也就是说真实直线比中点更高。因此上面的像素 ((x1,y1)) 更接近直线所以1如果≥0说明中点在直线上方或正好在线上那么下面的像素 ((x1,y)) 更合适所以 (y) 不变。5. 重点为什么后面不用重新算 f如果每一步都重新算(1,0.5)那就要做乘法、加法比较麻烦。但是观察这个函数(,)(0−1)(1−0)01−10它是一个一次函数。所以当 (x) 增加 1 时(f) 的变化量是固定的。情况一下一步只向右走也就是从(,)变成(1,)那么(1,)(,)(0−1)这就是图里第一条(1,)(,)(0−1)意思是横坐标加 1纵坐标不变时f 的值只需要加上 ((y_0-y_1))。情况二下一步向右上走也就是从(,)变成(1,1)那么(1,1)(,)(0−1)(1−0)这就是图里第二条(1,1)(,)(0−1)(1−0)意思是横坐标加 1纵坐标也加 1 时f 的值只需要加上两个增量。6. 把整个过程用人话说一遍假设当前已经画到了(,)下一列一定是1但是有两个候选像素(1,)和(1,1)于是看它们中间的点(1,0.5)如果真实直线在这个中点上方就选上面的像素。如果真实直线在这个中点下方就选下面的像素。判断中点在直线哪边用(1,0.5)如果0说明中点在直线下方选上面的像素所以1如果≥0说明中点在直线上方选下面的像素所以 (y) 不变。然后更新 (d)。关键是更新 (d) 不用重新算 (f)只需要加固定增量。7. 图里的伪代码整体含义y y0 d f(x0 1, y0 0.5) for x x0 to x1 do draw(x, y) if d 0 then y y 1 d d (x1 - x0) (y0 - y1) else d d (y0 - y1)对应的中文解释是从起点 ((x_0,y_0)) 开始。初始 (yy_0)。先计算第一个中点的判别值(01,00.5)每次画当前像素 ((x,y))。然后判断下一步应该走右边还是右上。如果 (d0)说明真实直线在中点上方所以 (y) 加 1。如果 (d 0)说明真实直线在中点下方或附近所以 (y) 不变。每次根据走法更新 (d)避免重新计算直线方程。
