메쉬 위의 곧은 측지선 (Straightest Geodesics on Polyhedral Surfaces)

측지선(Geodesics)은 기하학에서 곡면 위 직선을 일반화하기 위한 중요한 개념이다. 이 글에서는 메쉬 위에서 한 방향으로 쭉 나아가는 곧은 측지선 (Straightest Geodesics)에 대해서 설명한다. 한 점과 나아가고 싶은 방향이 있으니 초기값이 주어진 유일한 해를 구하는 문제라고 생각하면 된다. 이렇게 곧은 측지선을 구할 수 있다면 곡면 위에서 벡터의 평행이동이나, Tangential vector field에 대한 고차 수치 적분 방법(Discrete Runge-Kutta method)에도 응용 가능하다.

 

 

부드러운 곡면을 생각해보자. 그 위에서 측지선은 곧은 선이고 국소적으로는 가장 짧은 선이다. 측지선은 유클리드 공간의 직선을 곡면 위로 일반화한 개념이라고 보면 된다. 측지선에 대해서 주요한 특징이 두 가지 있다.

1. 측지선을 구한다는 것은 메쉬의 임의의 지점에서 임의의 방향으로 고유한 측지선을 구하는 초기값 문제(Initial value problem)이다.
2. 길이를 최소화한다는 특성 때문에 메쉬 위에서 두 점을 국소 최단경로로 잇는 경계값 문제(Boundary value problem)의 해를 구하는 문제가 된다.

 

 

최단 거리 / 근사 측지선 개념과는 다르게, 이 글에서는 2차원 다면체 곡면(polyhedral surface) 위에서 곧은 선을 구하는 법을 알아보자.

 

 

 

 

알고리즘

1. 시작점에서 주어진 방향으로 에지 교차점을 계산한다.
2. 교차점을 공유한 인접 삼각형을 평면으로 펼쳐 새로운 방향을 구한다.
3. 인접 삼각형과 새로운 방향과의 교차점을 구한다.
4. 목표 거리에 도달하거나 경계 에지와 만날 때까지 2, 3 과정을 반복한다.

 

 

알고리즘의 각 과정를 다음 그림과 같이 나타냈다. 과정 2에서 회색 각도는 빨간 방향과 에지와의 예각에 해당된다.

 

 

​

 

알고리즘 수행 중에 예외처리를 할 경우가 있다. 바로 아래 그림처럼 경로가 정점과 만나는 경우인데, 이 때에는 좌우 각도가 같도록 다음 방향을 결정해야 한다.

 

 

 

 

 

 

[참고] Polthier, Konrad, and Markus Schmies. "Straightest geodesics on polyhedral surfaces." ACM SIGGRAPH 2006 Courses. 2006.