Geometry & Recognition

이미지 상의 한 점은 픽셀로 표현이 된다. 그러나 실제적으로 색을 표시하기 위해서 픽셀은 유한한 크기를 갖는다. 따라서 픽셀이 한 점을 표시한다는 말을 할 때는 실제상으로는 그 점은 픽셀의 중앙을 의미한다고 생각하면 된다. 예를 들어, 점(1, 3)에 색을 칠한다고 하면 엄밀한 의미로는 [0.5,1.5] x [2.5,3.5]로 주어지는 정사각형 영역을 채우는 것을 의미한다. 픽셀을 가지고 작업을 하는 경우는 항상 정수단위로 움직인다. 이런 사실 때문에 원치 않은 결과가 나오기도 한다. 기울기가 매우 작은 직선을 그리는 작업을 생각해 보자. 예를 들면 기울기가 2/10인 경우에 픽셀상에서의 작업은 0부터 4까지는 같은 y=0인 픽셀에, 5, 9까지는 y=1인 픽셀에 칠해야 한다. 실수 값을 다룰 수 없으므로 4와 5를 지나면서 갑자기 계단을 형성하게 된다. 

이러한 계단 현상은 눈에 보이는 그래픽의 품질을 저하시키는 결과를 초래하므로 이것을 피하는 선 그리기 방법이 있어야 한다. 간단히 생각할 수 있는 방법은 블러링을 주는 방법이다. 우선 기울기가 1보다 작은 경우만 생각하자. 나머지의 경우는 대칭을 생각하면 쉽게 확장이 가능하다. 이 상황에서는 x 좌표값이 독립변수의 역할을 하고, y가 종속변수다. 각각의 픽셀(x=정수)에서 y값을 계산하면 일반적으로 실수 값을 갖는다. 이 y값에 가까운 두 개의 정수 y값에 해당하는 픽셀에 색을 칠하는데, 이때 농도는 거리의 차이에 반하도록 잡는다.

     (x, y)  -> (x, int( y ) ),       명암 가중치 = 1 – (y-int(y));

               -> (x, int( y ) + 1 ),  명암 가중치 = y – int(y) ;

처음점과 끝점 좀 더 특별한 처리가 필요하다. 여기서도 역시 블러링의 효과를 주기 위해서 가중치를 주는데 y에 의한 가중치에 덧붙여 x에 의한 가중치도 준다. x가 정수 값을 취할 경우에 50%의 가중치를 주는 것을 기준으로 하면, x + 0.5를 기준으로 이것의 정수 값이 벗어나는 정도를 취하면 된다.  그리고  x의 경우는 가장 가까운 정수에서부터 시작한다.

     (x, y)     ->  (int(x + 0. 5), int(y)),  명암 가중치 = (1 – (y - int(y))) * (1 - (x + 0.5 - int(x + 0.5)))

                  ->  (int(x + 0. 5), int(y) + 1), 명암 가중치 = (y - int(y)) * (1- ( x + 0.5 - int(x + 0.5)))

오른쪽 끝점은 x에서 오는 가중치는 왼쪽의 complement이므로 x+0.5-int(x+0.5)로 바꾸어야 한다.
아래의 그림은 이 알고리즘으로 그린 선분(위)과 Bresenham 알고리즘(아래)을 이용한 선분을 비교한 것이다( 2배로 확대시킨 그림이다)

이 알고리즘은 1991년도에 Wu에 의해서 제시되었다.

#define FPART(x) ((x) - int(x))     // fractional part of (x)
void DrawLine(double x1, double y1, double x2, double y2) {
    if (x2 < x1) {
    	swap(x1, x2); swap(y1, y2);
    }
    double dx = x2 - x1;
    double dy = y2 - y1;
    double grad = dy / dx ;
    if ( fabs(dx) > fabs(dy)) { // 수평에 가까운 선분;
        //(start point)
        int xs = int(x1 + 0.5);                 //x1 에 제일 가까운 정수 xs ;
        double ys = y1 + grad * (xs - x1);      //픽셀점(xs)에서 y값;
        int ixs = xs ;
        int iys = int(ys) ;
        double xgap = 1 - FPART(x1 + .5);   //x1에 의한 가중치
        setPixel(ixs, iys,     (1 - FPART(ys)) * xgap);
        setPixel(ixs, iys + 1, FPART(ys) * xgap);
        //(end point)
        int xe = int(x2 + 0.5);                 //x2에 제일 가까운 정수 xe;
        double ye = y2 + grad * (xe - x2);      //픽셀점(xe)에서의 y값
        xgap = FPART(x2 + .5);
        int ixe = xe; 
        int iye = int(y2);
        setPixel(ixe, iye,    (1 - FPART(ye)) * xgap);
        setPixel(ixe, iye + 1, FPART(ye) * xgap);
        
        //[ixs+1,..., ixe-1];
        double y = ys + grad ;            // 시작(xs) 다음점에서 y-값;
        for (int ix = ixs + 1; ix < ixe; ix++) {
            setPixel(ix, int(y),      1 - FPART(y));
            setPixel(ix, int(y) + 1,  FPART(y));
            y += grad ;
        }
    } else {
        // 이 경우는 x와 y의 역할을 바꾼다;생략;
    };
};

이 함수는 음수가 아닌 인자에 대해서만 성립한다. 그러나 일반적인 경우로도 쉽게 확장이 가능하다.
참고 :
1. http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm
2. http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm
3. http://www.gamedev.net/reference/articles/article382.asp