픽셀 위에서 원을 그리는 알고리즘 - Midpoint Algorithm

서론

 

 이전에 직선 그리는 알고리즘에서 브레젠헴이 만든 알고리즘을 사용을 했는데, 픽셀 위 원을 그리는데도 이 사람의 알고리즘을 사용하게 됩니다. 왜 Midpoint 알고리즘이냐고 묻는다면 대답해드리는 게 인지상정. 그래서 이전의 알고리즘과 비슷하다고 생각을 하면서 보면 좋을 것 같습니다.

 

픽셀 위에 직선 그리는 알고리즘 - 2. Bresenham’s Algorithm, 브레젠헴 알고리즘

 

 기존 선을 그리는 알고리즘을 그대로 적용하게 되면 원에서 Y 증분이 커지는 부분들에서 X + 1 에서 Y 가 급격히 변하게 되므로 구간이 끊기는 문제가 생기게 됩니다. 그래서 이번 미드 포인트 알고리즘을 다루면서 최대한 연산량을 줄여 원을 화면 위에 그리는 방법을 알아보도록 하겠습니다.

 

 

원을 그릴때 8등분을 하자

그림이 좀 못났지만

 

 일단 원을 그리는 방법에 대해서는 위 그림에서 왕관이 그려진 곳의 호를 먼저 그린 뒤 이걸 y축, x 축, y = x, y = -x에 대해서 대칭해주면 됩니다. 알고리즘을 통해서 그려질 (x, y) 좌표가 있다면 이걸 다 대칭 이동하면 되는 것입니다.

 

 그럼 서론에서 이야기한 Y 증분 관련한 문제는 해결이 되었고 그럼 저 왕관이 그려진 호 하나를 어떻게 그리는가 입니다.

 

격자무늬에서 그린 원

 큰 격자무늬에서 파란 점이 이미 그려진 픽셀이라고 하면 다음 점을 그리기 위해서 2가지 후보군이 준비되게 됩니다. 파란색 점의 위치가 (x_k, y_k)라고 가정을 해 봅시다. 그러면 다음 점의 x 좌표는 이전 좌표에서 1이 더해진 모습일 텐데 y 좌표가 "그대로인가, -1 인가" 2가지로 나뉘게 됩니다.

파란 점

 

다음에 올 두 점

  그러면 이 2가지 y 좌표 중 하나를 정해야 할 필요가 있는데 이때 중간점(midpoint)을 사용하게 됩니다. 위 그림에서 보라색으로 표시한 것이 midpoint로 이 좌표를 통해서 판별을 하게 됩니다.

 

midpoint가 원 안에 있다면 y - 1 선택,
그 외의 경우 y 선택

 그러면 여기서 의문이 하나 들게 되는데 이전에 직선 알고리즘에서 소수 계산을 없애기 위해 그 노력을 기울였는데 여기 midpoint에서는 당장 중간점이 y - 1/2라서 이를 개선할 필요가 있습니다. (심지어 원의 방정식은 제곱 연산)

 

 그러기 위해서 여기서 다음 점을 결정하는 decision parameter인 Pk를 사용하게 됩니다.

 그러면 저 pk가 0 이하인지 아닌지 판별을 해야 합니다. 그리고 이 연산들이 정수 계산으로 이루어지는지 봐야 할 필요가 있습니다.(정수 연산이 아니면 비싸니깐)

pk가 0보다 작을때

pk가 0 이상일 때

 일단 정수 판별을 위해서 pk에서 구해지는 다음 두 좌표(pk + 1)에서 pk를 제외하고는 전부 정수 연산으로 이루어지게 됩니다.(x, y가 정수 좌표라는 가정 - 픽셀 위니깐) 그래서 pk만 정수라는 게 판별이 나면 되는데 재귀 함수처럼 따라가다 보면 p0가 정수라면 앞으로의 모든 연산이 전부 정수 연산으로 판별이 됩니다.

 

 일단 위 그림을 참고하면 이 알고리즘에서 처음 시작점은 (0, r)이 되며

원의 방정식에 넣으면 위와 같은 식이 만들어지게 됩니다. 이 decision parameter로 치환을 한 건데 이건 부호를 판별해야 하는 방식입니다. 그런데 5/4에서 1/4는 정수 기준으로 부호에 영향을 줄 수 없게 됩니다. 따라서 이를 제거하면 1 - r 이 되므로 p0를 마치 정수인 것처럼 사용할 수 있게 되고 이후에 나오는 p1, p2, ... , pk도 정수로 판별할 수 있게 됩니다.

 

 그럼 정수로 만들 수 있다는 게 판별되었으니 위에 있는 pk+1 식들을 이용하면 완성이 되게 됩니다.

 

 

결론

midpoint algorithm은 decision parameter pk를 사용,
pk가 0 이상일 때 다음 점 판별 시 2xk - 2yk + 5 더하기
그 외의 경우 2xk + 3 더하기

 알고리즘은 위처럼 정해지게 됩니다. 굳이 코드로 적지 않았는데 현재 대부분 그래픽스 API에서 이런 직선이랑 원을 코드로 그리는 경우는 잘 없으므로 이론만 간단하게 정리를 해 뒀습니다. 혹시 오류난 점이 있다면 댓글로 알려주시면 감사하겠습니다.