这里不仔细讲原理，只是把我写的算法发出来，跟大家分享下，如果有错误的话，还请大家告诉我，如果写的不好，也请指出来，一起讨论进步。
基本思想: 先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边界除外)勾画出来，然后将着色的像素点依x坐标递增的顺序两两配对，再将每一对像素所构成的扫描线区间内的所有像素置为填充色。具体分为两个步骤;
(1) 打标记。对多边形的每条边进行直线扫描转换。
(2) 填充。 对每条与多边形相交的扫描线，依从左到右顺序，按“左闭右开”的原则对扫描线上的像素点进行填充。使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真，否则为假。inside初值为假，第当当前访问像素为被打上标记的点时就把inside取反。对未打标记的像素，inside不变。若访问当前像素时，对inside作必要操作后，inside为真，由把该像素置为填充色。
下面是程序：
/*
* Date: 11/23/2010
*/
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <vector>
#include <iostream>
#include <fstream>
using std::ofstream;
using std::ifstream;
using std::cout;
using std::endl;
ifstream cin ("polypoints.txt");
typedef struct _Point
{
int x;
int y;
}Point;
typedef struct _PolyPoints
{
Point * pPoint; // Pointer to points
int n; // Number of points
int yMax; // Max y of all points
int yMin; // Min y of all points
int xMax; // Max x of all points
int xMin; // Min x of all points
}PolyPoints;
PolyPoints g_polyPoints; // Storage for points of polygons
bool ** g_pbEdgeFlag; // Edge flag
void inputPoints (void)
{
int n;
cin>>n;
if (n < 3)
{
cout<<"number of points can not be less than 3"<<endl;
exit (0);
}
g_polyPoints.n = n;
g_polyPoints.pPoint = new Point[n];
g_polyPoints.yMax = INT_MIN;
g_polyPoints.yMin = INT_MAX;
g_polyPoints.xMax = INT_MIN;
g_polyPoints.xMin = INT_MAX;
int x, y;
for (int i = 0; i < n; ++i)
{
cin>>x>>y;
g_polyPoints.pPoint[i].x = x;
g_polyPoints.pPoint[i].y = y;
if (g_polyPoints.yMax < y)
{
g_polyPoints.yMax = y;
}
if (g_polyPoints.yMin > y)
{
g_polyPoints.yMin = y;
}
if (g_polyPoints.xMax < x)
{
g_polyPoints.xMax = y;
}
if (g_polyPoints.xMin > x)
{
g_polyPoints.xMin = x;
}
}
int xLen = g_polyPoints.xMax - g_polyPoints.xMin + 1;
int yLen = g_polyPoints.yMax - g_polyPoints.yMin + 1;
g_pbEdgeFlag = new bool *[yLen];
for (int i = 0; i < yLen; ++i)
{
g_pbEdgeFlag[i] = new bool [xLen];
memset (g_pbEdgeFlag[i], 0, sizeof (bool) * xLen);
}
}
// Free the memory
void destroy (void)
{
int yLen = g_polyPoints.yMax - g_polyPoints.yMin + 1;
for (int i = 0; i < yLen; ++i)
{
delete g_pbEdgeFlag[i];
}
delete g_pbEdgeFlag;
}
void scanConvertLineAndFlag (const Point & p1, const Point & p2)
{
int x1 = p1.x;
int y1 = p1.y;
int x2 = p2.x;
int y2 = p2.y;
int x, y, dx, dy, e;
// k does not exist
if (x1 == x2)
{
if (y1 < y2)
{
y = y1;
glBegin (GL_POINTS);
while (y <= y2)
{
glVertex2i (x1, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x1-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x1-g_polyPoints.xMin] = !bFlag;
++ y;
}
glEnd ();
} // if (y1 < y2)
else
{
y = y2;
glBegin (GL_POINTS);
while (y <= y1)
{
glVertex2i (x1, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x1-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x1-g_polyPoints.xMin] = !bFlag;
++ y;
}
glEnd ();
}
} // if (x1 == x2)
else if (y1 == y2) // k = 0
{
if (x1 < x2)
{
glBegin (GL_POINTS);
x = x1;
while (x <= x2)
{
glVertex2i (x, y1);
++ x;
}
glEnd ();
} // if (x1 < x2)
else
{
x = x2;
glBegin (GL_POINTS);
while (x <= x1)
{
glVertex2i (x, y1);
++ x;
}
glEnd ();
}
}
else
{
if (x1 > x2)
{
int temp = x1;
x1 = x2;
x2 = temp;
temp = y1;
y1 = y2;
y2 = temp;
}
x = x1;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
// k = 1
if (dx == dy)
{
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
++ x;
++ y;
}
glEnd ();
}
else if (dx == -dy) // k = -1
{
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
++ x;
-- y;
}
glEnd ();
}
else if (dy > dx) // k > 1
{
glBegin (GL_POINTS);
dx <<= 1;
e = - dy;
dy <<= 1;
y = y1 > y2 ? y2 : y1;
int maxY = y1 > y2 ? y1 : y2;
while (y <= maxY)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
++ y;
e += dx;
if (e > 0)
{
++ x;
e -= dy;
}
}
glEnd ();
}
else if (dy > 0) // 0 < k < 1
{
e = -dx;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
++ x;
e += dy;
if (e > 0)
{
e -= dx;
++ y;
}
}
glEnd ();
}
else if (-dy < dx) // 0 > k > -1
{
e = -dx;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
++ x;
e += dy;
if (e < 0)
{
-- y;
e += dx;
}
}
glEnd ();
}
else if (-dy > dx) // k < -1
{
e = dy;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
y = y1 > y2 ? y1 : y2;
int minY = y1 > y2 ? y2 : y1;
while (y >= minY)
{
glVertex2i (x, y);
// Flag current point
bool bFlag = g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin];
g_pbEdgeFlag[y-g_polyPoints.yMin][x-g_polyPoints.xMin] = !bFlag;
e += dx;
-- y;
if (e > 0)
{
++ x;
e += dy;
}
}
glEnd ();
}
}
}
void init (void)
{
glClearColor (0.0f, 0.0f, 0.0f, 1.0f);
}
void flagAllEdges (void)
{
Point * pPoint = g_polyPoints.pPoint;
int n = g_polyPoints.n;
for (int i = 0; i < n; ++ i)
{
scanConvertLineAndFlag (pPoint[i], pPoint[(i+1)%n]);
}
for (int i = 0; i < n; ++i)
{
int j1 = (i+n-1)%n;
int j2 = (i+1)%n;
if (pPoint[j1].y > pPoint[i].y && pPoint[j2].y > pPoint[i].y ||
pPoint[j1].y < pPoint[i].y && pPoint[j2].y < pPoint[i].y)
{
g_pbEdgeFlag[pPoint[i].y - g_polyPoints.yMin][pPoint[i].x - g_polyPoints.xMin] = false;
}
else
{
g_pbEdgeFlag[pPoint[i].y - g_polyPoints.yMin][pPoint[i].x - g_polyPoints.xMin] = true;
}
}
}
void edgeFlagFillPolygon (void)
{
int xLen = g_polyPoints.xMax - g_polyPoints.xMin + 1;
int yLen = g_polyPoints.yMax - g_polyPoints.yMin + 1;
int nScanLine = g_polyPoints.yMin;
glBegin (GL_POINTS);
for (int i = 0; i < yLen; ++i, ++ nScanLine)
{
bool bFlag = false;
int nHorizontal = g_polyPoints.xMin;
for (int j = 0; j < xLen; ++j, ++ nHorizontal)
{
if (g_pbEdgeFlag[i][j])
{
bFlag = !bFlag;
}
while (bFlag)
{
glVertex2i (nHorizontal, nScanLine);
++ j;
++ nHorizontal;
if (g_pbEdgeFlag[i][j])
{
bFlag = !bFlag;
}
}
}
}
glEnd ();
}
void display (void)
{
glClear (GL_COLOR_BUFFER_BIT);
glLoadIdentity ();
glColor3f (1.0f, 0.0f, 0.0f);
//flagAllEdges ();
// Fill a polygon
edgeFlagFillPolygon ();
glutSwapBuffers ();
}
void reshape (int w, int h)
{
glViewport (0, 0, (GLsizei) w, (GLsizei) h);
glMatrixMode (GL_PROJECTION);
glLoadIdentity ();
if (w <= h)
{
gluOrtho2D (-600.0, 600.0, -600.0 * (GLfloat) h / (GLfloat) w, 600.0 * (GLfloat) h / (GLfloat) w);
}
else
{
gluOrtho2D (-600.0 * (GLfloat) w / (GLfloat) h,600.0 * (GLfloat) w / (GLfloat) h, -600.0, 600.0);
}
glMatrixMode (GL_MODELVIEW);
glLoadIdentity ();
}
void keyboard (unsigned char key, int x, int y)
{
switch (key)
{
case 27: // 'VK_ESCAPE'
exit (0);
break;
default:
break;
}
}
int main (int argc, char ** argv)
{
glutInit (&argc, argv);
glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);
glutInitWindowSize (600, 600);
glutCreateWindow ("Bresenham line");
init ();
inputPoints ();
flagAllEdges ();
glutReshapeFunc (reshape);
glutDisplayFunc (display);
glutKeyboardFunc (keyboard);
glutMainLoop ();
destroy ();
return 0;
}
polypoints.txt中的示例内容如下: 7 30 120 10 70 30 10 60 50 80 10 120 90 70 80