OpenGL——使用Bresenham算法绘制圆

　　Bresenham算法是计算机图形学中为了“显示器（屏幕或打印机）系由像素构成”的这个特性而设计出来的算法，使得在求直线各点的过程中全部以整数来运算，因而大幅度提升计算速度。——摘自 “百度百科”。

　　Bresenham算法绘制直线就不赘述了，大家看一看算法简介就能很好理解与实践。

　　稍稍麻烦一点的就是用该算法绘制圆了，算法思想其实是一样的，并没有太大改变。

　　算法核心：

　　组合以上式子，当Dupper-Dlower<0时，取上点；当Dupper-Dlower>0时，取下点；否则任意。

　　实验过程中，我使用了两种方法：① 画点法 ② 连线法。

　　一、画点法：

　　　　画点法就是仅仅用OpenGL绘制点。可以选择按照圆的轨迹画整个圆，当然这样的算法要比较慢，而且要注意分段函数的增减性。

　　我使用的是对称法，利用圆的对称性质，仅仅计算1/8的圆弧的点（当然算1/4也可以），其余的点均用对称性直接绘制。如下图所示：

　　　　代码如下：

 1 /*
 2  * Draw Circle by Bresenham Algorithm
 3  * @para < xc, yc - 圆心: (xc, yc) >
 4  * @para < r - 半径 >
 5  * @para < deltaX - 坐标系每个小格的间距，用于控制精细度 >
 6  */
 7 void drawCircle_Bresenham(GLfloat xc, GLfloat yc, GLfloat r, const GLfloat deltaX) {
 8     GLfloat xi = - r, yi = 0; /* 圆上点 (xi, yi) */
 9     GLfloat du_l; /* upper - lower */
10     glBegin(GL_POINTS);    
11     while (abs(xi) >= abs(yi)) {
12         // 根据圆的八向对称，只计算其中八分之一的点，然后对称得出其他点
13         // 假设圆心在原点，先求点，再平移
14         glVertex2f(xc + xi, yc + yi);
15         glVertex2f(xc - xi, yc + yi);
16         glVertex2f(xc + xi, yc - yi);
17         glVertex2f(xc - xi, yc - yi);
18         glVertex2f(xc + yi, yc + xi);
19         glVertex2f(xc - yi, yc + xi);
20         glVertex2f(xc + yi, yc - xi);
21         glVertex2f(xc - yi, yc - xi);
22         
23         xi += deltaX; //　下一个x
24         float yi_1 = sqrt(pow((GLfloat)r, 2) - pow((GLfloat)xi, 2)); // yi+1
25         du_l = 2 * (GLfloat)yi + deltaX - 2 * yi_1;
26         yi = (du_l <= 0) ? (int)yi_1 + deltaX : (int)yi_1;
27     }
28     glEnd();
29     glFlush();
30 }

　　结果如图（半径150，圆心在原点，横坐标间隔为0.001）：

　　二、画线法：

　　根据圆弧四个象限的增减性和凹凸性的不同，分别绘制四段曲线，组合成一个圆。核心算法和第一种方法相同。

 1 const GLint FIRST_QUA = 1; // 第一象限
 2 const GLint SECOND_QUA = 2; // 第二象限
 3 const GLint THIRD_QUA = 3;
 4 const GLint FOURTH_QUA = 4;
 5 
 6 /*
 7  * 根据起点和终点绘制弧(画线法)
 8  * @para < deltaX - 坐标系每个小格的间距，用于控制精细度 >
 9  * @para < Quadrant - 象限 >
10  */
11 void setPixel(GLfloat startX, GLfloat endX, GLfloat startY, GLfloat xc, GLfloat yc, GLfloat r, GLfloat deltaX, GLint Quadrant) {
12     GLfloat du_l; /* upper - lower */
13     int inc = (Quadrant % 2 == 1) ? -1 : 1;
14     int nag = (Quadrant > 2) ? -1 : 1;
15     glBegin(GL_LINE_STRIP);
16     while (startX <= endX) {
17         // 假设圆心在原点，先求点，再平移
18         glVertex2f(startX + xc, startY + yc);
19         startX += deltaX;
20         float yi_1 = nag * sqrt(pow((GLfloat)r, 2) - pow((GLfloat)startX, 2)); // yi+1
21         du_l = 2 * (GLfloat)startY + inc * deltaX - 2 * yi_1;
22         startY = (du_l <= 0) ? (int)yi_1 + deltaX : (int)yi_1;
23     }
24     glEnd();
25 }
26 
27 /*
28  * Bresenham 算法（画线法）
29  * @para < xc, yc - 圆心(xc, yc) >
30  * @para < r - 半径 >
31  */
32 void drawCircle_Bresenham_line(GLfloat xc, GLfloat yc, GLfloat r, GLfloat deltaX) {
33     setPixel(-r, 0, 0, xc, yc, r, deltaX, SECOND_QUA); // 左上半
34     setPixel(0, r, r, xc, yc, r, deltaX, FIRST_QUA); // 右上半
35     setPixel(0, r , -r, xc, yc, r, deltaX, FOURTH_QUA); // 右下半
36     setPixel(-r, 0, 0, xc, yc, r, deltaX, THIRD_QUA); // 左下半
37     glFlush();
38 }

　　结果如图（半径150，圆心在原点，横坐标间隔为0.001）：