geodesic distances 논문 정리

1. Fast Marching Method

1.1 참고 논문: KIMMEL, Ron; SETHIAN, James A. Computing geodesic paths on manifolds. Proceedings of the national academy of Sciences, 1998, 95.15: 8431-8435

1.2 주요 방법론

A. Triangulated domain에 적용할 수 있는 Fast Marching Method의 application을 제시함

B. The Fast Marching Method는 본질적으로 wavefront propagation 알고리즘임

C. 본 논문의 주요 아이디어는 전파를 upwind 방식으로 진행하여 mesh의 vertices에 새로운 거리 값을 생성하는 것임

I. 이때 upwind란 파동이 흐르는 방향으로 그래프 상의 vertex를 순차적으로 업데이트하는 것을 의미함

II. 즉 출발점에서 전파를 시뮬레이션하면서 그래프 상의 vertices의 거리값을 계산하고, 이를 vertex에 저장하며, 거리값의 increasing order대로 vertex의 최단 거리 정보를 갱신함

D. 이러한 방법론은 Eikonal equation을 통해 공식화됨

E. time complexity: O(nlogn)

1.3 코드

matlab

https://kr.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

Toolbox Fast Marching

scikit-fmm library(Python)

https://pythonhosted.org/scikit-fmm/

scikit-fmm documentation — scikit-fmm 0.0.9 documentation

 

 

 

2. MMP method

1.1 참고 논문: SURAZHSKY, Vitaly, et al. Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG), 2005, 24.3: 553-560.

1.2 주요 방법론

A. 본 논문은 triangle mesh에 대한 최단 거리의 정확한 근사치를 계산하는 현실적인 방법을 제시함

B. 해당 방법론은 Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.에 기반하고 있으며 MMP 알고리즘의 효율적인 적용 방법론임

I. 저자는 MMP 알고리즘의 시간 복잡도가 최악의 경우 O(n^2logn)라는 의견에 비관적이며 실제로는 2차 다항식 이하의 시간복잡도를 보인다고 함

II. 예를 들어, triangle mesh의 400K vertex를 약 1분 내로 계산할 수 있음

C. 해당 방법론은 제한된 오차 내에서 효율적이고 정확한 근사치를 제공하기 위해 merging operation을 포함함

I. 본 논문에서 구현한 MMP 알고리즘은 실질적으로 O(nlogn)의 시간 복잡도 내에서 작동함

1.3 코드

pygeodesic library(Python)

https://pypi.org/project/pygeodesic/

github

https://github.com/mojocorp/geodesic

 

 

 

3. CH method

1.1 참고 논문: CHEN, Jindong; HAN, Yijie. Shortest paths on a polyhedron. In: Proceedings of the sixth annual symposium on Computational geometry. 1990. p. 360-369.

1.2 선행 연구

A. MITCHELL, Joseph SB; MOUNT, David M.; PAPADIMITRIOU, Christos H. The discrete geodesic problem. SIAM Journal on Computing, 1987, 16.4: 647-668.

I. 위 논문에서는 Dajkstra 알고리즘에 기반한 MMP method를 제시하였으며 O(n^2logn)의 시간 복잡도를 보임

B. CHEN, Jindong; HAN, Yijie. Shortest paths on a polyhedron. In: Proceedings of the sixth annual symposium on Computational geometry. 1990. p. 360-369.

I. 위 논문에서는 시간 복잡도를 O(n^2)를 개선한 method를 제시함

C. SURAZHSKY, Vitaly, et al. Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG), 2005, 24.3: 553-560.

I. 위 논문에서는 MITCHELL의 MMP method가 실질적으로는 훨씬 빠르게 작동한다는 실험적인 증거를 보였으며, 이는 CHEN과 HAN의 method보다 빠른 작동 시간임

1.3 주요 방법론

A. 원 CH algorithm은 다면체의 edge에 windows 세트를 사용하여 최단 거리의 구조를 encode하는 방식으로 작동함

I. 본 논문에서는 CH algorithm에서 계산된 windows 중 99%가 최단 거리 정의를 위해 사용되지 않는다는 점을 지적함

B. 따라서 본 논문에서는 원 CH algorithm에서 두 가지 개선점을 제안함

I. vertex 까지의 현재 distance 추정치를 활용하여 불필요한 window를 필터링하는 방안

II. priority queue를 유지하는 것

C. 위의 개선점을 통해 원 CH algorithm보다 시간과 공간 복잡도가 훨씬 개선되었으며, MMP 알고리즘보다 일반적으로 빠르게 동작하고 적은 메모리를 사용하는 것을 실험을 통해 입증하였음

1.4 코드

github

https://github.com/aalavandhaann/ch_bl_geodesics

GitHub - aalavandhaann/ch_bl_geodesics: Geodesics algorithm for Blender using ChenHan algorithm

chenhancc library

https://pypi.org/project/chenhancc/

chenhancc

https://github.com/aalavandhaann/chenhancc

GitHub - aalavandhaann/chenhancc: A faster python geodesic path cutting across mesh surface