알고리즘 레포트 - 컴퓨터에서 점과 선을 자연스럽게 그릴 수 있는 여러 알고리즘에 대해 조사하고, 각 알고리즘의

I. 서론

그래픽 프로그램에서 마우스로 선을 그으면 화면에는 매끈한 선이 나타나는 듯하지만, 화면을 크게 확대하면 작은 네모 칸이 이어져 있다. 컴퓨터 화면은 연속된 종이가 아니라 정수 좌표를 가진 픽셀의 격자이기 때문이다. 문제는 두 점 사이의 수학적 직선에 실제 픽셀이 무한히 놓일 수 없다는 데서 시작한다. 어느 픽셀을 켜야 원래 선에 가장 가까운지, 계산을 얼마나 적게 하면서 같은 모양을 얻을지, 기울기가 달라져도 선의 두께가 들쭉날쭉하지 않게 할지 판단해야 한다. 여기에 가장자리의 계단 모양을 어떻게 줄일지도 붙는다. 점과 선을 그리는 알고리즘은 그래서 좌표 계산 문제이면서 동시에 사람이 자연스럽다고 느끼는 화면을 만드는 문제다.

II. 본론

1) 연속 좌표를 픽셀로 바꾸는 점과 기본 선분 처리

점은 컴퓨터 그래픽에서 가장 작은 출력 단위처럼 보이지만 실제 처리는 좌표계와 화면 격자를 연결하는 과정이다. 어떤 점의 위치가 정수 좌표라면 대응하는 픽셀을 선택하기 쉽다. 실수 좌표라면 가장 가까운 픽셀 중심으로 반올림하거나 렌더링 규칙에 따라 주변 픽셀에 기여도를 나눌 수 있다. 점 하나를 표시하는 연산은 선이나 다각형의 바탕이 된다. 선분도 결국 어느 픽셀을 차례로 선택할지 결정한 점들의 모음으로 화면에 나타난다. 수학에서는 두 점을 잇는 직선이 끊김 없이 이어지지만 래스터 화면에서는 정수 좌표의 표본으로 바뀌므로 원래 선과 픽셀 중심 사이의 오차를 관리해야 한다.

가장 곧게 떠올릴 수 있는 방법은 직선 방정식을 이용하는 방식이다. 두 끝점에서 기울기와 절편을 구한 뒤 x를 일정하게 증가시키며 y를 계산하거나, 기울기가 가파르면 y를 증가시키며 x를 계산한다. 계산된 실수 좌표를 가까운 정수 좌표로 바꾸고 해당 픽셀을 켜면 선이 된다. 이해하기 쉽다는 장점이 있지만 매 위치마다 곱셈이나 나눗셈이 들어갈 수 있고 반올림도 계속 필요하다. 오래된 하드웨어에서는 그런 계산이 부담이 컸다. 기울기가 아주 크거나 수직선에 가까운 경우에는 x를 기준으로만 처리하는 식이 불안정하므로 진행 축을 바꾸는 조건도 필요하다.

점과 선을 화면에 옮기는 작업을 래스터화라고 부른다. 래스터화의 핵심은 기하학적 모양을 픽셀 집합으로 바꾸는 데 있다. 화면 해상도가 높아지면 픽셀이 작아져 계단 모양이 덜 눈에 띄지만 알고리즘 문제가 사라지는 것은 아니다. 같은 해상도에서도 어떤 픽셀을 고르느냐에 따라 선이 한쪽으로 치우쳐 보이거나 중간에서 두꺼워질 수 있다. 끝점을 포함할지, 같은 선분을 반대 방향으로 그렸을 때 똑같은 픽셀이 나오는지, 서로 이어지는 선분 사이에 틈이 생기지 않는지도 구현 품질에 영향을 준다. 그래픽 알고리즘 수업에서 선 그리기를 오래 다루는 까닭은 작은 문제 안에 수치 계산과 효율, 시각 품질이 함께 들어 있기 때문이다.