再談繪製直線

之前已經在[從零開始計算機圖形學]之七畫線 寫過繪製直線了，現在再來仔細的看一下這個問題。

此篇文章思想來自此處：

tinyrenderer?

github.com

嘗試一： 按照參數繪製直線

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
for (float t=0.; t<1.; t+=.01) {
int x = x0 + (x1-x0)*t;
int y = y0 + (y1-y0)*t;
image.set(x, y, color);
}
}

這裡的問題有兩個：

  • 效率低
  • t如何控制

t取大了畫出來的並不是線，而是一堆點。t取小了會浪費，有很多重複的x和y。

嘗試二： 按x的增加畫線

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
for (int x=x0; x<=x1; x++) {
float t = (x-x0)/(float)(x1-x0);
int y = y0 + (y1 - y0)*t;
image.set(x, y, color);
}
}

我們想著要節約，就每次 x 增加1，然後來畫y。

這樣畫線是對的因為我們假設 y = mx + b , 直線斜率m， 截距b

frac{y1 - y0}{x1 - x0} = m\

y0 = mx0 + b

y = y0 + frac{y1 - y0}{x1 - x0}(x - x0)

所以

y = y0 + mx - mx0 = mx + (y0 - mx0) = mx + b

同時它的問題是我們也已經指出:

  • 如果直線斜率太大，比如 m = 3, 那麼x每增加1個像素，y增加3個像素，這樣畫出來就是分離的點。
  • 只能適用於 x0 < x1的狀況

嘗試三

所以想法是：

  • 如有必要交換 x0 和 x1，這樣使得 x0 一定小於 x1
  • 如果斜率比較大，則交換 x 和 y

看代碼：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) { // if the line is steep, we transpose the image
 std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) { // make it left?to?right
 std::swap(x0, x1);
std::swap(y0, y1);
}
for (int x=x0; x<=x1; x++) {
float t = (x-x0)/(float)(x1-x0);
int y = y0 + (y1 - y0)*t;
if (steep) {
image.set(y, x, color); // if transposed, de?transpose
 } else {
image.set(x, y, color);
}
}
}

這樣就可以完善上述出現的問題來畫線了。

嘗試四：優化

其實上述代碼加上 compiler 本身的優化已經可以很快了 (g++ -O3)，但是因為歷史原因我們繼續來看它的優化畫法，首先是上述演算法中

  • 每次都出現了相同的被除數 → float t = (x-x0)/(float)(x1-x0)
  • 我們只需要畫在整數的像素上

我們現在一定有 |x1 - x0| geq |y1 - y0| , 畢竟如果 |x1 - x0| < |y1 - y0| 都已經被我們交換了。

我們令

derror = frac{|dy|}{|dx|}

那麼這個derror就是x每增加1，y的變化量的絕對值，我們知道derror一定小於1大於0.

我們令error來表示y應該有的偏移量, 每當error > 0.5，我們就把y增加（或者減少）1，同時把error減少1.

看代碼：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) {
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
float derror = std::abs(dy/float(dx));
float error = 0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error += derror;
if (error>.5) {
y += (y1>y0?1:-1);
error -= 1.;
}
}
}

理解的話，當偏移量大於0.5時候，我們根據線是朝上或者朝下來畫點，同時把error - 1.重置這個偏移量。

或者看下方：

y = y + error = (y + 1) + (error - 1)

因為每次變化之後y都增加或者減少了1，所以error這個偏移量需要重置。

最後一搏

上一版中出現了浮點數 derror 和 0.5：

derror = frac{|dy|}{|dx|}

我們用另一個數來替換這個 derror，叫它 error2. 令它等於 derror * dx * 2.然後在相應的error和比較地方做修正：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) {
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
int derror2 = std::abs(dy)*2;
int error2 = 0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error2 += derror2;
if (error2 > dx) {
y += (y1>y0?1:-1);
error2 -= dx*2;
}
}
}

優化完成，done！

這就是大名鼎鼎的Bresenhams line algorithm.

不過正如之前說的，其實版本3已經被compiler優化的很不錯了。

python-pillow/Pillow畫線也是用的這個演算法。


推薦閱讀：
相关文章