선 그리기 알고리즘 - 브레젠험 알고리즘

- 개요

직선의 방정식

 

위와 같이 정의된 직선의 방정식을 사용하면 점 P2부터 시작하여 점 P1까지 점이 연결된 선분이 완성된다

그러나 점을 찍을 모니터 화면은 정수 좌표로 구성되어 있으므로 픽셀에 대응하는 여러개의 벡터가 생성된다

따라서 선을 구성하는 픽셀만 얻어내는 방법이 있다면 효과적으로 선을 그릴 수 있다

이런 상황에서 사용할 수 있는 방법이 브레젠험 알고리즘이다

 

- 브레젠험 알고리즘이란?

이미지 출처 : https://www.geeksforgeeks.org/c/bresenhams-circle-drawing-algorithm/

 

브레젠험 알고리즘은 화면을 8등분 영역으로 구분하여 각 영역별로 그려나가는 방식을 사용한다

해당 알고리즘은 Y축이 아래로 증가하는 스크린 좌표계에서 구현하므로 시계 방향으로 회전한다

 

- 1팔분면에 대한 분석

1팔분면에서 점의 진행

 

1팔분면은 0°~45°의 범위를 갖고 있는데, 따라서 1팔분면에 존재하는 모든 선의 기울기가 1을 넘을 수 없다

이러한 성질로 인해 1팔분면을 구성하는 점의 진행은 위와 같은 특징이 있다

 

- 1팔분면을 통한 브레젠험 알고리즘의 원리 파악

선분을 그리기 위한 기본 설정

 

정수로 변환된 두 점의 스크린 좌표가 주어질 때 첫 번째 시작점의 정수 좌표를 (x0, y0)으로 표기하고

선분의 너비와 높이를 위와 같이 w와 h로 지정하였다

 

두 번째 픽셀의 위치 판별

 

시작 위치의 픽셀에서 다음에 찍을 픽셀의 x 좌표는 x0 + 1로 구할 수 있지만,

y 좌표는 y0 또는 y0 + 1의 두 가지 경우가 존재한다

이 중에서 하나를 선택하기 위해 중간값인 0.5를 사용하는 것이 브레젠험 알고리즘의 기본 원리이다

따라서 브레젠험 알고리즘을 중점 알고리즘이라고 표현한다

이때 그릴 선이 중간값을 지닌 점보다 위에 있는지 아래에 있는지를 판단하면 된다

 

픽셀의 위치를 계산하는 식

 

그릴 선의 y 값을 y0 + 0.5의 값과 비교하여 결과값에 따라 다음과 같이 동작한다

• 그릴 선의 y값 < y0 + 0.5 : 수평으로 선을 그려 픽셀을 찍는다
• 그릴 선의 y 값 > y0 + 0.5 : 대각선 방향으로 선을 그려 픽셀을 찍는다

 

비교하는 식을 정리하면 위와 같이 높이와 너비를 통해 그릴 픽셀의 위치를 계산할 수 있다

마찬가지로 결과값에 따라 다음과 같이 동작한다

• 2h - w < 0 : 수평으로 선을 그려 픽셀을 찍는다
• 2h - w > 0 : 대각선 방향으로 선을 그려 픽셀을 찍는다

 

1팔분면의 각 중점에서의 판별식

 

1팔분면에서 각 중점별로 픽셀의 위치를 계산하는 식을 적용하면 위와 같이 정리할 수 있다

 

- 최종 정리

최종적으로 정리하면 다음과 같다

• 다음으로 그릴 픽셀의 x 값이 증가할수록 판별식을 2h만큼 증가
• 다음으로 그릴 픽셀의 y 값이 증가할수록 판별식을 2w만큼 감소
• 판별식을 팔분면에 따라 수정하는 것이 가능
  • 2팔분면의 경우 2w - h로 변경하여 사용