Hausdorff Distance Computation Between Triangle Mesh and Quad Mesh

Abstract

본 논문에서는 준정규 사각형 메시의 사용성을 증대시키기 위한 다양한 기하 알고리즘을 소개한다. 우선 기하 연산을 가속화하는 데에 쓰이는 bounding volume hierarchy로 사각형 메시에 특화시킨 새로운 구조를 선보인다. 이를 이용하면 사각형 메시로의 점 투영(최단 거리 계산)을 빠르게 수행할 수 있다. 점 투영은 하우스도르프 거리 계산 및 사각형 메시 재건을 위해 본 논문에서 새롭게 제안하는 알고리즘에서 큰 비중을 차지하는 핵심 연산이다.<br/> <br/> 한 삼각형 메시와 이를 근사하는 사각형 메시 사이의 하우스도르프 거리는 그 근사 품질을 평가할 수 있는 척도이다. 하지만 물체 정합에도 쓰이는 하우스도르프 거리를 계산하는 일은 메시 모델에 대해 늘 매우 어려운 문제이어 왔고 특히 사각형 메시에 대해서는 아예 연구된 바가 없다. 본 논문에서 소개하는 알고리즘은 질의 모델을 반복적으로 분할하고 무관한 조각들을 제거함으로써 하우스도르프 거리가 발생하는 곳과 하우스도르프 거리의 상한과 하한을 점차 좁혀나간다. 하한을 갱신하는 일과 영향력이 없는 모델 조각을 찾아내는 데에 점 투영이 깊게 관여한다. 상호작용 가능한 속도가 달성되었으며 알고리즘의 높은 정확도는 계산 정밀도의 제약만을 받는다. 이는 모델 근사나 물체 정합에 있어서 선호되는 결과인 하우스도르프 거리가 영에 가까운 상황에도 성립하는데, 사실 가장 난이도가 높은 경우이다.<br/> <br/> 또한, 본 논문은 사각형 메시를 생성하는 데에 도움을 주는 인터페이스를 제안한다. 주어진 메시 모델이나 점 구름을 사각형 메시로 변환하기 위해 먼저 사용자가 원하는 사각 레이아웃을 그려넣도록 한다. 인터페이스의 알고리즘은 입력 데이터를 레이아웃의 각 패치에 자동으로 할당하고 이를 근사하는 사각형 메시도 자동으로 생성한다. 사각형 메시를 반복적으로 다듬는 과정에서 점 투영은 다시 한 번 큰 비중을 차지한다. 이 사각형 메시는 앞서 제시된 알고리즘을 통해 계산되는 하우스도르프 거리로 평가할 수 있다.