픽셀 위에 직선 그리는 알고리즘 - 2. Bresenham’s Algorithm, 브레젠헴 알고리즘

픽셀 위에 직선 그리는 알고리즘 - 1. Digital Differential Analyzer (DDA) 알고리즘

서론

 이전에 픽셀에 직선을 그리는 알고리즘으로 DDA 알고리즘을 알아봤었습니다. 글 마지막에 설명한 대로 DDA 알고리즘의 경우 float과 관련한 연산들이 있어 이를 개선해줄 필요가 있었습니다.

 

 여기서 생각을 틀어서 어차피 사각형으로 된 좌표들 위에 픽셀을 찍는 것이니 직선의 경우 (x, y) 에 점을 찍었다면 다음 점은 (x+1, y+1) 이거나 (x+1, y), 2개 중 하나라는 것입니다. 그러니 다음 시점에서 y의 값이 증가를 하는가 안 하는가를 결정해주면 쉽게 진행을 할 수 있다는 것입니다.

 

 

 위 그림을 보면 주황색 직선의 방정식에 대해 (x, y) 픽셀을 칠했다고 하면 다음 점의 y 좌표는 1이 증가하는가 그대로인가 2개 중 하나를 고르게 됩니다. 이때 실제 점의 좌표와의 거리를 보고 비교를 하게 되는데 y+1과 실제 y좌표의 차이를 d_upper, y와의 차이를 d_lower라고 합니다.

 

 

Bresenham’s Algorithm은 정수로 할 수 있는 알고리즘인가? - 최적화가 되어있는가?

여기서 d_lower - d_upper가 양수라면 y+1을 선택하고 음수라면 아래에 있는 점을 선택하면 됩니다. 함수의 식을 y[k] = m*x[k] + b 라고 했을 때 x[k] + 1 에서 아래 식을 구할 수 있게 됩니다.

 

// x[k]+1, y[k]+1 이 선택된 것으로
d_upper = (y[k] + 1) - y = y[k] + 1 - (m*x[k] + b)

// x[k]+1, y[k] 이 선택된 것으로
d_lower = y - y[k] = m*x[k] + b - y[k]

따라서 d_lower - d_upper은
2m*(x[k] + 1) - 2y[k] + 2b - 1 이 됩니다.

 그런데 아직까지 기울기 m이 float 형태로 되어 있고 d도 상수지만 기울기를 통해서 구해야 하므로 아직 float 형태로 되어 있습니다. 이제 이것들을 int형태로 바꿔주기 위해서 decision parameter를 결정해주게 됩니다. 그리고 이걸 Pk 로 부르기로 했습니다.

 

 기존의 d_lower - d_upper의 부호에 따라 결정되기 때문에 Δx를 곱해준다고 해서 다음 찍는 점의 위치가 달라지지는 않습니다. (기울기가 0~1일 때 Δx는 무조건 양수가 되므로) 따라서 Pk = Δx(d_lower - d_upper)로 식을 바꿔주게 됩니다. 이를 식으로 풀어보면

Pk = Δx(d_lower - d_upper)
= 2Δyx[k] - 2Δyy[k] + (2Δy + Δx(2b - 1))
= 2Δyx[k] - 2Δyy[k] + C

 위에서 뒷부분은 항상 상수이니 C 로 통일을 하고 나서 계산을 해주게 됩니다. 여기서 Pk > 0이면 다음 점은 (x[k]+1, y[k] + 1)이 되고 아니라면 다음 점은 (x[k] + 1, y[k])가 됩니다.

 

 일단 현재 우리들이 점을 그리는 곳이 픽셀 좌표계이므로 x는 1만큼 증가하는 unit step의 간격을 가지게 됩니다. 그러니 위 Pk에서 Pk+1의 경우 2Δy(x[k]+1) - 2Δyy[k+1] + C 이 됩니다 (y는 아직 미정).  이를 일반화해주기 위해 Pk+1 - Pk를 해주면

Pk+1 - Pk = 2Δy(x[k+1] - x[k]) - 2Δy(y[k+1] - y[k]) + (C - C)

 위에서 x[k+1] = x[k] + 1 이므로 뒷부분만 고려해주면 되게 됩니다. 그런데 이 Bresenham’s Algorithm을 구하는 이유가 float 연산을 없애기 위함인데 위 식에서 k = 0일 때 값이 정수라면 이후 값들도 전부 정수가 되므로 이 알고리즘의 효율성을 증명하기 위해(정수만으로 됨을 증명) P0가 정수임을 보여야 합니다.

 

 P0의 시점에는 시작점인 x0, y0를 사용하게 됨을 알아둔 뒤 식을 정리해 봅시다. 그리고 b는 기울기 m에 의해서 y - mx = y0 - (Δy/Δx)x0임을 유도할 수 있습니다.

P0 = 2Δy*x0 - 2Δx*y0 + C
= 2Δy*x0 - 2Δx*y0 + 2Δy + Δx(2b - 1)
= 2Δy0*x - 2Δx*y0 + 2Δy + Δx(2(y0 - (Δy/Δx)x0) - 1)
= 2Δy0*x - 2Δx*y0 + 2Δy + 2Δx*y0 - 2Δy*x0 - 2Δx
=  2Δy - 2Δx

 여기서 2Δy - 2Δx는 정수 상수로 결정되므로 P0가 정수임을 알 수 있습니다. 따라서 Bresenham’s Algorithm은 정수 값을 이용한다는 걸 알 수 있습니다. 그럼 남은 건 각 점에서 다음 점을 어떻게 고를지 정하는 것입니다.

 

 

그럼 Decision Parameter  Pk는 어떻게 되는가?

 

 이제 이 알고리즘이 정수를 기반으로 하는 알고리즘임을 알았습니다. 그럼 Pk > 0 이면 다음 점의 y 좌표가 +1 된다고 했는데 이를 구하는 방법은 아래에서 유도할 수 있습니다.

 

Pk+1 = Pk + 2Δy - 2Δx(y[k+1] - y[k])

 위 식을 통해서 이전 pk에서 y축을 증가시켰다고 하면 Pk+1 = Pk + 2Δy - 2Δx가 되어서 이전 값에서 2Δy - 2Δx를 더해주면 되고 y축이 증가하지 않았었다면 2Δy를 더해주면 됩니다.

 

 

이걸 C++로 나타내면?

 

void Bres (int x0, int y0, int xEnd, int yEnd)
{
	int dx = fabs (xEnd - x0), dy = fabs(yEnd - y0);
    int p = 2 * dy - dx;
    int twoDy = 2 * dy, twoDyMinusDx = 2 * (dy - dx);
    int x, y;
    
	// 어디가 왼쪽이고 오른쪽인지
	if (x0 > xEnd) {
      x = xEnd;
      y = yEnd;
      xEnd = x0;
	}
	else {
		x = x0;
		y = y0; 
	}

 	setPixel (x, y);
  	while (x < xEnd) {
		x++;
    	if (p < 0)
			p += twoDy;
		else { 
			y++;
      		p += twoDyMinusDx;
    	}
    setPixel (x, y);
	}
}

 

 

이 알고리즘의 장점

 이전 DDA 알고리즘에 비해서 float 연산이 없는 알고리즘이다 보니 단순 정수의 더하기나 곱하기 연산만 하면 됩니다. 그리고 곱하기도 2를 곱하는 것이라 쉬프트 연산이 가능하므로 전체적으로 빠른 알고리즘이라고 할 수 있습니다.

 그리고 x, y축을 바꿔 주는 것으로 기울기가 1 이하일 그래프 외 다양한 그래프들에 적용이 가능합니다.

 

손필기