線生成算法>
一、DDA算法
數字微分分析儀（digital differential analyzer, DDA）方法是一種線段掃描轉換算法。
假設線段的起點坐标是（xstart, ystart），終點坐标是（xend, yend）,線段的斜率是m,水準方向增量是dx,垂直方向增量是dy;
（1）、算法概括
1*、輸入線段兩個端點的像素位置，端點位置間的水準和垂直內插補點賦給參數dx,dy；
2*、判斷是x方向、y方向上的增量，誰更大（該方向變化更快），dx,dy中絕對值大的确定參數steps（循環執行次數）值;
3*、确定沿線段生成下一個像素位置的每一步所需的偏移量，從像素位置（x0,y0）開始，循環該過程steps次。
每一步增量的确定規則：
如果dx絕對值大于dy的絕對值，且xstart小于xend: x、y方向上的增量值分别是1和m;
如果dx絕對值大于dy的絕對值，且xstart大于xend: x、y方向上的增量值分别是-1和-m;
如果dx絕對值小于dy的絕對值，且xstart小于xend: x、y方向上的增量值分别是1/m和1;
如果dx絕對值小于dy的絕對值，且xstart大于xend: x、y方向上的增量值分别是-1/m和-1;
（2）、算法描述
#include < stdlib.h>
#include < math.h >
inline int round(const float a){ return (int)(a+0.5f);};
void lineDDA( int x0, int y0, int xEnd, int yEnd)
{
int dx = xEnd - x0;
int dy = yEnd - y0;
int steps, k;
float xIncrement, yIncrement, x = x0, y = y0;
(int)fabs((float)dx) > (int)fabs((float)dy) ? steps = fabs((float)dx) : steps = fabs((float)dy);
xIncrement = float(dx) / float(steps);
yIncrement = float(dy) / float(steps);
setPixel( round(x), round(y));//該函數用于設定像素點，不同的系統可能函數名稱不同。
for( k=0; k<steps; k++)
{
x += xIncrement;
y += yIncrement;
setPixel(round(x), round(y));
}
return ;
}
（3）、優缺點
DDA方法計算像素位置要比直接使用直線方程計算的速度更快。但是在浮點增量的連續疊加中，取整誤差的積累使得對于較長線段所計算的像素位置偏離實際線段，而且該過程中的取整操作和浮點運算仍然十分耗時。可以通過将增量m和1/m分離成整數和小數部分，進而使所有的計算都簡化為整數操作來改善DDA算法的性能。
二、Bresenham畫線算法
Bresenham畫線算法是由Bresenham提出的一種精确而有效的光栅線生成算法，該算法僅僅使用增量整數計算。該算法也可以用于顯示圓和其他曲線。
該算法在沿線路徑方向的取樣位置Xk+1，使用Dlower和Dupper來辨別兩個像素與數學上的線路徑的偏差，并确定兩個像素中哪一個更接近線路徑，然後繪制更接近線路徑的那個像素。
（1）、算法概括
|m|<1時的Bresenham畫線算法：
1*、輸入線段的兩個端點，并将左端點存儲在（x0,y0）中;
2*、将（x0,y0）裝入幀緩存中，畫出第一個點;
3*、計算常量dx、dy、2dy和2dy-2dx,并得到決策參數的第一個值：p0 = 2dy - dx;
4*、從k=0開始，在沿線路徑的每個Xk處，進行一下檢測：
如果Pk <0 ,下一個要繪制的點是（Xk+1, Yk）,并且Pk+1= Pk +2dy;
否則，下一個要繪制的點是（Xk+1, Yk+1）,并且Pk+1= Pk + 2dy - 2dx;
5*、重複步驟4，共dx-1次。
（2）、算法實作（斜率0<k<1.0）
#include <stdlib.h>
#include <math.h>
/* Bresenham line-drawing procedure for |m| < 1.0 */
void lineBres(int x0, int y0, int xEnd, int yEnd)
{
int dx = fabs(xEnd - x0), dy = fabs(yEnd - y0);
int p = 2 * dy - dx ;
int twoDy = 2 * dy, twoDyMinusDx = 2 * (dy - dx);
int x, y;
/* Determine which endpoint to use as start position .*/
if(x0 > xEnd)
{
x = xEnd;
y = yEnd;
xEnd = x0;
}
else
{
x = x0;
y = y0;
}
setPixel(x, y);
while( x <xEnd )
{
x++;
if( p<0 )
p += twoDy;
else
{
y++;
p += twoDyMinusDx;
}
setPixel(x, y);
}
}
Bresenham對于任意斜率具有通用性。對于斜率為正值且大于1.0的線段，隻要交換x、y方向上的規則，即可使用上述算法。水準線、垂直線和對角線，它們都可以直接裝入幀緩存而無需進行畫線算法處理。
<圓生成算法>
三、中點畫圓算法
（1）、背景
利用笛卡爾坐标系或極坐标系的圓方程以及利用圓的對稱性來繪制圓，仍然是效率較差的，比較耗時的。因為使用笛卡爾坐标系的圓方程畫圓，需要乘法和平方根運算，利用極坐标的圓方程來畫圓，需要乘法和三角運算，這些運算都是非常耗時的。
将光栅系統的Bresenham畫線算法移植為畫圓算法，可以通過比較像素與圓的距離的平方而避免平方根運算；
然而，更加優秀的算法：中點畫圓算法，可以不做平方運算而直接比較距離。該算法的基本思想是檢驗兩個像素間的中間位置以确定該中心是在圓邊界之内還是之外。這種方法更易應用于其他圓錐曲線，而且對于整數圓半徑，中點方法生成與Bresenham畫圓算法相同的像素位置。而且使用中點檢驗時，沿任何圓錐截面曲線所确定的像素位置，其誤差限制在像素間隔的1/2以内。
（2）、概述
中點畫圓算法的步驟：
1*、輸入圓半徑r和圓心(Xc,Yc),并得到圓周（圓心在原點）上的第一個點：（x0,y0）=( 0, r);
2*、計算決策參數的初始值：p0 = 5/4 - r;
3*、在每個Xk位置,從k=0開始，完成下列測試：假如Pk <0, 圓心在（0,0）的圓的下一點為（Xk+1, Yk）,并且Pk+1= Pk + 2Xk+1+ 1,否則，圓的下一個點是（Xk + 1, Yk- 1），并且Pk+1 = Pk + 2Xk+1 + 1 - 2Yk+1 ,其中2Xk+1= 2Xk +2 且2Yk+1= 2Yk -2。
4*、确定在其他七個八分圓中的對稱點。
5*、将每個計算出的像素位置（x，y）移動到圓心在（Xc，Yc）的圓路徑上，并畫坐标值：x = x+Xc， y = y + Yc;
6*、重複步驟3到步驟5，直至x >= y。
（3）、算法描述
#include <GL/glut.h>
class screenPt
{
private:
GLint x, y;
public:
screenPt()
{
x = y = 0;
}
void setCoords( GLint xCoordValue, GLint yCoordValue)
{
x = xCoordValue;
y = yCoordValue;
}
GLint getx() const
{
return x;
}
GLint gety() const
{
return y;
}
void incrementx()
{
x++;
}
void decrementy()
{
y--;
}
};
void setPixel( GLint xCoord, GLint yCoord)
{
glBegin(GL_POINTS);
glVertex2i(xCoord, yCoord);
glEnd();
}
void circleMidpoint(GLint xc, GLint yc, GLint radius)
{
screenPt circPt;
GLint p = 1 - radius;
circPt.setCoords(0, radius);
void circlePlotPoints( GLint , GLint , screenPt);
circlePlotPoints(xc, yc, circPt);
while(circPt.getx() < circPt.gety() )
{
circPt.incrementx();
if( p<0 )
p += 2 * circPt.getx() + 1;
else
{
circPt.decrementy();
p += 2 * ( circPt.getx() - circPt.gety() ) +1;
}
circlePlotPoints(xc, yc, circPt);
}
}
<橢圓生成算法>
四、中點橢圓算法
（1）、算法概括
中點橢圓算法的步驟：
1* 、輸入 橢圓的x軸半徑rx, y軸半徑ry 和橢圓中心（xc, yc）,并得到橢圓（中心在原點）上的第一個點： （x0, y0）= (0, ry);
2*、計算區域1中決策參數的初始值：p10 = ry^2 - rx^2*ry + (rx^2)/4;
3*、在區域1的每個xk位置，從k =0開始，完成以下測試：假如p1k <0, 沿中心在（0,0）的橢圓的下一點為（xk+1, yk）,并且P1k+1= p1k + 2*ry^2* xk+1+ ry^2,否則，沿橢圓的下一個點為（xk + 1, yk -1）,并且p1k+1= p1k + 2*ry^2*xk+1 -2* rx^2*yk+1+ry^2, 其中2* ry^2*xk+1= 2* ry^2*xk + 2* ry^2, 2*rx^2 * yk+1= 2*rx^2 *yk - 2* rx^2，并且直到2*ry^2*x >= 2* ry^2*y。
4*、使用區域1中計算的最後點（x0, y0）來計算區域2中參數的初始值：p20 = ry^2(x0 + 1/2)^2 + rx^2 *(y0-1)^2 - rx^2* ry^2。
5*、在區域2的每個yk位置處，從 k=0開始，完成以下測試：假如p2k >0, 沿中心為（0,0）的橢圓的下一個點為（xk,yk-1）,并p2k+1= p2k - 2*rx^2* yk+1+ rx^2, 否則，沿橢圓的下一個點為（xk+1, yk -1）,并且p2k+1= p2k + 2* ry^2* xk+1- 2* rx^2*yk+1+ rx^2,使用與區域1中相同的x和y增量進行計算，直到y = 0；
6*、确定其他三個象限中的對稱點。
7*、将計算出的每個像素位置（x,y）移動到中心在（xc,yc）的橢圓軌迹上，并按坐标值繪制點：x = x+xc, y = y+yc。
（2）、算法描述
inline int round( const float a){ return int (a + 0.5); }
void ellipseMidpoint( int xCenter, int yCenter, int Rx, int Ry)
{
int Rx2 = Rx * Rx;
int Ry2 = Ry * Ry;
int twoRx2 = 2 * Rx2;
int twoRy2 = 2 * Ry2;
int p;
int x = 0;
int y = Ry;
int px = 0;
int py = twoRx2 * y;
void ellipsePlotPoints( int, int, int, int);
ellipsePlotPoints( xCenter, yCenter, x, y);
/*Region 1*/
p = round(Ry2 - (Rx2 * Ry) + (0.25 * Rx2));
while(px <py)
{
x++;
px += twoRy2;
if( p<0 )
p += Ry2 +px;
else
{
y--;
py -= twoRx2;
p += Ry2 +px - py;
}
ellipsePlotPoints(xCenter, yCenter, x, y);
}
/*Region 2*/
p = round(Ry2 * (x+0.5) * (x+0.5) + Rx2 * (y-1)*(y-1) - Rx2 * Ry2);
while( y>0 )
{
y--;
py -= twoRx2;
if( p>0 )
p += Rx2 - py;
else
{
x++;
px += twoRy2;
p += Rx2 - py + px;
}
ellipsePlotPoints(xCenter, yCenter, x, y);
}
}
void ellipsePlotPoints(int xCenter, int yCenter, int x, int y)
{
setPixel(xCenter + x, yCenter + y);
setPixel(xCenter - x, yCenter + y);
setPixel(xCenter + x, yCenter - y);
setPixel(xCenter - x, yCenter - y);
}
![配置 x64 glew glfw并運作示例[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)