電腦圖形學經典算法：DDA 與 Bresenham 畫線算法原理與 C++ 實現

問題定義

給定兩端點 P0(x0,y0)、P1(x1,y1)，在離散像素網格上繪製直線段。核心挑戰：僅用整數運算、避免浮點除法、最小化誤差。

DDA（Digital Differential Analyzer）算法

數學基礎

直線方程 y = kx + b，斜率 k = (y1-y0)/(x1-x0)。假設 |k| ≤ 1，x 每增 1，y 增 k。實際像素座標需四捨五入：round(y)。

C++ 實現

void drawLineDDA(int x0, int y0, int x1, int y1, Color color) {
    int dx = x1 - x0, dy = y1 - y0;
    int steps = std::max(std::abs(dx), std::abs(dy));
    float xInc = dx / (float)steps, yInc = dy / (float)steps;
    float x = x0, y = y0;
    for (int i = 0; i <= steps; ++i) {
        setPixel(round(x), round(y), color);
        x += xInc; y += yInc;
    }
}

缺點

• 每步需浮點加法 + 四捨五入
• 斜率計算需除法，dx=0 需特判
• 累積誤差導致線條抖動

Bresenham 畫線算法：整數運算的極致

核心思想：誤差項判決

假設當前像素 (x,y)，下一步只能選 (x+1,y)（東）或 (x+1,y+1)（東北）。決策變數 d 表示理想直線與兩候選像素中心的距離差：

• d < 0 → 理想線更靠近東像素 → 選 (x+1,y)
• d ≥ 0 → 更靠近東北像素 → 選 (x+1,y+1)

推導整數誤差項

初始 d = 2*dy - dx（對應 -0.5*2*dx）。迭代更新：

• 選東：d += 2*dy
• 選東北：d += 2*(dy - dx)，y++

全程僅整數加減乘，零除法、零浮點。

完整 C++ 實現（八方向通用）

void drawLineBresenham(int x0, int y0, int x1, int y1, Color color) {
    int dx = std::abs(x1 - x0), dy = std::abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1, sy = (y0 < y1) ? 1 : -1;
    int err = dx - dy;

    while (true) {
        setPixel(x0, y0, color);
        if (x0 == x1 && y0 == y1) break;
        int e2 = 2 * err;
        if (e2 > -dy) { err -= dy; x0 += sx; }
        if (e2 < dx)  { err += dx; y0 += sy; }
    }
}

此版本處理所有八象限，無需分支交換 x/y，源自 err = dx - dy 的對稱性。

擴展：畫圓與畫橢圓

Midpoint Circle Algorithm

利用八向對稱性，僅計算 1/8 圓弧。決策變數 d = 1 - r，迭代更新：

• d < 0：d += 2*x + 3
• d ≥ 0：d += 2*(x - y) + 5，y--

Bresenham 橢圓算法

分兩區域：斜率 > -1 與 < -1，決策變數分別推導，同樣純整數運算。

現代 GPU 繪製管線對比

教學價值總結

• 展示「將浮點幾何問題轉化為整數決策」的經典技巧
• 誤差項遞推思想廣泛應用於：光柵化、數控機床插補、數位訊號處理
• 理解 GPU 光柵化單元的前世今生

Bresenham 算法以「零浮點、零除法、極小誤差」三大特性，成為電腦圖形學教科書的永恆經典。