선 그리기를 할 때 그릴 선이 어디 위치에 있는지 구하려면 실수 연산이 필요한데
이를 정수연산으로만 끝낼 수 없을까에서 찾아본 결과 "브레젠험알고리즘"이란 것을 발견하였다.
Bresenham의 선 알고리즘 :
-> 실수 연산이 필요 없고 정수 연산만으로 처리되는 속도가 매우 빠른 래스터 방식
-> 컴퓨터 그래픽에서 선을 긋는 알고리즘.
https://translate.google.co.kr/translate?hl=ko&sl=en&u=https://en.wikipedia.org/wiki/Bresenham%2527s_line_algorithm&prev=search
실수연산이 정수연산에 비해서 매우 느린 것도 이유가 되고,
화면에 그려질 때도 정수단위의 픽셀에 그려지기 때문에 정수 연산만으로 처리하는 것이 더 좋다고 한다.
x의 변화량이 y의 변화량 보다 크다면
위와 같은 그림으로 그려지게 될 텐데 xi와 xi + 1까지는 y값이 더 가깝기 때문에 yi에 점이 그려지고
xi + 2때는 y값이 yi + 1에 더 가깝기 때문에 yi + 1에 그려져야 나름 부드럽게 보이는 선이 만들어지게 된다.
방정식에 의해 나온 y값이 정수값인 yi와 yi + 1중 어디에 가까운지 판단하는 것 부터 생각해보면 된다.
위에 그림처럼 d1과 d2값을 구해 더 차이가 적은 쪽을 선택하면 된다.
직선의 방정식 : mx + b ( m는 기울기, b는 y절편 ) m = dy / dx
d1 = m(xi + 1) + b - yi
d2 = (yi + 1) - m(xi + 1) - b
계산 한 번으로 어디에 가까운지 판단하기 위해서 위에 두 식을 합쳐야 한다.
d1 - d2를 구해 이 값이 0보다 작다면 d1이 작다는 의미로 판단할 수 있고,
0보다 크다면 d2가 더 작다는 것을 알 수 있다.
d1 - d2 = m(xi + 1) + b - yi - (( yi + 1 ) - m(xi + 1) - b )
= m(xi + 1) + b - yi - ( yi + 1 ) + s ( xi + 1) + b
= 2m(xi + 1 ) + 2b - 2yi - 1
식을 x와 y값을 이용해서만 계산할 수 있게 하기위해 m = dy / dx를 넣어 정리해준다.
d1 - d2 = 2(dy / dx) (xi + 1) + 2b - 2yi - 1
해당 값의 부호만 판단하면 되기 때문에 굳이 비용이 많이 드는 나누기 연산을 할 필요가 없다.
따라서 dx를 양변에 곱해준다.
dx(d1 - d2) = 2(dy)xi + 2dy + 2b(dx) - 2(dx)yi - dx
b , dx, dy값은 변화하지 않는 상수이므로 한 번만 계산하면 된다.
위의 식을 다시 이쁘게 정리 해보면,
dx( d1 - d2 ) = 2(dy)xi - 2(dx)yi + 2dy - dx + 2b(dx)
= 2(dy)xi - 2(dx)yi + 2dy + dx(2b - 1)
2dy + dx(2b - 1)로 인해 dx, dy, b의 값을 알 수 있기 때문에 계산을 하고 한 변수에 넣어 두면 된다.
식에서도 보기 쉽게 2dy + dx(2b - 1)를 A로 표현하겠다.
브레젠험 알고리즘은 이전 값을 이용하여 다음 값을 찾는 형식으로 루프를 돌게 되어있다.
이전 값을 Pi라 하고 그 이후의 값을 Pi + 1이라고 하자.
Pi = 2(dy)xi - 2(dx)yi + A
Pi+1 = 2(dy)xi + 1 - 2(dx)yi + 1 + A
이전 Pi값에 계속 값을 더해주어서 다음 값을 찾는 방법을 이용하기 때문에 더해줘야 되는 값을 구하기 위해
Pi + 1에서 Pi를 빼보겠다.
Pi + 1 - Pi - 2(dy)xi+1 - 2(dx)yi + 1 + A - 2(dy)x + 2(dx)y - A
= 2(dy)(xi + 1 - xi) - 2(dx)(yi+1 - yi)
지금은 무조건 한 칸씩 옆으로 가니까 dx가 dy보다 크다고 가정을 한 상태에서 식을 세우고 있기 때문에
xi+1 - xi = 1 이 된다.
대신 y값은 이전과 같은 점일 수도 있고 한 칸 움직인 점일 수도 있다.
그렇기 때문에 위의 식에서 부터 두 가지 경우에 대한 식으로 정리할 수 있다.
1. yi+1 - yi = 0 일 때 : 2(dy) -> Pi + 1 = Pi + 2(dy)
2. yi+1 - yi = 1 일 때 : 2(dy) - 2(dx) -> Pi+1 = Pi + 2(dy) - 2(dx)
이를 통해 다음 P값을 구할 수 있는 식을 구하게 되었다.
현재 상황의 경우에는 처음 점을 (x1, y1)으로 두고 그 다음 점을 (x1 + 1, y1 + 0.5)로 두고 구하면 된다.
x는 1씩 증가하지만 y는 어떻게 될 지 모르기 때문에 절반 값만 넣어주었다.
위의 점화식에 넣고 구해보면 최종적으로 처음 점은 P0 = 2(dy) - (dx)가 나오게 된다.
