SLAM从入门到精通（bresenham绘制算法）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

        前面我们说过，学术界和工业界对于slam的要求是不一样的。前者要求robot在运动的过程中，同步实现定位和制图的操作。但是工业界中，一般两者是分开来的。首先进行制图，一旦制图完成之后就专注于定位操作。但是这两者之间没有明显的差别。

1、学术slam和工业slam的关系

        整理来说，完全可以把工业界的应用看成是slam的一个特例。真正的slam一般是这样的，首先在robot开始的位置设置为原点，lidar扫描的地方，绘制出一个地图。接着，通过遥控按钮操作robot，这个时候robot就走到了一个新的位置。借助于odom数据、lidar数据和之前的地图数据，我们可以求解出robot新位置的坐标。这样，我们通过robot的新位置、lidar扫描数据，又可以绘制出新的地图了。循环往复，不断重复上面的过程，最终就会可以得到一个完整的地图。这就是slam的基本原理。

2、slam和定位的转换

        有了上面的分析，大家也就明白了为什么很多论文都是讲slam算法，但是不谈具体的定位算法。这主要就是因为如果把slam算法中的制图删除、定位算法中的地图直接换成全局地图，这本身就是一个相对完整的定位算法方案了。

3、制图的算法

        有了准确的位姿之后，制图就不复杂了。前面我们说过，制图其实就是绘制很多的射线。雷达无法扫描到的地方一般被认为是灰色。没有达到最远测量距离，提前返回来的地方，那就是黑色，也就是有障碍物的地方。而lidar和障碍物之间的区域，这就是白色，可以被认为是能够自由活动的区域。

        上面这些描述，都是建立在lidar和base_link基本一致的基础上得出来的。如果两者不一致，那么还需要做一个tf转换。所以大家看到得是地图文件，实际上是通过一条、一条得射线绘制出来的。

4、bresenham算法

        这个算法本身是属于计算机图形学的一个基本算法。我们平时在绘制直线的时候，很容易遇到浮点数。但是计算机屏幕上面是没有浮点数的，每一个x、y坐标都是一个整数。那么怎么把这些直线上的数据在屏幕上面显示出来，这就是bresenham算法所要解决的事情。

        希望了解算法详细内容的同学，可以看下这个wiki连接，讲的还是很仔细的，

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

5、编译和测试

        不喜欢看算法，想直接看代码的同学也可以直接github上查找对应的代码。网上有很多bresenham算法的实现代码，这里给出一个链接，

https://gist.github.com/nowke/965fed0d5191bf373f1262be584207bb

        如果链接也不想看，这里给出一个可以编译版本的代码方案。主要是头文件需要修改下，

        这里的编译命令是在ubuntu 20.04上实现的，如果有glut.h文件无法找到的错误，可以先安装一下这个库，

sudo apt-get install libglfw3-dev libgl1-mesa-dev libglu1-mesa-dev

        安装好库之后，就可以用命令gcc来编译了，

gcc draw.c -lglut -lGL -lGLEW -lGLU -o draw

        一切顺利的话，就可以生成./draw文件。执行后，会看到一个提示，要求我们输入起点和终点的坐标，

        老老实实输入坐标后，按回车就可以看到对应的直线显示了，

        整个算法借助于opengl实现了显示过程。有兴趣的同学可以单步调试一下。