開一個新坑，記錄從零開始學習圖形學的程序，現在還是個正在學習的萌新，寫的不好請見諒，

首先從最基礎的直線生成演算法開始，當我們要在螢屏上畫一條直線時，由于螢屏由一個個像素組成，所以實際上計算機顯示的直線是由一些像素點近似組成的，直線生成演算法解決的是如何選擇最佳的一組像素來顯示直線的問題，

對這個問題，首先想到的最暴力的方法當然是從直線起點開始令x或y每次增加1直到終點，每次根據直線方程計算對應的函式值再四舍五入取整，即可找到一個對應的像素，但這樣做每一步都要進行浮點數乘法運算，效率極低，所以出現了DDA和Bresenham兩種直線生成演算法，

數值微分法（DDA演算法）

DDA演算法主要是利用了增量的思想，通過同時對x和y各增加一個小增量，計算下一步的x和y值，

根據上式可知$\bigtriangleup x$=1時，x每遞增1，y就遞增k，所以只需要對x和y不斷遞增就可以得到下一點的函式值，這樣避免了對每一個像素都使用直線方程來計算，消除了浮點數乘法運算，

代碼實作：

#include<Windows.h>#include<iostream>#include<cmath>using namespace std;const int ScreenWidth = 500;const int ScreenHeight = 500;LRESULT CALLBACK WinProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam){    switch (message) {    case WM_CLOSE:        DestroyWindow(hWnd);        break;    case WM_DESTROY:        PostQuitMessage(0);        break;    default:        return DefWindowProc(hWnd, message, wParam, lParam);        break;    }    return 0;}void DDALine(int x0,int y0,int x1,int y1,HDC hdc){    int i=1;    float dx, dy, length, x, y;    if (fabs(x1 - x0) >= fabs(y1 - y0))        length = fabs(x1 - x0);    else        length = fabs(y1 - y0);    dx = (x1 - x0) / length;    dy = (y1 - y0) / length;    x = x0;    y = y0;    while (i<=length)    {        SetPixel(hdc,int(x + 0.5), ScreenHeight-40-int(y + 0.5), RGB(0, 0, 0));        x = x + dx;        y = y + dy;        i++;    }}int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int nShowCmd){    WNDCLASS wcs;    wcs.cbClsExtra = 0;                                         // 視窗類附加引數      wcs.cbWndExtra = 0;                                         // 視窗附加引數      wcs.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);    // 視窗DC背景      wcs.hCursor = LoadCursor(hInstance, IDC_CROSS);             // 滑鼠樣式      wcs.hIcon = LoadIcon(NULL, IDI_WINLOGO);                    // 視窗icon      wcs.hInstance = hInstance;                                  // 應用程式實體      wcs.lpfnWndProc = (WNDPROC)WinProc;    wcs.lpszClassName = "CG";    wcs.lpszMenuName = NULL;    wcs.style = CS_VREDRAW | CS_HREDRAW;    RegisterClass(&wcs);    HWND hWnd;    hWnd = CreateWindow("CG","DrawLine", WS_OVERLAPPEDWINDOW, 200, 200, ScreenWidth, ScreenHeight, NULL, NULL, hInstance, NULL);    ShowWindow(hWnd, nShowCmd);    UpdateWindow(hWnd);    MSG msg;    // hdc init    HDC hdc = GetDC(hWnd);    // 繪圖，畫一條從點（0,0）到（100,350）的直線    DDALine(0, 0, 100, 350, hdc);// 訊息回圈      while (GetMessage(&msg, 0, NULL, NULL)) {        TranslateMessage(&msg);        DispatchMessage(&msg);    }    // release    ReleaseDC(hWnd, hdc);    return 0;}

以上是DDA演算法的實作，WinMain和WinProc函式是Windows API編程特有的，我們只需要關注DDALine這個繪圖函式，該函式傳入兩個點的坐標畫出一條直線，

首先判斷起點和終點間x軸和y軸哪個軸向的跨度更大（斜率范圍），為了防止丟失像素，應讓跨度更大的軸向每次自增1，這樣能獲得更精確的結果，

接下來就沒什么好說的，依次讓x和y加上增量然后四舍五入就行了，浮點數四舍五入可以直接用int(x+0.5)計算，setPixel函式用于設定像素的顏色值（需要傳入視窗的hdc句柄），由于Windows視窗坐標的原點在左上角，所以拿視窗高度減去y值就可以轉換成平常習慣的左下角坐標系了，

運行結果:

Bresenham演算法

DDA演算法盡管消除了浮點數乘法運算，但仍存在浮點數加法和取整操作，效率仍有待提高，1965年Bresenham提出了更好的直線生成演算法，成為了時至今日圖形學領域使用最廣泛的直線生成演算法，該演算法采用增量計算，借助一個誤差量的符號確定下一個像素點的位置，該演算法中不存在浮點數，只有整數運算，大大提高了運行效率，

 我們先只考慮斜率在0-1之間的情況，從線段左端點開始處理，并逐步處理每個后續列，每確定當前列的像素坐標$(x_{i},y_{i})$后，那么下一步需要在列$x_{i+1}$上確定y的值，此時y值要么不變，要么增加1，這是因為斜率在0-1之間，x增長比y快，所以x每增加1，y的增量是小于1的，

對于左端點默認為其像素坐標，下一列要么是右方的像素，要么是右上方的像素，設右上方像素到直線的距離為d2，右方像素到直線的距離為d1，顯然只需要判斷直線離哪個像素點更近也就是d1-d2的符號即可找到最佳像素，

 所以可以推出以下式子：

 其中$\bigtriangleup x$起點到終點x軸上距離，$\bigtriangleup y$為y軸上距離，k=$\bigtriangleup y$/$\bigtriangleup x$，c是常量，與像素位置無關，

令$e_{i}$=$\bigtriangleup x$(d1-d2),則$e_{i}$的計算僅包括整數運算，符號與d1-d2一致，稱為誤差量引數，當它小于0時，直線更接近右方像素，大于0時直線更接近右上方像素，

可利用遞增整數運算得到后繼誤差量引數，計算如下：

 所以選擇右上方像素時($y_{i+1}$-$y_{i}$=1)：

 選擇右方像素時($y_{i+1}$-$y_{i}$=0)：

 初始時，將k=$\bigtriangleup y$/$\bigtriangleup x$代入$\bigtriangleup x$(d1-d2)中可得到起始像素的第一個引數：

斜率在0-1之間的Bresenham演算法代碼實作（替換上面程式中DDALine即可）：

void Bresenham_Line(int x0, int y0, int x1, int y1, HDC hdc){    int dx, dy, e, x=x0, y=y0;    dx = x1 - x0; dy = y1 - y0;    e = 2 * dy - dx;    while (x<=x1)    {        SetPixel(hdc, x, ScreenHeight-40-y, RGB(0, 0, 0));        if (e >= 0)//選右上方像素        {            e = e + 2 * dy - 2 * dx;            y++;        }        else//選右方像素        {            e = e + 2 * dy;        }        x++;    }}

運行結果：

要實作任意方向的Bresenham演算法也很容易，斜率在0-1之間意味著直線位于坐標系八象限中的第一象限，如果要繪制第二象限的直線，只需要利用這兩個象限關于直線x=y對稱的性質即可，可以先將x和y值互換先在第一象限進行計算，然后呼叫SetPixel時再將x和y值反過來，在第二象限中繪制，其他象限也是類似的思路，

繪制任意方向直線的Bresenham演算法代碼實作：

void Bresenham_Line(int x0, int y0, int x1, int y1, HDC hdc){    int flag = 0;    int dx = abs(x1 - x0);    int dy = abs(y1 - y0);    if (dx == 0 && dy == 0)   return;    if (abs(x1 - x0) < abs(y1 - y0))    {        flag = 1;        swap(x0, y0);        swap(x1, y1);        swap(dx, dy);    }    int tx = (x1 - x0) > 0 ? 1 : -1;    int ty = (y1 - y0) > 0 ? 1 : -1;    int x = x0;        int y = y0;    int dS = 2 * dy;   int dT = 2 * (dy - dx);    int e = dS - dx;    SetPixel(hdc, x0, y0, RGB(0,0,0));    while (x != x1)    {        if (e < 0)            e += dS;        else        {            y += ty;  e += dT;        }        x += tx;        if (flag)            SetPixel(hdc, y, ScreenHeight - 40 - x, RGB(0, 0, 0));        else            SetPixel(hdc, x, ScreenHeight - 40 - y, RGB(0, 0, 0));    }}

直線生成演算法就到這里啦，接下來也要加油學習圖形學~

標籤：其他

上一篇：DirectX：色彩基礎

下一篇：圖形學入門(2)——圓生成演算法（中點畫圓法）