등고선으로 표현된 물체의 볼륨정보에서부터 3차원 표면을 재구성하는 새로운 알고리즘을 제안한다. 등고선 삼각분할법이라고도 불리는 이 방법의 가장 어려운 문제가 인접 단층사이에서 표면이 다중으로 분기하는 경우에 발생하는데, 이것은 하나의 등고선이 인접한 층의 두 개 이상의 등고선과 연결되는 형태로 나타나며, 표면 생성시 많은 모호성을 발생시킨다. 본 논문에서는 이러한 다중분기문제를 여러 개의 가상벨트와 가상계곡으로 나누어 이들에 대한 표면생성문제로 단순화 시키는 방법을 제안한다. 가상벨트의 표면생성에는 띠분할 알고리즘을 채택하였으며, 가상계곡은 반복적인 볼록정점 제거와 중앙정점 추가로 보다 자연스러운 표면을 생성한다. 기존의 대부분의 알고리즘특이 다중분기문제를 한 쌍의 등고선간의 표면생성문제로 변환하는데 초점을 맞추는데 비해 제안된 방법은 더 작은 형태인 가상벨트와 가상계곡으로 단순화한다. 또한 제안된 방법은 표면정의에 복잡한 기준을 사용하지 않으며, 표면삼각분할을 위한 매우 명확하고 일관된 알고리즘을 제공한다. 실험을 통해 제안된 방법이 많은 분기가 발생하는 복잡한 데이터에서도 잘 동작하는 것을 알 수 있었다.
This paper addresses a new technique for constructing surface model from a set of wire-frame contours. The most difficult problem of this technique, called contour triangulation, arises when there are many branches on the surface, and causes lots of ambiguities in surface definition process. In this paper, the branching problem is reduced as the surface reconstruction from a set of virtual belts and virtual canyons. To tile the virtual belts, a divide-and-conquer strategy based tiling technique, called the BPA algorithm, is adopted. The virtual canyons are covered naturally by an iterative convex removal algorithm with addition of a center vertex for each branching surface. Compared with most of the previous works reducing the multiple branching problem into a set of tiling problems between contours, our method can handle the problem more easily by transforming it into more simple topology, the virtual belt and the virtual canyon. Furthermore, the proposed method does not involve any set of complicated criteria, and provides a simple and robust algorithm for surface triangulation. The result shows that our method works well even though there are many complicated branches in the object.
