DDA알고리즘
Digital: 디지털 방식을 쓰는
Differential: 차이, 격차
Analyzer: 분석자, 분해자, 분석적으로 검토하는 사람, 분석기
디지트(digit)는 사람의 손가락이나 동물의 발가락이라는 의미에서 유래한 말.
아날로그와 대응되는 의미로, 임의의 시간에서 값이 최소값의 정수배로 되어 있고,
그 이외의 중간값을 취하지 않는 양을 가리킴. 중요, DDA알고리즘의 핵심
구체적인 예로, 디지털 시계가 있음.
데이터를 한 자리씩 끊어서 다루므로 애매모호한 점이 없고 정밀도를 높일 수 있음
래스터 방식의 출력장치에서 모든 그림은 프레임버퍼 내의 픽셸로 표현되므로 그림을 구성하고 있는 모든 선은 최종적으로 픽셸로 변환하여 그려져야 함. 래스터 출력장치에서 선을 그리기 위한 알고리즘은 여러가지가 있는데 그 중에 하나가 DDA 선그리기 알고리즘. DDA알고리즘은 선의 주어진 양 끝 좌표로부터 레스터 출력장치로 변환하는 가장 기본적인 알고리즘임. DDA알고리즘은 선의 공식은 y=f(x) 형태로 계산하여 각 픽셸을 구하는 방법. 아주 간단히 말하면, 선분이 지나가는 픽셀을 찾아 내는 것. 우선 선의 양끝 점 (x1, y1)과 (x2, y2)로부터 아래와 같이 선의 공식을 구함.
y = mx + c (m = (y2-y1)/(x2-x1))
기울기 m이 0<=m<=1인 경우에는 x값을 매번 1씩 증가 시키면 y값은 기울기 값인 m만큼 증가함.
만약 기울기가 1보다 큰 경우 x값을 매번 1씩 증가시키면 y방향으로 증가되는 값이 m이 1보다 크므로 픽셀 사이가 멀어짐.
기울기가 m인 직선 y=0.5x 을 픽셀상에 그리려고 한다면. 첫번째 픽셀 x=1일때 y=0.5, x=2일때 y=1, x=3일때 y=1.5. 픽셀의 좌표는 정수로만 이루어져있으므로, 함수의 y 값을 반올림해서 2D 픽셀에 나타내면 아래와 같이 나타낼 수 있음. (@: 색칠된 픽셀, _ :색칠 안된 픽셀)
_ _ _ _ @ @
_ _ @ @ _ _
@ @ _ _ _ _
그런데 만약 기울기가 가파르다면, 예를들어 y=3x라면 x값에 따라 y 값을 결정하면 다음처럼 띄엄띄엄 그려지게 됨.
_ _ _ @
_ _ _ _
_ _ _ _
_ _ @ _
_ _ _ _
_ _ _ _
_ @ _ _
_ _ _ _
_ _ _ _
@ _ _ _
이때는 y 값을 1씩 증가시키면서 그에 따른 x 값을 구하는게 낫다.
_ _ _ @
_ _ @ _
_ _ @ _
_ _ @ _
_ @ _ _
_ @ _ _
_ @ _ _
@ _ _ _
@ _ _ _
@ _ _ _
즉 기울기의 절대값이 1이하인 경우는 x 값을 1씩, 기울기 절대값이 1 이상인 경우는 y값을 1씩 증가시키면서 해당되는 픽셀을 찾아내는 방법.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
float m= (y2-y1)/(x2-x1)
float mInv = 1/m;
int x = 0;
int y = 0;
if(abs(m) < 1)
{
for( x=x1; x<=x2;++x){
y+=m;
setPixel(x, round(y));
}
}else{
for( y=y1; y<=y2; ++y){
x+=mInv;
setPixel(round(x), y);
}
}