jebae's dev blog

브레슨햄 선그리기 알고리즘 (Bresenham's line algorithm)

부동소수점 연산을 사용하지 않고 평면에 직선을 그리는 방법

2019년 05월 05일

선그리기

두 점 (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2) 에 대한 직선의 방정식은 다음과 같이 쓸 수 있습니다.

y−y1=dydx(x−x1)(dy=y2−y1, dx=x2−x1)\begin{aligned} y - y_1 = \frac{dy}{dx}(x - x_1) \\ (dy = y_2 - y_1,\text{ }dx = x_2 - x_1) \end{aligned}

직선의 방정식에 대해 수학적으로 완벽한 선을 그리려면 float 자료형으로 표현해야 합니다. 하지만 컴퓨터 모니터의 픽셀 좌표는 정수형입니다. x,yx, y 좌표를 반올림해서 픽셀을 그리는 방법도 있지만 int 보다 float 을 다루는 것이 느리고 부동 소수점이기 때문에 부정확할 수 있습니다. 컴퓨터 그래픽스에서 흔히 사용하는 브레슨햄 선그리기 알고리즘은 int 자료형만으로 선그리기를 가능케 합니다.





브레슨햄 선그리기 (yiy_i 와 yi+1y_i + 1 의 선택)

브레슨햄 알고리즘은 직선의 기울기가 0과 1 사이일 때를 가정해 정리됩니다. 이후에 다른 가정에서는 변수만 바꾼 후 같은 알고리즘으로 적용가능합니다. 평면 상에 아래와 같은 직선이 그려져 있습니다.

브레슨햄 알고리즘의 핵심은 마킹된 현재 픽셀로부터 다음 픽셀을 어떻게 선택할지의 결정입니다. 기울기가 0과 1 사이이므로 xx 값은 항상 1씩 증가합니다. 그렇다면 매 이터레이션마다 yy 값을 이전과 똑같은 값으로 유지할지 또는 1 증가된 값을 선택할지가 관건이겠습니다. 위 그림에서 가장 왼편 아래 픽셀을 초기값이라 하고 오른쪽으로 갈수록 xx 값이 증가한다고 하겠습니다. 그림의 d1d_1 과 d2d_2 는 실제 직선의 방정식에 대해 각각 yiy_i 와 yi+1y_i + 1 로부터의 거리라 할 수 있습니다. 브레슨햄 알고리즘은 d1d_1과 d2d_2 중 더 작은 경우를 찾고 d1d_1 이 더 작을 경우 yy 값을 유지하고 d2d_2 가 더 작을 경우 yy 값을 1 증가시킵니다.





브레슨햄 선그리기 (점화식)

첫 픽셀의 위치를 (x1,y1)(x_1, y_1), 현재 픽셀의 위치를 (xi,yi)(x_i, y_i) 라 하고 직선의 방정식을 y−y1=dydx(x−x1)y - y_1 = \frac{dy}{dx}(x - x_1) 와 같이 쓰겠습니다. 이 때 d1d_1 과 d2d_2 는 다음과 같이 쓸 수 있습니다.

d1=y−yi=dydx(xi+1−x1)+y1−yid2=yi+1−y=yi+1−{dydx(xi+1−x1)+y1}\begin{aligned} d_1 & = y - y_i \\ & = \frac{dy}{dx} (x_i + 1 - x_1) + y_1 - y_i \\ \\ d_2 & = y_i + 1 - y \\ & = y_i + 1 - \left \{\frac{dy}{dx} (x_i + 1 - x_1) + y_1 \right \} \end{aligned}

위 식의 yy 값에 직선의 방정식을 대입할 때 xi+1x_i + 1 과 대응하는 yy 값을 구해야 하므로 xx 를 xi+1x_i + 1 로 바꿔 씁니다.

d1d_1 과 d2d_2 중 더 큰 값을 구하기 위해서 d1−d2d_1 - d_2 가 0보다 작은지 큰지를 이용할 수 있습니다.

d1−d2=2dydxxi+2dydx−2dydxx1+2y1−2yi−1d_1 - d_2 = 2 \frac{dy}{dx} x_i + 2 \frac{dy}{dx} - 2 \frac{dy}{dx} x_1 + 2 y_1 - 2 y_i - 1

나눗셈을 포함하고 있는 위 식을 그대로 코드로 옮기면 나눗셈 연산으로 인해 연산속도가 감소할 수 있으므로 식의 양변에 dxdx 를 곱합니다.

dx(d1−d2)=2dyxi−2dxyi+2dy−2dyx1+2dxy1−dx=2dyxi−2dxyi+C\begin{aligned} dx(d_1 - d_2) & = 2 dy x_i - 2 dx y_i + 2 dy - 2 dy x_1 + 2 dx y_1 - dx \\ & = 2 dy x_i - 2 dx y_i + C \end{aligned}

식의 우변에서 2dy−2dyx1+2dxy1−dx2 dy - 2 dy x_1 + 2 dx y_1 - dx 은 상수이므로 CC 로 치환해 둡니다. 이제 위 식을 이용해 점화식을 찾아보겠습니다. dx(d1−d2)=2dyxi−2dxyi+Cdx(d_1 - d_2) = 2 dy x_i - 2 dx y_i + C 을 pip_i 라 하고 pi+1−pip_{i + 1} - p_i 를 구해보겠습니다.

pi+1−pi=2dy(xi+1−xi)−2dx(yi+1−yi)p_{i + 1} - p_i = 2 dy (x_{i + 1} - x_i) - 2 dx (y_{i + 1} - y_i)

이 때 xi+1−xix_{i + 1} - x_i 는 항상 1입니다. 만약 pi≤0p_i \le 0 이여서 yi+1=yiy_{i + 1} = y_i 라면 pi+1p_{i + 1} 은 아래와 같이 정리할 수 있습니다.

pi+1=pi+2dyp_{i + 1} = p_i + 2 dy

만약 pi>0p_i > 0 이라면 yi+1=yi+1y_{i + 1} = y_i + 1 이므로 아래와 같이 정리할 수 있습니다.

pi+1=pi+2dy−2dxp_{i + 1} = p_i + 2 dy - 2 dx

점화식에 필요한 초깃값은 ii 에 1을 대입해 구할 수 있습니다.

p1=dx(d1−d2)=2dyx1−2dxy1+2dy−2dyx1+2dxy1−dx=2dy−dx\begin{aligned} p_1 = dx(d_1 - d_2) & = 2 dy x_1 - 2 dx y_1 + 2 dy - 2 dy x_1 + 2 dx y_1 - dx \\ & = 2 dy - dx \end{aligned}

알고리즘을 C 코드로 옮겨 보겠습니다.

typedef struct	s_coord
{
	int			x;
	int			y;
} 				t_coord;

void plot_line_low(t_coord *p1, t_coord *p2, int (*mark_pixel)(t_coord *))
{
	int			dx;
	int			dy;
	int			D;
	t_coord	p;

	p = *p1;
	dx = p2->x - p1->x;
	dy = p2->y - p1->y;
	D = 2 * dy - dx;
	while (p.x <= p2->x)
	{
		mark_pixel(&p);
		if (D > 0)
		{
			p.y += 1;
			D -= 2 * dx;
		}
		D += 2 * dy;
		p.x++;
	}
}

(위 코드에서 mark_pixel 함수는 화면에 직접 마킹하는 함수가 될 수도 있고 단순히 터미널 창에 좌표를 출력하는 함수가 될 수도 있겠습니다.)





브레슨햄 선그리기 (여러 상황에서의 적용)

기울기가 0 과 1 사이인 경우에 대해 점화식과 그 초깃값을 알아보고 코드로 옮겨 보았습니다. 이번에는 기울기가 0 과 -1 사이인 경우를 생각해보겠습니다. 이 경우 직선을 기울기가 0 과 1 사이인 경우로 대체하면(xx 축 대칭) 반대되는 부호에 상관없이 d1−d2d_1 - d_2 는 그대로 이용할 수 있습니다. 대신 d1−d2>0d_1 - d_2 > 0 인 경우 yi+1=yi−1y_{i + 1} = y_i - 1 이 됩니다. 이를 앞서 작성했던 코드에 적용해 보겠습니다.

void plot_line_low(t_coord *p1, t_coord *p2, int (*mark_pixel)(t_coord *))
{
	int			dx;
	int			dy;
	int			yi;
	int			D;
	t_coord	p;

	p = *p1;
	dx = p2->x - p1->x;
	dy = p2->y - p1->y;
	yi = 1;
	if (dy < 0 && (yi = -1))	/* important */
		dy = -dy;				/* important */
	D = 2 * dy - dx;
	while (p.x <= p2->x)
	{
		mark_pixel(&p);
		if (D > 0)
		{
			p.y += yi;
			D -= 2 * dx;
		}
		D += 2 * dy;
		p.x++;
	}
}

이제 기울기가 1 보다 큰 경우를 생각해보겠습니다. 기울기가 1보다 클 경우 yy 값은 항상 1씩 증가하고 xx 값은 이전 픽셀과 같은 값을 유지하거나 1 증가합니다. 따라서 d1d_1 과 d2d_2 를 다음과 같이 쓸 수 있습니다.

d1=x−xi=dxdy(yi+1−y1)+x1−xid2=xi+1−x=xi+1−{dxdy(yi+1−y1)+x1}\begin{aligned} d_1 & = x - x_i \\ & = \frac{dx}{dy} (y_i + 1 - y_1) + x_1 - x_i \\ \\ d_2 & = x_i + 1 - x \\ & = x_i + 1 - \{\frac{dx}{dy} (y_i + 1 - y_1) + x_1\} \end{aligned}

위 식을 이용해 d1−d2d_1 - d_2 를 정리하면 다음과 같습니다.

d1−d2=2dxdyyi+2dxdy−2dxdyy1+2x1−2xi−1d_1 - d_2 = 2 \frac{dx}{dy} y_i + 2 \frac{dx}{dy} - 2 \frac{dx}{dy} y_1 + 2 x_1 - 2 x_i - 1

양변에 dydy 를 곱해주면 다음을 얻습니다.

dy(d1−d2)=2dxyi−2dyxi+2dx−2dxy1+2dyx1−dy=2dxyi−2dyxi+C\begin{aligned} dy(d1 - d2) & = 2 dx y_i - 2 dy x_i + 2 dx - 2 dx y_1 + 2 dy x_1 - dy \\ & = 2 dx y_i - 2 dy x_i + C \end{aligned}

이전과 동일한 절차로 진행하면 다음과 같은 점화식과 초깃값을 얻습니다.

pi+1=pi+2dx−2dy(xi+1−xi)p1=2dx−dy\begin{aligned} p_{i + 1} &= p_i + 2 dx - 2 dy(x_{i + 1} - x_i) \\ p_1 &= 2 dx - dy \end{aligned}

짐작하셨다시피 xx 와 yy 가 모두 전치되었습니다. 아래는 모든 상황에 브레슨햄 알고리즘을 적용한 최종 코드입니다.

# define ABS(N) ((N < 0) ? (-N) : (N))

typedef struct	s_coord
{
	int			x;
	int			y;
} 				t_coord;

static void plot_line_low(t_coord *p1, t_coord *p2, int (*mark_pixel)(t_coord *))
{
	int			dx;
	int			dy;
	int			yi;
	int			D;
	t_coord	p;

	p = *p1;
	dx = p2->x - p1->x;
	dy = p2->y - p1->y;
	yi = 1;
	if (dy < 0 && (yi = -1))
		dy = -dy;
	D = 2 * dy - dx;
	while (p.x <= p2->x)
	{
		mark_pixel(&p);
		if (D > 0)
		{
			p.y += yi;
			D -= 2 * dx;
		}
		D += 2 * dy;
		p.x++;
	}
}

static void plot_line_high(t_coord *p1, t_coord *p2, int (*mark_pixel)(t_coord *))
{
	int			dx;
	int			dy;
	int			xi;
	int			D;
	t_coord	p;

	p = *p1;
	dx = p2->x - p1->x;
	dy = p2->y - p1->y;
	xi = 1;
	if (dx < 0 && (xi = -1))
		dx = -dx;
	D = 2 * dx - dy;
	while (p.y <= p2->y)
	{
		mark_pixel(&p);
		if (D > 0)
		{
			p.x += xi;
			D -= 2 * dy;
		}
		D += 2 * dx;
		p.y++;
	}
}

void plot_line(t_coord *p1, t_coord *p2, int (*mark_pixel)(t_coord *))
{
	if (ABS(p2->x - p1->x) > ABS(p2->y - p1->y))
	{
		if (p2->x > p1->x)
			plot_line_low(p1, p2, mark_pixel);
		else
			plot_line_low(p2, p1, mark_pixel);
	}
	else
	{
		if (p2->y > p1->y)
			plot_line_high(p1, p2, mark_pixel);
		else
			plot_line_high(p2, p1, mark_pixel);
	}
}




출처 및 참고

그래픽스
# 알고리즘# 그래픽스# C