등치선(wire-frame contour)으로 표현된 물체의 볼륨정보에서부터 3차원 표면을 재구성하는 것은 의료영상이나 컴퓨터 애니메이션등 다양한 분야에서 매우 중요한 문제이다. 본 논문에서는 물체의 표면 모델을 추출하기 위한 새로운 표면 삼각분할 알고리즘을 제안한다. 일반적으로 이 문제를 해결하기 위한 최적해 방법들은 처리 시간이 매우 많이 걸린다는 단점이 있으며, 경험적 방법들은 인접 등치선의 형태가 상이할 경우 매우 부자연스러운 표면을 만든다는 단점이 있다. 제안된 표면 삼각분할 알고리즘은 인접한 등치선 사이의 표면을 가상의 띠(band)로 생각하고, 이러한 띠를 연속적으로 분할하는 방법으로 표면 모델을 만들게 된다. 이 방법은 등치선의

The surface reconstruction problem from a set of wire-frame contours is very important in diverse fields such as medical imaging or computer animation. In this paper, a surface triangulation method is proposed for solving the problem. Generally, many optimal triangulation techniques suffer from the large computation time but heuristic approaches may produce very unnatural surface when contours are widely different in shape. To compensate the disadvantages of these approaches, we propose a new heuristic triangulation method which iteratively decomposes the surface generation problem from a band (a pair of vertices chain) into two subproblems from two sub-bands. Generally, conventional greedy heuristic contour triangulation algorithm, suffer from the drastic error propagation during surface modeling when the adjacent contours are different in shape. Our divide-and-conquer algorithm, called band partitioning algorithm, processes eccentric parts of the contours first with more global information. Consequently, the resulting facet model becomes more stable and natural even though the shapes are widely different. An interesting property of our method is that it supports multi-resolution capability in surface modeling time. According to experiments, it is proved to be very robust and efficient in many applications.