2차원 그래픽스 기본요소와 그리기(1/2)

2차원 그래픽스

2차원 그래픽스의 기본적인 출력요소는 대게 점, 선, 다중선, 다각형, 원, 타원, 곡선, 문자 등으로 구성됩니다.

점과 선

• 점 (Point)

2차원 그래픽스의 모든 그림에는 점과 선이 가장 기본적인 구성요소로 이용되고 있으며 이러한 출력요소들은 래스터 방식의 출력장치에서 픽셀로 표현됩니다. 점의 속성으론 크기(Size), 명암(Intensity) 또는 색상(Color), 모양(Shape)등이 사용되고 있습니다.

• 선(Line)
  

선을 일반적으로 양 끝점으로 정의하며 점의 좌표는 절대좌표 또는 상대좌표를 이용하여 표현합니다. 선의 속성은 실선 점선등을 지정하는 선의 유형(Line Type), 선의 굶기(Width), 선의 명암 또는 색상 그리고 선끝 모양(Line Cap) 등이 있습니다.

선 그리기 알고리즘 (DDA 선 그리기 알고리즘)

래스터 방식의 출력장치에서 모든 그림은 프레임버퍼 내의 픽셀로 표현되므로 그림을 구성하고 있는 모든 선은 최종적으로 픽셀로 변환하여 그려져야합니다. 래스터 출력장치에서 선을 그리기 위한 알고리즘은 여러가지 있는데 그중에 하나가 DDA(Digital Differencetial Analyzer) 선그리기 알고리즘입니다. DDA알고리즘은 선의 주어진 양 끝 좌표로부터 레스터 출력장치로 변환하는 가장 기본적인 알고리즘입니다. DDA 알고리즘은 선의 공식은 y=f(x) 형태로 계산하여 각 픽셀을 구하는 방법입니다. 우선 선의 양끝 점로부터 아래와 같이 선의 공식을 구하게됩니다.

기울기 m 이 0<=m<=1인 경우에는 x값을 매번 1씩 증가 시키면 y 값은 기울기 값인 m만큼 증가하여 위에 있는 그림의 위 2개의 선의 경우가 됩니다. 만약 기울기가 1보다 큰 경우에 x 값을 매번 1씩 증가시키면 y 방향으로 증가되는 값이 m이 1보다 크므로 가장 아래있는 선처럼 픽셀의 사이가 멀어지게됩니다.  따라서 기울기가 1보타 큰 경우에는 x값을 증가시키지 않고 y값을 증가시키게 됩니다. 이러한 원칙을 적용하여 다음과 같이 공식을 유도할 수 있습니다.

1) 초기화

2-1 ) 기울기 -1<m<1 일때 다음 계산을 수행

매번 K+1번째 점에서 (단 )

2-2 ) 기울기 -1>=m  , m>=1 일때 다음 계산을 수행

이 알고리즘은 방향가 증가하는 방향에 따라서 더해주기도 하고 빼기도 하는등 알맞게 조정해서 사용할 수 있습니다.

하지만, DDA 알고리즘은 곱하기가 없어서 연산만을 반복하므로 비교적 계산량이 적은데 소수점(Floating-point) 계산을 해야 하는 부담이 됩니다. 또한 DDA 알고리즘에서 매번 좌표를 구할떄 마다 기울기 m 또는 1/m을 더하여 반올림을 하여 값을 구할 때마다 오차가 축적되는 단점이 있습니다.

선 그리기 알고리즘 (Bresenham 선 그리기 알고리즘)

DDA알고리즘에서는 소수점 계산이 필요한데 비하여 Bresenham이 고안한 알고리즘에서는 소수점 계산없이 정수의 더하기 연산과 시프트 연산만으로 처리되므로 더욱 속도가 빠릅니다. 현재에 사용되는 방법입니다. Bresenham 알고리즘의 기본 개념은 다음과 같습니다. 선 y = mx + c에서이 0과 1사이라고 가정할 때 선을 구성하고 있는 어느 한 점의 다음 점은 반드시 오른쪽 점 또는 오른쪽 바로 위의 점이 됩니다.

위의 그림에서 보듯이 k번쨰 점 의 다음점 은 이거나 또는 입니다. 이때 어느 점을 판단은 원래의 선과 K+1번 째 점에서의 차인값 d1과 d2로 부터 판별식을 계싼하여 결정하게됩니다. k+1번째 점에서의 차이값d1에서 d2를 뺀 값을 구하면

같이 됩니다. 기울기 m의 값은 이므로 위 식의 양변에 를 곱하여 이를 이라 하면

이 되며 이 식에서 에 를 대입하면 과 의 관계식을 구할 수 있습니다.

는 1또는 0이므로 다음과 같은 식을 2개를 얻을 수 있습니다.

또는 

여기서 을 C1으로 하고 를 C2로 하게됩니다.

선의 시작점은 이므로 의 공식으로부터 초기값 을 다음과 같이 구합니다.

이 식에서 초기값 p1을 알면 p2를 구할 수 있고 pk+1은 pk를 통해서 구할 수 있습니다. 따라서 정리하게 되면 Bresenham 선 그리기 알고리즘은 다음과 같이 됩니다.

(기울기가  로 가정)

1) 초기화

시작점의 좌표를 (x1,y1)로 하고 다음 계산을 합니다.

C1 =  , C2 =

2) d1-d2의 판별식 pk의 값에 따라 다음 점의 위치를 아래와 같이 구합니다. ()

인 경우 다음 픽셀 점은 이며 입니다.

인 경우는  다음 픽셀 점은 이며 입니다