다면체간의 강건한 민코스키합경계면 계산 (Robust Computation of Polyhedral Minkowski Sum Boundary)

서지정보

· 발행기관 : (사)한국컴퓨터그래픽스학회
· 수록지 정보 : 한국컴퓨터그래픽스학회논문지 / 16권 / 2호 / 9 ~ 17페이지
· 저자명 : 경민호, Elisha Sacks

초록

기하학에서 민코스키합은 두 집합에 들어 있는 모든 점들간의 합으로 이루어지는 집합을 구하는 연산으로 정의되는데, 로보틱스, NC 가공, 솔리드 모델링 등의 다양한 분야의 기하학적 문제를 다루는 매우 유용한 이론적 도구로 사용되고 있다. 하지만, 단순한 정의에도 불구하고 수치연산의 반올림 오차로 인하여 다면체간의 민코스키합을 정밀하고 강건하게 계산하는 것은 매우 어렵다. 본 논문에서는 컨볼루션 계산방법을 이용하여 다면체간의 민코스키합 경계를 계산하는 알고리즘을 제안한다. 알고리즘의 강건성을 보장하기 위한 방법으로 CLP(controlled linear perturbation) 기법을 처음으로 적용하였다. CLP는 인위적 교란방법의 하나로 알고리즘의 강건성을 해치는 반올림 오차에 의한 논리적 오류발생을 막는다. 본 논문의 알고리즘은 실험 예제들에서 민코스키합의 경계면을 구성하는 완전한 2차원 다양체 구조메시를 10⁻¹⁴의 정밀도로 출력하고, 이때 입력 다면체의 꼭지점 좌표는 10⁻¹⁰까지 교란되는 결과를 얻었다

영어초록

Minkowski sum of two polyedra is an operation to compute the sum of all pairs of points contained in the polyhedra. It has been a very useful tool to solve many geometric problems arising in the areas of robotics, NC machining, solid modeling, and so on. However, very few algorithms have been proposed to compute Minkowski sum of polyhedra, because computing Minkowski sum boundaries is susceptible to roundoff errors. We propose an algorithm to robustly compute the Minkowski sum boundaries by employing the controlled linear perturbation scheme to prevent numerically ambiguous and degenerate cases from occurring. According to our experiments, our algorithm computes the Minkowski sum boundaries with the precision of 10⁻¹⁴ by perturbing the vertices of the input polyhedra up to 10⁻¹⁰.

참고자료

· 없음