메쉬 위의 최단 거리 (Shortest Path on Polygonal Meshes)

삼각 메쉬 위의 정점들에 대한 근사화된 거리를 얻는 방법을 알아보자.

 

 

 

 

기준점 s에서 v_i까지 거리는 국소적으로 최적화 되어야 하며 다음 식을 만족해야 한다.

 

 

 

 

여기서 U (y)는 s에서 y까지의 측지 거리의 국소 근사값이다. 다음과 같이 가상의 기준점 s' 를 정하면 U (y)를 쉽게 계산할 수 있다. 

 

 

 

 

또한 다음 부등식을 만족한다면 삼각형T_ijk에 의해 span되는 평면 위에 가상의 기준점s' 가 존재한다.

 

 

 

 

기준점 s' 존재 여부에 따라 s' 에서 v_i 까지 거리를 다음과 같이 계산한다.

 

 

 

 

Algorithm

메쉬위의 기준점에서 다른 점들까지의 최단거리를 구하는 알고리즘을 알아보자. Dijkstra 알고리즘과 비슷한 형태의 동적 프로그래밍 방식을 사용한다. 위에서 설명한 U_i 를 기준점에서 주변 영역까지 계산하며 전파시켜 나가면 된다.

 

 

알고리즘에서 initializeNeighbourhood(s) 는 기준점 s의 이웃 정점과의 거리를 초기화하는 함수이다. 집합 candidates는 정점 v_i 와 거리 U_i 데이터로 구성된 힙이고 거리에 따라 정렬된다. 거리 U_i는 computeDistance(i)에서 계산된다. 알고리즘은 집합 candidates가 비었을 때 종료된다. 

 

 

 

[참고] Eivind Lyche and Martin Reimers, Geodesic Polar Coordinates on Polygonal Meshes, Computer Graphics Forum, 2012