【CG】Bresenham算法 画直线与圆

@(CG)

Bresenham算法的意义在于避免了浮点数运算，无论是画直线还是画圆，都提高了效率。 本文参考了网上的资料后，根据自己作业的需要，完成了Bresenham画直线和画圆的算法，分享出来希望能帮助到需要的人、。

画直线算法

算法步骤：

参考：https://blog.csdn.net/mmogega/article/details/53055625

这篇blog的代码有点bug，重点在于是递增x还是y的选择和方向的选择，我重写的代码如下： 代码输入2个点的坐标，然后使用bresenham画线算法，并将得到的点都存入一个vector中返回。

vector<int> Bresenham(int x0, int y0, int x1, int y1) { vector<int> points; points.push_back(x0); points.push_back(y0); int dx= x1- x0; int dy= y1- y0; int direct_x= dx> 0? 1: -1; int direct_y= dy> 0? 1: -1; if (abs(dx)> abs(dy)) { int p= 2* dy- dx; int x= x0; int y= y0; int two_dy= 2* dy; int two_dy_sub_two_dx= 2* dy- 2* dx; while (x< x1) { printf("%d, %d\n", x, y); points.push_back(x); points.push_back(y); if (p> 0) { y+= direct_y; p= p+ two_dy_sub_two_dx; } else { p= p+ two_dy; } x+= direct_x; } } else { int p= 2* dx- dy; int x= x0; int y= y0; int two_dx= 2* dx; int two_dx_sub_two_dy= 2* dx- 2* dy; while (y< y1) { printf("%d, %d\n", x, y); points.push_back(x); points.push_back(y); if (p> 0) { x+= direct_x; p= p+ two_dx_sub_two_dy; } else { p= p+ two_dx; } y+= direct_y; } } }

画圆算法

参考：https://blog.csdn.net/mmogega/article/details/53055625 原理这篇blog解释得非常清楚了，bresenham的画圆算法是由中点画圆算法优化得到的，其重点将圆分成了8区间，每次得到一个区间的点，然后根据对称性得到其他的7个点。

我的test代码如下： 代码输入圆心的坐标和半径，然后使用bresenham画圆算法，并将得到的点都存入一个vector中返回。

#include <iostream> #include <vector> #include <cmath> using namespace std; void getAllPoints(int x0, int y0, int x, int y, vector<int> &points) { points.push_back(x0+ x); points.push_back(y0+ y); points.push_back(x0+ x); points.push_back(y0- y); points.push_back(x0- x); points.push_back(y0+ y); points.push_back(x0- x); points.push_back(y0- y); points.push_back(x0+ y); points.push_back(y0+ x); points.push_back(x0+ y); points.push_back(y0- x); points.push_back(x0- y); points.push_back(y0+ x); points.push_back(x0- y); points.push_back(y0- x); } vector<int> BresenhamCircle(int x0, int y0, int r) { vector<int> points; int x, y, d; y= r; x= 0; d= 3- 2* r; getAllPoints(x0, y0, x, y, points); while (x< y) { if (d< 0) { d= d+ 4* x+ 6; } else { d= d+ 4* (x- y)+ 10; y--; } x++; getAllPoints(x0, y0, x, y, points); } return points; } int main() { vector<int> v; v= BresenhamCircle(0, 0, 50); }

算法结果

使用Opengl3.3+ IMGUI，能够根据得到的包含点的vector转换为Opengl需要的vertices，使用opengl的函数，最后将点画出来。

用Bresenham画直线算法画出来3条直线构成三角形：

用Bresenham画圆算法将圆画出来：

完整的代码还整合了三角形的光栅化，为三角形着色，参考我的另外一篇blog： https://blog.csdn.net/timso1997/article/details/79732779

完整的代码参考我的github： https://github.com/sysuts13/CG/tree/master/Opengl3_IMGUI_Bresenham- TriangleRas