# Signed Distance Field **Repository Path**: Li-Yan-Xiao/signed-distance-field ## Basic Information - **Project Name**: Signed Distance Field - **Description**: 计算平面内一条折线段的有向距离场，并通过OpenCV上色进行可视化 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-10-08 - **Last Updated**: 2022-10-12 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # Signed Distance Field > 作者：李彦筱 liyanxiao050804@126.com 在一个600 \* 400 的画布里随机生成一条有三段、含有一个钝角和一个锐角的折线段，并且在画布范围内绘制一个关于它的有向距离场。 主要内容包含四个部分：符合要求的折线段的生成，画布里每个点到折线段距离的计算，每个点距离正负的定义，每个点的绘制。折线段的生成放置于broken_line.h与broken_line.cpp中，每个点到折线段有向距离的计算在distance.h与distance.cpp中，点的绘制在draw.h与draw.cpp里。Line.h与Line.cpp为自己定义的，表示线段的一个类 [TOC] ## 程序使用方式 按下q键退出 按下r生成一个预设的折线的有向距离场 > 本文档中所有演示用的都是这一条预设的折线 > > 第一次运行，刷新之前生成的也是这条折线的有向距离场 按下其他任意键生成一个全新的有向距离场 计算一次所花时间大约为500ms。 ## 折线段的生成 折线段的每个点使用C++的`random`标准库生成。 第一条线段的两个端点在（600，400）的范围内随机生成 第二条线段的起始点为第一条折线的终点，终点随机生成，并通过点乘这两条折线的向量，要求结果小于零来确保这两条线段的夹角是个钝角。 第三条线段的起始点是第二条折线的终点，终点在满足以下两个条件的前提下随机生成： 1. 第二条线与第三条线成锐角：第三条线段与第二条线段的向量的点乘大于零 2. 第三条线与第一条线不相交： ​ 计算两条线的交点，其位置满足以下条件的任何一条即可： 1. 该交点的横坐标 < 0 或 > 600 或者 纵坐标 < 0或 > 400（即该交点坐标在图像边界外） 例如： > 红线代表第一条线，蓝线第二条，绿线第三条。第一条与第二条线一定夹钝角，第二条与第三条线一定夹锐角 ![image-20221008214447101](./README.assets/image-20221008214447101.png) 2. 该交点与第一条线终点的连线与第一条线成钝角，且该交点与第三条线起点连线和第三条线成钝角（也就是说两条线段的反向延长线相交） 例如：![image-20221008214609220](./README.assets/image-20221008214609220.png) 或者：![image-20221008214656520](./README.assets/image-20221008214656520.png) ## 每个点与折线绝对距离的计算 [toc] ### 一个点与一条线段最短距离的计算 做一根线段两端的垂线，可以把平面分成三个部分 ![绘制本-2](./README.assets/绘制本-2.jpeg) #### 为什么要这么分呢？ 分类之后，可以**轻松算出点到一条线段的距离** **当点在1区时，其到线段的距离就是它到左端点的距离。** **当点在2区时，直接用点到直线距离公式即可算出它到线段距离** **当点在3区时，其到线段的距离就是它到右端点的距离。** #### 怎么做这种分类呢？ 平面内的某个点属于哪个部分可以通过该点到线段开头/结尾的向量点乘线段对应的向量的正负性来判断。 ```C++ /* * Line是我自己写的类，line.getStartPoint如同它的名字一样，就是获取线段的起始 * 点。line.vector就是线段开头指向末端的向量 */ /* * 判断一个点是否在一条线起点左侧（即1区域） */ inline bool OverStart(const Eigen::Vector2i& point, const Line &line) { return (point - line.getStartPoint()).dot(line.vector()) < 0; } /* * 判断一个点是否在一条线终点右侧（即3区域） */ inline bool OverEnd(const Eigen::Vector2i &point, const Line &line) { return (point - line.getEndPoint()).dot(line.vector()) > 0; } ``` 通过这两个函数，可以判断每个点位于某条线段的1区，2区还是3区。 #### 怎么求每种情况下的距离呢？ 点在1区，3区时，可以直接计算点到左/右端点的距离 ```C++ inline double DistancePointToPoint(const Eigen::Vector2i &point1, const Eigen::Vector2i &point2) { // sqrt是求平方根，pow（？，2）是求平方 return sqrt(pow(point1.x() - point2.x(), 2) + pow(point1.y() - point2.y(), 2)); // 其实就是算了 (x1 - x2) ** 2 + (y1 - y2) ** 2 的平方根 } ``` 点在2区时，使用点到直线距离公式 ```C++ inline double DistancePointToLine(const Eigen::Vector2i &point, const Line &line) { return abs(point.x() + line.getB() * point.y() + line.getC()) / sqrt(1 + line.getB() * line.getB()); } ``` 综合起来，加上条件判断，求一个点到一条线段距离的函数如下： ```C++ double DistancePointToLineSegment(const Eigen::Vector2i &point, const Line &line) { if (OverStart(point, line)){ // 这个函数在上面的展示里给过了 return DistancePointToPoint(point, line.getStartPoint()); } else if (OverEnd(point, line)){ return DistancePointToPoint(point, line.getEndPoint()); } else{ // 这个在上面也给过实现了 return DistancePointToLine(point, line); } } ``` ### 怎么求点到一堆线的最短距离？ 上一小节里，已经阐述了求点到一条线段的距离的方法。求点到一系列线，可以采取以下方法： **求出点到每条线的最短距离，然后求这几个最短距离中的最短距离** 下面的代码求出了点到三条线段的距离中最短的值（变量min_value），还有最短距离对应的是哪条线段(变量min_place) ```C++ double MinDistance(const Eigen::Vector2i &point, const Line *line) { double distances[3]; distances[0] = DistancePointToLineSegment(point, line[0]); distances[1] = DistancePointToLineSegment(point, line[1]); distances[2] = DistancePointToLineSegment(point, line[2]); double min_value = distances[0]; int min_place = 0; int i; for (i = 0; i < 3; i++) { if (distances[i] <= min_value) { min_value = distances[i]; min_place = i; } } } ``` 这样一来，就可以求出一个点到一条折线的最短距离了。 ### 一点点优化 很可惜，由于计算每个点到折线的距离这一步整整要跑1.6秒…我对它进行了一点简化： 在这张600x400的图里，每隔一行/一列计算一次点到折线的距离，并把这个值赋给附近的四个像素点 比如： > 一个单元格中写着(0,0)，代表其值为（0，0）单元格里的值，以此类推… | (0,0) | (0,0) | (2,0) | (2,0) | |-------|-------|-------|-------| | (0,0) | (0,0) | (2,0) | (2,0) | | (0,2) | (0,2) | (2,2) | (2,2) | | (0,2) | (0,2) | (2,2) | (2,2) | 这样子，在精确度损失不太离谱的情况下，代码提速了4倍，运行一次大概在0.4到0.5秒间 ## 正负号判断 [TOC] 由于要做一个Signed Distance Field，距离应当是有方向属性的，这个方向属性会通过距离的正负来体现。 在我的代码中，统一定义一条线段所属直线的**左侧**是**正**，**右侧**是**负** > 在下一节还会提到，我的代码把所有正距离染成红色，负距离染成蓝色 ### 点在一条线段的哪侧？ 点在一条线段的哪一侧可以通过叉乘来判断。由于叉乘理论上说，是三维向量才有的属性，所以需要把参与的点的z值设为0，判断叉乘结果向量的z值与0的大小即可，大于等于0即在左侧（**正**），小于0在右侧（**负**） ```C++ bool Cross2(Eigen::Vector2i vec1, Eigen::Vector2i vec2) { // 由于点是个二维向量，需要把它扩展成一个z值为0的三位向量才能计算 Eigen::Vector3i temp_1(vec1.x(),vec1.y(), 0); Eigen::Vector3i temp_2(vec2.x(),vec2.y(), 0); // 判断结果的z是否大于0 return (temp_1.cross(temp_2).z() >= 0); } ``` 如果叉乘的值小于0，就把距离设置成负值，大于0则什么都不做。 ### 点在一堆线段的哪侧？ 事实上，在有三条线段的情况下，点完全可以在第一条左侧，第二条右侧，第三条左侧这样子…为了找到一个**唯一**的方法描述距离的正负性，我选择使用**离点最近的线段**作为参考，仅计算点在**离它最近的线段**的哪一侧。 ![绘制本-4](./README.assets/绘制本-4.jpeg) 上图中，蓝线是从线段起始点指向待求方向那个点的向量。用线段的向量与其叉乘，就可以得到点在线段的左侧还是右侧 ```C++ Eigen::Vector2i point_to_line = point - line[min_place].getStartPoint(); Eigen::Vector3i temp_vector_1(line[min_place].vector().x(), line[min_place].vector().y(), 0); Eigen::Vector3i temp_vector_2(point_to_line.x(), point_to_line.y(), 0); Eigen::Vector3i temp_vector_3; temp_vector_3 = temp_vector_1.cross(temp_vector_2); if (temp_vector_3.z() > 0) { // 当点在线段右侧时，把距离调成负数 min_value = -min_value; } ``` ### 特定点的正负值问题 如果就这么结束求正负部分的话，会出现这样的问题： ![image-20221012143219755](./README.assets/image-20221012143219755.png) 注意左下部分，那里出现了蓝色（然而那边是第三条线的左侧，应该是红色）。 #### 原因 在绘制部分里，我通过从左到右，从上到下遍历的方式绘制每一个点。但是，代码的逻辑判断这片蓝色区域中的点都离第二条线最近，因此会按第二条线给自己赋正负值。然而，这些点在第二条直线的右侧，距离为负数，被绘制部分染成了蓝色，造成了这个问题。 #### 解决方法 额外写一块代码，对于位于第三条线起始点外侧，第二条线终止点外侧的区域进行额外检查。 ![绘制本-5](./README.assets/绘制本-5.jpeg) > 下列代码中，temp_vector_3是第二条线与点到第二条线起始点的叉乘，即上图中a叉乘d。temp_vector_6是第三条线与点到第三条线起始点的叉乘，即上图中b叉乘c。 ```C++ // 当第三条线在第二条线右侧时，进入这个修正部分 // 此时“外侧”（第二条线与第三条线间角度较大的那一大半）的距离应当为正 if (!Cross2(line[1].vector(), line[2].vector())) { // 当点在a左侧，b右侧时： if (temp_vector_3.z() < 0 && temp_vector_6.z() > 0) { // 优先参考b染色 min_value = -abs(min_value); } // 当点在a右侧，b左侧时： if (temp_vector_3.z() > 0 && temp_vector_6.z() < 0) { // 优先参考a染色 min_value = -abs(min_value); } } else { // 当第三条线在第二条线左侧时，进入这个修正部分 // 此时“外侧”（第二条线与第三条线间角度较大的那一大半）的距离应当为负 if (temp_vector_3.z() < 0 && temp_vector_6.z() > 0) { min_value = abs(min_value); } if (temp_vector_3.z() > 0 && temp_vector_6.z() < 0) { min_value = abs(min_value); } } ``` 修正完后，结果如下： ![image-20221012145339463](./README.assets/image-20221012145339463.png) 可以看到，左下异常的蓝色被重新染色为红而消失。 ## 每个点的绘制 先在OpenCV中，创建一个三通道，（600x400)的图像 `cv::Mat image = cv::zeros(400, 600 CV_8UC3)` > CV_8UC3,CV_16UC1之类的东西命名规则如下： > > CV_ ： 固定开头 > > 第一位数字：图像深度，即多少个bit被用来储存一个像素 > > 第一个字母（U/C/F/S): 代表每个像素点的数据类型。 > > ​ U:unsigned int F: float > > 第二个字母C: 固定内容 > > 第二个数字：代表图像是几通道的，只能在1～4里选 ### 距离归一化 每个点到折线距离从0到600千差万别，直接拿去当像素值显然是不行的。因此，需要对距离进行**归一化**，将距离化为·255～255之间的值。 求出距离中绝对值最大的那个，然后把每段距离除以最大距离，得到-1～1间的距离值。再对这个距离值乘255，即可将其变为-255～255间的值 ```C++ double max_value = abs_matrix.maxCoeff(); for (int i=0;irows();i++){ for (int j=0;jcols();j++){ double val = (*distances)(i,j); (*dst)(i, j) = val / max_value * 255; // 实现归一化 } } ``` ### 每点的绘制 从（0，0）到（600，400），遍历每一个点，然后对之前创建的image中对应位置的像素点赋对应值。 在我的程序中，距离为正会被赋值为红色，负会变成蓝色。距离越小，其BGR值就越高（越接近白色）；距离越大，其BGR值就越低（接近黑色） ```C++ for (int i=0;i= 0) { // B与G从255向下递减，R不变，就一定一直是红色 image.at(i, j)[0] = 255 - floor(distance); image.at(i, j)[1] = 255 - floor(distance); image.at(i, j)[2] = 255; } else { // G与R从255向下递减，B不变，就一定一直是蓝色 image.at(i, j)[0] = 255; image.at(i, j)[1] = 255 + floor(distance); image.at(i, j)[2] = 255 + floor(distance); } } } ``` > OpenCV的三通道比较奇怪：它是按B（蓝色）G（绿色）R（红色）排列的。因此，想调整蓝色通道，就得改第1通道而不是第3通道 这样一来，有向距离场的绘制就完成了………吗？ ### 边缘跳变 在结果图中，可以看到一段锯齿状的白色，这是为什么产生的呢？![image-20221012145339463](./README.assets/image-20221012145339463.png) 去掉这段优化后，结果如下： ![image-20221012151111659](./README.assets/image-20221012151111659.png) 右下角可以清晰地看到，蓝色和红色失去了过渡，成锯齿状跳变。 #### 原因 线段只延伸到一半，而线段延长线上的部分离线段的距离较远，颜色较深，而且在跨越线段所在直线时发生符号突变，导致蓝色和红色直接接在了一起。 #### 解决方法 在求一个点到折线距离的函数中，添加一个判断： 当点位于第1条线反向延长线/第3条线延长线上时，让点的距离等于其到线段所在直线的距离 ![绘制本-6](./README.assets/绘制本-6.jpeg) 之前，右下方那个圈到折线的距离是蓝线。经过优化后，圈到折线的距离只有绿线这么一点了。 这样子，就会在蓝色区域与红色区域间构成天然的白色屏障。虽然这个屏障和其他位置过渡的不太自然，但至少解决了蓝色红色跳变的问题。 最终结果就是上面的样子： ![image-20221012145339463](./README.assets/image-20221012145339463.png)