Processing math: 100%

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

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

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

dlower=yyk=m(xk+1)+byk

dupper=(yk+1)y=yk+1m(xk+1)b

이 과정을 실수 연산 없이 판별하는 방법을 알아내자. dlowerdupper의 차이는 

dlowerdupper=2m(xk+1)2yk+2b1

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

pk=Δx(dlowerdupper)=2Δy(xk+1)2Δxyk+Δx(2b1)

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

pk+1=2Δy(xk+1)2Δxyk+1+Δx(2b1)

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

pk+1=pk+2Δy2Δx(yk+1yk)p0=2ΔyΔx

이를 이용하면 시작 픽셀 (x0,y0)에서 p0=2ΔyΔx을 계산하여 0보다 작지 않으면 (xk+1,yk+1) 픽셀에 점을 찍고,  그다음 점찍을 픽셀은  pk+1=pk+2Δy2Δx을 이용해서 판별한다. p0<0 이면 (xk+1,yk) 픽셀에 점을 찍고,  그다음 점을 찍을 픽셀은 pk+1=pk+2Δ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
,