Signed Distance Field(SDF)
YeeKal
•
•
"#"
- general method
- fast marching method
- fast sweeping method
- level set method, 水平集方法
- geometry shape calculation
- object
- 2d / 3d
- geometry shape
- image
- 3d model, such as stl
- application
- Surface Normals
- Collision Detection
- Geometry Processing: The gradient can be used for smoothing and sharpening features of a model, morphological operations, and other geometry processing tasks in 3D modeling and CAD software.
computational sweeping
- find the filled seed
- BFS expand
gradient
梯度为0的地方
鱼骨图 skeletal graphs
8-points Signed Sequential Euclidean Distance Transform
Distance Transform
Distance Transform
Distance Transform源于图像处理，表示每个像素点距离前景图像之间的距离，可以用于图像分割，形态学，骨架提取等。事实上这其实就是产生了无符号的距离场。在机器人领域，可以用于生成障碍物的距离场，用于规划算法中。
- project
- sdf blog
field sweeping
field sweeping isn’t perfect. the distance and the gradient may be slightly wrong.
use Eikonal Sweep. The comparison:
Fast marching method
FMM: Fast Marching Method / FMS: fast marching square
- paper/notes:
- 1999 - Fast marching method:Fast methods for the eikonal and related Hamilton-Jacobi equations on unstructured meshes.
- Eran Treister and Eldad Haber. A fast marching algorithm for the factored eikonal equation. Journal of Computational Physics, 324:210-225, 2016.
- Implementing and Analysing the Fast Marching Method
- project
fast marching method 是求解程函方程的一种数值方法
Eikonal方程解u(x)的物理含义是从源点x0以速度f(x)到达计算域Ω内x点所需要消耗的最短时间。当f(x) = 1的特殊情况下，方程解就代表计算域Ω内的距离场。
Dijkstra算法和Fast marching算法思想相似，不同之处在于Dijkstra算法利用节点之间的欧式距离进行更新. 而Fast marching算法利用由Eikonal方程化简得到的近似偏微分方程进行更新，更加接近真实的距离，边缘处更加光滑。
Collision Detection
Ref
- paper
- blog
- project