화면이나 그림에서 직선을 그리려면 직선의 방정식을 만족하는 모든 픽셀들을 찾으면 된다. 하지만 픽셀의 위치는 연속적인 값이 아니라  이산적이므로 그림에 그려진 직선을 구성하는 픽셀은 그 직선을 표현을 하는 식이 주는 값에 가장 가까운 정수를 찾아서 그린 것이다. 직선을 그리기 위해서 실수 연산을 한 후 정수로 반올림하는 과정이 들어가게 된다. 

Bresenham 알고리즘은 평면 위의 두 점 $(x_0, y_0), (x_1, y_1)$을 연결하는 직선을 정수 연산만을 사용하여 그릴 수 있음을 보여준다. 직선의 방정식은 $y = mx +b$의 형태로 표현이 되고, 두 점이 주어지는 경우 기울기는 $m = \frac {y_1 - y_0}{x_1 - x_0} = \frac {\Delta y}{\Delta x}$, $y-$절편은 $b =y_0 - m  x_0$로 얻을 수 있다. 직선의 기울기가 1보다 크면 $x$와 $x+1$에서 변할 때 종속변수 $y$값의 차이가 커지므로 선이 연속적으로 그려지지 않게 보인다.  이 경우 $y$를 독립변수로 사용하면 되고, 기울기가 음수면 시작과 끝을 바꾸면 된다. 따라서 기울기가 $0\le m \le 1$인 경우만 살펴보면 충분하다. 

이제, $(x_k, y_k)$ 위치에서 직선의 픽셀이 정해진 경우,  $x_{k+1}= x_k + 1$에서 직선식의 값 $y =m (x_k + 1) + b$는 어떤 정수 값으로 대체되어야 하는가? 기울기가 1보다 작으므로 $y$는 구간 $[y_k, y_k +1]$에서 값을 취한다. 즉,  오른쪽 옆이나 오른쪽 위 픽셀에 점을 찍어야 한다. 수식으로는 구간의 아래($d_{lower}$)와 위쪽($d_{upper}$)과의 차이를 비교하여 작은 쪽으로 결정하면 된다:

$$ d_{lower} = y - y_k = m(x_k + 1) +b - y_k$$

$$ d_{upper} = (y_k + 1) - y = y_k + 1 - m (x_k + 1) -b$$

이 과정을 실수 연산 없이 판별하는 방법을 알아내자. $d_{lower}$와 $d_{upper}$의 차이는 

$$ d_{lower} - d_{upper} = 2m (x_k + 1) - 2 y_k + 2b -1$$

로 표현되고, 나눗셈을 하지 않기 위해서 $\Delta x$을 곱한 값을 discriminator로 사용하자:

$$p_k = \Delta x(d_{lower} - d_{upper} )= 2 \Delta y (x_k + 1) - 2 \Delta x y_k  + \Delta x (2b-1)$$

의 꼴로 표현되므로 직선의 정보($\Delta x, \Delta y$)와 현재 점을 찍은 픽셀($x_k, y_k$)을 알면 다음번에 점을 찍을 픽셀을 정수 연산만 가지고 판별할 수 있는 장점이 있다. $k+1$일 때 판별식이

$$ p_{k+1} = 2 \Delta y (x_k + 1)  - 2 \Delta x y_{k+1}  + \Delta x (2b-1)$$

이므로 다음과 같은 recursion relation을 만족한다:

$$p_{k+1} = p_k + 2\Delta y - 2\Delta x  (y_{k+1} - y_k) \\ p_0 = 2\Delta y - \Delta x$$

이를 이용하면 시작 픽셀 $(x_0, y_0)$에서 $p_0 = 2\Delta y - \Delta x$을 계산하여 0보다 작지 않으면 $(x_k + 1, y_k+1)$ 픽셀에 점을 찍고,  그다음 점찍을 픽셀은  $p_{k+1} = p_k + 2\Delta y - 2\Delta x$을 이용해서 판별한다. $p_0 < 0$ 이면 ($x_k +1, y_k$) 픽셀에 점을 찍고,  그다음 점을 찍을 픽셀은 $p_{k+1}= p_k + 2\Delta y$을 계산하여 판별한다.

void BresenhamLine(int x1, int y1, int x2, int y2, DWORD color) {
    int dx = x2 - x1 ;
    int incx = 1;
    if (dx < 0) {
        dx = -dx;
        incx = -1;
    }
    int dy = y2 - y1;
    int incy = 1;
    if (dy < 0) {
        dy = -dy;
        incy = -1;
    }
    setPixel(x1, y1,color);
    if (dx > dy) {
        int p = (dy << 1) - dx;
        while (x1 != x2) {
            if (p >= 0) {
                y1 += incy;
                p -= (dx << 1);
            }
            x1 += incx;
            p += (dy << 1);
            setPixel(x1, y1, color);
        }
    } else {
        int p = (dx << 1) - dy;
        while (y1 != y2) {
            if (p >= 0) {
                x1 += incx;
                p -= (dy << 1);
            }
            y1 += incy;
            p += (dx << 1);
            setPixel(x1, y1, color);
        }
    }
};
728x90

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Rotating Calipers  (3) 2021.03.31
Convex Hull Peeling  (0) 2021.03.29
Graham Scan  (0) 2021.03.28
Posted by helloktk
,

이미지 상의 한 점은 픽셀로 표현이 된다. 그러나 실제적으로 색을 표시하기 위해서 픽셀은 유한한 크기를 갖는다. 따라서 픽셀이 한 점을 표시한다는 말을 할 때는 실제상으로는 그 점은 픽셀의 중앙을 의미한다고 생각하면 된다. 예를 들어, 점(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

728x90

'Computational Geometry' 카테고리의 다른 글

Ellipse Drawing Algorithm  (0) 2008.06.04
Circle Drawing Algorithm  (1) 2008.06.03
Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Posted by helloktk
,