브레젠험 알고리즘이란?
DDA 알고리즘의 발전형으로 선을 찍기 위해 만든 알고리즘이다.
모니터 상에 우리가 찍는 선은 다음과 같이 표현된다.
여기서 우리가 그리고자 하는 선은 빨간색이고, 각 네모가 실제 픽셀이다. 따라서 각 픽셀의 조정을 통해 선을 표기해야 한다.
그럼, 픽셀의 조정을 무슨 수로 해야하는가?
픽셀의 조정
다음과 같은 상황이 있다고 쳐보자.
이때, 그 다음 칸은 보라색을 칠해야 하는가? 아니면 초록색을 칠해야 하는가?
이를 판별식을 통해 보는 것이 바로 브레젠험 알고리즘이다.
판별식 만들기
목표하는 점과 점 사이의 직선의 기울기에 따라 2가지로 나뉜다.
0 < (기울기) < 1 인 경우
- x값은 자동적으로 증가한다.
- 그러나, y값은 증가할수도, 그 전 픽셀의 y값을 그대로 찍을 수도 있다
- 이를 결정하는 것은 F(m_k)로 나오는 판별값이다.
또, k가 증가함에 따라 다음과 같이 판별값 도출식을 일반화할 수 있다.
\begin{align*}
\text{if. } F(m_k)& \text{ 가 양수인 경우}
\\[5pt]
F(m_{k+1}) &= F(m_k) + 2(y2 - y1)
\\[10pt]
\text{if. } F(m_k)& \text{ 가 음수인 경우}
\\[5pt]
F(m_{k+1}) &= F(m_k) + 2(y2 - y1) - 2(x2 - x1)
\end{align*}
1 < (기울기) 인 경우
- y값은 자동적으로 증가한다.
- 그러나, x값은 증가할수도, 그 전 픽셀의 x값을 그대로 찍을 수도 있다
- 이를 결정하는 것은 F(m_k)로 나오는 판별값이다.
또, k가 증가함에 따라 다음과 같이 판별값 도출식을 일반화할 수 있다.
\begin{align*}
\text{if. } F(m_k)& \text{ 가 양수인 경우}
\\[5pt]
F(m_{k+1}) &= F(m_k) + 2(x2 - x1)
\\[10pt]
\text{if. } F(m_k)& \text{ 가 음수인 경우}
\\[5pt]
F(m_{k+1}) &= F(m_k) + 2(x2 - x1) - 2(y2 - y1)
\end{align*}