[CGs] Scan Converting Lines

📖 Scan Converting Lines

• $x$ or $y$ 증가시키면서 픽셀을 하나씩 선택
• 선택 대상은 인접한 2개의 픽셀 중 1개를 선택
• 정확히 일치하는 픽셀은 있을 수 없음

📌 Midpoint Line Algorithm

• P의 다음 픽셀이 어떤것이 올지 정하는 알고리즘
• 선분 함수에 중점 M 위치를 집어 넣어 이것이 NE(North East) 픽셀을 뜻하는지, E(East) 픽셀을 뜻하는지 정하는 알고리즘이다

• F는 직선의 음함수 표기법이다.
• 직선의 기울기는 y의 증가량 / x의 증가량 이다.
• 변수 d는 직선에 대한 중점 M의 상대적 위치를 나타내는 값이다

• d>0이면, 직선 F는 중점 M보다 더 위쪽에 있다는 뜻이므로 NE를 뜻한다

• d<0이면, 직선 F는 중점 M보다 더 아래쪽에 있다는 뜻이므로 E를 뜻한다

• d=0이면, 직선 F는 정확히 M을 지난다. 따라서 NE와 E 둘 중 아무거나 선택 가능하다.
  대신 알고리즘은 일정해야 하므로 다음에 d = 0일때도 똑같은 방식을 적용해야 한다

맨 처음 d값은 시작점 $(x_{0},y_{0})$으로 계산한다.

• 첫 $M$값 기준, $a(x_{0}+1)+b(y_{0}+{1\over2})+c$이고, 이는 $F(x_{0},y_{0})+a+{b\over2}$이다

• 직선상의 한 점은 무조건 0이 되므로 $F(x_{0},y_{0}) = 0$ 이다.

• 이 말은, 첫 $M$값 기준 $d$ 값은 $dy-{dx\over2}$라는 뜻이다.

만약 $E$가 선택될 경우 다음 $M$의 좌표는 $(x_{p}+2,y_{p}+{1 \over 2})$이 되고, 이는 $a(x_{p}+2)+b(y_{p}+{1 \over 2})+c$이다

• 이를 풀어서 계산해보면 $d_{new} =$ $d_{old}+a$이다

• 즉 $E$가 채택되고 다음 $M$값에 대한 $d$값 증가량은 $dy$라는 뜻이다

만약 $NE$가 선택될 경우 다음 $M$의 좌표는 $(x_{p}+2,y_{p}+{3 \over 2})$이 되고, 이는 $a(x_{p}+2)+b(y_{p}+{3 \over 2})+c$이다

• 이를 풀어서 계산해보면 $d_{new}=$ $d_{old}+a+b$이다

• 즉 $E$가 채택되고 다음 $M$값에 대한 $d$값 증가량은 $dy-dx$라는 뜻이다$(a=dy,b=-dx)$

---

`대화형 레스터 그래픽에서는 처리 속도가 생명이므로 정수형 연산으로만 이루어진 스캔 변환 알고리즘을 구현하는 것이 중요하다. 따라서 알고리즘을 정수형태로 변환하기 쉽게 만들어 주어야한다.

void MidpointLine(int x0, int y0, int x1, int y1, int value) {
	int dx, dy, incrE, incrNE, d, x, y;
	dx = x1 - x0;
	dy = y1 - y0;
    				//나눗셈은 오차가 많이 발생함으로 2를 곱해서 없애줌
	d =dy*2 - dx;	//맨 처음 M값에 대한 d값, 이 값의 절대값은 필요없고 오직 부호만 알면되니 2를 곱해도 상관없음
	incrE=dy*2;		//E가 채택되고 다음 M값에 대한 d값 증가량
	incrNE=(dy-dx)*2;	//NE가 채택되고 다음 M값에 대한 d값 증가량
	x = x0;
	y = y0;
	WritePixel(x, y, value); //시작 pixel
	while(x<x1) {
		if (d <= 0) { //E를 선택한 경우
			d += incrE;
			x++;
		}
		else { //NE를 선택한 경우
			d += incrNE;
			x++;
			y++;
		}
		WritePixel(x, y, value); //선택된 픽셀 그리기
	}
}

• 위의 알고리즘을 적용하여 이런 결과가 나온다.
• $0$일때는 $E$와 $NE$ 모두 선택 가능하나 여기서는 $E$를 선택했음.

스캔 변환 방향이 반대방향에서 시작한다면 고려해야할 사항은?

• $d$가 $0$일때 $SW$를 선택해야 한다.
• 끝점 순서(스캔 변환 방향)와 관계없이 동일한 결과가 나와야한다.

$Line$ $B$의 기울기는 $45^o$ 즉, 1이므로 픽셀들간의 거리가 멀어서 밝기의 불균형이 일어나게 된다.
이는 하드웨어적인 해상도를 높이는 것으로는 해결되지 않는다.

📌 Summary

• 도형의 기하학적 속성과 달리 그래픽 도형은 스캔 변환 시에 추가적으로 고려할 사항이 있다.
• 예를 들면 선분의 스캔 변환은 선분의 기울기(slope)나 두 끝점(endpoint)이 주어지는 순서에 따른 고려사항이 알고리즘에 반영되어야 한다.
• 대화형 래스터그래픽(interactive raster graphics)에서는 처리 속도가생명이므로 정수형 연산만으로 이루어진 스캔 변환 알고리즘을 구현하는 것이 중요하다.