삼각형 메시와 사각형 메시 사이의 영에 가까운 하우스도르프 거리 계산 (Computation of Near-Zero Hausdorff Distance Between Triangle Mesh and Quad Mesh)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 / 46권 / 2호 / 116 ~ 121페이지
· 저자명 : 강윤구, 윤승현, 경민호, 김명수

초록

두 물체 사이의 하우스도르프 거리는 유사성의 척도로 사용될 수 있지만 하우스도르프 거리의 정확한 계산은 매우 어려운 문제이며 두 물체가 유사할수록 더욱 복잡해진다. 하우스도르프 거리가 나타나는 위치를 쉽사리 특정 짓기가 어렵기 때문이다. 본 논문에서는 이러한 장애를 극복하고 삼각형 메시 모델과 사각형 메시 모델 사이의 하우스도르프 거리를 빠르고 정확하게 계산하는 알고리즘을 소개한다. 모델을 작은 조각으로 분할하고 영향력이 없는 조각들을 제거하는 작업을 반복해 하우스도르프 거리가 발생하는 위치를 좁혀나간다. 각 조각에 대해 “대응 곡면”을 생각하고 그에 따른 하우스도르프 거리 상한을 계산함으로써 그 조각의 보존 여부를 판단할 수 있다. 이렇게 구한 하우스도르프 거리를 활용하면 삼각형 메시를 근사하는 사각형 메시의 유사도를 평가할 수 있다.

영어초록

The Hausdorff distance between two objects can be used as a measure for their similarity, but its precise computation is a significantly challenging problem that is as complex as the objects are similar, since it is more difficult to locate where the Hausdorff distance occurs. In this paper, we solve this obstacle and present an algorithm that precisely computes the Hausdorff distance between a triangle mesh model and a quad mesh model. We narrow down where the Hausdorff distance occurs by iteratively partitioning the models into smaller pieces and removing irrelevant ones.
The “match” that we set for each piece and its corresponding upper bound for the Hausdorff distance enable us to decide whether to keep the piece. The Hausdorff distance thus computed can be used to evaluate quad meshes that approximate triangle meshes.

참고자료

· 없음