聲明：歡迎任何人和組織轉載本blog中文章，但必須標記文章原始鏈接和作者信息。??

本文鏈接：http://blog.csdn.net/li_007/archive/2010/05/25/5622943.aspx

開拓進取的小烏龜------->CSDN點滴點點滴滴Blog

（一）數值微分(DDA)法

?

??? 設過端點P0(x0 y0)、P1(x1 y1)的直線段為L(P0 P1)，則直線段L的斜率?? L的起點P0的橫坐標x0向L的終點P1的橫坐標x1步進，取步長=1(個象素)，用L的直線方程y=kx+b計算相應的y坐標，并取象素點(x round(y))作為當前點的坐標。因為：

????yi+1 = kxi+1+b = k1xi+b+kDx?= yi+kDx

??? 所以，當Dx =1; yi+1 = yi+k。也就是說，當x每遞增1，y遞增k(即直線斜率)。

??? 根據這個原理，我們可以寫出DDA畫線算法程序。?void DrawLines::lineWithDDA(GLint x0, GLint y0, GLint xn, GLint yn, GLint hexColor) { GLfloat dx = xn - x0; GLfloat dy = yn - y0; GLint steps = 0; GLfloat deltaX = 0; GLfloat deltaY = 0; GLfloat x = x0; GLfloat y = y0; ofSetColor(hexColor); if(ABS(dx) > ABS(dy)) { steps = ABS(dx); } else { steps = ABS(dy); } deltaX = (GLfloat)dx / (GLfloat)steps; deltaY = (GLfloat)dy / (GLfloat)steps; glBegin(GL_POINTS); for(GLint i = 1; i <= steps; i ++) { x += deltaX; y += deltaY; glVertex2i(x, y); } glEnd(); }

（二）中點畫線法

???? 假定直線斜率k在0~1之間，當前象素點為（x_p y_p），則下一個象素點有兩種可選擇點P₁（x_p+1 y_p）或P₂（x_p+1 y_p+1）。若P₁與P₂的中點（x_p+1 y_p+0.5）稱為M，Q為理想直線與x=x_p+1垂線的交點。當M在Q的下方時，則取P₂應為下一個象素點；當M在Q的上方時，則取P₁為下一個象素點。這就是中點畫線法的基本原理。

???? 下面討論中點畫線法的實現。過點(x₀ y₀)、(x₁y₁)的直線段L的方程式為F(x y)=ax+by+c=0，其中，a=y₀-y₁ b=x₁-x₀ c=x₀y₁-x₁y₀，欲判斷中點M在Q點的上方還是下方，只要把M代入F（x，y），并判斷它的符號即可。為此，我們構造判別式:

???? d=F(M)=F(x_p+1 y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c

???? 當d<0時，M在L(Q點)下方，取P₂為下一個象素；

???? 當d>0時，M在L(Q點)上方，取P₁為下一個象素；

???? 當d=0時，選P₁或P₂均可，約定取P₁為下一個象素；

?????注意到d是x_p y_p的線性函數，可采用增量計算，提高運算效率。

???? 若當前象素處于d30情況，則取正右方象素P₁(x_p+1 y_p) 要判下一個象素位置，應計算 d₁=F(x_p+2 y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a，增量為a。若d<0時，則取右上方象素P₂(x_p+1 y_p+1)。要判斷再下一象素，則要計算d₂= F(x_p+2 y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=d+a+b ，增量為a＋b。畫線從(x₀ y₀)開始，d的初值 d₀=F(x₀+1 y₀+0.5)=F(x₀ y₀)+a+0.5b，因? F(x₀ y₀)=0，所以d₀=a+0.5b。

????? 由于我們使用的只是d的符號，而且d的增量都是整數，只是初始值包含小數。因此，我們可以用2d代替d來擺脫小數，寫出僅包含整數運算的算法程序。void DrawLines::lineWithMP(GLint x0, GLint y0, GLint xn, GLint yn, GLint hexColor) { GLint a = yn - y0; GLint b = -(xn - x0); GLint c = xn*y0 - x0*yn; GLint deltaA = 0; GLint deltaB = 0; if(0 != a) { deltaA = a / ABS(a); } if(0 != b) { deltaB = -1 * b / ABS(b); } GLfloat x = x0; GLfloat y = y0; ofSetColor(hexColor); if(ABS(a) < ABS(b)) { GLint steps = ABS(b); for(GLint i = 0; i < steps; i ++) { // 注意屏幕坐標系和世界坐標系的不同。也就是為什么是大于 0 if(0 < (a * (x + 1) + b * (y + 0.5) + c)) { y += 1 * deltaA; } x += 1 * deltaB; glBegin(GL_POINTS); glVertex2i(x, y); glEnd(); } } else { GLint steps = ABS(a); for(GLint i = 0; i < steps; i ++) { if(0 <= (a * (x + 1) + b * (y + 0.5) + c)) { x += 1 * deltaB; } y += 1 * deltaA; glBegin(GL_POINTS); glVertex2i(x, y); glEnd(); } } }

（三）Bresenham算法

???? ?Bresenham算法是計算機圖形學領域使用最廣泛的直線掃描轉換算法。仍然假定直線斜率在0~1之間，該方法類似于中點法，由一個誤差項符號決定下一個象素點。

????? 算法原理如下：過各行各列象素中心構造一組虛擬網格線。按直線從起點到終點的順序計算直線與各垂直網格線的交點，然后確定該列象素中與此交點最近的象素。該算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定該列的所求象素。

???? 設直線方程為y_i+1=y_i+k(x_i+1-x_i)+k。假設列坐標象素已經確定為x_i，其行坐標為y_i。那么下一個象素的列坐標為x_i＋1，而行坐標要么為y_i，要么遞增1為y_i＋1。是否增1取決于誤差項d的值。誤差項d的初值d₀＝0，x坐標每增加1，d的值相應遞增直線的斜率值k，即d＝d＋k。一旦? d≥1，就把它減去1，這樣保證d在0、1之間。當d≥0.5時，直線與垂線x=x_i＋1交點最接近于當前象素(x_i，y_i)的右上方象素(x_i＋1，y_i＋1)；而當d<0.5時，更接近于右方象素(x_i＋1，y_i)。為方便計算，令e＝d－0.5，e的初值為－0.5，增量為k。當e≥0時，取當前象素(x_i，y_i)的右上方象素(x_i＋1，y_i＋1)；而當e<0時，取(x_i，y_i)右方象素(x_i＋1，y_i)。

void DrawLines::lineWithBresenham(GLint x0, GLint y0, GLint xn, GLint yn, GLint hexColor) { GLint dx = xn - x0; GLint dy = yn - y0; GLint steps = 0; GLfloat slope = 0.0f; GLfloat x = x0; GLfloat y = y0; GLint deltaX = 0; GLint deltaY = 0; GLfloat e = -0.5f; if(0 != dx) { deltaX = dx / ABS(dx); slope = (GLfloat)dy / (GLfloat)dx; } else { slope = 65535; } if(0 != dy) { deltaY = dy / ABS(dy); } ofSetColor(hexColor); if(ABS(slope) <= 1) { steps = ABS(dx); glBegin(GL_POINTS); for(GLint i = 1; i <= steps; i ++) { x += deltaX; e += slope; if(0 < e) { y += deltaY; e -= slope / ABS(slope); } glVertex2i(x, y); } glEnd(); } else { steps = ABS(dy); slope = 1 / slope; glBegin(GL_POINTS); for(GLint i = 1; i <= steps; i ++) { y += deltaY; e += slope; if(0 > e) { x += deltaX; e -= slope / ABS(slope); } glVertex2i(x, y); } glEnd(); } }

?

? 測試代碼如下：

lineWithDDA(1, 500, 720, 500, 0xff0000); lineWithDDA(100, 550, 500, 50, 0xff0000); lineWithDDA(100, 150, 700, 550, 0xff0000); lineWithDDA(200, 20, 200, 680, 0xff0000); lineWithMP(1, 550, 720, 550, 0x0000ff); lineWithMP(100, 500, 500, 0, 0x0000ff); lineWithMP(100, 100, 700, 500, 0x0000ff); lineWithMP(250, 20, 250, 680, 0x0000ff); lineWithBresenham(1, 450, 720, 450, 0x00ff00); lineWithBresenham(100, 600, 500, 100, 0x00ff00); lineWithBresenham(100, 200, 700, 600, 0x00ff00); lineWithBresenham(150, 20, 150, 680, 0x00ff00);

?

結果視圖如下：

轉載于:https://www.cnblogs.com/leezhm/archive/2010/05/25/2560305.html

總結

以上是生活随笔為你收集整理的基于OpenGL的三种直线生成算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。