선 그리기.

Presentation on theme: "선 그리기."— Presentation transcript:

1 선 그리기

2 Line Equation 기울기 절편 선의 공식: y = m . x + b m = (y2 - y1) / (x2 - x1)
b = y1 - m . X1 y2 (x2,y2) y1 선분의 두 끝점 (x1,y1), (x2,y2)을 알면 기울기 m과 절편 b를 구 할 수 있고, 이 식을 사용하여 x의 위치에 대응하는 y값을 계산하여 두 점을 잇는 선 상에 위치하는 pixel의 위치를 찾아내서 값을 set할 수 있다. (x1,y1) x1 x2 선 그리기

3 DDA(Digital Differential Analyzer) 알고리즘
기준이 되는 축의 단위 값(1)에 대하여 상대 축의 값의 변화량을 계산하여 그 값을 가감 하는 방법을 사용하는 선 그리기 알고리즘 예: 0  기울기  1 인 경우에는 x축 상의 변화량이 y축 상의 변화량보다 크므로 x축을 기준으로 정한다. 시작점의 x값으로부터 출발하여 x값을 1씩 증가 시키면서 이에 대한 y의 변화량을 직전의 y값에 계속 더해 간다. y k+1 = yk + m (m = y : m = y / x 이고 x=1 이므로 m은 x가 1일 변할 때의 y의 변화량이다) 기울기  1 인 경우에는 y축 상의 변화량이 x축 상의 변화량보다 크므로 y축을 기준으로 정한다. 시작점의 y값으로부터 출발하여 y값을 1씩 증가 시키면서 이에 대한 x의 변화량을 직전의 x값에 계속 더해 간다. x k+1 = xk + (1/m) ( (1/m) = y : x = y/m 이고 y 가 1이므로 (1/m)은 y가 1 변할 때의 x의 변화량이다) 그러나 이 방법은 m,(1/m)값이 실 수이고 이를 누적하는 변수(x,y) 또한 실수를 사용해야 하므로 실행 속도면에서 효율적이지 못하다. 또한 변화량에 오차가 있을 경우에는 점점 오차가 누적되어 그리는 선이 제 위치에서 벗어날 수도 있다. 선 그리기

4 Bresenham Line Algorithm
간단한 정수 덧셈만으로 직선상의 pixel의 위치를 계산하는 방법 아래의 그림과 같이 식에 의하여 그려지는 선으로부터 가장 가까이 위치한 pixel을 찾아내는 방법을 사용한다. Raster scan 장치에서는 pixel의 위치가 미리 고정되어 있기 때문에 식에 의해서 그려지는 선 상에 정확하게 일치하는 pixel이 없을 때에는 가장 가까운 위치의 pixel을 사용하여 선을 표현하여야 한다. 따라서 Raster Scan 장치에 사선을 그릴 때에는 옆의 그림과 같이 계단처럼 보이는 jaggi현상이 나타난다. 그러나 이러한 Raster scan장치의 단점을 이용하면 라인을 빨리 그릴 수 있다. 14 식에 의하여 그려져야 할 선의 본래의 방향 13 12 11 10 10 11 12 13 14 선 그리기

5 Bresenham line 알고리즘을 (0 < 기울기 > 1)인 라인을 예로 들어서 설명하면
기울기가 0과 1 사이 라는 것은 라인의 각도가 x축에 대하여 0도에서 45도 사이라는 의미이다. 따라서 옆의 그림에서 현재(10,11)의 위치에 pixel을 set하였다면 그 다음 pixel의 위치는 인접한 두 개의 pixel (그림에서 점선으로 표시) 중 하나 일 것이다. 따라서 우리는 이 두개의 pixel중 어느것이 실제 라인상의 위치에 가까운지를 알아내기만 하면 다음 번에 set될 pixel의 위치를 결정 할 수 있다. 10 xk 11 12 13 yk 11 d1 d2 y = mx + b 선 그리기

6 d2 d1 우리는 우선 d1과 d2의 길이를 알아내야 한다.
(현재 k번째의 점 (xk,yk)를 (x10, y11)에 set하였다고 하고 그 다음 k+1번째의 점(xk+1, yk+1)의 좌표를 찾는다고 할 때: 선의 공식에 의한 실제 선상의 y값: y = m(xk + 1) + b d1의 길이: d1 = y - yk = m(xk + 1) + b - yk d2의 길이: d2 = (yk + 1) - y = yk m(xk + 1) - b d1과 d2의 길이의 차이: d1 - d2 = [m(xk + 1) + b - yk] - [ yk m(xk + 1) - b ] = m(xk + 1) + b - yk - yk m(xk + 1) + b = 2 m(xk + 1) - 2 yk + 2b - 1 위의 식에서 m은 (y / x)로서 실수 값이다. 식에서 실수 값을 제거하기 위하여 m 대신에 (y/ x)를 대입하여 양변에 x를 곱하면 다음과 같은 관계를 얻는다 10 (xk) 11 (xk+1) 12 13 (Yk) 11 (yk+1) 12 d1 d2 y = mx + b 선 그리기

7 d2 d1 m대신 (y/ x)를 대입: d1 - d2 = 2 m(xk + 1) - 2 yk + 2b - 1
= 2 (y / x) (xk + 1) - 2 yk + 2b - 1 양변에 x를 곱하면: x(d1 - d2 ) = 2 y (xk + 1) - 2x yk + 2x b - x = 2 y xk + 2 y - 2x yk + x(2b - 1) = 2 y xk - 2x yk + [ 2 y + x(2b - 1) ] = 2 y xk - 2x yk + C x는 양수 이기때문에 (d1 - d2 ) 에 x를 곱해도 값의 부호는 바뀌지 않는다. 우리가 필요한 것은 (d1 - d2 ) 의 정확한 값이 아니라 d1 과 d2 중에서 어느쪽이 더 가까운가(짧은가)의 여부이기 때문에 부호만이 중요하다. 즉, (d1 - d2 ) 가 음수이면 d1 이 더 짧고 (d1 - d2 ) 가 양수이면 d2 가 더 짧다. pk  x(d1 - d2 ) = 2 y xk - 2x yk + C 로 정의하면 (xk, yk)의 위치에 pixel을 set한 후 pk 의 값을 구하여 pk 가 음수이면 그 다음 pixel (xk+1, yk+1) 의 위치는 (xk + 1, yk) 이고 pk 가 양수이면 다음 pixel의 위치는 (xk + 1, yk+ 1)이 된다. 상수: C 10 (xk) 11 (xk+1) 12 13 (Yk) 11 (yk+1) 12 d1 d2 y = mx + b 선 그리기

8 그 다음 위치 (xk+2, yk+2)의 좌표 값을 구하기 위하여서는 pk+1 의 값을 구하여야 할 것이다.
즉 다음의 식의 값을 구하여야 한다. pk+1 = 2 y xk+1 - 2x yk+1 + C 그러나 이 식의 값을 직접 계산하지 않고 그 앞에서 미리 구한 pk의 값으로부터 쉽게 구 할 수 있다. 즉, pk+1 과 pk의 차이를 구해 보면 pk+1 - pk = [2 y xk+1 - 2x yk+1 + C] - [2 y xk - 2x yk + C] = 2y(xk+1 - xk ) - 2x(yk+1 - yk) + C - C = 2y(xk xk ) - 2x(yk+1 - yk) /* xk+1 = xk + 1 이므로 */ = 2 y - 2x(yk+1 - yk) 따라서 pk+1 = pk + 2 y - 2x(yk+1 - yk) 위 식에서 (yk+1 - yk) 의 값은 pk 가 음수이면 0, 양수이면 1 이므로 pk+1 의 값은 pk가 음수이면: pk+1 = pk + 2y pk가 양수이면: pk+1 = pk + 2y - 2x 2y, 2x 모두 값이 변하지 않는 상수성질의 값이다. 따라서 2y, 2y-2x 의 값을 미리 계산하여 각각 변수에 저장한 후 이전 의 p 값의 부호에 따라서 두 값 중의 하나를 p에 더하면 그 다음의 p값들을 연속적으로 구할 수 있다. 선 그리기

9 최초의 p값(P0)은 다음의 식에 의하여 간단히 구할 수 있다. p0 = 2y x0 - 2x y0 + C
= 2y x0 - 2x y y + x(2b - 1) = 2y x0 - 2x y0 + 2 y + 2x b - x = 2y x0 - 2x [(y/x) x0 + b] + 2 y + 2x b - x = 2y x0 - 2y x0 - 2 x b + 2 y + 2x b - x = 2y - x C y0 이제까지의 내용을 구현하면 알고리즘을 기술하면 다음과 같다. 1. 두 끝점으로부터 x, y를 구하여 2y와 (2y - 2x)의 값을 구하여 변수에 저장한다. 2. 시작점(x0, y0)의 위치에 pixel을 mark하고, pk=0 = 2y - x를 계산한다. 3. (xk, yk) 의 pixel을 mark한 상황에서 pk < 0 이면 그 다음 pixel의 좌표는 (xk + 1, yk) 이고 pk+1 = pk + 2y 그러지 않으면 다음 pixel의 좌표는 (xk + 1, yk+ 1) 이고 pk+1 = pk + 2y - 2x 4. 끝점에 도달할 때까지 3번을 반복한다. 선 그리기

10 예: 두 점(20,10), (30,18) 사이의 선 그리기 19 18 17 16 15 14 13 12 11 10 9 20 21 22 23 24 25 26 27 28 29 30 31 32 33 1 3 2 4 5 6 7 8 k pk (xk+1, yk+1) (21, 11) (22, 12) (23, 12) (24, 13) (25, 14) (26, 15) (27, 16) (28, 16) (29, 17) (30, 18) x = 10, y = 8 2y = 16, 2y - 2x = -4 p0 = 2y - x = 6 앞 페이지의 알고리즘을 사용하여 (20,10)~(30,18) 사이의 라인을 그린 결과 선 그리기

11 선 그리기 함수 line_bres() int line_bres(int x1, int y1, int x2, int y2, float r, float g, float b) { int x, y, dx, dy, d2x, d2y, p, i, s1, s2, interchanged; x = x1; y = y1; dx = abs(x2 - x1); dy = abs(y2 - y1); s1 = sign(x2 - x1); s2 = sign(y2 - y1); interchanged = 0; if(dy > dx) { int temp; temp = dx; dx = dy; dy = temp; interchanged = 1; } 계속 선 그리기

12 선 그리기 함수 line_bres() 계속 계속 d2y = 2*dy; d2x = 2*dx;
p = d2y - dx; /* initial value of p */ set_pixel(x,y,r,g,b); /* first pixel point */ for(i = 0; i < dx; i++) { if(p >= 0) { p = p - d2x; if(interchanged) x = x + s1; else y = y + s2; }/*if p*/ if(interchanged) y = y + s2; else x = x + s1; set_pixel(x, y, r,g,b); p = p + d2y; } /*for i*/ return 1; } 선 그리기