c語言劃線

① 求一用C語言畫直線的程序

不調用畫圖 API，用C 或 C++ 如何實現畫一條線？
Milo Yip：如何開始用 C++ 寫一個光柵化渲染器？
我嘗試用不同技術實現畫直線的方法（完整源代碼在 miloyip/line），此文簡單介紹個中思路。本文的代碼採用 C 語言、標准庫及極簡的 PNG 編碼函數 svpng()，沒有使用其他 API。

1. Bresenham 演算法
Bresenham直線演算法 [1] 是最簡單的直線光柵化（rasterization）演算法。


Bresenham 直線
如果像上圖，直線的高度小於寬度，那麼 Bresenham 直線演算法會為 軸每個坐標填入一個像素，繪畫每個像素時按斜率判斷 是否需要調整。整個演算法可以避開浮點數運算，只用整數運算實現。以下是一個簡單實現：

// Modified from https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#C
void bresenham(int x0, int y0, int x1, int y1) {
int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
int dy = abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
int err = (dx > dy ? dx : -dy) / 2;

while (setpixel(x0, y0), x0 != x1 || y0 != y1) {
int e2 = err;
if (e2 > -dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}
為了測試不同角度，我做了一個測試用例：

int main() {
memset(img, 255, sizeof(img));
float cx = w * 0.5f - 0.5f, cy = h * 0.5f - 0.5f;
for (int j = 0; j < 5; j++) {
float r1 = fminf(W, H) * (j + 0.5f) * 0.085f;
float r2 = fminf(W, H) * (j + 1.5f) * 0.085f;
float t = j * PI / 64.0f;
for (int i = 1; i <= 64; i++, t += 2.0f * PI / 64.0f) {
float ct = cosf(t), st = sinf(t);
bresenham((int)(cx + r1 * ct), (int)(cy - r1 * st), (int)(cx + r2 * ct), (int)(cy - r2 * st));
}
}
svpng(fopen("line_bresenham.png", "wb"), W, H, img, 0);
}
完整代碼 line_bresenham.c

渲染結果及中間局部放大：



2. 采樣方法
Bresenham 直線演算法有 3 個問題：

不能控制直線寬度；
坐標為整數；
只能對像素寫入一個顏色，只用單色會有嚴重的鋸齒效果。
在圖形學中，除了以逐個圖元（如直線）方式渲染，我們還可以通過對每個像素進行采樣（sampling），換句話說，我們可對整個圖像逐像素詢問：「這個像素的顏色是什麼？」

用采樣方式畫直線時，我們可以用一個具有面積的形狀去表示「直線」，例如是長方形。但在本文中，我們使用膠囊體（capsule）去表示直線。這樣就能解決上面前兩個問題：(1) 可用膠囊體半徑設置直線的寬度；(2) 坐標可以為浮點數。不過，用最簡單的采樣方式，我們需要在每像素查詢所有圖元是否佔有該像素，效率很低。