본문 바로가기

진리는어디에

브레즌햄(Bresenham) 알고리즘

브레즌햄 알고리즘은 컴퓨터 그래픽스에서 복잡하고 계산을 느리게 만드는 실수 계산을 배제하고 정수 계산만으로 직선을 그리기 위해 만들어진 알고리즘 입니다. 직선의 공식을 이용해 계산된 좌표값은 결국 스크린에 표현하기 위해서는 소수점 이하를 버림한다던지 반올림 해서 정수로 만들게 됩니다. 이렇게 버려지는 소수점 이하의 복잡한 계산을 브레즌햄 공식을 이용하여 간단한 정수 연산으로 바꾸는 과정을 알아보도록 하겠습니다.

먼저 두 점을 지나는 직선의 방정식을 보면 아래와 같습니다 :

y - y1 = (x2 - x1) / (y2 - y1) * (x - x1)
y = (x2 - x1)/(y2 - y1) * (x - x1) + y1

예를 들어 (2, 1) 과 (6, 4)를 지나는 직선의 점들 중 x가 3일때 y의 값은

y - 1 = (6 - 2) / (4 - 1) * (3 - 2)
y = 4 / 3 * 1 + 1
y = 2.333333...

와 같이 나올 수 있고 일반적으로 y = mx + n 와 같은 공식으로 표현합니다. 여기서 m은 직선의 기울기, n은 y 절편의 값 입니다.

직선 상에 있는 수많은 점들은 실수 값으로 무수히 표현 될 수 있지만 스크린 상에서 표시할 수 있는 것은 정수 값이므로 직선이 맞닿아 있는 두 값 중에 가까운쪽에 점을 찍어 주면 됩니다.

y축의 두 점 yi와 yi + 1 중간 어느즘에 있을 때 가까운 쪽을 선택하면 됩니다. 위의 예에서는 2.333... 2와 3중에 가까운 2에 y를 좌표를 지정해 줄수 있다는 의미 입니다.

d1 = y - yi
d2 = yi + 1 - y

만일 d1 - d20 보다 작다면 yi 쪽에 가까운 것이고 크다면 yi + 1 쪽에 가까운 것이다. 여기서 우리에게 필요한 것은 d1 - d2가 0보다 큰지 작은지이지 실제 값이 중요한 것은 아닙니다.

다시 브레즌햄 알고리즘으로 돌아가겠습니다. 브레즌햄 알고리즘의 가장 처음은 x축과 y축 중 직선의 시작과 끝에서 변위가 큰 축을 선택하는 것입니다. 변위가 큰축을 기준으로 시작 부터 끝까지 1씩 증가 시키며 다른 축의 값의 가장 가까운 정수 값을 찾는 것입니다.

위의 예 (2, 1) 과 (6, 4)에서 x 축의 변위가 더 크므로 x축으로 1씩 증가하며 y 값을 구해가는 방법을 알아보도록 하겠습니다. 만일 y 축 변위가 더 크다면 x와 y를 반대로 생각하시면 됩니다.

d1 = y - yi
      = m((xi + 1) - x1) + y1 - yi

mx 가 아니라 m(x+1) 이 된 이유는 x 축으로 1증가한 곳의 y를 구하기 때문입니다. 그리고 d2는 아래와 같이 정의 될수 있습니다.

d2 = (yi + 1) - y = yi + 1 - (m((xi + 1) -x1) + y1)
     = yi - m((xi + 1) - x1) - y1 + 1
반응형

그럼 이제 두 거리의 차이를 구해 보겠습니다.

d1 - d2 = m((xi +1) - x1) + y1 - yi - (yi - m((xi + 1) - x1) - y1 + 1)
              = m((xi + 1) - x1) + y1 - yi - yi + m((xi + 1) - x1) + y1 - 1
              = 2m((xi + 1) - x1) + 2y1 - 2yi - 1

또한 위에서 이미 언급한대로 m 은 기울기인 dy/dx 이므로,

d1 -d2 = 2(dy/dx)((xi+1) - x1) + 2y1 - 2yi - 1

와 같이 정의 됩니다.

위에서 dx는 변위 나타내므로 무조건 양수고 우리가 궁금한 것은 d1 - d2가 양수인지 음수인지만 궁급합니다. dx 값을 양변에 곱하여 우항에서 소거 한다고 하더라도 결과는 변하지 않으므로 나눗셈이 있는 부분을 양편에 dx를 곱해서 없애겠습니다.

dx(d1 - d2) = 2dy((xi+1) -x1) + 2dxy1 - 2dxyi - dx
                   = 2dyxi + 2dy - 2dyx1 + 2dxy1 - 2dxyi - dx
                   = 2dyxi - 2dxyi + 2dy - 2dyx1 + 2dxy1 - dx

위 공식에서 변수 부분인 xi 또는 yi가 들어간 부분과, 한번 계산되면 다시 계산할 필요가 없는 상수 부분으로 정리해 보았습니다. 굵은 글씨로 쓰여져 있는 부분이 한번 계산 이후에는 동일한 값을 가지게 되는 상수 부분입니다. 상수 부분을 C로, 실제 값이 필요한게 아닌 부호만이 필요하므로 dx(d1 - d2)를 단순화 해서 변수 pi로 정의하겠습니다.

pi = 2dyxi - 2dxyi + C

위에서 'd1 - d20보다 작다면 yi 쪽에 가까운 것이고 크다면 yi + 1 쪽에 가깝다' 라고 이야기 했습니다. pi 가 음수이면 y는 yi 가 되고 양수이면 yi + 1 가 됩니다.

다음 pi+1은 2dyxi+1 - 2dxyi+1 + C 와 같이 구할 수 있습니다.

그런데 여기서 x는 1씩 증가 합니다. 그러므로 이전 xi+1 - xi 은 1이 되어 위의 2dyxi+1를 부분을 그냥 dy로 변경이 가능합니다. 그리고 지금 우리는 방정식을 풀고 있습니다. 방정식은 가운데 두 양쪽 항이 같은 조건을 만족하면 됩니다. 그래서 우리는 이전 공식 '2dyxi - 2dxyi + C'를 '2dyxi+1 - 2dxyi+1 + C' 에서 빼주고 방정식을 맞추기 위해서 pi+1 에서도 pi 를 빼줍니다. 이 방법을 통해 식을 단순화 할 수 있습니다. 그렇게 나온 결과 공식이 아래입니다.

pi+1 - pi = 2dyxi+1 - 2dxyi+1 + C - (2dyxi - 2dxyi + C)
             = 2dyxi+1 - 2dxyi+1 + C - 2dyxi + 2dxyi - C
             = 2dy(xi+1 - xi) - 2dx(yi+1 - yi)

위에서 이미 말 했듯이

xi+1 - xi는 1이므로 아래와 같이 정리할 수 있습니다.

pi+1 - pi = 2dy(xi+1- xi) - 2dx(yi+1- yi)
             = 2dy - 2dx(yi+1- yi)

이제 pi+1 값만 구한다면,

pi+1 = pi + 2dy - 2dx(yi+1- yi)

pi+1 = 2dyxi+1 - 2dxyi+1 + C 였던 공식이 pi+1 = pi + 2dy - 2dx(yi+1- yi) 와 같이 변경 되었습니다. 여전히 복잡해 보이지만 스크린 좌표는 정수이고 yi+1와 yi의 차이가 0 또는 1이라는 점을 상기한다면 :

  • pi 값이 양수일 경우 d2이 더 가까우므로 다음 점은 현재의 yi 보다 1만큼 큰 값을 가지게 됩니다. 그래서,
    pi+1 = pi + 2dy - 2dx
    가 되며,
  • pi 값이 음수일 경우 d1이 더 가까우므로 다음 점은 yi 값과 같아지고 yi+1 - yi 는 0이 되므로,
    pi+1 = pi + 2dy

처럼 됩니다.

위에서 계산된pi+1 값은 다음 루프의 pi 값이 되므로 이를 루프에서 계속 이용한다고 하면, 처음 p0를 구하고 다음 pi값으로 대입하며 위치를 찾아 점을 찍으면 됩니다.

using System;
using System.Collections;

public class Bresenham2D : IEnumerable
{
    Position start; // http://kukuta.tistory.com/185
    Position end;
        
    public Bresenham2D(Position start, Position end)
    {
        this.start = start;
        this.end = end;
    }
    
    public IEnumerator GetEnumerator()
    {
        int dx = Math.Abs(end.x - start.x); // 시작 점과 끝 점의 각 x 좌표의 거리
        int dy = Math.Abs(end.y - start.y); // 시작 점과 끝 점의 각 y 좌표의 거리
        
        if (dy <= dx)
        {
            int p = 2 * (dy - dx);
            int y = start.y;
            
            int inc_x = 1;
            if (end.x < start.x)
            {
                inc_x = -1;
            }
            
            int inc_y = 1;
            if (end.y < start.y)
            {
                inc_y = -1;
            }
            
            for (int x = start.x; (start.x <= end.x ? x <= end.x : x >= end.x); x += inc_x)
            {
                if (0 >= p)
                {
                    p += 2 * dy;
                }
                else
                {
                    p += 2 * (dy - dx);
                    y += inc_y;
                }
                yield return new Position(x, y);
            }
        }
        else
        {
            int p = 2 * (dx - dy);
            int x = start.x;
            
            int inc_x = 1;
            if (end.x < start.x)
            {
                inc_x = -1;
            }
            
            int inc_y = 1;
            if (end.y < start.y)
            {
                inc_y = -1;
            }
            
            for (int y = start.y; (start.y <= end.y ? y <= end.y : y >= end.y); y += inc_y)
            {
                if (0 >= p)
                {
                    p += 2 * dx;
                }
                else
                {
                    p += 2 * (dx - dy);
                    x += inc_x;
                }
                yield return new Position(x, y);
            }
        }
    }
 }

 

유익한 글이었다면 공감(❤) 버튼 꾹!! 추가 문의 사항은 댓글로!!