various
计算机图形学
直线的扫描转换
数值微分法 DDA line algorithm
对于斜率的绝对值小于1的直线，从左端点P0(x0,y0)开始，x每增加1，y就增加k
void DDA(int x0, int y0, int x1, int y1) {
float k = 1. * (y1 - y0) / (x1 - x0);
for (; x0 <= x1; x0++) {
drawPixel(x0, y0);
y0 += k;
}
}
中点画线法 Midpoint line algorithm
直线上点(x, y)满足F(x, y) = ax + by + c = 0（其中a = y0 - y1，b = x1 - x0，c = x0y1 - x1y0），直线下方的点算得F(x, y) < 0，直线上方的点算得F(x, y) > 0。
斜率在0~1的曲线，x每增加1，y会增加1或不变。
在确定好点(xp, yp)的位置后，要确定这个点右边的点是P1(xp + 1, yp)还是P2(xp + 1, yp + 1)，可以取P1和P2的中点M(xp + 1, yp + 0.5)，看F(M)的正负。
- 如果F(M) < 0，说明点M在直线的下方，因此直线距点P2更近。
- 如果F(M) > 0，说明直线距离点P1更进近。
- 如果F(M) = 0，则M正好在直线上，人为规定此时选取P1（和>0时相同）
void Midpoint(int x0, int y0, int x1, int y1) {
int a = y0 - y1, b = x1 - x0, c = x0 * y1 - x1 * y0;
for (; x0 <= x1; x0++) {
float f = a * x0 + b * (y0 + 0.5) + c;
if (f < 0) y0++;
drawPixel(x0, y0);
}
}
接下来我们优化f的计算：其实新的f可以通过上次的f求得。
设当前我们画了点L1，接下来该画点L2（L2是L1右边相邻的点）。记(xl1, yl1 + 0.5)为M1，记(xl2, yl2 + 0.5)为M2，记F(M1)为f1，记F(M2)为f2。 则f1 = a * xm1 + b * ym1 + c, f2 = a * xm2 + b * ym2 + c。 ∴f2 - f1 = a * (xm2 - xm1) + b * (ym2 - ym1) ∴f2 = f1 + a * (xm2 - xm1) + b * (ym2 - ym1)
因为m2是m1右边的下一个点，所以xm2 - xm1 = 1 而ym2 - ym1 = 1 或 0 当m2是m1右上方的点时，ym2 - ym1 = 1，此时f1 < 0，f2 = f1 + a 当m2是m1正右边的点时，ym2 - ym1 = 0，此时f1 ≥ 0，f2 = f1 + a + b
通过以上方法我们即可用前一个点的f值求得后一个点的f值，初始值f0 = F(x0, y + 0.5) = a + 0.5b
void midPoint(int x0, int y0, int x1, int y1) {
int a = y0 - y1, b = x1 - x0;
float f = a + 0.5 * b; // 斜率在0~1，∴f > 0，符合初始条件中点在直线上方
for (; x0 <= x1; x0++) {
if (f < 0) y0++, f += a;
else f += a + b;
drawPixel(x0, y0);
}
}
每次f的增量都是整数，只有初始值的时候f = a + 0.5 * b 可能为小数。 因此我们可以令F(x, y) = 2 * a * x + 2 * b * y + 2 * c，这样就避免了小数问题。
void midPoint(int x0, int y0, int x1, int y1) {
int a = y0 - y1, b = x1 - x0;
int f = 2 * a + b; // 此处就可以改为int了
for (; x0 <= x1; x0++) {
if (f < 0) y0++, f += 2 * a;
else f += 2 * (a + b);
drawPixel(x0, y0);
}
}
Bresenham算法 Bresenham’s line algorithm
记直线方程为y=kx+b。
误差项d初始值为0，x每增加1，d就增加k 当d ≥ 1 时，就让 d 减一，保证d在0~1之间
- 如果 d ≥ 0.5，那么应该取下方的点
- 如果 d < 0.5，那么应该取上方的点
小改进： 令 e = d - 0.5，则e的范围是[-0.5, 0.5)，初始值-0.5，e ≥ 0.5时减一，判断e的正负来判断取上方的点还是下方的点。
void bresenham(int x0, int y0, int x1, int y1) {
float k = (y1 - y0) / (x1 - x0);
float e = -0.5;
for (; x0 <= x1; x0++) {
drawPixel(x0, y0);
e += k;
if (e >= 0) e -= 1, y0++;
}
}
改进： 上述运算中同样用到了小数。但不难发现e的判断只与符号有关。 因此我们可以让 e’ = 2 * dx * e，则初始值e’ = -0.5 * 2 * dx = -dx，e’每次加上2 * dx * k = 2 * dy，e’ ≥ 0 时应减去1 * 2 * dx = 2 * dx。
void bresenham(int x0, int y0, int x1, int y1) {
int dx = x1 - x0;
int e = -dx;
for (; x0 <= x1; x0++) {
drawPixel(x0, y0);
e += 2 * dy;
if (e >= 0) e -= 2 * dx, y0++;
}
}