와이어프레임 형태의 등가면의 생성과 조작을 위한 O(n) 알고리즘

Abstract

등가면과 같이 복잡한 3차원 물체를 연구하기 위하여는 회전, 확대, 이동 등의 조작이 대회식의 사용자 인터페이스와 실시간에 가까운 속도록 이루어져야 할 필요가 있다. 따라서 와이어프레임 형태의 등가면을 연구하기 위하여는 등가면의 빠른 생성도 중요하고 동시에 조작을 빨리 할 수 있어야 한다. 와이어프레임 형태의 등가면은 2차원의 등가선을 생성하는 알고리즘을 반복해서 사용하므로, 효율적인 2차원 등가선 알고리즘을 찾아야 한다. 이 글에서는 기존의 세가지 알고리즘을 분석하였고, 등가선의 생성과 조작에 모두 효율적인 알고리즘을 개발하여 소개한다. 그 새로운 알고리즘은 등가선 생성에 O(n)의 계산량을 소모하면서도, 생성된 등가면을 화면상에서 조작할 때에 벡터처리 (Vectorization)가 가능하여 그 조작 성능이 좋다.