【CG】Bresenham算法 画直线与圆

【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-%20TriangleRas