간단프로그래밍2011. 12. 20. 15:50


어떤 정수좌표에서 다른 정수좌표로 긋는 선이 있을때

이를 픽셀 (2차원에서) 혹은 복셀( 3차원에서) 로 표현을 하려면

일반적으로는 직선의 방정식을 구하여 , 반올림 하는 식으로

한칸씩 채워 나갈 것이다. 

하지만 실수 계산이 많아 , 이를 전부 정수 계산 및 곱셉을 제거하게 하는

Bresenham 알고리즘이 나오게 되었다.


기본적으로 픽셀을 찍는 원리는 매우 간단하다 



가로 방향이 dx 이고 세로 방향이 dy 라고 할때 

err 변수를 두고 dy만큼을 계속 더해 나간다. 이 값에서 dx 만큼 뺀 양이 

초록색의 너비가 된다.

이때 dx의 절반... 즉 dx/2 을 넘어서느냐 안 넘어서느냐에 따라 

위에 찍히는지 아래에 찍히는지 결정되는 것이다.

넘어서게 되면 다시 dx 만치 빼서 음의 값을 만든다.

매우 간단하다.

그렇지만 또 2로 나누는 나눗셈 과정이 있기 때문에

실제 브레제남 알고리즘에서는 이를 식을 변형해서 미리 2를 곱한 값을 구하고

그 값을 이용하여 구한다.

위의 예는 기준 delta 값이 dx 로 가정하였지만,

실제로 직선이 dy가 더 클 경우도 있다.



더 큰 delta 값을 지니는 축을 기준으로 하여 

다른 축의 delta가 서서히 증가하도록 계산을 하게되면 된다.


이런식으로 계산하면 2차원~ 3차원~ N차원 까지 가능하다.


아래는 3차원 공간에 대해

두 정수좌표를 잇는 직선이 점유하는 복셀을 찾아내는

3차원 브레제남 알고리즘이다.


 




위 예제를 실행하면 아래와 같이 출력된다.

(1, 2, 3) -> (5, -7, 9) 

를 잇는 직선이 차지하는 복셀의 리스트들이다.


Posted by 멍충한아싸

댓글을 달아 주세요