브레젠험(Bresenham's algorithm) 알고리즘이란?
두 점 사이 의 직선에 가까운 근사를 형성하기 위해 선택해야 하는 n차원 래스터의 점을 결정하는 알고리즘입니다. 비트 맵 이미지 (예 : 컴퓨터 화면)에서 선 프리미티브를 그릴 때 주로 사용되며, 정수 추가, 빼기 및 비트 쉬프트 만 사용하므로 표준 컴퓨터 아키텍처에서 매우 저렴한 작업입니다. 증분 오류 알고리즘입니다. 컴퓨터 그래픽 분야에서 개발된 최초의 알고리즘 중 하나입니다. 원 알고리즘을 확장하면 원 그리기에 사용될 수 있습니다.
Wu의 알고리즘과 같은 알고리즘 은 안티 앨리어싱을 지원할 수 있기 때문에 최신 컴퓨터 그래픽에서 자주 사용되지만 Bresenham의 회선 알고리즘의 속도와 단순성은 여전히 중요하다는 것을 의미합니다. 알고리즘은 플로터 및 최신 그래픽 카드의 그래픽 칩과 같은 하드웨어에서 사용됩니다. 또한 많은 소프트웨어 그래픽 라이브러리에서 찾을 수 있습니다. 이 알고리즘은 매우 간단하기 때문에 현대 그래픽 카드의 펌웨어 또는 그래픽 하드웨어에서 구현되는 경우가 많습니다.
"Bresenham"이라는 레이블은 오늘날 Bresenham의 원래 알고리즘을 확장하거나 수정하는 알고리즘 계열에 사용됩니다.
브레젠험 알고리즘의 원리
실수 연산이 필요 없고 정수 연산만으로 처리되는 속도가 매우 빠른 래스터 방식 컴퓨터 그래픽에서 선을 긋는 알고리즘으로, 가로나 세로의 어느 한쪽 좌표를 시작점으로 하여 종료점까지 1씩 가산하여 좌표를 증가시킬 것 인가 또는 그대로 유지할 것인가를 판단합니다.
1. 기울기가 0과 1 사이인 직선을 가정해줍니다.
2. 현재 좌표에서 다음 찍어야 할 좌표값을 구해야 되는데 x는 항상 1만큼 증가하고, y는 Yk, Yk+1 둘 중 하나를 선택합니다. y좌표 선택 판단기준은 중단점 M으로 판별합니다.
3. 중단점 M을 통해 직선보다 위에 존재하면 아래쪽의 칸을 선택하고, 직선보다 아래에 존재하면 위쪽의 칸을 선택합니다.
4. 즉, 중단점 M이 직선의 위에 있냐 아래에 있냐로 다음 점의 위치를 판단한다는 것인데, 그 판별식은 다음과 같은 방법으로 구합니다.
① 그리는 선분의 양 끝점을 입력받습니다. Pa(Xa, Ya), Pb(Xb, Yb)
② 두 점을 이용해서 W값과 H값을 구합니다.
③ 직선의 방정식의 기울기에 대입합니다.
④ 두 점을 이용하여 직선의 방정식을 구합니다.
⑤ 식을 한편으로 정리를 합니다.
5. 도출된 식으로 중단점을 대입하고, 값의 크기를 0과 비교합니다.
이때, 중단점 M은 다음과 같습니다.
이 값을 위의 식에 대입합니다.
이 값을 판별하여, 0보다 크면, 중단점이 직선보다 위에 있으므로, 다음 점의 위치는 다음과 같습니다.
0보다 작으면, 중단점이 직선보다 아래에 있으므로, 다음 점의 위치는 다음과 같습니다.
정리를 하면, 다음과 같은 결과가 됩니다.
일반화를 하면 함수는 다음과 같이 정의됩니다.
'게임 수학' 카테고리의 다른 글
| 프러스텀 컬링 ( 뷰좌표계 ) (0) | 2019.12.18 |
|---|---|
| 왼손 좌표계, 오른손 좌표계 (0) | 2019.12.17 |
| 삼각형 빠르게 칠하기(Flat Shading) (0) | 2019.12.17 |
| NDC(Clip Space)란 무엇인가? (0) | 2019.12.17 |
| 투영 행렬 유도하기 (0) | 2019.12.17 |